NeurIPS 2020 | 超越同质性假设: 解决当前GNN的局限与并提出有效性设计

https://arxiv.org/pdf/2006.11468.pdf

Beyond Homophily in Graph Neural Networks

本文研究图网络神经在异构或低同质性下的半监督节点分类任务中的表示能力，(即在连接节点可能具有不同标签。

目前，许多GNN无法应用到此异构或低同质性的setting，甚至还不如没有考虑图结构MLP。为了解决该问题，本文确定了一组关键设计（ego嵌入和邻域嵌入的分离，高阶邻域以及intermediate表示的组合），这些设计可以有助于在异构结构下的图结构学习。

该工作将它们组合到一个图神经网络并且命名为H2GCN，实验分析表明，该模型具有强同质性的传统基准，在有异质性的合成网络和真实网络实验，能够使GNN的准确性分别提高了40％和27％。

Motivation

同质性是许多真实网络普遍存在的现象，也就是说链接的节点通常属于同一类或具有相似的特征（“物以类聚”）。例如，一个人的朋友和自己可能有相似的政治信仰或年龄，一篇论文倾向于引用同一研究领域的论文。GNN通过传播特征并通过不同机制（例如，平均，LSTM）将特征聚集进行建模。

但是，在现实世界中，也存在“异性相吸”的情况，也就是网络异质，具体来说：链接的节点可能来自不同的类或具有不同的功能。例如，大多数人倾向在约会中与异性交往，不同的氨基酸类型在蛋白质结构中交互比同类更频繁，网络骗子一般会跟受害者交互更多，并且远远大于跟自己同伙的联系。

许多现有的GNN都具有很强的同质性假设，因此它们无法推广到具有异质性（或同质性的低/中水平）的网络。

本文贡献

分析当前GNN的局限性：本文分析了GNN在异质网络上学习的局限性

异质性和新模型的设计：本文确定了一组关键设计，可以在不牺牲同质性的准确性的情况下，提升异质性图结构的学习：

（D1）ego embedding和邻居 embedding 分离;

（D2）高阶邻域和（D3）intermediate表示的结合。

本文从理论上证明设计合理，然后将它们组合到模型H2GCN中，该模型可以有效地适应异构和同构。与以前的GNN模型进行比较，有加大的提升。

在合成数据集上的效果

具体方法细节，这里就不多介绍了，跟之前的工作GemoGCN, Non-localGNN本质上类似的,下面主要看看本文的理论分析。以下证明都假设节点的向量是one-hot向量。

定理1：GCN层要比分离了自身与邻居的嵌入鲁棒性差

这意味着把自己跟邻居直接结合在这种图上效果不行，同时也是GraphSAGE在某些情况更好的原因

定理2：在一个异质图上，2-hop的邻域总是被同质性的节点主导

这个定理主要解释ChebyNet, MixHop为什么效果比GCN, GAT好

定理3：高异质性率的图在谱域有更高的频率

这意味着高频和低频信号都有用

下面是一些实验结果：