论文解读（AGE)《Adaptive Graph Encoder for Attributed Graph Embedding》

论文信息

论文标题：Adaptive Graph Encoder for Attributed Graph Embedding
论文作者：Gayan K. Kulatilleke, Marius Portmann, Shekhar S. Chandra
论文来源：2020, KDD
论文地址：download
论文代码：download

1 Introduction

　　基于 GCN 的方法有三个主要缺点：

• • 图卷积滤波器和权值矩阵的纠缠会损害其性能和鲁棒性；
  • 图卷积滤波器是广义拉普拉斯平滑滤波器的特殊情况，但没有保持最优的低通特性；
  • 现有算法的训练目标通常是恢复邻接矩阵或特征矩阵，处理与现实不符；

　　AGE 由两个模块组成：

• • 拉普拉斯平滑滤波器；
  • 自适应编码器；

　　首先，一个GCN 编码器由多个图卷积层组成，每一层包含一个图卷积滤波器 H$H$、一个权值矩阵 (W1$W_1$、W2$W_2$) 和一个激活函数。[35] 证明，滤波器和权值矩阵的纠缠并没有为半监督图表示学习提供性能增益，甚至损害了训练效率，因为它加深了反向传播的路径。

　　 

　　其次，考虑图卷积滤波器， [18] 在理论上表明，它们实际上是应用于低通去噪的特征矩阵上的拉普拉斯平滑滤波器 [28]。本文证明了现有的图卷积滤波器并不是最优的低通滤波器，因为它们不能过滤某些高频噪声。因此，它们不能达到最好的平滑效果。

　　最后，本文认为这些算法的训练目标（重建邻接矩阵 [23,31] 或特征矩阵 [24,32]）与现实应用不兼容。具体来说，重构邻接矩阵是将邻接矩阵设为地面真值成对相似度，但不适合于缺乏特征信息的情况。然而，恢复特征矩阵将迫使模型记住特征中的高频噪声，因此也是不合适的。

2 Method

　　整体框架：

　　 

　　组成部分：

• • a Laplacian smoothing filter
    • Laplacian Smoothing Filter: The designed filter H$H$ serves as a low-pass filter to denoise the high-frequency components of the feature matrix  X$\mathrm{X}$ . The smoothed feature matrix  X~$\tilde{\mathrm{X}}$  is taken as input of the adaptive encoder.
      
  • an adaptive encoder
    • Adaptive Encoder: To get more representative node embeddings, this module builds a training set by adaptively selecting node pairs which are highly similar or dissimilar. Then the encoder is trained in a supervised manner.　　

2.1 Laplacian Smoothing Filter

　　基本假设：图上邻居节点具有相似性。

2.1.1 Analysis of Smooth Signals

　　从图信号处理的角度来解释图平滑。以 x∈Rn$\mathbf{x}\in {\mathbb{R}}^n$ 作为图信号，每个节点被分配一个值向量。为测量图信号 x$x$ 的平滑度，可以计算出图拉普拉斯矩阵 L$L$ 和 x$x$ 上的瑞利商：

　　　　R(L,x)=x⊤Lxx⊤x=∑(i,j)∈E(xi−xj)2∑i∈Vx2i(1)$R(\mathbf{L},\mathbf{x})=\frac{{\mathbf{x}}^{\mathbf{\top }}\mathbf{L}\mathbf{x}}{{\mathbf{x}}^{\mathrm{\top }}\mathbf{x}}=\frac{\sum _{(i,j)\in \mathcal{E}}{(x_i-x_j)}^2}{\sum _{i\in \mathcal{V}}{x}_i^2}(1)$

　　PS：拉普拉斯矩阵的性质

　　fTLf=fTDf−fTWf=∑i=1Ndif2i−∑i=1N∑j=1Nwijfifj=12(∑i=1Ndif2i−2∑i=1N∑j=1Nwijfifj+∑j=1Ndjf2j)=12(∑i=1N∑j=1Nwijf2i−2∑i=1N∑j=1Nwijfifj+∑i=1N∑j=1Nwijf2j)=12∑i=1N∑j=1Nwij(fi−fj)2$\begin{array}{rl}{f}^{T}Lf& =f^{T}Df-f^{T}Wf\\ & =\sum _{i=1}^N{d}_i{f}_i^2-\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{f}_i{f}_j\\ & =\frac{1}{2}(\sum _{i=1}^N{d}_i{f}_i^2-2\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{f}_i{f}_j+\sum _{j=1}^N{d}_j{f}_j^2)\\ & =\frac{1}{2}(\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{f}_i^2-2\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{f}_i{f}_j+\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{f}_j^2)\\ & =\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{w}_{ij}{(f_i-f_j)}^2\end{array}$

　　Eq.1$\text{Eq.1}$ 显然是 x$x$ 的标准化方差分数。平滑信号应该在相邻节点上分配相似的值。因此，假设瑞利商较低的信号更平滑，接着给出特征向量 ui$u_i$ 的光滑性度量：

　　　　R(L,ui)=u⊤iLuiu⊤iui=λi(2)$R(\mathbf{L},{\mathbf{u}}_i)=\frac{{\mathbf{u}}_i^{\mathrm{\top }}\mathbf{L}{\mathbf{u}}_i}{{\mathbf{u}}_i^{\mathrm{\top }}{\mathbf{u}}_i}={\lambda }_i(2)$

　　Eq.2$\text{Eq.2}$ 表示平滑的特征向量与较小的特征值相关联，即较低的频率。因此，基于Eq.1$\text{Eq.1}$、Eq.2$\text{Eq.2}$   L$L$ 分解信号 x$x$):

　　　　x=Up=∑i=1npiui(3)$\mathbf{x}=\mathbf{U}\mathbf{p}=\sum _{i=1}^n{p}_i{\mathbf{u}}_i(3)$

　　其中 pi$p_i$ 是特征向量 ui${\mathbf{u}}_i$ 的系数，那么 x$x$ 的平滑度是：

　　　　R(L,x)=x⊤Lxx⊤x=∑i=1np2iλi∑i=1np2i(4)$R(\mathbf{L},\mathbf{x})=\frac{{\mathbf{x}}^{\mathrm{\top }}\mathbf{L}\mathbf{x}}{{\mathbf{x}}^{\mathrm{\top }}\mathbf{x}}=\frac{\sum _{i=1}^n{p}_i^2{\lambda }_i}{\sum _{i=1}^n{p}_i^2}(4)$

　　因此，为获得更平滑的信号，本文滤波器的目标是在保留低频分量的同时滤掉高频分量。

2.1.2 Generalized Laplacian Smoothing Filter

　　如[28]所述，广义拉普拉斯平滑滤波器为：

　　　　H=I−kL(5)$\mathbf{H}=\mathbf{I}-k\mathbf{L}(5)$

　　采用 H$\mathbf{H}$ 作为滤波器矩阵，滤波后的信号 x~$\tilde{\mathbf{x}}$ 为：

　　　　x~=Hx=U(I−kΛ)U−1Up=∑i=1n(1−kλi)piui=∑i=1np′ui(6)$\tilde{\mathbf{x}}=\mathbf{H}\mathbf{x}=\mathbf{U}(\mathbf{I}-k\mathrm{\Lambda }){\mathbf{U}}^{-1}\mathbf{U}\mathbf{p}=\sum _{i=1}^n(1-k{\lambda }_i)p_i{\mathbf{u}}_i=\sum _{i=1}^n{p}^{\mathrm{\prime }}{\mathbf{u}}_i(6)$

　　因此，为实现低通滤波(low-pass filtering)，频率响应函数 1−kλ$1-k\lambda$ 应是一个递减和非负函数。叠加 t$t$ 次拉普拉斯平滑滤波器，将滤波后的特征矩阵 X~$\tilde{\mathbf{X}}$ 表示为

　　　　X~=HtX(7)$\tilde{\mathbf{X}}={\mathbf{H}}^t\mathbf{X}(7)$

　　请注意，该过滤器根本是非参数化的。

2.1.3  The Choice of k

　　在实践中，使用重整化技巧 A~=I+A$\tilde{\mathrm{A}}=\mathrm{I}+\mathbf{A}$，采用对称归一化图拉普拉斯矩阵

　　　　L~sym=D~−12L~D~−12(8)${\tilde{\mathbf{L}}}_{sym}={\tilde{\mathbf{D}}}^{-\frac{1}{2}}\tilde{\mathbf{L}}{\tilde{\mathbf{D}}}^{-\frac{1}{2}}(8)$

　　此时滤波器为：

　　　　H=I−kL~sym(9)$\mathbf{H}=\mathbf{I}-k{\tilde{\mathbf{L}}}_{sym}(9)$

　　注意，如果设置 k=1$k=1$，滤波器将成为 GCN 滤波器。
　　为选择最优 k$k$，需要计算特征值 Λ~$\tilde{\mathrm{\Lambda }}$ 的分布（由 L~sym=U~Λ~U~−1${\tilde{\mathbf{L}}}_{sym}=\tilde{\mathbf{U}}\tilde{\mathrm{\Lambda }}{\tilde{U}}^{-1}$ 分解得到）。

　　x~$\tilde{\mathbf{x}}$ 的平滑度是

　　　　R(L,x~)=x~⊤Lx~x~x~=∑ni=1p′2iλi∑ni=1p′2i(10)$R(\mathbf{L},\tilde{\mathbf{x}})=\frac{{\tilde{\mathbf{x}}}^{\mathrm{\top }}\mathbf{L}\tilde{\mathbf{x}}}{\tilde{\mathbf{x}}\stackrel{\mathbf{~}}{\mathbf{x}}}=\frac{\sum _{i=1}^n{p}^{\mathrm{\prime }}{}_i^2{\lambda }_i}{\sum _{i=1}^n{p}^{\mathrm{\prime }}{}_i^2}(10)$

　　因此，p′2i$p^{\mathrm{\prime }}{}_i^2$ 应随 λi${\lambda }_i$ 的增加而减少。将最大特征值表示为 λmax${\lambda }_{max}$，理论上，如果 k>1/λmax$k>1/{\lambda }_{max}$ ，滤波器在 (1/k,λmax]$(1/k,{\lambda }_{max}]$ 内不是低通，因为 p′2i$p^{\mathrm{\prime }}{}_i^2$ 在这个间隔内增加；如果 k<1/λmax$k<1/{\lambda }_{max}$ 该滤波器不能使去出高频噪声部分。因此，k=1/λmax$k=1/{\lambda }_{max}$ 是最优选择。

　　[7] 证明了拉普拉斯特征值的范围在 0~2$\text{0~2}$ 之间，因此GCN滤波器在 (1,2]$(1,2]$ 区间内不是低通的。工作 [31] 相应地选择了 k=1/2$k=1/2$，然而，我们的实验表明，在重整化后，最大特征值 λmax${\lambda }_{max}$ 将缩小到 3/2$3/2$ 左右，这使得 1/2$1/2$ 不是最优。在实验中，我们计算每个数据集的 λmax${\lambda }_{max}$，并设置 k=1/λmax$k=1/{\lambda }_{max}$，并进一步分析了不同 k$k$ 值的影响。

3 Adaptive Encoder

　　通过 t$t$ 层拉普拉斯平滑过滤，输出特征更平滑，保持丰富的属性信息。本文自适应地选择高相似度的节点对作为正训练样本，而低相似度的节点对作为负训练样本。

　　给定过滤后的节点特征 X~$\tilde{\mathbf{X}}$，节点嵌入由线性编码器 f$f$ 进行编码：

　　　　Z=f(X~;W)=X~W(11)$\mathbf{Z}=f(\tilde{\mathbf{X}};\mathbf{W})=\tilde{\mathbf{X}}\mathbf{W}(11)$

　　其中，W$\mathbf{W}$ 是权重矩阵。然后，为度量节点的成对相似度，利用余弦相似度。相似度矩阵 S$S$ 为：

　　　　S=ZZT∥Z∥22(12)$\mathrm{S}=\frac{{\mathrm{Z}\mathrm{Z}}^{\mathit{T}}}{\Vert \mathrm{Z}{\Vert }_2^2}(12)$

　　接下来，我们将详细描述我们的训练样本选择策略。

3.1 Training Sample Selection.

　　在计算相似矩阵后，对相似序列按降序排列。这里 rij$r_{ij}$ 是节点对的排序位置  (vi,vj)$(v_i,v_j)$。然后将正样本的最大排序位置设为 rpos$r_{pos}$，将负样本的最小排序位置设为 rneg$r_{neg}$。因此，为节点对 (vi,vj)$(v_i,v_j)$ 生成的标签为

　　lij=⎧⎩⎨⎪⎪10 None rij≤rposrij>rneg otherwise (13)$l_{ij}=\{\begin{array}{ll}1& r_{ij}\le r_{pos}\\ 0& r_{ij}>r_{neg}\\ \text{ None }& \text{ otherwise }\end{array}(13)$

　　这样，构造了一个包含  rpos $r_{\text{pos }}$  个正样本和  n2−rneg$n^2-r_{neg}$  个负样本的训练集。在第一次构造训练集时，由于编码器没有被认训练， 直接使用平滑的特征来初始化  S$\mathbf{S}$  :

　　　　S=X˜X˜T∥X˜∥22(14)$\mathbf{S}=\frac{\tilde{\mathbf{X}}{\tilde{\mathbf{X}}}^{\mathbf{T}}}{\Vert \tilde{\mathbf{X}}{\Vert }_2^2}(14)$

　　构造好训练集后，可以用监督的方式训练编码器。在真实世界的图中，不相似的节点对总是远远多于正节点对，因此在训 练集中选择多于  rpos$r_{pos}$  个负样本。为了平衡正/负样本，在每次迭代中随机选择  rpos$r_{pos}$  个负样本。平衡训练集用  O$\mathcal{O}$  表示。因 此，交叉熵损失表示如下:

　　　　L=∑(vi,vj)∈O−lijlog(sij)−(1−lij)log(1−sij)(15)$\mathcal{L}=\sum _{(v_i,v_j)\in O}-l_{ij}\log \left(s_{ij}\right)-(1-l_{ij})\log (1-s_{ij})(15)$

3.2 Thresholds Update

　　本文为 rpos$r_{pos}$ 和 rneg$r_{neg}$ 设计了一个特定的更新策略来控制训练集的大小。在训练开始时，选择更多的样本为编码器寻找粗化的聚类。之后，保留具有更高置信度的样本进行训练，将迫使编码器捕获细化的聚类。

　　在实践中，随着训练过程的进行，rpos $r_{\text{pos }}$ 减少，而 rstneg$r_{neg}^{st}$ 呈线性增加。将初始阈值设置为 rstpos $r_{\text{pos }}^{st}$ 和 rstneg$r_{neg}^{st}$，最终阈值设置为 redpos $r_{\text{pos }}^{ed}$ 和 redneg$r_{neg}^{ed}$ 。有 redpos ≤rstpos $r_{\text{pos }}^{ed}\le r_{\text{pos }}^{st}$ 和 redneg≥rstneg. $r_{neg}^{ed}\ge r_{\text{neg. }}^{st}$。假设阈值被更新为 T$T$次，我们将更新策略表示为

　　　　r′pos =rpos+redpos −rstpos T(16)$r_{\text{pos }}^{\mathrm{\prime }}=r_{pos}+\frac{r_{\text{pos }}^{ed}-r_{\text{pos }}^{st}}{T}(16)$

　　　　r′neg=rneg+redneg−rstnegT(17)$r_{neg}^{\mathrm{\prime }}=r_{neg}+\frac{r_{neg}^{ed}-r_{neg}^{st}}{T}(17)$

　　随着训练过程的进行，每次阈值更新时，都会重建训练集并保存嵌入。

　　对于节点聚类，我们对保存嵌入的相似矩阵进行谱聚类[22]，利用戴维斯堡丁索引[8](DBI)选择最佳时期，在没有标签信息的情况下测量聚类质量。对于链路预测，我们在验证集上选择执行得最好的历元。Algorithm 1 给出了计算嵌入矩阵 Z$Z$ 的总体过程。

　　

4 Experiments

数据集

　　

节点聚类

　　 

-----------------------------------------------------------------------------------------------------

https://zhuanlan.zhihu.com/p/440760513

https://zhuanlan.zhihu.com/p/432080955

 

• 论文信息
• 1 Introduction
• 2 Method
•     2.1 Laplacian Smoothing Filter
•         2.1.1 Analysis of Smooth Signals
•         2.1.2 Generalized Laplacian Smoothing Filter
•         2.1.3  The Choice of k
• 3 Adaptive Encoder
•     3.1 Training Sample Selection.
•     3.2 Thresholds Update
• 4 Experiments

__EOF__