GNN（续）

十四、GCMC[2017]

1. 随着电商平台和社交媒体平台的爆炸式增长，推荐算法已经成为很多企业不可或缺的工具。通常而言，推荐算法有两个主流方向：基于内容的推荐系统、基于协同过滤的推荐系统。

   • 基于内容的推荐系统使用 user 和 item 的内容信息来进行推荐，如用户的职业、item 的类型。
   • 基于协同过滤的推荐使用 user-item 交互数据（如购买、评分等）来进行推荐。

   论文 《Graph Convolutional Matrix Completion》 将矩阵补全问题视为一个图的链接预测问题：协同过滤中的交互数据可以由用户节点和 item 节点之间的二部图来表示，观察到的评分/购买由链接来表示。内容信息自然地以节点特征的形式包含在这个框架中。评分预测问题变为预测 user-item 二部图中的 labeled link 。

   论文提出了图卷积矩阵补全 graph convolutional matrix completion: GCMC：一种 graph-based 的自编码器框架用于矩阵补全，它建立在图上深度学习的最新进展的基础上。自编码器 auto-encoder 通过在二部图上消息传递的形式来产生 user latent feature 和 item latent feature 。这些潜在 user representation 和 item representation 用于通过双线性解码器重建评分链接rating link。

   当有额外的辅助信息side information 可用时，将矩阵补全问题视为二部图上的链接预测问题带来的好处尤为明显。将辅助信息和交互数据结合在一起可以有效缓解冷启动问题。论文证明了所提出的图自编码器模型有效地结合了交互数据和辅助信息。

2. 相关工作：

   • 自编码器auto-encoder：user-based 或 item-based 自编码器是最近一类 state-of-the-art 协同过滤模型，可以视为我们的图自编码器模型的一个特例，其中仅考虑了 user embedding 或仅考虑了 item embedding 。

     • 《Autorec: Auto-encoders meet collaborative filtering》 是第一个这样的模型，其中 user （或 item）部分观察到的评分向量 rating vector 通过编码器层 encoder layer 投影到潜在空间，并使用具有均方重构误差损失mean squared reconstruction error loss 的解码器层 decoder layer 进行重构。

     • 《A neural autoregressive approach to collaborative filtering》 提出的 CF-NADE 算法可以被认为是上述自编码器架构的一个特例。在 user-based 的设置中，消息仅从 item 传递给user；而在 item-based 的设置中，消息仅从 user 传递给 item 。

       我们的图自编码器同时考虑了 item 传递给 user ，以及 user 传递给 item 。

       注意，与我们的模型相比，CF-NADE 给未评分的 item 在编码器中被分配了默认评分 3 ，从而创建了一个全连接的交互图 interaction graph 。CF-NADE 对节点进行随机排序，并通过随机切割 random cut 将传入消息划分为两组，并仅保留其中一组。因此，该模型可以看做是一个降噪自编码器，其中在每次迭代中随机丢弃输入空间的一部分。

       我们的模型仅考虑观测的评分，因此不是全连接的。

   • 分解模型：很多流行的协同过滤算法都是基于矩阵分解 matrix factorization: MF 模型，这种方式假设评分矩阵可以很好滴近似为低秩矩阵：

     $$\mathbf{M}\simeq \mathbf{U}{\mathbf{V}}^{\mathrm{\top }}$$

     其中：

     • $\mathbf{U}\in {\mathbb{R}}^{|\mathbb{U}|\times d}$$\mathbf U\in \mathbb R^{|\mathbb U|\times d}$ 表示用户 embedding 矩阵，每一行代表一个用户的 user embedding 向量，即user latent feature representation 。
     • $\mathbf{V}\in {\mathbb{R}}^{|\mathbb{V}|\times d}$$\mathbf V\in \mathbb R^{|\mathbb V|\times d}$ 表示 item embedding 矩阵，每一行代表一个 item embedding 向量，即item latent feature representation 。
     • $d$$d$ 为 embedding 向量的维度，并且满足 $d\ll |\mathbb{U}|,d\ll |\mathbb{V}|$$d\ll |\mathbb U|, d\ll |\mathbb V|$ ，$\mathbb{U}$$\mathbb U$ 为 user 集合，$\mathbb{V}$$\mathbb V$ 为 item 集合。

     在这些矩阵分解模型中：

     • 《Probabilistic matrix factorization》 提出的概率矩阵分解 probabilistic matrix factorization: PMF 假设 $\mathbf{M}$$\mathbf M$ 中的评分是带高斯噪声的独立随机变量，然后最大化观测评分。这种最大似然估计等价于 $\mathbf{M}$$\mathbf M$ 中的观测值和 $\mathbf{U}{\mathbf{V}}^{\mathrm{\top }}$$\mathbf U\mathbf V^\top$ 中对应的重建值之间的均方误差最小化。
     • 《Matrix factorization techniques for recommender systems》 提出的 BiasedMF 通过融合 user-specifc bias, item-specific bias, global-bias 来改进 PMF 。
     • 《Neural network matrix factorization》 提出的 Neural network matrix factorization: NNMF 通过将 latent user feature 和 latent item feature 传递给前馈神经网络来扩展 MF 方法。
     • 《Local low-rank matrix approximation》 提出的局部低秩矩阵近似介绍了使用不同低秩近似的组合来重建评分矩阵的思想。

   • 带辅助信息的矩阵补全matrix completion with side information：在矩阵补全问题中，目标是使用低秩矩阵来逼近 $\mathbf{M}$$\mathbf M$ 。但是，秩 rank 的最小化是一个棘手的问题。

     • 《Exact matrix completion via convex optimization》 使用最小化核范数nuclear norm（矩阵的奇异值之和）来代替秩的最小化，从而将目标函数变成了可处理的凸函数。

     • Inductive matrix completion: IMC 将 user 和 item 的内容信息融入到特征向量中，并预估 user $u_i$$u_i$ 对 item $v_j$$v_j$ 的评分为：

       $$m_{i,j}={\overrightarrow{\mathbf{x}}}_i^{\mathrm{\top }}\mathbf{U}{\mathbf{V}}^{\mathrm{\top }}{\overrightarrow{\mathbf{y}}}_j$$

       其中 ${\overrightarrow{\mathbf{x}}}_i$$\mathbf{\vec x}_i$ 为用户 $u_i$$u_i$ 的特征向量， ${\overrightarrow{\mathbf{y}}}_j$$\mathbf{\vec y}_j$ 为 item $v_j$$v_j$ 的特征向量。$\mathbf{U}$$\mathbf U$ 和 $\mathbf{V}$$\mathbf V$ 为低秩的、待学习的user embedding 矩阵和 item embedding 矩阵。

     • 《Matrix completion on graphs》提出的 geometric matrix completion: GCM 模型通过以 user graph 和 item graph 的形式添加辅助信息，从而对矩阵补全模型进行正则化。

     • 在 《Collaborative filtering with graph information: Consistency and scalable methods》 提出的 GRALS 将一种更有效的交替最小二乘优化方法引入了图正则化矩阵补全问题。

     • 最近，《Geometric matrix completion with recurrent multi-graph neural networks》 提出，通过在图上使用卷积神经网络将 graph-based 辅助信息融合到矩阵补全中，并结合递归神经网络来建模动态评分生成过程。

       和他们不同，GCMC 直接使用图卷积编码器/解码器对评分的二部图进行建模，通过一个non-iterative 步骤即可预测 unseen 的评分。

       相比之下，sRGCNN 需要用迭代式的多个 step 才能预测评分。

14.1 模型

1. 给定用户集合 $\mathbb{U}$$\mathbb U$ 以及 item 集合 $\mathbb{V}$$\mathbb V$ 。考虑评分矩阵 $\mathbf{M}\in {\mathbb{R}}^{|\mathbb{U}|\times |\mathbb{V}|}$$\mathbf M\in \mathbb R^{|\mathbb U|\times |\mathbb V|}$ ，矩阵的第 $i$$i$ 行、$j$$j$ 列代表用户 $u_i$$u_i$ 对 item $v_j$$v_j$ 的评分 $m_{i,j}$$m_{i,j}$ 。

   $$\begin{array}{c}{m}_{i,j}\{\begin{array}{ll}>0,& \text{observed}\\ =0,& \text{non-observed}\end{array}\end{array}$$

   我们将矩阵补全问题转化为链接预测问题。考虑二部图 $G=(\mathcal{W},\mathcal{E},\mathcal{R})$$G=(\mathcal W,\mathcal E,\mathcal R)$ ，其中： $\mathcal{W}=\mathbb{U}\cup \mathbb{V}$$\mathcal W = \mathbb U\cup \mathbb V$ 为所有节点集合， $\mathcal{E}$$\mathcal E$ 表示所有链接集合（每个链接表示一个观测评分），$\mathcal{R}=\{1,2,\cdots ,R\}$$\mathcal R = \{1,2,\cdots,R\}$ 为评分等级（这里最高 $R$$R$ 级评分）。$(u_i,m_{i,j},v_j)\in \mathcal{E}$$(u_i,m_{i,j},v_j)\in \mathcal E$ 表示用户 $u_i$$u_i$ 对item $v_j$$v_j$ 的评分为 $m_{i,j}\in \mathcal{R}$$m_{i,j}\in \mathcal R$ 。

   如下图所示：

   • 左图为评分矩阵 $\mathbf{M}$$\mathbf M$ ，每一项对应于 user-item 之间的评分（评分在 1~5 分之间），或者未观测（评分记作 0）。
   • 第二幅图表示 user-item 评分的二部图，边对应于评分行为，边上的数字对应于评分数值。
   • 最后两幅图表示矩阵补全问题可以转换为二部图上的链接预测问题，并使用端到端的可训练的图自编码器进行建模。

   矩阵补全问题转化为链接预测问题的核心是：链接如何对应到评分？GCMC 的做法是：每个等级的评分对应一条边，因此有 $R$$R$ 种不同类型的边。

   • 每种类型的边都有一个编码器，所有编码器的结果聚合得到 node embedding 。
   • 每种类型的边都有一个解码器，所有解码器的结果求期望得到预估的评分。

   但是，这里没有考虑评分之间的大小关系：评分为 1 要小于评分为 $R$$R$ 。因此这里忽视了非常重要的评分排序关系。

   

2. 之前的 graph-based 推荐算法通常采用 multi-stage pipeline，其中包括图的特征抽取模型（如 graph embedding 模型）以及图的链接预测模型。这些模型都是独立分开训练。

   但是最近的研究结果表明：通过端到端的技术来建模图结构化数据可以显著提升效果。在这些端到端技术中，应用于无监督学习和链接预测的图自编码graph auto-encoder 技术尤为突出。因此我们提出一种图自编码器的变种来应用于推荐任务。

14.1.1 图自编码器

1. 图自编码器由一个编码器和一个解码器组成，其中：

   • 编码器模型：$\mathbf{Z}=f(\mathbf{X},\mathbf{A})$$\mathbf Z = f(\mathbf X, \mathbf A)$ 。其中：

     • $\mathbf{X}\in {\mathbb{R}}^{|\mathcal{W}|\times d_f}$$\mathbf X\in \mathbb R^{|\mathcal W|\times d_f}$ 为输入的特征矩阵，每一行代表一个节点的特征向量， $d_f$$d_f$ 为节点的特征向量维度。
     • $\mathbf{A}\in {\mathbb{R}}^{|\mathcal{W}|\times |\mathcal{W}|}$$\mathbf A \in \mathbb R^{|\mathcal W|\times |\mathcal W|}$ 为图的邻接矩阵。
     • $\mathbf{Z}\in {\mathbb{R}}^{|\mathcal{W}|\times d_e}$$\mathbf Z\in \mathbb R^{|\mathcal W|\times d_e}$ 为节点的 embedding 矩阵，每一行代表一个节点的 embedding 向量，$d_e$$d_e$ 为 node embedding 向量维度。

   • 解码器模型：$\hat{\mathbf{A}}=g(\mathbf{Z})$$\hat{\mathbf A} = g(\mathbf Z)$ 。解码器以一对节点 embedding $({\overrightarrow{\mathbf{z}}}_i,{\overrightarrow{\mathbf{z}}}_j)$$\left(\mathbf{\vec z}_i,\mathbf{\vec z}_j\right)$ 为输入，并预测节点 $i$$i$ 和 $j$$j$ 之间的连接性，即预估的邻接矩阵的项 ${\hat{A}}_{i,j}$$\hat A_{i,j}$ 。

2. 对于二部图 $G=(\mathcal{W},\mathcal{E},\mathcal{R})$$G=(\mathcal W,\mathcal E,\mathcal R)$ ，我们重新定义编码器为：

   $$[\mathbf{U},\mathbf{V}]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)$$

   其中：

   • $\mathbf{U}\in {\mathbb{R}}^{|\mathbb{U}|\times d_e}$$\mathbf U\in \mathbb R^{|\mathbb U|\times d_e}$ 为 user embedding 矩阵，$\mathbf{V}\in {\mathbb{R}}^{|\mathbb{V}|\times d_e}$$\mathbf V\in \mathbb R^{|\mathbb V|\times d_e}$ 为 item embedding 矩阵。

   • ${\mathbf{M}}_r\in \{0,1{\}}^{|\mathbb{U}|\times |\mathbb{V}|}$$\mathbf M_r\in \{0,1\}^{|\mathbb U|\times |\mathbb V|}$ 为评分等级为 $r$$r$ 的邻接矩阵，它的元素在 {0,1} 内取值，$1\le r\le R$$1\le r\le R$。并且当用户 $u_i$$u_i$ 对 item $v_j$$v_j$ 的观测评分 $m_{i,j}=r$$m_{i,j} = r$ 时 $M_r(i,j)=1$$M_{r}(i,j) = 1$ ，否则为零。

     因此，${\mathbf{M}}_r$$\mathbf M_r$ 定义了原始评分矩阵中评分等级为 $r$$r$ 关联的邻接矩阵。

     这里对每种类型的边定义了一个邻接矩阵，不同的邻接矩阵代表了不同的模型，因此类似于 《Convolutional Networks on Graphs for Learning Molecular Fingerprints》 提出的 neural graph fingerprint 模型。

   类似地，我们重新定义解码器为：

   $$\hat{\mathbf{M}}=g(\mathbf{U},\mathbf{V})$$

   解码器输入一对 user-item 的 embedding 向量，并返回 user $u_i$$u_i$ 对 item $v_j$$v_j$ 预估的评分 ${\hat{m}}_{i,j}$$\hat m_{i,j}$ ，其中 ${\hat{m}}_{i,j}$$\hat m_{i,j}$ 为 $\hat{\mathbf{M}}$$\hat{\mathbf M}$ 的第 $i$$i$ 行第 $j$$j$ 列。

   我们通过最小化预测评分矩阵 $\hat{\mathbf{M}}$$\hat{\mathbf M}$ 和真实评分矩阵 $\mathbf{M}$$\mathbf M$ 之间的重构误差来训练该自编码器（注意：通常只考虑观测值上的重构误差）。通常评估重构误差的指标为 RMSE （将评分预测视为回归问题）或者交叉熵（将评分预测视为分类问题）。

   最后，我们注意到可以将最近提出的几个矩阵补全 state-of- the-art 模型纳入我们的框架中，并将它们视为我们模型的特例。

14.1.2 图卷积编码器

1. 这里我们选择了一种特定的编码器模型，它可以有效地利用图中 location 之间的权重共享，并为每种边类型 $r\in \mathcal{R}$$r\in \mathcal R$ 分配独立的处理通道。

2. 我们选择局部图卷积 local graph covolution 作为编码器模型。这类局部图卷积可以视为消息传递的一种方式，其中消息在图的链接之间传递和转换。

   在我们case 中，我们为每个评分等级分配一个level-specific 变换，使得从 item $v_j$$v_j$ 到用户 $u_i$$u_i$ 的消息传递形式为：

   $${\overrightarrow{\mu }}_{j\to i}^{(r)}=\frac{1}{c_{i,j}}{\mathbf{W}}_r{\overrightarrow{\mathbf{x}}}_j$$

   其中：

   • $c_{i,j}$$c_{i,j}$ 为归一化常数，通常选择为 $|{\mathcal{N}}_i|$$|\mathcal N_i|$ （左归一化left normalization） 或者 $\sqrt{|{\mathcal{N}}_i||{\mathcal{N}}_j|}$$\sqrt{|\mathcal N_i||\mathcal N_j|}$ （对称归一化）。 ${\mathcal{N}}_i$$\mathcal N_i$ 为节点 $u_i$$u_i$ 的邻域节点集合，${\mathcal{N}}_j$$\mathcal N_j$ 为节点 $v_j$$v_j$ 的邻域节点集合。

     根据论文的描述，这里应该是 ${\mathcal{N}}_i^{(r)}$$\mathcal N_i^{(r)}$ 和 ${\mathcal{N}}_j^{(r)}$$\mathcal N_j^{(r)}$ ，即类型为 $r$$r$ 的邻域。此外，还要求满足：$v_j\in {\mathcal{N}}_i^{(r)}$$v_j\in \mathcal N_i^{(r)}$ 以及 $u_i\in {\mathcal{N}}_j^{(r)}$$u_i\in \mathcal N_j^{(r)}$ 。

   • ${\mathbf{W}}_r$$\mathbf W_r$ 为评分等级 $r$$r$ 的 level-specific 权重矩阵。

   • ${\overrightarrow{\mathbf{x}}}_j$$\mathbf{\vec x}_j$ 为节点 $v_j$$v_j$ 的特征向量。

   同理，用户 $u_i$$u_i$ 到 item $v_j$$v_j$ 的消息传递形式为：

   $${\overrightarrow{\mu }}_{i\to j}^{(r)}=\frac{1}{c_{j,i}}{\mathbf{W}}_r{\overrightarrow{\mathbf{x}}}_i$$

   这里也可以选择使用不同的 level-specific 权重矩阵 ${\mathbf{W}}_{r,u2i},{\mathbf{W}}_{r,i2u}$$\mathbf W_{r,u2i},\mathbf W_{r,i2u}$（即 user -> item 和 item -> user 传递消息时，权重矩阵不同）。

   在消息传递之后：

   • 首先通过求和来聚合类型为 $r$$r$ 的所有邻居 ${\mathcal{N}}_i^{(r)}$$\mathcal N_{i}^{(r)}$ 的消息，得到领域类型为 $r$$r$ 的单个representation 向量。
   • 然后将所有邻域类型的 representation 向量聚合，从而得到节点的单个聚合向量。
   • 最后对聚合向量进行变换，最终得到节点的 embedding 向量。

   以下公式为用户节点 $u_i$$u_i$ 的 embedding 计算公式，item 节点 $v_j$$v_j$ 的 embedding 也是类似的。

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i=\sigma \left[\text{accum}(\sum _{v_j\in {\mathcal{N}}_i^{(1)}}{\overrightarrow{\mu }}_{j\to i}^{(1)},\cdots ,\sum _{v_j\in {\mathcal{N}}_i^{(R)}}{\overrightarrow{\mu }}_{j\to i}^{(R)})\right]\\ {\overrightarrow{\mathbf{u}}}_i=\sigma \left(\mathbf{W}{\overrightarrow{\mathbf{h}}}_i\right)\end{array}$$

   其中第一行公式称作卷积层，第二行公式称作 dense 层。

   注意：

   • 当没有辅助信息可用时， dense 层对于 user 和 item 都采用相同的参数矩阵 $\mathbf{W}$$\mathbf W$ 。

     当存在辅助信息可用时， dense 层对于 user 和 item 都采用单独的参数矩阵 $\mathbf{W}$$\mathbf W$ ，分别记作 ${\mathbf{W}}^{(U)},{\mathbf{W}}^{(V)}$$\mathbf W^{(U)},\mathbf W^{(V)}$。

   • 这里卷积层只有一层。虽然可以堆叠更多的卷积层来构建更深的模型，但是在最初的实验中我们发现堆叠更多卷积层并不能提高性能。

     同理，堆叠更多的 dense 层也不能提高性能。因此，最终我们选择单层卷积层 + 单层 dense 层的组合作为图编码器。

   • 这里给出的模型仅仅是一种可能性。虽然编码器的选择相对简单，但是也可以选择不同的变种。例如：

     • 可以使用神经网络来计算消息传递（${\overrightarrow{\mu }}_{j\to i}^{(r)}=\text{nn}({\overrightarrow{\mathbf{x}}}_i,{\overrightarrow{\mathbf{x}}}_j,r)$$\vec\mu_{j\rightarrow i}^{(r)} = \text{nn}\left(\mathbf{\vec x}_i,\mathbf{\vec x}_j, r\right)$），从而替换掉简单的线性变换。
     • 可以使用 attention 机制从模型中学习每个消息的权重，从而替代消息的归一化常数 $c_{i,j}$$c_{i,j}$ 。

14.1.3 双线性解码器

1. 我们使用双线性解码器 bilinear decoder 来重建二部图的链接。令用户 $u_i$$u_i$ 对 item $v_j$$v_j$ 预估的评分为 ${\hat{m}}_{i,j}$$\hat m_{i,j}$ ，则解码器输出预估评分为 $r$$r$ 的概率为：

   $$p({\hat{m}}_{i,j}=r)=\frac{\exp \left({\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{Q}}_r{\overrightarrow{\mathbf{v}}}_j\right)}{\sum _{s\in \mathcal{R}}\exp \left({\overrightarrow{\mathbf{u}}}_i^{\mathrm{\top }}{\mathbf{Q}}_s{\overrightarrow{\mathbf{v}}}_j\right)}$$

   其中每个评分等级 $r$$r$ 关联一个可训练的参数 ${\mathbf{Q}}_r\in {\mathbb{R}}^{d_e\times d_e}$$\mathbf Q_r\in \mathbb R^{d_e\times d_e}$ ，$d_e$$d_e$ 为 embedding 向量的维度。

   每个评分登记 $r$$r$ 关联一个 ${\mathbf{W}}_r$$\mathbf W_r$ 用于编码、关联一个 ${\mathbf{Q}}_r$$\mathbf Q_r$ 用于解码。

   模型最终预估的评分为所有评分等级预估结果的期望值：

   $${\hat{m}}_{i,j}=g({\overrightarrow{\mathbf{u}}}_i,{\overrightarrow{\mathbf{v}}}_j)={\mathbb{E}}_{p({\hat{m}}_{i,j}=r)}[r]=\sum _{r=1}^{R}r\times p({\hat{m}}_{i,j}=r)$$

14.1.4 模型训练

1. 损失函数：模型训练期间我们将 GCMC 模型的损失函数定义为：最小化预估评分 ${\hat{m}}_{i,j}$$\hat m_{i,j}$ 的对数似然：

   $$\mathcal{L}=-\sum _{(i,j):{\mathrm{\Omega }}_{i,j}=1}\sum _{r=1}^{R}I(r=m_{i,j})\times \log p({\hat{m}}_{i,j}=r)$$

   其中：

   • $I(\cdot )$$I(\cdot)$ 为示性函数：$I(\text{true})=1,I(\text{false})=0$$I(\text{true}) = 1, I(\text{false}) = 0$ 。
   • $\mathbf{\Omega }$$\mathbf\Omega$ 为观测值的mask 矩阵：对于观测值对应的项，${\mathrm{\Omega }}_{i,j}=1$$\Omega_{i,j} = 1$ ；对于未观测值对应的项，${\mathrm{\Omega }}_{i,j}=0$$\Omega_{i,j} = 0$ 。

   因此，上述目标函数仅在所有观测的评分上优化。

2. GCMC 模型的整体框架如下所示。模型由图卷积编码器 $[\mathbf{U},\mathbf{V}]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)$$[\mathbf U, \mathbf V] = f(\mathbf X, \mathbf M_1,\cdots,\mathbf M_R)$ 以及双线性解码器 $\hat{\mathbf{M}}=g(\mathbf{U},\mathbf{V})$$\hat{\mathbf M} = g(\mathbf U,\mathbf V)$ 组成。其中：

   • 编码器从 user-> item 或者 item -> user 传递并变换消息。
   • 解码器根据 user embedding 和item embedding 的 pair 对来预估评分。

   

3. node dropout：为使得模型能够很好地泛化到未观测的评分，我们以概率 $p_{\text{dropout}}$$p_\text{dropout}$ 随机丢弃某个节点传出的所有消息，我们称之为 node dropout 。注意：和常规 dropout 一样，在消息丢弃之后需要 rescale。

   这种 node-level 的 dropout 和常规的 dropout 不同。常规的 dropout 是在message-level进行 dropout，称作 message dropout 。

   • 在 message dropout 中，每条消息随机独立地丢弃，使得最终 embedding 对于边的扰动更为鲁棒。
   • 而在 node dropout 中，每个节点随机独立地丢弃，使得最终 embedding 对于特定用户和特定 item 的影响更为鲁棒。这会缓解一些热门用户或热门item 的影响。

   最后，我们还对卷积自编码器的 dense 层的隐单元使用了常规的 dropout 。

4. mini-batch 训练：为了训练较大的数据集（如 MovieLens-10M 数据集），我们需要对观测数据进行采样，从而进行 mini-batch 训练。这是将 MovieLens-10M 的完整模型加载到 GPU 内存所必须的。

   我们从每个等级的观测评分中采样固定比例的评分，然后仅考虑该 mini-batch 的损失。这样我们在训练过程中仅需要考虑当前 mini-batch 中出现的 user 和 item。这既是正则化的有效手段，又可以降低训练模型需要的内存。

   通过在 Movielens-1M 数据集上使用 mini-batch 训练和 full-batch 训练的实验对比（对比时针对二者分别调优了各自的正则化参数），我们发现二者产生了可比的结果。

   最后，对于 MovieLens-10M 以外的其它数据集，我们选择 full-batch 训练，因为 full-batch 训练相比 mini-batch 训练的收敛速度更快。

14.1.5 向量化实现

1. 在 GCMC 的实现中，我们可以使用高效的稀疏矩阵乘法来实现图自编码器模型，其算法复杂度和边的数量呈线性关系，即 $O(|\mathcal{E}|)$$O(|\mathcal E|)$ 。

   假设聚合函数 accum 为累加，则图卷积编码器为（采用左归一化）：

   $$\begin{array}{c}{\mathbf{A}}_r=\left[\begin{array}{cc}\mathbf{0}& {\mathbf{M}}_r\\ {\mathbf{M}}_r^{\mathrm{\top }}& \mathbf{0}\end{array}\right]\\ \left[\begin{array}{c}{\mathbf{H}}_u\\ {\mathbf{H}}_v\end{array}\right]=\sigma \left(\sum _{r=1}^R{\mathbf{D}}^{-1}{\mathbf{A}}_r\mathbf{X}{\mathbf{W}}_r^{\mathrm{\top }}\right)\\ \left[\begin{array}{c}\mathbf{U}\\ \mathbf{V}\end{array}\right]=f(\mathbf{X},{\mathbf{M}}_1,\cdots ,{\mathbf{M}}_R)=\sigma \left(\left[\begin{array}{c}{\mathbf{H}}_u\\ {\mathbf{H}}_v\end{array}\right]{\mathbf{W}}^{\mathrm{\top }}\right)\end{array}$$

   其中：

   • $\mathbf{D}$$\mathbf D$ 为节点的度矩阵 degree matrix， $D_{i,i}=|{\mathcal{N}}_i|$$D_{i,i} = |\mathcal N_i|$ 。

     这里是否要替换为 ${\mathbf{D}}_r$$\mathbf D_r$ ，即评分等级 $r$$r$ 下的邻接矩阵的度矩阵？

   • $\sigma \left(\sum _{r=1}^R{\mathbf{D}}^{-1}{\mathbf{A}}_r\mathbf{X}{\mathbf{W}}_r^{\mathrm{\top }}\right)$$\sigma\left(\sum_{r=1}^R \mathbf D^{-1} \mathbf A_r \mathbf X \mathbf W^{ \top}_r\right)$ 可以替换为向量拼接（而不是累加）。

   另外，采用对称归一化的图卷积编码器以及双线性解码器的向量化 vectorization 也以类似的方式进行。

14.1.6 辅助信息

1. 理论上可以将包含每个节点的信息（如内容信息）的特征直接作为节点的输入特征（即特征矩阵 $\mathbf{X}$$\mathbf X$ ），并直接作用到图自编码器中。但是，当内容信息不足以区分不同的用户（或者 item）及其兴趣时，将内容信息直接馈入图卷积层会导致严重的信息流瓶颈bottleneck of information flow 。

   此时，可以通过单独的处理通道 channel，从而将用户特征向量或 item 特征向量以辅助信息的形式纳入全连接层中。

   由于内容信息灌入到模型的最后一层，因此上述的信息流瓶颈不会出现，因为瓶颈只会出现在中间层。那么这么做对不对？理论依据是什么？

   我们选择输入特征矩阵 $\mathbf{X}$$\mathbf X$ 为一个单位矩阵，即每个节点的输入特征为节点的 one-hot 表示。令用户节点 $u_i$$u_i$ 的辅助信息特征向量为 ${\overrightarrow{\mathbf{x}}}_i^f$$\mathbf{\vec x}_i^f$ ，则作用到全连接层之后，节点的embedding 为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{f}}}_i=\sigma ({\mathbf{W}}_1^{(U,f)}{\overrightarrow{\mathbf{x}}}_i^f+{\overrightarrow{\mathbf{b}}}^{(U)})\\ {\overrightarrow{\mathbf{u}}}_i=\sigma ({\mathbf{W}}^{(U)}{\overrightarrow{\mathbf{h}}}_i+{\mathbf{W}}_2^{(U,f)}{\overrightarrow{\mathbf{f}}}_i)\end{array}$$

   其中：

   • ${\mathbf{W}}_1^{(U,f)},{\mathbf{W}}_2^{(U,f)}$$\mathbf W_1^{(U,f)},\mathbf W_2^{(U,f)}$ 都是可训练的权重矩阵，${\overrightarrow{\mathbf{b}}}^{(U)}$$\mathbf{\vec b}^{(U)}$ 为可训练的 bias 向量。

   • user 节点的参数为 $\{{\mathbf{W}}_1^{(U,f)},{\mathbf{W}}_2^{(U,f)},{\overrightarrow{\mathbf{b}}}^{(U)},{\mathbf{W}}^{(U)}\}$$\left\{\mathbf W_1^{(U,f)},\mathbf W_2^{(U,f)} , \mathbf{\vec b}^{(U)}, \mathbf W^{(U)}\right\}$ ，而 item 节点的参数为 $\{{\mathbf{W}}_1^{(V,f)},{\mathbf{W}}_2^{(V,f)},{\overrightarrow{\mathbf{b}}}^{(V)},{\mathbf{W}}^{(V)}\}$$\left\{\mathbf W_1^{(V,f)},\mathbf W_2^{(V,f)} , \mathbf{\vec b}^{(V)}, \mathbf W^{(V)}\right\}$ 。即 user,item 类型的节点使用两套不同的参数。

     因为 user 节点和 item 节点具有不同的输入特征空间。

   • 本文实验中使用的数据集中，用户内容以及 item 内容的信息大小有限，因此我们使用这种辅助信息的方式。

2. 注意：辅助信息不一定要以节点特征向量的形式出现，也可以是图结构（如社交网络）、自然语言或者图像数据。此时可以将上式中的 dense 层替换为适当的可微模块，如 RNN、CNN 或者其它图卷积网络。

14.1.7 权重共享

1. 编码器权重共享：在辅助信息的方式中，我们使用节点的 one-hot 向量作为输入。此时矩阵 ${\mathbf{W}}_r$$\mathbf W_r$ 的第 $i$$i$ 列可以视为节点 $i$$i$ 在评分等级 $r$$r$ 下的潜在因子向量。这些潜在因子向量通过消息传递，被传递到与该节点相连的 user 节点（如果节点 $i$$i$ 为 item 节点）或者 item 节点（如果节点 $i$$i$ 为 user 节点）。

   但是，并非所有用户拥有评分等级为 $r$$r$ 的相同评分数量，也并非所有 item 拥有评分等级为 $r$$r$ 的相同评分数量。这将导致 ${\mathbf{W}}_r$$\mathbf W_r$ 的某些列的优化频次明显低于其它列。因此，对于不同的 $r$$r$ 我们期待矩阵 ${\mathbf{W}}_r$$\mathbf W_r$ 之间的权重共享，从而缓解该优化问题。

   遵从 《A neural autoregressive approach to collaborative filtering》我们实现了以下权重共享策略：

   $${\mathbf{W}}_r=\sum _{s=1}^r{\mathbf{T}}_s$$

   由于更高的评分等级包含的权重矩阵数量更多，因此我们称这种权重共享为有序权重共享 ordinal weight sharing 。

   为什么更高评分包含的权重矩阵数量更多？完全没有道理。

2. 解码器权重共享：对于成对双线性解码器，我们采用一组基权重矩阵 basis weight matrix $\{{\mathbf{P}}_1,\cdots ,{\mathbf{P}}_{n_b}\}$$\{\mathbf P_1,\cdots,\mathbf P_{n_b}\}$ ，其中：

   $${\mathbf{Q}}_r=\sum _{s=1}^{n_b}{a}_{r,s}{\mathbf{P}}_s$$

   其中：

   • $n_b$$n_b$ 为基权重矩阵的数量。注意，为缓解过拟合并减少参数数量， $n_b$$n_b$ 应该小于评分等级数量 $R$$R$ 。
   • $a_{r,s}$$a_{r,s}$ 为可学习的参数，用于决定对每个解码器权重矩阵 ${\mathbf{Q}}_r$$\mathbf Q_r$ 的线性组合的系数。

   这种解码器的权重共享是一种有效的正则化手段。

14.2 实验

1. 数据集：我们在多个常见的协同过滤 benchmark 数据集上评估我们的模型。

   • MovieLens （100K,1M, 10M）数据集：包含多个用户对多部电影的评级数据，也包括电影元数据信息（如电影题材）和用户属性信息（如用户年龄、性别、职业）。该数据集有多个版本，对应于不同的数据量。
   • Flixster 数据集：来自于社交电影网站 Flixster 的电影评分数据集，数据集包含了用户之间的好友关系。
   • Douban 数据集：来自豆瓣的电影评分数据集，数据集包含用户之间的好友关系。
   • YahooMusic 数据集：来自 Yahoo! Music 社区的用户对音乐家的评分数据集。

   对于 Flixster,Douban, YahooMusic 数据集，我们使用《Geometric matrix completion with recurrent multi-graph neural networks》 论文提供的预处理的子集。预处理后，每个数据集包含 3000 个用户节点以及 3000 个 item 节点，以及对应的 user-user 或 item-item 交互图。

   下图给出了数据集的统计信息，其中Features 表示是否包含用户特征或者item 特征，Ratings 表示数据集的评分数量，Density 表示评分矩阵中已观测评分的占比，Rating level 表示评分等级范围。

   

2. baseline 模型：

   • 矩阵补全模型，包括 MC, IMC, GMC, GRALS, sRGCNN 。具体细节参考前文所述。
   • 矩阵分解模型，包括 PMF, I-RBM, BiasMF, NNMF 。 具体细节参考前文所述。
   • 协同过滤模型，包括 LLORMA-Local, I-AUTOREC, CF-NADE 。 具体细节参考前文所述。

   另外我们还对比了我们不带额外信息的GCMC 模型，以及带辅助信息的 GCMC+Feat 模型。

3. 参数配置：

   • 所有 baseline 方法直接采用原始论文中的实验结论数据（因此也不需要实现和运行这些 baseline 方法）。

   • 对于 GCMC 模型，我们通过验证集从以下超参数范围选择最佳的超参数：

     • 聚合函数accumulation ：stack vs sum。
     • 是否在编码器中使用有序权重共享：是 vs 否。
     • 编码器中 $c_{i,j}$$c_{i,j}$ 为归一化常数：左归一化 vs 对称归一化。
     • node dropout 比例： $p_{\text{dropout}}\in \{0.3,0.4,0.5,0.6,0.7,0.8\}$$p_\text{dropout}\in \{0.3,0.4,0.5,0.6,0.7,0.8\}$ 。

     另外，除非另有说明，否则我们使用以下超参数配置：

     • 使用学习率为 0.01 的 Adam 优化器。
     • 解码器基权重矩阵数量 $n_b=2$$n_b = 2$ 。
     • 编码器采用：维度 500 的单层卷积层（使用 ReLU 激活函数） + 维度 50 的单层 dense层（无激活函数）。

     最后，我们使用学习模型参数的指数移动平均（衰减因子 0.995）在保留的测试集上评估模型。

4. Movielens-100k 数据集（特征向量形式的辅助信息实验）：我们直接使用数据集原始的 u1.base/u1.test 的训练集/测试集拆分结果。对于该数据集，我们使用辅助信息来参与所有模型的训练。在该数据集我们对比了矩阵补全 baseline 方法和我们的 GCMC 方法，其中：

   • GMC, GRALS, sRGCNN 通过 $k$$k$ 近邻图来表示 user/item 特征。
   • 其它方法直接使用原始特征向量。

   对于 GCMC 的超参数，我们将原始训练集按照 80:20 进行训练集/验证集的拆分，然后通过验证集来调优超参数：在图卷积中使用 stack 作为累积函数，选择 $p_{\text{dropout}}=0.7$$p_\text{dropout} = 0.7$ ，使用左归一化。一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 GCMC 模型，我们不带任何辅助信息。对于 GCMC + Feat 我们使用辅助信息，并且辅助信息的 side information layer 使用维度大小为 10 的 dense 层（采用 ReLU 激活函数）。

   我们使用 1000 个 full-batch epoch 来训练 GCMC 和 GCMC + Feat 。我们随机重复执行 5 次并报告测试集上的平均 RMSE 结果。整体评估结果如下（baseline 数据直接来自于 《Geometric matrix completion with recurrent multi-graph neural networks》）。

   结论：

   • 我们的 GCMC 方法明显优于baseline 方法，即使在没有辅助信息的情况下也是如此。

   • 和我们方法最接近的是 sRGCNN 方法，它在用户和 item 的近邻图上使用图卷积，并使用 RNN 以迭代的方式学习表示。

     实验结果表明，使用简单的解码器（而不是复杂的 RNN）直接从学到的user embedding/ item embedding 中直接评估评分矩阵可以更有效，同时计算效率更高。

   

5. MovieLens-1M, MovieLens-10M 数据集（无辅助信息的实验）：在该数据集上我们和当前的 state-of-the-art 协同过滤算法（如 AutoRec, LLorma, CF-NADE ）进行比较。

   我们采取和 《A neural autoregressive approach to collaborative filtering》 相同的训练集/测试集拆分方式，拆分比例 90:10 。另外，baseline 方法的结果直接使用该论文的数值。

   该数据集不带任何辅助信息，因此我们没有比较 GCMC + Feat 。我们对原始训练集按照 95:5 随机拆分为训练集/验证集，然后通过验证集来调优超参数：

   • 对于 MovieLens-1M 数据集，我们使用 sum 作为累计函数，选择 $p_{\text{dropout}}=0.7$$p_\text{dropout} = 0.7$ ，使用对称归一化。

   • 对于 MovieLens-10M，我们使用 stack 作为累计函数，选择 $p_{\text{dropout}}=0.3$$p_\text{dropout} = 0.3$ ，使用对称归一化。

     另外考虑到该数据集的评分等级数量翻倍，我们选择解码器的基参数矩阵数量 $n_b$$n_b$ 用于翻倍（即 $n_b=4$$n_b = 4$ ）。

   一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 MovieLens-1M 我们训练 3500 个 full-batch epoch，对于 MovieLens-10M 我们训练 18000 个 mini-batch step（对应于 batch size =10000, epoch = 20 ）。

   我们按照 90:10 随机拆分原始训练集/测试集，并重复执行 5 轮，报告模型在测试集上的平均 RMSE。所有 baseline 评分来自于论文 《A neural autoregressive approach to collaborative filtering》 中的数据。对于 CF-NADE 我们报告了最佳性能的变体。

   结论：

   • GCMC 方法可以扩展到大规模数据集，其性能可以达到 user-based 或者 item-based 协同过滤的 state-of-the-art 方法。
   • CF-NADE 引入的几种技术，如：layer-specific 学习率、特殊的ordinal 损失函数、评分的自回归建模，这些都和我们的方法正交，因此这些技术也可以和我们的 GCMC 框架结合使用。

   

6. Flixster, Douban, YahooMusic （图形式的辅助信息实验）：这些数据集包含了一些图结构的辅助信息。我们通过使用这些图的邻接向量（根据degree 进行归一化）作为相应的 user/item 的特征向量，从而引入辅助信息。

   注意：辅助信息的图是社交网络等 user-user 图，或者 item-item 图。它们不同于 user-item 二部图。

   我们根据论文 《Geometric matrix completion with recurrent multi-graph neural networks》 的训练集/测试集拆分。所有 baseline 方法的结果都取自于该论文的数值。

   我们从训练集中按照 80:20 随机拆分为训练集/验证集，然后通过验证集来调优超参数：在图卷积中使用 stack 作为累积函数，选择 $p_{\text{dropout}}=0.7$$p_\text{dropout} = 0.7$ ，使用左归一化。一旦选择好超参数之后，我们就在整个原始训练集上重新训练模型，并利用训练好的模型来评估测试集。

   对于 GCMC 模型，我们使用辅助信息，并且辅助信息的 side information layer 使用维度大小为 64 的 dense 层（采用 ReLU 激活函数）。

   我们使用 full-batch 训练 200 个 epoch 。

   最终我们重复执行 5 轮，并报告模型在测试集上的平均 RMSE。其中 Flixster 有两组结果：左侧结果表示同时引入了 user 辅助信息和 item 辅助信息；右侧结果表示仅考虑 item 辅助信息。

   结论：GCMC 在所有baseline 中取得了 state-of-the-art 效果。

   注意：GCMC 在所有三个数据集上都采用相同的超参数配置，如果针对各自数据集调优，效果会进一步提升。

   

7. 冷启动实验：为深入了解 GCMC 模型如何通过辅助信息来提升冷启动性能，我们选择 MovieLens-100K 数据集，随机选择固定数量的冷启动用户 $N_c$$N_c$ ，这些用户最多随机保留 $N_r$$N_r$ 个评分（整个实验中随机数种子固定，因此每次随机选择的结果都相同）。注意：MovieLens=100K 原始数据仅包含具有至少 20 个评分的用户。

   我们考察当 $N_r\in \{1,5,10\},N_c\in \{0,50,100,150\}$$N_r\in \{1,5,10\}, N_c\in \{0,50,100,150\}$ 时GCMC 的性能（$N_c=0$$N_c=0$ 表示所有用户都保留所有评分）。其中超参数和测试集如前面所述一样选择。结果如下图所示，虚线表示不带辅助信息时模型的表现。

   可以看到：对于冷启动用户，使用辅助信息能够带来显著的提升，在只有一个评分的用户上表现尤为突出。

   

十五、JK-Net[2018]

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 达到了 state-of-the-art 性能。另外，将 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 的图。

15.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 ）。

15.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 。

15.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 中获取信息，这可能意味着噪音并影响最终预测。

       

15.1.3 JK-Net

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

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

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

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

   • 和常见的邻域聚合网络一样，每一层都是通过聚合来自上一层的邻域来扩大影响力分布的范围。
   • 但是在最后一层，对于每个节点我们都从所有的这些 itermediate 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。