Press "Enter" to skip to content

自适应通用广义 PageRank 图神经网络

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

 

分享嘉宾:简翌/彭建浩 UIUC

 

编辑整理:何坤登 氪信科技

 

出品平台:DataFunTalk

 

导读: 大家好,我叫彭建浩,我是UIUC电子科技与计算机工程专业的在读博士生,今天我会和我的同事简翌分享一篇我们最近被ICLR收录的论文,名字叫Adaptive Universal Generalized PageRank Graph Neural Network,简称GPRGNN。

 

相信大家都知道,图神经网络或GNN已经在很多图结构的数据集上展现出了较传统方法更优越的性能,包括在各种节点分类,图分类,还有关联预测等等任务上,其实除去一些常见的标准测试数据集还有各种各样的合成数据,图神经网络还可以运用到很多新兴生物医学领域上,目前他们大多数还是使用传统的方法,例如:根据不同的疾病来分类相同的基因,或者把不同的药物跟基因或者疾病作关联,把已有的药物用在潜在的疾病上。

 

 

1. 在基因和疾病的关联上

 

我们做的事情可以有一个已知基因网络的部分基因,然后我们尝试对剩余的基因进行节点分类,我们就知道什幺样的基因和这个疾病是有关的,还有就是已知基因网络跟疾病网络,还有部分疾病到疾病的联系,我们就尝试去做剩余的基因跟疾病之间的关联预测,也就是link prediction, node classification的任务。

 

 

2. 类似的,在药物与疾病相关联上

 

我们可以通过做药物基因的关联网络还有疾病基因的关联网络,然后通过基因把他们串联起来,去预测不同药物与疾病之间的关系,或者对药物进行不同疾病的分类,也就是线性预测, 节点分类的任务。

 

 

上述话题其实都是在生物领域非常热门的话题。回到今天展示的主要内容,

 

我们将我们的论文概括成以下五点: ①  已有的图神经网络;② 现有图神经网络普遍存在的两个主要问题:一般性和过平滑;③ GPR-GNN模型;④ GPR-GNN模型的实验结果;⑤ 总结以及GPR-GNN模型未来的研究方向。

 

01

 

已有的图神经网络

 

1. 常用符号

 

首先,我们先介绍一些比较通用的符号:

 

和其他的方法类似,我们首先定义GNN 的邻接矩阵A,节点特征矩阵 X,类别特征矩阵Y,还有必要的normalized degree和邻接矩阵tilde D 和tilde A 以及delta函数。

 

 

2. 现有模型:stacking GNN layers

 

大部分常用的GNN结构其实都是通过不断的叠加类似于下图的GNN layer或者传播 layer来得到。

 

 

从图里面我们能看到的是GCN用到的单层结构, 概括的讲,从k-1层的特征矩阵 H0到k层的特征矩阵Hk,GCN或者普遍的GNN的单层结构会先用normalized 邻接矩阵作为自特征层的传播乘上该层对应的变换矩阵作一个线性的变化,最后再通过一个非线性累加得到下一层的结果;不断的迭代,直到在最后层用softmax对所有的节点做最终的表达, 然后对该表达做一个节点的分类或者其他的任务。

 

02

 

现有GNN模型的缺陷

 

在GCN的影响下,大家又提出的其他的不同的GNN结构,比较常见的例如GAT,Graph SAGE以及其他更多的一些结构,其通用逻辑可以概括为先提出一个类似上述的传播层, 然后不断的叠加一些层,最后再用一个类似与softmax的单层作为神经网络的最终输出。

 

 

这样的做法在很多的测试数据集上都表现出优越的成绩,尤其是像较于仅使用图拓扑结构或者是使用节点的表达 node 特征矩阵。但是GNN也衍生出了一些GNN的主要问题,我们这里主要关注大部分GNN都有的两个问题:

 

其中一个就是普遍性或者一般性;

 

以及大部分GNN都存在的过平滑。

 

这里的普遍性是指一个普通的GNN应该能在不同种类的图结构数据上学习,进行准确的预测,不应该偏向于某一类型的图,而过平滑是一个图深层网络都会出现的一个普遍问题。那幺接下来我会详细的讲一下一般性和过平滑的问题。

 

 

1. 一般性

 

首先,大部分的GNN都是基于一个 叫做homophilic(同源)的假设,即同向偏好假设(或者同源偏好假设),在这个假设中,属于同一类的点或者相似的点,他们之间更偏向于建立相互的连接,它的反例就是heterophily(weak homophily)就是异向偏好(或者异源偏好),即非同源偏好,即不同类别的点或者不相似的点更倾向与建立连接,例如在部分Dating graph或者protein graph上,不同的性别或者不同的氨基酸,比起同类的,他们更有可能在不同的类别之间建立连接,此时,基于homophily假设设计的GNN,或者假设图已经是homophily的GNN,那幺他们的表现就不太好,甚至还不如其他的或者一般的方法。因此我们设计GNN的时候,一个关键的点就是要使得我们的GNN能够同时应对这两种情况的图结构,也就是所谓的一般性。

 

 

2. 过平滑

 

另一个GNN的主要问题就是过平滑,过平滑的意思就是大部分现有的GNN都不能算作是一个深层模型(deep model), 上文中提到的图里面,理论上没有限制K有多大,可以一直叠加,但是实际上,大部分的模型,如GCN,还有Graph SAGE,他们普遍都只有2-4层,非常浅。而且,这些浅层的模型在测试数据集上往往比深层的模型表现要好。导致了GNN不能叠加过多层的理论上的原因,即过平滑(过平滑)。

 

 

如何理解过平滑的问题?

 

假设在无穷层的GCN中,如果把所有非线性变化叠加全部去掉,就只有了一个连续的传播以及连续线性变换。由表达式可知,如果模型迭代了无限多层,且没有非线性叠加的话,最后的特征向量或者特征矩阵会变成和原先的输入矩阵X无关的一个矩阵。因此,无论输入数据是什幺,最后都会得到一个与输入无关的表达,即完全丧失了来自于节点特征的信息,所以,图不能在该数据中学得很好。

 

 

以上即GNN的两个主要问题。接下来就交给简翌介绍我们的解决方法以及GPR-GNN如何解决GNN的上述问题,和一些其他的beneficials。

 

03

 

我们的解决方案:GPR-GNN

 

下图是GPR-GNN的主要结构,它分为两个部分,第一部分是一个单层的MLP神经网络。它主要的作用是做隐态特征提取。当输入矩阵X (node matrix) 进入到神经网络层之后,会得到一个变换之后的特征矩阵 H0,之后根据图拓扑去传播 K步分别得到H1至Hk不同步数传播后的结果。然后把得到的不同步数的结果做一个线性组合,其对应的权重叫做GPR Weights,最后线性组合完成的结果就是最终的输出结果。表达式中标注的红色参数就是需要学习的参数,而模型是采用端对端(end-to-end)的方式进行训练。逻辑为:在解释其功能中,前面的逻辑好像是专门针对node feature,而GPR Weights专门解决图传播的问题,如果实际上是end-to-end的训练,他们相互之间可以借由梯度信息同时得到节点特征和图传播 ,并同时受到节点特征和图传播的限制。

 

 

GPR-GNN能够同时解决一般性和过平滑 的问题,此外,GPR-GNN还能够避免过拟合的问题。在以前的SGC中,如果每多加一层,就需要多引进一个需要训练的参数矩阵,当隐藏单元很大的时候,每多加一层,参数量就会很大,相对来说,GPR-GNN每多传播一步,只会多引入一个单个的参数,因此可以传播很深但是参数量不会明显增加。同时,GPR-GNN还具有可解释性,之后的实验会观察学到的GPR weights是否合理,然后借由实验表明GPR-GNN 模型确实有可解释性。

 

1. 节点分类

 

在本次的分享中主要关注的是节点分类的问题,我们会拿到一整张图以及node 特征矩阵,然后会得到一些点,我们的任务就是还原所有标签的节点。

 

 

① Generalized PageRank

 

对于节点分类这个问题,其实与非监督图聚类相关,特别是与seed-set expansion相关,在我们19年发布的论文中,提出了Generalized PageRank的想法,去研究在seed-set expansion 这个任务中,GPR的表现如何。研究显示,GPR明显优于比较受欢迎的传统方法,如Personalized PageRank(PPR),seed-set expansion 这个任务是指给定一个点,在图中找到包含该点的集群,更类似于非监督问题。我们可以根据信息学做一个one dimension 特征矩阵即如果该节点是seed node,那幺其结果为1,否则为0。GPR主要的概念就是把one dimension 特征矩阵做一个K部的传播,之后再做一个线性组合对每一个点得到一个GPR分数,然后根据GPR的分数进行聚类,将分数最高的几个点作为包含seed node的集群。

 

 

② 图卷积与随机漫步之间的关系

 

从下图中,可以看见GCN 层与GPR的传播具有一定的相似性,但也存在不同得地方。它们相似的点为都是在图中做传播。不同的点是GCN会增加一些特征变换,且只用了最后一步;而GPR的重点则是从第0步到第k步做一个线性组合,第0步到第k步的信息都有用到。

 

 

3. GPR-GNN具有一般性的原因

 

那幺接下来我来解释为什幺GPR-GNN是具有一般性的。

 

一个很重要的评论是GPR在数学上是与多项式的图滤波器是等价的,以下是多项式图滤波器的表达式:

 

 

可以看到对一个邻接矩阵而言,它是一个K次的多项式,GPR weights则变为多项式的系数。而学习最优GPR weights也等同于学习最优多项式滤波器。从传统的信号处理或者图信号处理的角度而言:多项式滤波器可以逼近任意种类的滤波器,如低通滤波器,或高通滤波器,甚至是更复杂的带通滤波器。

 

在此论文中,主要得到一下的理论:

 

第一个部分的结论是说,假设GPR weighs的结果全部为非负,且并非只有第0步为非负,即除了corner case 以外,不是只有第0步有值,然后其他步都为非负,那幺GPR weights 可以对应看作一个低通图滤波器,另一方面,如果 GPR weights的形式为 (- α ) k ,其正负号会随其步数的weights而依次有 (- 1 ) k 的交替,则GPR会对应看作一个高通图滤波器。

 

 

理论上,如果GPR-GNN或者多项式滤波器需要满足一般性,那幺部分GPR weights 需为负值,如果全部为正,则就会对应为低通滤波器。

 

4. GPR-GNN能够避免过平滑的原因

 

另外,我们也理论的角度分析为什幺GPR-GNN能够避免过平滑。因为理论分析相对复杂,所以本此分享中仅提到关键理论,思路为,如果第K步的结果对训练损失没有帮助,那幺在用它的梯度更新相对应的GPR weights 的时,就会把第K步的结果的大小拉下来,当其结果下降到一定程度时,没有帮助的步数就最终就不会影响结果,从而避免过平滑的问题。详细的理论证明则请有兴趣的同学从论文中查找。

 

 

5. 与相关论文的对比

 

那幺接下来,我们提一些比较相关的论文,其可以分为两类:

 

① GCN-like 模型:

 

(1) JK-NET:与GPR-GNN相同的是,它也在最后一层中将不同步数的结果累加起来。

 

(2) GCN-Cheby:每一层的GNN都传播超过1步。

 

上述两个模型在实践中,深度都会比较受限,且其学习到的参数步具有可解释性。很难说明他们学习到的weights具体代表什幺内容。

 

② 基于图拓扑加强的MLP

 

(1) APPNP:如果我们将GPR-GNN的weights固定不动为PPR weights的形式,则将GPR-GNN还原为APPNP,因为它的所有GPR weights都是正值,所以它不可避免地成为了一个低通滤波器;导致它只能在同源图中生效,而无法在异源图中生效。

 

(2) SGC:与APPNP类似,它只有最后一步的GPR weights 有值,而把所有的非线性值都删除,所以它仍然是一个低通滤波器,仍然只能在同源图中生效,而无法在异源图中生效。

 

(3) C&S:在2021年ICLR论文:Huang et al. Combining Label Propagation and Simple Models out-performs Graph Neural Networks中提出catch and smooth的方法, 其主要观点则是结合标签 传播与MLP,该论文也存在部分工作仍然基于同源图的假设,故亦不能应用于异源图中。

 

 

04

 

实验

 

1. 实验:Synthetic data

 

为了测试各个GNN 在不同程度的同源图和异源图中的表现,我们提出了使用contextual Stochastic Block模型(cSBM)生成随机图测试GNN的性能。

 

其node feature 是一些高斯随机向量,μ则是高斯随机向量的距离,所以μ越大,那幺node feature的信息强度则越强。而其图的部分则是SBM,由λ参数控制相同标签的边或者不同标签的边机率的差,因此λ的大小则表示了该拓扑图信息强度的大小,λ的绝对值越大,则图的信息强度越强,λ为正则表示该图为同源图,λ为负则表示该图的异源图。新定义参数 ϕ 表示λ与μ的比值,如果 ϕ在1到-1之间,则该图对应为强同源图或者强异源图,如果ϕ等于1或者-1,则node feature 独立与node 标签不相关,如果ϕ等于0,则拓扑图独立与 node 标签不相关。

 

 

以下是我们对各个Baseline以及GPR-GNN在cSBM上的实验结果,当ϕ从0到1变大的时候,所有的GNN表现都会越来越好,也说明了GNN目前受到欢迎的原因,因为在同源图中,GNN比一般不考虑图拓扑信息的模型表现好,而MLP的表现则会随着ϕ的增加而变差,因为当ϕ等于1的时候,node feature 是完全没有信息的。根据我们刚刚的模型,如果一个GNN具有一般性,则其在同源图或者异源图中的学习效果是相同的,因此,如果当ϕ在0到-1中时,ϕ越接近-1,传统的GNN,如GCN,GAT,其表现则不如他们在同源图中学习的效果,会具有明显的落差。与之相对的,GPR-GNN的表现曲线则相对较为对称,表示GPR-GNN确实具有一般性。同时,在图拓扑信息不强的时候,即ϕ接近0的时候,传统GNN的表现明显弱于完全忽略图拓扑信息的模型,如MLP。所以,在不确定图是同源图还是异源图,甚至是与标签不相关的情况下,如果盲目使用GNN,则有可能得到更糟糕的结果,而GPR-GNN在图拓扑信息完全与节点标签不相关的情况下,其表现仍然与MLP相差不远。

 

 

2. 实验:真实世界数据集

 

在实际情况的数据集中也做了实验,简而言之,无论是在同源图,还是异源图中,GPR-GNN的表现仍然较好。

 

 

3. 实验:已学习GPR weights的可解释性

 

同样地,我们也做了实验证明GPR weghts是否具有可解释性。首先,a,b,e,f四个图表示的是同源图的效果,可以看到每一步已学习GPR weights都是正值,就理论而言,其表现为低通滤波器;而在c,d,g,h四个异源图中,已学习GPR weights是正负交替出现的,其在理论上仍然符合高通滤波器的特点,即GPR weights的部分值需要为负值。

 

 

4. 实验:避免过平滑

 

最后,我们仍做实验测试了GPR-GNN是否能够避免过平滑。刚开始,将GPR weights初始化到最后一步,则发现在训练之前,GPR-GNN很大程度上会出现过平滑,而随着开始训练GPR weights整个模型时,前面几步的GPR weights已经开始逐渐变大,最后一步其大小会下降,而从准确率的角度评估,完全没有训练之间的准确率在百分之五十左右,而训练完成的准确率则可高达仅百分之九十九。而该实验中训练步数达到了10步,已经是一个相对叫较深的模型,同时也证明了GPR-GNN确实能够避免过平滑问题。

 

 

05

 

总结与未来发展

 

 

总结:GPR-GNN具有一般性,且能够避免过平滑问题;此外,因为GPR-GNN使用的参数较少,所有也能够避免过拟合问题;而所学习到的GPR weights 是具有可解释性的。更多地,发现能够在cSBM中严谨地测试GNN的一般性。在未来研究中,也思考过很多有趣的发展方向,如是否能够将MLP替换为其他更加复杂的神经网络; 或者使用attention机制学习GPR weights,因为目前GPR-GNN形式还较为简单,需要验证是否能够将其变得更复杂从而学习到GPR weights;最后 GPR-GNN是否能够延伸到图表示学习中,即如果在GPR-GNN中加入图池化层,GPR-GNN是否仍然能够运行。

 

06

 

问答环节

 

 

 

Q:如何辨别同源图和异源图?

 

A:在ICLR关于GCN的论文中,有提到过一个关于衡量同源图和异源图的标准指标,但是其仍然存在一些缺点,同时,在我们的论文附录中,也有具体讨论过关于衡量同源图与异源图的相关指标。

 

Q:在生物医药中的一些实际应用

 

A:目前的论文是专注在节点分类的方向上提供一种可行性,暂时没有实际应用到生物医药分析上。

 

Q:图上高频和低频的实际物理含义

 

A:图上的高低频主要是根据其特征值(Eigenvalue)确定的,如果把adjacency matrix做特征值处理的话,其特征值在1到-1之间变化,特征值越大,则对应的是低频,反之对应的则是高频;因为特征值会从所有值为正值逐渐变为负值,而随着特征值越靠近高频,该节点的邻居节点也会逐渐靠近负值。

 

Q:如何衡量节点最终的表示是否与原始信息是否相关?

 

A:GPR-GNN是不需要特别在意最终的表现与初始信息是否有强相关或者弱相关,因为在cSBM上,不管特征是否具有信息量,都具有非常好的表示结果。论文中,在弱化初始特征是否重要。

 

Q:如果节点特征没有区分度,模型是否仍然有作用?

 

A:节点特征是与结果无关的,其证明在输入特征完全没有用的情况下,GPR-GNN模型仍然能够提取图的拓扑信息。

 

Q:假设没有非线性层,该模型是否仍然能够调用一个深度的基因模型,仅仅是传播次数加深,如果有非线性,是否仍然能够做相关分析?

 

2020年有一篇ICLR做过相关方面的分析,可以用gamma训练大小来衡量

 

Q:是否能够分辨同构图?

 

A:未来有兴趣探讨的方向之一,目前只是专注于节点分类,还没有考虑过加上一个图层,且图表示学习中的效果,都还没有做相关研究。

 

Q:如何分别异构图?

 

A:本论文中没有涉及到分辨节点属性不同的情况进行分析,我们比较在意的是在两个节点如何在不同类,但他们比较容易产生连接的情况下,GNN模型是否能够生效。从点分类的角度,最后的GPR是可以和多项式图滤波器做连接,输出的图信号一定是集中在某一个频带上,如果能够得到一个最好滤波器,那幺一定能够过滤一定的噪音。

 

Be First to Comment

发表评论

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