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

Ian Gallagher; Minh Triet Pham

arxiv: 2605.22346 · v3 · pith:TGYEBITBnew · 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

Pith reviewed 2026-05-22 03:41 UTC · model grok-4.3

classification 📊 stat.ML cs.LGcs.SI

keywords adjacency spectral embeddinglaplacian spectral embeddingdegree heterogeneityeigengapgraph regularitylatent subspacecommunity structurespectral methods

0 comments

The pith

Regular graphs force adjacency and Laplacian spectral embeddings to recover identical latent subspaces.

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

The paper shows that when every node has exactly the same degree, adjacency spectral embedding and Laplacian spectral embedding produce the same latent subspaces. Any unevenness in node degrees creates disagreement, and the authors supply an explicit bound that separates two opposing effects: degree heterogeneity increases the gap while community structure strength, captured by the eigengap, shrinks it. Thousands of simulated networks confirm that the ratio of these two quantities reliably indicates when the two embeddings can be treated as interchangeable.

Core claim

Regularity is a sufficient condition for perfect agreement: when every node has the same number of connections, the two methods produce identical latent subspaces. Any departure from this regularity introduces disagreement, and we prove an explicit bound whose two terms suggest the structural ingredients controlling it: degree heterogeneity, which pushes the methods apart, and community structure strength, which pulls them back together.

What carries the argument

The explicit bound on subspace disagreement, with one term driven by degree heterogeneity and the opposing term driven by the eigengap that measures community structure.

If this is right

In any regular graph the two embeddings can be used interchangeably without loss in the recovered latent subspace.
Greater spread in node degrees increases the subspace disagreement between the two methods.
Larger eigengap, indicating stronger community structure, reduces the disagreement and improves interchangeability.
The ratio of degree heterogeneity to eigengap size predicts whether the embeddings behave as equivalent representations.

Where Pith is reading between the lines

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

Practitioners working with real networks could first compute degree variance and the leading eigengap to decide whether ASE and LSE are likely to give compatible results.
The bound may suggest simple preprocessing steps, such as degree normalization, to reduce disagreement without changing the underlying graph model.
Similar disagreement phenomena could appear in directed or weighted graphs once an appropriate notion of regularity is defined.

Load-bearing premise

The graph is undirected and the eigenvectors of interest are separated by an eigengap that corresponds to community structure.

What would settle it

Finding measurable disagreement between ASE and LSE on a perfectly regular graph, or perfect agreement on a clearly non-regular graph, would contradict the central claim.

Figures

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

**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 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 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 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 ↗

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.

Desk Editor's Note private letter to a colleague

Regularity guarantees ASE and LSE produce the same latent subspace, with an explicit bound showing degree heterogeneity increases disagreement while eigengap from community strength reduces it.

read the letter

The key takeaway is that regularity is sufficient for ASE and LSE to produce identical latent subspaces, and the paper derives an explicit bound on their disagreement split into degree heterogeneity pushing them apart and eigengap from community structure pulling them together. This separation of drivers is the new part. Earlier work has noted that the two embeddings can differ, but this gives a structural account with a bound that directly ties disagreement to those two quantities. The simulations across thousands of networks add weight by showing the predicted relationships hold in practice, and the ratio of heterogeneity to community strength serves as a predictor for interchangeability. That combination of proof and large-scale check is solid. The soft spots are mostly about scope. The bound assumes an undirected graph where the community eigenvectors are well-separated by a positive eigengap, which rules out some cases like directed networks or graphs with repeated eigenvalues. The paper likely states these conditions, but if they are not broad, the result applies mainly to standard stochastic block model settings. The empirical validation is on simulated data, which matches the theory but doesn't test robustness on empirical networks with different degree distributions or noise. These are not central flaws, just boundaries on where the result applies cleanly. This paper is for network analysts and embedding users who need to decide when ASE and LSE can be used interchangeably. Readers focused on spectral graph theory or practical graph ML will find the bound and the empirical confirmation useful for understanding discrepancies. It shows clear thinking on the math and honest engagement with the literature on graph embeddings, so it deserves a serious referee. I recommend putting it through peer review.

Referee Report

2 major / 2 minor

Summary. The paper claims that regularity (constant node degree) is a sufficient condition for perfect agreement between the latent subspaces produced by Adjacency Spectral Embedding (ASE) and Laplacian Spectral Embedding (LSE) on undirected graphs. It derives an explicit bound on subspace disagreement whose terms isolate degree heterogeneity as the factor increasing disagreement and community strength (via eigengap) as the factor suppressing it. Both the bound and the drivers are validated empirically across thousands of simulated networks, with the heterogeneity-to-eigengap ratio proposed as a predictor of when the two embeddings may be treated as interchangeable.

Significance. If the central claims hold, the work supplies a structural account of when and why two standard graph embedding techniques diverge, which is useful for practitioners selecting embeddings and for theoretical understanding of spectral methods on graphs. The explicit bound together with large-scale reproducible simulations on simulated networks constitute clear strengths that provide falsifiable predictions and concrete guidance on interchangeability.

major comments (2)

[§3, Theorem 1] §3, Theorem 1 (perfect-agreement claim): the statement that regularity implies identical ASE and LSE subspaces rests on the graph being undirected and on L = dI - A sharing the exact eigenspace; the additional requirement that the relevant eigenvectors remain simple and separated by a positive eigengap that directly quantifies community strength is invoked but not accompanied by explicit conditions on eigenvalue multiplicity or on the generative model (SBM versus configuration model), which is load-bearing for the generality of the subsequent bound.
[§4, derivation of the explicit bound] §4, derivation of the explicit bound: the two-term decomposition (heterogeneity pushing apart, eigengap pulling together) is presented as derived from perturbation analysis, yet the proof sketch does not state the precise conditions under which the eigengap remains positive and the perturbation terms remain controlled when eigenvalues may collide or when the graph is weighted or directed; without these, the structural-driver interpretation risks being model-specific rather than general.

minor comments (2)

[Notation] The definition of the subspace disagreement metric (e.g., whether it is the sine of principal angles or a Frobenius-type distance) is introduced late; moving a precise statement to the notation section would improve readability.
[Figures 3-5] Simulation figures lack explicit statements of the exact parameter ranges and number of replicates per cell; adding these to the captions would make the empirical validation easier to reproduce.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive and detailed comments. We address each major comment below and are prepared to revise the manuscript to improve clarity on assumptions and scope.

read point-by-point responses

Referee: [§3, Theorem 1] §3, Theorem 1 (perfect-agreement claim): the statement that regularity implies identical ASE and LSE subspaces rests on the graph being undirected and on L = dI - A sharing the exact eigenspace; the additional requirement that the relevant eigenvectors remain simple and separated by a positive eigengap that directly quantifies community strength is invoked but not accompanied by explicit conditions on eigenvalue multiplicity or on the generative model (SBM versus configuration model), which is load-bearing for the generality of the subsequent bound.

Authors: We agree that explicit statement of assumptions improves the theorem's presentation. Theorem 1 applies to undirected graphs, where constant degree makes the combinatorial Laplacian L = D - A identical to dI - A, so that A and L share the same eigenspace. The positive eigengap is invoked to guarantee that the relevant eigenvectors are simple, which is a standard prerequisite for the subsequent perturbation analysis. While the empirical sections use the stochastic block model, the algebraic identity in Theorem 1 holds for any regular undirected graph and does not depend on a specific generative model. In revision we will add a dedicated remark listing the eigenvalue-simplicity and undirected-graph assumptions and clarifying that the result is model-agnostic within the regular undirected setting. revision: yes
Referee: [§4, derivation of the explicit bound] §4, derivation of the explicit bound: the two-term decomposition (heterogeneity pushing apart, eigengap pulling together) is presented as derived from perturbation analysis, yet the proof sketch does not state the precise conditions under which the eigengap remains positive and the perturbation terms remain controlled when eigenvalues may collide or when the graph is weighted or directed; without these, the structural-driver interpretation risks being model-specific rather than general.

Authors: The bound in §4 is obtained via a standard perturbation argument (Davis-Kahan type) that requires a positive eigengap to control the subspace distance. We acknowledge that the current proof sketch could state these conditions more explicitly, including safeguards against eigenvalue collisions. The entire development is restricted to undirected, unweighted graphs; weighted or directed graphs would require different normalizations and fall outside the paper's scope. In the revision we will insert a precise paragraph in §4 listing the conditions that keep the eigengap positive and the perturbation terms bounded, thereby making the domain of the structural-driver interpretation transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity: bound derived from graph assumptions, not reduced to inputs by construction

full rationale

The paper states that regularity is a sufficient condition for identical ASE and LSE subspaces and derives an explicit bound whose terms involve degree heterogeneity and eigengap (as community strength). No quoted equations or steps in the abstract or described derivation reduce the bound to a fitted parameter, self-definition, or load-bearing self-citation chain. The empirical validation across simulated networks is presented as confirmation rather than the source of the bound itself. The derivation chain remains self-contained under the stated undirected-graph and eigengap-separation assumptions, with no evidence that the central claim is equivalent to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Based solely on the abstract, the central claim rests on standard spectral-graph assumptions (undirected graphs, existence of an eigengap tied to community structure) rather than newly invented entities or fitted constants; no free parameters are mentioned.

axioms (1)

domain assumption The graph is undirected and the relevant eigenvectors are separated by an eigengap that measures community strength.
Invoked when the bound is stated and when community structure strength is identified with the eigengap.

pith-pipeline@v0.9.0 · 5688 in / 1385 out tokens · 48359 ms · 2026-05-22T03:41:28.770109+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean absolute_floor_iff_bare_distinguishability unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Proposition 3.1 (Regular Anchor): If A represents a d-regular graph ... then ASE and LSE produce identical eigenvectors: ∥sin Θ(UA, UL)∥F = 0.
IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 3.2 (Regularity Departure Bound) ... ∥sin Θ(UA, UL)∥F ≤ 2∥E∥F/δ(K) + α(2+α)√(n d̄)/δ(K)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.