北京通州做网站的公司,网站开发软件学习,网站色彩运用,wordpress能多人登录论文
https://arxiv.org/pdf/1810.00826
abstract
图神经网络(gnn)是一种有效的图表示学习框架。gnn采用邻域聚合方案#xff0c;通过递归聚合和变换相邻节点的表示向量来计算节点的表示向量。已经提出了许多GNN变体#xff0c;并在节点和图分类任务上取得了最先进的结果。…论文
https://arxiv.org/pdf/1810.00826
abstract
图神经网络(gnn)是一种有效的图表示学习框架。gnn采用邻域聚合方案通过递归聚合和变换相邻节点的表示向量来计算节点的表示向量。已经提出了许多GNN变体并在节点和图分类任务上取得了最先进的结果。然而尽管gnn彻底改变了图表示学习但人们对其表示特性和局限性的理解有限。-一个理论框架用来分析GNN捕获不同图结构的能力。
introduction
使用图结构数据进行学习例如分子、社会、生物和金融网络需要有效地表示它们的图结构。
GNN广泛遵循递归邻域聚合(或消息传递)方案其中每个节点聚合其邻居的特征向量以计算其新的特征向量。经过k次聚合迭代后节点由变换后的特征向量表示特征向量捕获节点k- hop邻域内的结构信息。然后可以通过池化获得整个图的表示例如通过将图中所有节点的表示向量相加。
首先将给定节点的邻居的特征向量集表示为一个multiset即一个可能含有重复元素的集合。那么gnn中的邻居聚合可以看作是multiset上的聚合函数。没明白因此为了具有强大的表示能力GNN必须能够将不同的多集聚合成不同的表示。multiset函数的判别性越强底层GNN的表示能力就越强。
文章的主要贡献
证明了GNN在图结构的识别上最多和WL测试一样强大。建立了邻居聚合neighbor aggregation和图读出函数graph readout functions的条件在此条件下所得的GNN与WL测试一样强大识别了流行的GNN变体如gcn 和GraphSAGE无法区分的图结构并且精确地描述了基于GNN的模型可以捕获的图结构类型。图同构网络(GIN)其判别/表征能力等于WL测试的能力。
preliminaries
notation介绍
表示图图的节点特征向量被表示为。有两个task
node classification。每一个节点都有一个与之相关的标签。这一个任务的目标是学习一个节点的向量表示可以把的标签预测为graph classification。给定一系列图图的标签为目标是学一个向量表示来帮助预测整张图的标签
graph neural networks
GNNs使用图结构和节点特征来学习一个节点或者整张图的向量表示。GNN遵循邻域聚合策略通过聚合其邻居的表示来迭代更新节点的表示。经过k次聚合迭代后节点的表示捕获其k-hop网络邻居中的结构信息。GNN的第k层可以表示为 这里是节点在第次迭代层的特征向量。我们将第0层初始化。表示的是一些列邻近的节点。在GNN中选择和十分重要。 这一段不翻译了前面已经在别的论文中看一遍了
Weisfeiler-Lehman test
图同构问题是指两个图在拓扑上是否相同。除了一些极端情况图同构的Weisfeiler- lehman (WL)检验是一种有效的、计算效率高的检验可以区分一大批图(Babai kuucera, 1979)。它的一维形式“naïve vertex refinemen”类似于GNN中的邻居聚合。
wl测试迭代地(1)聚合节点及其邻域的标签(2)将聚合的标签散列成唯一的新标签。如果在某一次迭代中两个图的节点的标签不同就认为这两张图是非同构的。
theoretical framework: overview GNN递归地更新每个节点的特征向量以捕获其周围其他节点的网络结构和特征即其根子树结构(图1)。为了简化标记我们可以在{a, b, c…}中为每个特征向量分配一个唯一的标签。然后一组相邻节点的特征向量形成一个multiset(图1):同一元素可以出现多次因为不同节点可以有相同的特征向量。
定义1 Multiset
multiset是集合的广义概念它允许其元素有多个实例即一个multiset是一个2-tuple二元这里S是由的离散元distinct elements指在集合中不重复的元素组成的基础集合underlying set在数学中指一个拓扑空间的基本元素组成的集合。而赋予了元素的多重性.
一个最强大的GNN只有在两个节点具有相同的子树结构并在相应节点上具有相同的特征时才能将两个节点映射到相同的位置。由于子树结构是通过节点邻域递归地定义的(图1)我们可以将分析简化为GNN是否将两个邻域(即两个多集)映射到相同的embedding或表示。最强大的GNN永远不会将两个不同的邻域(即多组特征向量)映射到相同的表示这意味着它的聚合方案必须是注入的injective。
building powerful graph neural networks
理想情况下最强大的GNN可以通过将不同的图结构映射到嵌入空间中的不同表示来区分不同的图结构。然而这种将任意两个不同的图映射到不同嵌入的能力意味着要解决具有挑战性的图同构问题。也就是说我们希望同构图映射到相同的表示而非同构图映射到不同的表示。
lemma 2
令和为两个非同构图若存在一个图神经网络将和映射到不同的embeddingWeisfeiler-Lehman图同构检验同样会认为和为两个非同构图。
因此任何基于聚合的gnn在区分不同图方面最多与WL测试一样强大。一个自然的后续问题是原则上是否存在与WL测试一样强大的gnn-可只要邻居聚合和图级读出函数是单射的那么得到的GNN和WL测试一样强大。
Therorem 3
令为一个图神经网络在足够的GNN层数下如果满足以下条件将任意Weisfeiler-Lehman检验判定为非同构的图和映射到不同的嵌入:
1A通过迭代地聚合和更新节点特性其中是作用于multiset的函数是单射的。 2的graph-level readout即在multiset的节点特征上做操作的是单射的。
稍微断一下什么是injective单射, One to one Function
lemma 4
假设输入特征空间是可数的。令为GNN的第层确定参数的函数。其中是被定义在有固定大小的multiset上的。的范围即节点隐藏特征的空间对于同样也是可数的。
除了区分不同的图之外GNN还有一个重要的好处值得讨论即捕获图结构的相似性。注意WL测试中的节点特征向量本质上是单热编码因此无法捕获子树之间的相似性。相比之下满足theorem 3标准的一个GNN通过学习将子树嵌入到低维空间来推广WL检验。这使得GNN不仅可以区分不同的结构还可以学习将相似的图结构映射到相似的嵌入并捕获图结构之间的依赖关系。
Graph Isomorphism NetworkGIN
为了对邻域聚集的单射multiset函数建模提出了“deep multisets”理论即用用通用的multiset 函数来参数话神经网络。
lemma 5
假设是可数的。存在一个函数使得对于每个固定大小的multi set是独特的。此外任何multiset函数对于一些函数可以分解为
deep multisets和集合之间的一个重要区别是某些流行的单射集函数如均值聚集器不是单射multiset函数。
corollary 6
假设是可数的存在一个函数因此对于无穷多选择的包含所有无理数对于每一对这里是multiset的固定大小都是独特的。此外任何函数对于一些函数使用对都可以分解成
可以使用多层感知机来学习和 graph-level readout of GIN
通过GIN学习的节点嵌入可以直接用于节点分类和链路预测等任务。对于图分类任务提出以下“readout”函数给定单个节点的嵌入生成整个图的embedding。
随着迭代次数的增加对应于子树结构的节点表示会变得更加精细和全局。足够的迭代次数是获得良好判别能力的关键。然而来自早期迭代的特性有时可能会更好地泛化。为了考虑所有的结构信息使用来自模型的所有深度/迭代的信息。我们通过类似于“Jumping Knowledge Network”的架构来实现这一点。 Less powerful but still interesting GNNs
与使用mlp的模型不同1层感知器(即使带有偏置项)不是多集函数的通用逼近器。因此即使具有1层感知器的gnn可以在某种程度上将不同的图嵌入到不同的位置这种嵌入可能无法充分捕获结构相似性并且对于简单分类器(例如线性分类器)来说很难拟合。 平均池化和最大池化不能区分结构。
这一节在描述之前的一些池化trick的使用结论。
下面是其他博客的摘录老实说到了图之后才发现相关的文章少了很多相比于CV和NLP
论文阅读_图神经网络GIN - 知乎
之前研究方法着重于表示节点引文着眼于表征图的结构。作者认为之前方法难以区分不同的图结构并提出了一种基于GNN的方法GIN它的区分效果与WL-Test效果相当。
一般情况下一个节点的表式通过聚合它k跳之内的邻近节点计算而全图的表示则通过对所有节点的池化计算。文中使用了WL-test方法即图同构测试它是一个区分网络结构的强效方法也是通过迭代聚合邻居的方法来更新节点它的强大在于使用了injective见后聚合更新方法。而这里要评测GNN是否能达到类似WL-test的效果。
文中还使用了多合集multiset的概念指可能包含重复元素的集合。 如图-1所示有一个图左图如果想表征其中的蓝色节点且只考虑两跳计算方法如中图所示子树; 通过迭代变成了右图所示每个节点只考虑其邻居计算邻居时再考虑邻居的邻居。
算法需要满足injectiveinjective可译为内射即可把不同的元素映射成不同输出在图结构中不同的邻居结构需要生成不同的节点表征而maxmean池化显然都不是injective的后详述。 平均池化和最大池化都不是内射的。
图-2展示了在多合集情况下sum的效果最好mean次之max最差。
图-3中不同颜色表示不同实体其中图2-a中两图结构不同但平均池化和最大池化不能加以区分而求和可以区分图-2b中平均池化可区分两图但最大池化取红与绿中最大值不能区分两图同理使用平均池化和最大池化也不能区分图-3c中的两个图。
How Powerful are Graph Neural Networks GIN 图同构网络 ICLR 2019 论文详解-CSDN博客
文中提出了一个理论框架去分析GNNs的表达能力。在学习表示和区分不同的图结构时描述了不同GNN变体的表达能力。Weisfeiler-Lehman 图同构测试(1968)(WL)是一种强大的检验方法可以区分大量的图。与GNNs类似WL测试通过聚集网络邻居的特征向量迭代地更新给定节点的特征向量。WL测试之所以如此强大是因为它的单射聚合更新将不同的节点邻居映射到不同的特征向量。作者的主要观点是如果GNN的聚合方案具有高度表达性并且能够对单射函数建模那么GNN可以具有与WL测试同样大的区分能力。
将节点邻居映射到不同的特征向量这与之前的很多GNN的目的都差不太多的样子前面的可能是计算、卷积、这里可能偏重函数形式
为了在数学上形式化上述观点文中提出的框架首先将给定节点的邻居的特征向量集表示为一个multiset即一个可能有重复元素的集合。然后可以将GNNs中的邻居聚合看作是multiset上的聚合函数。因此为了拥有强大的表示能力GNN必须能够将不同的multiset聚合到不同的表示中。文中严格地研究了multiset函数的几个变体并从理论上描述了它们的区分能力即不同的聚合函数如何区分不同的multiset。multiset函数的判别能力越强GNN的表示能力就越强。
我其实没太明白为什么要使用multiset是说邻居的聚合方式可能是重复的如果结构一样的话
GNNs的表达能力是捕获图结构的关键。文中通过在图分类数据集上的实验来验证理论对比了使用各种聚合函数的GNNs的性能。 实验结果表明在作者的理论中最强大的GNN即图同构网络GIN根据经验判断也具有很高的表示能力因为它几乎完全适合训练数据而较弱的GNN变体往往严重不适合训练数据。此外这种表达能力更强的GNN在测试集精度方面优于其他GNNs并且在许多图分类benchmarks上实现了最先进的性能。
READOUT表示一个置换不变性函数permutation invariant function也可以是一个图级pooling函数。 上图是WL test的例子请移步原博客看解释。
https://www.cnblogs.com/BlairGrowing/p/15961951.html _______________________________________
一点题外话啊读完回忆一下之前读的论文觉得还有需要关注的疑问后期会单独写一篇回答自己的疑问如果能找到答案的话就贴回答
