Distance-Resolved Scoring for Community Detection Near the Detectability Threshold

In very sparse networks, where each node has only a handful of links, community detection has a sharp limit. Below a known signal strength, the Kesten–Stigum threshold, no algorithm can label nodes better than chance on a global scale. Algorithms are nonetheless benchmarked with single-number similarity scores such as normalized mutual information, the adjusted Rand index, or overlap, which compare the predicted partition to the planted one. This note argues that these scores cannot tell two different kinds of success apart. One is local agreement, such as putting adjacent nodes together, and remains possible even below the threshold. The other is global recovery, which is what the threshold is about. An algorithm that outputs many small, tightly connected clusters can score above chance on a well-behaved metric while recovering nothing global. As a result, empirical detectability curves and algorithm rankings mix the two.

The proposal is to score a predicted partition separately for node pairs at each graph distance $\ell$, producing a similarity profile instead of a single number. The motivation comes from the theory of reconstruction on trees: in a two-community block model, the planted labels of two nodes $\ell$ steps apart agree with excess probability that decays like $\lambda^\ell$. Here $\lambda$ is the gap between within- and between-community link rates, normalized by their sum. The number of such pairs grows like $c^\ell$ with average degree $c$. The threshold condition $c\lambda^2>1$ is precisely the condition that this signal survives at long range. Global recovery should therefore appear as a profile that stays bounded away from zero out to the typical inter-node distance, of order $\log n$. Purely local success should appear as a profile that decays to zero. We will build this diagnostic, check which axiomatic metric properties survive stratification by distance, and use it to re-examine claims about spectral and modularity-based methods on synthetic and real sparse graphs.

Core Claim

The claim is that single-number similarity indices, including those that pass the strongest axiomatic tests, conflate local and global recovery in sparse graphs. A distance-stratified correlation profile separates them, and it yields finite-size threshold estimates and algorithm rankings that track true weak recovery better than any flat index.

The prior work on metric axioms motivates and constrains this choice. Systematic Analysis of Cluster Similarity Indices proves three things relevant here. First, no pair-counting index can be monotone, a true distance, and have a constant chance baseline all at once. Second, $NMI_{\max}$ and F-measure fail monotonicity. Third, the Correlation Coefficient (CC) and Adjusted Mutual Information (AMI) are among the few indices that behave well. We therefore build on CC and give up the distance property, which matters for comparing partitions to each other but not for measuring recovery. That paper also names the "level of balance", meaning how indices weigh errors in small versus large clusters, as an open problem. Our stratification addresses one concrete form of it: small clusters can only contribute short-range pairs.

An Exact No Free Lunch Theorem for Community Detection shows that AMI under a null model fixing cluster sizes gives trivial outputs an unfair advantage, and repairs this by averaging over all partitions. That repair concerns the chance baseline of the metric over the universe of all partitions. It does not address the case we target: below the threshold, an algorithm's output is genuinely but only locally correlated with the planted labels. That local correlation is real signal rather than baseline bias, so no null-model correction removes it.

Research Program

The object we will build is a profile $s(\ell)$. For each distance $\ell$, it is the Pearson correlation between two binary indicators over all node pairs at shortest-path distance exactly $\ell$: whether the pair shares a predicted cluster, and whether it shares a planted community. Equivalently, it is the CC index of Gösgens et al. computed on that stratum of pairs. For large graphs we estimate each stratum by breadth-first sampling from random source nodes. This costs roughly the number of sources times the number of edges and runs on graphs with millions of edges. Pairs in different connected components are reported as a separate stratum, $\ell=\infty$. This matters because sparse graphs always have isolated nodes and small components, and algorithms must label them arbitrarily, a point Stochastic Block Model and Community Detection in Sparse Graphs makes in arguing that exact recovery is unattainable there.

The analysis has three parts.

First, we check axioms per stratum. Because CC restricted to any fixed subset of pairs remains a correlation on that subset, we expect monotonicity and a constant baseline under random relabeling with fixed cluster sizes to hold within each stratum. We will verify this formally and check numerically that it holds for AMI-style information analogues.

Second, we characterize the profile on the block model. Using locally tree-like neighborhoods, we will derive the profile of the planted labels themselves, which is $\lambda^\ell$, together with an upper bound on the profile of any estimator. We target a statement that below $c\lambda^2<1$, every estimator's profile at distances of order $\log n$ tends to zero. This would follow from non-reconstruction on trees, the link exploited by Exact phase transitions for stochastic block models and reconstruction on trees and A Proof of the Block Model Threshold Conjecture. Above the threshold, a weakly consistent estimator should have a long-range plateau. We will treat this as a conjecture to prove for the two-community case and to check numerically for three and four communities.

Third, we define a scalar summary for people who want one number: the plateau height $s^\ast$, the median of $s(\ell)$ over distances at or above the median inter-node distance. We will compare it against flat indices as a measure of global recovery.

The algorithms under study cover the sparse-graph toolbox. On the spectral side, they include the adjacency matrix, the non-backtracking matrix, the Bethe-Hessian at $r=\sqrt{c}$ from Spectral Clustering of graphs with the Bethe Hessian, and its degree-corrected version at $r=\zeta$ from Revisiting the Bethe-Hessian. We also include the trimming-plus-refinement pipeline of Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms. On the local and modularity side, we include Louvain, Infomap, and the label-propagation method SLPA, each with and without the Intimacy re-weighting of Community Cores, plus Morse clustering from Morse Theory and an Impossibility Theorem for Graph Clustering.

The Bethe-Hessian estimates the number of communities by counting negative eigenvalues. Community detection with the Bethe-Hessian proves this count is consistent above the threshold for expected degree at least 2, so we run each spectral method both with that estimated count and with the true count.

Baselines

The naive reference point is current practice. Each algorithm is scored with overlap (accuracy after the best label permutation, rescaled so chance is zero), $NMI_{\max}$, and the adjusted Rand index, all on the same graphs and the same predicted partitions as our profile. If the profile only reproduces the rankings and thresholds these give, the proposal has failed.

The strongest existing evaluation is a flat axiomatically sound index: CC and AMI as recommended by Gösgens et al., together with AMI and ARI under the all-partitions null of McCarthy et al. These are the strongest competitors because they already fix the baseline and monotonicity defects that a reviewer would otherwise blame for any discrepancy. They are computed on identical outputs, so there is no tuning budget to equalize. To beat them, three things must happen.

First, below the threshold on block-model graphs, the flat indices must give some algorithm a score significantly above zero across seeds while its profile plateau is indistinguishable from zero.

Second, the threshold estimated from where $s^\ast$ departs from zero must lie closer to $c\lambda^2=1$ at a given $n$ than the threshold estimated from flat indices.

Third, on real graphs, the algorithm ordering under $s^\ast$ must differ from the flat-index ordering in at least one case where a held-out check supports the $s^\ast$ ordering.

The strongest existing algorithm is the degree-corrected Bethe-Hessian at $r=\zeta$. On Political Blogs, Dall'Amico et al. report an overlap of 0.91, against 0.32 for the original Bethe-Hessian and 0.26 for adjacency spectral clustering. We reproduce these numbers before computing profiles. Our hypothesis is that the 0.91 is genuinely global, with a flat long-range profile. We also expect some local methods to match or exceed it on flat indices while showing a decaying profile. On the block model, the comparison point is the theoretical threshold itself. For other reported numbers on the same benchmarks: for the Amazon co-purchasing network, Jones et al. report SLPA at 0.242 NMI without Intimacy and 0.273 with it. For Karate, Dolphins, and Adjnoun, we found no reported numerical result on Lacuna for the Bethe-Hessian or the non-backtracking matrix. Saade et al. state only that the Bethe-Hessian noticeably outperformed the non-backtracking operator on the last two.

The key ablation isolates graph distance as the ingredient. We replace distance strata with random strata of identical sizes, and separately with strata defined by predicted-cluster size. If random strata reproduce the separation between local and global methods, the effect comes from subsampling, not from distance, and the claim fails. If cluster-size strata reproduce it, the simpler size-based fix in the next section wins.

Why not just…?

Why not just use overlap with the true number of communities, as the physics literature does? Overlap requires the algorithm to output exactly $k$ groups. That rules out Louvain, Infomap, SLPA, Morse clustering, and the Bethe-Hessian with estimated cluster count, which are precisely the methods whose outputs vary in granularity. Forcing them to $k$ groups adds a merging step that becomes part of what is evaluated. Overlap also weights every node equally, including isolated nodes that carry no information. We will report overlap wherever it is defined and test whether it already separates local from global success on fixed-$k$ outputs. If it does, the profile adds value only for variable-$k$ methods, and we will say so.

Why not just use a constant-baseline index such as CC or AMI under the all-partitions null? These fix bias from chance agreement, but the issue here is real local agreement. Adjacent nodes in an assortative block model truly share labels more often than chance, at every signal strength, so a partition into small connected clusters earns positive correlation even when global recovery is impossible. Whether this effect is large enough to matter at practical $n$ is an empirical question, and it is the main risk to the proposal. It shrinks with $n$, since short-range pairs are a vanishing fraction of all pairs. The first decisive check below measures its size directly across $n$ from $10^4$ to $10^6$. If flat CC below the threshold is negligible for every algorithm already at $n=10^4$, the problem is too small to matter, and we will narrow the contribution to the real-data ranking analysis.

Why not just discard small clusters, or score only the giant component? This is the strongest simple alternative, and the cluster-size ablation tests it directly. It may suffice for Louvain-style fragmentation. It fails in principle when an algorithm produces large clusters that are internally local, for example long chains grown by label propagation that span the graph but do not align with the planted split. Distance strata detect that case and size filters do not. If the size filter matches the profile on every benchmark here, we will adopt it as the recommended practice and report the profile only as its justification.

Why not just compare to the theoretical threshold on synthetic graphs and ignore real ones? Real graphs have no known threshold, so the profile's main practical use is there. On Political Blogs, DBLP, Amazon, and YouTube, it can say whether a reported gain, such as Intimacy's NMI improvement on Amazon, comes from short-range or long-range agreement. Jones et al. suggest that Intimacy helps small cores and hurts on large overlapping communities. The profile tests that interpretation directly.

Proposed Experiments

The synthetic sweep uses two-community block models with $n\in\{10^4,10^5,10^6\}$, average degree $c\in\{3,5,10\}$, and $c\lambda^2$ swept from 0.5 to 2. We add three- and four-community models and degree-corrected models with power-law degrees, following the setting of Dall'Amico et al. Each configuration uses 20 random seeds.

The first decisive check concerns the regime below the threshold. Every algorithm's plateau $s^\ast$ should be statistically zero. We record which algorithms receive nonzero flat CC, AMI, and $NMI_{\max}$, and how that excess scales with $n$.

The second concerns the regime above the threshold. Methods proven to achieve weak recovery, namely the Bethe-Hessian and the non-backtracking matrix, should show a long-range plateau. We will quantify whether their plateau tracks the planted-label value $\lambda^\ell$ in the short-distance strata. Adjacency spectral clustering should show a decaying or near-zero profile, consistent with hub localization.

The third is a finite-size threshold estimate. For each metric, we fit the signal strength at which the score departs from zero and compare its distance from $c\lambda^2=1$ as $n$ grows.

The fourth tests discretization. Gap analyses based on Clustering Redemption suggest $k$-means on eigenvectors may be unreliable when clusters are weakly separated, and Dall'Amico et al. observe one-sided eigenvector coordinates in easy regimes. We compare the profile of the continuous embedding, using sign-based and correlation-based readouts, with the profile after $k$-means. This tells us whether discretization destroys long-range signal or only short-range signal.

The real-data part uses Political Blogs, Karate, Dolphins, and Adjnoun from Saade et al. and Dall'Amico et al., and Amazon, DBLP, and YouTube from Jones et al. Here the held-out check is a split of ground-truth labels. We fit a simple label-propagation readout from each predicted partition on half the labeled nodes. We then measure accuracy on held-out nodes far, in graph distance, from any training node. This independently estimates long-range usefulness. The profile is supported if $s^\ast$ predicts held-out far-node accuracy better than flat indices do, measured by rank correlation across algorithms and datasets. It is refuted if a flat index predicts as well.