Spectral graph clustering with inhomogeneous latent geometry

arXiv:2608.11321v1 [cs.SI] 11 Aug 2026

The paper studies spectral clustering in the presence of a confounding latent geometry. The authors note that "The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the spectrum. They analyze the spectral properties of the adjacency matrix through a limiting integral operator" and use its structure to develop DBSPEC, a density-based spectral clustering algorithm that requires only approximate localization of the informative eigenvalue and is robust to poor eigenvalue separation. Crucially, this approach handles general latent geometries, overcoming restrictions to homogeneous toroidal models in prior works. The theoretical predictions for the location of the informative eigenvalue notably align with observations in real-world experiments.

The paper addresses a fundamental problem in network clustering: real-world networks are shaped by both geometric and community-based factors. For example, in collaboration graphs, Shared research interests increase the chance of collaboration, while geographic distance reduces it due to logistical challenges. The authors note that most existing theoretical models include either geometric or community structure, but not both. The stochastic block model captures purely community-based structure, while latent position models provide a purely geometric framework.

The paper builds on prior work on the two-cluster Soft Geometric Block Model (SGBM), which assigns nodes uniform random positions on a d-dimensional torus. Previous work by Avrachenkov et al. [5] found that sign-based spectral clustering can still be made to work in the SGBM, but only if one considers an eigenvalue deeper in the spectrum. However, that analysis strongly depends on the nodes being distributed uniformly in the d-dimensional torus and the exact appropriate eigenvalue position must be known and the algorithm is not robust when the eigenvalue is not well-separated from other eigenvalues.

The present paper generalizes this to inhomogeneous latent geometry, where nodes are independently assigned positions Xi on some arbitrary compact set following a law that does not need to be uniform. The connection probabilities are proportional to K(Xi, Xj), where K is a general symmetric kernel satisfying a mild L2-continuity condition.

The paper introduces the block latent-space model. Fix a compact subset X ⊆ Rd and assume nodes are independently assigned latent positions following a probability distribution mu. Independently assign random labels sigma1,...,sigman ∼ Unif 1,2. Fix a measurable symmetric function K: X × X → [0,1], parameters a,b ∈ [0,1], and a sparsity parameter rhon.

A random graph G = (V,E) on n nodes comes from this model if edges are present conditionally independently given latent positions and cluster assignments, with:

P X,sigma((v,w) ∈ E) = rhon K(Xv, Xw)P(sigmav, sigmaw)

where P is the symmetric 2×2 matrix with entries a on the diagonal and b off-diagonal.

Example 2.1: If X = 0 is a single point, one recovers the stochastic block model. If X ⊆ R and K(x,y) = xy, one recovers the degree-corrected stochastic block model.

Example 2.2: With K(x,y) = 1 ∥x−y∥ ≤ R, one recovers the geometric random graph model when a = b, and a soft geometric block model when a ≠ b. The paper notes that the restriction to tori will not be needed in the present work.

Non-example 2.3: The setup is intended to model a setting where clusters and geometry are two different features. Geometry-based clusters as in Gaussian mixture block models are not admitted.

• Assumption 2.4: The compact set X ⊆ Rd is connected, and supp(mu) = X.

• Assumption 2.5: The function x ↦ K(x,·) is continuous in the L2-norm for mu.

• Assumption 2.6: a + b > 0, a − b ≠ 0, and ∫ X K(x,y)dmu(y) > 0 for every x ∈ X.

The paper associates with kernel K a linear operator K: L2(X,mu) → L2(X,mu) given by:

(Kf)(x):= ∫ X f(y)K(x,y)dmu(y)

This operator is self-adjoint and compact, so the spectral theorem applies with eigenfunctions phi1, phi2,... and eigenvalues kappa1 ≥ kappa2 ≥...

Proposition 3.1: Let lambdâ1,...,lambdân be eigenvalues of the rescaled adjacency matrix A/(nrhon) with rhon = omega(ln(n)/n). Then there exists a measure nu such that for any fixed Borel set B with nu(∂B) = 0 and 0 ∉ B:

in probability, where the limiting measure is explicitly:

nu = Σi (delta(a+b)kappai/2 + delta(a−b)kappai/2)

Proposition 3.2: The eigenvectors of the adjacency matrix approximate those of a limiting operator A defined on two copies of X. The eigenfunctions are (phii, phii) and (phii, −phii) with eigenvalues (a+b)kappai/2 and (a−b)kappai/2 respectively. The paper shows that with appropriate orthogonal transformations, the eigenvectors of A/(nrhon) converge to the vectors psii± defined by:

(psii+)v ∝ phii(Xv) and (psii−)v ∝ phii(Xv) if sigmav = 1, −phii(Xv) if sigmav = 2

The proof approach differs from prior work: "While the analysis in [4,5] used delicate combinatorial arguments for the tracial moments of the adjacency matrix where the shape of the limiting spectrum appears somewhat miraculously, here we adopt an operator-theoretic perspective."

The paper notes that a generalization of the Perron–Frobenius theorem ensures the greatest eigenvalue kappa∗ of K has a strictly positive eigenfunction phi∗. The vector psi∗− then has sign aligned with cluster labels, making it informative for clustering.

However, sign-based clustering has disadvantages:

1. It becomes unstable when the limiting eigenvalue has nontrivial multiplicity.

2. It requires knowing exactly which eigenvector to use, and the correct eigenvalue to use is not necessarily the second largest.

Algorithm 1 (DBSPEC):

1. Compute eigenvalues lambdâ1,...,lambdân and eigenvectors psî1,...,psîn of A

2. Select indices Jn with eigenvalues in a set Λn

3. For each node w, construct embedding V̂w = [(psîⱼ)w: j ∈ Jn]

4. Apply DBSCAN to the points V̂w with parameters epsilon and MinPts

Theorem 4.1: Given a Borel set B with (a−b)kappa∗/2 ∈ B satisfying the usual conditions, and assuming rhon = omega(ln(n)/n), there exist constants c1, c2 > 0 such that the partition output by Algorithm 1 with parameters epsilon = c1/√n and MinPts = c2n satisfies asymptotically almost surely:

• (a) Two linearly sized clusters: all except two parts have cardinality o(n), and the remaining two parts have size n/2 − o(n).

• (b) Almost exact recovery: there exists a permutation pi such that sigmav = 1 for all except o(n) members of C pi(1), and sigmav = 2 for all except o(n) members of C pi(2).

Remark 4.2: The algorithm is not overly sensitive to parameter choices. There exists C1 > 0 such that for every fixed 0 < c1 < C1, every choice of epsilon ∈ [c1/√n, C1/√n] will work as n → ∞.

Example 4.3: In a simulation on a one-dimensional torus with parameters chosen so the ideal eigenvalue is non-simple, "none of the individual eigenvectors psii close to the ideal eigenvalue produces a clear separation of communities. On the other hand, if the eigenvectors are combined into a 3D spectral embedding... then the two communities become cleanly separated. Algorithm 1 would here give accuracy 100%, while a sign-based clustering algorithm such as HOSC [5] using the single eigenvector psi3 would obtain accuracy only 64%."

Remark 4.4: The analysis extends to more than two clusters. With cluster assignments in 1,...,k, probabilities qⱼ, and a general symmetric k×k matrix P, the limiting operator becomes P̃ ⊗ K with P̃:= P diag(q1,...,qk). The limiting measure becomes Σⱼ Σi delta tauⱼkappai where tau1,...,tauk are eigenvalues of P̃.

The proof uses a preliminary reduction (Lemma 5.1) showing that ∥A − E[AX,sigma]∥/(nrhon) → 0 in probability when rhon = omega(ln(n)/n), using the matrix Bernstein inequality.

The paper then defines a kernel A on the discrete union of two copies of X and shows the limiting operator A is the integral operator associated with this kernel. Propositions 3.1 and 3.2 follow from results by Koltchinskii and Giné [29] and Koltchinskii [28] regarding eigenvalues and eigenvectors of matrices sampled from integral operators.

For Theorem 4.1, the proof establishes:

• Lemma 6.6: Every eigenfunction associated with a non-zero eigenvalue of K has a continuous representative.

• Lemma 6.7: The eigenfunction phi∗ for the greatest eigenvalue of K is strictly positive (via Jentzsch's theorem).

• Lemma 6.8: For every epsilon > 0 there exists delta > 0 such that asymptotically almost surely ∥Vv − Vw∥ < epsilon/√n for all values with ∥Xv − Xw∥ 0 such that asymptotically almost surely ∥Vv − Vw∥ > epsilon0/√n whenever sigmav ≠ sigmaw.

• Lemma 6.10: The fraction of good indices (where the empirical embedding is close to the limiting one) tends to 1.

• Lemmas 6.11–6.13: Establish that all good points are core points, points in the same cluster are density connected, and points in different clusters are not density connected.

The paper tests predictions on three real-world datasets:

1. LiveJournal [42]: A social network with 2766 nodes, average degree 17.45.

2. Political Blogs [2]: A hyperlink network with 1224 nodes, average degree 27.31.

3. DBLP [32]: A collaboration network with 13036 nodes (DBLP A) or 12212 nodes (DBLP B).

The paper derives a testable prediction for the ideal eigenvalue location. Since the largest eigenvalue should be lambdâ max ≈ nrhon(a+b)kappa∗/2, the ideal eigenvalue should be located near:

lambdâ∗:= lambdâ max · (tau min/tau max)

where tau min and tau max are the minimum and maximum eigenvalues of the matrix P̃ accounting for unequal community sizes and densities.

Results for sign-based clustering:

Dataset Classical HO (lambdâ∗) HO (lambdâ opt) Index lambdâ∗ Index lambdâ opt

Political Blogs 93% 93% 93% 2 2

DBLP A 56% 56% 76% 1 12

DBLP A∗ 56% 76% 76% 10 10

DBLP B 65% 74% 75% 4 15

LiveJournal 56% 77% 85% 3 4

The paper notes: "The classical and higher-order methods naturally have identical performance when the corresponding eigenvalues coincide, as in Political Blogs. However, the second eigenvalue does not always match the one predicted by our theory. When it does not, selecting the predicted higher-order eigenvalue can substantially improve performance."

For DBLP A, the paper explains that large cliques (sizes 18 and 22) affect the estimate of the largest eigenvalue. After removing these cliques (creating DBLP A∗), our estimator lambdâ∗ = 14.31 also changes substantially and now accurately reflects the optimal value.

For LiveJournal, the paper applies DBSPEC with the three largest eigenvectors. Initially, applying DBSCAN on the 3-dimensional spectral embeddings with an ad-hoc optimized parameter choice epsilon = 0.0003 and MinPts = 30 achieves 88% accuracy on the assigned points but labels 62% of the vertices as noise. The paper identifies radial streaks as a known phenomenon from degree fluctuations. After normalizing embeddings to the unit sphere (following [36]), applying DBSCAN with ad-hoc parameters epsilon = 0.3 and MinPts = 50 returns two clusters with only 0.4% of the vertices labeled as noise and near-perfect 99.3% accuracy on the assigned points.

The paper concludes: "This paper studied spectral clustering in the block latent space model, a random graph model with community structure in the presence of a potentially inhomogeneous confounding latent geometry. Propositions 3.1 and 3.2 described the spectrum of the graph's adjacency matrix in terms of a limiting kernel. Theorem 4.1 leveraged this structure to give a consistency guarantee for DBSPEC, a DBSCAN-based higher-order spectral clustering algorithm."

"For real-world data, our results are consistent with the observed behavior once the understood effects of large cliques and degree fluctuations are taken into account. We found that a higher-order eigenvalue can give better performance than the classical second eigenvalue, and our theory gives good predictions for the location of the ideal eigenvalue. Further, robust multidimensional spectral embedding can significantly improve performance relative to sign-based assignment with a single eigenvector."

The appendices provide:

• Appendix A: Proof for the multi-cluster generalization (Remark 4.4), including Theorem A.2 with the condition tauⱼkappa∗: j ≤ k, tauⱼ ≠ 0 ⊆ B.

• Appendix B: Additional synthetic experiments showing the effect of geometry (square vs. torus), robustness to non-simple eigenvalues, and performance in sparse regimes.

• Appendix C: Conditions for the ideal eigenvalue being non-simple in the limiting spectrum, derived from Fourier transform analysis.

• Appendix D: Additional DBSPEC experiments on DBLP A∗, where the algorithm surprisingly finds four natural clusters rather than two, with only 3.6% of edges crossing block boundaries.

Based on this paper, here are the specific improvements that can be made to AI systems:

Improvement: Replace single-eigenvector spectral clustering (e.g., classical spectral clustering or HOSC) with the DBSPEC algorithm that uses multi-dimensional spectral embeddings and density-based clustering (DBSCAN).

What the improved system can do:

• Recover community structure in networks where latent geometry (e.g., geographic distance, similarity) confounds the signal, even when the informative eigenvalue is not well-separated or has multiplicity

• Achieve near-perfect accuracy (99.3% in LiveJournal experiments) where sign-based methods fail (56-85%)

• Automatically handle non-simple eigenvalues by combining multiple eigenvectors into an embedding rather than relying on a single one

• Maintain robustness when the exact eigenvalue location is unknown—only approximate localization is needed

We study spectral clustering in the presence of a confounding latent geometry. The leading eigenvectors may then be dominated by the latent geometry rather than by the communities. Nevertheless, we show in a block latent-space model that communities can be recovered from eigenvectors deeper in the spectrum. We analyze the spectral properties of the adjacency matrix through a limiting integral operator and use its structure to develop DBSPEC, a density-based spectral clustering algorithm that requires only approximate localization of the informative eigenvalue and is robust to poor eigenvalue separation. Crucially, this approach handles general latent geometries, overcoming restrictions to homogeneous toroidal models in prior works. Our theoretical predictions for the location of the informative eigenvalue notably align with observations in real-world experiments.