Departure from Regularity: Degree Heterogeneity and Eigengap as the Structural Drivers of ASE-LSE Latent Subspace Disagreement

📄 arXiv: 2605.22346v1 📥 PDF

作者: Minh Triet Pham, Ian Gallagher

分类: stat.ML, cs.LG, cs.SI

发布日期: 2026-05-21

备注: 12 pages (excluding references + appendices), 5 figures

💡 一句话要点

揭示图结构异质性与特征值间隙对谱嵌入差异的影响

🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation)

关键词: 图嵌入 谱嵌入 邻接谱嵌入 拉普拉斯谱嵌入 度异质性 社群结构 图结构分析

📋 核心要点

  1. 现有图嵌入方法（ASE和LSE）在相同网络上表现出差异，但其结构性原因尚不明确。
  2. 论文核心思想是正则性是ASE和LSE一致的充分条件，度异质性导致差异，社群结构强度抑制差异。
  3. 实验通过大量模拟网络验证了度异质性与社群结构强度对嵌入差异的影响，并提出了可互换性的预测指标。

📝 摘要（中文）

邻接谱嵌入(ASE)和拉普拉斯谱嵌入(LSE)是两种常用的图数据分析方法，但它们在应用于同一网络时常产生不同的结果。本文旨在从结构角度解释这种差异。研究表明，正则性是完美一致的充分条件：当每个节点具有相同数量的连接时，两种方法产生相同的潜在子空间。任何偏离正则性的情况都会引入差异。论文提出了一个明确的界限，其两项分别代表了控制差异的结构因素：度异质性，它使两种方法分离；以及社群结构强度，它使它们靠拢。通过数千个模拟网络的实验验证，证实了异质性会增加差异，社群强度会抑制差异，并且它们的比率可以很好地预测何时可以将两种嵌入视为可互换，以及何时不能。

🔬 方法详解

问题定义：论文旨在解决当对同一图数据使用邻接谱嵌入(ASE)和拉普拉斯谱嵌入(LSE)时，两种方法产生不同结果的问题。现有方法缺乏对这种差异的结构性解释，难以判断何时可以使用哪种嵌入方法。痛点在于无法根据图的结构特征来预测和理解两种嵌入的差异。

核心思路：论文的核心思路是，图的正则性（即所有节点的度相同）是ASE和LSE产生一致结果的充分条件。当图偏离正则性时，度异质性会使两种嵌入方法产生差异，而社群结构强度则会抑制这种差异。通过分析度异质性和社群结构强度之间的关系，可以预测两种嵌入方法的差异程度。

技术框架：论文的技术框架主要包括以下几个步骤： 1. 理论分析：推导出一个明确的界限，用于量化ASE和LSE之间的差异，该界限由度异质性和社群结构强度两项组成。 2. 模拟网络生成：生成大量具有不同度异质性和社群结构强度的模拟网络。 3. 嵌入计算：对每个模拟网络分别计算ASE和LSE。 4. 差异评估：计算ASE和LSE之间的差异，并与理论界限进行比较。 5. 验证分析：验证度异质性和社群结构强度对嵌入差异的影响，并评估它们比率的预测能力。

关键创新：论文最重要的技术创新点在于，它从图的结构角度解释了ASE和LSE之间的差异，并提出了一个可量化的界限，该界限能够根据图的度异质性和社群结构强度来预测两种嵌入方法的差异程度。这与以往的研究主要关注算法本身不同，而是深入探讨了图的结构特征对嵌入结果的影响。

关键设计：论文的关键设计包括： 1. 差异度量：选择合适的度量方式来量化ASE和LSE之间的差异，例如子空间之间的距离。 2. 模拟网络设计：设计能够控制度异质性和社群结构强度的模拟网络生成方法。 3. 理论界限推导：推导出一个紧凑且易于计算的理论界限，该界限能够准确地反映度异质性和社群结构强度对嵌入差异的影响。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，度异质性与ASE和LSE的差异呈正相关，而社群结构强度与差异呈负相关。论文提出的理论界限能够准确地预测两种嵌入方法的差异程度。此外，度异质性与社群结构强度的比率可以作为判断两种嵌入方法是否可互换的有效指标。在模拟网络上验证了该指标的有效性。

🎯 应用场景

该研究成果可应用于各种图数据分析场景，例如社交网络分析、生物网络分析和知识图谱分析。通过理解ASE和LSE的差异，可以选择更合适的嵌入方法，提高分析结果的准确性和可靠性。此外，该研究还可以用于设计更鲁棒的图嵌入算法，使其对图的结构变化更加稳定。

📄 摘要（原文）

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 network. Yet the structural reasons behind this disagreement remain incompletely understood. This paper provides a structural account. We show that 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. We validate both drivers empirically across thousands of simulated networks, confirming that heterogeneity drives disagreement up, community strength suppresses it, and their ratio provides a strong predictor of when the two embeddings can be treated as interchangeable and when they cannot.