Given a weighted graph $G=(V,E)$ and given two integers $n$ and $k$, I want to find (if they exist) $n$ nodes such that the sum $S$ of all the edges incident to such $n$ nodes is smaller than $k$. Of course, if an edge has both extremes in the $n$ nodes, its contribution to $S$ must be taken into account just once.
How can we retrieve such $n$ nodes whose sum $S$ is smaller than $k$?
I believe what you have stated is a variation of the Cheeger / isoperimetric problem. It is helpful to analyze it by posing a corresponding integer programming problem. Let $E\in\{0,1\}^{m\times n}$ and $F\in\{-1,0,1\}^{m\times n}$ be the undirected and directed incidence matrices of the graph respectively, \begin{align*} E(e,v) & =\begin{cases} 1 & \text{edge }e\text{ hits vertex }v\\ 0 & \text{otherwise} \end{cases},\\ F(e,v) & =\begin{cases} 1 & \text{edge }e\text{ starts at vertex }v\\ -1 & \text{edge }e\text{ ends at vertex }v\\ 0 & \text{otherwise} \end{cases}, \end{align*} and let $W\in\mathbb{R}^{m\times m}$ be the weight matrix, $$ W(e,e)=\text{weight of edge }e. $$ Then given the support vector of a vertex set, $x\in\{0,1\}^{n}$, the weight of the corresponding edge set hit by the vertex set is $\frac{1}{2}(\|WEx\|_{1}+\|WFx\|_{1})$. To see this, note that $\|WEx\|_{1}$ will give the total sum of the edges hit by $x$, but will double count the interior edges, i.e. if $e=\{v_{1},v_{2}\}$, then selecting $v_{1}$ and $v_{2}$ will count the weight of $e$ twice. Conversely, $\|WFx\|_{1}$ will only give the total sum of the boundary edges, i.e. if $e=\{v_{1},v_{2}\}$, then selecting $v_{1}$ and $v_{2}$ will not count the weight of $e$ at all.
Hence if the specified vertex set exists, it will be found by the binary linear integer program, $$ x_{opt}=\{\arg\min\,\|WEx\|_{1}+\|WFx\|_{1}:\sum_{i=1}^{n}x_{i}=n,x\in\{0,1\}^{n}\}, $$ and the $l_{1}$ norm can be converted into linear objective and constraints using standard techniques. If the objective is less than $2k$, then $x_{opt}$ satisfies the original constraints; if not, then it is the closest vertex set to satisfying the constraints. For smaller graphs, we may directly solve the integer program using branch-and-cut as the algorithm, and for medium-sized graphs, we may augment branch-and-cut with a good search heuristic.
Next, to consider the issue of building an algorithm with a good asymptotic complexity, note that one way to see the problem is a MINIMAL RESTRICTED CUTSET (aka "MIN K-CUTSET") problem with the cost function $\|WFx\|_1$ and $\|x\|_1$ constraint, but "regularized" by the monotonic cost function $\|WEx\|_1$. Indeed, most of the difficulties of the problem comes from its relation to the cut problem. Fortunately, MIN K-CUTSET is also a fairly well-studied problem, due to its relation to the isoperimetric cut. It should be possible to adopt existing algorithms designed for the isoperimetric problem.