【GNN】第八章基于GIN的图表征学习

2024-03-12 02:52| 来源: 网络整理| 查看: 265

本文参考自datawhale2021.6学习：图神经网络

【GNN】第一章图论基础

【GNN】第二章 PyG中的图与图数据集

【GNN】第三章消息传递范式与PyG的MessagePassing基类

【GNN】第四章节点表征学习与节点分类任务（理论+调包实操）

【GNN】第五章构造数据完全存于内存的数据集类InMemoryDataset

【GNN】第六章边预测任务

本章目录前言1 WL-test1.1 同构图 Graph Isomorphism1.2 多重集 Multiset1.3 1-dimensional WL-test 及图相似度量1.4 WL子树1.5 WL-test的公式表示 2 GIN2.1 单射的聚合方案2.2 WL-test是GNN的上界2.3 GIN：一个与 WL-test 性能相当的 GNN2.3.1 GIN的聚合：SUM+MLP2.3.2 GIN的读出：SUM+CONCAT2.3.3 GIN优异的原因 3 作业4 代码实现4.1 基于GIN的图表征模块 GINGraphRepr Module4.2 GINConv图同构卷积层4.2.1 接口函数4.2.2 重写一个支持边属性的GINConv模块

前言图表征学习要求根据节点属性、边和边的属性（如果有的话）生成一个向量作为图的表征，基于图表征我们可以做图的预测基于图同构网络（Graph Isomorphism Network, GIN）的图表征网络是当前最经典的图表征学习网络

在论文《How Powerful are Graph Neural Networks?》中：

首先证明了 WL-test 是目前所有 GNN 的性能上界，并通过分析目前 GNN 出现的问题提出了构建有效的 GNN 的方法：使用单射函数同时也利用 MLP 拟合单射函数设计出一个新的架构模型 GIN，并通过实验证明 GIN 的性能逼近 WL-test 1 WL-test

目前解决图同构问题最有效的算法

1.1 同构图 Graph Isomorphism 两图的边和顶点数量相同，且边的连接性相同也可以认为一图的点是由另一图的点映射得到计算图同构可以度量图的相似度（比如实际应用中具有相似结构的分子可能具备相似的功能特性）在这里插入图片描述

1.2 多重集 Multiset

一组可能重复的元素集合。例如：{1,1,2,3}就是一个多重集合

1.3 1-dimensional WL-test 及图相似度量通过计算图特征向量来衡量图相似度。WL 算法可以是 K-维的，K-维 WL 算法在计算图同构问题时会考虑顶点的 k 元组。如果只考虑顶点的自身特征（如标签、颜色等），那么就是 1-维 WL 算法举例说明：一次迭代给定两个图 G G G和 G ′ G^{\prime} G′，每个节点拥有标签（实际中，一些图没有节点标签，我们可以以节点的度作为标签）在这里插入图片描述

2.3. 考虑节点邻域的标签，并对此排序。逗号前是当前标签排序的原因在于要保证单射性，即保证输出的结果不因邻接节点的顺序改变而改变在这里插入图片描述 4. 对标签进行压缩映射 5. 得到新的标签 6. 计算图特征向量：迭代 1 轮后，利用计数函数分别得到两张图的计数特征，得到图特征向量后便可计算图之间的相似性了

当出现两个图相同节点标签的出现次数不一致时，即可判断两个图不相似如果上述的步骤重复一定的次数后，没有发现有相同节点标签的出现次数不一致的情况，那么我们无法判断两个图是否同构 1.4 WL子树在WL Test的第 k k k次迭代中，一个节点的标签代表了：以该节点为根的高度为 k k k的子树结构当两个节点的 h h h层的标签一样时，表示：分别以这两个节点为根节点的WL子树是一致的举例：右图是节点1迭代两次的子树在这里插入图片描述

1.5 WL-test的公式表示 WL-test分为四步：聚合邻接节点标签、多重集排序、标签压缩、更新标签公式： a v k = f ( { h u k − 1 : u ∈ N ( v ) } ) h v k = Hash ⁡ ( h v k − 1 , a v k ) a^{k}_v = f\left(\{ h^{k-1}_u:u\in N(v) \} \right) \\ h^{k}_{v} =\operatorname{Hash}\left(h_v^{k-1}, a_v^k\right) avk=f({huk−1:u∈N(v)})hvk=Hash(hvk−1,avk)由公式发现，WL-test和GNN一样，学习节点表征分为两步：聚合和结合 2 GIN 2.1 单射的聚合方案直观来说，一个好的 GNN 算法仅仅会在两个节点具有相同子树结构时才会将其映射到同一位置由于子树结构是通过节点邻域递归定义的，所以我们可以将分析简化为这样一个问题：GNN 是否会映射两个邻域（即multiset）到相同的 Representation一个好的 GNN 永远不会将两个不同领域映射得到相同的Representation。即，聚合模式必须是单射因此，我们可以将 GNN 的聚合方案抽象为一类神经网络可以表示的多重集函数，并分析其是否是单射。 2.2 WL-test是GNN的上界引理：对于两个非同构图 G 1 G_1 G1 和 G 2 G_2 G2，如果存在一个图神经网络将这两个图映射到不同的Embedding向量中，那么也可以通过WL-test确定 G 1 G_1 G1 和 G 2 G_2 G2 是非同构图反证法可以证明 2.3 GIN：一个与 WL-test 性能相当的 GNN

GNN 和 WL-test 的主要区别在于单射函数中。顺利成章的，作者设计一个满足单射函数的图同构网络 GIN h v k = ϕ ( h v k − 1 , f ( { h u k − 1 : u ∈ N ( v ) } ) ) h_v^k = \phi(h^{k-1}_v,f(\{h_u^{k-1}:u\in N(v)\})) hvk=ϕ(hvk−1,f({huk−1:u∈N(v)}))

f f f 作用在 multisets 上， ϕ \phi ϕ 为单射函数另外GNN 作用在 multiset 的 READOUT 函数也是单射的 2.3.1 GIN的聚合：SUM+MLP 引理：设 X \mathcal{X} X （有限多重集的集合）可数，那么会存在一个函数 f f f： X → R n \mathcal{X}\rightarrow \mathbb{R}^n X→Rn 使得对于任意有限多重集 X ⊂ X X \subset \mathcal{X} X⊂X 都有 h ( X ) = ∑ x ∈ X f ( x ) h(X) = \sum_{x\in X}f(x) h(X)=x∈X∑f(x) 其中 h ( X ) h(X) h(X) 对各 X ⊂ X X \subset \mathcal{X} X⊂X 唯一，即有聚合的单射函数此外，任意一个多重集函数 g g g 都可以被分解为： g ( X ) = ϕ ( ∑ x ∈ X f ( x ) ) g(X) = \phi(\sum_{x\in X}f(x)) g(X)=ϕ(x∈X∑f(x))推论：设 X \mathcal{X} X （有限多重集的集合）可数，那么会存在一个函数 f f f： X → R n \mathcal{X}\rightarrow \mathbb{R}^n X→Rn 对于任意实数 ε \varepsilon ε 和任意有限多重集 X ⊂ X X \subset \mathcal{X} X⊂X、 c ∈ X c \in \mathcal{X} c∈X 都有 h ( c , X ) = ( 1 + ε ) ⋅ f ( c ) + ∑ x ∈ X f ( x ) h(c,X) = (1+\varepsilon)\cdot f(c)+ \sum_{x\in X}f(x) h(c,X)=(1+ε)⋅f(c)+x∈X∑f(x) 其中 h ( c , X ) h(c,X) h(c,X) 对各组合 ( c , X ) (c,X) (c,X) 唯一，即有聚合的单射函数此外，任意一个函数 g g g 都可以被分解为： g ( c , X ) = ϕ ( ( 1 + ε ) ⋅ f ( c ) + ∑ x ∈ X f ( x ) ) g(c,X) = \phi((1+\varepsilon)\cdot f(c)+\sum_{x\in X}f(x)) g(c,X)=ϕ((1+ε)⋅f(c)+x∈X∑f(x))因此，得到 GIN 的聚合方式引入多层感知机来学习函数 ϕ \phi ϕ 和 f f f： h v k = MLP ⁡ k ( ( 1 + ε ) ⋅ h v k − 1 + ∑ u ∈ N ( v ) h u k − 1 ) h_v^k = \operatorname{MLP}^k((1+\varepsilon)\cdot h_v^{k-1}+\sum_{u\in N(v)}h_u^{k-1}) hvk=MLPk((1+ε)⋅hvk−1+u∈N(v)∑huk−1) 多层感知机可以近似拟合任何函数第一次迭代时，若输入的是one-hot编码，则求和前不需要适用MLP计算 f f f，因为one-hot向量求和后依然是单射的 2.3.2 GIN的读出：SUM+CONCAT READOUT 函数的作用是将图中节点的 Embedding 映射成整张图的 Embedding作者提出SUM+CONCAT的方式：每轮迭代的节点特征求和作为该论的图特征，再拼接起每轮迭代的图特征作为最终图特征 h G = CONCAT ⁡ ( ∑ v ∈ G h v k ∣ k = 0 , 1 , ⋯ , K ) h_G=\operatorname{CONCAT}(\sum_{v\in G}h_v^k|k=0,1,\cdots, K) hG=CONCAT(v∈G∑hvk∣k=0,1,⋯,K) 2.3.3 GIN优异的原因

GIN 层数更多，多数GNN的变体只有一层

GIN 采用了更好的 sum 的聚合操作： sum可以学到网络结构信息，mean、max都不可以在这里插入图片描述

sum可以学习到更多信息： sum 可以捕捉到全部标签及其数量，mean 只能学习到标签的相对分布信息（标签比例），max 则偏向于学习具有代表性的信息（标签集合）在这里插入图片描述

3 作业

这里是引用在这里插入图片描述

4 代码实现 4.1 基于GIN的图表征模块 GINGraphRepr Module

基于图同构网络（Graph Isomorphism Network, GIN）的图表征学习主要包含以下两个过程：

首先计算得到节点表征其次对图上各个节点的表征做图池化（Graph Pooling），或称为图读出（Graph Readout），得到图的表征（Graph Representation）

若要进行图预测，则可以加多一个线性层，将图表征转换为预测结果

代码实现：求得节点表征：首先采用GINNodeEmbedding模块对图上每一个节点做节点嵌入（Node Embedding）求得图表征：对节点表征做图池化图的预测：最后用一层线性变换将图表征转换为预测结果 import torch from torch import nn from torch_geometric.nn import global_add_pool, global_mean_pool, global_max_pool, GlobalAttention, Set2Set from gin_node import GINNodeEmbedding class GINGraphRepr(nn.Module): def __init__(self, num_tasks=1, num_layers=5, emb_dim=300, residual=False, drop_ratio=0, JK="last", graph_pooling="sum"): """ Args: num_tasks (int, optional): 图表征维度，默认1 num_layers (int, optional): GINConv 层数，默认5 emb_dim (int, optional): 节点维度，默认300 residual (bool, optional): adding residual connection or not. Defaults to False. drop_ratio (float, optional): dropout rate. 默认0 JK (str, optional): 可选的值为"last"和"sum"。选"last"，只取最后一层的结点的嵌入，选"sum"对各层的结点的嵌入求和。默认"last" graph_pooling (str, optional): 图池化方式. 可选的值为"sum"，"mean"，"max"，"attention"和"set2set"。默认 "sum". Out: graph representation """ super(GINGraphPooling, self).__init__() self.num_layers = num_layers self.drop_ratio = drop_ratio self.JK = JK self.emb_dim = emb_dim self.num_tasks = num_tasks if self.num_layers

【本文地址】

公司简介

联系我们

【GNN】第八章 基于GIN的图表征学习

【GNN】第八章基于GIN的图表征学习