揭示图嵌入中ASE与LSE差异的结构根源,给出可预测分歧的理论框架。
The ASE-LSE Disagreement Landscape: An End-to-End Characterisation of Extremes and Structural Drivers

- 证明当图是正则或双正则二分图时,两种嵌入完全一致
- 发现分歧无最大值,且度异质性和特征间隙是影响分歧的核心因素
- 提出可量化分歧的规律,适用于评估图嵌入方法的可互换性
邻接谱嵌入(ASE)和拉普拉斯谱嵌入(LSE)是分析图数据的两种主流方法,但对同一图常产生不同结果,其结构性原因尚不清晰。本文首次提供从头到尾的完整刻画:证明当拉普拉斯矩阵为邻接矩阵的标量倍时,两种嵌入在所有维度下一致,且该条件等价于图是正则或双正则二分图。这一基准结果确立了分歧的下限,并用于后续扰动分析。进一步证明不存在最大分歧图或图族,分歧始终低于理论上限,且存在实例表明分歧无上界。在此基础上,推导出‘规则偏离界’,其两项分别捕捉度异质性和特征间隙,共同决定中段分歧水平。上千个模拟图的实证验证了该界预测:度异质性提升分歧,特征间隙抑制分歧,二者比值成为统一预测指标,明确指示何时可互换使用ASE与LSE。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。