IJCAI2022: 利用随机游走进行聚合的图神经网络

转载自：MIND Laboratory

图片

原文地址：IJCAI2022: 利用随机游走进行聚合的图神经网络

01  Introduction

在同质图中，具有相同标签或相似特征的结点更倾向于靠近彼此。而在异质图中，具有不同标签或不相似特征的结点也有邻接的可能性。在真实世界网络中，很多网络都是异质的，并不满足同质图的假定。比如在电商网络中，诈骗者经常骚扰正常用户；在邮件网络中，我们的邮箱经常会收到垃圾信息。

图卷积方法(Graph-Convolution-based methods)已在同质图的表示学习中取得了良好的效果。然而，由于图卷积网络(Graph Convolutional Networks, GCNs)是基于同质图假定下的方法，对异质图的适用性较差。

本文提出了新的基于随机游走进行聚合的图神经网络(RAW-GNN)，一方面利用广度优先策略的随机游走获取图中的同质性信息，另一方面利用深度优先策略的随机游走获取图中的异质性信息。这使得RAW-GNN能够同时适用于同质图和异质图。

02  Motivation

目前，针对GCN受同质性限制的这一问题，解决方案大致可分为2种：

1、在聚合函数中，对具有不同标签的邻居结点之间的注意力权重进行调整。结果是，来自相同标签结点的信息被赋予正权值，而来自不同标签结点的信息被赋予负权值，进而阻止了不相似的邻居之间进行有害或无用的信息传递。

2、直接从高阶邻居进行信息聚合。此方法假定在异质图中，某结点的直接邻居中异质的结点占多数，但在高阶邻居中，同质的结点则占多数，进而能提供给目标节点更有用的信息。这样的方法能从一定程度上缓解异质性问题。

然而，上述方法并不能从根本上解决问题。原因是GCN的核心聚合机制中采用了加法运算符，这是GCN等方法受限于同质图的关键。

为了解决这一问题，本文介绍了基于随机游走聚合的图神经网络，简记为RAW-GNN。

与传统的把结点邻居的定义不同，本文将结点邻居定义扩展到结点的k-hop基于路径的邻居。一条基于随机游走生成的k-hop路径保留了这k个结点的原始特征，以及在此游走序列中结点的结构信息。除了采用BFS和DFS游走策略分别对同质性和异质性信息进行获取外，本文还采用了基于循环神经网络(Recurrent Neural Networks, RNN)的聚合函数，能够获取随机游走中结点的序列信息。除此之外，对于从DFS通道或BFS通道获取的信息，采取注意力机制进行重要性的学习，使得模型能够根据不同的网络特征，自动地进行同质性和异质性之间的权衡。

图片

如图所示，现有的方法把结点的邻居定义为与目标结点距离为k的结点，这样做有可能忽视来自与目标结点距离不同的结点对或结点序列为目标节点提供的信息，比如说上图左侧认为结点0的1阶邻居是结点1和2，2阶邻居是结点3。然而这种定义方式可能会像刚才说的那样，结点1和3之间的边或结点2和3之间的边无法为目标结点0提供有用的信息。

为了避免这种情况发生，本文采用随机游走的方式对结点邻居进行定义，认为结点序列<3,1,0>作为结点0的“DFS邻居”，传递异质性信息；结点序列<1,2,0>作为结点0的“BFS邻居”，传递同质性信息。这样无论是较近的同质性信息或较远的异质性信息都能为生成结点0的嵌入做出贡献。

03  Preliminaries

3.1 Basic Notations

图片

3.2 Message-Passing Neural Network, MPNN

传统的l层MPNN被定义如下：

图片

我们知道，不同MPNN模型之间的不同之处在于不同的结点i的邻居N_i 、aggregate和combine函数进行表示。通常，结点i的邻居结点被认为是i的直接邻居结点或k-hop邻域结点。与之不同的是本文下来将定义的基于路径的邻居。

3.3 Path-based Neighborhoods

路径P 被定义为结点有序序列的形式：P=\{v_{p_1},v_{p_2},...,v_{p_K}\} 其中K 是路径长度。P_i 结点i的基于路径定义的邻居记为P_i ，其中结点i位于结点序列的末尾也就是v_{p_K} 。所有基于游走策略s \in S 的结点i的邻居P_i 组成了基于路径的邻域N^s_i 。其中S 是策略集。换句话说，有：P_i \in N^s_i 。

3.4 Generalized Edge Homophily Ratio 边同质比

图总体的同质性由此参数进行衡量。具体来说，计算的是连接一对具有相同标签的结点的边的数量，再除以总边数得到的一个分数：

图片

这一标量是基于结点标签进行设计的。本文对其进行generalize，扩展到结点特征上进行设计。

首先定义两结点间的相似度函数(在0到1之间)：

图片

该函数应具有如下性质，当结点i和j相似时，sim(i,j) 应当接近1；当结点i和j不相似时，sim(i,j) 应当接近0。进而定义扩展边同质比如下：

图片

容易注意到，当相似度函数sim(i,j) 被如下式定义时，式2就变回上面提到的基于结点标签定义的边同质比了。意思就是可以把分母拆开成E个1相加，分子对于每条边来说如果是相似的被设置为1，不相似的被设置为0，然后再加起来。这样是一个非0即1的离散的处理方式。

图片

而本文提出的基于特征来定义的结点相似度是这样的：

图片

可以这样理解：在向量空间内对结点i和j的特征求cos值，若两向量相距很近，那么其cos值就会很大，相似度很大，反之亦然。这也在直观上相符。这样的处理是非离散的，相似度根据计算，结果会是在[0,1]内的连续值。

04  RAW-GNN

图片

4.1 Overview

如图所示，RAW-GNN模型主要包含4部分：

1、随机游走生成器，用于生成随机游走序列；

2、基于RNN的聚合；

3、基于注意力的同种游走策略内组合(intra-strategy)；

4、不同种游走策略间的组合(inter-strategy)。

4.2 Random Walk Generator

邻居结点的作用在于为目标结点提供有用的信息，不同于GCN，本文采用路径的方式来定义邻居。为了生成结点邻居，本文采用类似Node2Vec的方式，使用2阶随机游走策略。引入参数p、q对BFS和DFS游走的倾向进行指导。这是一种biased random walk。

如图所示，假设当前的一次随机游走刚刚从结点t出发，经过边e_{t,s} ，目前位于结点s ，并且将要访问下一个结点r ，本文将下一个被访问的结点的(未归一化)概率设置为：

图片

其中d_{tr} 表示结点t 和r 之间的最短距离。

简单的示意图如下：

图片

p、q的作用在于对随机游走的倾向进行调整：p越小，游走返回上一个结点的可能性越大；q越小，游走移动至距上一个结点更远的结点的可能性越大。

本文认为，设置p<1同时q>1，则随机游走倾向于以BFS方式进行；设置p>1同时q<1，则随机游走倾向于以DFS方式进行。

4.3 RNN-based Path Aggregator

聚合函数的目的是对路径上所有结点进行编码，同时考虑结点的次序信息，这样能够保留关于路径上结点的更多结构性信息。

第l层的路径聚合函数

图片

被定义为：

图片

其中h^{(l)}_P \in \mathbb{R}^{d_l}是路径P=\{v_{n_1},v_{n_2},...,v_{n_K}\} 在第l层的嵌入。h^{(l)}_{P_k} \in \mathbb{R}^{d_l} 是结点v_{n_K} 在第l层的特征。k=1,2,...K 和\theta 代表聚合函数所有的可学习参数。

4.4 Attention-based Intra-Strategy Combinator

在计算出采用游走策略s时所有结点v_i \in V 的路径嵌入h^s_P \in N^S_i 后，我们需要将在当前游走策略下得到的嵌入进行结合，使其成为策略特殊性的结点嵌入。

为了能更好地体现不同的随机游走路径对目标结点嵌入的贡献程度，本文采用注意力机制对N^S_i 中的路径嵌入所具有的不同权重进行学习：

图片

其中a_P \in \mathbb{R}^{d_l} 时可学习的注意力系数；e_P 是路径P的未归一化的权重值；\alpha_P 是利用softmax函数对N^S_i 中的所有路径权重进行归一化的值。

为了强化学习效果，本文采用标准的多头注意力机制：

图片

4.5 Inter-Strategy Combinator

在将同种游走策略得到的嵌入进行结合后，进而对不同游走策略得到的嵌入再次进行结合。与GCN中的加法运算操作不同，本文采用串联(concatenation)的方式对不同游走策略得到的嵌入进行结合。这样做的目的是能够保留不同游走策略得到的路径分布，保留较为完整的结构信息。

图片

其中h_i \in \mathbb{R}^{d_{final}} 表示结点v_i 的最终嵌入。

4.6 Classifier

本文的工作主要集中在半监督的结点分类任务上。先采用一个线性层进行处理，然后再用softmax计算得到预测的标签可能性，并使用标准交叉熵作为损失：

图片

其中W \in \mathbb{R}^{d_{final}\times |C|} 是可学习的权重矩阵，|C| 是类别总数。Y_i,\hat y_i \in \mathbb{R}^{|C|} 分别是标签y_i 以及预测得到的结点i的标签的one-hot嵌入。当c=y_i 时有Y_{i_C}=1 ，Y_i 中的其他所有元素被设置为0。

05  Experiments

本实验采用了7个真实世界数据集：4个强异质性数据集和3个强同质性数据集。(黄色为同质数据集，绿色为异质数据集)

对于RAW-GNN的随机游走采样，本文采用p = 10, q = 0.1作为DFS策略的参数，p = 0.1, q = 10作为BFS策略的参数。实验结果如下：

图片

本文还将得到的结点嵌入投影至2维平面上进行可视化：

图片

可以看出，相较于其他方法，RAW-GNN得到的2维嵌入各类别之间的分界更为清晰。

06  Conclusion

本文提出了基于随机游走进行聚合的图神经网络RAW-GNN，将传统GCN对结点邻居的定义扩展至基于路径的定义。采用2阶随机游走策略，设置参数p与q对随机游走的倾向进行控制和调整。得到的嵌入先在游走策略内部进行组合，再在不同策略之间进行组合，最大程度保留游走结点次序信息和图的结构信息。在结点分类实验中取得了SOTA的结果。