一、JK-Net [2018]

《Representation Learning on Graphs with Jumping Knowledge Networks》

1. 图是一种普遍存在的结构，广泛出现在数据分析问题中。现实世界的图（如社交网络、金融网络、生物网络和引文网络）代表了重要的丰富的信息，这些信息无法仅仅从单个实体中看到（如一个人所在的社区、一个分子的功能角色、以及企业资产对外部冲击的敏感性）。因此，图中节点的 representation learning 旨在从节点及其邻域中抽取高级特征，并已被证明对许多 application 非常有用，如节点分类、节点聚类、以及链接预测。

   最近的工作集中在 node representation 的深度学习方法上。其中大多数深度学习方法遵循邻域聚合（也称作消息传递 message passing ）方案。这些模型迭代式地聚合每个节点的 hidden feature 及其周围邻域节点的 hidden feature，从而作为该节点的新的 hidden feature。其中每一次迭代都由一层神经网络来表示。理论上讲，执行 $k$$k$ 次迭代从而得到节点 $v_i$$v_i$ 的 hidden feature 的聚合过程，利用了以节点 $v_i$$v_i$ 为根节点的一棵高度为 $k$$k$ 的子树结构。已经证明这种方案是 Weisfeiler-Lehman 图同构测试（graph isomorphism test）的推广，并且能够同时学习图的拓扑结构以及邻域节点特征的分布。

   但是，这种聚合方式可能会产生出人意料的结果。例如，已经观察到 GCN 的深度为 2 时达到最佳性能；当采用更深网络时，虽然理论上每个节点能够访问更大范围的信息，但是GCN 的效果反而更差。在计算机视觉领域中，这种现象称作学习退化 （degradation），该问题可以通过残差连接来解决，这极大地帮助了深度模型的训练。但是在 GCN 中，在很多数据集（如，引文网络）上即使采用了残差连接，多层 GCN 的效果仍然比不过 2 层 GCN 。

   基于上述观察，论文 《Representation Learning on Graphs with Jumping Knowledge Networks》 解决了两个问题：

   • 首先，论文研究了邻域聚合方案的特点及其局限性。

   • 其次，基于这种分析，论文提出了jumping knowledge network: JK-Net 框架。该框架和现有的模型不同，JK-Net 为每个节点灵活地利用不同的邻域范围，从而实现自适应的结构感知表示 （structure-aware representation）。

   通过大量实验，论文证明了 JK-Net 达到了 SOTA 性能。另外，将 JK-Net 框架和 GCN/GraphSage/GAT 等模型结合，可以持续改善这些模型的性能。

2. 模型分析：为评估不同邻域聚合方案的行为，论文分析了节点 $v_i$$v_i$ 的representation 依赖的邻域范围。论文通过节点的影响力分布 （the influence distribution ）（即不同邻域节点对于 $v_i$$v_i$ 的representation 的贡献的分布）来刻画这个邻域范围。邻域范围隐式的编码了 $v_i$$v_i$ 的 nearest neighbors 的先验假设。

   具体而言，我们将看到这个邻域范围严重受到图结构的影响。因此引发了一个疑问：是否所有的节点 $v_i\in V$$v_i\in V$ 都适用于同一个邻域范围（即，“一刀切”）？尤其是当图中存在各种各样类型的子图时（如，tree-like 子图、expander-like 子图）。

   进一步地，论文形式化地分析将 $v_i$$v_i$ 的影响力分布和从节点 $v_i$$v_i$ 开始的随机游走扩散联系在一起。这是一个易于理解的现象，因为影响力分布是图结构和特征值（eigenvalue）的函数。

3. 改变的局部性（changing locality）：为了说明图结构的影响和重要性，请回想一下许多现实世界的图具有强烈局部变化的结构（locally strongly varying structure）。在生物网络和引文网络中，大多数节点几乎没有连接，而一些节点 （hub）连接到许多其它节点。社交网络和 web 网络通常由 expander-like 部分组成，它们分别代表 well-connected 实体和小社区 （small community）。

   除了节点特征之外，这种子图结构对于邻域聚合结果也有非常大的影响。邻域范围扩张的速度（或者叫影响半径的增长）通过随机游走的 mixing time 来刻画（即：从节点 $v_i$$v_i$ 的随机游走收敛到平稳分布所需要的时间）。这个时间在不同结构的子图上差异巨大。因此，相同数量的迭代可能导致差异很大的局部影响力分布。

   例如考虑如下 GooglePlus 的社交网络，该图说明了从正方形节点开始的随机游走的扩散（随机游走的扩散也代表了影响力分布的扩散）。可以看到：不同结构的子图带来不同的邻域范围。

   • 图 a 中，来自核心区域内节点的随机游走很快就覆盖了几乎整个图（随机游走覆盖的节点以绿色表示）。

   • 图 b 中，来自tree 形区域节点的随机游走经过相同的 step 之后，仅覆盖图的一小部分（随机游走覆盖的节点以绿色表示）。

   • 图 c 中，来自 tree 形区域节点使用更长的 step 之后达到了核心区域，并且影响力突然快速扩散。

   在graph representation 模型中，这种随机游走的扩散转换为影响力分布。这表明：在同一个图中，相同数量的随机游走 step 可以导致非常不同的效果。因此我们需要根据具体的图，同时结合较大的邻域范围和较小的邻域范围：

   • 太大的邻域范围可能会导致过度平滑，从而丢失局部信息。

   • 太小的邻域范围可能信息不足，从而不足以支撑准确的预测。

   

4. JK network：上述观察提出一个问题：能否有可能对不同的图和不同的节点自适应地调整邻域范围。为此论文 《Representation Learning on Graphs with Jumping Knowledge Networks》提出了 JK-Net 框架，该框架在网络最后一层选择性地组合不同邻域范围，从而自适应地学习不同邻域的局部性（locality）。如，将不同邻域范围 jump 到最后一层，因此这个网络被称作 Jumping Knowledge Networks: JK-Nets。

5. 相关工作：谱图卷积神经网络 （spectral graph convolutional neural network）使用图拉普拉斯特征向量作为傅里叶基，从而在图上应用卷积。与诸如邻域聚合之类的空间方法（spatial approach）相比，谱方法（spectral method）的一个主要缺点是：需要提前知道图拉普拉斯矩阵（是 transductive 的）。因此，谱方法无法推广到 unseen 的图。

1.1 模型

1. 定义图 $G=(V,E)$$G=(V,E)$ ，其中 $V=\{v_1,\cdots ,v_n\}$$V=\{v_1,\cdots,v_n\}$ 为节点集合，$E$$E$ 为边集合。每个节点 $v\in V$$v\in V$ 关联一个节点特征向量 ${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_v\in \mathbb R^{d_f}$ ，$d_f$$d_f$ 为特征向量的维度。

   定义图 $\tilde{G}=(V,\tilde{E})$$\tilde G = (V,\tilde E)$ 为图 $G$$G$ 每个节点 $v$$v$ 上添加一个自连接得到的图，其中 $\tilde{E}=E\cup \{(v_i,v_i)\mid v_i\in V\}$$\tilde E = E\cup \{(v_i,v_i)\mid v_i\in V\}$ 。

   假设基于消息传递的模型有 $L$$L$ 层，第 $l$$l$ 层学到的节点 $v$$v$ 的 hidden feature 为 ${\overrightarrow{\mathbf{h}}}_v^{(l)}\in {\mathbb{R}}^{d_h}$$\mathbf{\vec h}_v^{(l)}\in \mathbb R^{d_h}$ ，其中 $d_h$$d_h$ 为 hidden feature 的维度。为讨论方便，我们选择所有层的 hidden feature 维度都相等。另外，我们记 ${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v$ 。

   定义节点 $v$$v$ 的邻域 ${\mathcal{N}}_v=\{u\in V\mid (v,u)\in E\}$$\mathcal N_v = \{u\in V\mid (v,u)\in E\}$ 为与节点 $v$$v$ 直接相连的节点集合。定义 $\tilde{G}$$\tilde G$ 中节点 $v$$v$ 的邻域 ${\tilde{\mathcal{N}}}_v={\mathcal{N}}_v\cup \{v\}$$\tilde{\mathcal N}_v = \mathcal N_v\cup \{v\}$ ，它包含了节点 $v$$v$ 自身。

   则典型的消息传递模型可以描述为：对于第 $l\in \{1,2,\cdots ,L\}$$l\in \{1,2,\cdots,L\}$ 层，每个节点 $v\in V$$v\in V$ 的 hidden feature 更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\sigma ({\mathbf{W}}_l\cdot \text{AGG}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(l-1)},\mathrm{\forall }u\in {\tilde{\mathcal{N}}}_v\}\right))$$

   其中：

   • AGG 为聚合函数，不同的模型采用不同的聚合函数。

   • ${\mathbf{W}}_l$$\mathbf W_l$ 为待学习的第 $l$$l$ 层的权重矩阵，它在所有节点之间共享。

   • $\sigma (\cdot )$$\sigma(\cdot)$ 为一个非线性激活函数。

2. GCN 图卷积神经网络（《Semi-supervised classification with graph convolutional networks》）hidden feature 更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\text{relu}\left({\mathbf{W}}_l\sum _{u\in {\tilde{\mathcal{N}}}_v}\frac{{\overrightarrow{\mathbf{h}}}_u^{(l-1)}}{\sqrt{\text{deg}(v)\times \text{deg}(u)}}\right)$$

   其中 $\text{deg}(v)$$\text{deg}(v)$ 为节点 $v$$v$ 在图 $G$$G$ 中的 degree。

3. 《Inductive representation learning on large graphs》 推导出一个在 inductive learing 中的 GCN 变体（即，GraphSAGE ），其hidden feature 更新方程为：

   $${\overrightarrow{\mathbf{h}}}_v^{(l)}=\text{relu}\left({\mathbf{W}}_l\frac{1}{\widetilde{\text{deg}}(v)}\sum _{u\in {\tilde{\mathcal{N}}}_v}{\overrightarrow{\mathbf{h}}}_u^{(l-1)}\right)$$

   其中 $\widetilde{\text{deg}}(v)$$\widetilde{\text{deg}}(v)$ 为节点 $v$$v$ 在 $\tilde{G}$$\tilde G$ 中的 degree 。

4. Neighborhood Aggregation with Skip Connections：最近的一些模型并没有同时聚合节点及其邻域，而是先聚合邻域，然后将得到的neighborhood representation和节点的上一层representation 相结合。其hidden feature 更新方程为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)}=\sigma ({\mathbf{W}}_l\cdot {\text{AGG}}_{\mathcal{N}}\left(\{{\overrightarrow{\mathbf{h}}}_u^{(l-1)},\mathrm{\forall }u\in {\mathcal{N}}_v\}\right))\\ {\overrightarrow{\mathbf{h}}}_v^{(l)}=\text{COMBINE}({\overrightarrow{\mathbf{h}}}_v^{(l-1)},{\overrightarrow{\mathbf{h}}}_{{\mathcal{N}}_v}^{(l)})\end{array}$$

   其中 ${\text{AGG}}_{\mathcal{N}}$$\text{AGG}_\mathcal N$ 和 $\text{COMBINE}$$\text{COMBINE}$ 函数由具体的模型定义。

   在这种范式中，COMBINE 函数是关键，可以将其视为跨层的跳跃连接（skip connection）。 对于COMBINE 的选择，GraphSAGE 在特征转换之后直接进行拼接，Column Network 对二者进行插值，Gated GCN 使用 GRU 单元。

   但是，该跳跃连接是 input-specific 的，而不是 output-specific 的。考虑某个节点 $v$$v$ ，假设在第 $l$$l$ 层计算 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 时使用了 skip 。则后续更高层 $l+j,j>1$$l+j,j\gt 1$ 中，对于所有依赖于节点 $v$$v$ 的其它节点 $u$$u$ ，计算 ${\overrightarrow{\mathbf{h}}}_u^{(l+j)}$$\mathbf{\vec h}_u^{(l+ j)}$ 都隐式的使用了这个 skip 。我们无法做出这样的选择：对于第 $l+j_1$$l+j_1$ 层使用 skip、对于第 $l+j_2$$l+j_2$ 层不使用 skip。即跳跃连接是由输入决定，而不是由输出决定。因此，跳跃连接无法自适应地独立调整 final-layer representation 的邻域大小。

5. Neighborhood Aggregation with Directional Biases：最近有些模型没有平等地看到邻域节点，而是对“重要”的邻居给与更大的权重。可以将这类方法视为 directional bias 的邻域聚合，因为节点受到某些方向的影响要大于其它方向。

   例如：GAT 和 VAIN 通过 attention 机制选择重要的邻居，GraphSAGE 的 max-pooling 隐式地选择重要的邻居。

   这个研究方向和我们的研究方向正交。因为它调整的是邻域扩张的方向，而我们研究的是调整邻域扩张的范围。我们的方法可以和这些模型相结合，从而增加模型的表达能力。

   在下文中，我们证明了 JK-Net 框架不仅适用于简单的邻域聚合模型（GCN），还适用于跳跃连接 （GraphSAGE）和 directional bias（GAT ）。

1.1.1 影响力分布

1. 我们首先利用 《Understanding black-box predictions via influence functions》 中的敏感性分析（sensitivity analysis） 以及影响力函数的思想，它们衡量了单个训练样本对于参数的影响。给定节点 $v$$v$ ，我们研究都有哪些其它节点会影响节点 $v$$v$ 的 representation。从这个影响范围，我们可以了解到节点 $v$$v$ 获取有效信息的邻域范围大小。

   我们通过衡量节点 $y$$y$ 的输入特征的变化对节点 $x$$x$ 的 final representation 的影响程度，从而测量节点 $x$$x$ 对节点 $y$$y$ 的敏感度（或者节点 $y$$y$ 对节点 $x$$x$ 的影响）。对于任何节点 $x$$x$ ，影响力分布捕获了所有其它节点对节点 $x$$x$ 的相对影响。

2. 影响力得分和分布的定义：给定一个图 $G=(V,E)$$G=(V,E)$ ，令 ${\overrightarrow{\mathbf{h}}}_x^{(0)}$$\mathbf{\vec h}_x^{(0)}$ 为节点 $x$$x$ 的输入特征向量，${\overrightarrow{\mathbf{h}}}_x^{(l)}$$\mathbf{\vec h}_x^{(l)}$ 为节点 $x$$x$ 在网络第 $l$$l$ 层的 hidden feature， ${\overrightarrow{\mathbf{h}}}_x^{(L)}$$\mathbf{\vec h}_x^{(L)}$ 为节点 $x$$x$ 的final representation 。

   定义雅可比矩阵：

   $$\begin{array}{c}\mathbf{J}(x,y)=\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]=\left[\begin{array}{cccc}\frac{\partial h_{x,1}^{(L)}}{\partial h_{y,1}^{(0)}}& \frac{\partial h_{x,2}^{(L)}}{\partial h_{y,1}^{(0)}}& \cdots & \frac{\partial h_{x,d_h}^{(L)}}{\partial h_{y,1}^{(0)}}\\ \frac{\partial h_{x,1}^{(L)}}{\partial h_{y,2}^{(0)}}& \frac{\partial h_{x,2}^{(L)}}{\partial h_{y,2}^{(0)}}& \cdots & \frac{\partial h_{x,d_h}^{(L)}}{\partial h_{y,2}^{(0)}}\\ ⋮& ⋮& \ddots & ⋮\\ \frac{\partial h_{x,1}^{(L)}}{\partial h_{y,d_f}^{(0)}}& \frac{\partial h_{x,2}^{(L)}}{\partial h_{y,d_f}^{(0)}}& \cdots & \frac{\partial h_{x,d_h}^{(L)}}{\partial h_{y,d_f}^{(0)}}\end{array}\right]\end{array}$$

   定义节点 $y$$y$ 对节点 $x$$x$ 的影响力得分（influence score）为：雅可比矩阵 $\mathbf{J}(x,y)$$\mathbf J(x,y)$ 的各元素的绝对值之和：

   $$I(x,y)=\sum _{s=1}^{d_f}\sum _{t=1}^{d_h}|J(x,y{)}_{s,t}|$$

   其中：$J(x,y{)}_{s,t}$$J(x,y)_{s,t}$ 为雅克比矩阵 $\mathbf{J}(x,y)$$\mathbf J(x,y)$ 的第 $s$$s$ 行第 $t$$t$ 列。

   定义节点 $x$$x$ 的影响力分布（influence distribution ）为：所有节点对于节点 $x$$x$ 的影响力得分的归一化分布：

   $$\begin{array}{c}{I}_x(y)=\frac{I(x,y)}{\sum _{z\in V}I(x,z)}\\ {\overrightarrow{\mathbf{I}}}_x=(I_x(v_1),\cdots ,I_x(v_n){)}^{\mathrm{\top }}\end{array}$$

   对于任何节点 $x$$x$ ，影响力分布 ${\overrightarrow{\mathbf{I}}}_x$$\mathbf{\vec I}_x$ 捕获了图中所有节点对它的 representation 的影响。

3. 考虑在 $\tilde{G}$$\tilde G$ 上从节点 $v_0$$v_0$ 开始的随机游走。假设在第 $t$$t$ 步随机游走到节点 $v_t$$v_t$ ，则第 $t+1$$t+1$ 步均匀随机地移动到 $v_t$$v_t$ 的任何邻居节点（包括 $v_t$$v_t$ 自身）。因此，节点 $v_0$$v_0$ 开始的随机游走的分布为：

   $$P_t(i)=Prob(v_t=i)$$

   其物理意义为：随机游走第 $t$$t$ 步到达节点 $i$$i$ 的概率。

   类似的定义适用于具有非均匀转移概率的随机游走。

   随机游走分布的一个重要属性是：如果图是非二部图（non-bipartite），则它随着 $t$$t$ 的增加而扩散 spread ，并收敛到极限分布。收敛速度取决于以节点 $v_0$$v_0$ 开始的子图结构，并受到随机游走转移概率矩阵的spectral gap （或者 conductance） 的限制（bounded） 。

1.1.2 模型分析

1. 不同聚合模型和节点的影响力分布可以深入了解各个 representation 所捕获的信息。以下结果表明：常见的聚合方法的影响力分布和随机游走分布密切相关。这些观察暗示了我们接下来要讨论的优缺点。

   假设 relu 在零点的导数也是零（实际上 relu 函数在零点不可导），则我们得到 GCN 和随机游走之间的关系：

   定理：给定一个 $L$$L$ 层的 GCN 变体，假设以相同的成功率 $\rho$$\rho$ 激活了模型计算图中的所有路径。则任意节点 $x$$x$ 的影响力分布 ${\overrightarrow{\mathbf{I}}}_x$$\mathbf{\vec I}_x$ 等价于（在期望上）在 $\tilde{G}$$\tilde G$ 上从节点 $x$$x$ 开始的 $L$$L$ 步的随机游走分布。

   证明：令 ${\overrightarrow{\mathbf{f}}}_x^{(l)}$$\mathbf{\vec f}_x^{(l)}$ 为 ${\overrightarrow{\mathbf{h}}}_x^{(l)}$$\mathbf{\vec h}_x^{(l)}$ 经过激活函数之前的值，即：

   $${\overrightarrow{\mathbf{f}}}_x^{(l)}={\mathbf{W}}_l\frac{1}{\widetilde{\text{deg}}(x)}\sum _{u\in {\tilde{\mathcal{N}}}_x}{\overrightarrow{\mathbf{h}}}_u^{(l-1)}$$

   则有：

   $$\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(l)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}=\frac{1}{\widetilde{\text{deg}}(x)}\cdot \text{diag}\left({\overrightarrow{\mathbf{1}}}_{{\overrightarrow{\mathbf{f}}}_x^{(l)}>0}\right)\cdot {\mathbf{W}}_l\cdot \sum _{u\in {\tilde{\mathcal{N}}}_x}\frac{\partial {\overrightarrow{\mathbf{h}}}_u^{(l-1)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}$$

   这里我们简化了 $\sigma (\cdot )$$\sigma(\cdot)$ 函数的梯度，认为：

   $$\begin{array}{c}\delta (x)=\frac{\partial \sigma (x)}{\partial x}=\{\begin{array}{ll}1,& x>0\\ 0,& x\le 0\end{array}\end{array}$$

   这里 $\text{diag}\left({\overrightarrow{\mathbf{1}}}_{{\overrightarrow{\mathbf{f}}}_x^{(l)}>0}\right)$$\text{diag}\left(\mathbf{\vec 1}_{\mathbf{\vec f}^{(l)}_x \gt 0}\right)$ 为对角矩阵：

   $$\begin{array}{c}\text{diag}\left({\overrightarrow{\mathbf{1}}}_{{\overrightarrow{\mathbf{f}}}_x^{(l)}>0}\right)=\left[\begin{array}{cccc}\delta (f_{x,1}^{(l)})& 0& \cdots & 0\\ 0& \delta (f_{x,2}^{(l)})& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & \delta (f_{x,d_h}^{(l)})\end{array}\right]\end{array}$$

   假设存在 $\mathrm{\Psi }$$\Psi$ 条从节点 $x$$x$ 到节点 $y$$y$ 的、长度为 $L+1$$L+1$ 的路径，其中第 $p$$p$ 条路径记作：

   $${\text{Path}}_p=(v_p^{(L)},v_p^{(L-1)},\cdots ,v_p^{(0)})$$

   其中 $v_p^{(L)}=x,v_p^{(0)}=y,v_p^{(l-1)}\in \tilde{\mathcal{N}}(v_p^{(l)})$$v_p^{(L)} = x, v_p^{(0)} = y, v_p^{(l-1)}\in \widetilde{\mathcal N}(v_p^{(l)})$ 。

   则根据链式法则，我们有：

   $$\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}=\sum _{p=1}^{\mathrm{\Psi }}{\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]}_p=\sum _{p=1}^{\mathrm{\Psi }}\prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}\cdot \text{diag}\left({\overrightarrow{\mathbf{1}}}_{{\overrightarrow{\mathbf{f}}}_{v_p^{(l)}}^{(l)}>0}\right)\cdot {\mathbf{W}}_l$$

   对于每条路径 ${\text{Path}}_p$$\text{Path}_p$ ，偏导数 ${\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]}_p$$\left[\frac{\partial \mathbf{\vec h}_x^{(L)}}{\partial \mathbf{\vec h}_y^{(0)}}\right]_p$ 定义了一个从节点 $x$$x$ 开始、节点 $y$$y$ 结束、长度为 $L$$L$ 的有向无环计算图。这个计算图的输入大小和 ${\mathbf{W}}_1$$\mathbf W_1$ 的大小相同。

   现在我们考虑偏导数 ${\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]}_p$$\left[\frac{\partial \mathbf{\vec h}_x^{(L)}}{\partial \mathbf{\vec h}_y^{(0)}}\right]_p$ 的第 $i$$i$ 行 $j$$j$ 列的元素，它表示输入神经元 $i$$i$ （ ${\overrightarrow{\mathbf{h}}}_y^{(0)}$$\mathbf{\vec h}_y^{(0)}$ 的第 $i$$i$ 项）对输出神经元 $j$$j$ （${\overrightarrow{\mathbf{h}}}_x^{(L)}$$\mathbf{\vec h}_x^{(L)}$ 的第 $j$$j$ 项）的影响。考虑到给定路径 ${\text{Path}}_p$$\text{Path}_p$ ，由于权重矩阵 ${\mathbf{W}}_l$$\mathbf W_l$ 的存在，从输入神经元 $i$$i$ 到输出神经元 $j$$j$ 存在很多更细粒度的路径。假设 $i\to j$$i\rightarrow j$ 神经元粒度的路径数量为 $\mathrm{\Phi }$$\Phi$ ，$w_q^{(l)}$$w_q^{(l)}$ 表示 ${\mathbf{W}}_l$$\mathbf W_l$ 中用于计算第 $q$$q$ 条神经元粒度的路径的项， $Z_q$$Z_q$ 表示第 $q$$q$ 条神经元粒度的路径是否激活，则有：

   $${\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]}_p^{(i,j)}=\prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}\sum _{q=1}^{\mathrm{\Phi }}{Z}_q{w}_q^{(l)}$$

   其中 $Z_q$$Z_q$ 刻画了 relu 激活函数在 ${\overrightarrow{\mathbf{f}}}_{v_p^{(l)}}^{(l)}$$\mathbf{\vec f}_{v_p^{(l)}}^{(l)}$ 的第 $q$$q$ 条路径上的结果：

   $$\begin{array}{c}{Z}_q=\{\begin{array}{ll}1,& \text{if path q is activated}\\ 0,& \text{else}\end{array}\end{array}$$

   假设 $Z$$Z$ 是伯努利分布的随机变量，对于所有路径 $q$$q$ 它的激活概率均为：$Pr(Z_q=1)=\rho$$Pr(Z_q= 1) = \rho$ 。则有：

   $$\mathbb{E}\left[{\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]}_p^{(i,j)}\right]=\rho \cdot \prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}{w}_q^{(l)}$$

   因此有：

   $$\mathbb{E}\left[\frac{\partial {\overrightarrow{\mathbf{h}}}_x^{(L)}}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\right]=\rho \cdot \prod _{l=L}^1{\mathbf{W}}_l\cdot \left(\sum _{p=1}^{\mathrm{\Psi }}\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}\right)$$

   另外，我们知道从节点 $x$$x$ 开始的随机游走在第 $L$$L$ 步到达 $y$$y$ 的概率，可以通过从节点 $x$$x$ 到 $y$$y$ 的所有长度为 $L$$L$ 的路径的概率之和来计算，即：

   $$\sum _{p=1}^{\mathrm{\Psi }}\prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}$$

   假设每一层的权重相同：${\mathbf{W}}_1=\cdots ={\mathbf{W}}_L=\mathbf{W}$$\mathbf W_1 = \cdots = \mathbf W_L = \mathbf W$ 。则影响力得分 $I(x,z)$$I(x,z)$ 对于任何节点 $z$$z$ 的期望，等于从节点 $x$$x$ 开始经过 $L$$L$ 步随机游走之后达到节点 $z$$z$ 的概率，乘以对所有 $z$$z$ 都相同的项 $\rho \mathbf{W}$$\rho \mathbf W$ 。因此：则任意节点 $x$$x$ 的影响力分布 ${\overrightarrow{\mathbf{I}}}_x$$\mathbf{\vec I}_x$ （归一化后）等价于（在期望上）在 $\tilde{G}$$\tilde G$ 上从节点 $x$$x$ 开始的 $L$$L$ 步的随机游走分布（归一化后）。

   这里的证明缺少了很多假设条件的说明，因此仅做参考。

2. 很容易修改上述定理的证明，从而得到 GCN 版本的近似结果。唯一区别在于，对于随机游走路径 ${\text{Path}}_p=(v_p^{(L)},v_p^{(L-1)},\cdots ,v_p^{(0)})$$\text{Path}_p = \left (v_p^{(L)}, v_p^{(L-1)} ,\cdots, v_p^{(0)} \right)$ ，其概率从 $\rho \prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}$$\rho \prod_{l=L}^1 \frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}$ 变为：

   $$\frac{\rho }{Q}\prod _{l=L}^1\frac{1}{\widetilde{\text{deg}}(v_p^{(l)})}\cdot {(\widetilde{\text{deg}}(x)\widetilde{\text{deg}}(y))}^{-1/2}$$

   其中 $Q$$Q$ 为归一化因子。因此二者的差异非常小，尤其是当 $x$$x$ 和 $y$$y$ 的 degree 接近时。

   类似地，我们也可以证明具有directional bias 的邻域聚合方案类似于有偏的随机游走分布。这可以通过替换掉上述定理中相应的概率得到证明。

3. 从经验上看，我们观察到即使假设有所简化，但是我们的理论分析仍然接近于实际情况。

   我们可视化了训练好的 GCN 的节点（正方形标记）的影响力分布的热力图，并与从同一节点开始的随机游走分布的热力图进行比较。较深的颜色对应于较高的影响力得分（或者较高的随机游走概率）。我们观察到 GCN 的影响力分布对应于随机游走分布。

   

   为显示跳跃连接的效果，下图可视化了一个带跳跃连接的 GCN 的节点的影响力分布热力图。同样地，我们发现带跳跃连接的 GCN 的节点影响力分布大致对应于 lazy 随机游走分布（lazy 表示每步随机游走都有较高的概率停留在当前节点，这里 lazy 因子为 0.4 ）。由于每次迭代过程中，所有节点的局部信息都以相似的概率进行保留，因此这无法适应不同高层节点的各种各样的需求。

   

4. 为进一步理解上述定理，以及相应邻域聚合算法的局限性，我们重新审视了下图中社交网络的学习场景。

   • 对于 expander（左图）内部开始的随机游走以 $O(\log |V|)$$O(\log |V|)$ 的 step 快速收敛到几乎均匀分布。根据前述的定理，在经过 $L=O(\log |V|)$$L= O(\log |V|)$ 层的聚合之后，每个节点的 representation 几乎受到 expander 中所有任何其它节点的影响。因此，每个节点的 representation 将代表 global graph，以至于过度平滑并带有节点自身的非常少的信息。

   • 对于 tree-like （右图）开始的随机游走，其收敛速度较慢。这使得经过消息传递模型的聚合之后，每个节点的 representation 保留了更多的局部信息。

   如果消息传递模型的层数 $L$$L$ 对所有节点都是统一固定的，那么模型很难在适应不同节点的影响力扩展速度以及影响力邻域大小这些差异。这使得难以为所有节点带来最佳的 representation。

   

5. 最后我们描述了热力图的相关细节，并提供了更多的可视化结果。

   热力图中的节点颜色对应于影响力分布得分或者随机游走分布的概率。颜色越浅则得分越低、颜色越深则得分越高。我们使用相同的颜色来表示得分（或者概率）超过 0.2 的情形，因为很少有节点的影响力得分（或概率）超过 0.2。对于得分（或概率）低于 0.001 的节点，我们没有在热力图中展示。

   • 首先我们比较 GCN 的影响力分布 vs 随机游走概率分布，以及带跳跃连接的 GCN 的影响力分布 vs 惰性随机游走概率分布。

     • 目标节点（被影响的节点或者随机游走的起始节点）标记为方块。

     • 数据集为 Cora citation 网络，模型分别为 2/4/6 层训练好的 GCN （或者带跳跃连接的 GCN Res）。我们使用 《Semi-supervised classification with graph convolutional networks》 描述的超参数来训练模型。

     • 影响力分布、随机游走分布根据前述的公式进行计算。

     • lazy 随机游走使用 lazy factor = 0.4 的随机游走，即每个节点在每次转移时有 0.4 的概率留在当前节点。

     • 注意：对于degree 特别大的节点，GCN 影响力和随机游走概率的颜色有所不同。这是因为我们这里的 GCN 是基于公式 ${\overrightarrow{\mathbf{h}}}_v^{(l)}=\text{relu}\left({\mathbf{W}}_l\sum _{u\in {\tilde{\mathcal{N}}}_v}\frac{{\overrightarrow{\mathbf{h}}}_u^{(l-1)}}{\sqrt{\text{deg}(v)\times \text{deg}(u)}}\right)$$\mathbf{\vec h}_v^{(l)} = \text{relu}\left(\mathbf W_l \sum_{u\in \tilde{\mathcal N}_v}\frac{\mathbf{\vec h}_u^{(l-1)}}{\sqrt{\text{deg}(v)\times \text{deg}(u)}}\right)$ ，其中 $v$$v$ 为目标节点。对于节点 $u$$u$ 其权重为 $\frac{1}{\sqrt{\text{deg}(v)\times \text{deg}(u)}}$$\frac{1}{\sqrt{\text{deg}(v)\times \text{deg}(u)}}$ 。相比较而言，随机游走概率分布中，节点 $u$$u$ 的权重为 $\frac{1}{\widetilde{\text{deg}}(v)}$$\frac{1}{\widetilde{\text{deg}}(v)}$ 。

       这使得在 GCN 影响力模型中，degree 更大的节点，其权重越低。

     

   • 然后我们考察了不同子结构，这些可视化结果进一步支持了前述的定理。

     • 下图中，使用 2 层的 GCN 模型分类错误，但是使用 3 层或 4 层 GCN 模型分类结果正确。

       当局部子图结构是 tree-like 时，如果仅仅使用 2 层 GCN （即查看 2-hop邻域），则抽取的信息不足以支撑其预测正确。因此，如果能够从 3-hop 邻域或 4-hop 邻域中抽取信息，则可以学到节点的局部邻域的更好表示。

       

     • 下图中，使用 3 或 4 层的 GCN 模型分类错误，但是使用 2 层 GCN 模型分类结果正确。这意味着从 3-hop 或 4-hop 邻域中抽取了太多无关的信息，从而使得节点无法学到正确的、有助于预测的 representation。

       • 在 expander 子结构中，随机游走覆盖的节点爆炸增长，3-hop 或者 4-hop 几乎覆盖了所有的节点。因此这种全局信息的 representation 对于每个节点的预测不是很理想。

       • 在 bridge-like 子结构中，抽取更远的节点的信息可能意味着从一个完全不同的 community 中获取信息，这可能意味着噪音并影响最终预测。

       

1.1.3 JK-Net

1. 前述观察提出了一个问题，即：在通用聚合方案中使用固定的、但是结构依赖的影响力半径大小是否能够实现所有任务中节点的best representation。

   • 如果选择的影响力半径过大，则可能导致过度平滑（oversmoothing）。

   • 如果选择的影响力半径国小，则可能导致聚合的信息量不足。

   为此，我们提出了两个简单有效的体系结构调整：跳跃连接 + 自适应选择的聚合机制。

   如下图所示为 JK-Net 的主要思想。

   • 和常见的邻域聚合网络一样，每一层都是通过聚合来自上一层的邻域来扩大影响力分布的范围。

   • 但是在最后一层，对于每个节点我们都从所有的这些 intermediate representation 中仔细挑选（jump 到最后一层），从而作为最终的节点 representation。

   由于这是针对每个节点独立完成的，因此模型可以根据需要为每个节点调整有效邻域范围，从而达到自适应的效果。

   可以理解为常规的 GCN 模型之上再添加一个聚合层。

   

2. JK-Net 也使用通用的层聚合机制，但是最终的节点 representation 使用自适应选择的聚合机制。这里我们探索三种主要的聚合方法，其它方法也可以在这里使用。

   令 ${\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}$$\mathbf{\vec h}^{(1)}_v,\cdots,\mathbf{\vec h}_v^{(L)}$ 为节点 $v$$v$ 的中间 representation （每个中间层代表了不同的影响力范围），并将它们 jump 到最后一层。

   • concatenation 聚合：直接拼接 $[{\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}]$$\left[\mathbf{\vec h}_v^{(1)},\cdots,\mathbf{\vec h}_v^{(L)}\right]$ 是最简单直接的方法。拼接之后可以执行一个线性变换 $\mathbf{W}[{\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}]$$\mathbf W \left[\mathbf{\vec h}_v^{(1)},\cdots,\mathbf{\vec h}_v^{(L)}\right]$ 。

     • 如果这个线性变换的权重 $\mathbf{W}$$\mathbf W$ 在所有节点之间共享，则这种方式不是 node-adaptive 的。

     • 如果这个线性变换的权重 $\mathbf{W}$$\mathbf W$ 对每个节点都有不同，从而以适应于整个数据集的方式聚合子图的特征，则这种方式是 node-adaptive 的。

     $\mathbf{W}$$\mathbf W$ 的权重共享通常应用在比较小的图或者结构比较规则的图上，因为这些图需要较少的自适应性。并且权重共享也有助于减少过拟合。

   • max-pooling 聚合：对 $\{{\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}\}$$\left\{ \mathbf{\vec h}^{(1)}_v,\cdots,\mathbf{\vec h}_v^{(L)}\right\}$ 执行逐元素的最大池化从而对每个特征维度feature coordinate选择信息最丰富的layer 。这种方式是自适应的，并且不会引入任何其它额外的学习参数。

   • LSTM-attention 聚合：注意力机制通过对每个节点 $v$$v$ 计算每层 $l$$l$ 上的注意力得分 $s_v^{(l)}$$s_v^{(l)}$ 来表示第 $l$$l$ 层学到的 representation 对于节点 $v$$v$ 的重要性。其中 $\sum _{l=1}^L{s}_v^{(l)}=1$$\sum_{l=1}^L s_v^{(l)} = 1$ 。最终节点 $v$$v$ 聚合后的 representation 为所有中间层的 representation 的加权平均：$\sum _l{s}_v^{(l)}{\overrightarrow{\mathbf{h}}}_v^{(l)}$$\sum_l s_v^{(l)} \mathbf{\vec h}_v^{(l)}$ 。

     对于 LSTM-attention ：

     • 先将 $\{{\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}\}$$\left\{ \mathbf{\vec h}^{(1)}_v,\cdots,\mathbf{\vec h}_v^{(L)} \right\}$ 作为一个双向 LSTM 的输入，并对每层 $l$$l$ 产生一个前向 LSTM hidden feature ${\overrightarrow{\mathbf{f}}}_v^{(l)}$$\mathbf{\vec f}_v^{(l)}$ 、一个后向 LSTM hidden feature ${\overrightarrow{\mathbf{b}}}_v^{(l)}$$\mathbf{\vec b}_v^{(l)}$ 。

     • 然后通过对层 $l$$l$ 的拼接 hidden feature $[{\overrightarrow{\mathbf{f}}}_v^{(l)},{\overrightarrow{\mathbf{b}}}_v^{(l)}]$$\left[\mathbf{\vec f}_v^{(l)},\mathbf{\vec b}_v^{(l)}\right]$ 进行线性映射，从而产生得到标量的重要性得分 $s_v^{(l)}$$s_v^{(l)}$ 。

     • 然后通过一个 softmax layer 应用到 ${\left\{s_v^{(l)}\right\}}_{l=1}^L$$\left\{s_v^{(l)}\right\}_{l=1}^L$ ，从而执行归一化，得到节点 $v$$v$ 在不同层上的 attention 得分。

     • 最后，将 $[{\overrightarrow{\mathbf{f}}}_v^{(l)},{\overrightarrow{\mathbf{b}}}_v^{(l)}]$$\left[\mathbf{\vec f}_v^{(l)},\mathbf{\vec b}_v^{(l)}\right]$ 按照 attention 得分的加权和，作为节点 $v$$v$ 的最终 final representation。

     LSTM-attention 是 node-adaptive 的，因为不同节点的 attention score 是不同的。实验表明，这种方法适用于大型复杂的图。由于其相对较高的复杂度，会导致在小型图上过拟合。

     另外，也可以将 LSTM 和最大池化相结合，即 LSTM max-pooling 。

     这种 LSTM 聚合的方式太复杂，可以简单地基于 $\{{\overrightarrow{\mathbf{h}}}_v^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}_v^{(L)}\}$$\left\{ \mathbf{\vec h}^{(1)}_v,\cdots,\mathbf{\vec h}_v^{(L)}\right\}$ 来计算一个注意系数，然后基于注意力来聚合。

   JK-Net 的实现比较简单，大量的篇幅都在形容理论。但是，这里的理论仅仅是解释问题，并没有解决问题。这里的 layer aggregation 方式既没有理论解释，也没有解决问题（针对不同的节点自适应地选择不同的邻域大小）：

   • 为什么如此聚合？论文未给出原因。

   • 不同的聚合方式代表了什么样的领域大小？这里也没有对应的物理解释。

3. 层聚合（layer aggregation）函数设计的关键思想是：在查看了所有中间层学到的 representation 之后，确定不同影响力范围内子图representation 的重要性，而不是对所有节点设置固定的、相同的影响力范围。

   假设 relu 在零点的导数也是零（实际上 relu 函数在零点不可导），则 layer-wise max-pooling 隐式地自适应地学习了不同节点的局部影响力。layer-wise attention 也是类似的。

   推论：假设计算图中相同长度的路径具有相同的激活概率 $\rho$$\rho$ ，则在一个采用了 layer-wise max-pooling 的 $L$$L$ 层 JK-Net 中，对于任意 $x,y\in V$$x,y\in V$ 的影响力得分 $I(x,y)$$I(x,y)$ 等价于 $\tilde{G}$$\tilde G$ 中从 $x$$x$ 到 $y$$y$ 的 $0,\cdots ,L$$0,\cdots,L$ 步随机游走分布的期望的加权和，加权系数依赖于 ${\overrightarrow{\mathbf{h}}}_x^{(l)}$$\mathbf{\vec h}_x^{(l)}$ 的值。

   证明：假设经过层聚合之后节点 $x$$x$ 的的 representation 为 ${\overrightarrow{\mathbf{h}}}_x^{(final)}$$\mathbf{\vec h}_x^{(final)}$，令 ${\left[{\overrightarrow{\mathbf{h}}}_x^{(final)}\right]}_i$$\left[\mathbf{\vec h}_x^{(final)}\right]_i$ 为它的第 $i$$i$ 项元素。对于任意节点 $y$$y$ ，我们有：

   $$I(x,y)=\sum _i{\Vert \frac{\partial {\left[{\overrightarrow{\mathbf{h}}}_x^{(final)}\right]}_i}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\Vert }_1=\sum _i{\Vert \frac{\partial {\left[{\overrightarrow{\mathbf{h}}}_x^{(j_i)}\right]}_i}{\partial {\overrightarrow{\mathbf{h}}}_y^{(0)}}\Vert }_1$$

   其中 $j_i=\arg \underset{l}{max}\left({\left[{\overrightarrow{\mathbf{h}}}_x^{(l)}\right]}_i\right)$$j_i = \arg\max_l \left(\left[\mathbf{\vec h}_x^{(l)}\right]_i\right)$ 。

   根据前述的定理，我们有：

   $$\mathbb{E}[I(x,y)]=\sum _l{c}_x^{(l)}\cdot z_l\cdot \mathbb{E}[I_x(y{)}^{(l)}]$$

   其中：

   • $I_x(y{)}^{(l)}$$I_x(y)^{(l)}$ 为从节点 $x$$x$ 到节点 $y$$y$ 经过 $l$$l$ 步随机游走的概率。

   • $z_l$$z_l$ 为归一化因子。

   • $c_x^{(l)}$$c_x^{(l)}$ 为 ${\overrightarrow{\mathbf{h}}}_x^{(l)}$$\mathbf{\vec h}_x^{(l)}$ 通过最大池化选择的项乘以某个比例系数。

4. 下图给出了采用 max-pooling 的 6 层 JK-Net 如何学习从而自适应引文网络上不同的子结构。

   • 在 tree-like 结构中，影响力仍然停留在节点所属的 small community 中。

     相反，在 6 层 GCN 模型中，影响力可能会深入到与当前节点不想关的其它 community 中；而如果使用更浅层的 GCN 模型，则影响力可能无法覆盖当前节点所在的 community 。

   • 对于 affiliate to hub （即 bridge-like）节点，它连接着不同的 community ，JK-Net 学会了对节点自身施加最大的影响，从而防止将其影响力扩散到不想关的community。

     GCN 模型不会捕捉到这种结构中节点自身的重要性，因为在几个随机游走step 之后，停留在 bridge-like 节点自身的概率很低。

   • 对于 hub 节点（即 expander），JK-Net 会在一个合理范围内将影响力扩散到相邻节点上。这是可以理解的，因为这些相邻节点和 hub 节点一样，都具有信息性。

   

5. JK-Net 的结构有些类似于 DenseNet，但是一个疑问是：是否可以像 DenseNet 一样在所有层之间都使用跳跃连接，而不仅仅是中间层和最后一层之间使用跳跃连接。如果在所有层之间都使用跨层的跳跃连接，并使用 layer-wise concatenation 聚合，则网络结构非常类似于 DenseNet 。

   从 graph theory 角度审视 DenseNet，图像对应于规则的 graph ，因此不会面临具有变化的子图结构的挑战。确实，正如我们在实验中看到的，使用 concatenation 聚合的模型在更规则的图（如图像、结构良好的社区）上表现良好。

   作为更通用的框架，JK-Net 接受更通用的 layer-wise 聚合模型，并在具有更复杂结构的图上实现更好的 structure-aware representation。

1.2 实验

1. 数据集：

   • 引文网络数据集 (Citeseer, Cora) ：数据集中每个节点代表一篇论文，特征为论文摘要的 bag-of-word，边代表论文之间的引用链接。节点类别为论文的主题。

   • Reddit 数据集：数据集中每个节点代表一个帖子，特征为帖子所有单词的 word vector 。如果某个用户同时在两个帖子上发表评论，则这两个帖子之间存在链接。节点类别为帖子所属的 community 。

   • PPI 数据集：数据集包含 24 个图，每个图对应于一个人体组织的蛋白质结构图。图中每个节点都有 positional gene sets, motif gene sets, immunological signatures 作为特征， gene ontology sets 作为标签。

     我们使用 20 个图进行训练、2 个图进行验证、剩余的 2 个图作为测试。

   数据集的统计信息如下表所示：

   

2. baseline 模型：GCN 、GraphSage、GAT 。

3. 实验配置：

   • 在 transductive 实验中，我们只允许访问单个图中的节点子集作为训练数据，剩余节点作为验证集/测试集。

     在 Citeseer, Cora, Reddit 数据集上的实验是 transductive 的。

   • 在 inductive 实验中，我们使用多个完整的图作为训练数据，并使用训练时未见过的、剩余的图作为验证集/测试集。

     在 PPI 数据集上的实验是 inductive 的。

4. 对于 Citeseer 和 Cora 数据集，我们选择GCN 作为 base 模型，因为在我们的数据集实验中它超越了 GAT 。

   我们分别选择 MaxPooling(JK-MaxPool)、Concatenation(JK-Concat)、LSTM-attention(JK-LSTM) 作为最终聚合层来构建 JK-Net。在进行最终聚合时，被聚合的 representation 除了图卷积中间层的 representation 之外，我们还考虑了第一个线性变换的 representation （可以理解为第零层的 representation）。最终预测是通过 final 聚合层的 representation 之上的全连接层来完成。

   我们将每个图的节点根据 60%:20%:20% 的比例随机拆分为训练集、验证集、测试集。对于每个模型，我们将层数从 1 到 6 ，针对验证集选择性能最佳的模型（及其对应的卷积层深度）。

   JK-Net 配置：

   • 学习率为 0.005 的 Adam 优化器。

   • 比例为0.5 的 dropout 。

   • 从 $\{16,32\}$$\{16,32\}$ 中选择 hidden feature 维度（Citeseer 为 16，Cora 为 32 ）。

   • 在模型参数上添加 0.0005 的 $L_2$$L_2$ 正则化。

   每组实验随机执行3 次并报告准确率 accuracy 的均值和标准差（标准差在括号中给出），实验结果如下表所示。可以看到：

   • 就预测准确率而言，JK-Net 优于 GAT 和 GCN 这两个baseline 。

   • 尽管 JK-Net 总体表现良好，但是没有始终如一的赢家，并且各个数据集上的性能略有不同。

   • 模型名字后面括号中的数字（1~6 之间）表示表现最佳的层数。仔细研究 Cora 的结果发现：

     • GCN 和 GAT 都在模型为2 层或 3 层时才能达到最佳准确率。这表明局部信息比全局信息更有助于分类。

       层数越浅，则表明邻域范围越小，则表明是局部信息。

     • JK-Net 在模型为 6 层上获得最佳性能，这表明全局信息和局部信息事实上都有助于提高性能。这就是 JK-Net 这类模型发挥价值的所在。

   • LSTM-attention 可能由于复杂性太高，从而不适用于此类小模型。因此 JK-LSTM 在这两个数据集中表现最差。

   

5. 对于 Reddit 数据集，由于它太大使得无法由 GCN 或 GAT 很好地处理。因此我们使用可扩展性更高的 GraphSAGE 作为 JK-Net 的 base 模型。

   在 GraphSAGE 中存在不同的节点聚合方式，我们分别使用 MeanPool 和 MaxPool 来执行节点聚合，然后跟一个线性变换。考虑到 JK-Net 最后一层的三种聚合模式MaxPooling、Concatenation、LSTM-attention ，两两组合得到 6 种 JK-Net 变体。

   我们采用和原始论文完全相同的 GraphSAGE 配置，其中模型由两层卷积层组成，hidden layer 维度为 128 维。我们使用学习率维 0.01 的 Adam 优化器，无权重衰减。

   实验结果如下表所示，评估指标维 Micro-F1 得分。结论：

   • 当采用 MaxPool 作为节点聚合器、Concat 作为层聚合器时，JK-Net 获得了最佳的 Micro-F1 得分。

     注意：原始的 GraphSAGE 在 Reddit 数据集上的表现已经足够好（Micro-F1 = 0.950），JK-Net 继续将错误率下降了 30% 。

   • Reddit 数据集中的社区是从表现良好的中等规模大小的社区中挑选而来，这是为了避免太大的社区中包含大量噪音、太小的社区是 tree-like 的。结果，该图比原始 Reddit 数据集更加规则，因此不会出现子图结构多样性的问题。

     在这种情况下，node-specific 自适应邻域选择所增加的灵活性可能不是那么重要，而 concatenation 的稳定特点开始发挥作用。这也是为什么 JK-Concat 效果较好的原因。

   

6. 对于 PPI 数据集，我们用它来证明自适应 JK-Net 的强大能力，该数据集的子图结构比 Reddit 数据集的子图结构更多样和复杂。

   我们将 GraphSAGE 和 GAT 都作为 JK-Net 的 base model。GraphSAGE 和 GAT 有很大的区别：GraphSAGE 基于采样，其中对每个节点的邻域采样固定的邻居数量；GAT 基于 attention，它考虑每个节点的所有邻居。这种差异在可扩展性和性能方面导致巨大的差距。鉴于 GraphSAGE 可以扩展到更大的图，因此评估 JK-Net 在 GraphSAGE 上的提升显得更有价值。但是我们的实验在二者上都进行。我们的评估指标为 Micro-F1 得分。

   • 对于 GraphSAGE，我们遵循 Reddit 实验中的配置，只是在可能的情况下使用 3 层网络，并训练 10 到 30 个 epoch。带有 * 的模型采用2 层（由于 GPU 内存限制），其它模型采用 3 层。作为对比，采用两层的 GraphSAGE 性能为 0.6 （未在表中给出）。

     实验结果见下表。

     

   • 对于 GAT 及其 JK-Net 变体，我们使用两层或三层网络，其中有 4 个 attention head，每个 head 有 256 维（共 1024 维）。最后一个预测层有 6 个 attention head，每个head 有 121 维。我们将这 6 个 head 执行均值池化，并灌入到 sigmoid 激活函数。我们在中间 attention 层之间引入跳跃链接。

     所有这些模型都使用学习率为 0.005 的 Adam 优化器，并使用 batch size = 2 的 mini-batch 训练。

     我们的 baseline 为 GAT 和 MLP 模型，网络层数从 2,3 之间选择。由于 GPU 内存限制，JK-Dense-Concat 和 JK-Dense-LSTM 的层数为 2 。

     实验结果见下表。

     

   • 结论：

     • 带有 LSTM-attention 聚合器的JK-Net 超越了具有 concatenation 聚合器的非自适应性 JK-Net 模型，以及 GraphSAGE/GAT/MLP 等 baseline 模型。

     • 在训练 30 个 epoch 之后，JK-LSTM 在 Micro-F1 得分上比 GraphSAGE 高出 0.128（绝对提升）。

     • 结构感知的节点自适应模型在 PPI 这类具有不同结构的复杂图上特别有效。