一、AANE [2017]

《Accelerated Attributed Network Embedding》

1. 网络分析已经成为许多实际应用中的有效工具，例如精准营销 （targeted marketing） 和基因分析。识别有效特征对于这些任务至关重要，但是这涉及大量的人力和大规模的工程实验。作为替代方案，network embedding 将每个节点的拓扑结构（topological structure）映射为低维的向量represetnation ，从而可以很好地保留原始网络邻近性（proximity） 。已有工作表明，network embedding 可以使各种任务收益，例如节点分类、链接预测、网络聚类。

   虽然现有的 network embedding 算法专注于纯网络 （pure network），但是现实世界网络中的节点通常关联一组丰富的特征或属性，这称作属性网络（attributed network） 。像同质性（ homophily） 和社交影响 （social influence） 等社会科学理论表明：节点属性与网络结构高度相关，即一方的形成取决于并影响了另一方。例如，微博中用户帖子和“关注” 关系之间的强关联，论文主题和引用关系的高度相关性。在各种应用中，已有工作表明联合利用这两个信息源（即节点拓扑结构和节点属性）可以提高学习性能。受到这些的启发，论文《Accelerated Attributed Network Embedding》提出研究节点特征是否可能有助于学到更好的 embedding representation 。

   此外，现实世界的网络通常是大规模的，具有大量节点和高维特征。例如，截至 2016 年，美国每月有超过 6500 万活跃的 Twitter 用户，每个用户可以发布数千条推文。这对 embedding 算法的可扩展性提出了更高的要求。属性网络 embedding 在以下三个方面具有挑战性：

   • 高的时间复杂度可能是限制算法在实践中应用的瓶颈。一些工作致力于利用网络结构和属性信息来寻找低秩（low-rank ）的潜在 representation 。它们要么在每次迭代中需要具有 $O(n^3)$$O(n^3)$ 时间复杂度的特征分解（ eigen-decomposition）（其中 $n$$n$ 为节点的总数），要么采用通常收敛速度较慢的梯度下降。

   • 由于异质信息（heterogeneous information）的各种组合，在网络和属性的联合空间中评估节点邻近性（node proximity）具有挑战性。另外，随着网络规模的扩大，节点属性邻近性（node attribute proximity） 矩阵往往太大，无法存储在单机上，更不用说对它的操作了。因此，如果 embedding 算法也是可扩展的，那么将很有吸引力。

   • 两个信息源都可能不完整（incomplete） 的且充满噪音 （noisy）的，这进一步加剧了 embedding representation learning 问题。

   因此，鉴于数据的独有特性，现有方法不能直接应用于可扩展的、属性网络的 embedding 。为了应对上述挑战，论文研究了在属性网络上有效地学习 embedding representation 的问题。论文旨在回答以下问题：

   • 如何在网络结构和节点属性组成的联合空间中有效地建模节点邻近性？

   • 如何使 vector representations learning 过程具有可扩展性（scalable ）和高效 （efficient） ？

   通过调研这些问题，论文提出了一个称作 Accelerated Attributed Network Embedding: AANE 的新框架。总之，本文贡献如下：

   • 正式定义属性网络 embeding 问题。

   • 提出一个可扩展的、高效的框架 AANE 。AANE 通过将节点属性邻近性纳入 network embedding，从而学到有效的、统一的 embedding representation 。

   • 提出一种分布式优化算法。该算法将复杂的建模和优化问题分解为许多低复杂度的子问题，使得 AANE 能够高效地处理每个节点。

   • 在三个真实数据集上验证了 AANE 的效率和效果。

2. 相关工作：

   network embedding 已经成为处理大规模网络的有效工具。人们已经从各个方面进行了努力。

   • 《Scalable learning of collective behavior based on sparse social dimensions》 提出了一种 edge-centric 的聚类方案，从而提高学习效率并减轻内存需求。

   • 《Distributed large-scale natural graph factorization》 提出了一种基于随机梯度下降的分布式矩阵分解算法来分解大规模图。

   • 《LINE: Large scale Information Network Embedding》 通过将weighted edge 展开（ unfolding）为多个binary edge 来提高随机梯度下降的效率。

   • 《Asymmetric transitivity preserving graph embedding》 设计了一种 Jacobi-Davidson 类型的算法来近似和加速 high-order proximity embedding 中的奇异值分解。

   • 《Structural deep network embedding》 涉及深度架构从而有效地嵌入节点的一阶邻近性和二阶邻近性。

   人们已经研究并分析了各个领域中的属性网络，并表明：通过联合利用几何结构和节点属性来提高学习性能变得越来越有希望。

   • 《What's in a hashtag? content based prediction of the spread of ideas in microblogging communities》 通过利用内容和拓扑特征改善了对思想（ideas）传播的预测。

   • 《Exploring context and content links in social media: A latent space method》 基于 pairwise 相似性对内容信息进行建模，并通过学习语义概念semantic concept 之间的结构相关性（structural correlation），从而将内容信息与上下文链接一起映射到语义潜在空间中。

   • 《Probabilistic latent document network embedding》 通过为网络链接和文本内容找到一个联合的低维 representation，从而为文档网络提出了一个基于概率的框架。

   • 《Heterogeneous network embedding via deep architectures》 设计了一种深度学习方法，将丰富的链接信息和内容信息映射到潜在空间，同时捕获跨模态数据之间的相关性。

   属性网络分析不同于多视图学习。属性网络的网络结构不止一个视图，其底层属性很复杂，包括连通性（connectivity ）、传递性（transitivity） 、一阶和更高阶的邻近性等等。

1.1 模型

1.1.1 基本概念

1. 设 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})$$\mathcal G=(\mathcal V,\mathcal E,\mathbf W)$ 为一个网络，其中 $\mathcal{V}=\{v_1,\cdots ,v_n\}$$\mathcal V=\{v_1,\cdots,v_n \}$ 为节点集合，$n$$n$ 为节点数量，$\mathcal{E}$$\mathcal E$ 为边的集合，$\mathbf{W}=\{w_{i,j}\}\in {\mathbb{R}}^{n\times n}$$\mathbf W=\{w_{i,j}\}\in \mathbb R^{n\times n}$ 为边的权重矩阵。定义节点 $v_i$$v_i$ 的直接邻居节点为 $\mathcal{N}(v_i)$$\mathcal N(v_i)$ ，其大小为 $N_i$$N_i$ 。

   每条边 $(v_i,v_j)\in \mathcal{E}$$(v_i,v_j)\in \mathcal E$ 关联一个权重 $w_{i,j}\ge 0$$w_{i,j}\ge 0$ 。这里我们关注于无向图，因此有 $w_{i,j}=w_{j,i}$$w_{i,j} = w_{j,i}$ 。更大的 $w_{i,j}$$w_{i,j}$ 意味着节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间产生更强的关联，或者说更大的相似性。$w_{i,j}=0$$w_{i,j} = 0$ 意味着节点 $v_i$$v_i$ 和 $v_j$$v_j$ 之间不存在边。

   定义节点 $v_i$$v_i$ 的属性向量为 ${\overrightarrow{\mathbf{a}}}_i\in {\mathbb{R}}^m$$\mathbf{\vec a}_i\in \mathbb R^m$ ，其中 $m$$m$ 为属性的维度。定义属性矩阵为 $\mathbf{A}\in {\mathbb{R}}^{n\times m}$$\mathbf A\in \mathbb R^{n\times m}$ ，其中 ${\overrightarrow{\mathbf{a}}}_i$$\mathbf{\vec a}_i$ 为 $\mathbf{A}$$\mathbf A$ 的第 $i$$i$ 行。

   定义attributed network embedding 为：给定网络 $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})$$\mathcal G=(\mathcal V,\mathcal E,\mathbf W)$ 以及属性矩阵 $\mathbf{A}$$\mathbf A$ ，任务的目的是给出每个节点 $v_i\in \mathcal{V}$$v_i\in \mathcal V$ 一个低维embedding 向量 ${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec h}_i\in \mathbb R^d$ ，使得embedding 向量能够同时保留节点的结构邻近关系、节点的属性邻近关系。所有节点的 embedding 向量构成 embedding 矩阵 $\mathbf{H}\in {\mathbb{R}}^{n\times d}$$\mathbf H\in \mathbb R^{n\times d}$ 。

1.1.2 AANE

1. 现实世界属性网络的理想 embedding 方法需要满足以下三个要求：

   • 首先，它需要能够处理任意类型的边（如，无向/有向边、无权/带权边）。

   • 其次，它需要同时在网络空间和属性空间中都很好地保持节点邻近性。

   • 最后，可扩展性很重要，因为节点的数量 $n$$n$ 和属性维度 $m$$m$ 可能很大。

   为此，我们开发了一个满足所有要求的、有效的、高效的框架 AANE。这里我们将描述 AANE 如何以有效的方式联合建模网络结构邻近性和属性邻近性。

2. 网络结构建模：为了保持 $\mathcal{G}$$\mathcal G$ 中的节点邻近性， AANE 提出两个假设：

   • 首先，假设基于图的映射（graph-based mapping） 在边上是平滑的，特别是对于节点密集的区域。这符合 “聚类假设”（ cluster hypothesis ）。

   • 其次，具有更相似拓扑结构或由更高权重连接的一对节点更有可能具有相似的 embedding 。

   为了实现这些目标，我们提出以下损失函数来最小化相连节点之间的 embedding 差异：

   $${\mathcal{J}}_{\mathcal{G}}=\sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$

   其中 ${\overrightarrow{\mathbf{h}}}_i,{\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_i,\mathbf{\vec h}_j$ 分别为节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的 embedding representation，$w_{i,j}$$w_{i,j}$ 是节点 $v_i,v_j$$v_i,v_j$ 之间边的权重。核心思想是：为最小化 ${\mathcal{J}}_{\mathcal{G}}$$\mathcal J_\mathcal G$ ，当 $w_{i,j}$$w_{i,j}$ 较大时（节点 $v_i$$v_i$ 和 $v_j$$v_j$ 相似性更大），模型将迫使 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 ${\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_j$ 的距离较小。

3. 属性邻近性建模：节点的属性信息与网络拓扑结构紧密相关。网络空间中的节点邻近性应该与节点属性空间中的节点邻近性一致。为此，我们研究如何使得 embedding representation $\mathbf{H}$$\mathbf H$ 也很好地保持节点属性的邻近性。

   受对称矩阵分解（symmetric matrix factorization）的启发，我们提出使用 $\mathbf{H}$$\mathbf H$ 和 ${\mathbf{H}}^{\mathrm{\top }}$$\mathbf H^\top$ 的乘积来近似属性亲和矩阵 （attribute affinity matrix） $\mathbf{S}\in {\mathbb{R}}^{n\times n}$$\mathbf S\in \mathbb R^{n\times n}$ 。基本思想是：强制 embedding representation ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 ${\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_j$ 的内积与对应的属性相似性 $s_{i,j}$$s_{i,j}$ 相同。在数学上，该损失函数定义为：

   $${\mathcal{J}}_A=\sum _{i=1}^n\sum _{j=1}^n{(s_{i,j}-{\overrightarrow{\mathbf{h}}}_i\cdot {\overrightarrow{\mathbf{h}}}_j)}^2={\Vert \mathbf{S}-\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}\Vert }_F^2$$

   其中亲和矩阵可以通过节点属性相似性来计算，具体而言这里我们采用余弦相似度。假设节点 $v_i$$v_i$ 和 $v_j$$v_j$ 的属性相似性为 $s_{i,j}$$s_{i,j}$ ，即 $s_{i,j}={\overrightarrow{\mathbf{a}}}_i\cdot {\overrightarrow{\mathbf{a}}}_j$$s_{i,j} = \mathbf{\vec a}_i \cdot \mathbf{\vec a}_j$ 。

   计算亲和矩阵的时间复杂度为 $O(n^2)$$O(n^2)$，存储亲和矩阵的空间复杂度为 $O(n^2)$$O(n^2)$ 。我们可以对每个节点仅计算和存储最相似属性的 top k 个节点，从而将时间复杂度和空间复杂度降低到 $O(kn)$$O(kn)$ 。

4. Joint Embedding Representation Learning：现在我们有两个损失函数 ${\mathcal{J}}_G$$\mathcal J_G$ 和 ${\mathcal{J}}_A$$\mathcal J_A$，它们分别建模网络拓扑结构中的节点邻近性、节点属性中的节点邻近性。为了对这两种邻近性互补，形成一个统一的联合空间，我们在以下优化问题中对这两种类型的信息进行联合建模：

   $$J={\mathcal{J}}_A+\lambda {\mathcal{J}}_{\mathcal{G}}={\Vert \mathbf{S}-\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}\Vert }_F^2+\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$

   其中 $\lambda$$\lambda$ 用于平衡网络结构损失和属性损失：

   • 当 $\lambda \to 0$$\lambda \rightarrow 0$ 时，网络拓扑结构不影响最终的节点 embedding，。因此每个节点都可以是一个孤立的 cluster。

   • 当 $\lambda \to +\mathrm{\infty }$$\lambda\rightarrow +\infty$ 时，最优解倾向于使得所有节点的 embedding 相同（即 ${\overrightarrow{\mathbf{h}}}_i={\overrightarrow{\mathbf{h}}}_j$$\mathbf{\vec h}_i = \mathbf{\vec h}_j$ ）， 此时所有节点在embedding 空间中形成单个 cluster 。

   因此我们可以通过调节 $\lambda$$\lambda$ 从而调整 embedding 空间中 cluster的数量。

   AANE 可以视为带正则化项的矩阵分解，其中将 $\mathbf{S}$$\mathbf S$ 分解为 $\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}$$\mathbf H \mathbf H^\top$ 。在分解过程中施加了基于网络结构的正则化 $\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{h}}}_j\Vert }_2$$\lambda \sum_{(v_i,v_j)\in\mathcal E} w_{i,j}\left\|\mathbf{\vec h}_i - \mathbf{\vec h}_j\right\|_2$，该正则化迫使相连的节点在 embedding 空间中彼此靠近。

   AANE 仅考虑网络结构的一阶邻近性，无法捕获网络结构的高阶邻近性。

   AANE 仅捕获线性关系，未能捕获非线性关系。

   AANE 分别独立地建模网络结构邻近性和节点属性邻近性，并未建模二者之间的交互。

1.1.3 加速算法

1. AANE 的目标函数不仅联合建模网络结构邻近性和节点属性亲和性，而且它还具有特殊的设计， 从而能够更有效地和分布式地优化：$\mathcal{J}$$\mathcal J$ 对每个 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 都是可分离（separable）的，因此可以重新表述为双凸优化问题 （bi-convex optimization） 。

   如果我们添加一个副本 $\mathbf{Z}=\mathbf{H}$$\mathbf Z = \mathbf H$，${\overrightarrow{\mathbf{z}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec z}_i\in \mathbb R^d$ 为 $\mathbf{Z}$$\mathbf Z$ 的第 $i$$i$ 行。因此有：

   $${\Vert \mathbf{S}-\mathbf{H}{\mathbf{Z}}^{\mathrm{\top }}\Vert }_F^2=\sum _{i=1}^n{\Vert {\overrightarrow{\mathbf{s}}}_i-{\overrightarrow{\mathbf{h}}}_i{\mathbf{Z}}^{\mathrm{\top }}\Vert }_2^2=\sum _{i=1}^n{\Vert {\overrightarrow{\mathbf{s}}}_i-\mathbf{H}{\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}\Vert }_2^2$$

   则目标函数重写为：

   $$\begin{array}{c}\underset{\mathbf{H}}{min}\sum _{i=1}^n{\Vert {\overrightarrow{\mathbf{s}}}_i-{\overrightarrow{\mathbf{h}}}_i{\mathbf{Z}}^{\mathrm{\top }}\Vert }_2^2+\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{z}}}_j\Vert }_2\\ s.t.{\overrightarrow{\mathbf{h}}}_i={\overrightarrow{\mathbf{z}}}_i\end{array}$$

   这表明 $\mathcal{J}$$\mathcal J$ 对每个 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 和 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ 都是可分离的。考虑到上式的每一项都是凸函数，因此这是一个双凸优化问题。因此我们可以将原始问题划分为 $2n$$2n$ 个更小的凸优化子问题。

   但是， 对于这 $2n$$2n$ 个子问题无法获得闭式解，所以我们参考交替乘子法（Alternating Direction Method of Multipliers: ADMM）的做法来加速优化过程：将学习过程转换为 $2n$$2n$ 个子问题的updating step 和一个矩阵 updating step 。

   也可以用随机梯度下降法来求解。这里介绍的优化算法需要 $O(n^2)$$O(n^2)$ 的复杂度，因此对于大型网络是不可行的。

2. 现在我们介绍优化过程的细节。我们首先引入增强的拉格朗日函数：

   $$\mathcal{L}=\sum _{i=1}^n{\Vert {\overrightarrow{\mathbf{s}}}_i-{\overrightarrow{\mathbf{h}}}_i{\mathbf{Z}}^{\mathrm{\top }}\Vert }_2^2+\lambda \sum _{(v_i,v_j)\in \mathcal{E}}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{z}}}_j\Vert }_2+\frac{\rho }{2}\sum _{i=1}^n({\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{z}}}_i+{\overrightarrow{\mathbf{u}}}_i\Vert }_2^2-{\Vert {\overrightarrow{\mathbf{u}}}_i\Vert }_2^2)$$

   其中 ${\overrightarrow{\mathbf{u}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec u}_i\in \mathbb R^d$ 为对偶变量， $\rho >0$$\rho\gt 0$ 为罚项参数。

   我们可以交替优化 $\mathbf{H},\mathbf{Z},\mathbf{U}$$\mathbf H,\mathbf Z,\mathbf U$ 从而得到 $\mathcal{L}$$\mathcal L$ 的极小值点。$\mathbf{U}$$\mathbf U$ 为对偶变量构成的矩阵，其中 ${\overrightarrow{\mathbf{u}}}_i\in {\mathbb{R}}^d$$\mathbf{\vec u}_i\in \mathbb R^d$ 为 $\mathbf{U}$$\mathbf U$ 的第 $i$$i$ 行。对于节点 $v_i$$v_i$ ，在第 $k+1$$k+1$个 step 的更新为：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{(k+1)}=\arg \underset{{\overrightarrow{\mathbf{h}}}_i}{min}({\Vert {\overrightarrow{\mathbf{s}}}_i-{\overrightarrow{\mathbf{h}}}_i{\mathbf{Z}}^{(k{)}^{\mathrm{\top }}}\Vert }_2^2+\lambda \sum _{v_j\in \mathcal{N}(v_i)}{w}_{i,j}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{z}}}_j^{(k)}\Vert }_2+\frac{\rho }{2}{\Vert {\overrightarrow{\mathbf{h}}}_i-{\overrightarrow{\mathbf{z}}}_i^{(k)}+{\overrightarrow{\mathbf{u}}}_i^{(k)}\Vert }_2^2)\\ {\overrightarrow{\mathbf{z}}}_i^{(k+1)}=\arg \underset{{\overrightarrow{\mathbf{z}}}_i}{min}({\Vert {\overrightarrow{\mathbf{s}}}_i-{\mathbf{H}}^{(k+1)}{\overrightarrow{\mathbf{z}}}_i^{\mathrm{\top }}\Vert }_2^2+\lambda \sum _{v_j\in \mathcal{N}(v_i)}{w}_{j,i}{\Vert {\overrightarrow{\mathbf{z}}}_i-{\overrightarrow{\mathbf{h}}}_j^{(k+1)}\Vert }_2+\frac{\rho }{2}{\Vert {\overrightarrow{\mathbf{z}}}_i-{\overrightarrow{\mathbf{h}}}_i^{(k+1)}+{\overrightarrow{\mathbf{u}}}_i^{(k)}\Vert }_2^2)\\ {\mathbf{U}}^{(k+1)}={\mathbf{U}}^{(k)}+({\mathbf{H}}^{(k+1)}-{\mathbf{Z}}^{(k+1)})\end{array}$$

   根据偏导数为零，我们解得 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k+1) }$ 和 ${\overrightarrow{\mathbf{z}}}_i^{(k+1)}$$\mathbf{\vec z}_i^{(k+1) }$ ：

   $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}_i^{(k+1)}=\frac{2{\overrightarrow{\mathbf{s}}}_i{\mathbf{Z}}^{(k)}+\lambda \sum _{v_j\in \mathcal{N}(v_i)}\frac{w_{i,j}{\overrightarrow{\mathbf{z}}}_j^{(k)}}{{\Vert {\overrightarrow{\mathbf{h}}}_i^{(k)}-{\overrightarrow{\mathbf{z}}}_j^{(k)}\Vert }_2}+\rho ({\overrightarrow{\mathbf{z}}}_i^{(k)}-{\overrightarrow{\mathbf{u}}}_i^{(k)})}{2{\mathbf{Z}}^{(k{)}^{\mathrm{\top }}}{\mathbf{Z}}^{(k)}+(\lambda \sum _{v_j\in \mathcal{N}(v_i)}\frac{w_{i,j}}{{\Vert {\overrightarrow{\mathbf{h}}}_i^{(k)}-{\overrightarrow{\mathbf{z}}}_j^{(k)}\Vert }_2}+\rho )\mathbf{I}}\\ {\overrightarrow{\mathbf{z}}}_i^{(k+1)}=\frac{2{\overrightarrow{\mathbf{s}}}_i{\mathbf{H}}^{(k+1)}+\lambda \sum _{v_j\in \mathcal{N}(v_i)}\frac{w_{i,j}{\overrightarrow{\mathbf{h}}}_j^{(k+1)}}{{\Vert {\overrightarrow{\mathbf{z}}}_i^{(k)}-{\overrightarrow{\mathbf{h}}}_j^{(k+1)}\Vert }_2}+\rho ({\overrightarrow{\mathbf{h}}}_i^{(k+1)}+{\overrightarrow{\mathbf{u}}}_i^{(k)})}{2{\mathbf{H}}^{(k+1{)}^{\mathrm{\top }}}{\mathbf{H}}^{(k+1)}+(\lambda \sum _{v_j\in \mathcal{N}(v_i)}\frac{w_{i,j}}{{\Vert {\overrightarrow{\mathbf{z}}}_i^{(k)}-{\overrightarrow{\mathbf{h}}}_j^{(k+1)}\Vert }_2}+\rho )\mathbf{I}}\end{array}$$

   这里我们使用 ${\overrightarrow{\mathbf{h}}}_i^{(k)}$$\mathbf{\vec h}_i^{(k)}$ 来估计距离 ${\Vert {\overrightarrow{\mathbf{h}}}_i^{(k)}-{\overrightarrow{\mathbf{z}}}_j^{(k)}\Vert }_2$$\left\|\mathbf{\vec h}_i^{(k)} -\mathbf{\vec z}_j^{(k)}\right\|_2$ 。《Efficient and robust feature selection via joint $l_{2,1}$$l_{2,1}$ -norms minimization》证明了这种更新规则的单调递减特性。由于每个子问题都是凸的，因此当 ${\overrightarrow{\mathbf{h}}}_i^{(k)}={\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k)} = \mathbf{\vec h}_i^{(k+1)}$ 时 ${\overrightarrow{\mathbf{h}}}_i^{(k)}$$\mathbf{\vec h}_i^{(k)}$ 就是极值点。因此当 ${\overrightarrow{\mathbf{h}}}_i^{(k)}$$\mathbf{\vec h}_i^{(k)}$ 和 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k+1)}$ 足够接近时，停止迭代。

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

   • 在计算 ${\overrightarrow{\mathbf{z}}}_i^{(k+1)}$$\mathbf{\vec z}_i^{(k+1)}$ 之前必须计算所有的 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k+1)}$ 。

   • 计算 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k+1)}$ 之间是相互独立的。

   • 如果机器内存有限，则也可以不必存储亲和矩阵 $\mathbf{S}$$\mathbf S$ ，而是需要的时候独立计算 ${\overrightarrow{\mathbf{s}}}_i$$\mathbf{\vec s}_i$ ：

     $$\begin{array}{c}{\overrightarrow{\mathbf{s}}}_i=\left({\overrightarrow{\mathbf{a}}}_i{\mathbf{A}}^{\mathrm{\top }}\right)\odot \left(\frac{1}{q_i\overrightarrow{\mathbf{q}}}\right)\\ \overrightarrow{\mathbf{q}}=(\sqrt{{\overrightarrow{\mathbf{a}}}_1\cdot {\overrightarrow{\mathbf{a}}}_1},\cdots ,\sqrt{{\overrightarrow{\mathbf{a}}}_n\cdot {\overrightarrow{\mathbf{a}}}_n})\end{array}$$

     其中 $q_i$$q_i$ 为 $\overrightarrow{\mathbf{q}}$$\mathbf{\vec q}$ 的第 $i$$i$ 项， $\odot$$\odot$ 为逐元素积。

3. 为了进行适当的初始化，我们在第一次迭代中将 $\mathbf{H}$$\mathbf H$ 初始化为 ${\mathbf{A}}_0$$\mathbf A_0$ 的左奇异值。其中 ${\mathbf{A}}_0\in {\mathbb{R}}^{n\times 2d}$$\mathbf A_0\in \mathbb R^{n\times 2d}$ 为一个矩阵，它包含了 $\mathbf{A}$$\mathbf A$ 的前 $2d$$2d$ 列。

4. AANE 将优化过程分为 $2n$$2n$ 个子问题，然后迭代地求解它们。在每轮迭代过程中，可以分布式地将 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ （或者 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$ ）的 $n$$n$ 个 updating step 分配给 $t$$t$ 个 worker 。当原始残差 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}-{\overrightarrow{\mathbf{h}}}_i^{(k)}$$\mathbf{\vec h}_i^{(k+1)} - \mathbf{\vec h}_i^{(k)}$ 或者对偶残差 ${\overrightarrow{\mathbf{u}}}_i^{(k+1)}-{\overrightarrow{\mathbf{u}}}_i^{(k)}$$\mathbf{\vec u}_i^{(k+1)} - \mathbf{\vec u}_i^{(k)}$ 足够小时，停止迭代。

   整体而言，AANE 优化算法有几个不错的特性：

   • 首先，它使得 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ （或 ${\overrightarrow{\mathbf{z}}}_i$$\mathbf{\vec z}_i$）的 $n$$n$ 个 updating step 彼此独立。因此，在每次迭代中，global coordination 可以将任务并行分配给 worker 并从这些 worker 中收集结果，而无需考虑任务顺序。

   • 其次，所有 updating step 都具有低复杂度。

   • 最后，该方法快速收敛到一个合适的解。

5. AANE 优化算法：

   • 输入：

     • 图 $\mathcal{G}(\mathcal{V},\mathcal{E},\mathbf{W})$$\mathcal G(\mathcal V,\mathcal E,\mathbf W)$

     • 节点属性矩阵 $\mathbf{A}\in {\mathbb{R}}^{n\times m}$$\mathbf A\in \mathbb R^{n\times m}$

     • embedding 维度 $d$$d$

     • 收敛阈值 $ϵ$$\epsilon$

   • 输出：所有节点的 embedding 矩阵 $\mathbf{H}\in {\mathbb{R}}^{n\times d}$$\mathbf H\in \mathbb R^{n\times d}$

   • 步骤：

     • 从属性矩阵 $\mathbf{A}$$\mathbf A$ 中提取前 $2d$$2d$ 列，构成 ${\mathbf{A}}_0\in {\mathbb{R}}^{n\times 2d}$$\mathbf A_0\in \mathbb R^{n\times 2d}$。

     • 初始化：$k=0$$k=0$， ${\mathbf{H}}^{(k)}$$\mathbf H^{(k)}$ 为 ${\mathbf{A}}_0$$\mathbf A_0$ 的左奇异向量， ${\mathbf{U}}^{(0)}=\mathbf{0}$$\mathbf U^{(0)} = \mathbf 0$， ${\mathbf{Z}}^{(k)}={\mathbf{H}}^{(k)}$$\mathbf Z^{(k)} = \mathbf H^{(k)}$ 。

     • 计算属性亲和矩阵 $\mathbf{S}\in {\mathbb{R}}^{n\times n}$$\mathbf S\in \mathbb R^{n\times n}$ 。

     • 迭代，直到残差 ${\Vert {\overrightarrow{\mathbf{h}}}_i^{(k+1)}-{\overrightarrow{\mathbf{h}}}_i^{(k)}\Vert }^2\le ϵ$$\left\|\mathbf{\vec h}_i^{(k+1)} - \mathbf{\vec h}_i^{(k)}\right\|^2\le \epsilon$ 或者对偶残差 ${\Vert {\overrightarrow{\mathbf{u}}}_i^{(k+1)}-{\overrightarrow{\mathbf{u}}}_i^{(k)}\Vert }^2\le ϵ$$\left\|\mathbf{\vec u}_i^{(k+1)} - \mathbf{\vec u}_i^{(k)}\right\|^2\le \epsilon$ 。迭代步骤为：

       • 计算 ${\mathbf{Z}}^{(k{)}^{\mathrm{\top }}}{\mathbf{Z}}^{(k)}$$\mathbf Z^{(k)^\top} \mathbf Z^{(k)}$。

       • 分配 $n$$n$ 个子任务到 $t$$t$ 个 worker， 然后更新：对于 $i=1,\cdots ,n$$i=1,\cdots,n$ 计算 ${\overrightarrow{\mathbf{h}}}_i^{(k+1)}$$\mathbf{\vec h}_i^{(k+1)}$ 。

       • 计算 ${\mathbf{H}}^{(k+1{)}^{\mathrm{\top }}}{\mathbf{H}}^{(k+1)}$$\mathbf H^{(k+1)^\top} \mathbf H^{(k+1)}$。

       • 分配 $n$$n$ 个子任务到 $t$$t$ 个 worker， 然后更新：对于 $i=1,\cdots ,n$$i=1,\cdots,n$ 计算 ${\overrightarrow{\mathbf{z}}}_i^{(k+1)}$$\mathbf{\vec z}_i^{(k+1)}$ 。

       • 计算 ${\mathbf{U}}^{(k+1)}\leftarrow {\mathbf{U}}^{(k)}+({\mathbf{H}}^{(k+1)}-{\mathbf{Z}}^{(k+1)})$$\mathbf U^{(k+1)} \leftarrow \mathbf U^{(k)} + \left(\mathbf H^{(k+1)} - \mathbf Z^{(k+1)}\right)$ 。

       • 更新 $k\leftarrow k+1$$k\leftarrow k+1$。

     • 返回 $\mathbf{H}$$\mathbf H$ 。

6. 下图说明了 AANE 的基本思想：给定一个 $n=6$$n=6$ 个节点的网络，它首先将属性亲和矩阵 $\mathbf{S}\in {\mathbb{R}}^{n\times n}$$\mathbf S\in \mathbb R^{n\times n}$ 分解为 $\mathbf{H}$$\mathbf H$ 和 ${\mathbf{H}}^{\mathrm{\top }}$$\mathbf H^\top$ 的乘积。同时，它对这种分解施加了基于边的惩罚，使得相连的节点在 $\mathbf{H}$$\mathbf H$ 中彼此靠近，并且靠近程度由 $\mathbf{W}$$\mathbf W$ 中的边权重所控制。模型的目标是使得网络空间中更相似的节点在 $\mathbf{H}$$\mathbf H$ 中更靠近。

   为了加速优化算法，我们提出了一种分布式优化算法，将原始问题分解为 $2n=12$$2n=12$ 个低复杂度的子问题。前 $n=6$$n=6$ 个子问题被设计为相互独立，而后 $n=6$$n=6$ 个子问题也是相互独立的。所有子问题都可以分配给 $t=3$$t=3$ 个 worker。在最终输出中，节点 1 和节点 3 分别分配了相似的向量 [0.54, 0.27] 和 [0.55, 0.28]，这表明这两个节点在原始网络和属性的联合空间（joint space）中彼此相似。

   

7. 算法复杂度：由于AANE 的优化算法是一个典型的 ADMM 算法，因此训练算法在迭代很少的几个 step 之后就能收敛到很高的精度。

   • 在初始化步骤，由于需要计算奇异值向量，因此计算复杂度为 $O(d^{2}n)$$O(d^2n)$ 。

   • 在每个子任务过程中，更新 ${\overrightarrow{\mathbf{h}}}_i$$\mathbf{\vec h}_i$ 的计算复杂度为 $O(d^3+dn+d{N}_i)$$O(d^3+dn+d N_i)$ 。注意：我们只需要在每轮迭代中计算一次 ${\mathbf{Z}}^{(k{)}^{\mathrm{\top }}}{\mathbf{Z}}^{(k)}$$\mathbf Z^{(k)^\top}\mathbf Z^{(k)}$ ，其分摊的算法复杂度为 $O(n^2/t)$$O(n^2/t)$。由于 $d\ll n$$d\ll n$， 因此其计算复杂度为 $O(n)$$O(n)$ 。

     另外，可以验证每个子任务的空间复杂度为 $O(n)$$O(n)$ 。

   因此 AANE 总的时间复杂度为 $O(n\times n_A+n^2/t)$$O(n\times n_A + n^2/t)$ ，其中 $n_A$$n_A$ 为矩阵 $\mathbf{A}$$\mathbf A$ 的非零元素数量， $t$$t$ 为 worker 数量。

   AANE 的算法复杂度总体而言在 $O(n^2)$$O(n^2)$ ，这对于大型图（如上亿节点）而言是不可行的。

1.2 实验

1. 数据集：

   • BlogCatalog 数据集：一个博客社区，用户彼此关注从而构成一个网络。用户可以生成关键词来作为其博客的简短描述，我们将这些关键词作为节点（用户）的属性。用户也可以将其博客注册为指定的类别，我们将这些类别作为用户的 label 。没有关注或者没有指定类别的用户从网络中剔除。

   • Flickr 数据集：一个在线图片共享社区，用户彼此关注从而构成一个网络。用户可以为图片指定 tag ，我们将这些 tag 作为节点（用户）的属性。用于可以加入不同的组，我们将这些组作为用户的 label 。

   • Yelp 数据集：一个类似大众点评的本地生活评论网站。我们基于用户的社交关系来构成一个网络。我们从用户的评论中利用bag-of-word 抽取文本信息来作为用户的属性信息。所有本地商家分为 11 个主要类别，如 Active Life, Fast Food, Services... ，我们将用户所点评的商家的类别作为用户的 label 。

   这些数据集的统计信息如下所示。

   

2. baseline 模型：为评估节点属性的贡献，我们对比了 DeepWalk,LINE,PCA 等模型，这些baseline 模型仅能处理网络结构或者节点属性，无法处理二者的融合；为了对比AANE 的效率和效果，我们对比了其它的两种 ANE 模型 LCMF, MultiSpec 。

   • DeepWalk：使用 SkipGram 学习基于图上的、截断的随机游走序列从而得到图的 embedding 。

   • LINE：建模图的一阶邻近度和二阶邻近度从而得到图的 embedding 。

   • PCA：经典的降维技术，它将属性矩阵 $\mathbf{A}$$\mathbf A$ 的 top d 个主成分作为图的 embedding 。

   • LCMF：它通过对网络结构信息和顶点属性信息进行联合矩阵分解来学习图的 embedding 。

   • MultiSpec：它将网络结构和顶点属性视为两个视图 （view） ，然后在两个视图之间执行 co-regularizing spectral clustering 来学习图的 embedding 。

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

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

   所有模型的 embedding 维度设置为 $d=100$$d=100$ 。所有实验均随机重复 10 并报告评估指标的均值。

4. 属性信息的影响：我们分别将分类训练集的规模设置为 10%,25%,50%,100%。其中，由于 Yelp 数据集的规模太大，大多数ANE 方法的复杂度太高而无法训练，因此我们随机抽取其 20% 的数据并设置为新的数据集，即 Yelp1 。

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

   

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

   

   结论：

   • 由于利用了顶点的属性信息，因此LCMF,MultiSpec,AANE 等属性网络embedding 方法比 DeepWalk,LINE 等网络结构embedding 方法效果更好。例如，在 BlogCatalog 数据集上，结合属性信息的 AANE 在 Micro-average 得分上比 DeepWalk 相对提升 38.7%、比 LINE 提升 36.3%。

   • 我们提出的 AANE 始终优于 LCMF, MultiSpec 方法。例如，在 Flickr 数据集上，AANE 比 LCMF 相对提升 18.2%。这可以解释为通过分解网络矩阵（network matrix ）和属性矩阵（attribute matrix）学到的潜在特征是异质的，并且很难将它们直接结合起来。

   • LCMF,MultiSpec 方法无法应用于大型数据集。

5. 效率评估：然后我们评估这些方法的训练效率。我们将 AANE 和 LCMF,MultiSpec 这些属性网络 embedding 方法进行比较。下图给出了这些模型在不同数据集上、不同顶点规模的训练时间。

   结论：

   • AANE 的训练时间始终比 LCMF 和 MultiSpec 更少。

   • 随着顶点规模的增加，训练效率之间的 gap 也越来越大。

   • AANE 可以在多线程环境下进一步提升训练效率。

   这种比较意义不大，本质上 AANE 是 $O(n^2)$$O(n^2)$ 的复杂度，因为无法适用于大型网络。另外，其它两种方法和 AANE 的时间曲线是平行的，也就是相差常数时间。在算法中，相差 $O(1)$$O(1)$ 的复杂度并不会带来本质上的效率提升。

   

6. 参数敏感性：这里我们研究参数 $\lambda$$\lambda$ 和 $d$$d$ 的影响。

   • 参数 $\lambda$$\lambda$ 平衡了网络结构和顶点属性之间的贡献。为研究 $\lambda$$\lambda$ 的影响，我们将其从 ${10}^{-6}$$10^{-6}$ 变化到 ${10}^3$$10^3$ ，对应的分类 Micro-F1 效果如下所示。

     • 当 $\lambda$$\lambda$ 接近于 0 时，模型未考虑网络结构信息，就好像所有节点都是孤立的。随着 $\lambda$$\lambda$ 的增加，AANE 开始根据拓扑结构对节点进行聚类，因此性能不断提升。

     • 当 $\lambda$$\lambda$ 接近 0.1 时，模型在 BlogCatalog 和 Flickr 上的效果达到最佳。随着 $\lambda$$\lambda$ 的继续增加，模型性能下降。因为较大的 $\lambda$$\lambda$ 倾向于使得所有顶点具有相同的 embedding 。

     

   • 为研究 embedding 维度 $d$$d$ 的影响，我们将 $d$$d$ 从 20 变化到 180，对应的分类 Micro-F1 效果如下所示。我们仅给出 Flickr 数据集的结果，BlogCatalog 和 Yelp 的结果也是类似的。

     可以看到：

     • 无论 $d$$d$ 为多少，DeepWalk 和 LINE 都不如属性网络 embedding 方法（AANE,LCMF,MultiSpec ）

     • 无论 $d$$d$ 为多少，AANE 的效果始终最佳。

     • 当 $d$$d$ 增加时，这些模型的效果先提高、然后保持稳定。这表示低维 embedding 已经能够捕获大多数有意义的信息。