论文阅读笔记：Random Walk Graph Neural Networks（NIPS2020）

0、简介

• 论文名字：Random Walk Graph Neural Networks
• 下载地址：https://www.lix.polytechnique.fr/~nikolentzos/files/rw_gnns_neurips20
• 会议：NIPS2020

1、论文的motivation

图神经网络可以学习图的特征，从而进行图分类的任务。目前，主流的图神经网络算法都是MPNN的结构。这种结构的图神经网络可以很好的学习节点的特征信息，但是却忽略的图的结构信息。为了利用学习图的结构信息，这篇文章提出了基于随机游走核函数（random walk kernel）的图神经网络，取名叫做Random Walk Graph Neural Network（RWNN）。该模型可以学习图的结构信息，并将学到的信息用于图分类任务，并且该模型具有很强的可解释性。

2、模型结构

这篇文章提出了“隐藏图”（hidden graph）的概念。那么何为隐藏图呢？隐藏图就是随机初始化的N个图，图的节点数可以是任意的。使用模型进行图分类，向模型中输入一张图，输入图和每一个隐藏图通过random walk kernel 计算相似度，将计算得到的相似度值组成一个矩阵传入一个全连接神经网络，接下来就是和一般神经网络做分类问题一样了。下图为论文给出的模型结构。

3、实现细节

3.1 相似度值矩阵的计算

使用random walk kernel 计算相似度时，可以设置步长，步长不同计算的相似度值不一样。比如说图G和图G2之间，可以计算1-step的相似度，也可以计算2-step的相似度，可以计算P-step的相似度。至于如何使用random walk kernel 计算两个图之间不同step的相似度，我们先按下不表。我们设模型中有 N N N个隐藏图，输入图和每个隐藏图都计算1到P step的相似度，那么我们就能得到一个相似度值矩阵 H H H, H H H的维度是N*P，第 i i i行的第 j j j个值代表输入图和第 i i i个隐藏图之间j-step的相似度值。

3.2 神经网络进行分类

作者在这块并没有太多的叙述，只用了下面这一句话来说明

Then, matrix H is flattened and fed into a fully-connected neural network to produce the output.

这里确实没有太多需要仔细讲的，全连接神经网络，输出层再接一个softmax，就可以用来做分类问题了。到这里，抛开刚才按下没表的random walk kernel 部分，这篇论文的模型其实就已经结束了。训练模型的时候，采用梯度下降算法，通过优化全连接神经网络中的参数就可以让模型拥有图分类的能力。因此这篇论文大部分篇幅都是在讲random walk kernel的问题，一开始的时候，也是在介绍random walk kernel，所以，我第一次看这篇论文的时候，觉得模型学习的时候会更新random walk kernel中的参数，但是把论文读完后，我发现模型中更新的参数应该只有全连接神经网络中的参数。random walk kernel内部是没有参数的，他其实是定义了一种运算，具体细节我们这里依然不表。

3.2 random walk kernel 的作用

上节我们说到random walk kernel内部是没有参数，因此我们可以把random walk kernel看做是一个特征提取器，提取一个特征矩阵 H H H。他在神经网络中的角色和pooling操作是一样的，我们在优化模型的时候是不会优化random walk kernel的。

3.3、如何使用random walk kernel 计算相似度

random walk kernel算法计算两图的相似度是在论文[1]中提出的。该算法把两个图之间匹配的随机游走路径的数量作为了两图的相似度值。计算的时候先求两个图 G G G和 G ′ G^{'} G′的直积 G x G_{x} Gx​(direct product, 什么是两个图的直积，可以参考这篇博客中的讲解：基础笔记：图的一些概念），使用 G x G_{x} Gx​的邻接矩阵 A x A_{x} Ax​可以求得两个图之间匹配的随机游走路径的数量。计算公式如下所示

3.4 模型的可解释性

本文的一个创新点就是：本文提出的模型具有较强的可解释性。作者将隐藏图的邻接矩阵设置为可训练的，每次更新参数的时候，不只会更新神经网络中的参数，隐藏图的邻接矩阵也会更新。此时就存在一个问题，那就是3.3中random walk kernel 计算相似度的方法是不可微的，梯度是回传不回去的。作者基于此提出了一种可微的random walk kernel 计算相似度的方法，计算方法如下所示

作者说该计算方法是可微的，这个公式和上面的公式的差距就在于没有把不同step的邻接矩阵加起来，而是每一个step都计算了一次相似度值。至于为什么这种形式的计算就是可微的，我目前还没有搞清楚，微积分的定义这块我学的也不是很扎实，后续弄懂了，我会进行更新。

使用了可微的核函数后，隐藏图在训练过程中就可以被更新到了。训练结束后，将隐藏图可视化，对可视化结果分析可以发现图的结构信息被学习到。作者做了两类实验，一种是人工生成的图，一种是真实世界的图。作者对人工生成的图的实验的隐藏图进行了可视化，结果如下所示

第一行的5个图是5种不同类型的图，下面十幅图是隐藏图，通过可视化可以看出来，隐藏图学习到了每类图的结构特征，比如Cycle 类的图，就有对应的隐藏图是含有圈的，Star类的图，也有对应的隐藏图是有中心节点这种结构的。

3.5 图的节点特征

前面讲的方法中，没有涉及到节点的特征，作者同样给出了节点特征的处理方法。图的节点特征可以用节点特征矩阵来表示，输入图的节点特征矩阵为 X X X,维度是n*d，n为节点数量，d是特征维度。隐藏图的节点特征矩阵为 Z Z Z，维度为c*d，c为节点数量，隐藏图的特征维度和输入图的特征维度相同。通过 Z X T Z X^{T} ZXT就可以计算出两个图的两两节点之间的相似度，这个计算相似度的方法和attention中计算相似度类似。在计算random walk kernel 的时候，将两个图用直积生成了一个新的图（图用直积的概念请看：基础笔记：图的一些概念），新图的节点就是原来两图的节点对，新图中每个节点都是由输入图中的一个节点和隐藏图中的一个节点组成的，因此，新图中的节点特征就是组成该节点的两节点之间的相似度值。在计算random walk kernel 的时候，就是计算从一个节点出发，到另一个节点总共有多少种路径方式，比如说从节点a出发，到节点c，有3种路径，当有了节点特征，就把节点a和节点c的特征相乘（注意，这里是在新图上操作的，新图的节点特征都是标量），然后再乘以路径数3，这种方法就是带节点特征图的random walk kernel计算方法。作者在计算过程用了矩阵进行计算，我这里就给大家讲解一下方法的思路，具体实现请大家看论文中对应的部分。

3.6 优化方法

作者对模型的实现进行了优化，主要是一些矩阵上的变换，可以提升计算效率，我这里就不具体写了，因为我也没怎么看懂，大家感兴趣查看论文对应部分。

4 我的想法

4.1 论文中的优点

• 论文实验很充足，在模拟图和真实世界图上都做了实验。

• 论文将Graph kernel和神经网络结合在了一起，是一个很不错的创新点。

4.2 论文的不足

• 在3.2中我们提到，random walk kernel可以看做是一个特征提取器，如果从这个角度出发，作者可以设置实验，探究隐藏图个数对图分类的影响。同样还可以探究步数p对分类效果的影响。

• 改变了random walk kernel算法，让梯度回传，对隐藏图做了更新，作者在文中说了这么一句话：

  For non-differentiable graph comparison algorithms, the “hidden graphs” could be held constant during training. However, that would limit a lot the expressive power of the model.

作者认为采用不可微分的比较算法（也就是不更新隐藏图）会影响模型的表达能力，但是作者并没有给出相应的对比实验来说明。

Reference

[1] On Graph Kernels: Hardness Results and Efficient Alternatives