Spectral clustering finds groups in a network by computing a few eigenvectors of a matrix built from the graph, placing each node at a point given by its eigenvector entries, and running $k$-means on those points. On sparse networks with very uneven degrees, such as social graphs where a few nodes have thousands of links and most have a handful, this breaks in two places. First, the eigenvectors stop describing communities. They pile their weight onto one hub or onto small tree-shaped fringes hanging off the graph by a single edge. This failure is called eigenvector localization. Second, even when the matrix is repaired so the eigenvectors spread over communities again, the final step of turning coordinates into $k$ discrete groups is still an unprincipled $k$-means call. That call can fail, and it carries no guarantee and no way to tell how far its answer is from optimal.
We propose to replace that last step with a small linear program from the Sherali-Adams hierarchy. The hierarchy tightens a relaxation by demanding that the fractional values on every small group of variables look like a genuine probability distribution over discrete labelings. The repaired eigenvectors are used only to choose a few anchor nodes per community, on which the program is conditioned. The claim is that one mechanism explains both failures. A multi-way linear program on a sparse graph is useless until its symmetric "everything fractionally in every cluster" solution is broken by conditioning on a few nodes. Localization is exactly what makes naive eigenvectors pick the wrong nodes to condition on: hubs and fringe trees. Delocalized anchors plus a low-level, sparsity-restricted lift should give partitions at least as accurate as Bethe-Hessian with $k$-means. They should also give a per-instance lower bound on the cut objective, which no spectral pipeline in the literature provides.
Core Claim
Take a graph $G=(V,E)$ with $n$ nodes, $m$ edges and a target of $k$ groups. The sparse Sherali-Adams relaxation has local distributions $p_S$ over labelings of small node sets $S$. Here $S$ ranges only over edges, triangles and radius-one stars of low-degree nodes, not over all subsets, so its size is $O(m k^2)$ plus a term for triangles, which are rare in sparse graphs. The objective is the expected number of cut edges,
$$\min_{p}\ \sum_{(u,v)\in E} \Pr_{p_{uv}}[x_u \neq x_v] \quad \text{s.t. local consistency,}\ \ \sum_{u} d_u\, p_u(i) \ \ge\ \beta\,\tfrac{\mathrm{vol}(V)}{k}\ \ \forall i,$$
where $x_u$ is the label of node $u$, $p_u(i)$ is its marginal probability of label $i$, $d_u$ is its degree, $\mathrm{vol}(V)=2m$, and $\beta\in(0,1]$ is a loose lower bound on cluster volume.
As written, this program has optimum zero. It is solved by the mixture "all nodes in cluster 1, or all in cluster 2, …", which is locally consistent at every level and satisfies the averaged volume constraint. This is the multi-way form of the size-unknown gap that Louis and Makarychev found for assignment SDPs of sparsest $k$-partitioning. The standard Sherali-Adams remedy is conditioning. Fixing the labels of a few variables collapses such mixtures, which is what the MakeIndependent step of Avdiukhin et al. does to decorrelate local distributions before rounding.
The proposal conditions on anchor sets $T_1,\dots,T_k$, meaning small groups of nodes forced to labels $1,\dots,k$. The anchors are chosen as the nodes with the largest confident mass in the negative-eigenvalue eigenvectors of the Bethe-Hessian $H(r)=(r^2-1)I - rA + D$, with $r=\zeta$ as in Dall'Amico et al.. Here $A$ is the adjacency matrix and $D$ the diagonal matrix of degrees. The number of negative eigenvalues also supplies $k$, following Saade et al. and the consistency proof of Stephan and Zhu.
With anchors fixed, the program becomes a strengthened multiway-cut linear program, which has well-studied rounding. Its optimum is a valid lower bound on the cut of any partition that respects those anchors.
We make three predictions. First, fringe trees are resolved integrally for free. Local consistency over edges is exact on trees, and Conditions beyond treewidth for tightness of higher-order LP relaxations gives conditions under which such relaxations are tight beyond trees, while the bounded-treewidth sparsest cut work shows the same lifting logic is exact on low-treewidth pieces. The dangling sets that Zhang and Rohe identify as the trap for vanilla spectral clustering should therefore never take fractional values. Second, fractional mass should concentrate on the boundaries between communities in the dense core, precisely where $k$-means on "one-sided" coordinates fails, as noted by Dall'Amico et al. Third, if the anchors come from localized eigenvectors, the program should produce degenerate partitions. That would make localization visible as an anchoring failure rather than an embedding failure.
Research Program
The work has three parts.
The first part builds the solver. We will implement the sparse relaxation with a first-order linear programming solver so it scales to graphs with around $10^5$ edges and $k\le 10$. We will add lifted volume constraints, which are the volume inequality multiplied by an anchor indicator, and triangle and star consistency. We then add a rounding scheme. The main rounding is threshold rounding of anchored marginals in the style of multiway cut. The fallback treats poorly assigned nodes as outliers and reassigns them greedily, borrowed from the two-stage rounding of Avdiukhin et al. Anchors are selected by a confidence score on the row-normalized Bethe-Hessian embedding. Row normalization collapses degree-induced rays, as Qin and Rohe proved for regularized Laplacians. Anchor set size is a single parameter $s$ per cluster, swept from 1 to 20.
The second part analyzes the method on degree-corrected stochastic block models. These are random graphs with planted communities and uneven degrees (DC-SBM). We aim to bound how many anchor errors the program tolerates. We also aim to show that, above the detection threshold, Bethe-Hessian anchors are correct with high probability for $s$ growing slowly with $n$. This would connect the recovery guarantees of Stephan and Zhu to the rounding step, which they leave as plain projection.
The third part studies the gap empirically. On each instance we report the ratio between the rounded cut and the anchored lower bound. This gives the first measurement of Sherali-Adams integrality gaps for multi-way partitioning on sparse heterogeneous ensembles, a question the file shows to be entirely open.
The contrast with prior work is specific. The Sherali-Adams clustering results of Avdiukhin et al. and Cohen-Addad, Lee and Newman lift over all small subsets of metric or complete signed instances, at $n^{O(1/\epsilon^2)}$ cost. We lift only over the sparse graph's own local structures and replace blind conditioning with spectrally chosen anchors. The Bethe-Hessian line supplies our anchors but stops at $k$-means. InfraredGP and LTM rounding change the rounding step but give no bound on the cut. Measure-based SDPs attack the same size-unknown gap with orthogonal separators and lose an $O(\sqrt{\log n})$ factor. We attack it by conditioning, and our guarantee is instance-wise rather than worst-case.
Baselines
The naive reference point is adjacency spectral clustering with $k$-means. On Polblogs, Dall'Amico et al. report an overlap of 0.26 for it, and Qin and Rohe report that it dumps nearly all nodes into one cluster. Regularized spectral clustering is included at its published setting, with $\tau$ equal to the average degree. On Polblogs it mis-clusters about 80 of 1,222 nodes.
The strongest competitor is the Bethe-Hessian at $r=\zeta$ followed by $k$-means, which reaches an overlap of 0.91 on Polblogs, against 0.32 at $r=\sqrt{c}$. It is the strongest because it already solves localization, and it produces the very embedding we anchor on. Any gain we show therefore comes from the rounding step alone. To keep the comparison fair, both methods use the identical eigenvector computation, the same estimated $k$, and the same $\zeta$ estimator. The Bethe-Hessian pipeline gets 50 $k$-means restarts, matched in wall-clock time to our solver.
On enterprise-network data the strongest competitor is spherical-coordinate spectral clustering with a Gaussian mixture, which reports an ARI of 0.938 on ICL2. ARI is the adjusted Rand index, a chance-corrected measure of agreement with ground-truth groups. At scale, InfraredGP is reported within 0.5% of the best iterative methods on the IEEE HPEC Graph Challenge, and partitions a million-node graph in about 36 seconds.
Beating the Bethe-Hessian baseline means one of two outcomes. The first is a statistically significant overlap gain on DC-SBM near the threshold, or for $k\ge 4$ with imbalanced clusters. The second is matching accuracy at 0.91 on Polblogs together with a certified gap below 1.1. That second outcome is a certificate the baseline cannot produce.
Two ablations isolate the key ingredients. The first keeps the anchors but drops all lifted and triangle constraints, which isolates the contribution of lifting. The second keeps the full program but takes anchors from the unregularized adjacency eigenvectors, which isolates the contribution of delocalization.
Why not just…?
Why not just refine the Bethe-Hessian partition with local moves or belief propagation? Belief propagation passes label probabilities between neighboring nodes until they agree. Started from the spectral partition, it is a real threat to our accuracy claim. Bethe-Hessian is itself the linearization of belief propagation around the uninformative fixed point, and our edge-level program is closely related to its variational form. We expect comparable accuracy on clean block-model data. We will run belief propagation from the same anchors with the same time budget, as a named baseline. If it matches us, the surviving contribution is the lower bound and the measured gap, which neither belief propagation nor local search can supply. The file reports belief propagation only as roughly 500× slower than the dynamic Bethe-Hessian of the realistic-graphs paper, not as less accurate. So this question is genuinely open.
Why not just use a better model-based rounding, such as latent tree models or spherical Gaussian mixtures? LTM rounding reaches a Rand index of 0.97 on crescent data and estimates about 9.3 clusters on MNIST. Spherical Gaussian mixtures reach an ARI of 0.938 on ICL2. Both, however, fit distributions to coordinates and never look at the edges again. Nodes whose coordinates are one-sided or noisy are misplaced even when their neighborhood labels are unambiguous. Our program uses those edges directly. The per-node comparison on DC-SBM, restricted to low-degree and boundary nodes, will show whether that matters.
Why not just skip lifting and solve the anchored multiway-cut LP? The first ablation tests exactly this. If the plain anchored program is already integral on real sparse graphs, then Sherali-Adams adds nothing beyond conditioning, and we will say so. The prediction that could fail is that triangle constraints and lifted volume constraints measurably shrink the gap on core boundaries.
Proposed Experiments
On synthetic DC-SBM we will vary average degree from 2 to 20, power-law degree exponent from 2.1 to 3.5, $k$ from 2 to 10, and cluster-size imbalance. Metrics are overlap and ARI against planted labels, together with the certified gap. We will also report where fractional mass sits, split into fringe trees, hubs and core boundaries. The decisive check is the anchor-source ablation. If anchors from localized eigenvectors do not produce markedly worse partitions or larger gaps than Bethe-Hessian anchors, the claimed link between localization and conditioning is wrong.
On real graphs we will use Polblogs, where the target is overlap of at least 0.91 plus a certified gap. We will also use ICL2 (ARI against 0.938), the 242-node, 10-class SocioPatterns primary-school network taken per time step, and SNAP networks up to about $10^5$ edges. For SNAP we will report cluster sizes and conductance. No reported conductance numbers were found on Lacuna for the regularized method on SNAP, beyond its roughly 8× speedup and its avoidance of clusters under 10 nodes, so we rerun it ourselves.
For scalability we will use the smaller IEEE HPEC Graph Challenge graphs and report runtime against InfraredGP's reported speed. We expect to be much slower, and the question is whether the certificate justifies that cost at the $10^4$–$10^5$ scale. The sharpest single check is the tree-exactness prediction. On every graph, the fraction of fringe-tree nodes left fractional should be essentially zero. If it is not, the treewidth argument underlying the design does not hold in practice.
References
- Approximation Algorithm for Sparsest k-Partitioning
- Approximation Scheme for Weighted Metric Clustering via Sherali-Adams
- Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
- Spectral Clustering of graphs with the Bethe Hessian
- Community detection with the Bethe-Hessian
- Conditions beyond treewidth for tightness of higher-order LP relaxations
- Sparsest cut on bounded treewidth graphs: algorithms and hardness results
- Understanding Regularized Spectral Clustering via Graph Conductance
- Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel
- Correlation Clustering with Sherali-Adams
- InfraredGP: Efficient Graph Partitioning via Spectral Graph Neural Networks with Negative Corrections
- A Model-Based Approach to Rounding in Spectral Clustering
- Spectral Clustering on Spherical Coordinates Under the Degree-Corrected Stochastic Blockmodel
- Community Detection in Sparse Realistic Graphs: Improving the Bethe Hessian