GNN

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)$。 ...

Paper Introduction 由于GNNs过度强调平滑的节点特征而不是图结构，使得在Link Prediction任务上的表现甚至弱于heuristic方法。平滑邻居难以反映邻域结构的相关性以及其他拓扑特征。 Structural information, (e.g., overlapped neighborhoods, degrees, and shortest path), is crucial for link prediction whereas GNNs heavily rely on smoothed node features rather than graph structure。 Link prediction heuristics: 基于预定义的假设的链路预测。举几个例子[1]： Common Neighbors (CN)： 公共邻居较多的节点存在边（heuristic），则需要计算节点对间的公共邻居。 Preferential Attachment (PA): 一个节点当前的连接越多，那么它越有可能接受到新的连接（heuristic）,这需要统计每个节点的度, i.e., $P A(x, y)=|N(x)| *|N(y)|$ Katz Index heuristic: $\sum^{\infty}_{\ell=1} \beta^{\ell}|walks(x,y)=\ell|$ 表示从$x$到$y$的所有路径数， $0<\beta<1$， 表示越长的路径权重越低。 katz Index作为Link prediction heuristic假设来作为边是否存在的预测。 本文提出了Neighborhood Overlap-aware Graph Neural Networks (Neo-GNNs)来从邻接矩阵中学习结构信息，并且估计重叠多跳邻域用于link prediction。 Preliminaries GNNs for Link Prediction $$ \hat{y}_{i j}=\sigma\left(s\left(h_{i}^{(L)}, h_{j}^{(L)}\right)\right) $$ ...

Paper Introduction 加深GNN层数来增加感受野会导致优化不稳定性，比如梯度消失和oversmoothing。 因此本文采用Transformer-based self-attention来学习成对节点间的长距离关系，并且提出一种新型的readout池化机制来学习global graph embedding。即在一个GNN模块后接一个置换不变（permutation-invariant）Transformer, GNN模块捕获local信息，Transformer捕获global信息。 GNN作为一种专门的架构医学系节点直接邻域结构的局部表示， 而Transformer作为全局推理模块以位置无关的方式计算所有成对节点的交互。作者认为，一个没有positional encoding的Transformer是置换不变的，因此很适合图。 Motivation 强关系Inductive bias(我的理解是Homophily假设) 鼓励学习局部短距离的关联性。 而对于长距离相关性，结构化较低的模块（不需要过于考虑图的结构信息）更受欢迎。 GraphTrans leaves learning long-range dependencies to Transformer, 通过Transformer来学习图中所有节点对的依赖关系而不是只关注局部邻居。 下图中展示了一个子图的attention map。一共有17个节点，横坐标表示目标节点，纵坐标表示源节点，第$i$行第$j$列表示节点$i$在Transformer中聚合$j$的attention权重。第18行为一个特殊的$<CLS>$token 作为图的readout embedding。结合本文的SOTA效果，表面在学习长距离依赖时不考虑图结构先验（spatial priors）对Graph summarization（graph-level representation）是有必要的 Model GNN Module 一个通用的GNN模块： $$ \boldsymbol{h}_{v}^{\ell}=f_{\ell}\left(\boldsymbol{h}_{v}^{\ell-1},\left\{\boldsymbol{h}_{u}^{\ell-1} \mid u \in \mathcal{N}(v)\right\}\right), \quad \ell=1, \ldots, L_{\mathrm{GNN}} $$ Transformer Module 通过上面的GNN模块，我们可以得到每个节点的embedding $h_{v}^{L_{\mathrm{GNN}}}$, 将所有节点作为Transformer的Input。传统Transformer中输入先计算Self-attention（当前输入的$Q$向量和所有节点的$K$向量做内积得到输入节点和其他节点的att值，再用这个att值来为当前输入节点加权聚合所有节点的$V$向量），聚合后再和自身相加做residual,然后在做Layer Norm, 即对节点$i$的表示做Layer Norm 为$x_i^\prime = \frac{x_i-m}{\sigma}$, 其中$m$为$x_i$的均值， $\sigma$为$x_i$的标准差。 这里的Transformer不同的是， 先对所有节点做一次MLP，然后直接计算Layer Norm: $$ \overline{\boldsymbol{h}}_{v}^{0}=\operatorname{LayerNorm}\left(\boldsymbol{W}^{\text {Proj }} \boldsymbol{h}_{v}^{L_{\mathrm{GNN}}}\right) $$ 其中$\boldsymbol{W}^{\text {Proj }} \in \mathbb{R}^{d_{\mathrm{TF}} \times d_{L_{\mathrm{GNN}}}}$， 把GNN的输出维度转为TF的输入维度$d_{\mathrm{TF}}$。将所有节点的GNN node embeddings作为Transformer的输入（无positional encoding）。 每个节点的$Q$, $K$和$V$向量分别用$\boldsymbol{W}_{\ell}^{Q}, \boldsymbol{W}_{\ell}^{K}, \boldsymbol{W}_{\ell}^{V} \in \mathbb{R}^{d_{\mathrm{TF}} / n_{\text {head }} \times d_{\mathrm{TF}} / n_{\text {head }}}$计算， 对于第$\ell$层 Transformer, 节点$v$ 的$Q$向量$Q_v = \boldsymbol{W}_{\ell}^{Q} \overline{\boldsymbol{h}}_{v}^{\ell-1}$和节点$u$的$K$向量$K_u = \boldsymbol{W}_{\ell}^{K} \overline{\boldsymbol{h}}_{u}^{\ell-1}$做内积，得到两个节点之间的attention。然后用$\alpha_{v, u}^{\ell}$来为节点$v$聚合其他所有节点的$V$向量$V_u = \boldsymbol{W}_{\ell}^{V} \overline{\boldsymbol{h}}_{u}^{\ell-1}$, 如下所示: $$ a_{v, u}^{\ell}=\left(\boldsymbol{W}_{\ell}^{Q} \overline{\boldsymbol{h}}_{v}^{\ell-1}\right)^{\top}\left(\boldsymbol{W}_{\ell}^{K} \overline{\boldsymbol{h}}_{u}^{\ell-1}\right) / \sqrt{d_{\mathrm{TF}}} \tag{1} $$ ...

paper Introduction 很多GNN易受图结构攻击的影响，本文首先证明了symmetric normalized laplacian的低频分量作为GCN的filter，在某个特征值区间内对于结构扰动更加robust。基于该理论提出GCN-LFR，通过一个辅助神经网络迁移低频分量的robustness。 Q: 对抗扰动边是否会对graph spectrum产生同等的影响？过去的研究显示来自结构攻击的扰动在图谱上表达了一种隐含的趋势。如下图所示，结构扰动后，小的特征值（低频）变化较小， 高频变化较大，即高频对扰动更加敏感。 本文证明了当normalized symmetric laplacian的特征值落于某个特定区间时，低频分量会更加robust。 Methodology Poisoning Attack是指训练前扰动： Problem 1 （Poisoning Attack）: 给定一个扰动图 $\mathcal{G}^\prime$, 要对目标集合$\mathcal{T}$做对抗防御的目的是设计一个更加鲁棒的模型，使得模型在扰动图上训练后对$\mathcal{T}$中节点的预测结果和在原图上训练得到的预测结果相似： $$ \min_{\boldsymbol{\Theta}^{r *}} \sum_{u \in \mathcal{T}}\left|\left|\mathcal{M}_{u}^{r}\left(\boldsymbol{A}^{\prime}, \boldsymbol{X} ; \boldsymbol{\Theta}^{r *}\right)-\mathcal{M}_{u}\left(\boldsymbol{A}, \boldsymbol{X} ; \boldsymbol{\Theta}^{*}\right)\right|\right| $$ 即模型可以尽可能避免扰动对预测带来的影响。 其中$\mathcal{M}_{u}^{r}\left(\boldsymbol{A}^{\prime}, \boldsymbol{X} ; \boldsymbol{\Theta}^{r *}\right)=\hat{\boldsymbol{y}}_{u}^{r}$模型在扰动图上训练过后对节点$u$的预测，$\mathcal{M}_{u}^{r}$是在扰动图上训练过后的模型，最佳参数为$\boldsymbol{\Theta}^{r *}$, $\mathcal{M}$是在原图上训练过后的模型。 观察$\hat{\boldsymbol{A}}$的特征值， 因为$\hat{\boldsymbol{A}} = I - L$, 所以$\hat{\boldsymbol{A}}$的大特征值对应于低频分量，小特征值对应于高频分量。 从图1可以看出$\hat{\boldsymbol{A}}$的大特征值对于结构扰动更加鲁棒, 因为扰动之后大特征值的变化较小。所以GCN-SVD只是用最低频的分量来做defense. 接下来本文证明了只有一条边被扰动的情况下，一定存在低频$\lambda_b$，比所有高频都robust, 鲁棒区间为： $$ \max \left(0, \frac{d_{b}-d_{a}+c_{a} \lambda_{a}}{c_{b}}\right)<\lambda_{b}<\min \left(\frac{d_{b}+d_{a}-c_{a} \lambda_{a}}{c_{b}}, 1\right) $$ 即，当特征值落于这个区间中时，它一定比高频更加鲁棒。 对于Non-targeted Perturbation, 图中有多条边被扰动，那么特征值的鲁棒区间为： $$ \max_{v \in \mathcal{P}_{u}, u \in \mathcal{T}}\left(0, \frac{d_{b u v}-d_{a u v}+c_{a u v} \lambda_{a}}{c_{b u v}}\right)<\lambda_{b}<\min_{v \in \mathcal{P}_{u}, u \in \mathcal{T}}\left(\frac{d_{b u v}+d_{a u v}-c_{a u v} \lambda_{a}}{c_{b u v}}, 1\right) $$ 在得到不同扰动情况下的鲁棒区间后，我们可以基于鲁棒区间来增强GCN的鲁棒性。 ...

Paper Code Introduction 无监督图学习算法基于重构损失，不可避免的需要图相似度计算（重构embedding和输入embedding的loss), 计算复杂度较高。本文提出一种通用的归纳式无监督图学习算法SEED（Sampling, Encoding, and Embedding Distributions）。通过计算采样子图的重构损失来代替整个图的重构损失。 即 先采样子图，在用GNN编码子图，最后计算子图分布的embedding来作为整个图的representation. 过程如下图所示： SEED: Sampling, Encoding, and Embedding Distributions Anonymous Random Walk Definition 1 (Random Anonymous Walks[1]): Given a random walk $\mathbf{w}=(w_1, \cdots, w_l)$ where $\langle w_i, w_{i+1} \rangle \in E$, the anonymous walk for $\mathbf{w}$ is defined as： $$ \mathrm{aw}(\mathbf{w}) = (\mathrm{DIS}(\mathbf{w}, w_1),\mathrm{DIS}(\mathbf{w}, w_2),\cdots, \mathrm{DIS}(\mathbf{w}, w_l) ) $$ where $\mathrm{DIS}(\mathbf{w}, w_i)$ denotes the number of distinct nodes in $\mathbf{w}$ when $w_i$ first appears in $\mathbf{w}$, i.e. $$ \mathrm{DIS}(\mathbf{w}, w_i) = |{w_1, \cdots w_p}|, \quad p = \min_j {w_j=w_i} $$ 匿名随机游走和随机游走的不同在于，匿名随机游走描述了随机游走的潜在“patterns”, 不管具体被访问的节点是什么。 距离来说，给定两条随机游走序列 $\mathbf{w_1}=(v_1, v_2, v_3, v_4, v_2)$ 和$w_2=(v_2, v_1, v_3, v_4, v_1)$, 这两个RW相关联的匿名随机游走是一样的，即$\mathrm{aw}(\mathbf{w_1}) = \mathrm{aw}(\mathbf{w_2}) = (1,2,3,4,2)$, 即使$\mathbf{w_1}$和$\mathbf{w_2}$访问不同的节点。即每个节点在RW中首次被访问时的位置就是这个点在ARW中的id,如在$\mathbf{w_2}$中，$v_1$首次访问是在第二个时刻，那么他的id就是2，在ARW中用2表示。 ...