[WWW2021]图结构估计神经网络

题目：Graph Structure Estimation Neural Networks

作者：Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi and Xing Xie

简介：尽管现有的GNN已成功应用于各种场景，但存在一个基本的假设：所观察到的图结构是正确的且符合GNN的性质。实际上，由于图通常抽取自复杂的交互系统，该假设总是被违反。原因之一是这些交互系统通常包含不确定性或错误。例如，在蛋白质相互作用图中，传统的实验误差是错误的主要来源。另一个原因是数据缺失是不可避免的。例如，Internet构建的图通过检查路由表或跟踪路由路径集合确定，而这两个表仅给出了边的子集。已经有研究表明不可靠的图结构可能会严重限制GNN的表示能力，其中一个典型的例子是GNN的性能会在同配性（即同一社区内的节点倾向于相互连接）差的图上大大降低。简而言之，在实际的图中普遍存在缺失、无意义甚至错误的边，这导致其与GNN的性质不匹配，并对结果的准确性或正确性产生影响。因此，迫切需要探索适宜于GNN的图结构。

然而，有效学习适合于GNN的图结构在技术上具有挑战性。我们认为，需要解决两个障碍。（1）应考虑图生成机制。网络科学的很多文献中已经证明图的生成可能受某些基本原则的约束，如随机块模型模型。考虑这些原则，可以从根本上驱使学得的图保持规则的全局结构，并对实际观测中的噪声更鲁棒。不幸的是，大多数当前方法对每条边进行参数化，没有考虑全局结构和图的基础生成机制，因此学得的图对噪声和稀疏性的容忍度较低。（2）应该利用多方面信息以减少偏差。从一个信息源学习图结构不可避免地会导致偏差和不确定性。合理的假设是如果一条边在多次测量中存在，则边存在的置信度会更大。因此，一个可靠的图结构应该考虑全面的信息，尽管要获得多视图的信息并描述它们与GNN的关系是很复杂的。现有的方法主要利用特征相似性，从而使学得的图易受单一视图偏差的影响。

为了解决上述问题，在本文中我们提出了图结构估计神经网络（GEN），通过估计适宜于GNN的图结构来提高节点分类性能。我们首先分析GNN的性质以匹配适当的图生成机制。GNN作为低通滤波器，平滑邻域以使相邻节点表示相似，适用于具有社区结构的图。因此，我们提出结构模型约束图生成过程，假设图是从随机块模型（SBM）中产生的。此外，除观察到的图结构和节点特征外，我们还创造性地利用多阶邻域信息来规避偏差，并提出观测模型将上述多视图信息作为最佳图结构的观测共同建模。为了估计最佳图结构，我们在GNN训练期间构造观测集合，并基于结构和观测模型应用贝叶斯推断来计算图结构的后验分布。最后，估计的图结构和GNN的参数通过精心设计的迭代优化实现彼此增强。