Press "Enter" to skip to content

Graph-MLP: 用MLP与优化优雅地超越GNN

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

最近在arxiv上看到一篇十分有趣的文章: Graph-MLP: Node Classification without Message Passing in Graph ,用MLP和constrastive loss组合,在节点分类任务上能比现有的GNN表现得还好。觉得很有趣,想分享一下并试图从个人角度给出一些理论上的解释为什幺MLP的效果能够比GNN好。这篇文章只是个人之见,靠谱的文章介绍请看作者本人的知乎文章

三上酱:图学习新范式Graph-MLP,纯MLP做图节点分类 ​ zhuanlan.zhihu.com

本文分成一下几个部分:

 

Part I: Graph-MLP简介

 

Part II: 不一定靠谱的理论推导

 

Part I: Graph-MLP简介

 

一般的GNN工作的原理是依赖于邻接节点之间显式的message passing[1],也就是在模型结构当中加入graph convolution。那幺在transductive的任务当中能不能只在loss当中用graph信息而结构上只用MLP呢?这样做有下面几个优势[0]:

无message passing模块,计算简单,方便部署
支持batch training
inference无需adjacency matrix

这篇graph-mlp提供了一个初步的尝试。网络的结构呢,就是正常的MLP

在loss function当中呢,我们想要让k-hop相邻的节点的representation更为相似,k-hop不临近的点的representation变得不相似。

其中 是normalized adjacency matrix。这个模型十分简单,效果也非常不错,能过比肩或者超越现有的GNN。

Part II: 不一定靠谱的理论推导

 

那幺为什幺不用GNN也能获得这幺好的效果呢?遗憾的是,作者在文章当中并没有给出理论分析。在这篇知乎当中,我试图给出一些个人的观点,不一定是正确的,如果有错误请务必指出来,以免误导大家。

 

想要了解MLP+constrastive loss为什幺这幺好,我们首先需要理解SGD在优化的过程当中做了什幺。作为一篇知乎并不需要很严谨,我们首先简化掉sample的过程,sim取向量内积。在这个时候constrastive loss可以写成

 

 

其中 是k-hop邻接矩阵, 是A的补图。上面的loss可以分成positive和negative两个部分,其中positive的部分

 

 

求导,我们有

 

 

做梯度下降,假设步长为 ,在第t个iteration当中,我们有

 

 

上面(1)式可以看成是加了residue link的graph attention networks。推导到这里,我们得以一窥constrastive loss的庐山真面目:在每次梯度下降当中其实是对于k-hop的邻接节点做了一次graph attention。如果用GD迭代到收敛的话其实是相当于deep equilibrium models [2]。在今年的ICML当中,也有一篇非常有意思的文章用了deep equilibrium models等一些技巧训练了1000层GNN并得到了非常不错的结果[3]。

 

positive的部分我们到这里就分析完了,那幺negative部分在做什幺呢?我们注意到在(1)的迭代当中并没有normalization的出现。从优化角度分析,如果梯度下降迭代很多次会出现所有 都相等的情况(trivial solution),在GCN分析当中这个一般叫做over-smoothing,而negative的loss可以用于解决这个问题。对于negative部分,梯度下降可以表示为

 

 

这个操作是为了让k-hop不相邻的节点的representation不接近,从而避免trival solution的产生,从GNN角度上来看是对A的补图做了类似于[4]当中的high-pass filter 。

 

通过一定程度的简化,我们得以管中窥豹:在transductive setting当中,MLP + contrastive loss等价于 graph attention networks + deep equilibrium models。

 

在这篇知乎的的分析与原文的实验当中,一个比较好玩的点在于 model architecture和loss具有一定的等价性 。其实emmm这似乎并不是一个特别新的观点, loss和model architecture的等价性在马毅老师最近的深度学习的第一性原理当中对于他的MCR loss也有详细理论推导与证明[5] 。

 

参考文献

 

[0] Graph-MLP: Node Classification without Message Passing in Graph

 

图学习新范式Graph-MLP,纯MLP做图节点分类

 

[1] How Powerful are Graph Neural Networks?

 

[2] Deep Equilibrium Models

 

[3] Training Graph Neural Networks with 1000 Layers

 

[4] Beyond Low-frequency Information in Graph Convolutional Networks

 

[5] 基于第一原理的深度(卷积)神经网络by马毅

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注