论文阅读笔记：Random Walk Graph Neural Networks (随机游走图神经网络)_随机游走图核

论文简介

NeurIPS 2020接收的，论文下载地址.

摘要

近年来，图神经网络(GNNs)已成为在图上执行机器学习任务的实际工具。大多数GNN属于消息传递神经网络族(MPNNs)。这些模型采用迭代邻域聚合（neighborhood aggregation）方案来更新顶点表示。然后，为了计算图的向量表示，它们使用一些置换不变函数（permutation invariant function）来聚合顶点的表示。因此，MPNN将图形视为集合，因此似乎忽略了从图形拓扑中产生的特征。
本文提出了一种更直观、更透明的图形结构数据体系结构，即随机步行图神经网络(RWNN)。模型的第一层由许多可训练的“隐藏图”组成，这些图与使用随机游走核（random walk kernel）产生图形表示的输入图进行比较。然后将这些表示传递给产生输出的完全连接的神经网络。所采用的随机游走核是可微的，因此该模型是端到端可训练的。演示了模型在合成数据集上的透明度。 此外，在图分类数据集上对模型进行了实证评估，并表明它具有很强的性能。

permutation invariant function：如求和、均值或最大值。指的是特征之间没有空间位置关系。但是对卷积网络而言情况就不同了，特征是有位置关系的。

介绍

虽然最近提出了许多GNN变体，但它们中的大多数都有相同的基本思想，可以重新制定为一个单一的共同框架，即所谓的消息传递神经网络(MPNNs)。这些模型使用消息传递过程来聚合顶点的局部信息。对于与图相关的任务，MPNN通常将一些置换不变函数permutation invariant readout function应用于顶点表示，以产生整个图的表示。常见的readout function将每个图视为一组顶点表示，从而忽略了顶点之间的相互作用。注：这些些相互作用被隐式编码到消息传递过程产生的学习顶点表示中。 然而，由于图结构与特征信息相结合带来的透明度不足，这一点很难得到验证。

在深度学习出现之前，图核graph kernels已经成为在图上执行机器学习任务的标准方法。图核是在图的空间上定义的对称正半定函数。核方法的复杂度，神经网络模型可以学习对特定任务有用的表示，使得核方法在很大程度上被GNN所掩盖。不同于核函数直接比较图模型，MPNNs首先通过聚合其顶点的表示将图转换为向量，然后将一些函数（多层感知器）应用于这些图表示。GNN模型对学到内容的缺乏解释性，理想情况下，希望有一个模型，它直接将某些函数应用于输入图，而不首先将它们转换为向量。

论文中，提出了随机游走图神经网络(RWNN)。 该模型包含许多可训练的“隐藏图”，并使用随机游走核比较输入图与这些图。然后将核值传递给产生输出的完全连接的神经网络。 所使用的随机游走核是可微的，因此可以在训练过程中用反向传播来更新“隐藏图”。所提出的神经网络是端到端可训练的。该方法保留了核方法应用于结构化数据的灵活性，也学习任务相关的特征，而不需要特征工程。

1. 贡献1：提出RWNN，使用随机游走内核来产生图形表示。模型是高度可解释的。
2. 贡献2：开发了一种有效的计算方案，以降低所提出的模型的时间和空间复杂度。
3. 贡献3：评估性能。

About Graph Kernel
kernel method 在图结构中的研究主要有两类：
一是Graph embedding 算法，将图结构嵌入到向量空间,得到图结构的向量化表示，然后直接应用基于向量的核函数(RBF kernel, Sigmoid kernel, etc.) 处理，但是这类方法将结构化数据降维到向量空间损失了大量结构化信息；
二是Graph kernel算法， 直接面向图结构数据，既保留了核函数计算高效的优点，又包含了图数据在希尔伯特高维空间的结构化信息，针对不同的图结构(labeled graphs, weighted graphs, directed graphs, etc.) 有不同的Graph kernel。
图核的构建方法：
现在大多数的Graph Kernel都是基于Hausler在1999年提出的R-convolution理论构建的，这个理论的核心思想是设计一种图的分解方法，两个图的kernel value和分解后的子结构的相似程度有关。
给定两个图$G_1\left(V_1,E_1\right)$和$G_2\left(V_2,E_2\right)$，一种图的分解方式是$\mathcal{F}$，分解后的子结构为 F ( G 1 ) = { S 1 , 1 , S 1 , 2 , … , S 1 , N 1 } \mathcal{F}\left( {{G}_{1}} \right)=\left\{ {{S}_{1,1}},{{S}_{1,2}},\ldots ,{{S}_{1,{{N}_{1}}}} \right\} F(G1​)={S1,1​,S1,2​,…,S1,N1​​}, F ( G 2 ) = { S 2 , 1 , S 2 , 2 , … , S 2 , N 2 } \mathcal{F}\left( {{G}_{2}} \right)=\left\{ {{S}_{2,1}},{{S}_{2,2}},\ldots ,{{S}_{2,{{N}_{2}}}} \right\} F(G2​)={S2,1​,S2,2​,…,S2,N2​​}，基于上述结构，$G_1$和$G_2$的kernel value可以表示为：
$$k_R\left(G_1,G_2\right)=\sum _{n_1=1}^{N_1}\sum _{n_2=1}^{N_2}\delta \left(S_{1,n_1},S_{2,n_2}\right)$$其中，$\delta \left(S_{1,n_1},S_{2,n_2}\right)$表示在$S_{1,n_1}$和$S_{2,n_2}$同构时为1，不同时为0。任意一种图的分解式和子结构同构的判断方式的组合都可以定义一个新的Graph Kernel。常见的几种：基于游走（Random Walk）；基于路径的；基于子树的等。

相关工作

MPNNs：采用消息传递过程，每个顶点通过聚合邻居的特征向量来更新其特征向量。在消息传递过程的k次迭代之后，每个顶点获得一个特征向量，该特征向量捕获其k跳邻域内的结构信息。MPNNs与Weisfeiler-Lehman subtree kernel (WL)密切相关。具体来说，这些模型将WL核的重新标记过程推广到顶点与连续特征向量相关联的情况。标准的MPNN在区分非同构图中的作用最大程度上与WL核一样强大。

预备知识

论文中重点在图形分类问题。形式上给定一组图形 { G 1 , … , G N } ⊆ G \left\{ {{G}_{1}},\ldots ,{{G}_{N}} \right\}\subseteq \mathcal{G} {G1​,…,GN​}⊆G和他们的分类标签 { y 1 , … , y N } ⊆ Y \left\{ {{y}_{1}},\ldots ,{{y}_{N}} \right\}\subseteq \mathcal{Y} {y1​,…,yN​}⊆Y，目标学习一个特征向量${\mathbf{h}}_G$，可以预测图形$G$标签$y_G=f\left({\mathbf{h}}_G\right)$。该模型还可以处理其他与图形相关的任务，如图形回归问题。

设$G=(V,E)$表示无向图，顶点数为n，边数为m，邻接矩阵$\mathbf{A}\in {\mathbb{R}}^{n\times n}$是一个对称（通常是稀疏）矩阵，用于在图中编码边缘信息。对于节点分布图，图中的每个节点都与特征向量相关联。节点的特征$X\in {\mathbb{R}}^{n\times \text{d}}$，第i行是第i个节点的特征。

给定两个图[G=(V,E)]和[G’=(V’,E’)]，它们的直接积$G_{\times }=\left(V_{\times },E_{\times }\right)$是一个图有顶点集合 V × = { ( v , v ′ ) : v ∈ V ∧ v ′ ∈ V ′ } {{V}_{\times }}=\left\{ \left( v,{{v}^{\prime }} \right):v\in V\wedge {{v}^{\prime }}\in {{V}^{\prime }} \right\} V×​={(v,v′):v∈V∧v′∈V′}
和边集 E × = { { ( v , v ′ ) , ( u , u ′ ) } : { v , u } ∈ E ∧ { v ′ , u ′ } ∈ E ′ } {{E}_{\times }}=\left\{ \left\{ \left( v,{{v}^{\prime }} \right),\left( u,{{u}^{\prime }} \right) \right\}:\{v,u\}\in E\wedge \left\{ {{v}^{\prime }},{{u}^{\prime }} \right\}\in {{E}^{\prime }} \right\} E×​={{(v,v′),(u,u′)}:{v,u}∈E∧{v′,u′}∈E′}

举个例子

随机游走GNNs

图的神经网络设计的主要挑战之一是如何处理置换不变性。图的顶点的任何排列都会产生一个结构相同的图。因此，无论图的顶点排序如何，GNN的输出都是相同的。图通常由其邻接矩阵表示，也可能由包含其顶点属性的矩阵表示。给定一个图G的邻接矩阵A，该模型对于所有矩阵$\mathbf{P}\mathbf{A}{\mathbf{P}}^{\top }$产生相同的输出是必要的，其中P∈Π，Π表示n×n个置换矩阵的集合。大多数MPNN是通过将一些置换不变函数应用于顶点表示来实现的（函数例如，和，最大，平均算子)。其他GNN通常使用一些启发式方法，通过对图的顶点施加排序来实现不变性。 在本文中，提出了一种不同的方法来获得图形表示。利用图核中已建立的概念，并利用函数来比较对其输入顶点排列不变的图。

所提出的RWNN模型将输入图与许多“隐藏图”进行比较，即图的邻接矩阵和属性矩阵是可训练的。提出的模型中包含N个隐藏图，这些图的定点数目（图的大小）不尽相同。这些图可以是未标记的，也可以用连续的多维特征注释它们的顶点。这些“隐藏图”的结构和顶点属性（若存在）是可训练的，即大小为n的“隐藏图”Gi的邻接矩阵由可训练矩阵${\mathbf{W}}_i\in {\mathbb{R}}^{n\times n}$表示，而顶点属性包含在另一个可训练矩阵${\mathbf{Z}}_i\in {\mathbb{R}}^{n\times d}$的行中。注，“隐藏图”可以是带或不带自循环的加权有向或无向图。在实验中，将其约束为无向图，且不需要自循环(n(n-1)/2个可训练参数)。由于“隐藏图”的结构适合于手头的任务，因此所提出的模型具有很高的可解释性。通过可视化训练阶段结束时“隐藏图”的结构，可以更直观地理解所考虑的问题。这些图将学习允许模型区分可用类的结构。

与现有的方法相比，本文将输入图映射到向量，将它们与模型的N个“隐藏图”进行比较。注，图比较算法需要是可微的，才能使网络达到端到端的训练。否则，“隐藏图”的结构和属性无法在反向传播训练期间学习（大多比较图的算法都是不可微的）。对于不可微图比较算法，在训练过程中，“隐藏图”可以保持不变。然而，这将大大限制模型的表现力。在本文中，提出了一个可微函数，用于比较图之间的关系，属于随机游走核族。一般来说，随机游走核根据两个图中常见游走的数量来量化两个图的相似性。在随机游走核的众多变化中，本文重点研究了P步随机游走核，它比较了两个图中长度为P的随机游走。

在两个图G和G’的直接积G×（在第3节中引入）上执行随机游走相当于在两个图G和G’上同时执行随机游走。G×的邻接矩阵为A×。如上所述，随机游走内核计数G和G’上的所有匹配游走对。假设在G和G0的顶点上的开始和停止概率为均匀分布，通过积图G×的邻接矩阵A×可以得到匹配步数。给定一些P∈N，将两个图G和G’之间的P步随机游走核定义为：$$k\left(G,G^{\prime }\right)=\sum _{i=1}^{|V_{\times }|\mid }\sum _{j=1}^{|V_{\times }|}{\left[\sum _{p=0}^P{\lambda }_p{\mathbf{A}}_{\times }^p\right]}_{ij}$$所提出的RWNN模型计算了P步随机游走核的一个轻微变体，它计算了两个图G和G’之间的公共长度步数（方程2）：$$k^{(p)}\left(G,G^{\prime }\right)=\sum _{i=1}^{|V_{\times }|\mid }\sum _{j=1}^{V_{\times }\mid }{\left[{\mathbf{A}}_{\times }^p\right]}_{ij}$$（邻接矩阵的p次方，即随机走p步后的邻接矩阵）。对于不同的p可以得到不同的核值。这些核值可以被认为是输入图的特征。因此，给定两组 P = { 0 , 1 , … , P } \mathcal{P}=\{0,1,\ldots ,P\} P={0,1,…,P}和 G h = { G 1 , G 2 , … , G N } {{\mathcal{G}}_{h}}=\left\{ {{G}_{1}},{{G}_{2}},\ldots ,{{G}_{N}} \right\} Gh​={G1​,G2​,…,GN​}，其中$G_1,G_2,\dots ,G_N$表示N个“隐藏图”，可以计算笛卡尔积$\mathcal{P}\times {\mathcal{G}}_h$的每个元素的一个特征。对于每个输入图G，可以建立一个矩阵$\mathbf{H}\in {\mathbb{R}}^{N\times P}$其中${\mathbf{H}}_{ij}=k^{(j-1)}\left(G,G_i\right)$。然后，将矩阵H扁平化flatten，并将其输入到一个完全连接的神经网络中，以产生输出。所提出的体系结构如图1所示。

存在问题:上面提出的体系结构不能处理顶点被实值多维顶点属性注释的图。接下来，将上述函数推广到包含此类顶点属性的图。具体地，让$X\in {\mathbb{R}}^{n\times d}$表示包含输入图G的顶点属性的矩阵。同样，用相同维数的向量来注释“隐藏图”的顶点。对于每个“隐藏图”Gi，这些向量由一个可训练矩阵${\mathbf{Z}}_i\in {\mathbb{R}}^{c\times d}$的行表示，其中c是Gi的顶点数。令$\mathbf{S}={\mathbf{Z}}_i{\mathbf{X}}^{\top }$，$S\in {\mathbb{R}}^{\text{c}\times \text{n}}$。S的第ij个元素相当于隐藏图矩阵Gi第i个顶点和输入图G第j个顶点的内积（如果顶点中相同属性重合多，则Sij计算结果会大）。粗略地说，这个矩阵编码两个图的顶点的属性之间的相似性。
设vec表示矢量化算子，它通过将矩阵的列一个接一个地叠加来将矩阵转化为向量。将该操作应用到矩阵S上，可得到$\mathbf{s}=\mathrm{vec}(\mathbf{S})$，$s\in {\mathbb{R}}^{\text{nc}}$。然后，可以计算在两个图之间精确计算长度p的公共步数的核，如下所示（方程3）：$$k^{(p)}\left(G,G^{\prime }\right)=\sum _{i=1}^{|V_{\times }|}\sum _{j=1}^{|V_{\times }|}{\mathbf{s}}_i{\mathbf{s}}_j{\left[{\mathbf{A}}_{\times }^p\right]}_{ij}=\sum _{i=1}^{|V_{\times }||V_{\times }|}{\left[\left(\mathbf{s}{\mathbf{s}}^{\top }\right)\odot {\mathbf{A}}_{\times }^p\right]}_{ij}={\mathbf{s}}^{\top }{\mathbf{A}}_{\times }^p\mathbf{s}$$其中，$\odot$表示两个矩阵的元素的乘积。注，矩阵$A_{\times }^p$的第ij元素等于G×的第i和第j顶点之间长度p步游走可到达的数目。G×的每个顶点对应于一对顶点，一个来自输入图G，一个来自“隐藏图”Gi。可以给G×的每个顶点分配一个实值来量化它所表示的两个顶点的属性之间的相似性。这些值包含在向量s中。请注意，如果s是nc维向量，元素全为1，则方程(3)等于方程(2)。（这种情况出现在，所有顶点都有且仅有一个属性）。

应用细节

下面给出了更多关于所提出的RWNN模型的实现的细节。重要的是，提出了用来降低所提出的体系结构的时间和空间复杂性的计算方案。

如上所述，在实现过程中，“隐藏图”对应于没有自循环的无向图。因此，具有n个顶点的“隐藏图”的邻接矩阵用n(n-1)/2可训练参数表示。由于这些图是可训练的，它们的邻接矩阵的元素可能取负值。虽然这在一般情况下不是一个问题，但为了提高模型的可解释性，将ReLU函数应用于“隐藏图”的邻接矩阵，将边缘权重限制为非负实值。已知，如果A和A’是两个图G和G’各自的邻接矩阵，则直接积G×的邻接矩阵${\mathbf{A}}_{\times }=\mathbf{A}\otimes {\mathbf{A}}^{\prime }$，其中$\otimes$表示两个矩阵之间的Kronecker乘积。[此处可以根据预备知识部分中，两个图直接积的定义，尝试计算一个]。因此，在设置中，如果A和RELU(Wi)是输入图G和“隐藏图”Gi的邻接矩阵，则直接乘积的邻接矩阵等于${\mathbf{A}}_{\times }=\mathbf{A}\otimes \mathrm{RELU}\left({\mathbf{W}}_i\right)$。

如果A是一个 m x n 的矩阵，而B是一个 p x q 的矩阵，克罗内克积则是一个 mp x nq 的矩阵
A ⊗ B = [ a 11 B ⋯ a 1 n B ⋮ ⋱ ⋮ a m 1 B ⋯ a m n B ] A\otimes B=\left[

$$\begin{matrix} { {a}_{11}}B & \cdots & { {a}_{1n}}B \\ \vdots & \ddots & \vdots \\ { {a}_{m1}}B & \cdots & { {a}_{mn}}B \\ \end{matrix}$$ \right] A⊗B=⎣⎢⎡​a11​B⋮am1​B​⋯⋱⋯​a1n​B⋮amn​B​⎦⎥⎤​

接下来将证明，为了评估方程（3）中定义的核，不需要显式计算矩阵A×及其幂。Kronecker积和vec操作符是由众所周知的属性连接的（方程4）：$$\mathrm{vec}(\mathbf{A}\mathbf{B}\mathbf{C})=\left({\mathbf{C}}^{\top }\otimes \mathbf{A}\right)\mathrm{vec}(\mathbf{B})$$（这个公式可以通过观察2维方阵A,B,C计算结果加深理解）
让vec-1表示将向量转换为矩阵的逆矢量化算子。 给定矩阵A，vec-1(b)和C，方程（4）可以写成：
$$\mathrm{vec}\left(\mathbf{A}{\mathrm{vec}}^{-1}(\mathbf{b})\mathbf{C}\right)=\left({\mathbf{C}}^{\top }\otimes \mathbf{A}\right)\mathrm{vec}\left({\mathrm{vec}}^{-1}(\mathbf{b})\right)=\left({\mathbf{C}}^{\top }\otimes \mathbf{A}\right)\mathbf{b}$$
方程（3）和上述等式：
$$k^{(1)}\left(G,G_i\right)={\mathbf{s}}^{\top }{\mathbf{A}}_{\times }\mathbf{s}={\mathbf{s}}^{\top }\left(\mathbf{A}\otimes \mathrm{RELU}\left({\mathbf{W}}_i\right)\right)\mathbf{s}={\mathbf{s}}^{\top }\left({\mathbf{A}}^{\top }\otimes \mathrm{RELU}\left({\mathbf{W}}_i\right)\right)\mathbf{s}={\mathbf{s}}^{\top }\mathrm{vec}\left(\mathrm{RELU}\left({\mathbf{W}}_i\right){\mathrm{vec}}^{-1}(\mathbf{s})\mathbf{A}\right)$$第三个等式成立，因为假设输入图是无向的。 注，上述结果只适用于p=1（用到了直接积G×的邻接矩阵${\mathbf{A}}_{\times }=\mathbf{A}\otimes {\mathbf{A}}^{\prime }$）。 为了推广结果，有必要证明${\mathbf{A}}_{\times }^p={\mathbf{A}}_1^p\otimes {\mathbf{A}}_2^p$适用于所有p∈N。
命题1：${\mathbf{A}}_{\times }^p={\left({\mathbf{A}}_1\otimes {\mathbf{A}}_2\right)}^p={\mathbf{A}}_1^p\otimes {\mathbf{A}}_2^p$

【这个公式没看懂】从这个公式中得到的结论是：在计算$k^{(p)}\left(G,G_i\right)$时，可以不用计算${\mathbf{A}}^p$和$\mathrm{RELU}{\left({\mathbf{W}}_i\right)}^p$，而是计算$\mathrm{RELU}{\left({\mathbf{W}}_i\right)}^p{\mathbf{Z}}_i$和${\mathbf{X}}^{\top }{\mathbf{A}}^p$。举个例子，当p=3时，可以计算${\mathbf{X}}^{\top }{\mathbf{A}}^3\text{=}\left(\left({\mathbf{X}}^{\top }\mathbf{A}\right)\mathbf{A}\right)\mathbf{A}$。由于将A存储为具有m个非零项的稀疏矩阵，因此模型的有效实现的时间复杂度$\mathcal{O}(Pd(Nr(r+n)+m))$，其中P是最长游走的步数，d是顶点属性的维数，N是“隐藏图”的数目，r是每个“隐藏图”的大小，n是输入图的大小。在$P\ll m$和$d\ll m$的现实假设下，运行模型需要时间$\mathcal{O}(Nr(r+n)+m)$。

如果顶点属性是非常高维的，可以使用一个1层感知器，即$\tilde{\mathbf{X}}=f(\mathbf{X}\mathbf{W}+\mathbf{b})$，其中$\mathbf{W}\in {\mathbb{R}}^{d\times \tilde{d}}$，$b\in {\mathbb{R}}^{\tilde{d}}$分别是权重矩阵和偏置向量，f是非线性激活函数。 或者甚至可以使用MPNN体系结构来更新这些顶点表示，即$\tilde{\mathbf{X}}=\mathrm{MPNN}(\mathbf{A},\mathbf{X})$。

实验评估

合成数据集

如前所述，所提出的模型是高度可解释的，因为可以可视化学习的“隐藏图”，并可能发现数据背后变化的解释因素。
数据集：创建了5个二分类数据集，每个数据集具有1000个合成图。
结果：图3显示了5个数据集中的每个数据集的两个“隐藏图”。 有趣的是，“隐藏图”及其相应的基序具有一些相似的性质。

公开数据集

结论

本文提出了一种新的RWNN神经网络结构，用于在图上执行机器学习任务。 该模型通过一组可训练的“隐藏图”对输入图生成图形表示，使用P步随机游走核的变体。所进行的实验突出了所提出的模型的高可解释性及其在公开数据集上的有效性。