《Advances in Graph Neural Networks》第3章读书笔记(上)

admin 2022年11月26日19:50:31评论22 views字数 6604阅读22分0秒阅读模式
《Advances in Graph Neural Networks》第3章读书笔记(上)
本书是由GAMMA Lab实验室推出,全面介绍了图神经网络的基础和前沿问题,主要分为以下三个部分:
  • Part 1:GNNs的基本定义和发展(Chaps. 1 - 2);

    • 我们首先概述了不同图的基本概念,以及图神经网络的发展,包括几个典型的图神经网络。这一部分将帮助读者迅速了解这个领域的整体发展。特别是在第1章,将总结基本概念和定义,以及图神经网络的发展。第二章将介绍基本的图神经网络,包括GCN,GAT,GraphSAGE,HAN等。
  • Part 2:GNNs的前沿课题(Chaps. 3 - 7);

    • 我们接着对有代表性的图神经网络技术进行了深入而详细的介绍。该部分将帮助读者了解该领域的基本问题,并说明如何为这些问题设计高级图神经网络。特别是第三章讨论了同质图神经网络,包括多通道图神经网络等。第4章介绍了异质图神经网络,主要集中在异质图传播网络等。之后,我们在第五章中介绍了动态图神经网络,其中考虑了时态图、动态异质Hawkes process和时态异质图。然后,在第六章中,我们介绍了双曲图神经网络,包括双曲图注意网络和洛伦兹图卷积神经网络等。最后,第七章介绍了蒸馏图神经网络,包括图神经网络的知识蒸馏和对抗性知识蒸馏等。
  • Part 3:GNNs的未来发展方向(Chaps. 8)。

    • 我们做出结论并讨论了未来的研究方向。尽管有大量的图神经网络方法被提出,许多重要的开放性问题仍然没有得到很好的探索,例如图神经网络的鲁棒性和公平性。当图神经网络被应用于现实世界的应用,特别是一些风险敏感的领域时,这些问题仍需要被仔细考虑仔细考虑。
📖一言以蔽之,本书从图表示学习的基础知识开始,广泛地介绍了GNNs的前沿研究方向,包括heterogeneous GNNs, dynamic GNNs, hyperbolic GNNs, distilling GNNs等。一方面基本知识可以帮助读者迅速了解GNNs的优点,另一方面各种前沿GNNs则有望激发读者开发自己的模型。相信,无论是初学者还是来自学术界或工业界的研究人员,相信都会从本书的内容中受益。
经过Part 1对GNNs基本定义和发展以及经典模型的简单介绍和讲解,本文开始分享Part 2,主要介绍第三章同质图神经网络,首先对第三章的整体结构做一个介绍,然后讲解了本实验室在同质图方向上的两个经典的工作,AM-GCN(自适应多通道图卷积网络)和FAGCN(频率自适应图卷积网络)。
(其余章节会在GAMMA Lab公众号持续更新,希望能与读者一同在本书中获益🥰)

✏️chapter 3-Homogeneous Graph Neural Networks

所谓同质图,是指图中只有一种类型的节点和边,如引文网络,只有朋友关系的社交网络等,与异质图相比网络结构较为简单,是一种简化。因此,同质图神经网络通常只需要聚合单一类型的邻居来更新节点的表示即可,目前的图神经网络也主要针对同质图设计。

3.1 章节介绍

图神经网络 (GNNs) 在处理图结构数据的分析任务方面广受欢迎,精心设计的消息(或传播)机制是 GNNs 最基本的部分。在Part 1我们介绍了GNNs的经典模型,如GCN,GAT和GraphSAGE等。虽然这些模型取得了成功,但现有的消息传递功能仍然存在一些问题,这可能会导致某些应用程序的性能欠佳。
  • 在3.2节中,我们首先介绍了GCN在节点特征和拓扑结构的融合上存在着不足的研究结果。基于此,提出了一种新的 GNN,即自适应多通道图卷积网络(AM-GCN),用于在消息传递过程中自适应地聚合特征和结构信息。

  • 在3.3节介绍频率自适应图卷积网络(FAGCN),它可以自适应地聚合低频和高频信息。FAGCN设计了一种广义的注意力机制,可以帮助现有的消息传递方法摆脱低通过滤。

  • 在3.4节介绍了图估计神经网络(GEN),它可以为 GNN 学习更好的消息传递结构,即图拓扑。由于其强大的去噪和社区检测能力,GEN比GCN拥有更好的鲁棒性。

  • 在3.5节中,我们引入了现有 GNN 的统一框架,将不同的消息传递函数总结为一个封闭形式的对象。这一发现可以帮助研究人员理解消息传递机制背后的原理。

最后,在3.6节给出了本章的综合结论,在3.7节给出延展阅读。
本文主要介绍3.2节和3.3节的两个工作。

3.2 Adaptive Multi-channel Graph Convolutional Networks(AM-GCN)

3.2.1 综述

  • 首先发现问题。GCN取得巨大成功的一部分原因是GCN提供了一种关于拓扑结构和节点特征的融合策略来学习节点嵌入。然而,研究表明GCN在融合节点特征和拓扑结构方面存在着不足。

  • 然后进行调研。我们设计了两个实验评估GCN在融合拓扑结构和节点特征方面的能力。实验表明,GCN在网络拓扑结构和节点特征上的融合能力显然与最优相去甚远。即使在节点特征/拓扑与节点标签之间的相关性非常明确的一些简单情况下,GCN 仍然无法充分融合节点特征和拓扑结构以提取最相关的信息。

  • 最后提出解决方法。我们提出了一种用于半监督分类的自适应多通道图卷积网络 (AM-GCN)。中心思想是我们同时基于节点特征、拓扑结构及其组合来学习节点嵌入。在一系列基准数据集上的实验结果清楚地表明,AM-GCN 优于最先进的 GCN,并且可以很好地从节点特征和拓扑结构中提取最相关的信息,以应对具有挑战性的分类任务。

3.2.2 调研

我们设计了两个简单而直观的实验来检验GCNs是否可以自适应地从图中的节点特征和拓扑结构中学习,并将它们充分融合以完成分类任务。主要思想是我们将建立节点标签与网络拓扑和节点特征之间的高度相关性,然后我们将在这两个简单的情况下检查GCN的性能。
  • 实验 1:随机拓扑但节点特征与标签相关。我们生成一个节点标签与节点特征高度相关,但与拓扑结构无关的网络。即任意两个节点之间建立边的概率一定,而具有相同标签的节点,我们用同一种高斯分布来生成节点特征。我们分别用 GCN 和 MLP 来训练这个网络,其分类准确率分别为 75.2% 和 100%。由于节点特征与节点标签高度相关,因此 MLP 表现出优异的性能。 GCN同时从节点特征和拓扑结构中提取信息,但不能自适应地融合它们以避免拓扑结构的干扰,所以它无法与 MLP 的高性能相提并论。
  • 实验 2:拓扑与标签相关但节点特征随机。我们生成一个节点标签与拓扑结构高度相关,但与节点特征无关的网络。即节点特征随机生成,但对于拓扑结构,我们使用随机块模型 (SBM) 将节点分成 3 个社区,同一社区内的点之间产生边的概率大于不同社区间的,并且同一社区的标签相同。我们分别将 GCN 和 DeepWalk 用于该网络,其分类准确率分别为 87% 和 100%。GCN同时从节点特征和拓扑结构中提取信息,但不能自适应地融合它们以避免节点特征的干扰,所以它无法与 DeepWalk 的高性能相提并论。
  • 《Advances in Graph Neural Networks》第3章读书笔记(上)

《Advances in Graph Neural Networks》第3章读书笔记(上)
从两个实验的结果可以看出,目前GCN的融合机制远未达到最优。即使节点标签与网络拓扑或节点特征之间的相关性非常高,当前的 GCN 也无法充分利用节点标签的监督来自适应地提取最相关的信息。然而,现实中的情况更为复杂,因为很难知道是拓扑还是节点特征与最终任务的相关性更高,一种新的融合机制被需要。

3.2.3 AM-GCN方法

我们关注图 的半监督节点分类任务,其中 是具有 n 个节点的对称邻接矩阵, 是节点特征矩阵,d 是节点特征的维度。
3.2.3.1 AM-GCN的整体框架
AM-GCN的关键思想是允许节点特征不仅在拓扑空间中传播,而且在特征空间中传播,并且应该从这两个空间中提取与节点标签最相关的信息。为此,我们基于节点特征构建特征图。然后使用两个特定的卷积模块,使能够在特征图和拓扑图上传播,分别学习两个特定的嵌入。此外,考虑到这两个空间中的信息具有共同的特征,我们设计了一个具有共享参数的公共卷积模块来学习公共嵌入。同时我们采用一致性约束来增强的共性,采用差异性约束来保证以及之间的独立性。考虑到节点标签可能与拓扑或特征或两者相关,AM-GCN 利用注意力机制实现自适应融合,从而为最终分类任务提取最相关的信息。
《Advances in Graph Neural Networks》第3章读书笔记(上)
3.2.3.2 特殊卷积模块
首先,我们基于节点的特征矩阵构造一个k-最邻近(kNN)图,也即特征图,,其中是特征图的邻接矩阵。我们首先通过余弦相似度计算 n 个节点之间的相似度矩阵

然后我们为每个节点选择前k个相似节点对来设边,最后得到邻接矩阵
类比GCN中节点特征在拓扑空间的传播,我们将特征图输入特殊卷积模块,从而学习在特征空间中捕获特定信息 的节点嵌入:

其中,  并且 的对角度矩阵。 至于拓扑空间中的传播,将原始图 作为 输入即可学习节点特征在拓扑空间捕获特定信息 的节点嵌入。
3.2.3.3 共享卷积模块
我们不仅需要提取这两个空间中特定信息的节点嵌入,还要提取这两个空间共享的公共信息的节点嵌入。为了解决这个问题,我们设计了一个共享权重矩阵的GCN卷积层,以获取两个空间中共享嵌入。
当将拓扑图输入时:

当将特征图输入时:

可以发现两者是共享权重矩阵的,而共享矩阵可以将两个空间中的公共信息给筛选出来。不同的图输入我们可以得到不同的节点嵌入,我们取公共信息的节点嵌入为:

3.2.3.4 注意力机制模块
现在我们有了两个特殊节点嵌入,以及一个公共节点嵌入。然后我们使用注意力机制学习它们三个在节点分类任务中的重要性,分配不同的权重,实现三者的自适应融合:

其中,就是重要性系数,为了便于矩阵相乘表示将其转化对角矩阵,那么将三者融合得到最终的节点嵌入为:

那么,我们怎样计算呢? 以为例,对一个节点来说:

其中,是共享注意力向量,是权重矩阵,是偏置向量。然后再做softmax操作:

最终将各个节点集成在一起即可得也是相似的操作。
3.2.3.5 约束
对于之间的一致性约束,我们首先对其做归一化,得到,通过将其与自己的转置相乘可以得到相似性矩阵:

而一致性约束则为:

而对于以及之间的独立性约束,我们采用HSIC独立性准则来实现:

其中,的Gram矩阵,而为单位矩阵,为元素全为1的列向量。类似的可得:

最终差异性约束为:

3.2.3.6 损失函数
通过最终得到的我们可以进一步得到

由此我们可以得到交叉熵损失函数:

再加上约束可以得到最终的损失函数:

其中,是超参数。由此我们就可以据此进行训练模型。
更多的细节可以参考原文。原文链接 AM-GCN: https://arxiv.org/abs/2007.02265

3.2.4 实验

可以看到AM-GCN在多个数据集上都取得了最好的效果。
《Advances in Graph Neural Networks》第3章读书笔记(上)

3.3 Beyond Low-Frequency Information in Graph Convolutional

3.3.1 综述

  • 首先发现问题。一般来说,GNNs通过聚合来自邻居的信息来更新节点表示,这可以看作是低通滤波器的一种特殊形式。研究表明,信号的平滑度,即低频信息,是 GNN 成功的关键。然而,我们只需要低频信息吗?其他信息在 GNN 中扮演什么角色?

  • 然后进行调研。我们以低频和高频信号为例,并通过实验来评估它们的作用。结果清楚地表明,它们都有助于学习节点表示。具体来说,我们发现当网络表现出不协调性时,高频信号的性能要好于低频信号。这意味着当前 GNN 很大程度上消除的高频信息并不总是无用的,而低频信息对于复杂网络并不总是最优的。

  • 最后提出解决方法。我们设计了一个频率自适应图卷积网络FAGCN,以自适应地聚合来自邻居或自身的不同信号。我们首先采用图信号处理理论来正式定义增强型低通和高通滤波器,以将低频和高频信号与原始特征分离。然后我们设计了一种自门控机制来自适应地集成低频信号、高频信号和原始特征。在六个真实世界网络上进行的大量实验验证了 FAGCN 比现有技术具有优势。

3.3.2 调研

以低频和高频信号为例,分析它们在学习节点表示中的作用。具体来说,我们测试了它们在一系列合成网络上的节点分类性能。主要思想是逐渐增加合成网络的异配性(所谓异配性就是不同类间的连接概率大于同类内的连接概率),并观察这两个信号的性能如何变化。
我们生成一个有200个节点的网络,并将它们随机分为2类。对于不同的类使用不同的高斯分布生成特征。此外,同一类中的连接是从概率 p = 0.05 的伯努利分布生成的,两个类之间的连接概率 q 从 0.01 到 0.1 不等。当 q 小时,网络表现出同配性;随着 q 的增加,网络逐渐呈现出异配性。然后,我们将第 3.3.3.1 节中描述的低通和高通滤波器应用于节点分类任务。
《Advances in Graph Neural Networks》第3章读书笔记(上)
如图 3.2a 所示,随着 q 的增加,低频信号的精度降低,而高频信号的精度逐渐提高。这证明了低频和高频信号都有助于学习节点表示。现有的 GNN 在 q 增加时失败的原因是,如图 3.2b 所示,它们只聚合来自邻居的低频信号,即让节点表示变得相似,而不管节点是否属于同一类,从而失去差异性。当网络变得不协调时,高频信号的有效性就出现了,但如图3.2a所示,单个滤波器无法在所有情况下都达到最佳效果。我们提出的 FAGCN 结合了低通和高通滤波器的优点,可以将同一类内的低频信号和不同类的高频信号聚合起来,如图 3.2c 所示,从而显示了每个合成网络上的最佳性能。

3.3.3 FAGCN的方法

考虑无向图,其邻接矩阵为节点个数。而归一化拉普拉斯矩阵定义为,其中是对角度矩阵,是单位矩阵。是实对称矩阵,所以它有一套完整的正交特征向量,其中每一个都有对应的特征值。 通过特征值和特征向量,我们有,其中
补充知识:图傅里叶变换。根据谱图理论,我们可以将归一化拉普拉斯矩阵的特征向量作为图傅里叶变换的基。即给定一个信号,图傅里叶变换定义为,同时逆图傅里叶变换是。因此,信号和卷积核之间的图卷积,其中运算为对应元素相乘,是对角矩阵,一般把它当作卷积核以代替。其实一般很少显式的写出,都是用来表示,一般的工作都是在上做改动,而就是图滤波器的特征值组成的对角矩阵。GCN的就是
3.3.3.1 分离高频和低频信息
我们设计了一个低通滤波器和一个高通滤波器来分离节点特征中低频和高频信息:

其中,是[0,1]范围内的超参数。然后进行图卷积可以得到:

我们注意到低通滤波器的,也即。当时,,为了避免负值,我们取,也即,这样的话当,那么,而当时,,这样不仅避免了负值还起到了增强低频信息抑制高频信息的效果。
这样我们可以分离出高频信息和低频信息,但是由于事先我们并不知道网络是同配性的还是异配性的,所以我们无法确定是高频信息更重要还是低频信息更重要,所以我们还需要自适应的聚合高频与低频信息,以更好地应用于不同的网络。
3.3.3.2 聚合
我们的模型的输入是节点特征,,其中是节点特征的维度。实现频率自适应的基本思想就是利用注意力机制学习低频和高频各自应占的比例:

其中表示节点的聚合结果,分别表示节点的邻居节点集合和度,分别表示节点给节点的低频信息和高频信息的比例,并且我们设定。 我们令,然后我们设计了一个共享自门机制来学习

其中表示连接操作, 可以看作是一个共享卷积内核,而tanh(·)是双曲正切函数,它可以自然地限制的值在[−1, 1] 中。此外,为了利用结构信息,我们只计算 节点和其一阶邻居之间的系数。所以最终聚合表达式为:

请注意,当聚合来自邻居的信息时,度数用于对系数进行归一化,从而防止聚合表示过大。
更多的细节可以参考原文。原文链接 FAGCN: https://arxiv.org/abs/2101.00797

3.3.4 实验

我们选择常用的引文网络,如Cora、Citeseer 和 Pubmed来作为同配性网络,选择Wikipedia网络和Actor co-occurrence网络来作为异配性网络。
《Advances in Graph Neural Networks》第3章读书笔记(上)
GraphHeat通过热核设计了一个低通滤波器,它比GCN可以更好地捕获低频信息。因此,它在基线中表现最好。但是我们可以看到,由于增强的低通滤波器,FAGCN在大多数网络上都超过了基准,这验证了低频信息的重要性。
《Advances in Graph Neural Networks》第3章读书笔记(上)
从图3.3可以看出,GCN和GAT的性能比其他方法差,这表明仅使用低通滤波器不适用于异配性网络。APPNP和ChebNet的表现优于GCN和GAT,这表明原始特征和多项式可以在一定程度上保留高频信息。最后,FAGCN在大多数数据集和标签率上表现最好,这反映了我们方法的优越性。
本期责任编辑:杨成
本期编辑:刘佳玮

北邮 GAMMA Lab 公众号
主编:石川
责任编辑:王啸、杨成
编辑:刘佳玮

长按下图并点击“识别图中二维码

即可关注北邮 GAMMA Lab 公众号

《Advances in Graph Neural Networks》第3章读书笔记(上)

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年11月26日19:50:31
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   《Advances in Graph Neural Networks》第3章读书笔记(上)https://cn-sec.com/archives/1426783.html

发表评论

匿名网友 填写信息