Question

1. 属性网络 attributed network 在各种现实世界的信息系统中无处不在，例如学术网络、医疗保健系统。与仅观测节点之间交互和依赖关系的常规网络不同，属性网络中的每个节点通常关联一组丰富的特征。例如，随着社交网络服务的普及，人们不仅可以结识朋友从而形成在线社区，还可以积极分享意见、发表评论。在社会科学中，人们已经研究了社交影响理论social influence theory ，即：个体的属性既可以反映、也可以影响他们的社区结构。此外，许多数据挖掘应用程序（如情感分析、信任预测）都可以受益于几何结构和节点属性之间的相关性。

   network embedding 作为一种高效的图挖掘计算工具，旨在将网络中所有节点的拓扑邻近性topological proximity 映射为连续的低维向量 representation 。学到的 embedding representation 有助于节点分类、链接预测、网络可视化等众多应用。虽然 network embedding 已被广泛研究，但是对 Attributed Network Embedding: ANE 的研究仍处于早期阶段。与从纯网络pure network 学习的 network embedding 相比，ANE 的目标是利用网络邻近性proximity 和节点属性亲和性affinity 。由于两种信息源的异质性，现有的 network embedding 算法很难直接应用于 ANE 。

   人们在各种现实世界的网络中收集了丰富的 label，如 group 或者社区类别。例如，在 Facebook 和 Flickr 等许多社交网络中，用户被允许加入一些预定义的分组。同组的用户倾向于分享类似主题的帖子或照片，并且组内用户之间也经常互动。引文网络是另一个例子。在同一个研究社区中发表的论文通常具有共同的主题，它们还大量引用来自同一社区的其它论文。这些事实可以用同质性假设homophily hypothesis 来解释，即，具有相同 label 的个体通常具有相似的社交关系和相似的节点属性。label 受到网络结构和属性信息的强烈影响，并与它们固有地相关。受到这一事实（即，label 可能有助于学习更好的联合 embedding representation）的启发，而现有方法关注于以无监督的方式学习 embedding，论文 《Label Informed Attributed Network Embedding》建议研究如何利用 label 信息并将其整合到 ANE 中。

   然而，在属性网络中建模和利用 label 是一项困难的任务。有两个主要挑战：

   • 首先，属性网络和 label 信息可能是稀疏sparse 的、不完整incomplete 的、噪音noisy 的。例如，在社交网络中，单个用户的好友数量相比总用户量而言总是极少的，特定 label 的活跃用户的占比也可能很小。
   • 其次，鉴于属性网络及其 label 的异质性，学习统一的 representation 具有挑战性。与评论和帖子等属性不同，label 将实例划分为不同的分组或社区。很难显式地建模所有这些多模态信息源之间的相关性correlation ，并将它们共同嵌入到信息量丰富的 embedding representation 中。

   因此，利用异质的、噪音的信息来相互补充从而获得有效的、鲁棒的 embedding representation 是一项具有挑战性的任务。

   在论文 《Label Informed Attributed Network Embedding》中，作者研究了 label informed attributed network embedding 的问题，并提出了一个有效的框架 LANE。具体而言，论文旨在回答以下问题：

   • 如何将 label 建模且融合到 ANE 框架中？
   • label 对 embedding representation learning 的潜在影响是什么？
   • LANE 通过利用 label 对其它学习任务（如节点分类）做出多大贡献？

   总之，论文的主要贡献如下：

   • 正式定义 label informed attributed network embedding 问题。
   • 提出一个新的框架 LANE。LANE 可以将 label 与属性网络关联，并通过建模它们的结构邻近性和相关性，将它们平滑地嵌入到低维 representation 中。
   • 提出一种有效的交替算法来解决 LANE 的优化问题。
   • 实验评估和验证了 LANE 在真实世界属性网络上的有效性。

2. 相关工作：

   近年来，network embedding 越来越受欢迎。

   • network embedding 的开创性工作可以追溯到 graph embedding 问题，该问题由 《On determining the genus of a graph in O(v^{O(g)}) steps》 在 1979 年作为 graph genus determining 问题所引入。

   • 一系列更通用的 graph embedding 方法是在 2000 年代左右开发的。他们的目标是生成可以对数据的非线性几何进行建模的低维流形low-dimensional manifold，包括 Isomap、Laplacian Eigenmap、谱技术。

   • 到目前为止，由于网络数据的普遍性，人们已经实现了各种 network embedding 算法。

     • 《Probabilistic latent semantic visualization: topic model for visualizing documents》 将概率潜在语义分析probabilistic latent semantic analysis: pLSA 应用于嵌入文档网络。
     • 《Community evolution in dynamic multi-mode networks》 研究了利用时间信息分析动态多模式网络的优势。
     • 《Structure preserving embedding》 利用半定程序semidefinite program 来学习低维 representation ，从而很好地保留了全局拓扑结构。
     • 《Topic modeling with network regularization》 设计了一种基于 harmonic regularization 的 embedding 框架来解决具有网络结构的主题建模问题。
     • 《Distributed large-scale natural graph factorization》 提出了一种用于大规模图的异步分布式矩阵分解算法。
     • 《Learning social network embeddings for predicting information diffusion》 将观察到的时间动态投影到潜在空间中，从而更好地建模网络中的信息扩散。
     • 《node2vec: Scalable feature learning for networks》 通过增加邻域的灵活性，进一步推进了基于随机游走的 embedding 算法。
     • 为了嵌入异质网络，《Learning latent representations of nodes for classifying in heterogeneous social networks》 将 transductive 模型和深度学习技术扩展到该问题中。
     • 《Revisiting semi-supervised learning with graph embeddings》 利用概率模型以半监督方式进行 network embedding。

     最近，人们提出了几种基于深度学习的 embedding 算法，从而进一步提高学习 representation 的性能。

   在众多现实世界网络中，节点往往关联丰富的节点属性信息，因此人们提出了属性网络分析。在这些网络中，人们普遍认为几何结构和节点属性之间存在相关性。因此，同时利用这两者的算法可以提高整体的学习性能。例如，《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》 探索了一种有效的算法，通过构建语义概念semantic concept 的潜在空间，从而联合嵌入社交媒体中的链接和内容。
   • 《Probabilistic latent document network embedding》 提出一个整体框架来同时处理文档链接和文本信息，并找到一个统一的低维 representation。他们通过联合概率模型来实现这一目标。
   • 《Unsupervised streaming feature selection in social media》 利用流式特征选择框架联合学习高维内容数据和链接信息中的潜在因子的概率。
   • 《Heterogeneous network embedding via deep architectures》 将内容转换为另一个网络，并利用非线性多层 embedding 模型来学习构建的内容网络与原始网络之间的复杂交互。

   在许多应用中，数据表现出多个方面multiple facets，这些数据被称作多视图数据。多视图学习 multi-view learning 旨在从多个信息源中学习统计模型。人们已经提出了许多算法。

   • 《A reconstruction error based framework for multi-label and multi-view learning》 研究了一种基于重构误差的框架，用于处理 multi-label 和 multi-view 学习。该框架可以显式量化多个 label 或视图的合并的性能。
   • 《Pre-trained multi-view word embedding using two-side neural network》 应用了一个 two-side 多模态神经网络来嵌入基于多个数据源的 word 。

   《A survey of multi-view machine learning》 对多视图学习给出了更详细的回顾。我们的工作与多视图学习之间的主要区别在于：属性网络可以被视为一个特殊构建的数据源，而且 ANE 本身就是一个具有挑战性的问题。label 也是具有特定形式的特殊数据源。

20.1 模型

20.1.1 基本概念

1. 定义$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W},\mathbf{A})$$ \mathcal G=(\mathcal V,\mathcal E,\mathbf W, \mathbf A) $ 为一个属性网络，其中：

   • $\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} $ 为所有边的权重矩阵，$w_{i,j}>0$$ w_{i,j}\gt 0 $ 表示边$(v_i,v_j)\in \mathcal{E}$$ (v_i,v_j)\in \mathcal E $ 的权重。当$(v_i,v_j)\ne \mathcal{E}$$ (v_i,v_j)\ne \mathcal E $ 时$w_{i,j}=0$$ w_{i,j} = 0 $ 。
   • $\mathbf{A}=\{a_{i,j}\}\in {\mathbb{R}}^{n\times m}$$ \mathbf A =\{a_{i,j}\}\in \mathbb R^{n\times m} $ 为所有节点的属性矩阵，$m$$ m $ 为属性向量的维度。$\mathbf{A}$$ \mathbf A $ 的第$i$$ i $ 行${\overrightarrow{\mathbf{a}}}_i=(a_{i,1},\cdots ,a_{i,m}{)}^{\mathrm{\top }}\in {\mathbb{R}}^m$$ \mathbf{\vec a}_i = (a_{i,1},\cdots,a_{i,m})^\top\in \mathbb R^m $ 表示节点$v_i$$ v_i $ 的属性向量。

   除了网络结构和节点属性之外，每个节点还关联一组 label 。节点的 label 矩阵为$\mathbf{Y}=\{y_{i,j}\}\in {\mathbb{R}}^{n\times k}$$ \mathbf Y = \{y_{i,j}\}\in \mathbb R^{n\times k} $ ，其中$k$$ k $ 为 label 种类。$\mathbf{Y}$$ \mathbf Y $ 的第$i$$ i $ 行${\overrightarrow{\mathbf{y}}}_i=(y_{i,1},\cdots ,y_{i,k}{)}^{\mathrm{\top }}\in {\mathbb{R}}^k$$ \mathbf{\vec y}_i = (y_{i,1},\cdots,y_{i,k})^\top\in \mathbb R^k $ 为 label 向量，$y_{i,j}=1$$ y_{i,j} = 1 $ 表示节点属于第$j$$ j $ 类 label ，每个节点可以属于其中某一类 label 或者某几类 label 。

   我们定义 label informed attributed network embedding 为：给定属性网络$\mathcal{G}$$ \mathcal G $ 以及 label 信息$\mathbf{Y}$$ \mathbf Y $ ，为每个节点$v_i$$ v_i $ 学习低维的向量representation${\overrightarrow{\mathbf{h}}}_i\in {\mathbb{R}}^d$$ \mathbf{\vec h}_i\in \mathbb R^d $ ，使得${\overrightarrow{\mathbf{h}}}_i$$ \mathbf{\vec h}_i $ 尽可能包含属性网络信息和 label 信息。

2. 我们提出了一种新颖的informed attributed network embedding: LANE 方法。LANE 可以建模属性网络空间和 label 信息空间中的节点邻近性，并将它们联合嵌入到统一的低维 representation 中。下图说明了 LANE 的主要思想，图中有一个含有六个节点的属性网络，每个节点都有各自的label 。

   LANE 通过两个模块来学习节点的embedding ：属性网络嵌入 Attributed Network Embedding、标签信息嵌入 Label Informed Embedding 。

   • 首先，我们将网络结构邻近性和网络节点属性邻近性映射到两个潜在representation${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 和${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 中，然后通过抽取${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 和${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 的相关性从而将${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 融合到${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 中。
   • 其次，我们利用融合的${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 来平滑label 信息，从而统一嵌入到另一个潜在空间${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ 中。
   • 最后，我们将所有学到的潜在representation 映射到一个统一的 representation$\mathbf{H}$$ \mathbf H $ 中。

   如下图所示，节点 1 和节点 3 的 embedding向量分别为 [0.54, 0.27] 和 [0.55, 0.28]，这意味着它们在原始空间中具有相似的属性。为了有效地学习节点 embedding ，我们设计了一种高效的交替优化算法。

   

20.1.2 Attributed Network Embedding: ANE

1. Attributed Network Embedding 模块的目标是寻找两个$n\times d$$ n\times d $ 矩阵来表示$\mathcal{G}$$ \mathcal G $ 中的节点，从而保持网络结构信息和节点属性信息。具体而言，我们旨在为结构相似或者属性相似的节点分配相似的向量representation 。

2. 首先考虑对网络结构进行建模。网络结构建模的核心思想是：如果节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的网络结构相似，则它们的representation 向量${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 和${\overrightarrow{\mathbf{u}}}_j$$ \mathbf{\vec u}_j $ 也应该相似。这里我们用余弦距离$s_{i,j}=\cos ({\overrightarrow{\mathbf{w}}}_i,{\overrightarrow{\mathbf{w}}}_j)$$ s_{i,j} = \cos(\mathbf{\vec w}_i,\mathbf{\vec w}_j) $ 来衡量节点$v_i,v_j$$ v_i,v_j $ 的结构相似性，用欧式距离${\Vert {\overrightarrow{\mathbf{u}}}_i-{\overrightarrow{\mathbf{u}}}_j\Vert }_2^2$$ \left\|\mathbf{\vec u}_i - \mathbf{\vec u}_j\right\|_2^2 $ 来衡量representation 向量的相似性，其中${\overrightarrow{\mathbf{w}}}_i\in {\mathbb{R}}^n$$ \mathbf {\vec w}_i \in \mathbb R^n $ 为边权重矩阵的第$i$$ i $ 行。当然，也可以使用其它相似度来衡量节点$v_i,v_j$$ v_i,v_j $ 的结构相似性。

   ${\overrightarrow{\mathbf{w}}}_i$$ \mathbf{\vec w}_i $ 的相似性刻画了节点一阶邻域之间的相似性。而 AANE 中采用边权重$w_{i,j}$$ w_{i,j} $ 作为结构相似性指标。

   我们通过$s_{i,j}\times {\Vert {\overrightarrow{\mathbf{u}}}_i-{\overrightarrow{\mathbf{u}}}_j\Vert }_2^2$$ s_{i,j}\times \left\| \mathbf{\vec u}_i - \mathbf{\vec u}_j\right\|_2^2 $ 来衡量$s_{i,j}$$ s_{i,j} $ 和$\{{\overrightarrow{\mathbf{u}}}_i,{\overrightarrow{\mathbf{u}}}_j\}$$ \{\mathbf{\vec u}_i,\mathbf{\vec u}_j\} $ 之间的不一致程度：

   • 当节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的结构相似时（即$s_{i,j}$$ s_{i,j} $ 较大），${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 和${\overrightarrow{\mathbf{u}}}_j$$ \mathbf{\vec u}_j $ 应该彼此靠近（即${\Vert {\overrightarrow{\mathbf{u}}}_i-{\overrightarrow{\mathbf{u}}}_j\Vert }_2^2$$ \left\| \mathbf{\vec u}_i - \mathbf{\vec u}_j\right\|_2^2 $ 较小）。
   • 当${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 和${\overrightarrow{\mathbf{u}}}_j$$ \mathbf{\vec u}_j $ 彼此距离较远时，节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的结构应该不相似（即$s_{i,j}$$ s_{i,j} $ 较小）。

   该损失函数无法解决结构不相似但是${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 和${\overrightarrow{\mathbf{u}}}_j$$ \mathbf{\vec u}_j $ 彼此靠近的情况。即上式存在一个特殊解：所有节点的 embedding 都相等。因此论文增加了约束条件${\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I}$$ \mathbf U^{(G)^\top} \mathbf U^{(G)} = \mathbf I $ 。

   考虑所有节点，则我们得到总的不一致程度为：

   $$\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{s}_{i,j}\times {\Vert {\overrightarrow{\mathbf{u}}}_i-{\overrightarrow{\mathbf{u}}}_j\Vert }_2^2$$

   定义图结构的pair-wise 结构相似性矩阵为${\mathbf{S}}^{(G)}$$ \mathbf S^{(G)} $ ，其中$s_{i,j}$$ s_{i,j} $ 为第$i$$ i $ 行、第$j$$ j $ 列的元素，$d_i=\sum _j{s}_{i,j}$$ d_i = \sum_{j} s_{i,j} $ 为第$i$$ i $ 行的元素之和。考虑到有些节点和很少的节点相似（即$d_i$$ d_i $ 较大），有的节点和非常多的节点相似（即$d_i$$ d_i $ 较小）。因此使用$d_i$$ d_i $ 和$d_j$$ d_j $ 进行归一化：

   $$\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{s}_{i,j}\times {\Vert \frac{{\overrightarrow{\mathbf{u}}}_i}{{\sqrt{d}}_i}-\frac{{\overrightarrow{\mathbf{u}}}_j}{{\sqrt{d}}_j}\Vert }_2^2$$

   这里采用这种归一化形式是为了得到拉普拉斯矩阵的矩阵形式。

   则我们的目标函数为：

   $$\underset{{\mathbf{U}}^{(G)}}{min}\frac{1}{2}\sum _{i=1}^n\sum _{j=1}^n{s}_{i,j}\times {\Vert \frac{{\overrightarrow{\mathbf{u}}}_i}{{\sqrt{d}}_i}-\frac{{\overrightarrow{\mathbf{u}}}_j}{{\sqrt{d}}_j}\Vert }_2^2$$

   其中${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 为网络结构 representation 矩阵，其第$i$$ i $ 行为${\overrightarrow{\mathbf{u}}}_i$$ \mathbf{\vec u}_i $ 。根据归一化图拉普拉斯矩阵的定义，我们将结构邻近性建模的目标函数重写为：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(G)}}{max}{\mathcal{J}}_G=\text{tr}\left({\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{L}}^{(G)}{\mathbf{U}}^{(G)}\right)\\ s.t.{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I}\end{array}$$

   其中：$\text{tr}(\cdot )$$ \text{tr}(\cdot) $ 为矩阵的迹，${\mathbf{L}}^{(G)}={\mathbf{D}}^{(G)-\frac{1}{2}}{\mathbf{S}}^{(G)}{\mathbf{D}}^{(G)-\frac{1}{2}}$$ \mathbf L^{(G)} = \mathbf D^{(G)-\frac 12} \mathbf S^{(G)} \mathbf D^{(G)-\frac 12} $ 为归一化的拉普拉斯矩阵，${\mathbf{D}}^{(G)}=\text{diag}(d_1,\cdots ,d_n)$$ \mathbf D^{(G)}=\text{diag}(d_1,\cdots,d_n) $ 为对角矩阵。

   我们添加约束${\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I}$$ \mathbf U^{(G)^\top}\mathbf U^{(G)} = \mathbf I $ 是为了得到唯一解。如果没有该约束，则解为任意多个。

3. 与网络结构建模类似，我们对节点属性邻近性建模过程也是类似的。定义节点属性pair-wise 邻近性矩阵为${\mathbf{S}}^{(A)}$$ \mathbf S^{(A)} $ ， 定义节点属性 representation 矩阵为${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 。节点属性邻近性建模的目标是最小化${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 和${\mathbf{S}}^{(A)}$$ \mathbf S^{(A)} $ 之间的不一致性。

   定义归一化拉普拉斯矩阵${\mathbf{L}}^{(A)}={\mathbf{D}}^{(A)-\frac{1}{2}}{\mathbf{S}}^{(A)}{\mathbf{D}}^{(A)-\frac{1}{2}}$$ \mathbf L^{(A)} = \mathbf D^{(A)-\frac 12} \mathbf S^{(A)} \mathbf D^{(A) -\frac 12} $ ，${\mathbf{D}}^{(A)}=\text{diag}(d_1^{(A)},\cdots ,d_n^{(A)})$$ \mathbf D^{(A)}=\text{diag}(d_1^{(A)},\cdots,d_n^{(A)}) $ 为对角矩阵，$d_i^{(A)}$$ d_i^{(A)} $ 为${\mathbf{S}}^{(A)}$$ \mathbf S^{(A)} $ 第$i$$ i $ 行之和。则节点属性邻近性建模的目标函数为：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(A)}}{max}{\mathcal{J}}_A=\text{tr}\left({\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{L}}^{(A)}{\mathbf{U}}^{(A)}\right)\\ s.t.{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}=\mathbf{I}\end{array}$$

4. 为了将${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 融合到${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ ，我们将${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 投影到${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 所在的空间。我们认为：结构相似性的节点之间很可能节点属性也相似。即，结构邻近性和节点属性邻近性相关性很大。我们将${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 投影后的矩阵的方差作为相关性度量：

   $${\rho }_1=\text{tr}\left({\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}\right)$$

   ${\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}$$ \mathbf U^{(G)^\top} \mathbf U^{(A)} $ 表示将${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 投影到${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 所在空间，它类比于向量$\overrightarrow{\mathbf{a}}$$ \mathbf{\vec a} $ 在向量$\overrightarrow{\mathbf{b}}$$ \mathbf{\vec b} $ 上的投影。

   这里是通过正则化的方式，迫使结构邻近性和节点属性邻近性产生高度的相关。

   为了使得网络结构信息和节点属性信息互补，我们在模型中共同最大化${\mathcal{J}}_G,{\mathcal{J}}_A$$ \mathcal J_G,\mathcal J_A $ ， 以及${\mathbf{U}}^{(A)},{\mathbf{U}}^{(G)}$$ \mathbf U^{(A)}, \mathbf U^{(G)} $ 之间的相关性${\rho }_1$$ \rho_1 $ ：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(G)},{\mathbf{U}}^{(A)}}{max}({\mathcal{J}}_G+{\alpha }_1{\mathcal{J}}_A+{\alpha }_1{\rho }_1)\\ s.t.{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I},{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}=\mathbf{I}\end{array}$$

   其中${\alpha }_1$$ \alpha_1 $ 平衡 ANE 模块内部网络结构和节点属性的贡献。

   论文 《Accelerated Attributed Network Embedding》 提出的 AANE 中，${\mathbf{U}}^{(A)}={\mathbf{U}}^{(G)}$$ \mathbf U^{(A)} = \mathbf U^{(G)} $ ，因此相关性指标${\rho }_1$$ \rho_1 $ 最大。相比之下，这里放松了${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ 和${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 的约束，使得模型表达能力更强。

5. 我们在 ANE 模块基于pair-wise 相似性来执行属性网络 embedding。这种方法和谱聚类相一致，它有几个优点：

   • 对于输入没有很强的假设，即普适性较好，可以推广到很多实际问题。
   • 目标函数可以使用很多图论来解释，如 ratio-cut partitioning、随机游走。
   • 可以通过eigen-decomposition 特征值分解很容易求解问题。

20.1.3 Label Informed Embedding: LIE

1. label 信息在确定每个节点内部结构方面起着至关重要的作用，它和网络结构、节点属性有着强烈的、固有的相关性。除了这些强相关性之外，label 还可能被纳入前面提到的 ANE 模块中。然而，label 通常是噪音noisy 的、且不完整incomplete 的。直接探索label 可能会对最终的 embedding 产生负面影响。我们提出了一种对 label 进行建模的方法，并且使用两个步骤来强化 embedding representation learning ：label information modeling 、correlation projection 。

2. Label Information Modeling：在这一步中，我们将label 邻近性映射到潜在representation${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ 中。其基本思想是：利用属性网络embedding 来平滑label 邻近性，使得当节点具有相同的 label 时，它们的网络结构、节点属性、以及最终的representation 都趋近于相似。

   具体而言，我们根据label 将节点划分到对应的团clique 中，对应的表示形式为$\mathbf{Y}{\mathbf{Y}}^{\mathrm{\top }}\in {\mathbb{R}}^{n\times n}$$ \mathbf Y\mathbf Y^\top\in \mathbb R^{n\times n} $ 。其中第$i$$ i $ 行$j$$ j $ 列的元素为${\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j$$ \mathbf{\vec y}_i\cdot \mathbf{\vec y}_j $ ，表示节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的label 向量的内积。假设每个节点仅属于一个label 类别：

   • 当节点$v_i$$ v_i $ 和$v_j$$ v_j $ 属于不同的类别时，${\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j=0$$ \mathbf{\vec y}_i\cdot \mathbf{\vec y}_j = 0 $ ，即顶点$v_i$$ v_i $ 和$v_j$$ v_j $ 属于不同的clique 。
   • 当节点$v_i$$ v_i $ 和$v_j$$ v_j $ 属于相同的类别时，${\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j=1$$ \mathbf{\vec y}_i\cdot \mathbf{\vec y}_j = 1 $ ，即顶点$v_i$$ v_i $ 和$v_j$$ v_j $ 属于相同的clique 。

   如果节点可以有多个label 类别，则${\overrightarrow{\mathbf{y}}}_i\cdot {\overrightarrow{\mathbf{y}}}_j$$ \mathbf{\vec y}_i\cdot \mathbf{\vec y}_j $ 对应于节点$v_i$$ v_i $ 和$v_j$$ v_j $ 的类别交集。

   我们根据$\mathbf{Y}{\mathbf{Y}}^{\mathrm{\top }}$$ \mathbf Y\mathbf Y^\top $ 来对label 邻近性来建模。令${\mathbf{S}}^{(YY)}$$ \mathbf S^{(YY)} $ 为$\mathbf{Y}{\mathbf{Y}}^{\mathrm{\top }}$$ \mathbf Y \mathbf Y^\top $ 的余弦相似度，定义其拉普拉斯矩阵为${\mathbf{L}}^{(YY)}={\mathbf{D}}^{(Y)-\frac{1}{2}}{\mathbf{S}}^{YY}{\mathbf{D}}^{(Y)-\frac{1}{2}}$$ \mathbf L^{(YY)} = \mathbf D^{(Y)-\frac 12} \mathbf S^{YY} \mathbf D^{(Y)- \frac 12} $ 。其中，度矩阵${\mathbf{D}}^{(Y)}$$ \mathbf D^{(Y)} $ 是一个对角矩阵，每个元素为${\mathbf{S}}^{(YY)}$$ \mathbf S^{(YY )} $ 对应行的和。

   我们可以参考网络结构邻近性和节点属性邻近性建模，通过矩阵的特征值分解来求解${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ 。但是注意到label 信息的特殊结构：$\mathbf{Y}\in {\mathbb{R}}^{n\times k}$$ \mathbf Y\in \mathbb R^{n\times k} $ 的秩小于等于$k$$ k $ ，因此$\mathbf{Y}{\mathbf{Y}}^{\mathrm{\top }}$$ \mathbf Y\mathbf Y^\top $ 的秩也小于等于$k$$ k $ ，因此${\mathbf{S}}^{(YY)}$$ \mathbf S^{(YY)} $ 的秩小于等于$k$$ k $ 。通常$k\ll d$$ k \ll d $ ，这导致对${\mathbf{L}}^{(YY)}$$ \mathbf L^{(YY)} $ 的特征值分解的效果不理想。

   为解决该问题，我们利用学到的网络结构邻近性${\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}$$ \mathbf U^{(G)}\mathbf U^{(G)^\top} $ 来smooth 模型。我们定义以下目标函数使得相同label 的节点具有相似的representation：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(Y)}}{max}{\mathcal{J}}_Y=\text{tr}\left({\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}({\mathbf{L}}^{(YY)}+{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}){\mathbf{U}}^{(Y)}\right)\\ s.t.{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}{\mathbf{U}}^{(Y)}=\mathbf{I}\end{array}$$

   这里假设结构相似的节点可能具有相同的 label 。这里没有考虑属性邻近性，主要是为了将 label 融合到网络结构中。

   这里是否可以考虑引入一个平衡因子$\lambda$$ \lambda $ ，从而平衡 label 信息和属性网络embedding 信息，即：${\mathbf{L}}^{(YY)}+\lambda {\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}$$ \mathbf L^{(YY)} + \lambda \mathbf U^{(G)} \mathbf U^{(G)^\top} $ ？论文并未讨论。

   ${\mathcal{J}}_A+{\rho }_1=\text{tr}\left({\mathbf{U}}^{(A{)}^{\mathrm{\top }}}({\mathbf{L}}^{(A)}+{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}){\mathbf{U}}^{(A)}\right)$$ \mathcal J_A+\rho_1 = \text{tr}\left( \mathbf U^{(A)^\top} \left( \mathbf L^{(A)} + \mathbf U^{(G)} \mathbf U^{(G)^\top}\right)\mathbf U^{(A)}\right) $ ，因此属性网络 embedding 也是用网络结构邻近性${\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}$$ \mathbf U^{(G)}\mathbf U^{(G)^\top} $ 来smooth 模型。

   这种方式有几个优点：

   • 首先，矩阵${\mathbf{U}}^{(G)}\in {\mathbb{R}}^{n\times d}$$ \mathbf U^{(G)}\in \mathbb R^{n\times d} $ ，因此${\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}$$ \mathbf U^{(G)} \mathbf U^{(G)^\top} $ 的秩为$d$$ d $ 并且位于噪声显著降低的低秩空间。

   • 其次，联合的邻近性融合了更多的信息，这使得label 信息与网络结构、节点属性等信息相一致。

     另外第二项$\text{tr}\left({\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(Y)}\right)$$ \text{tr}\left( \mathbf U^{(Y)^\top} \mathbf U^{(G)} \mathbf U^{(G)^\top} \mathbf U^{(Y)}\right) $ 也度量了${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 和${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ 之间的相关性，这有助于label 邻近性学习，因为label 和节点结构、节点属性是高度相关的。

   • 最后，学到的潜在representation${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ 中的噪音大大降低，并且原始的 label 空间中大部分信息可被恢复。

   因此，尽管label 信息可能是不完整的、且噪音的，但我们仍然能够捕获label 空间中的节点邻近性。

3. Correlation Projection：现在我们已经得到了属性网络embedding${\mathbf{U}}^{(A)},{\mathbf{U}}^{(G)}$$ \mathbf U^{(A)}, \mathbf U^{(G)} $ ， 以及label 信息embedding${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ ，最终我们需要根据它们联合学到一个统一的embedding$\mathbf{H}$$ \mathbf H $ 。

   我们将这些 embedding 都投影到新的embedding 空间$\mathbf{H}$$ \mathbf H $ 。为了尽可能保留投影后的信息，我们利用投影矩阵的方差作为其相关性的度量，定义为：

   $$\begin{array}{c}{\rho }_2=\text{tr}\left({\mathbf{U}}^{(G{)}^{\mathrm{\top }}}\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}{\mathbf{U}}^{(G)}\right)\\ {\rho }_3=\text{tr}\left({\mathbf{U}}^{(A{)}^{\mathrm{\top }}}\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}{\mathbf{U}}^{(A)}\right)\\ {\rho }_4=\text{tr}\left({\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}{\mathbf{U}}^{(Y)}\right)\end{array}$$

   则投影的目标函数定义为：

   $$\underset{{\mathbf{U}}^{(\cdot )},\mathbf{H}}{max}{\mathcal{J}}_{\text{corr}}={\rho }_2+{\rho }_3+{\rho }_4$$

   其中${\mathbf{U}}^{(\cdot )}$$ \mathbf U^{(\cdot)} $ 表示所有的三个潜在 embedding 。

   这里通过相关性最大，从而从三个潜在 embedding 中得到统一的embedding$\mathbf{H}$$ \mathbf H $ 。

20.1.4 联合学习

2. 现在我们考虑所有的 embedding ，以及所有的相关性。我们定义两个参数来平衡不同度量的重要性从而得到 LANE 的目标函数：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(G)},{\mathbf{U}}^{(A)},{\mathbf{U}}^{(Y)},\mathbf{H}}{max}\mathcal{J}=({\mathcal{J}}_G+{\alpha }_1{\mathcal{J}}_A+{\alpha }_1{\rho }_1)+{\alpha }_2{\mathcal{J}}_Y+{\mathcal{J}}_{\text{corr}}\\ s.t.{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I},{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}=\mathbf{I}\\ {\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}{\mathbf{U}}^{(Y)}=\mathbf{I},{\mathbf{H}}^{\mathrm{\top }}\mathbf{H}=\mathbf{I}\end{array}$$

   其中：${\alpha }_1>0$$ \alpha_1\gt 0 $ 用于平衡 ANE 模块内部网络结构和节点属性的贡献，${\alpha }_2>0$$ \alpha_2\gt 0 $ 用于平衡 ANE 模块和 LIE 模块的贡献。

   通过求解$\mathcal{J}$$ \mathcal J $ 的最优解，我们能够使得 embedding representation learning 和correlation projection 高度相关。通过这种方式，$\mathbf{H}$$ \mathbf H $ 能够捕获结构邻近性、属性邻近性、label 邻近性，以及它们之间的相关性。

3. 优化算法：目标函数有四个矩阵变量需要优化，因此无法得到闭式解。这里我们采用一种交替优化算法来逼近最优解。基本思想是：每轮迭代时固定其中三个变量而求解另外一个变量的局部最优解。当固定其中三个变量时，目标函数就是剩下变量的凸函数。

   考虑${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 的二阶导数：

   $${\mathrm{\nabla }}_{{\mathbf{U}}^{(G)}}^2\mathcal{J}={\mathbf{L}}^{(G)}+{\alpha }_1{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}+{\alpha }_2{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}{\mathbf{U}}^{(Y)}+{\mathbf{H}}^{\mathrm{\top }}\mathbf{H}$$

   其中${\mathbf{L}}^{(G)}$$ \mathbf L^{(G)} $ 为一个对称矩阵。由于${\alpha }_1>0,{\alpha }_2>0$$ \alpha_1\gt0,\alpha_2\gt0 $ ，${\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)},{\mathbf{H}}^{\mathrm{\top }}\mathbf{H}$$ \mathbf U^{(G)^\top} \mathbf U^{(G)},\mathbf H^\top\mathbf H $ 都是对称矩阵，因此${\mathrm{\nabla }}_{{\mathbf{U}}^{(G)}}^2\mathcal{J}$$ \nabla_{\mathbf U^{(G)}}^2 \mathcal J $ 为半正定矩阵。

   当${\mathbf{U}}^{(A)},{\mathbf{U}}^{(Y)},\mathbf{H}$$ \mathbf U^{(A)},\mathbf U^{(Y)},\mathbf H $ 固定时，$\mathcal{J}$$ \mathcal J $ 是${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 的凸函数，则可以通过拉格朗日乘子法来求最优解。令${\lambda }_1,{\lambda }_2,{\lambda }_3,{\lambda }_4$$ \lambda_1,\lambda_2,\lambda_3,\lambda_4 $ 为对应的拉格朗日乘子，根据${\mathrm{\nabla }}_{{\mathbf{U}}^{(G)}}\mathcal{J}=\mathbf{0}$$ \nabla_{\mathbf U^{(G)}} \mathcal J = \mathbf 0 $ ，则有：

   $$({\mathbf{L}}^{(G)}+{\alpha }_1{\mathbf{U}}^{(A)}{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}+{\alpha }_2{\mathbf{U}}^{(Y)}{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(G)}={\lambda }_1{\mathbf{U}}^{(G)}$$

   则${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 的解对应于${\mathbf{L}}^{(G)}+{\alpha }_1{\mathbf{U}}^{(A)}{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}+{\alpha }_2{\mathbf{U}}^{(Y)}{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}$$ \mathbf L^{(G)} + \alpha_1 \mathbf U^{(A)} \mathbf U^{(A)^\top} + \alpha_2 \mathbf U^{(Y)} \mathbf U^{(Y)^\top} + \mathbf H \mathbf H^\top $ 的 top$d$$ d $ 特征向量。

   类似地，最大化$\mathcal{J}$$ \mathcal J $ 等价于找出下列特征值分解问题的 top$d$$ d $ 特征向量：

   $$\begin{array}{c}({\alpha }_1{\mathbf{L}}^{(A)}+{\alpha }_1{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(A)}={\lambda }_2{\mathbf{U}}^{(A)}\\ ({\alpha }_2{\mathbf{L}}^{(YY)}+{\alpha }_2{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(Y)}={\lambda }_3{\mathbf{U}}^{(Y)}\\ ({\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+{\mathbf{U}}^{(A)}{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}+{\mathbf{U}}^{(Y)}{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}})\mathbf{H}={\lambda }_4\mathbf{H}\end{array}$$

   由于每个updating step 都是求解凸优化问题，因此可以保证收敛到局部最优解。

   我们从主要的信息源的representation${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ 开始更新，这是为了确保有一个合适的初始化。然后根据局部的特征值分解来分别更新四个参数矩阵，直到目标函数$\mathcal{J}$$ \mathcal J $ 的增长低于指定阈值$ϵ$$ \epsilon $ 为止。

4. LANE 训练算法：

   • 输入：

     • 异质网络$\mathcal{G}(\mathcal{V},\mathcal{E},\mathbf{W},\mathbf{A})$$ \mathcal G(\mathcal V,\mathcal E,\mathbf W,\mathbf A) $
     • label 信息矩阵$\mathbf{Y}$$ \mathbf Y $
     • embedding 维度$d$$ d $
     • 收敛阈值$ϵ$$ \epsilon $

   • 输出：节点的 embedding 矩阵$\mathbf{H}$$ \mathbf H $

   • 步骤：

     • 构建结构邻近度矩阵${\mathbf{S}}^{(G)}$$ \mathbf S^{(G)} $ 、属性邻近度矩阵${\mathbf{S}}^{(A)}$$ \mathbf S^{(A)} $ 、label 邻近度矩阵${\mathbf{S}}^{(YY)}$$ \mathbf S^{(YY)} $

     • 计算拉普拉斯矩阵${\mathbf{L}}^{(G)},{\mathbf{L}}^{(A)},{\mathbf{L}}^{(Y)}$$ \mathbf L^{(G)},\mathbf L^{(A)},\mathbf L^{(Y)} $

     • 初始化：$t=1,{\mathbf{U}}^{(A)}=\mathbf{0},{\mathbf{U}}^{(Y)}=\mathbf{0},\mathbf{H}=\mathbf{0}$$ t=1,\mathbf U^{(A)} = \mathbf 0, \mathbf U^{(Y)} = \mathbf 0,\mathbf H = \mathbf 0 $

     • 迭代，直到${\mathcal{J}}_t-{\mathcal{J}}_{t-1}\le ϵ$$ \mathcal J_t - \mathcal J_{t-1} \le \epsilon $ 。迭代步骤为：

       • 通过求解下式来更新${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ ：

         $$({\mathbf{L}}^{(G)}+{\alpha }_1{\mathbf{U}}^{(A)}{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}+{\alpha }_2{\mathbf{U}}^{(Y)}{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(G)}={\lambda }_1{\mathbf{U}}^{(G)}$$

       • 通过求解下式来更新${\mathbf{U}}^{(A)}$$ \mathbf U^{(A)} $ ：（这里采用更新后的${\mathbf{U}}^{(G)}$$ \mathbf U^{(G)} $ ）

         $$({\alpha }_1{\mathbf{L}}^{(A)}+{\alpha }_1{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(A)}={\lambda }_2{\mathbf{U}}^{(A)}$$

       • 通过求解下式来更新${\mathbf{U}}^{(Y)}$$ \mathbf U^{(Y)} $ ：（这里采用更新后的${\mathbf{U}}^{(G)},{\mathbf{U}}^{(A)}$$ \mathbf U^{(G)},\mathbf U^{(A)} $ ）

         $$({\alpha }_2{\mathbf{L}}^{(YY)}+{\alpha }_2{\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+\mathbf{H}{\mathbf{H}}^{\mathrm{\top }}){\mathbf{U}}^{(Y)}={\lambda }_3{\mathbf{U}}^{(Y)}$$

       • 通过求解下式来更新$\mathbf{H}$$ \mathbf H $ ：（这里采用更新后的${\mathbf{U}}^{(G)},{\mathbf{U}}^{(A)},{\mathbf{U}}^{(Y)}$$ \mathbf U^{(G)},\mathbf U^{(A)},\mathbf U^{(Y)} $ ）

         $$({\mathbf{U}}^{(G)}{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}+{\mathbf{U}}^{(A)}{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}+{\mathbf{U}}^{(Y)}{\mathbf{U}}^{(Y{)}^{\mathrm{\top }}})\mathbf{H}={\lambda }_4\mathbf{H}$$

5. 算法复杂度：LANE 框架在收敛之前只需要进行少量的迭代，在每轮迭代过程中都需要进行四个特征值分解。为计算${\mathbb{R}}^{n\times n}$$ \mathbb R^{n\times n} $ 矩阵的top d 个特征向量，类似于 Lanczos 方法的特征值分解方法最坏情况需要$O(d{n}^2)$$ O(dn^2) $ 复杂度。

   令$T_a$$ T_a $ 表示计算所有邻近度矩阵需要的计算复杂度，则 LANE 的总的时间复杂度为$O(T_a+d{n}^2)$$ O(T_a+dn^2) $ ，这与谱嵌入 spectral embedding 的计算复杂度相同。由于$d\ll n$$ d\ll n $ ，而$T_a$$ T_a $ 由$\mathbf{W}$$ \mathbf W $ 和$\mathbf{A}$$ \mathbf A $ 中的非零元素决定，因此LANE 总的时间复杂度为$O(n^2+n\mathcal{T})$$ O(n^2 + n \mathcal T) $ ，其中$\mathcal{T}$$ \mathcal T $ 为$\mathbf{W}$$ \mathbf W $ 和$\mathbf{A}$$ \mathbf A $ 中所有非零元素总数。

   另外，可以很容易得到 LANE 的空间复杂度为$O(n^2)$$ O(n^2) $ 。

   这种复杂度对于大型网络而言是不可行的。

6. 在某些网络中节点属性或者节点label 可能不可用。如，当移动通信公司希望分析客户网络以便提供更好的服务时，他们只能收集到通讯网络及其部分label 信息，通讯内容、用户偏好之类的属性不可用。LANE 也能够处理这类场景，其中节点属性或节点label 之一发生缺失，或者二者全部缺失。

   我们以label 信息缺失为例，此时$\mathcal{J}$$ \mathcal J $ 的两项不可用：${\mathcal{J}}_Y$$ \mathcal J_Y $ （它用于为label 信息建模）、${\rho }_4$$ \rho_4 $ （它用于对label 邻近性和$\mathbf{H}$$ \mathbf H $ 的相关性进行建模）。移除这两项之后，我们的目标函数为：

   $$\begin{array}{c}\underset{{\mathbf{U}}^{(G)},{\mathbf{U}}^{(A)},\mathbf{H}}{max}\mathcal{J}={\mathcal{J}}_G+{\beta }_1{\mathcal{J}}_A+{\beta }_2{\rho }_1+{\rho }_2+{\rho }_3\\ s.t.{\mathbf{U}}^{(G{)}^{\mathrm{\top }}}{\mathbf{U}}^{(G)}=\mathbf{I},{\mathbf{U}}^{(A{)}^{\mathrm{\top }}}{\mathbf{U}}^{(A)}=\mathbf{I},{\mathbf{H}}^{\mathrm{\top }}\mathbf{H}=\mathbf{I}\end{array}$$

   其中${\beta }_1>0,{\beta }_2>0$$ \beta_1\gt 0, \beta_2 \gt 0 $ 决定了节点属性的贡献，以及节点属性和网络结构相关性的贡献。

   LANE 的这种变体我们称作 LANE_w/o_LABEL ，其求解方法也类似于上述交替优化算法。

20.2 实验

1. 数据集：

   • BlogCatalog 数据集：一个博客社区，用户彼此关注从而构成一个网络。用户可以生成关键词来作为其博客的简短描述，我们将这些关键词作为节点（用户）的属性。用户也可以将其博客注册为指定的类别，我们将这些类别作为用户的 label 。
   • Flickr 数据集：一个在线图片共享社区，用户彼此关注从而构成一个网络。用户可以为图片指定 tag ，我们将这些 tag 作为节点（用户）的属性。用于可以加入不同的组，我们将这些组作为用户的 label 。

   

2. Baseline 模型可以分为四类：

   • 首先，为评估embedding 的效果，我们使用原始特征作为 baseline 。
   • 然后，为评估节点属性的贡献，我们考虑三种仅嵌入网络结构的方法，包括 DeepWalk,LINE, LANE_on_Net 。
   • 接着，为评估label信息的贡献，我们考虑两种 ANE 方法，包括 LCMF 和 LANE_w/o_Label 。
   • 最后，为评估 LANE 的效果，我们考虑SpecComb 和 MultiView 方法。

   具体描述如下：

   • Original Features 原始特征：将原始网络结构特征、原始节点属性特征直接拼接，从而作为节点特征。
   • DeepWalk：使用 SkipGram 学习基于图上的、截断的随机游走序列从而得到图的 embedding 。
   • LINE：建模图的一阶邻近度和二阶邻近度从而得到图的 embedding 。
   • LCMF：它通过对网络结构信息和节点属性信息进行联合矩阵分解来学习图的 embedding 。
   • SpecComb：将属性网络$\mathcal{G}$$ \mathcal G $ 和 label$\mathbf{Y}$$ \mathbf Y $ 拼接到一个矩阵，然后执行归一化的谱嵌入 normalized spectral embedding 。最后选择 top d 的特征向量作为embedding 。
   • MultiView：将网络结构、节点属性、节点 label 视为三个视图，并在它们上共同应用正则化的谱聚类spectral clustering 。
   • LANE_on_NET 和 LANE_W/o_LABEL：是LANE 的两个变种。LANE_on_NET 仅对单纯的网络结构建模， LANE_W/o_LABEL 对网络结构和节点属性建模（没有节点label 信息）。

3. 实验配置：我们验证不同算法学到的 embedding 对节点分类任务的有效性。我们使用五折交叉验证，并随机将数据集划分为训练集和测试集。其中，训练集不包含任何测试集的信息（训练期间测试节点是 unseen 的），但是测试集包含测试节点到任何其它节点的链接信息。

   我们首先在训练集上学到节点的 embedding，然后在训练集上训练一个SVM 分类器，分类器的输入为节点的 embedding、输出为节点的label 类别。然后，为了得到测试集的 embedding，我们首先构造两个线性映射函数${\mathbf{B}}^{(G)}$$ \mathbf B^{(G)} $ 和${\mathbf{B}}^{(A)}$$ \mathbf B^{(A)} $ ，它将图的权重矩阵$\mathbf{W}$$ \mathbf W $ 和节点属性矩阵$\mathbf{A}$$ \mathbf A $ 映射到 embedding 空间$\mathbf{V}$$ \mathbf V $ ：

   $$\mathbf{W}=\mathbf{V}{\mathbf{B}}^{(G)},\mathbf{A}=\mathbf{V}{\mathbf{B}}^{(A)}$$

   这相当于是根据$\mathbf{W}$$ \mathbf W $ 和$\mathbf{A}$$ \mathbf A $ 来拟合unseen 节点的$\mathbf{V}$$ \mathbf V $ 。

   为简单起见这里我们使用线性映射，也可以使用其它非线性映射函数。我们并没有根据测试集来训练 embedding，因为这会泄露测试集的 label 信息$\mathbf{Y}$$ \mathbf Y $ 。我们可以通过训练集来学习参数${\mathbf{B}}^{(G)}$$ \mathbf B^{(G)} $ 和${\mathbf{B}}^{(A)}$$ \mathbf B^{(A)} $ ，然后对于测试集的第$k$$ k $ 个顶点，其 embedding 向量为：

   $${\overrightarrow{\mathbf{h}}}_k={\overrightarrow{\mathbf{w}}}_k{\left({\overrightarrow{\mathbf{B}}}^{(G)}\right)}^{-1}+\delta {\overrightarrow{\mathbf{a}}}_k{\left({\overrightarrow{\mathbf{B}}}^{(A)}\right)}^{-1}$$

   其中：$\delta >0$$ \delta \gt 0 $ ，它平衡了$\mathbf{W}$$ \mathbf W $ 和$\mathbf{A}$$ \mathbf A $ 的贡献；$(\cdot {)}^{-1}$$ (\cdot)^{-1} $ 为逆矩阵。

   最后我们基于测试集的 embedding 和训练集学到的 SVM 分类器来对测试集进行分类，并报告分类的 F1 指标。每种配置都随机执行 10 次并报告指标的均值。

   对于所有方法，embedding 维度为$d=100$$ d=100 $ 。Baseline 方法的其它超参数都使用原始论文中的超参数，LANE 方法的超参数通过grid search 搜索到合适的值。

4. 为证明embedding 的有效性，我们将 LANE 及其变体与原始特征进行比较。其中 BlogCatalog 数据集的原始特征为 12346 维、Flickr 数据集的原始特征为 18107 维。实验中，我们将 embedding 维度从5 增加到 100。我们给出了Flickr 数据集上不同$d$$ d $ 对应的分类效果。我们忽略了 BlogCatalog 数据集，因为结果也类似。

   结论：

   • 当$d=60$$ d=60 $ 远小于18107 时，LANE_w/o_Label 可以达到和原始特征相近的分类能力。
   • 当$d=35$$ d=35 $ 远小于18107 时，LANE 可以达到和原始特征相近的分类能力。
   • LANE_on_Net 比原始特征效果更差，这是因为它仅包含网络结构信息。

   因此，通过利用 embedding representation learning，LANE 实现了比原始特征更好的性能。

   

5. 为研究 LANE 的有效性，我们对比了所有的 Baseline 模型。我们固定$d=100$$ d=100 $ ，并将训练样本规模设置为原始训练集大小的$\{\frac{1}{16},\frac{1}{8},\frac{1}{4},\frac{1}{2},1\}$$ \{\frac{1}{16},\frac{1}{8},\frac 14,\frac 12,1\} $ 。

   结论：

   • 所有情况下，LANE 总是优于Baseline 模型。
   • 当训练数据规模从$\frac{1}{16}$$ \frac 1{16} $ 增加到 100% 时，LANE 的性能持续改善，但增长的幅度变小。

   

6. 为评估label 信息对于 embedding 的影响，我们分析上表中的数据。

   • 与单纯的网络结构embedding 方法(DeepWalk, LINE, LANE_on_Net ) 相比，使用了节点属性信息的 LANE_w/o_Label 的效果更好。但是利用了label 信息之后，LANE 进一步超越了LANE_w/o_Label。这证明了将label 信息融合到 embedding 中的优势。

     另外 LANE 也超过了属性网络embedding 方法 LCMF，这进一步证明了label 信息的优势。

   • 通过 LANE 和 SpecComb/MultiView 的比较发现，SpecComb/MultiView 的效果始终不如 LANE，甚至比单纯的网络结构 embedding 方法（如 DeepWalk ）更差。这是因为：

     • SpecComb 没有明确考虑固有的相关性，并且直接拼接异质信息并不是组合异质信息的合适方法。
     • MultiView 会平等对待网络结构、节点属性、label 信息，这也不是融合这些异质信息的好方法。

   所有这些观察结果表明：

   • 属性网络和label 之间确实存在很强的相关性。
   • label 信息确实可以帮助我们获得更好的 embedding representation 。
   • 如何融合label 信息需要一种合适的方法。

   LINE 通过执行 label informed embedding 成功地实现了这一提升，并始终优于所有 baseline 方法。我们要强调的是：在节点分类任务中，所有方法都可以访问训练集中的 label，并以不同的方式利用label 信息。只有 LANE, SpecComb, MultiView 可以将这些 label 合并到 embedding representation learning 中。因此，LANE 的优势不是拥有额外的信息源，而是执行 label informed embedding 的结果。

7. 超参数${\alpha }_1,{\alpha }_2$$ \alpha_1,\alpha_2 $ 平衡了属性网络和label 信息的贡献。我们同时将它们从 0.01 增加到 100。Flickr 数据集上的指标如下，BlogCatalog 也有类似结果因此省略。

   结论：

   • 当属性网络和label 信息都具有足够的贡献时，即${\alpha }_1>1,{\alpha }_2>10$$ \alpha_1\gt 1,\alpha_2 \gt 10 $ 时，LANE 会实现相对较高的性能。

   • 当${\alpha }_1$$ \alpha_1 $ 很小，最佳性能出现在${\alpha }_2$$ \alpha_2 $ 适中，如${\alpha }_2\simeq 1$$ \alpha_2 \simeq 1 $ 。当${\alpha }_2$$ \alpha_2 $ 很小，结论也类似。

   • 当固定${\alpha }_1=100$$ \alpha_1 = 100 $ ，${\alpha }_2$$ \alpha_2 $ 从 0.01 变化到 100 时，模型性能提升了 42.7%；当固定${\alpha }_2=100$$ \alpha_2=100 $ ,${\alpha }_1$$ \alpha_1 $ 从 0.01 变化到 100 时，模型性能提升了 16.07%。这表明label 信息对于 LANE 的影响大于属性网络。

     因为在相同范围内取值时，模型性能随${\alpha }_2$$ \alpha_2 $ 的波动更大，这说明 label 信息的影响更大。

   总之，通过配置合理的参数，LANE 可以实现相对较高的性能。同时，label 信息在 embedding 过程中非常重要。

   

8. 我们将$d$$ d $ 从 20 变化到 180 来研究分类性能的影响。。在 Flickr 数据集上不同方法的效果和 d 的关系如下图，BlogCatalog 也有类似结果因此省略。

   结论：

   • 当$d>20$$ d\gt 20 $ 时之前观察到的结论都成立：LANE始终比所有基准方法效果更好。
   • 增加$d$$ d $ 时 LANE 的分类性能首先提高，然后保持稳定。这在实际应用中很有吸引力，因为人们可以在大范围内安全地调整超参数$d$$ d $ 。

   

9. 最后我们比较 LANE 和两种属性网络 ANE 方法（LCMF 和 MultiView ）的运行时间。我们在 Flickr 数据集上观察输入节点数量和训练时间（对数表示）的关系，BlogCatalog 也有类似结果因此省略。

   结论：LANE 的运行时间最少。原因是：

   • LCMF 基于随机梯度下降来优化，这通常收敛速度很慢。
   • MultiView 具有和 LANE 相同的时间复杂度，但经验表明 LANE 可以在这两个数据集上仅使用几个迭代就能收敛。因此这证明了 LANE 的计算效率。