12.Graph Embedding(续) - 十九、AANE - 《AI算法工程师手册》

十九、AANE
- 19.1 模型
- 19.2 实验

十九、AANE

在很多实际应用中，网络顶点通常会伴随着一组丰富的属性或特征，即属性网络 attributed network。因此，在对顶点embedding 建模的过程中考虑顶点属性会有所帮助，即 attributed network embedding:ANE 。但是，ANE 在以下三个方面具有挑战性：
- 算法复杂度：较高的算法复杂度限制了某些 ANE 算法在实际任务中的应用。已有一些算法基于网络的结构信息和属性信息来学习顶点embedding，但是这些算法要么在每个迭代step 中使用了复杂度的特征值分解，要么使用了收敛速度很慢的梯度下降。
- heterogeneous 异质信息：由于同时引入了结构信息和属性信息，因此如何在网络的结构和属性的联合空间中评估顶点的邻近度（即距离）是一个挑战。
  
  另外，随着网络规模的扩大，顶点的属性邻近度矩阵通常非常庞大，难以存储到单台计算机上，更别提对它进行操作。
- 噪音：网络结构信息和顶点属性信息可能都是残缺的、带噪音的，这进一步加入了顶点 embedding 学习的难度。
因此，现有方法无法直接应用于 scalable 的 attributed network embedding 。为解决该问题，论文 《Accelerated Attributed Network Embedding》 提出了一种加速属性网络 embedding 算法 accelerated attributed network embedding:AANE 。

一方面， AANE 将顶点属性纳入到顶点 embedding 过程中；另一方面，AANE 提出了一种分布式优化算法，该算法将复杂的建模和优化过程分解为很多子问题，从而能够以分布式方式完成联合学习。

19.1 模型

设为一个网络，其中为顶点集合，为定输数量，为边的集合，为权重矩阵。定义顶点的直接邻接顶点为，其大小为。
- 每条边关联一个权重。这里我们关注于无向图，因此有。
  - 更大的意味着顶点和之间产生更强的关联，或者说更大的相似性。
  - 意味着顶点和之间不存在边。
- 定义顶点的属性向量为，其中为属性的维度。定义属性矩阵为，其中为的第行。
定义attributed network embedding 为：给定网络以及属性矩阵，任务的目的是给出每个顶点一个低维embedding 向量，使得embedding 向量能够同时保留顶点的结构邻近关系、顶点的属性邻近关系。
ANE 需要保留网络的结构邻近关系，为此 AANE 提出两个假设：
- 首先，假设基于图的映射在边上是平滑的，特别是对于顶点密集的区域。即图上映射的连续性假设。
- 其次，边的权重更大的一对顶点更有可能具有相似的 embedding 。
因此 AANE 提出以下损失函数来最小化相连顶点之间的 embedding 差异：

当较大时（顶点和相似性更大），为最小化，和的距离将减小。
ANE 需要保留网络的属性邻近关系，AANE 考虑利用顶点的 embedding 内积来逼近顶点的属性相似性。

假设顶点和的属性相似性为，这里我们直接使用 cosin 相似度。因此有：

AANE 提出以下损失函数来最小化顶点之间的属性损失：

其中为顶点之间的属性相似度矩阵；embedding 矩阵为，其中为的第行。
现在我们有两个损失函数和，它们分别对顶点结构邻近度、顶点属性邻近度进行建模。为了对这两种邻近度在一个统一的、信息互补的联合空间中建模，AANE 模型为：

其中用于平衡网络结构损失和属性损失：
- 当时，网络的结构不影响最终的顶点 embedding，顶点 embedding 由顶点的属性决定。
- 当时，最优解倾向于使得所有顶点的 embedding 相同（即），此时所有顶点在embedding 空间中形成单个簇 cluster 。
因此我们可以通过调节从而调整 embedding 空间中簇的数量。
AANE 可以视为带正则化项的矩阵分解，其中将分解为。在分解过程中施加了基于网络结构的正则化，该正则化迫使相连的顶点在 embedding 空间中彼此靠近。
AANE 的目标函数不仅可以对网络结构邻近度和顶点属性邻近度进行联合建模，而且它还具有特殊的设计，从而能够更有效地优化：对每个都是独立的，因此可以重新表述为双凸优化问题 bi-convex optimization 。

令，为的第行。因此有：

则目标函数重写为：

这表明对每个和都是独立的。

考虑到上式的每一项都是凸函数，因此这是一个双凸优化问题。因此我们可以将原始问题划分为个更小的凸优化子问题。但是，对于这个子问题无法获得闭式解，所以我们参考交替乘子法 Alternating Direction Method of Multipliers:ADMM 的做法：将学习过程转换为个子问题的更新step 和一个矩阵更新 step 。

引入增强的拉格朗日函数：

其中为对偶变量，为罚项参数。

我们可以交替优化从而得到的极小值点。为对偶变量构成的矩阵，其中为的第行。对于顶点，在第个 step 的更新为：

根据偏导数为零，我们解得和：

由于每个子问题都是凸的，因此当时就是极值点。因此当和足够接近时，停止迭代。

由于原始问题是一个 bi-convex 问题，因此可以证明我们方法的收敛性，确保算法收敛到一个局部极小值点。

这里有几点需要注意：
- 在计算之前必须计算所有的。
- 计算之间是相互独立的。
- 机器内存有限，则也可以不必存储相似度矩阵，而是需要的时候相互独立计算：
  
  其中为的第项，为逐元素积。
为了进行适当的初始化，我们在第一次迭代中将初始化为的左奇异值。其中为一个矩阵，它包含了的前列。
AANE 将优化过程分为个子问题，然后迭代地求解它们。在每轮迭代过程中，可以分布式地将（或者）的个更新 step 分配给个 worker 。当原始残差或者对偶残差足够小时，停止迭代。

整体而言，AANE 优化算法具有以下优点：
- 或的个更新step 之间彼此独立。因此，在每轮迭代过程中，全局调度器可以将子优化任务分派给 worker ，无需考虑子任务之间的顺序。
- 每个子任务的算法复杂度都很低。
- 算法很快就能够收敛到一个合适的解。
AANE 优化算法：
- 输入：
  - 图
  - 顶点属性矩阵
  - embedding 维度
  - 收敛阈值
- 输出：所有顶点的 embedding 矩阵
- 步骤：
  - 从属性矩阵中提取前列，构成
  - 初始化：，为的左奇异向量，，
  - 计算属性相似度矩阵
  - 迭代，直到残差或者对偶残差。迭代步骤为：
    - 计算
    - 分配个子任务到个 worker，然后更新：对于计算。
    - 计算
    - 分配个子任务到个 worker，然后更新：对于计算。
    - 计算
    - 更新
  - 返回
下图说明了 AANE 的基本过程：给定一个包含个顶点的图，首先通过和来分解属性邻近度矩阵，在分解过程中增加了基于边的惩罚项，使得相连的顶点在 embedding 空间中彼此靠近。这种惩罚由来控制。

在优化过程中，我们将原始问题划分为个复杂度很低的子问题：前 6 个子问题相互独立、后 6 个子问题也相互独立。因此所有子问题可以分配给个 worker 。

在最终输出中，顶点 1 和 3 的 embedding 分别为以及。它们距离非常接近，这表明它们在原始结构和属性的联合空间中彼此相似。
由于AANE 的优化算法是一个典型的 ADMM 算法，因此训练算法在迭代很少的几个 step 之后就能收敛到很高的精度。
- 在初始化步骤，由于需要计算奇异值向量，因此计算复杂度为
- 在每个子任务过程中，更新的计算复杂度为。注意：我们只需要在每轮迭代中计算一次。由于，因此其计算复杂度为。
  
  另外，可以验证每个子任务的空间复杂度为。
因此 AANE 总的时间复杂度为，其中为矩阵的非零元素数量，为 worker 数量。

19.2 实验

数据集：
- BlogCatalog 数据集：一个博客社区，用户彼此关注从而构成一个网络。用户可以生成关键词来作为其博客的简短描述，我们将这些关键词作为顶点（用户）的属性。用户也可以将其博客注册为指定的类别，我们将这些类别作为用户的 label 。
  
  没有关注或者没有指定类别的用户从网络中剔除。
- Flickr 数据集：一个在线图片共享社区，用户彼此关注从而构成一个网络。用户可以为图片指定 tag ，我们将这些 tag 作为顶点（用户）的属性。用于可以加入不同的组，我们将这些组作为用户的 label 。
- Yelp 数据集：一个类似大众点评的本地生活评论网站。我们基于用户的社交关系来构成一个网络。我们从用户的评论中利用bag-of-word 抽取文本信息来作为用户的属性信息。所有本地商家分为 11 个主要类别，如 Active Life, Fast Food, Services... ，我们将用户所点评的商家的类别作为用户的 label 。
baseline 模型：为评估顶点属性的贡献，我们对比了 DeepWalk,LINE,PCA 等模型，这些baseline 模型仅能处理网络结构或者顶点属性，无法处理二者的融合；为了对比AANE 的效率和效果，我们对比了其它的两种 ANE 模型 LCMF, MultiSpec 。
- DeepWalk：使用 SkipGram 学习基于图上的随机游走序列从而得到图的 embedding 。
- LINE：建模图的一阶邻近度和二阶邻近度从而得到图的 embedding 。
- PCA：经典的降维技术，它将属性矩阵的 top d 个主成分作为图的 embedding 。
- LCMF：它通过对网络结构信息和顶点属性信息进行联合矩阵分解来学习图的 embedding 。
- MultiSpec：它将网络结构和顶点属性视为两个视图 view ，然后在两个视图之间执行 co-regularizing spectral clustering 来学习图的 embedding 。
所有模型的 embedding 维度设置为。

在所有实验中，我们首先在图上学习顶点的 embedding，然后根据学到的 embedding 向量作为特征，来训练一个SVM 分类模型。分类模型在训练集上训练，然后在测试集上评估Macro-F1 和 Micro-F1 指标。

在训练SVM 时，我们使用五折交叉验证。所有的顶点被随机拆分为训练集、测试集，其中训练集和测试集之间的所有边都被移除。考虑到每个顶点可能属于多个类别，因此对每个类别我们训练一个二类 SVM 分类器。

所有实验均随机重复 10 并报告评估指标的均值。
我们首先评估这些方法的效果。我们分别将分类训练集的规模设置为 10%,25%,50%,100%。其中，由于 Yelp 数据集的规模太大，大多数ANE 方法的复杂度太高而无法训练，因此我们随机抽取其 20% 的数据并设置为新的数据集，即 Yelp1 。

所有模型的分类效果如下所示：

所有模型在完整的 Yelp 数据集上的分类效果如下所示，其中 PCA,LCMF,MultiSpec 因为无法扩展到如此大的数据集，因此不参与比较：

结论：
- 由于利用了顶点的属性信息，因此LCMF,MultiSpec,AANE 等属性网络embedding 方法比 DeepWalk,LINE 等网络结构embedding 方法效果更好。
- 我们提出的 AANE 始终优于 LCMF, MultiSpec 方法。
- LCMF,MultiSpec 方法无法应用于大型数据集。
然后我们评估这些方法的训练效率。我们将 AANE 和 LCMF,MultiSpec 这些属性网络 embedding 方法进行比较。下图给出了这些模型在不同数据集上、不同顶点规模的训练时间。

结论：
- AANE 的训练时间始终比 LCMF 和 MultiSpec 更少。
- 随着顶点规模的增加，训练效率之间的 gap 也越来越大。
- AANE 可以在多线程环境下进一步提升训练效率。
参数敏感性：这里我们研究参数和的影响。
- 参数平衡了网络结构和顶点属性之间的贡献。为研究的影响，我们将其从变化到，对应的分类 Micro-F1 效果如下所示。
  - 当接近于 0 时，模型未考虑网络结构信息。随着的增加，AANE 开始考虑网络结构，因此性能不断提升。
  - 当接近 0.1 时，模型在 BlogCatalog 和 Flickr 上的效果达到最佳。随着的继续增加，模型性能下降。因为较大的倾向于使得所有顶点具有相同的 embedding 。
- 为研究 embedding 维度的影响，我们将从 10 变化到 180，对应的分类 Micro-F1 效果如下所示。我们仅给出 Flickr 数据集的结果，BlogCatalog 和 Yelp 的结果也是类似的。
  
  可以看到：
  - 无论为多少，DeepWalk 和 LINE 都不如属性网络 embedding 方法（AANE,LCMF,MultiSpec ）
  - 无论为多少，AANE 的效果始终最佳。
  - 当增加时，这些模型的效果先提高、然后保持稳定。这表示低维 embedding 已经能够捕获大多数有意义的信息。