The reviewed record of science sign in
Pith

arxiv: 2605.22346 · v3 · pith:TGYEBITB · submitted 2026-05-21 · stat.ML · cs.LG· cs.SI

The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers

Minh Triet Pham , Ian Gallagher This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-30 16:18 UTCgrok-4.3pith:TGYEBITBrecord.jsonopen to challenge →

classification stat.ML cs.LGcs.SI
keywords spectral embeddingadjacency spectral embeddinglaplacian spectral embeddinggraph regularitydegree heterogeneityeigengapperturbation analysisgraph disagreement
0
0 comments X

The pith

ASE and LSE produce identical latent subspaces exactly when the graph is regular or bipartite biregular, with disagreement always below its theoretical maximum and controlled by degree heterogeneity and eigengap.

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

The paper proves that two widely used graph embedding methods agree perfectly for any embedding dimension under a simple structural condition on the graph. This condition holds precisely when the graph is regular or bipartite biregular, establishing the lower end of the disagreement spectrum. The work further shows that disagreement never attains a finite maximum value, as demonstrated by families of graphs that approach but do not reach the theoretical ceiling. A derived bound then isolates degree heterogeneity as the factor that raises disagreement and the eigengap as the factor that lowers it, with their ratio emerging as a practical predictor of when the embeddings can be treated as interchangeable.

Core claim

The two methods produce identical latent subspaces for every embedding dimension whenever the Laplacian is a scalar multiple of the adjacency matrix, and this scalar relationship holds if and only if the graph is regular or bipartite biregular. No maximal-disagreement graph exists because disagreement remains strictly below its theoretical ceiling for any finite graph, with a witness family showing that the upper limit is approachable but unattainable. The Regularity Departure Bound isolates degree heterogeneity and eigengap as the primary structural drivers of disagreement in the intermediate regime.

What carries the argument

The scalar-multiple relationship between the Laplacian and the adjacency matrix, which serves as the exact condition for perfect agreement and the baseline for the subsequent perturbation analysis that yields the Regularity Departure Bound.

If this is right

  • If the graph is regular or bipartite biregular then ASE and LSE return identical latent subspaces in every embedding dimension.
  • Increasing degree heterogeneity raises ASE-LSE disagreement while increasing the eigengap lowers it.
  • The ratio of degree heterogeneity to eigengap serves as a unified predictor of the level of disagreement.
  • Because disagreement has no finite maximum, the space of possible disagreements is open at the upper end.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The heterogeneity-to-eigengap ratio could be computed on an observed network to decide whether the two embeddings are likely to give interchangeable results.
  • The same structural drivers might be checked before applying either method to decide whether one embedding is sufficient.
  • Extensions of the bound to directed or weighted graphs would require checking whether the scalar-multiple condition still isolates the agreement case.

Load-bearing premise

The graphs are undirected and unweighted and use the standard normalized or unnormalized Laplacian.

What would settle it

A single regular graph on which the two embeddings produce different subspaces for some dimension, or a sequence of graphs where the observed disagreement exceeds the value predicted by the Regularity Departure Bound for the measured heterogeneity and eigengap.

Figures

Figures reproduced from arXiv: 2605.22346 by Ian Gallagher, Minh Triet Pham.

Figure 1
Figure 1. Figure 1: Argument 1: degree heterogeneity drives latent subspace disagreement. Four panels [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: Argument 1: degree heterogeneity increases latent subspace disagreement. Four panels [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Argument 2: eigengap suppresses latent subspace disagreement. Four panels by [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 2
Figure 2. Figure 2: Argument 2: eigengap suppresses latent subspace disagreement. Four panels by [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Argument 3: the unified ratio CV(d)/δ(K) as predictor of latent subspace disagreement. All graphs pooled; colour encodes K. Overall Spearman ρ = +0.967 [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: Argument 3: the unified ratio CV(d)/δ(K) as predictor of latent subspace disagreement. All graphs pooled; colour encodes K. Overall Spearman ρ = +0.967. The most notable secondary feature is the visible K-banding: at any fixed ratio value, graphs with larger K (yellow) sit higher on the y-axis than those with smaller K (purple). This banding might superficially appear to be a failure of the joint ratio as … view at source ↗
Figure 4
Figure 4. Figure 4: Bound Point 1: non-vacuousness of the Regularity Departure Bound. Scatter of [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 4
Figure 4. Figure 4: Bound Point 1: non-vacuousness of the Regularity Departure Bound. Scatter of [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Bound Point 2: T1/T2 decomposition. Left: T1 and T2 shares against CV(d)/δ(K) with LOWESS smooths. Right: median shares as stacked bars by CV(d)/δ(K) quartile, with median α labelled [PITH_FULL_IMAGE:figures/full_fig_p011_5.png] view at source ↗
Figure 5
Figure 5. Figure 5: Bound Point 2: T1/T2 decomposition. Left: T1 and T2 shares against CV(d)/δ(K) with LOWESS smooths. Right: median shares as stacked bars by CV(d)/δ(K) quartile, with median α labelled [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
read the original abstract

Two of the most widely used methods for analysing graph data, Adjacency Spectral Embedding and Laplacian Spectral Embedding, often produce different results when applied to the same graph. Yet the structural reasons behind this disagreement remain incompletely understood. This paper provides an end-to-end account of ASE-LSE latent subspace disagreement. We first prove that the two methods produce identical latent subspaces for every embedding dimension whenever the Laplacian is a scalar multiple of the adjacency matrix, and show that this scalar relationship holds if and only if the graph is either regular or bipartite biregular. This anchor result identifies a sufficient condition for perfect agreement that pins down the floor of the disagreement spectrum and supplies the baseline for the perturbation analysis. We then prove that no maximal-disagreement graph or family of graphs exists: the disagreement is always strictly below its theoretical ceiling, and we exhibit a witness family demonstrating that no finite maximum is attainable, so the disagreement landscape has no maximiser. With both endpoints established, we derive a Regularity Departure Bound whose two terms isolate degree heterogeneity and eigengap as the primary structural factors influencing disagreement in the middle regime. Empirical validation across thousands of simulated graphs confirms the mechanisms predicted by the bound: heterogeneity pushes disagreement up, eigengap suppresses it, and their joint ratio emerges as a unified predictor of ASE-LSE disagreement, suggesting when the two embeddings can be treated as interchangeable and when they cannot.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript claims to deliver a complete characterization of the disagreement between Adjacency Spectral Embedding (ASE) and Laplacian Spectral Embedding (LSE) on graphs. It establishes an anchor result that the two embeddings yield identical latent subspaces for all dimensions precisely when the Laplacian matrix is a scalar multiple of the adjacency matrix, and proves this occurs if and only if the graph is regular or bipartite biregular. Building on this, it shows that the disagreement has no maximum (no maximizer exists), and derives a Regularity Departure Bound with terms for degree heterogeneity and eigengap. Empirical simulations across thousands of graphs are said to confirm that heterogeneity increases disagreement while eigengap decreases it.

Significance. The topic is important for practitioners choosing between ASE and LSE. If the anchor result and bound are correct, the work would provide clear structural guidance on when the embeddings agree and the factors driving their divergence. The demonstration that disagreement has no upper bound maximizer is a notable theoretical contribution. However, the central iff claim appears to rest on a condition that does not align with standard Laplacian definitions for the cited graph classes, which weakens the overall significance pending correction.

major comments (2)
  1. [Abstract] Abstract: The anchor result states that L = cA holds if and only if the graph is regular or bipartite biregular. However, under the standard combinatorial Laplacian L = D − A, for a d-regular graph this equation rearranges to dI = (c + 1)A, which cannot be satisfied by a non-trivial 0-1 adjacency matrix with zero diagonal. The same issue arises for bipartite biregular graphs. This contradiction means the sufficient condition for perfect agreement never materializes for the graphs identified in the iff statement, rendering the floor of the disagreement landscape and the subsequent perturbation analysis unsupported.
  2. [Abstract] Abstract: The manuscript refers to 'proofs' of the anchor result and the Regularity Departure Bound, but the provided abstract and description do not include the explicit assumptions, error terms, or full derivations for the perturbation step. Without these, it is not possible to assess whether the isolation of degree heterogeneity and eigengap holds under the stated conditions.
minor comments (1)
  1. The abstract mentions 'empirical validation across thousands of simulated graphs' but provides no details on the simulation design, graph models used, or quantitative metrics, which would aid reproducibility.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and insightful comments on our manuscript. We address each major comment point-by-point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: The anchor result states that L = cA holds if and only if the graph is regular or bipartite biregular. However, under the standard combinatorial Laplacian L = D − A, for a d-regular graph this equation rearranges to dI = (c + 1)A, which cannot be satisfied by a non-trivial 0-1 adjacency matrix with zero diagonal. The same issue arises for bipartite biregular graphs. This contradiction means the sufficient condition for perfect agreement never materializes for the graphs identified in the iff statement, rendering the floor of the disagreement landscape and the subsequent perturbation analysis unsupported.

    Authors: The referee correctly identifies a critical error in our characterization. Under the standard combinatorial Laplacian L = D - A, the relation L = cA cannot hold for any graph containing edges, as it would require equating the diagonal degree matrix D to a scalar multiple of the adjacency matrix A, which generally has nonzero off-diagonal entries. Consequently, our iff statement identifying regular and bipartite biregular graphs as the cases where L = cA is incorrect. While the implication that L = cA yields identical latent subspaces is valid (as the matrices share eigenspaces), the graphs achieving this condition are not as claimed, and in fact may not exist under standard definitions. We will revise the anchor result, correct the proofs, and adjust the discussion of the disagreement floor and perturbation analysis accordingly. This revision will strengthen the manuscript by providing an accurate baseline. revision: yes

  2. Referee: [Abstract] Abstract: The manuscript refers to 'proofs' of the anchor result and the Regularity Departure Bound, but the provided abstract and description do not include the explicit assumptions, error terms, or full derivations for the perturbation step. Without these, it is not possible to assess whether the isolation of degree heterogeneity and eigengap holds under the stated conditions.

    Authors: The complete proofs, including all assumptions, error terms, and derivations for the Regularity Departure Bound, are provided in the full manuscript (specifically in the sections detailing the anchor result and the bound). The abstract is intended as a concise summary. To improve clarity, we will revise the abstract to explicitly state the key assumptions and the form of the bound, ensuring readers can better assess the conditions under which degree heterogeneity and eigengap drive the disagreement. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained mathematical proof

full rationale

The paper's anchor result is an explicit mathematical proof establishing an iff relationship between the scalar-multiple condition on L and A and the external graph properties of regularity or bipartite biregularity. This is not a fitted quantity, self-definition, or reduction to the paper's own outputs; regularity and biregularity are standard, independently defined graph-theoretic notions. The subsequent Regularity Departure Bound is derived from the established endpoints (perfect agreement floor and absence of maximizer) without any step that renames a fit as a prediction or relies on a load-bearing self-citation. No self-citation chain, ansatz smuggling, or renaming of known empirical patterns appears in the derivation. The chain remains independent of the target disagreement measure itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard linear algebra facts about symmetric matrices and spectral embeddings; no free parameters or invented entities are mentioned in the abstract. The Regularity Departure Bound is presented as derived rather than postulated.

axioms (1)
  • standard math Standard properties of the adjacency and Laplacian matrices for undirected graphs (symmetry, non-negative entries, row sums equal to degrees).
    Invoked implicitly when stating that Laplacian is scalar multiple of adjacency iff regular or bipartite biregular.

pith-pipeline@v0.9.1-grok · 5787 in / 1395 out tokens · 26018 ms · 2026-06-30T16:18:11.711856+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Athreya, C

    A. Athreya, C. E. Priebe, M. Tang, V. Lyzinski, D. J. Marchette, and D. L. Sussman. A limit theorem for scaled eigenvectors of random dot product graphs. Sankhy\= a A , 78(1):1--18, 2016

    work page 2016

  2. [2]

    J. Cape, M. Tang, and C. E. Priebe. The two-to-infinity norm and singular subspace geometry with applications to high-dimensional statistics. The Annals of Statistics, 47(5):2405--2439, 2019

    work page 2019

  3. [3]

    Eckart and G

    C. Eckart and G. Young. The approximation of one matrix by another of lower rank. Psychometrika, 1(3):211--218, 1936

    work page 1936

  4. [4]

    Chung, B

    J. Chung, B. D. Pedigo, E. W. Bridgeford, B. K. Varjavand, H. S. Helm, and J. T. Vogelstein. GraSPy : Graph Statistics in Python . Journal of Machine Learning Research, 20(158):1--7, 2019

    work page 2019

  5. [5]

    J. F. Lutzeyer and R. T. Walden. Comparing graph spectra of adjacency and L aplacian matrices. In Complex Networks and Their Applications VIII, Springer, 2020

    work page 2020

  6. [6]

    J. F. Lutzeyer and R. T. Walden. Extending the D avis-- K ahan theorem for comparing eigenvectors of two symmetric matrices I : Theory. arXiv preprint arXiv:1903.08508, 2019

    work page arXiv 1903

  7. [7]

    Modell and P

    A. Modell and P. Rubin-Delanchy. Spectral clustering under degree heterogeneity: a case for the random walk L aplacian. arXiv preprint arXiv:2105.00987, 2021

    work page arXiv 2021

  8. [8]

    C. E. Priebe, Y. Park, J. T. Vogelstein, J. M. Conroy, V. Lyzinski, M. Tang, A. Athreya, J. Cape, and E. Bridgeford. On a two-truths phenomenon in spectral graph clustering. Proceedings of the National Academy of Sciences, 116(13):5995--6000, 2019

    work page 2019

  9. [9]

    Rubin-Delanchy, J

    P. Rubin-Delanchy, J. Cape, M. Tang, and C. E. Priebe. A statistical interpretation of spectral embedding: the generalised random dot product graph. Journal of the Royal Statistical Society: Series A, 84(4):1446--1473, 2022

    work page 2022

  10. [10]

    D. L. Sussman, M. Tang, D. E. Fishkind, and C. E. Priebe. A consistent adjacency spectral embedding for stochastic blockmodel graphs. Journal of the American Statistical Association, 107(499):1119--1128, 2012

    work page 2012

  11. [11]

    Tang and C

    M. Tang and C. E. Priebe. Limit theorems for eigenvectors of the normalized L aplacian for random graphs. The Annals of Statistics, 46(5):2360--2415, 2018

    work page 2018

  12. [12]

    Ye and L.-H

    K. Ye and L.-H. Lim. Schubert varieties and distances between subspaces of different dimensions. SIAM Journal on Matrix Analysis and Applications, 37(3):1176--1197, 2016

    work page 2016

  13. [13]

    Y. Yu, T. Wang, and R. J. Samworth. A useful variant of the Davis--Kahan theorem for statisticians. Biometrika, 102(2):315--323, 2015

    work page 2015

  14. [14]

    Girvan and M

    M. Girvan and M. E. J. Newman. Community structure in social and biological networks. Proceedings of the National Academy of Sciences, 99(12):7821--7826, 2002

    work page 2002

  15. [15]

    Lusseau, K

    D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behavioral Ecology and Sociobiology, 54:396--405, 2003

    work page 2003

  16. [16]

    W. W. Zachary. An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452--473, 1977

    work page 1977