论文《Bilinear Graph Neural Network with Neighbor Interactions》阅读

论文概况

作者提出了一个利用邻接节点的互动情况用于聚合（aggregate）结点feature作为目标节点embedding的图神经网络模型BGNN。这篇文章发表在IJCAI 2020上，文章是图神经网络的改进版本，实验使用baseline方法GCN的semi-supervised node classification实验。

论文地址：BGNN论文
代码地址：BGNN代码

Introduction

本文题目：Bilinear Graph Neural Network with Neighbor Interactions。
bilinear是指使用了双向互动，对于目标结点，不止是将邻接节点的embedding进行加权求和汇聚到目标结点这一种方式；而是将邻接节点（包括目标结点）的互动情况进行计算并汇聚到目标节点上去。
上文的互动情况，也是题目中的interaction，是指使用element-wise product表现，并将所有邻接节点的product进行加和。

Bilinear Graph Neural Network

Bilinear Aggregator

这里介绍了双线性的具体内容。

具体的，见下式：
B A ( { h i } i ∈ N ~ v ) = 1 b v ∑ i ∈ N ~ v    ∑ j ∈ N ~ v & i < j    h i W ⊙ h j W (2) BA(\{\bf{h}_i\}_{i\in \tilde{\mathcal{N}} _v }) = \frac{1}{b_v} \sum \limits _{i \in \tilde{\mathcal{N}} _v } \ \ \sum \limits _{j \in \tilde{\mathcal{N}} _v \& i < j } \ \ \bf{h}_i W \odot \bf{h}_j W \tag{2} BA({hi​}i∈N~v​​)=bv​1​i∈N~v​∑​  j∈N~v​&i<j∑​  hi​W⊙hj​W(2)

上式中限定 $i<j$ 的原因在于避免重复计算，利用这点即可给出矩阵计算形式，并证明算法的线性复杂度，如下所示：
B A ( { h i } i ∈ N ~ v ) = 1 b v ∑ i ∈ N ~ v    ∑ j ∈ N ~ v & i < j    h i W ⊙ h j W = 1 2 b v ( ∑ i ∈ N ~ v    ∑ j ∈ N ~ v    s i ⊙ s j − ∑ i ∈ N ~ v s i ⊙ s i ) = 1 2 b v ( ( ∑ i ∈ N ~ v s i ) 2 − ∑ i ∈ N ~ v s i 2 ) (3)

$$\begin{aligned} BA(\{\bf{h}_i\}_{i\in \tilde{\mathcal{N}} _v }) = \frac{1}{b_v} \sum \limits _{i \in \tilde{\mathcal{N}} _v } \ \ \sum \limits _{j \in \tilde{\mathcal{N}} _v \& i < j } \ \ \bf{h}_i W \odot \bf{h}_j W \\= \frac{1}{2b_v} (\sum \limits _{i \in \tilde{\mathcal{N}} _v } \ \ \sum \limits _{j \in \tilde{\mathcal{N}} _v} \ \ \bf{s}_i \odot \bf{s}_j - \sum \limits _{i \in \tilde{\mathcal{N}} _v } \bf{s}_i \odot \bf{s}_i ) \\ = \frac{1}{2b_v} ((\sum \limits _{i \in \tilde{\mathcal{N}} _v } \bf{s}_i )^2 - \sum \limits _{i \in \tilde{\mathcal{N}} _v } \bf{s}_i ^2 ) \tag{3} \end{aligned}$$ BA({hi​}i∈N~v​​)=bv​1​i∈N~v​∑​  j∈N~v​&i<j∑​  hi​W⊙hj​W=2bv​1​(i∈N~v​∑​  j∈N~v​∑​  si​⊙sj​−i∈N~v​∑​si​⊙si​)=2bv​1​((i∈N~v​∑​si​)2−i∈N~v​∑​si2​)​(3)

公式中 ${\mathbf{s}}_{\mathbf{i}}=\mathbf{W}{\mathbf{h}}_{\mathbf{i}}\in {\mathbb{R}}^{\mathbf{D}}$ 是为了表示直观。分析时间复杂度可以看到，对所有 ${\mathbf{s}}_{\mathbf{i}}$ 求和以及求平方都是 $\mathcal{O}(|{\tilde{\mathcal{N}}}_v|)$ 复杂度，即线性复杂度。

转置不变性证明

将上式矩阵化表示，如下：

$$BA(H,A)=\frac{1}{2}{\mathbf{B}}^{-1}((\tilde{\mathbf{A}}\mathbf{HW}{)}^2-\tilde{\mathbf{A}}(\mathbf{HW}{)}^2)\text{\hspace{1em}(4)}$$

这里需要注意的是这个平方符号指的是矩阵内部元素每个都进行平方的意思，是一个element-wise product符号。

作者为了证明转置不变性（具体哪个文献提出的不太清楚），使用了一个辅助的转置矩阵$P$，P具有以下性质：（1）$P^{T}P=I$，这个容易理解，转置矩阵行变换后列变换就换回去了；（2）对任意矩阵$M$，如果$PM$存在，则 $PM\odot PM=P(M\odot M)$，这个也容易理解，就是同一转置矩阵进行元素相乘，就等于矩阵先相乘再转置。

因此，作者对公式（4）进行了转置，有
$H$ 变成了 $PH$，另外，由于$\tilde{A}$和$\tilde{B}$ 是对称阵，所以转置后不变，也可以表示为左边行变换右边列变换的形式（就等于没有变换，参考性质2），因此可以有 $\tilde{A}$ 变成了 $P\tilde{A}{P}^T$， $\tilde{B}$ 变成了 $P\tilde{B}{P}^T$。将公式（4）中的各个变量都进行替换，可以得到

$$\begin{gathered} BA(PH,PA{P}^T)=\frac{1}{2}P{B}^{-1}{P}^T((P\tilde{A}{P}^{T}PHW{)}^2-P\tilde{A}{P}^T(PHW{)}^2) \\ =\frac{1}{2}P{B}^{-1}{P}^T((P\tilde{A}HW{)}^2-P\tilde{A}{P}^T(PHW{)}^2) \\ =\frac{1}{2}P{B}^{-1}{P}^T(P(\tilde{A}HW{)}^2-P\tilde{A}{P}^{T}P(HW{)}^2) \\ =\frac{1}{2}P{B}^{-1}{P}^{T}P((\tilde{A}HW{)}^2-\tilde{A}{P}^{T}P(HW{)}^2) \\ =\frac{1}{2}P{B}^{-1}((\tilde{A}HW{)}^2-\tilde{A}(HW{)}^2) \\ =P\cdot BA(H,A) \end{gathered}$$

上面的步骤是在文章的基础上，将每一步的详细过程写了出来方便读者理解。主要就是将$P^{T}P=I$进行消减，同时注意将element-wise平方中的P提取出来，就可以得到结果。从上面的公式可以看到，权重 $W$ 没有变换，除此以外，将邻接矩阵进行置换（同时包括度矩阵，即$B$），并进行BA运算，得到的结果也是置换过的，即相对于每一行，对应每个节点，计算结果是没有变化的。这一结果就证明了置换不变的性质。

BGNN模型介绍

作者并不是单一使用节点之间的bilinear interaction作为聚合方式，而是结合常用的AGG（加权求和）方式和本文提出的BA（双线性聚合bilinear aggregation）方式两种方法，并使用一个超参数 $\alpha$ 进行权衡。具体的，如下所示：
$$\begin{gathered} H^{(k)}=BGNN(H^{(k-1)},A) \\ =(1-\alpha )\cdot AGG(H^{(k-1)},A)+\alpha \cdot BA(H^{(k-1)},A) \end{gathered}$$

模型架构如下图所示：

具体到多层BGNN的使用中，作者又引入了一个超参系数$\beta$，这个系数是为了平衡多层之间节点的互动情况，越大则代表互动情况影响力越大。

论文总结

这篇文章在GNN的基础上加入了bilinear的互动，提出了BGNN模型。本文对于转置不变性的证明非常充实。

缺点是本文提出的BGNN不适用于大型的图，因为无法进行Batch Learning。