GNN

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 加深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表示。 ...

论文地址：GAT Introduction 本文介绍了一种新型的神经网络架构用来处理图结构。即__Graph Attention Networks__(GATs)。该方法利用masked self-attentional layer，即通过网络层的堆叠，可以获取网络中每个节点的领域特征，同时为领域中的不同节点指定不同的权重。这样做的好处是可以不需要各种高成本的矩阵运算也不依赖于的图结构信息。通过这种方式，GAT可以解决基于谱的图神经网络存在的问题，同时，GAT可以使用用归纳（inductive）和直推（transductive）问题。 归纳学习:先从训练样本中学习到一定的模式，然后利用其对测试样本进行预测（即首先从特殊到一般，然后再从一般到特殊），这类模型如常见的贝叶斯模型。 直推学习:先观察特定的训练样本，然后对特定的测试样本做出预测（从特殊到特殊），这类模型如k近邻、SVM等。 Architecture 图$G$中有$N$个节点，他们的特征向量为：$\textbf{h}={\vec{h_1},\vec{h_2},…,\vec{h_N}}$，其中，$\vec{h_i} \in \mathbb{R}^F$，$F$是每个节点特征数。我们的目的是输出一个新的节点特征向量集$\textbf{h’}={\vec{h_1’},\vec{h_2’},…,\vec{h_N’}}$，其中$\vec{h_i’} \in \mathbb{R}^{F’}$。 本质就是修改特征向量的维度（Network embedding） 为了获得足够的表达能力以将输入特征变换为更高级别的特征，需要至少一个可学习的线性变换。因此，以任意节点$i$和$j$为例，分别对节点$i$和节点$j$的特征向量做线性变换$W \in \mathbb{R}^{F \times F’}$，这样 就将$\vec{h_i}$和$\vec{h_j}$从$F$维的向量转化为$F’$维的向量： $$ e_{ij} = a(W\vec{h_i},W\vec{h_j}) $$ 上式中，分别对$\vec{h_i}$和$\vec{h_j}$做线性变换，然后使用self-attention为图中的每一个节点分配注意力（权重）。上式中，注意力机制$a$是一个$\mathbb{R}^{F’} \times \mathbb{R}^{F’} \to \mathbb{R}$的映射。最终得到的$e_{ij}$是节点$j$对节点$i$的影响力系数（一个实数）。 但是，上面的方法考虑其他节点对$i$的影响时，将图中的所有节点都纳入了考虑范围，这样就丢失了图的结构信息。因此，本文引入masked attention机制，即计算影响力系数$e_{ij}$时， 仅考虑节点$i$的一部分邻居节点 $j \in \mathcal{N}_i$（$i$也属于$\mathcal{N}_i$）。使用softmax将节点$i$部分邻居的注意力系数分配到(0,1)上： $$ \alpha_{ij} = \mathrm{softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k \in \mathcal{N}_i}\exp(e_{ik})} $$ 在本文中，$a$是一个单层前馈神经网络，参数是一个权重向量$\vec{\text{a}} \in \mathbb{R}^{2F’}$，然后使用负半轴斜率为0.2的LeakyReLU作为非线性激活函数： $$ \alpha_{ij} = \frac{\exp(\mathrm{LeakyReLU}(\vec{\text{a}}^T[W\vec{h_i}||W\vec{h_j}]))}{\sum_{k\in \mathcal{N}_i} \exp(\mathrm{LeakyReLU}(\vec{\text{a}}^T[W\vec{h_i}||W\vec{h_k}]))} $$ 其中$||$表示向量的连接操作。上述过程可以用下图表示： 这样，我们就可以获得节点$j$对节点$i$的注意力系数$\alpha_{ij}$，那么，节点$i$最终的输出特征$\vec{h_i’}$就是对$\mathcal{N}_i$中所有节点的加权（加注意力）求和： $$ \vec{h_i’} = \sigma (\sum_{j \in \mathcal{N}_i}\alpha_{ij} W\vec{h_j}) $$ ...