paper Introduction 本文提出图浓缩技术（Graph Condensation），旨在将大图浓缩为一个小图，使得在小图上训练的GNN可以得到和大图相当的效果。通过优化gradient matching loss来模拟GNN在原图上的训练轨迹，从而解决图浓缩问题。 通常有两个策略来简化图：Graph Sparsification(图稀疏化)和Graph Coarsening(图粗化)。图稀疏化通过减少边数来近似一个图； 图粗化旨在减少节点数量。（1）当节点具有属性特征时，由于稀疏化不会减少节点数量，因此属性量不会减少。 （2）图粗化的目的是保存一些图属性比如主特征值，这可能对下游任务不是最优的保存属性。 本文提出图浓缩，来学习生成图的结构和节点属性，从这两方面同时进行浓缩。对于Reddit数据集，GCond可以将节点数浓缩至0.1%，并且在浓缩图上可以得到和原图相当的效果。如下图所示： 本文解决了图浓缩面临的两个挑战：1. 构建目标函数， 2. 参数化可学习的节点特征和图结构。为了解决上述挑战，本文使用gradient matching loss来匹配每一个training step上原图与浓缩图的GNN参数梯度，使得GNN在浓缩图上的训练趋势与原图相匹配。为了参数化节点特征和图结构，本文将浓缩图的Feature Matrix设为自由参数矩阵，将浓缩图结构设为关于Feature matrix 的 函数（基于结构与特征相关联假设），使得计算开销降低。 Methodology A graph $\mathcal{T}=\{\mathbf{A}, \mathbf{X}, \mathbf{Y}\}$，其中$\mathbf{X} \in \mathbb{R}^{N \times d}$是$d$维节点特征，$\mathbf{Y} \in\{0, \ldots, C-1\}^N$ 表示$N$个节点的labels，共有$C$个class。图浓缩旨在学习一个小的生成图$\mathcal{S}=\left\{\mathbf{A}^{\prime}, \mathbf{X}^{\prime}, \mathbf{Y}^{\prime}\right\}$，其中$\mathbf{A}^{\prime} \in \mathbb{R}^{N^{\prime} \times N^{\prime}}$是浓缩图的邻接矩阵，$\mathbf{X}^{\prime} \in \mathbb{R}^{N^{\prime} \times D}$是浓缩图的特征矩阵，$\mathbf{Y}^{\prime} \in\{0, \ldots, C-1\}^{N^{\prime}}$是浓缩图的node labels 其中$N^{\prime} \ll N$，特征维度从$d$变为$D$。图浓缩的目标是基于原图训练过程学习浓缩图$\mathcal{S}$，使得在$\mathcal{S}$上训练的GNN应用在原图上的loss最小： $$ \min_{\mathcal{S}} \mathcal{L}\left(\mathrm{GNN}_{\boldsymbol{\theta}_{\mathcal{S}}}(\mathbf{A}, \mathbf{X}), \mathbf{Y}\right) \quad \text { s.t } \quad \boldsymbol{\theta}_{\mathcal{S}}=\underset{\boldsymbol{\theta}}{\arg \min } \mathcal{L}\left(\mathrm{GNN}_{\boldsymbol{\theta}}\left(\mathbf{A}^{\prime}, \mathbf{X}^{\prime}\right), \mathbf{Y}^{\prime}\right), $$ Outer：固定GNN参数，优化小图。 Inner: 固定小图，在小图上训练GNN参数。 ...

最近一些工作通过解耦Message-Passing 和 Feature Learning的方式来提升GNN的可拓展性，这里对一小部分相关工作做一个小总结。 1. Combining Label Propagation and Simple Models Out-performs Graph Neural Networks （ICLR2021） 模型首先忽略图结构，用简单模型（MLP），只使用节点特征预测label： $$ \min \sum_{i \in L_{t}} \ell\left(f\left(x_{i}\right), y_{i}\right) $$ 考虑一个inductive bias：预测误差与邻近度关系强相关，对图中所有节点的误差做校正。 具体来说，首先计算一个初始的误差矩阵$E$，其中训练集误差如下 $$ E_{L_{t},:}=Y_{L_{t},:}-Z_{L_{t},:} $$ 其他节点的误差未知：$E_{L_{v},:}=0, \quad E_{U,:}=0$。然后通过Label Propagation将误差矩阵在图上做平滑，使得相邻节点的误差相似： $$ \hat{E}=\underset{W \in \mathbb{R}^{n \times c}}{\arg \min } \operatorname{trace}\left(W^{T}(I-S) W\right)+\mu||W-E||_{F}^{2} $$ 由此得到所有节点的误差矩阵$\hat{E}$。然后用$\hat{E}$对基础MLP预测做校正，这个post-processing过程不涉及训练参数，校正后的预测为： $$ Z^{(r)} = Z + \hat{E} $$ 考虑homophily：校正的预测label要满足相邻节点label相似。 注意，这里不直接对$Z^{(r)}$做Label Propagation，而是构造了一个label矩阵$H \in \mathbb{R}^{n \times c}$，其中将训练集真实label和验证+测试集校正label加入$H$中，然后对$H$做label propagation： $$ \begin{aligned} H_{L_{t},:}&=Y_{L_{t},:} \\ H_{L_{v} \cup U,:}&=Z_{L_{v} \cup U,:}^{(r)} \end{aligned} $$ Label Prop: $$ H^{(t+1)}=(1-\alpha) H+\alpha S H^{(t)} $$ 最后直接用收敛的$H$做预测，即$\hat{Y} = H^{\infty}$，node $i$ 的预测class为： $$ y_i = \arg \max _{j \in\{1, \ldots, c\}} \hat{Y}_{i j} $$ ...

paper Introduction 本文研究了结合更简单的模型来处理transductive node classification任务。 主要包括1个预测模块和两个后处理（post-processing）模块： Base predictor：忽略图结构，用简单模型（如MLP或线性模型）使用节点特征预测label Error correction：校正步骤，将训练数据中的不确定性（误差）传播到图上，来校正Base predictor的预测 Smoothing：在图上平滑预测 其中只有第一步base predictor的参数是可学习的，即涉及图结构的操作（Correction和Smoothing）无需参数学习，这种简单的模型使得参数数量减少了几个数量级，训练时间也减少了几个数量级，并且可以轻松扩展到大规模图。 相比于过去的GNN+LP的方法，C&S更加高效：1）C&S首先只使用节点特征进行低成本的base prediction；2）然后再使用标签传播对基础预测进行校正 ；3）最后对最终预测进行平滑。 第一步是预测操作，后两部是后处理操作，也就是第一步为一个独立的端到端模型，后两部基于一个inductive bias来调整节点的表示。即homophily假设：相连节点的误差和label是相似的（正相关）。训练节点的误差和它相连节点的误差应相似，那么就用训练节点的误差来校正邻居节点。 因此，将标签更加直接的整合到GNN的学习算法中是本文性能的关键，并且发现LP与node features是相互互补的信号。实验表明，在OGB-Products上，参数量比GNN少了2个数量级，训练时间也减少2个数量级。 Correct and Smooth (C&S) Model 给定无向图$G=(V,E)$，$A$为邻接矩阵，$S=D^{-1 / 2} A D^{-1 / 2}$为归一化邻接矩阵。节点集划分为labeled nodes $V_L$和unlabeled nodes $V_U$，其中$V = V_L \cup V_U$。进一步，labeled nodes可以分为训练节点集$V_{L_t}$和验证节点集$V_{L_v}$。训练集和验证集的label分别为$Y_{L_t:}$和$Y_{L_v:}$， 每行为label的one-hot向量。 Simple Base Predictor $$ \min \sum_{i \in L_{t}} \ell\left(f\left(x_{i}\right), y_{i}\right) $$ $f(\cdot)$为简单的训练模型+softmax，如浅层MLP， $\ell$为cross-entropy loss。 基于训练节点$V_{L_t}$特征的模型$f$可以得到输出预测$Z \in \mathbb{R}^{n\times c}$， 其中$Z$的每行是softmax得到的分类概率分布。Simple Base Predictor是一个独立训练的端到端模型。 Correcting Base Prediction with Error Correlation (使用邻居误差关联来纠正基础预测） 通过融合标签信息来提高base prediction $Z$的准确率。 本文期望base prediction中的误差沿着图中的边正相关，即节点$i$出的预测误差在它的邻居处也会出现相似的误差。为了实现这个目的，首先定义一个误差矩阵$E \in \mathbb{R}^{n \times c}$用来保存每个节点的预测误差，其中误差为训练数据集上的残差（只有训练节点由误差）其他没有训练过程中不知道label的节点误差设为0： $$ E_{L_{t},:}=Y_{L_{t},:}-Z_{L_{t},:} \quad 为训练集节点 V_{L_t}的误差 $$ ...

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) 同理。 ...