论文阅读"Adaptive Graph Encoder for

作者: 掉了西红柿皮_Kee | 来源:发表于2021-10-19 12:42 被阅读0次

Cui G, Zhou J, Yang C, et al. Adaptive graph encoder for attributed graph embedding[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020: 976-985.

摘要翻译：
属性图嵌入从图的拓扑和节点特征中学习向量表示，是图分析的一项具有挑战性的任务。近年来，基于图卷积网络(GCNs)的方法在这一任务上取得了很大的进展。然而，现有的基于GCN的方法有三个主要的缺点。（1）实验表明，图卷积滤波器和权重矩阵的纠缠会损害其性能和鲁棒性。（2）作者证明了这些方法中的图卷积滤波器是广义拉普拉斯平滑滤波器的特殊情况，但它们没有保持最优的低通特性。（3）关于现有算法的训练目标通常是重构邻接矩阵或特征矩阵，这并不总是与现实应用相一致。为解决上述问题，论文提出了一种新的属性图嵌入框架----自适应图编码器(AGE)。AGE共有两个模块：（1）为了更好地缓解节点特征中的高频噪声，AGE首先应用了一个精心设计的拉普拉斯平滑滤波器。（2）AGE采用了一种自适应编码器，迭代地加强过滤后的特征，以获得更好的节点嵌入。提出的模型，在节点聚类和连接预测任务上的性能明显优于最先进的图嵌入方法。

模型浅析：

问题的形式化
给定一个图的描述 $G=(V,E,X)$ ，其中 $V=\{v_1, v_2,...,v_n\}$ 是 $n$ 个节点对应的顶点集合。 $E$ 是边的集合， $X=[x_1, x_2,....,x_n]^T$ 是一个特征矩阵。图 $G$ 的拓扑结构由邻接矩阵 $A=\{a_{ij} \in R^{n×n} \}$ 来定义。对角矩阵 $D=diag(d_1, d_2, ..., d_n) \in R^{n×n}$ 是 $A$ 的度矩阵。图的拉普拉斯矩阵为 $L=D-A$ 。属性图嵌入的目的是将节点映射到低维嵌入。论文中以 $Z$ 作为嵌入矩阵，获得的嵌入表示应该同时保留图 $G$ 的拓扑结构和特征信息。
对于下游任务，论文中考虑了节点聚类和链接预测。节点聚类任务的目的是将节点划分为 $m$ 个不相交的簇 $G_1, G_2,...,G_m$ ，其中相似的节点应该在同一组中。链路预测任务要求模型预测两个给定节点之间是否存在潜在的边。
总体结构
主要的组件分为：
（1）拉普拉斯平滑过滤器：滤波器 $H$ 作为一个低通滤波器来对特征矩阵 $X$ 的高频分量进行去噪。并以平滑特征矩阵 $\tilde{X}$ 作为自适应编码器的输入。
（2）自适应编码器：为了获得更有代表性的节点嵌入，该模块通过自适应地选择高度相似或不相似的节点对来构建一个训练集。然后以有监督的方式训练编码器。
训练过程结束后，将学习到的节点嵌入矩阵 $Z$ 用于下游任务。
拉普拉斯平滑过滤器
图学习的基本假设是，图上附近的节点应该是相似的，因此 graph manifold（图流形）上的节点特征应该是光滑的。在此启发下，作者给出了广义拉普拉斯平滑滤波器的定义，并证明了它是一个平滑算子。并回答了如何设计一个最优的拉普拉斯平滑滤波器。
（1）平滑信号分析
作者从图信号处理的角度解释“smooth”。以 $x∈R^n$ 作为图信号，其中每个节点都分配一个标量。将过滤矩阵记为 $H$ 。为了计算图信号 $x$ 的平滑性，首先可以在图拉普拉斯矩阵 $L$ 和 $x$ 上计算Rayleigh quotient $R(L,x)$ ：
Rayleigh quotient实际上是x的标准化方差分数。由‘平滑信号应该在相邻节点上分配相似的值’。因此，假设Rayleigh quotient较低的信号更平滑。
考虑图的拉普拉斯式的特征分解 $L=U\Lambda U^{-1}$ ，其中 $U∈R^{n×n}$ 包含特征向量； $\Lambda=Diag(\lambda_1, \lambda_2, ..., \lambda_n)$ 是特征向量的对角矩阵。由此，特征向量 $u_i$ 的平滑性为：该式表明越平滑的特征向量与越小的特征值相关联，对于图结构而言，越小的特征值代表着越低的出现频率。由上述（1）（2）两式，可以基于 $L$ 对信号 $x$ 进行分解：
$p_i$ 是特征向量 $u_i$ 对应的系数。 $x$ 的平滑性可以表示为：因此，为了获得更平滑的信号，论文中所设计的滤波器的目标是在保持低频分量的同时过滤掉高频分量。

由于其高计算效率和令人信服的性能，拉普拉斯平滑滤波器经常被用于这个目的。

（2）广义拉普拉斯平滑滤波器：
广义拉普拉斯平滑滤波器定义为：

k

为一个实数。使用过滤矩阵

H

，信号可以被表示为

因此，为了实现低通滤波，频率响应函数

1−kλ

应该是一个递减和非负函数。堆叠

t

个拉普拉斯平滑滤波器，滤波后的特征矩阵

\tilde{X}

表示为:

$x$ 表示图中的信号， $X$ 为图的特征表示矩阵， $H$ 为图上的过滤矩阵（即为滤波器）。

（3）关于 $k$ 的选择
在实际的实验中，对邻接矩阵 $A$ 使用重正则化技巧得到 $\tilde{A}=I+A$ ，并且对图拉普拉斯矩阵进行对称正则化：

\tilde{D}

和

\tilde{L}

分别是

\tilde{A}

对应的度矩阵和拉普拉斯矩阵。
所以（5）式可以转换为：

对于

k

值的选择，作者将其和拉普拉斯的矩阵分解

\tilde{L}_{sym}=\tilde{U}\tilde{\Lambda}\tilde{U}^{-1}

的特征值进行联系。类比（4）式，

\tilde{x}

的平滑性表示为：

{p'}_i^2

因随着

\lambda_i

的增加而减少。设最大的特征值为

\lambda_{max}

。
理论上，如果

k>1/λ_{max}

，滤波器在

(1/k，λ_{max}]

区间not low-pass，因为

{p'}_i^2

在该区间内增加；
相反，若

k<1/λ_{max}

，该滤波器不能对所有的高频组件进行去噪。因此，

k=1/λ_{max}

是最佳选择。

目前工作关于k的选择：

自适应编码器
为了从平滑特征中学习更好的节点嵌入，作者利用了受深度自适应学习启发的成对节点相似性用来监督整个训练过程。对于属性图嵌入任务，两个节点之间的关系是至关重要的，这需要训练目标是合适的相似度度量。基于gae的方法通常选择邻接矩阵作为节点对的真实标签。然而，论文中认为邻接矩阵只记录一跳结构信息，这是不够的。同时，通过前一个模块（平滑滤波）将结构和特征结合在一起，解决了特征的平滑问题或使得训练嵌入的相似性更准确。由此，作者自适应选择高相似的节点对作为正训练样本，低相似的节点对作为负样本。
给定滤波后的节点特征矩阵 $\tilde{X}$ ，使用线性编码器对节点表示进行编码操作：并计算了特征矩阵对应的相似矩阵表示 $S$ ：

(1)训练样本的选择：
在计算相似矩阵后，将成对相似序列按降序排序。记 $r_{ij}$ 是节点对的排序 $(v_i, v_j)$ 。然后将正例样本的最大排序设为r_{pos}，负例样本的最小排序设为 $r_{neg}$ 。由此，产生节点对的标签信息：
这样就构建了一个包含 $r_{pos}$ 个正例样本和 $n^2−r_{neg}$ 个负例样本的训练集。对于第一次构造训练集的相似矩阵由平滑后的特征表示 $\tilde{X}$ 得到：在构建了训练集后，以有监督的方式训练编码器。在现实世界的图中，负例的节点对总是比正例节点对多得多，为了平衡正例/负例样本，作者在每个Epoch随机选择 $r_{pos}$ 负例样本。
(2)阈值的更新：
我们为 $r_{pos}$ 和 $r_{neg}$ 设计了一个特定的更新策略来控制训练集的大小。在训练过程开始时，为编码器选择更多的样本来寻找粗糙的聚类模式。在那之后，保留具有更高可信度的样本用于训练，迫使编码器捕获精细的模式。在实验中，随着训练过程的进行， $r_{pos}$ 减少，而r_{neg}$呈线性增加。随着训练过程的进行，每次更新阈值时，模型会重建训练集并保存嵌入。
整体算法如下：