Uncovering Locally Low-dimensional Structure in Networks by Locally Optimal Spectral Embedding

📄 arXiv: 2603.11965v1 📥 PDF

作者: Hannah Sansford, Nick Whiteley, Patrick Rubin-Delanchy

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

发布日期: 2026-03-12

💡 一句话要点

提出局部邻接谱嵌入(LASE)，解决全局谱嵌入在复杂网络中局部几何结构模糊问题

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

关键词: 图嵌入 谱方法 局部低维结构 网络可视化 社交网络分析

📋 核心要点

  1. 现有全局邻接谱嵌入(ASE)难以捕捉复杂网络的局部几何结构，导致信息损失。
  2. 论文提出局部邻接谱嵌入(LASE)，通过加权谱分解聚焦局部低维结构，提升局部表示能力。
  3. 实验证明LASE在局部重建和可视化方面优于全局方法，并结合UMAP实现高保真全局可视化。

📝 摘要（中文）

标准的邻接谱嵌入(ASE)依赖于全局低秩假设，这通常与现实世界网络的稀疏、传递结构不兼容，导致局部几何特征被“模糊化”。为了解决这个问题，我们引入了局部邻接谱嵌入(LASE)，它通过加权谱分解来揭示局部低维结构。在具有核特征图的潜在位置模型下，我们将潜在位置的图像视为无限维特征空间中的局部低维集合。我们建立了有限样本边界，量化了局部化的统计成本与通过针对嵌入的局部低维区域而实现的减少的截断误差之间的权衡。此外，我们证明了充分的局部化会诱导快速的谱衰减和明显的谱隙的出现，从理论上证明了低维局部嵌入的合理性。在合成和真实网络上的实验表明，LASE在全局和子图基线上改进了局部重建和可视化，并且我们引入了UMAP-LASE，用于将重叠的局部嵌入组装成高保真全局可视化。

🔬 方法详解

问题定义：现实世界中的网络通常具有稀疏和传递的结构，这与标准邻接谱嵌入(ASE)所依赖的全局低秩假设不符。ASE在处理这类网络时，会模糊局部几何特征，导致无法有效提取和利用网络的局部结构信息。因此，需要一种能够更好地捕捉网络局部低维结构的方法。

核心思路：论文的核心思路是通过局部加权的方式，对网络的局部区域进行谱分解，从而提取局部低维结构。具体来说，将潜在位置的图像视为无限维特征空间中的局部低维集合，并通过局部化操作，使得谱分解的结果更加关注局部区域的信息，从而减少全局低秩假设带来的影响。

技术框架：LASE的整体框架包括以下几个主要步骤：1) 局部化：对网络中的每个节点，确定其局部邻域，并计算相应的权重。2) 加权邻接矩阵：根据局部邻域的权重，构建加权的邻接矩阵。3) 谱分解：对加权的邻接矩阵进行谱分解，得到局部低维嵌入。4) 可视化/重建：利用局部低维嵌入进行可视化或局部结构重建。对于全局可视化，论文还提出了UMAP-LASE，将重叠的局部嵌入组装成全局可视化。

关键创新：LASE的关键创新在于引入了局部化的思想，通过加权谱分解，使得嵌入过程更加关注网络的局部结构。与全局谱嵌入相比，LASE能够更好地捕捉网络的局部几何特征，从而提高局部重建和可视化的效果。此外，论文还从理论上证明了充分的局部化会诱导快速的谱衰减和明显的谱隙的出现，为局部低维嵌入提供了理论支撑。

关键设计：LASE的关键设计包括：1) 局部邻域的选择：如何确定每个节点的局部邻域，例如使用k近邻算法。2) 权重的计算：如何计算局部邻域的权重，例如使用高斯核函数。3) 嵌入维度的选择：如何选择局部低维嵌入的维度，需要权衡局部信息的保留和计算复杂度。4) UMAP-LASE的组装策略：如何将重叠的局部嵌入组装成全局可视化，需要考虑局部嵌入之间的对齐和融合。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，LASE在合成和真实网络上均优于全局和子图基线。具体来说，LASE在局部重建任务上取得了显著的性能提升，并且能够生成更清晰、更具可解释性的网络可视化结果。UMAP-LASE能够将重叠的局部嵌入组装成高保真全局可视化，进一步提升了LASE的实用性。

🎯 应用场景

LASE可应用于社交网络分析、生物网络分析、推荐系统等领域。例如，在社交网络中，LASE可以用于发现社区结构和用户之间的局部关系；在生物网络中，可以用于识别蛋白质复合物和基因调控模块；在推荐系统中，可以用于提高推荐的准确性和个性化程度。LASE通过提升对网络局部结构的理解，为这些应用带来更深入的洞察和更有效的解决方案。

📄 摘要（原文）

Standard Adjacency Spectral Embedding (ASE) relies on a global low-rank assumption often incompatible with the sparse, transitive structure of real-world networks, causing local geometric features to be 'smeared'. To address this, we introduce Local Adjacency Spectral Embedding (LASE), which uncovers locally low-dimensional structure via weighted spectral decomposition. Under a latent position model with a kernel feature map, we treat the image of latent positions as a locally low-dimensional set in infinite-dimensional feature space. We establish finite-sample bounds quantifying the trade-off between the statistical cost of localisation and the reduced truncation error achieved by targeting a locally low-dimensional region of the embedding. Furthermore, we prove that sufficient localisation induces rapid spectral decay and the emergence of a distinct spectral gap, theoretically justifying low-dimensional local embeddings. Experiments on synthetic and real networks show that LASE improves local reconstruction and visualisation over global and subgraph baselines, and we introduce UMAP-LASE for assembling overlapping local embeddings into high-fidelity global visualisations.