点击蓝字

关注我们

AI TIME欢迎每一位AI爱好者的加入！

以下文章来自 知乎 栾思焘：

文章：When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishability.（🔗链接：https://zhuanlan.zhihu.com/p/653631858）

代码 (近期更新，敬请关注)：🔗链接：

‍https://link.zhihu.com/?target=https%3A//github.com/SitaoLuan/When-Do-GNNs-Help

这篇博客尽量略去technical的部分，希望可以把主要意思传递清楚，需要了解细节的话可以看原文。

同配(Homophily)指的是在图中，标签一样（同类）的节点更有可能连接到一起；相反，不同类节点更有可能连接到一起的图被称为异配图。

Graph-aware Models vs. Graph-agnostic Models‍‍

Graph-aware models指的是在模型的每一层都会根据图结构做feature aggregation (这里统一用mean aggregation而不是），如GCN, SGC-1；Graph-agnostic models指的是模型没有用到图结构信息，例如两层或者一层MLP(MLP-2, MLP-1)。从上面的公式可以看到，如果把G-aware models每一层的抹去，就得到一个coupled的G-agnostic models，例如GCN和MLP-2，SGC-1和MLP-1。由此看来，一个GNN表现得好不好，关键就取决于的质量。那什么是“好”的或者“差”的？用什么指标可以衡量出的好坏？‍‍‍�^rw‍‍

‍

在以往的研究中人们普遍认为，在节点分类任务上，G-aware models之所以比G-agnostic models更优越，是图的同配性导致的；而异配性会导致G-aware model表现得更差，因为不同类的节点相互连接，会导致聚合的时候将不同类节点的特征相互混合，以至于让分类器无法分辨不同类的节点。但事实真的是这样吗？有研究提出了反对意见。

Homophily wins, Heterophily loses? No❌

Fig1: Example

[1]认为，GNN不需要同配这个条件也能表现好，只要同类节点的neighborhood pattern是一样的就可以，例如上图中的节点1，2，他们的邻居都来自不同类，但是heterophily pattern是一样，因此1，2在aggregation之后的embedding是一样，不影响他们的区分度。

然而上面这个分析显然忽略了一点：它只考虑了类内(intra-class)节点的区分度 (node distinguishability)，而忽略了类间(inter-class)节点的区分度，例如上图中的节点3，它的neighborhood pattern跟1，2相同但是来自绿类，在aggregation之后它会被错误的分到跟1，2是同一类中。这个例子告诉我们，我们必须同时考虑类内和类间的节点区分度，并且我们认为一个理想的情况是：类间节点的区分度大于类内节点的区分度。以下我们会尝试量化节点区分度，并研究homophily是如何影响它的。

CSBM-H及其节点区分度

我们先设计一个toy model：Contextual Stochastic Block Model for Homophily/Heterophily (‍CSBM-H)。假设有两组节点 ‍�0,�1

节点特征从高斯分布

节点特征从高斯分布‍ 中产生,节点的degree为‍ 中节点会连接‍ 个类内节点和‍ 个类间节点，‍ 中节点的邻居也用相同方式产生。Full-pass (FP), Low-pass (LP)和High-pass (HP) filters滤过的feature也可以直接算出来 (关于三种filters，请看[2], 简而言之，FP filtered features, 也即原feature‍‍ ; LP filtered feature ‍ ; HP filtered feature‍

Probabilistic Bayes Error 下面我们来计算这个toy model的节点区分度：首先我们算出它的Optimal Bayes Classifier ,根据我们可以计算出它的Probabilistic Bayes Error(PBE)，这个error可以用来度量节点区分度。

算出来的结果长上面这样，它跟广义卡方分布的Cumulative Distribution Function有关。具体计算过程请看原文章。我们可以用数值方法算出给定下的PBE，它能很精确描述节点区分度也能可视化，不过我们很难直接从公式中看出节点区分度是如何被类内以及类间节点区分度共同影响的。于是我们还想找一个更加可解释的度量。

Negative Generalized Jeffreys Divergence一个基于KL-divergence的度量，长下面这样，其中是两个分布中心的集合距离的平方；，假设，那我们有。

‍

‍‍

‍

‍‍

从‍可以看出节点区分度依赖两项：一个normalized distance项，还有一个variance ratio项。distance‍其实度量的是类间节点区分度，它的normalization项‍刻画了类内节点区分度，这与我们的claim的节点区分度是由类内和类间节点区分度共同影响是一致的。ratio项度量两个类内节点区分度的差异的影响，差异越大节点越容易区分。‍

‍

‍

根据上面定义的两个度量，我们可以可视化homophily ℎ 与节点区分度的关系。我们把标准CSBM-H设置为

‍

‍‍‍，LP filtered feature的PBE和‍曲线是 钟型(山峰型)的，这表明homophily副作用最大的区域并不是homophily value最小的区域，而是中等水平的homophily，这与一般的认知不同，但是与[2]中的发现是一致的，我们称这种现象为Mid-homophily Pitfall。

我们还观察到，FP-, LP-, HP-filtered features在不同的homophily区间会分别得到最小的 PBE和‍，我们分别称他们为FP区域(黑色), LP区域(绿色), HP区域(红色)。LP filter在homophily很低或很高的区间(区域两端)表现最好，HP filter在低到中homophily区域表现最好，FP filter(原始feature)在中到高homophily区间表现得好。‍‍

通过可视化与节点区分度的关系，我们可以研究不同filters,节点degree,类内方差(）对于节点区分度有何影响。下面我们举一个ablation study的例子，更多的ablation请看原文章。

‍

Ablation Study

‍

‍

在上图中，我们增加‍后，发现三条PBE和‍曲线都上升了，这意味着 HP-, LP-, and FP- filtered features都变得更加难以区分。同时HP区域大幅收缩，FP区域大幅扩张，这表明原feature对于不平衡的类内节点区分度更加robust，特别是在低homophily区域。‍

‍

‍More General Theoretical Analysis

除了上面这个toy example,我们还想把在更一般的条件下研究节点区分度。借鉴[1]中提出的某些条件，我们换了个角度去思考节点区分度。我们没有像[1]一样研究aggregation后节点embedding跟它的期望之间的距离，因为这个距离只体现了类内节点区分度，而只研究类内节点区分度已经被发现是一个不完整的理解了。‍我们准备研究的是“类内节点距离有多么显著地小于类间节点距离？‍”。定理具体内容请看原文。

结论 定理中不等式的上界依赖一个distance项 (类间节点区分度)和normalized variance项 (类内节点区分度),这与我们之前提到的”节点区分度是由类内和类间节点区分度共同影响“是一致的。

HP filter 我们还发现HP filter可以解决某些异配问题是因为它依赖relative center distance， 原理见上图：当homophily下降时，聚合后的中心 ‍会远离原来的中心‍,那么相对距离(紫色线)会越来越大(绿色短虚线表示移动方向)，那么定理中的上界也会大，表明类内节点区分度更有可能小于类间节点区分度，于是说明HP filter会帮助增加某些异配图中的节点区分度。

实‍验研究

我们想验证在实际中，“类内节点距离小于类间节点距离“是否与G-aware vs. G-agnostic models的表现有强相关性。我们计算了在GCN, SGC-1, MLP-2, MLP-1的输出层中类内节点距离显著小于类间节点距离的比例Prop，利用假设检验计算GCN vs. MLP-2和SGC-1 vs. MLP-1的Prop值是不是显著不一样，得到p-value。根据下面表格我们可以发现，在绝大部分情况下 (除了GCN vs. MLP-2 on PubMed), 当‍显著成立时, G-aware models 会比它coupled的G-agnostic models表现差，反之亦然. 这表明强相关性是存在的,且不论homophily水平是多少。

‍同时，这也提醒我们，p-value可以作为比homophily更好的performance metric。另外，p-value可以提供一个具有统计意义的阈值，例如‍, 这个性质也是现存同配度量所不具备的。

超越同配的新度量方法

用上面的方法得到p-value需要训练并且fine-tune模型，这样在实际中会费时费力，于是我们只用不需要iterative training的简单分类器的输出层来进行运算。这里我们选择Gaussian Naïve Bayes (GNB)和Kernel Regression (KR) with Neural Network Gaussian Process (NNGP)。从表1的结果看, KR 和 GNB都显著优于现有的同配度量，把错误从至少5个减少到1个，更多结果以及具体计算方法请看原文。

我们根据[2]中的方法合成了不同homophily level的数据，在下图(左)中我们发现‍‍‍‍‍与两个阈值NT0.5或者SST0.05的交叉点(绿)，跟SGC-1和MLP-1表现性能的交叉点(红)完美吻合，‍的曲线也分SGC-1一样是U型的，对于‍ 曲线(蓝)和GCN, MLP-2表现曲线也是类似的。这说明新的度量可以非常准确的衡量什么时候G-aware models会比G-agnostic models要好。‍

‍

‍‍‍

而在下图(右)中我们发现，node homophily (橙), class homophily (粉), generalized edge homophily (黄) 和adjusted homophily (蓝) 曲线几乎都是线性递增的，连U型都不能体现。尽管aggregation homophily (紫) 和label informativeness (灰) 在低homophily区域有一个回弹(bound)趋势，但是他们并不能提供一个合适的阈值，而且无法提供准确的性能交叉点位置。

博客到这里就结束了，如果有问题，可以私信讨论或者通过 Email: sitao.luan@mail.mcgill.ca; Twitter: @SitaoLuan。欢迎关注我们的文章，谢谢。

[1] Is Homophily a Necessity for Graph Neural Networks?. In International Conference on Learning Representations, 2022.

[2] Revisiting heterophily for graph neural networks. Advances in neural information processing systems,35, 1362-1375.

往期精彩文章推荐

关注我们 记得星标

 关于AI TIME 

AI TIME源起于2019年，旨在发扬科学思辨精神，邀请各界人士对人工智能理论、算法和场景应用的本质问题进行探索，加强思想碰撞，链接全球AI学者、行业专家和爱好者，希望以辩论的形式，探讨人工智能和人类未来之间的矛盾，探索人工智能领域的未来。

迄今为止，AI TIME已经邀请了1400多位海内外讲者，举办了逾600场活动，超600万人次观看。

我知道你

在看

哦

~

点击 阅读原文 跳转至“0:57:20”查看回放！