AGSEI: Adaptive Graph Structure Estimation With Long-Tail Distributed Implicit Graphs

Yunfei He

doi:10.1109/TETC.2024.3480132

2024-01-01

PRE

DOI：10.1109/TETC.2024.3480132

原文链接

原文求助

摘要

En 中文

凭借其显著优势，图神经网络（GNN）成为嵌入图结构数据并应用于各领域的强大工具。特别是，大多数GNN中普遍存在的一个假设是底层图结构的可靠性。这一通常隐含的假设可能会无意中导致通过虚假链接等结构传播误导性信息。为应对这一挑战，已开发出多种图结构学习（GSL）方法。在这些方法中，一种流行的方法是构建简单直观的K近邻（KNN）图作为样本以推断真实图结构。然而，遵循单点分布的KNN图容易误导真实图结构的估计。主要原因在于，从统计角度看，KNN图作为样本遵循单点分布，而真实图结构作为总体则整体上大多遵循长尾分布。理论上，样本与总体应共享相同分布；否则，准确推断真实图结构将变得困难。为解决此问题，本文提出了一种基于长尾分布隐式图的自适应图结构估计方法，简称AGSEI。AGSEI包含三个主要组件：长尾隐式图构建、显式图结构估计和联合优化。第一组件利用多层图卷积网络学习从低阶到高阶的节点表示，计算节点相似性并构建多个对应的长尾隐式图。由于原始不完善的图结构可能误导GNN传播虚假信息，这降低了长尾隐式图的可靠性。AGSEI通过引入希尔伯特-施密特独立性准则来限制无关信息的聚合，即最大化预测标签与真实标签之间的依赖性。通过此策略，AGSEI能够学习与标签相关的节点特征，以促进可靠长尾隐式图的构建，并随后提供自适应的多视角图结构信息，支持后续GSL。在第二组件中，采用期望最大化算法的随机块模型（SBM）进行图结构估计。考虑到单一GSL难以逼近真实图结构，第三部分考虑了长尾隐式图构建与显式图结构估计的联合优化，通过交替优化两部分直至模型收敛。我们在五个公开数据集上进行了包括分类和聚类任务在内的多项实验。这些实验不仅展示了AGSEI的性能，还证实了其估计的图结构与长尾分布一致。

Keyword:

Graph neural network

graph structure learning

long-tail distributed

hilbert-schmidt independence criterion

stochastic block model