【2019/ICML】Position-aware Graph Neural Networks

论文：https://arxiv.org/pdf/1906.04817.pdf
源码：https://github.com/JiaxuanYou/P-GNN

TL;DR

目前存在的 GNNs 系列模型都不能捕获给定节点相对于其它所有节点的位置特征，本文中提出一个可以捕获节点特征的图神经网络模型 P-GNN。P-GNN 首先采样 anchor nodes 集合，然后计算给定目标节点相对于 anchor nodes 集合的距离，再学习一个非线性的距离权重的聚合模式。因此 P-GNN 融合节点相对于其它节点的位置信息。论文实验部分在链路预测与社团检测任务中明显优于其它模型。

问题引入

目前的一系列 GNNs 模型不能捕获图中节点的位置信息。在不考虑节点属性特征的情况下，如果图中两个节点 $v_1, v_2$ 如果相邻节点结构相同，那么 GNN 模型将会将这两个节点嵌入到特征空间中的相同位置，即融合得到的特征相同，但实际上这两个节点应属于不同的类。如下图所示：

目前提出了两种方法来解决该问题：

以 one-hot 编码来扩充节点的属性；
增加 GNN 的深度；

但是以上两种方法存在对应的问题：增添节点属性时不能泛化到节点属性未知的情况，任意深度的 GNN 也不能区分同构图。

基于以上问题，作者提出的 P-GNN 不仅能够融合节点相对于其它的位置信息，还能保持模型的归纳能力和融合节点的属性特征。论文基于的假设是节点位置可以由其与 anchor nodes 节点的距离来量化。P-GNN 首先选择 $k$ 个节点子集来作为 anchor-sets，然后在前向过程中学习非线性的聚合模式来结合节点属性特征和加权节点和 anchor-sets 间的距离。至于如何选择 $k$ , 文中提到 Bourgain theorem 来决定 $k=O(log^2 n)$ 。

算法模型

P-GNN 的模型架构如下图所示：

$k$ 个不同大小的anchor-sets $S_i$
消息计算函数 $F$ 结合两个顶点特征和其距离。
矩阵 $M$ 表示 anchor-sets 消息，第 $i$ 行表示根据 $F$ 计算的一个 anchor-ser $\mathcal{M}_i$ 消息。
可训练的聚合函数 $AGG_M, AGG_S$ , $ADD_S$ 聚合 anchor sets 中节点的特征信息。
可训练的参数 $w$ 将消息矩阵 $M$ 映射到低维的向量空间 $\mathbf{z} \in \mathbb{R}^{k}$ 。

整个框架的算法如下图所示：

上面有几点需要说明一下：

$k$ 个 anchor sets 如何选择?
文中用了一堆理论证明 $k$ 的大小如何定义，核心是 Bourgain theorem 理论，这里直接记录结果。
$k=c\log^2 n \\\\ S_{i,j} \subset \mathcal{V},i=1,\cdots,\log n ,j=1,\cdots,c\log n$
其中每个节点的采样概率为： $\frac{1}{2^i}$ 。
消息计算函数 $F$ 如何定义？
需要计算两个节点间的距离，由于最短路径计算的时间复杂性太高，因此文中提出了 $q-hop$ 最短路径的计算方法：
$d_{s p}^{q}(v, u)=\left\{\begin{array}{ll} d_{s p}(v, u), & \text { if } d_{s p}(v, u) \leq q \\\\ \infty, & \text { otherwise } \end{array}\right.$
将节点间的距离转化为特征的相似性的计算方法：
$s(v, u)=\frac{1}{d_{s p}^{q}(v, u)+1}$
最终的计算函数 $F$ 定义为：
$F\left(v, u, \mathbf{h}_{v}, \mathbf{h}_{u}\right)=s(v, u) \operatorname{CONCAT}\left(\mathbf{h}_{v}, \mathbf{h}_{u}\right)$
消息聚集函数 $AGG_M, AGG_S$ 如何定义？
特征聚合的方式有很多， $MEAN, MIN, MAX, SUM$ 等等。论文中采用的是 $MEAN$ 聚合方式就可以达到很好的效果。