GNN

Paper Introduction SubGNN在学习子图representation时保留子图的三种属性：Position，Neighborhood，Structure，每种属性包含Internal 和Border两方面，并且要精心设计不同的anchor patch，所以过于复杂。通过分析SubGNN和普通GNN，作者发现子图表示的核心可能是区分子图内部和外部节点。基于此发现，本文提出了一种labeling trick, 即max-zero-one，来提升子图GNN的表达能力和可拓展性。 Subgraph representation task 如上图所示，目标子图$\mathbb{S}$被嵌入在整个图中，并且可能拥有多个连通分量，目标是学习子图的表示向量，使其可以预测子图的属性。NeurIPS2020文章SubGNN提出子图级message-passing来代替节点级的message passing，并且设计了三个message passing通道，每个通道分为内部和边界模块，分别捕获子图分量间的交互，以及子图与图的其他部分之间的交互。尽管取得了比普通GNN更好的效果，但是SubGNN需要繁琐的预计算，因为SubGNN通过不同采样规则的anchor patch来传递子图分量之间，以及子图分量与图其他部分之间的相关性，而三个通道共6个aspects需要不同的采样规则，以及各自的message passing，计算十分冗长（这里有解读）。另外 SubGNN对每个aspects需要使用不同的anchor patch随机采样策略，无法保证采样的anchor patch是最优的，因此效果的方差较大，使得鲁棒性堪忧。 通过对比SubGNN相较于普通GNN的优势，作者发现对于子图任务来说，区分子图内部节点和外部节点非常重要。基于这个发现，本文提出了一种labeling trick，即max-zero-one labeling trick，来标注每个节点是否在子图外或者子图内。 Labeling Trick [1]: 使用GNN生成multi-node representations （即，为一组节点，例如子图生成表示向量），该方法说明了为高阶结构生成有表达能力的representation，需要捕获结构内不同节点间的交互。在实现上，labeling trick通过一个专门设计的label来表示节点的结构特征，这个label与node feature 结合作为新的feature输入GNN中。 注： 本文只考虑诱导子图，即每个子图的每个连通分量保留原图中的所有边。 Plain GNN and SubGNN 如上图所示，$G$是一个regular graph, 所以在没有节点feature的情况下，每个节点的embedding相同，所以GNN无法区分子图$\mathcal{S}$和$\mathcal{S}^\prime$。如下图所示，Plain GNN 在message passing中子图$\mathcal{S}$内部节点1同时接收来自子图内和子图外的邻居信息，并不会加以区分。同样$\mathcal{S}^\prime$中节点3也同时接收子图内外节点，因此对于Plain GNN ，它无法区分节点1和3，因此无法区分两个子图。 而SubGNN引入了3个通道：position (P)，neighborhood (N), 和structure (S) 每个通道分别学习Internal 和Border两方面，共6个属性融入子图表示学习中。对于子图$\mathcal{S}$，为了捕获某个通道$i$的属性，SubGNN首先随机采样$n_A$个anchor patches： $\mathbb{A}_{i}=\left\{\mathcal{A}_{i}^{(1)}, \ldots, \mathcal{A}_{i}^{\left(n_{A}\right)}\right\}$，然后学习$\mathcal{S}$中的每个连通分量在这个属性$i$下的表示向量，通过子图内部连通分量和anchor patches之间的消息传递，来捕获子图内部连通分量的相对位置/邻域/结构信息，以及子图连通分量相对于子图外部分的位置/邻域/结构信息。如图2右边所示。对于通道$i$，它的Internal和border两方面采样的anchor patches表示为$\mathbb{A}_{i}=\left\{\mathcal{A}_{i}^{(1)}, \ldots, \mathcal{A}_{i}^{\left(n_{A}\right)}\right\}$，对于子图$\mathcal{S}$的一个连通分量$\mathcal{S}^{(c)}$，要学习该连通分量的表示，可使用一下subgraph-level message passing layer: $$ \begin{aligned} &\boldsymbol{a}_{i, \mathcal{S}^{(c)}}=\sum_{\mathcal{A}_{i} \in \mathbb{A}_{i}} \gamma_{i}\left(\mathcal{S}^{(c)}, \mathcal{A}_{i}\right) \boldsymbol{g}_{\mathcal{A}_{i}}, \\ &\boldsymbol{h}_{i, \mathcal{S}^{(c)}}^{(k)}=\sigma\left(W_{i} \cdot\left[\boldsymbol{a}_{i, \mathcal{S}^{(c)}}, \boldsymbol{h}_{i, \mathcal{S}^{(c)}}^{(k-1)}\right]\right) \end{aligned} $$ 其中$\gamma_{i}\left(\mathcal{S}^{(c)}, \mathcal{A}_{i}\right)$是子图分量$\mathcal{S}^{(c)}$和一个anchor patch $\mathcal{A}_{i}$的相似度。即每个子图分量依照与anchor patch 的相似度聚合来自anchor的信息。由于相似度函数的存在，SubGNN实际上是使用与子图分量$\mathcal{S}^{(c)}$接近或结构相似的anchor patch对$\mathcal{S}^{(c)}$的representation做平滑，即$\mathcal{S}^{(c)}$聚合更多与它结构相似的anchor patches的信息。通过精心设计的anchor和subgraph-level message passing，6个属性可以被各自保留，然后在融合。 ...

paper Introduction GNN通常关注节点级任务和图级任务，缺少针对子图级预测任务的方法。针对这个问题，本文提出SubGNNs用于解耦子图在不同结构aspect的表示。为了学习准确的子图表示，SubGNN在子图的连通分量和随机采样的anchor patches之间进行消息传递，从而学习高准确度的子图表示。SubGNN指定了三个通道，每个通道捕获子图不同的拓扑结构属性。 从拓扑的角度来看，子图是非常具有挑战性的结构，对子图的预测存在以下挑战： 如要对更大且size不同的子图做联合预测，挑战在于如何表征含有多个分量，甚至分量间间隔较远的子图。 子图包含了高阶连通模式（connectivity patterns），这些连通模式不仅存在于子图内节点之间，也存在与子图内节点与子图外部节点之间， 挑战在于如何将子图边界信息和子图外部信息注入GNN中。 子图可能存在于图中的一个特定区域，也可能它的连通分量分布于多个局部邻域，挑战在于如何学习子图在图中的位置。 子图间共享边（sharing edges）和非边（non-edges）存在相关性，挑战在于如何将这种子图间的依赖融合进模型中，同时任然能够将特征信息考虑在内进行辅助归纳推理。 本文提出SubGNN以解决上述挑战， SubGNN的核心原则是子图级的消息传递，可以捕获子图位置、邻域、结构三种特征 Formulating Subgraph Prediction 给定无向图$G=(V,E)$，它的一个子图表示为$S=\left(V^{\prime}, E^{\prime}\right)$，每个子图$S$有一个label $y_{S}$，并且子图$S$可能包含多个连通分量，连通分量表示为$S^{(C)}$。 Problem (Subgraph Representations and Property Prediction) 给定子图集合 $\mathcal{S} = \left\{S_{1}, S_{2}, \ldots, S_{n}\right\}$，SubGNN $E_S$为每个子图$S\in \mathcal{S}$生成一个$d_s$维的表示向量$\mathbf{Z}_S \in \mathbb{R}^{d_{s}}$， 然后用这些子图的表示向量学习一个子图分类器 $f: \mathcal{S} \rightarrow\{1,2, \ldots, C\}$，使得输入子图得到预测label: $f(S)=\hat{y}_{S}$。 本文针对子图分类任务，所提出的模型为一个可学习的embedding函数$E_{S}: S \rightarrow \mathbb{R}^{d_{s}}$， 将每个子图映射为低维表示向量，这些表示向量可以捕获子图拓扑对预测重要的aspects。具体来说，对于一个子图，message再它的连通分量之间传递，这使得我们可以对多个连通分量的子图学习有意义的表示。 SUBGNN: Properties of subgraph topology 子图拥有独特的内部结构，边界连通性，邻域概念，以及和图其他部分的相对位置。直觉上，我们的目标是以最大的似然保存保存特定的图属性。本文设计模型以考虑6种特定的图结构属性： 具体来说： (1) Position. Border Position: 该属性保留子图和图的其他部分之间的距离，通过这种距离关系，可以区分两个同构但处于不同位置的子图。 Internal Position：子图自己连通分量之间的距离。 (2) Neighborhood. Border Neighborhood：为子图的边界邻域，表示子图$S$中任意节点的$k$跳邻域中（不属于子图$S$）的节点集合。 ...

paper Introduction 现有的GNN在图和模型的size方面可拓展性有限。 对于大图，增加模型的深度对导致scope(感受野)大小成指数放大。深层model主要面临两个基本挑战： 1. oversmoothing导致表达能力下降，2. 邻域爆炸导致计算成本高昂。 本文旨在结构GNN的depth 和 scope，首先提取子图作为有限大小（bounded-size）的scope, 然后将任意深度的GNN用于子图上。 由于提取出的局部子图是由少量关键邻居组成，且排除了不相关的邻居，所以深层GNN也可以学到informative representations。 增加GNN层数会造成以下基本障碍： Expresivity (oversmoothing): 邻居的迭代混合导致不同节点的切入向量收敛到一个固定的低维子空间 Scalability (neighbor explosion): 多跳邻居递归导致感受野大小呈指数级增长 为了研究导致表达能力和可拓展性缺陷的根本原因，本文提出了以下insight: Two views on the graph: 如果从全局视角来看两个节点，如果两个节点在同一个图的同一个连通分量中，那么这两个节点在随机游走中存在到达概率，无论他们间隔多远。而本文给出了图的局部视角，具体来说， 给定节点$v$的局部子图$\mathcal{G}_{[v]}$，将$\mathcal{G}_{[v]}$仅包含节点$v$的特性，整个图看一看做所有子图$\mathcal{G}_{[v]}$的集合。那么$v$的邻域不在是所有节点$\mathcal{V}$，而它的邻域只存在于$\mathcal{V}_{[v]}$中。 如果节点$u$不在$\mathcal{V}_{[v]}$中，$u$将永远不会被考虑为$v$的邻居，无论GNN有多深。 Scope of GNNs: 加深GNN层次所造成的的表达能力和可拓展性问题都和GNN不断扩大的感受野（scope）有关。随着层次变深，感受野不断变大，使得每个节点包含的信息重叠越多，最终收敛到同一个子空间，导致oversmoothing; 另外 感受野变大，导致每个节点的邻居数呈指数级上升，导致邻居爆炸。所以GNN的层数加深会导致感受野变大（耦合），即$L$层GNN的感受野为全部$L$-hop以内的邻居，层数深度（depth）和感受野大小(scope)的强耦合限制了GNN的设计。 Decoupling the GNN depth and scope: 为了解耦GNN的深度（depth）与感受野(scope)，使得加层数与感受野无关。对于节点$v$，首先为它提取一个小的子图$\mathcal{G}_{[v]}$，然后在小的子图上应用任意层数的GNN。若GNN的层数$L^\prime$大于感受野的跳数，那么子图中的每对节点会交换多次信息，额外的消息传递有助于GNN更好的融合scope内的信息，从而增强表达能力。 Decoupling the Depth and Scope of GNNs Definition (Depth of subgraph) ：假设子图$\mathcal{G}_{[v]}$是连通的，$\mathcal{G}_{[v]}$的depth定义为$\max _{u \in \mathcal{V}_{[v]}} d(u, v)$, 其中$d(u, v)$表示$u$到$v$的最短路径。 本文提出shaDow-GNN，它包含了一个子图提取器$\text { EXTRACT}$。 shaDow-GNN的过程如下： 用子图提取器$\operatorname{EXTRACT}(v, \mathcal{G})$为节点$v$提取一个连通子图$\mathcal{G}_{[v]}$，子图的深度（距离$v$最远的节点和$v$之间的跳数）为$L$。 构建一个$L^\prime$层的GNN并应用在$\mathcal{G}_{[v]}$上。 如果 $L^\prime > L$那么可以反映decoupling，因为GNN层数此时与scope无关，层数加深不会影响感受野。 本文从三个不同的角度理论证明了shaDow-GNN可以提升GNN的表达能力。 ...

paper Introduction 本文提出了一种新型的Graph Contrastive Learning构造Contrastive pairs的方式，即将跨图的同维度特征作为positive pairs， 不同维度特征作为negative pairs。 和过去的GCL方法相比，本文无需互信息估计器（MI Estimator），映射头（Projector），不对称结构（asymmetric structures）。 并且理论证明了该方法可以看做Information Bottleneck 原则在自监督设置下的实例。 具体来说，受典型相关分析（From Canonical Correlation Analysis）的启发，本文提出了一种简单有效的GCL框架，从而是模型避免复杂难以理解多模块设计。 和过去的方法相同的是，为输入图以随机增强的方式生成两个view， 目的是为两个view学习共享的 node representations 通过共享的GNN Encoder。不同在于，本文利用了典型相关分析（CCA），具体来说，新目标旨在最大化同一输入的两个增强views之间的相关性，同时对单个视图表示的不同（特征）维度进行去相关（避免不同维度捕获相同信息，即同一个view内的不同维度channel互为negative pairs）。 这么做的目的是 1）本质上追求的是丢弃增强后变化的信息，同时保留增强后不变的信息，以及 2）防止维度崩溃（即不同维度捕获相同的信息）。 和其他方法的对比如上图所示， 本文提出的CCA-SSG无需negative pairs， 参数化的互信息估计器， projection head或者不对称结构。对比对的数量仅为$O(D^2)$, 其中$D$为输出维度。 Canonical Correlation Analysis CCA: Identify and Quantify the associations between two sets of variables， 即CCA用来衡量两组随机变量的相关性，每组可能有很多Random Variables. 从相关系数引入： Pearson 相关系数： 给定两组数据集$X$， $Y$。 其中$X \in \mathbb{R}^{N \times 1}$ 表示只有一个随机变量（属性），样本数为$N$。 $Y \in \mathbb{R}^{M \times 1}$: 一个随机变量，样本量为$M$。那么Pearson 相关系数$\rho$定义为： $$ \rho(X,Y)= \frac{\mathrm{Cov}(X,Y)}{\sigma_X \sigma_Y} $$ 其中$\sigma_X$，$\sigma_Y$分别为$X$和$Y$的标准差。$\mathrm{Cov}(X,Y)$为$X$, $Y$的协方差。$\rho \in [-1,1]$。 $\rho$越接近1， $X$和$Y$的线性相关性越高。$\rho$越接近0，$X$和$Y$的线性相关性月底。 ...

paper Introduction 本文旨在通过多视图Contrastive Learning 来学习节点表示和图表示。其中对比视图为结构视图（structural view）。本文发现，两个以上的对比视图不会提升性能（我觉得仅是针对本文的Diffusion-based view吧~）。 本文实验性的表明了基于一阶邻居和图扩散视图做CL可以达到最好的效果。 为了将对比学习应用到图表示学习任务，本文提出通过最大化图的不同结构视角的互信息来作为监督信号。通过对提出框架的系统研究，本文展示了一些GCL和visual CL上的不同： （1）将view数量（即增强）增加到两个以上不会提高性能，最好的性能是通过对比来自一阶邻居view的embedding和graph diffusion的embedding，(2) 与对比图编码或多尺度编码相比，跨视图对比节点和图编码在node classification 和 graph classification上都能获得更好的结果。 (3) 与分层图池化方法（例如DiffPool相比）一个简单的Readout在这node classification 和 graph classification上实现了更好的性能，以及 (4) 应用正则化（early stopping除外） 或归一化层对性能有负面影响。 Method MVGRL通过最大化一个view的node embedding和另一个view的graph embedding之间的 互信息来学习节点和图表示。如上图所示，MVGRL由以下几个部分构成 增强机制：将样本图转化为同一个图的相关view， 这个view只是structural view， 不会改变原图中的node feature，然后对两个增强图中的相同节点（identical node）进行子采样，类似于CV中的域剪裁。 两个专用的GNNs， 每个view一个GNN，再接一个共享的MLP作为projection head，来为两个view学习representation。 图池化层， 在MLP后学习两个图的graph-level representation。 判别器 来对比一个图的embedding和另一个图的节点embedding,并对他们的一致性（agreement）评分。 Augmentations 考虑两种类型的图增强：(1) 对初始节点特征进行操作的特征空间增强，例如，mask或添加高斯噪声，以及 (2) 通过添加或删除连通性、子采样或使用最短路径或diffusion matrix生成全局视图来对做图结构增强。 前一种增强可能是有问题的，因为许多数据集不带有初始节点特征。 此外，观察到在任一空间上屏蔽或添加噪声都会降低性能。 因此，本文选择生成全局视图，然后进行子采样。 实验表明，在大多数情况下，最好的结果是通过将邻接矩阵转化为扩散矩阵，并将这两个矩阵视为同一图的结构的两个一致view。因为邻接矩阵和扩散矩阵分别提供了图结构的局部和全局视图，从这两种view中学习到的表示之间最大一致性，从而鼓励模型同时编码的局部和全局信息。 Diffusion matrix从全局角度提供了任意节点对之间的相关性，其中$\mathbf{T} \in \mathbb{R}^{n \times n}$是通用转移矩阵，$\Theta$是权重系数，决定了全局和局部信息的比例，即对于每个节点，不同层次信息的比重， $\Theta_{k}$越大，表示全局信息权重越大。 令$\sum_{k=0}^{\infty} \theta_{k}=1, \theta_{k} \in[0,1]$，$\lambda_{i} \in[0,1]$,其中$\lambda$是$\mathbf{T}$的特征向量， 这样来保证$\mathbf{S}$可以收敛到一个固定矩阵。扩散用快速近似值和稀疏化方法计算： $$ \mathbf{S}=\sum_{k=0}^{\infty} \Theta_{k} \mathbf{T}^{k} \in \mathbb{R}^{n \times n} $$ 给定一个邻接矩阵$\mathbf{A} \in \mathbb{R}^{n \times n}$和一个对角度矩阵$\mathbf{D} \in \mathbb{R}^{n \times n}$, Personalized PageRank (PPR)和Heat Kernel分别为两种不同的Diffusion matrix实例。对于PPR和HK，转移概率矩阵定义为$\mathbf{T}=\mathbf{A} \mathbf{D}^{-1}$。PPR将第$k$层的权重系数设置为$\theta_{k}=\alpha(1-\alpha)^{k}$, 而HK将第$k$层的权重系数设置为$\theta_{k}=e^{-t} t^{k} / k !$。 ...

paper Introduction 图对比学习（GCL）已经成为图表示学习的主要技术，它最大化了共享相同语义的成对图增强之间的互信息。鉴于图数据的多样性，在增强过程中很难很好地保留语义。目前，GCL 中选择图增强方式的途径通常有以下三种。 1. 适用于不同数据集的图增强方式可能是不同的，需要在每个数据集上做验证，手动选择最适用于每个数据集的增强。2. 通过繁琐的搜索来选择增强方式。3. 通过邻域只是来选择增强方式。所有这些都限制了现有 GCL 方法的效率和通用性。为了解决该问题，本文提出了一种不需要对图做编辑， 而是对GNN编码器做扰动的增强方式： SimGRACE。并且对SimGRACE设计了对抗训练的方案：AT-SimGRACE。 上图的实验中，两类图用不同的颜色标出，三种GCL模型分别在三个数据集上训练，训练完成后的分类效果如第一行所示。 对于GraphCL, 对边做扰动后再输入GraphCL 训练好的encoder,可以看出GraphCL的encoder对于扰动后的图数据集无法很好的保留分类语义。而对于SIMGRACE，不对图做扰动，而对训练好的encoder做扰动，扰动后的encoder对数据集的分类效果可以很好地保留语义信息。由此实验性表明了对encoder扰动可以保留比直接对图扰动更多的语义信息。 GraphCL 表明 GNN 可以使用他们提出的框架获得鲁棒性。 但是，（1）他们没有解释为什么 GraphCL 可以增强鲁棒性； (2) GraphCL 似乎对随机攻击具有很好的免疫力，而对对抗性攻击的表现却不尽如人意。为了弥补这些缺陷，本文基于SimGRACE提出了一种新的算法 AT-SimGRACE通过对抗的方式来扰动编码器，从而是实现对抗训练的效果，它引入了更少的计算开销，同时显示出更好的鲁棒性。 Method SimGRACE 编码器扰动（Encoder perturbation） 给定一个GNN编码器$f(\cdot;\theta)$,它的参数扰动版本表示为$f(\cdot;\theta^\prime)$。如图中所示，参数扰动版本的编码器不需要梯度反传训练参数，每次训练过程更新$f(\cdot;\theta)$，而$f(\cdot;\theta^\prime)$的参数$\theta^\prime$只通过对$\theta$扰动得到。第$l$层GNN的参数表示为$\theta_l$，那么它的扰动后参数$\theta^\prime_l$有下式得到： $$ \theta_{l}^{\prime}=\theta_{l}+\eta \cdot \Delta \theta_{l} ; \quad \Delta \theta_{l} \sim \mathcal{N}\left(0, \sigma_{l}^{2}\right) $$ 其中$\eta$用来控制扰动的缩放，$\Delta \theta_{l}$是扰动项，扰动值采样自0均值$\sigma_{l}^{2}$的Gaussian Distribution。$f(\cdot;\theta)$和$f(\cdot;\theta^\prime)$的输出分别为$\mathbf{h}$和$\mathbf{h}^{\prime}$： $$ \mathbf{h}=f(\mathcal{G} ; \boldsymbol{\theta}), \mathbf{h}^{\prime}=f\left(\mathcal{G} ; \boldsymbol{\theta}^{\prime}\right) $$ 从下图可以看出，如果不对编码器施加扰动，即超参数$\eta=0$，效果会很差，扰动太多效果也会很差。 映射头 （Projection Head） 和其他大多数GCL方法一样，该方法也要一个projection head来对GNN的output representation做一次变换，通常就是个MLP，得到输出$z$和$z^\prime$： $$ z=g(\mathbf{h}), z^{\prime}=g\left(\mathbf{h}^{\prime}\right) $$ ...

paper Introduction 在Deeper GNN中，residual connections通常可以缓解oversmoothing问题，但是，若图中的存在abnormal node features, 那么residual connections会放大abnormal features的影响。本文旨在设计AirGNN， 在自适应调整残差连接的权重，是的可以弹性适应存在abnormal node features的图。太多聚合（deep layers）会导致oversmoothing，但residual 对深层GNN有益，但是对于abnormal features是脆弱的。 Preliminary Frobenius norm: $||\mathbf{X}||_{F}=\sqrt{\sum_{i j} \mathbf{X}_{i j}^{2}}$ $\ell_{21}$ norm: $||\mathbf{X}||_{21}= \sum_{i}\left|\left|\mathbf{X}_{i}\right|\right|_{2}=\sum_{i} \sqrt{\sum_{j} \mathbf{X}_{i j}^{2}}$ 表示对每行算$\ell_2$ norm 再对所有行算$\ell_1$ norm。 Study 如图Figure 1所示， 对于具有abnormal node feature 的图，添加residual（蓝线）会导致性能巨大下降，因为abnormal node feature是与任务无关的，residual相对于无residual 保留了更多original abnormal features。 对于node feature 都是normal的图， 没有residual的话，随着层次加深，GNN的性能会下降。 综上，residual可以是GNN层次加深（容忍更多聚合），但是对abnormal features的鲁棒性较差。 Understandings I: Feature aggregation as Laplacian smoothing 对于Laplacian Smoothing problem: $$ \underset{\mathbf{X} \in \mathbb{R}^{n \times d}}{\arg \min } \mathcal{L}_{1}(\mathbf{X}):=\frac{1}{2} \operatorname{tr}\left(\mathbf{X}^{\top}(\mathbf{I}-\tilde{\mathbf{A}}) \mathbf{X}\right)=\frac{1}{2} \sum_{\left(v_{i}, v_{j}\right) \in \mathcal{E}}\left|\left|\frac{\mathbf{X}_{i}}{\sqrt{d_{i}+1}}-\frac{\mathbf{X}_{j}}{\sqrt{d_{j}+1}}\right|\right|_{2}^{2} \tag{1} $$ 其目标是找到最佳的$X$,使得$X$在图上最平滑。而对于GCN, GCNII (w/o residual)和APPNP (w/o residual), 他们的每一层都可以看做是如下的特征聚合方式： $$ \mathbf{X}^{(k+1)}=\tilde{\mathbf{A}} \mathbf{X}^{(k)} = \tilde{\mathbf{A}}=(\hat{\mathbf{D}}^{-\frac{1}{2}} \hat{\mathbf{A}} \hat{\mathbf{D}}^{-\frac{1}{2}})\mathbf{X}^{(k)} \tag{2} $$ 实际上，迭代多层GNN可以看做是以 step size =1的条件下，以梯度下降的方式求解Laplacian Smoothing问题，即以梯度下降的方式找到在图上最平滑的信号： $$ \begin{equation} \begin{aligned} \mathbf{X}^{(k+1)} &= \mathbf{X}^{(k)}-\left.\gamma \frac{\partial \mathcal{L}_{1}}{\partial \mathbf{X}} \right|_{\mathbf{X}=\mathbf{X}^{(k)}}\\ &= \mathbf{X}^{(k)}-\left.\gamma \frac{\partial \frac{1}{2} \operatorname{tr}\left(\mathbf{X}^{\top}(\mathbf{I}-\tilde{\mathbf{A}}) \mathbf{X}\right)}{\partial \mathbf{X}} \right|_{\mathbf{X}=\mathbf{X}^{(k)}} \\ &= \mathbf{X}^{(k)} - (\mathbf{I}-\tilde{\mathbf{A}})\mathbf{X}^{(k)} \\ &= \tilde{\mathbf{A}} \mathbf{X}^{(k)} \end{aligned}\tag{3} \end{equation} $$ 其中令$\gamma = 1$, 所以，迭代多层GCN相当于以step size=1的方式迭代求解Laplacian Smoothing 问题。GCNII (w/o residual)和APPNP (w/o residual) 同理。 ...

Paper Introduction 本文是自监督方法在GCNs上首次系统的探索，设计了3种自监督任务来将分析自监督在GCN中起到的作用。自监督旨在充分利用unlabeled数据中的知识来设计前置任务（pretext task），来帮助模型学习更具迁移性和泛化能力的表示。前置任务可以认为是对目标任务有帮助的辅助正则化网络，设计用于帮助原任务学习到更多下游任务相关的语义信息。 GCN任务通常是直推半监督的（transductive semi-supervised）,含有大量unlabeled数据，而self-supervision(SSL)可以充分利用unlabeled data， 那么就产生了一个值得探索的问题：将自监督学习应用到GCN上是否也可以达到提升泛化能力和鲁棒能力的效果？ 先给结论 Q1: 自监督学习可否在分类任务中提升GCN？ 如果可以，如何将其合并到 GCN 中以最大化增益？ A1: 本文证明了通过多任务学习将自监督学习融入 GCN 是有效的，即多任务损失作为 GCN 训练中的正则化项。 这种作为自监督作为正则化项的方法，强于用自监督来预训练或者self-training。 Q2: 前置任务的设计重要吗？ GCN 有哪些有用的自监督前置任务？ A2: 本文研究了三个基于图属性的自监督任务。 分别是节点聚类node clustering, 图划分graph partitioning 和图补全graph completion。 并且进一步说明不同的模型和数据集倾向于不同的自监督任务。 Q3: 自监督也会影响 GCN 的对抗鲁棒性吗？ 如果是，如何设计前置任务？ A3: 本文进一步将上述发现推广到对抗性训练环境中。提供了广泛的结果，以表明自监督还可以提高 GCN 在各种攻击下的鲁棒性，而不需要更大的模型或额外的数据。 Method GCNs $\boldsymbol{Z}=\hat{\boldsymbol{A}} \operatorname{ReLU}\left(\hat{\boldsymbol{A}} \boldsymbol{X} \boldsymbol{W}_{0}\right) \boldsymbol{W}_{1}$可以分为两块来看 (1) 特征提取模块$f_{\theta}(\boldsymbol{X}, \hat{\boldsymbol{A}}) = \hat{\boldsymbol{A}} \operatorname{ReLU}\left(\hat{\boldsymbol{A}} \boldsymbol{X} \boldsymbol{W}_{0}\right)$ 参数为$\theta = \{\boldsymbol{W}_{0}\}$和（2）线性变换模块$\boldsymbol{Z}=f_{\theta}(\boldsymbol{X}, \hat{\boldsymbol{A}}) \boldsymbol{\Theta}$ 其中 参数$ \boldsymbol{\Theta} = \boldsymbol{W}_{1}$。 半监督GCN优化任务的目标函数为： $$ \begin{aligned} \boldsymbol{Z} &=f_{\theta}(\boldsymbol{X}, \hat{\boldsymbol{A}}) \boldsymbol{\Theta} \\ \theta^{*}, \boldsymbol{\Theta}^{} &=\arg \min_{\theta, \boldsymbol{\Theta}} \mathcal{L}_{\mathrm{sup}}(\theta, \boldsymbol{\Theta}) \\ &=\arg \min_{\theta, \boldsymbol{\Theta}} \frac{1}{\left|\mathcal{V}_{\text {label }}\right|} \sum_{v_{n} \in \mathcal{V}_{\text {label }}} L\left(\boldsymbol{z}_{n}, \boldsymbol{y}_{n}\right) \end{aligned} \tag{1} $$ 其中$L(\cdot, \cdot)$是每个labeled node的损失函数。 ...

Paper Introduction 类别不均衡（Class Imbalance）是真实场景中非常常见的问题。一般在我们提及类别不均衡时，默认指的是数量不均衡：即不同类中训练样本数量的不一致带来的模型于不同类别学习能力的差异，由此引起的一个严重问题是模型的决策边界会主要由数量多的类来决定 。 但是在图结构中，不同类别的训练样本不仅有在数量上的差异，也有在位置结构上的差异.这就使得图上的类别不均衡问题有了一个独特的来源：拓扑不均衡。这个工作最主要的动机就是研究拓扑不均衡的特点，危害以及解决方法，希望能够引起社区对拓扑不均衡问题的重视。 本文提出Topology-Imbalance Node Representation Learning （TINL）, 主要关注拓扑不平衡导致的决策边界漂移。所谓拓扑不平衡值得是， labeled nodes的位置如果位于拓扑中的决策边界，那么会传播错误的影响。 如上图所示，颜色和色调分别表示节点从labeled node接收到的influence类型和强度，节点R1位于两类节点的拓扑边界，第一张图可以看出，两个$\mathbf{x}$节点面临influence conflict问题，两个$\mathbf{Y}$节点由于远离R2，面临影响力不足的问题。也就是，如果决策便捷有labeled node（如R1）, 那么他的影响力很容易传播给另一个类的边界unlabeled节点，导致影响力冲突，从而分类错误。 而冲突较小的labeled node更可能位于类的拓扑中心（如R2）,顾增加其权重，是的它在训练过程中发挥更大作用。 Understanding Topology Imbalance via Label Propagation Label Propagation中，labels从labeled node延边传播， 看做label从labeled node开始的随机游走过程。LP最终收敛状态可以认为每个节点的soft-labels: $$ \boldsymbol{Y}=\alpha\left(\boldsymbol{I}-(1-\alpha) \boldsymbol{A}^{\prime}\right)^{-1} \boldsymbol{Y}^{0} $$ 其中$\boldsymbol{A}^{\prime}=\boldsymbol{D}^{-\frac{1}{2}} A D^{-\frac{1}{2}}$，其实就是PageRank的极限分布， $\boldsymbol{Y}^{0}$为每个节点的初始one-hot label。 第$i$个节点的预测结果为$\boldsymbol{q}_{i}=\arg \max _{j} \boldsymbol{Y}_{i j}$，每个节点的预测向量反映了每个节点主要受哪个类的影响。图(a)反映了GCN与LP的预测一致性，所以LP的节点影响力边界可以作为GNN的决策边界。理想状态下，labeled node的影响力边界应与真实类边界一致，例如红色的labeled node 在LP下所传播的影响力范围，应与所有红色node的范围一致。但是如图(b)所示，蓝色的labeled node如果较多位于真实类边界，这些位于边界的节点也会传播影响力，从而导致位于边界的真是红色节点被预测为蓝色，预测边界向红色类偏移。 Measuring Topology Imbalance by Influence Conflict 可以看出，位于决策边界的labeled node 会不可避免的将影响力传播到其他类节点，因此需要衡量labeled node与其所属类的相对拓扑位置（位于类边缘还是中心）。由于Homophily， 位于类边缘的节点也具有和其邻居相似的性质，因此利用邻域特征差别来判断labeled node是否位于边缘是不可靠的。因此本文利用整个图中的节点影响力冲突，提出基于冲突检测的拓扑相对位置Conflict Detection-based Topology Relative Location metric (Totoro). ...

Paper Introduction GNN的neighborhood aggregation中会引入邻域中任务无关的邻居，所以要移除图中有大量任务无关的边，顾本文提出NeuralSparse来解决该问题。 在构造数据集时，两个节点连接的动机可能与拿到这张图后要进行的下游任务无关，例如下游任务是节点分类，那么和这个任务相关的连接应是同类节点间产生边。但是构造图数据集是的两个节点连接的动机可能是特征相似的节点（不一定同类）。 下图给出一个例子，Blue 和 Red节点分别采样自两个独立的二维Gaussian distribution, 图1(a)显示两类节点的原始features有大量重合。对于每个节点，随机抽取10个其他节点作为他的邻居，这样生成的图（图1(b) )中的边和node label没有任何关系，即所有边都与节点分类任务无关。在这个图上做GCN得到(图1(b)下方)的node embedding，可以看到GCN学到的node embedding在任务无关的边上，无法区分两类节点。 图1(c)是DropEdge学到的node embedding，图1(d)为本文的NeuralSparse学到的node embedding。 Present work：根据监督信号来选择任务相关的边。 由sparsification network 和GNN两个模块组成. sparsification network旨在参数化稀疏过程，即在给定预算下， 为每个节点选择任务相关的一节邻居。在训练阶段，优化稀疏策略，即训练一个可以将图稀疏化的网络。在测试阶段，将测试图输入网络，得到一个稀疏化的图。 NeuralSparse Theoretical justification 首先从统计学习角度建模问题。将预测任务定义为$P(Y|G)$, 其中$Y$是预测目标，$G$是输入图。本文利用稀疏化子图来移除任务无关的边, 问题形式化为: $$ P(Y \mid G) \approx \sum_{g \in \mathbb{S}_{G}} P(Y \mid g) P(g \mid G) $$ $g$是一个稀疏化子图，$\mathbb{S}_{G}$为$G$的稀疏化子图集合。 $P(Y \mid g)$ 为给定一个稀疏化子图$g$，用$g$过GNN后预测为$Y$的概率。 $$ \sum_{g \in \mathbb{S}_{G}} P(Y \mid g) P(g \mid G) \approx \sum_{g \in \mathbb{S}_{G}} Q_{\theta}(Y \mid g) Q_{\phi}(g \mid G) $$ 用函数来近似(计算) 分布， 即给定$g$ 预测为$Y$的概率$ P(Y \mid g)$定义为一个参数为$\theta$的函数$Q_{\theta}(Y \mid g)$, 从$G$中获得子图$g$的概率$P(g \mid G)$定义为一个参数为$\phi$的函数$Q_{\phi}(g \mid G)$。 ...