Pith. sign in

REVIEW 3 major objections 5 minor 48 references

Spectral graph clustering with inhomogeneous latent geometry

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Communities that latent geometry hides in the leading eigenvectors can still be recovered almost exactly from deeper eigenvalues, given only an approximate window around the informative eigenvalue, the paper proves.

desk verdict Solid spectral theory for inhomogeneous latent geometry, but the practical eigenvalue-localization recipe is unproved and in-sample, so the algorithm's guarantee is conditional on an oracle set B. read the letter →

arxiv 2608.11321 v1 pith:QSDSI3CI submitted 2026-08-11 cs.SI cs.LGmath.PRstat.ML

Konstantin Avrachenkov , Lucas S. Sibemberg , Alexander Van Werde This is my paper · ORCID
classification cs.SIcs.LGmath.PRstat.ML MSC 05C8060B2062H3005C82
keywords blocklatent-spacemodelalmostexactrecoverydensity-basedspectralclusteringgeometricrandomgraphlatentgeometryintegraloperatorhigher-orderDBSCAN
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Many real networks are shaped by two forces at once: where nodes sit in a latent space (physical or topical proximity) and which community they belong to, and the geometry can dominate the leading eigenvectors of the adjacency matrix so completely that standard spectral clustering fails. The paper shows this is not fatal: in a block latent-space model with an arbitrary compact latent space, an $L^2$-continuous kernel, and average degree growing faster than $\log n$, the community information survives in an eigenvector whose eigenvalue sits near $(a-b)\kappa^*/2$, generally not at the top of the spectrum. Its main theorem guarantees that DBSPEC, a density-based spectral clustering algorithm that needs only an approximate window around that eigenvalue, recovers the two clusters with only $o(n)$ errors. The spectral structure behind this is explicit: the limiting spectrum of the adjacency matrix equals that of the integral operator $\tfrac{1}{2}P \otimes \mathbb{K}$, with eigenfunctions $(\varphi_i, \pm\varphi_i)$, which predicts where the informative eigenvalue is. On real collaboration and social networks the prediction matches the empirically best eigenvalue, and higher-order eigenvectors lift accuracy from near-random to 76–99 percent.

What carries the argument

The load-bearing object is the limiting integral operator $\mathbb{A} = \tfrac{1}{2}P \otimes \mathbb{K}$, acting on pairs of functions on the latent space by $(g_1,g_2)(x) = \tfrac{1}{2} P \int K(x,y)(f_1(y),f_2(y))\,d\mu(y)$; it is the mean-field limit of the rescaled adjacency matrix, and its eigenfunctions are $(\varphi_i,\varphi_i)$ and $(\varphi_i,-\varphi_i)$ with eigenvalues $(a\pm b)\kappa_i/2$. Two of its properties carry the proof. First, a Jentzsch-type theorem makes the principal eigenfunction $\varphi^*$ strictly positive, so the vector $\psi^-_* \propto \sigma_v\varphi^*(X_v)$ has sign equal to the community labels, which is why its eigenvalue is the ideal location $(a-b)\kappa^*/2$. Second, every nonzero eigenfunction of $\mathbb{K}$ has a continuous representative, which forces the spectral embedding of each cluster to be a connected, uniformly dense point cloud while the two clusters sit a uniform distance apart; DBSCAN's density-connected components then isolate exactly the two clusters. A corollary of this operator picture is robustness: including a few extra eigenvectors near the window preserves the within-cluster continuity, so the algorithm tolerates approximate eigenvalue localization and eigenvalue multiplicities, whereas sign-based methods do not.

What would settle it

Simulate the block latent-space model with a known kernel on, say, $\mathcal{X} = [0,1]^2$ and compute the count of eigenvalues of $A/(n\rho_n)$ inside a window $B$, comparing it with the predicted count $\nu(B) = \sum_i (\mathbf{1}\{(a+b)\kappa_i/2 \in B\} + \mathbf{1}\{(a-b)\kappa_i/2 \in B\})$; a discrepancy that persists as $n$ grows under $\rho_n = \omega(\ln n/n)$ would refute Proposition 3.1. Independently, hand DBSPEC a window $B$ that provably contains $(a-b)\kappa^*/2$ and excludes $0$, and measure the misclassification rate: Theorem 4.1 predicts $o(n)$ errors, so any linear fraction of errors would refute the algorithmic claim.

Watch

Extended reading notes

Core claim

The central claim is that community labels remain almost recoverable from mid-spectrum eigenvectors even when the latent geometry is arbitrary and inhomogeneous, and that the right eigenvalue is located by an explicit operator calculation. Concretely, for links realized with probability $\rho_n K(X_v,X_w)P(\sigma_v,\sigma_w)$, the rescaled adjacency matrix $A/(n\rho_n)$ mimics, in its eigenvalues and eigenspaces, the integral operator $\mathbb{A} = \tfrac{1}{2}P \otimes \mathbb{K}$ on two copies of the latent space: the limiting spectrum is the superposition of the sequences $\tfrac{a+b}{2}\kappa_i$ and $\tfrac{a-b}{2}\kappa_i$, where $\kappa_i$ are the eigenvalues of the kernel operator $\mathbb{K}$, and the limiting eigenvectors are $(\psi^+_i, \psi^-_i)$ with $\psi^\pm_i \propto (\pm 1)^{\sigma_v}\varphi_i(X_v)$. Because the principal eigenfunction $\varphi^*$ is strictly positive, $\psi^-_*$ has signs that match the cluster labels exactly, which makes it the informative eigenvector, with eigenvalue $(a-b)\kappa^*/2$. Theorem 4.1 states that whenever the eigenvalue window $B$ contains that value and excludes $0$, DBSPEC — embed the vertices using all eigenvectors with eigenvalues in $n\rho_n B$, then run DBSCAN with radius $\Theta(1/\sqrt{n})$ and minimum points $\Theta(n)$ — outputs two clusters of size $n/2 - o(n)$ with $o(n)$ misclassified vertices, asymptotically almost surely. A density-based step succeeds where sign thresholds fail because within a cluster the embedding coordinates are continuous functions of the latent position and hence density-connected, while across clusters the $\psi^-_*$ component leaves a uniform gap of order $1/\sqrt{n}$.

Load-bearing premise

The theorem presupposes that the algorithm receives a set of eigenvalues containing the ideal value $(a-b)\kappa^*/2$ and excluding $0$, and the paper's practical recipe for finding such a set, equation (7.2), is fitted from the same graph's cluster densities and largest eigenvalue, with no proof that the estimate lands in a valid window.

Editorial extensions

If this is right

  • Standard spectral clustering that thresholds the second eigenvector performs poorly (56 percent on DBLP A and LiveJournal, 65 percent on DBLP B) when geometry dominates; selecting the eigenvector nearest the predicted location raises accuracy to 74–77 percent, and the best higher-order eigenvector reaches 76–85 percent.
  • The recovery guarantee holds at superlogarithmic average degree, a much sparser regime than the linear average degree required by the earlier torus-based analysis, and the authors note that known regularization techniques could push almost-exact recovery even further.
  • The method is stable at degenerate eigenvalues where sign-based clustering fails: on the circle with parameters tuned so the ideal eigenvalue is non-simple in the limit, DBSPEC attains 100 percent accuracy while the sign-based predecessor attains 64 percent.
  • The same operator argument extends to $k \ge 2$ clusters with unequal sizes and a general symmetric connectivity matrix: the limiting spectrum is the union over the eigenvalues $\tau_j$ of $\widetilde{P} = P\,\mathrm{diag}(q_1,\dots,q_k)$ of the sequences $\tau_j\kappa_i$, and recovery holds whenever the window contains all nonzero $\tau_j\kappa^*$.
  • Degree fluctuations, visible as radial streaks in spectral embeddings of skewed networks, can be neutralized by normalizing each row to the unit sphere; for LiveJournal, DBSPEC then achieves 99.3 percent accuracy on 99.6 percent of the vertices even when the embedding uses the three leading eigenvectors.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural transfer test the paper does not run: the same limiting-operator mechanism should carry the informative component into related spectra, such as eigenvectors of the graph Laplacian or the normalized adjacency matrix, so a cheap check would be to run the windowed density-based scheme on those spectra of the same datasets and compare the recovered labels.
  • The step the theorem needs but does not supply is a provably valid, fully data-driven construction of the window $B$; the DBLP A versus DBLP A* comparison shows how sensitive the fitted estimator (7.2) is to outliers such as large cliques, so one testable remedy is an adaptive window that widens with the local eigenvalue gap around $\hat\lambda^*$, with a check that accuracy degrades gracefully ra
  • If the limiting-operator picture is right, the rescaled ideal eigenvalue $(a-b)\kappa^*/2$ depends on the geometry only through the kernel's principal eigenvalue, not on the fine shape of the latent measure, which could be tested by keeping the kernel fixed and varying the latent distribution from uniform to boundary-concentrated while watching whether the best eigenvector's location stays put.
  • The four-cluster structure DBSPEC reveals inside DBLP A* (a dataset planted with two labels) suggests the algorithm can surface genuine substructure beyond the stated communities; a stability check across random halves of the network would test whether those subclusters replicate or are artifacts of the embedding.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper studies spectral clustering in a block latent-space model in which vertices have random positions on a compact set X and edge probabilities are ρ_n K(X_v,X_w) times a 2×2 block matrix P. This generalizes the soft geometric block model from toroidal to arbitrary compact latent geometry under an L2-continuity assumption on K. The authors prove that the empirical eigenvalues of the rescaled adjacency matrix converge to the spectrum of a limiting integral operator (Propositions 3.1 and 3.2), identify an informative eigenvector whose sign tracks the community labels, and propose DBSPEC, a DBSCAN-based algorithm using an eigenspace whose eigenvalues lie in a user-supplied set Λ_n. Theorem 4.1 states that, conditional on a Borel set B containing the ideal eigenvalue (a−b)κ*/2 and excluding 0, DBSPEC achieves almost exact recovery with o(n) errors under superlogarithmic average degree. The paper also reports real-world experiments on Political Blogs, LiveJournal, and DBLP, using the estimator λ̂* = λ̂max τmin/τmax in Eq. (7.2) to select a higher-order eigenvector, and reports that DBSPEC improves over sign-based clustering after normalization for degree fluctuations.

Significance. If the mathematical claims hold after the gaps noted below are fixed, the paper makes a substantive contribution: it replaces the torus-specific tracial moment analysis of prior work with an operator-theoretic framework, extends the model to inhomogeneous and non-toroidal latent spaces, and gives a consistency guarantee under average degree just superlogarithmic. The paper also provides a useful algorithmic insight: multidimensional eigenspaces are more robust than sign-based clustering when the informative eigenvalue is non-simple or poorly separated, and the proof strategy via Bernstein concentration, Weyl/Davis–Kahan perturbation, and Jentzsch positivity is standard and mostly convincing. The real-data experiments are suggestive, but the claimed alignment between theory and observations is currently weaker than the abstract suggests because the eigenvalue-location estimator is fitted in-sample and no theorem guarantees that it produces a valid set B for Theorem 4.1.

major comments (3)
  1. [§7, Eq. (7.2) and Table 2] The abstract and Section 7 claim that theoretical predictions for the ideal eigenvalue location align with real-world observations, but this claim is not established by the current experiments. The quantities a1, a2, b, n1, n2 entering Eq. (7.2) are computed from the same graphs whose ground-truth labels are used both to evaluate accuracy and to estimate these parameters, and no confidence interval, bandwidth, or alternative data split is provided. More importantly, no theorem states that an interval around λ̂* satisfies the hypotheses of Theorem 4.1 (contains nρ_n(a−b)κ*/2 and excludes 0). Table 2 shows that the predicted index equals the optimal index only in DBLP A*, which is obtained by manually removing the two largest cliques; in LiveJournal and DBLP B the predicted index is not the optimal one (3 vs 4 and 4 vs 15, respectively), and in DBLP A it is 1, giving no improvement over classical spectral clustering. To support the predictive claim, the paper should either provide a provable construction of a set B from observable data, or state the empirical claim in a substantially more qualified form.
  2. [§3, proof of Proposition 3.1 (Section 5) and Proposition 3.2] The proof of Proposition 3.1 asserts that ν(∂B)=0 implies the existence of ε>0 such that every eigenvalue of the limiting operator has distance at least ε from ∂B, and consequently that B contains only finitely many eigenvalues. This implication is false when B is not separated from 0: since the κ_i accumulate at 0, a Borel set with 0 in the closure of ∂B but 0∉B can have no uniform spectral gap and can contain infinitely many eigenvalues. Proposition 3.2 and Lemma 6.8 require the matrix Ψ_B to have finite dimension ν(B), and the Davis–Kahan step requires a positive spectral gap near B. The statements should replace the condition 0∉B with the stronger condition inf{|y|: y∈B}>0, or otherwise justify that the convergence in rearrangement distance alone suffices for unbounded-count indicator sets. As written, the proof of Propositions 3.1 and 3.2 has a load-bearing technical gap.
  3. [§7.1, Eq. (7.1)–(7.2), and Appendix A (Remark 4.4)] The estimator (7.2) for unbalanced clusters is asserted without a derivation. Remark 4.4 and Theorem A.2 provide a sufficient condition of the form {τ_j κ*: τ_j≠0}⊆B, but they do not prove that the informative eigenvalue for clustering is given by λ̂max τmin/τmax, nor that this quantity is the analog of (a−b)κ*/2 when community sizes and internal densities differ. Since all datasets in Table 1 violate the equal-size/equal-density assumption of the main theorem, the empirical predictions in Table 2 depend on this unproved generalization. The paper should provide a derivation of Eq. (7.2) from the k-cluster analysis, or explicitly mark it as a heuristic and adjust the strength of the empirical conclusions accordingly.
minor comments (5)
  1. [References] The journal name in reference [29] is misspelled as "Bernouilli"; it should be "Bernoulli".
  2. [Lemma 6.9] The sentence "There exists some ε0>0 such that such that asymptotically almost surely" contains a duplicated "such that" and should be reworded.
  3. [Appendix A.3, proof of Lemma A.5] In the line defining r, the expression |(ρ_j)_s−(ρ_j)_s| should read |(ρ_j)_s−(ρ_j)_t|.
  4. [Eq. (7.1) and surrounding text] The definition of P̃ in Eq. (7.1) would benefit from an explicit statement that it corresponds to P diag(n1/n, n2/n) from Remark 4.4, and the connection between n1,n2 and the q_j of the appendix should be stated in one place.
  5. [§6, Lemma 6.12] The notation in the proof of Lemma 6.12 uses w(0),...,w(k) while the text also refers to w(ℓ) and w(m); the indexing is slightly confusing and should be cleaned up for readability.

Circularity Check

1 steps flagged · score 3.0 of 10

Core spectral analysis is self-contained; the real-data eigenvalue-location 'prediction' (eq. 7.2) is an in-sample rescaling of the same graph's spectrum and fitted cluster densities.

  1. fitted input called prediction [Section 7, eq. (7.2) and Table 2]
    "Let τmin and τmax denote the minimum and maximum eigenvalues of P̃, respectively. Then, by Remark 4.4, the ideal eigenvalue for clustering should be located near the following value: λ̂* := λ̂max τmin/τmax."

    The quantities entering (7.2) are all measured on the same graph that is being clustered: λ̂max is the observed largest eigenvalue of the adjacency matrix, and τmin/τmax are eigenvalues of P̃ built from n1, n2, a1, a2, b in Table 1, where a1, a2, b are empirical edge densities computed with the ground-truth labels that the method is supposed to recover. Hence λ̂* is an algebraic rescaling of the same spectrum whose informative eigenvalue is being predicted, and the agreement reported in Table 2 (index closest to λ̂* versus empirically best index) is an in-sample comparison. The theoretical ratio (a−b)/(a+b) adds content, but the advertised claim that the predictions 'align with observations' is partly forced by construction rather than an independent, parameter-free prediction.

full rationale

The mathematical core of the paper is not circular. Propositions 3.1 and 3.2 are proved from external integral-operator results of Koltchinskii and Giné [29] and Koltchinskii [28], together with Weyl's inequality, Davis–Kahan, and matrix Bernstein; Theorem 4.1 follows from those propositions and standard DBSCAN properties. Citations to the authors' earlier works [4,5] are used for background and comparison, not as the load-bearing step, and no uniqueness theorem is imported from self-citations. The only partial circularity is the empirical eigenvalue-location 'prediction' in Section 7: eq. (7.2) is computed from the largest observed eigenvalue of the same adjacency matrix and from cluster-level densities estimated with ground-truth labels on the same graph, so the Table 2 agreement is in-sample rather than an independent test. The absence of a data-driven construction of the oracle set B in Theorem 4.1 is a correctness/completeness gap, not a circularity, as is the technical concern about the uniform spectral gap near zero in Proposition 3.1. Overall, the central derivation is self-contained, and the empirical prediction claim carries a modest in-sample circularity.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The theoretical core uses no fitted parameters: a,b, K, μ are model inputs. The empirical part introduces fitted quantities: cluster densities a_i,b estimated from the graph, hand-tuned DBSCAN parameters, and an ad hoc eigenvalue-location estimator (7.2). No new physical entities are postulated.

free parameters (2)
  • Cluster edge densities a_1, a_2, b = Table 1: e.g., Political Blogs a1=0.042, a2=0.039, b=0.0042; LiveJournal a1=0.0061, a2=0.0197, b=0.00014
    Estimated from the observed adjacency matrix in Section 7 and used to compute the predicted ideal eigenvalue location via (7.2). The theoretical results treat a,b as given model constants.
  • DBSCAN hyperparameters ε and MinPts = LiveJournal: ε=0.0003, MinPts=30 (unnormalized), ε=0.3, MinPts=50 (normalized); DBLP A*: ε=0.30, MinPts=500
    Chosen by hand in Section 7 and appendices; the theorem only asserts existence of constants, not how to pick them.
assumptions (6)
  • domain assumption X is compact and connected, supp(μ)=X (Assumption 2.4)
    Needed for compactness, eigenfunction continuity, and the positivity argument in Lemma 6.7.
  • domain assumption K is L2-continuous in the first argument (Assumption 2.5)
    Ensures the integral operator is Hilbert-Schmidt and that eigenfunctions have continuous representatives.
  • domain assumption a+b>0, a≠b, and ∫ K(x,y)dμ(y)>0 for every x (Assumption 2.6)
    Rules out unidentifiable clusters and guarantees the kernel has positive integral, used in Jentzsch-type positivity.
  • ad hoc to paper The set B with (a-b)κ*/2 ∈ B, ν(∂B)=0, 0∉B is known to the algorithm (Theorem 4.1 input)
    The consistency guarantee is conditional on approximate eigenvalue localization; the paper does not prove a feasible estimator for B with rates.
  • standard math External results: Koltchinskii-Giné [29, Thm 3.1], Koltchinskii [28, Thm 2.1], Davis-Kahan [43, Thm 2], Jentzsch [25, Thm I]
    Used in Propositions 3.1, 3.2, and Lemma 6.7; these are established results.
  • ad hoc to paper In experiments, eq. (7.2) estimates the ideal eigenvalue location from observed a,b and λ̂max
    No formal guarantee that this estimator lies in a valid set B; the agreement is empirical and in-sample.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Spectral graph clustering with inhomogeneous latent geometry." pith.science (2026). https://pith.science/paper/QSDSI3CI

@misc{pith2026260811321,
  author       = {Pith},
  title        = {Pith review of: Spectral graph clustering with inhomogeneous latent geometry},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QSDSI3CI}},
  note         = {Machine review of arXiv:2608.11321}
}
read the original abstract

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.

Figures

Figures reproduced from arXiv: 2608.11321 by the authors.

Figure 1
Figure 1. A random soft geometric graph with 200 points uniformly drawn in the square X as in Example 2.2 with parameters 𝑅 = 1/2𝜋, 𝑎 = 0.75 and 𝑏 = 0.2. Community membership is indicated by node colors. 2.1. Assumptions. So far, the cluster assignments 𝜎𝑣 could just as well have been incorpo￾rated in the latent positions by replacing the latent space X with two disjoint copies of itself and modifying the kernel 𝐾. The follow… view at source ↗
Figure 2
Figure 2. As described in Example 4.3, we consider a simulation of the soft geometric block model on X = 𝕋 1 . We take parameters 𝑛 = 5000, 𝑅 = 1/2𝜋, 𝑎 = 0.5, and 𝑏 = 𝑎(1 − sinc(2𝜋𝑅))/(1 + sinc(2𝜋𝑅)). It can be shown that the ideal eigenvalue location should here be 362.42. The observed adjacency matrix in-fact has three eigenvalues close to this location: the second largest eigenvalue ˆ𝜆2 ≈ 373.98, third largest ˆ𝜆3 ≈ 362.38… view at source ↗
Figure 3
Figure 3. (right). While removing the clique does not substantially change the best possible achievable accuracy, it does have significant effect on the estimator for the optimal eigenvalue location [PITH_FULL_IMAGE:figures/full_fig_p017_3.png] view at source ↗
Figures from the paper (8 more)
Figure 4
Figure 4. Figure 4: (right) visualizes the renormalized spectral embeddings. We observe a much cleaner separation between the clusters, aside from only a relatively small number of points that can reasonably be considered due to noise. Applying DBSCAN with ad-hoc parameters 𝜖 = 0.3 and Mi…
Figure 5
Figure 5. Figure 5: On the left, plot of the eigenvector coordinates associated with ˆ𝜆4 = 255.09. On the right, the eigenvector coordinates associated with ˆ𝜆2 = 308.87 [PITH_FULL_IMAGE:figures/full_fig_p025_5.png]
Figure 6
Figure 6. Figure 6: On the left, plot of the eigenvector coordinates of 𝜓2 associated with 𝜆2 = 318.81. On the right, plot of the eigenvector coordinates of 𝜓4 associated with 𝜆4 = 281.19. us continue with X = 𝕋 2 and set 𝑛 = 3000, 𝑅 = 1/2𝜋, 𝜌𝑛 = 1, and 𝐾(𝑥, 𝑦) = 1{||𝑥 − 𝑦|| ≤ 𝑅}. We vary…
Figure 7
Figure 7. Figure 7: Accuracy of SGBM for HOSC [5] and DBSPEC with 𝑏 is chosen depending on 𝑎 as in (B.1). Due to the linearity of (B.1), changing 𝑎 is here equivalent to modifying the sparsity parameter 𝜌𝑛. The bars indicate one standard deviation for the individual samples across runs […
Figure 8
Figure 8. Figure 8: On the left, evolution of DBSPEC accuracy in the sparse regime as 𝑛 increases, that is, the proportion of correctly classified vertices. On the right, the average density for each 𝑛, where the density is the ratio between the number of edges and the total number of pos…
Figure 9
Figure 9. Figure 9: shows the spectral embedding given by the rows of [𝜓8 𝜓9 𝜓10], after normalizing each embedded point to lie on the unit sphere. Interestingly, for a wide range of DBSCAN parameters (for instance 𝜖 = 0.30 and MinPts = 500) this embedding yields four clusters rather than…
Figure 10
Figure 10. Figure 10: Adjacency matrix of DBLP A∗ with rows and columns sorted by the four DBSCAN clusters of [PITH_FULL_IMAGE:figures/full_fig_p028_10.png]
Figure 11
Figure 11. Figure 11: visualizes the (normalized) spectral embeddings associated to the rows of [𝜓3𝜓4𝜓5] in LiveJournal. The accuracy of DBSCAN in this case is 99.2%, essentially identical to the per￾formance 99.3% achieved using [𝜓1 𝜓2 𝜓3]. This confirms that the accuracy is not too sensi…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 29 canonical work pages

  1. [1]

    E. Abbe, F. Baccelli, and A. Sankararaman. Community detection on Euclidean random graphs.Information and Inference: A Journal of the IMA, 2021. doi: 10.1093/imaiai/iaaa009

    work page doi:10.1093/imaiai/iaaa009 2021

  2. [2]

    L. A. Adamic and N. Glance. The political blogosphere and the 2004 US election. In Proceedings of the WWW-2005 Workshop on the Weblogging Ecosystem, 2005. doi: 10.114 5/1134271.1134277

    work page arXiv 2004

  3. [3]

    Adhikari, R

    K. Adhikari, R. J. Adler, O. Bobrowski, and R. Rosenthal. On the spectrum of dense random geometric graphs.The Annals of Applied Probability, 2022. doi: 10.1214/21-AAP1720

    work page doi:10.1214/21-aap1720 2022

  4. [4]

    L. E. Allem, K. Avrachenkov, C. Hoppen, H. Manjunath, and L. S. Sibemberg. Multi- community spectral clustering for geometric graphs.arXiv preprint arXiv:2508.00893,

    arXiv

  5. [5]

    Avrachenkov, A

    K. Avrachenkov, A. Bobu, and M. Dreveton. Higher-order spectral clustering for geomet- ric graphs.Journal of Fourier Analysis and Applications, 2021. doi: 10.1007/s00041-021-0 9825-2

    work page doi:10.1007/s00041-021-0 2021

  6. [6]

    Avrachenkov, B

    K. Avrachenkov, B. Kumar, and L. Leskelä. Community detection on block models with geometric kernels.arXiv preprint arXiv:2403.02802, 2024. doi: 10.48550/arXiv.2403.02802

    work page doi:10.48550/arxiv.2403.02802 2024

  7. [7]

    Bordenave

    C. Bordenave. Eigenvalues of Euclidean random matrices.Random Structures & Algo- rithms, 2008. doi: 10.1002/rsa.20228

    work page doi:10.1002/rsa.20228 2008

  8. [8]

    Bubeck, J

    S. Bubeck, J. Ding, R. Eldan, and M. Z. Rácz. Testing for high-dimensional geometry in random graphs.Random Structures & Algorithms, 2016. doi: 10.1002/rsa.20633

    doi:10.1002/rsa.20633 2016

Show all 48 references
  1. [9]

    Cao and Y

    Y. Cao and Y. Zhu. Spectra of high-dimensional sparse random geometric graphs.arXiv preprint arXiv:2507.06556, 2025. doi: 10.48550/arXiv.2507.06556

    2025 doi arXiv

  2. [10]

    Chaudhuri, F

    K. Chaudhuri, F. Chung, and A. Tsiatas. Spectral clustering of graphs with general degrees in the extended planted partition model. InProceedings of the 25th Annual Conference on Learning Theory. PMLR, 2012

    2012

  3. [11]

    J. B. Conway.A course in functional analysis. Springer, 2nd edition, 2007. doi: 10.1007/97 8-1-4757-4383-8

    2007 doi

  4. [12]

    Dasgupta, J

    A. Dasgupta, J. E. Hopcroft, and F. McSherry. Spectral analysis of random graphs with skewed degree distributions. In45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, 2004. doi: 10.1109/FOCS.2004.61. 19

    2004 doi

  5. [13]

    Ding and Y

    X. Ding and Y. Hu. On the edge eigenvalues of sparse random geometric graphs.arXiv preprint arXiv:2509.07372, 2025. doi: 10.48550/arXiv.2509.07372

    2025 doi arXiv

  6. [14]

    Dubova, Y

    S. Dubova, Y. M. Lu, B. McKenna, and H.-T. Yau. Universality for the global spectrum of random inner-product kernel matrices in the polynomial regime.arXiv preprint arXiv:2310.18280, 2023. doi: 10.48550/arXiv.2310.18280

    2023 doi arXiv

  7. [15]

    Ester, H.-P

    M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. InKDD’96: Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, 1996

    1996

  8. [16]

    Galhotra, A

    S. Galhotra, A. Mazumdar, S. Pal, and B. Saha. The geometric block model. InProceedings of the AAAI Conference on Artificial Intelligence, 2018. doi: 10.1609/aaai.v32i1.11905

    2018 doi

  9. [17]

    Galhotra, A

    S. Galhotra, A. Mazumdar, S. Pal, and B. Saha. Community recovery in the geometric block model.Journal of Machine Learning Research, 24(338):1–53, 2023

    2023

  10. [18]

    C. Gao, Z. Ma, A. Y. Zhang, and H. H. Zhou. Community detection in degree-corrected block models.The Annals of Statistics, 2018. doi: 10.1214/17-AOS1615

    2018 doi

  11. [19]

    Gaudio, C

    J. Gaudio, C. Guan, X. Niu, and E. Wei. Exact label recovery in Euclidean random graphs. arXiv preprint arXiv:2407.11163, 2024. doi: 10.48550/arXiv.2407.11163

    2024 doi

  12. [20]

    Gaudio and C

    J. Gaudio and C. K. Guan. Sharp exact recovery threshold for two-community Euclidean random graphs. In2025 IEEE International Symposium on Information Theory (ISIT). IEEE,

  13. [21]

    Gaudio and A

    J. Gaudio and A. Jin. Exact recovery in the geometric SBM.arXiv preprint arXiv:2512.22773,

  14. [22]

    doi: 10.1109/ISIT63088.2025.11195628

    2025

  15. [23]

    M. S. Handcock, A. E. Raftery, and J. M. Tantrum. Model-based clustering for social networks.Journal of the Royal Statistical Society Series A: Statistics in Society, 2007. doi: 10.1111/j.1467-985X.2007.00471.x

    2007 arXiv

  16. [24]

    doi: 10.48550/arXiv.2512.22773

    doi

  17. [25]

    Gaudio, X

    J. Gaudio, X. Niu, and E. Wei. Exact community recovery in the geometric SBM. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2024

    2024

  18. [26]

    Horn and C

    R. Horn and C. Johnson.Matrix analysis. Cambridge University Press, second edition,

  19. [27]

    Holland, K

    P. Holland, K. Laskey, and S. Leinhardt. Stochastic blockmodels: First steps.Social networks, 1983. doi: 10.1016/0378-8733(83)90021-7

    1983 doi

  20. [28]

    Horiguchi and Y

    T. Horiguchi and Y. Fukui. A variation of the Jentzsch theorem for a symmetric integral kernel and its application.Interdisciplinary Information Sciences, 1996. doi: 10.4036/iis.19 96.139

    1996 doi

  21. [29]

    Koltchinskii and E

    V. Koltchinskii and E. Giné. Random matrix approximation of spectra of integral operators. Bernouilli, 2000. doi: 10.2307/3318636

    2000 doi

  22. [30]

    M. C. Le, E. Levina, and R. Vershynin. Concentration and regularization of random graphs. Random Structures & Algorithms, 2017. doi: 10.1002/rsa.20713

    2017 doi

  23. [31]

    Karrer and M

    B. Karrer and M. Newman. Stochastic blockmodels and community structure in networks. Physical Review E, 2011. doi: 10.1103/PhysRevE.83.016107

    2011 doi

  24. [32]

    Koltchinskii

    V. Koltchinskii. Asymptotics of spectral projections of some random matrices ap- proximating integral operators. InHigh dimensional probability. Springer, 1998. doi: 10.1007/978-3-0348-8829-5_11

    1998 doi

  25. [33]

    Li and T

    S. Li and T. Schramm. Spectral clustering in the Gaussian mixture block model.arXiv preprint arXiv:2305.00979, 2023. doi: 10.48550/arXiv.2305.00979. 20

    2023 doi arXiv

  26. [34]

    S. Lloyd. Least squares quantization in PCM.IEEE transactions on information theory,

  27. [35]

    Lei and A

    J. Lei and A. Rinaldo. Consistency of spectral clustering in stochastic block models.The Annals of Statistics, 2015. doi: 10.1214/14-AOS1274

    2015 doi

  28. [36]

    Leskovec and A

    J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection, 2014. https://snap.stanford.edu/data/

    2014

  29. [37]

    Penrose.Random geometric graphs

    M. Penrose.Random geometric graphs. OUP Oxford, 2003. doi: 10.1093/acprof:oso/9780 198506263.001.0001

    2003 doi

  30. [38]

    Qin and K

    T. Qin and K. Rohe. Regularized spectral clustering under the degree-corrected stochastic blockmodel.Advances in neural information processing systems, 26, 2013

    2013

  31. [39]

    Sankararaman and F

    A. Sankararaman and F. Baccelli. Community detection on Euclidean random graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2018. doi: 10.1137/1.9781611975031.142

    2018 doi

  32. [40]

    Lovász.Large networks and graph limits

    L. Lovász.Large networks and graph limits. American Mathematical Society, 2012

    2012

  33. [41]

    A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14, 2001

    2001

  34. [42]

    Yang and J

    J. Yang and J. Leskovec. Defining and evaluating network communities based on ground- truth. InProceedings of the IEEE International Conference on Data Mining (ICDM), 2012. doi: 10.1145/23501/2350190.2350193

    2012

  35. [43]

    Y. Yu, T. Wang, and R. Samworth. A useful variant of the Davis–Kahan theorem for statisticians.Biometrika, 2015. doi: 10.1093/biomet/asv008. 21 AppendixA.Proof for Remark 4.4 Recall that Remark 4.4 concerns generalizations to settings with multiple clusters and non- uniform cl...

    2015 doi

  36. [45]

    J. Tropp. User-friendly tail bounds for sums of random matrices.Foundations of compu- tational mathematics, 2012. doi: 10.1007/s10208-011-9099-z

    2012 doi

  37. [46]

    Von Luxburg, M

    U. Von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering.The Annals of Statistics, 2008. doi: 10.1214/009053607000000640

    2008 doi

  38. [1982]

    doi: 10.1109/TIT.1982.1056489

    1982

  39. [2012]

    doi: 10.1017/CBO9780511810817

    doi

  40. [2025]

    doi: 10.48550/arXiv.2508.00893

    doi arXiv

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.