NeurIPS 2020 | RWNN：随机游走图神经网络

论文标题｜ Random Walk Graph Neural Networks
论文来源｜ NeurIPS 2020
论文链接｜ https://proceedings.neurips.cc/paper/2020/file/Paper.pdf
源码链接｜ https://github.com/giannisnik/rwgnn

TL;DR

这篇论文中作者提出了更加直观透明的图神经网络模型 RWNN(Random Walk Graph Neural Network)，RWNN 模型的第一层由一系列可训练的 “hidden graphs”组成，这些“hidden graphs”与随机游走核 (random walk kernel) 对应的输入图进行对比，以此来生成 graph-level 的表示，然后经过全连接神经网络来得到最终的分类结果。其中随机游走核是可微的因此模型 RWNN 可以端到端进行训练。实验部分在人工数据集中说明了 RWNN 的透明度（解释性），且在真实图数据集的图分类任务中验证了模型的强大性能。

Problem Definition

为了得到 graph-level 的表示，目前很多 MPNNs (message passing neural networks) 都是采用些 readout functions 来组合 node-level 表示来得到整图表示，但是这些忽略了节点间的 interactions，这些 interactions 特征虽然通过信息传递编码到节点表示中，但是这些过程缺少透明度我们很难了解到有用的信息是否真的编码到节点表示中。

此处解释下常用图中的 readout functions：一般先用平均操作求每一层的图表示，然后将所有层的图表示加权求和得到最终的图表示，如下图所示

在 GNNs 未流行前，Graph kernel 是图机器学习处理的主流方法，只是现在 GNNs 大热导致利用 Graph kernel 的方法少了而已，例如之前图分类任务较为流行的是 Graph kernel + SVM，模型解释性强但 Graph kernel 的缺点是计算复杂度较大。

目前 MPNNs 主要是将图转为向量表示然后用于下流任务，但是很难解释 MPNN 模型到底学到了什么知识，因此需要模型透明度较好，可以在输入图中先进行函数变换而不是直接将图转为向量表示。

综上所述问题，自然而然就知晓这篇论文会结合 Graph kernel 方法和 MPNN 的优势提出了图表示学习模型 RWNN ！👍🏻

定义图分类任务：给定图集合 $\{G_1,\cdots, G_N\}\subseteq \mathcal{G}$ 及其对应的标签 $\left\{y_{1}, \ldots, y_{N}\right\} \subseteq \mathcal{Y}$ ，需要学习图 $G$ 的向量表示 $\mathbf{h}_G$ 和映射函数 $f$ 以此应用图的分类任务或者回归任务：

$y_{G}=f\left(\mathbf{h}_{G}\right)$

令无向图 $G=(V,E)$ 中节点数 $n$ 边数 $m$ ，邻接矩阵 $\mathbf{A}\in \mathbb{R}^{n\times n}$ 及其对应的节点特征 $\mathbf{X}\in \mathbb{R}^{n\times d}$ 。

给定两个图 $G=(V,E)$ 和 $G^{'}=(V^{'},E^{'})$ ，图的叉乘表示为 $G_{\times} =( V_{\times}, E_{\times})$ 其中 $V_{\times}=\left\{\left(v, v^{\prime}\right): v \in V \wedge v^{\prime} \in V^{\prime}\right\}$ ， $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\}$ ，即节点包含两个图中的所有的节点对，边表示节点在两个图中都是相邻的。

Algorithm/Model

首先 GNN 的设计需要解决排列不变性 (permutation invariant) 的问题，即对于任意排列矩阵 $\mathbf{P} \in \Pi$ 其 $\mathbf{P} \mathbf{A} \mathbf{P}^{\top}$ 计算的结果是唯一的。

当前 MPNNs 系列一般是通过排列不变函数例如 sum、max、mean 等来聚合节点特征或者某种启发式策略来固定节点顺序，而这篇文章通过图核的方法来解决这个问题。

论文中提出的 RWNN 模型框架如下

从👆🏻图可以看出，RWNN 直接将输入图和 “hidden graphs” 进行对比，然后基于图核计算得到高维特征进行分类。主要问题在于如何得到这些可训练的 “hidden graphs”。

RWNN 包含 $N$ 个 “hidden graphs” $G_1,...,G_N$ ，其节点数量和节点特征不同且是可训练的，例如一个隐藏图 $G_i$ 包含 $n$ 个节点对应可训练的邻接矩阵为 $\mathbf{W}_i \in \mathbb{R}^{n\times n}$ ，节点特征为 $\mathbf{Z}_i \in \mathbb{R}^{n\times d}$ 。

📢 注意隐藏图可有向或者无向，论文中用到的是无向无自环图。在模型训练后通过可视化这些“隐藏图”即可非常直观地了解到模型学习到了哪些子图结构来区分不同的图，这就是论文提到的透明度和可解释性吧~ 👍🏻

为了使模型可以是端到端进行训练的，因此输入图和“hidden graphs”的对比函数需要是可微分的，但是当前很多图对比函数都是不可微分的。因此，作者一大创新点就是提出了基于随机游走核的图对比函数，随机游走核的主要思想就是计算两个图中相同随机游走序列的数量。

首先在叉乘图 $G_{\times}$ 上进行 $P$ 步随机游走，等价于同时在图 $G、G^{\prime}$ 上进行随机游走，其叉乘图对应的邻接矩阵为 $\mathbf{A}_{\times}$ 。那么两个图对应的 $P$ 步随机游走核定义如下：

$k\left(G, G^{\prime}\right)=\sum_{i=1}^{\left|V_{\times}\right|} \sum_{j=1}^{\left|V_{\times}\right|}\left[\sum_{p=0}^{P} \lambda_{p} \mathbf{A}_{\times}^{p}\right]_{i j}$

其中 $\lambda_p$ 表示随机游走权重。对于计算第 $p$ 步的核函数值如下，📢 论文中将权重参数 $\lambda$ 去掉即变体形式，没什么解释应该是对实验结果影响不大。

$k^{(p)}\left(G, G^{\prime}\right)=\sum_{i=1}^{\left|V_{\times}\right|} \sum_{j=1}^{\left|V_{\times}\right|}\left[\mathbf{A}_{\times}^{p}\right]_{i j}$

对于每一步 $p$ 可以计算得到核函数值。对于 $\mathcal{P}=\{0,...,P\}$ 和隐藏图集合 $\mathcal{G}_{h}=\left\{G_{1}, G_{2}, \ldots, G_{N}\right\}$ ，得到的输入图的特征即为笛卡尔积 $\mathcal{P}\times \mathcal{G}_h$ 维度特征，即 $\mathbf{H} \in \mathbb{R}^{N \times P}$ ，其中 $\mathbf{H}_{i j}=k^{(j-1)}\left(G, G_{i}\right)$ 。最后将 $\mathbf{H}$ 作为特征输入到 MLP 中进行分类。

很明显上述计算图核的过程中没有采用节点的特征，所以需要对上述函数进行泛化。

对于输入图 $G$ 其节点特征为 $\mathbf{X}\in \mathbb{R}^{n\times d}$ ，隐藏图 $G_i$ 及其可训练特征向量为 $\mathbf{Z}_i \in \mathbb{R}^{c\times d}$ 其中 $c$ 表示节点数量。令 $\mathbf{S}=\mathbf{Z}_{i} \mathbf{X}^{\top} \in \mathbb{R}^{c\times n}$ ，矩阵 $\mathbf{S}$ 即表示两个图间的相似性。定义 $vec$ 表示矩阵向量拼接操作， $\mathbf{s}=\operatorname{vec}(\mathbf{S}) \in \mathbb{R}^{nc}$ ，那么上述定义的图核计算可以重写为

$k^{(p)}\left(G, G^{\prime}\right)=\sum_{i=1}^{\left|V_{\times}\right|}\sum_{j=1}^{\left|V_{\times}\right|} \mathbf{s}_{i} \mathbf{s}_{j}\left[\mathbf{A}_{\times}^{p}\right]_{i j}=\sum_{i=1}^{\left|V_{\times}\right|} \sum_{j=1}^{\left|V_{\times}\right|}\left[\left(\mathbf{s} \mathbf{s}^{\top}\right) \odot \mathbf{A}_{\times}^{p}\right]_{i j}=\mathbf{s}^{\top} \mathbf{A}_{\times}^{p} \mathbf{s}$