一、TADW [2015]

《Network Representation Learning with Rich Text Information》

1. 网络在我们的日常生活中无处不在，例如 Facebook 用户之间的友谊或学术论文之间的引用。近年来，研究人员广泛研究了网络中许多重要的机器学习应用，例如顶点分类（vertex classification ）、标签推荐（ tag recommendation）、异常检测 （anomaly detection）、链接预测（ link prediction）。数据稀疏（ data sparsity ）是这些任务面临的常见问题。为了解决数据稀疏性问题，network representation learning: NRL 在统一的低维空间中编码和表达每个顶点。 NRL 有助于我们更好地理解顶点之间的语义相关性（semantic relatedness ），并进一步缓解稀疏性带来的不便。

   NRL 中的大多数工作从网络结构中学习 representation。例如，social dimensions 是计算网络的拉普拉斯（ Laplacian ）矩阵或 modularity 矩阵的特征向量（ eigenvectors ）。最近，NLP 中的 word representation 模型 SkipGram 被引入，用于从社交网络中的随机游走序列中学习顶点的 representation，称作 DeepWalk 。social dimensions 和 DeepWalk 方法都将网络结构作为输入来学习 network representation，但是没有考虑任何其它信息。

   在现实世界中，网络中的顶点通常具有丰富的信息，例如文本内容和其它元数据（ meta data）。例如，维基百科文章相互连接并形成网络，每篇文章作为一个顶点都包含大量的文本信息，这些文本信息可能对 NRL 也很重要。因此，论文 《Network Representation Learning with Rich Text Information》 提出了同时从网络结构和文本信息中学习 network representation 的想法，即 text-associated DeepWalk: TADW 。

   • 一种直接的方法是：分别独立地从文本特征和网络特征中学习 representation，然后将两个独立的 representation 拼接起来。然而，该方法没有考虑网络结构和文本信息之间复杂的交互 interaction ，因此通常会导致效果不佳。

   • 在现有的 NRL 框架中加入文本信息也不容易。例如，DeepWalk 在网络中的随机游走过程中，无法轻松地处理附加信息。

   幸运的是，给定网络 $G=(V,E)$$G=(V,E)$ ，论文证明 DeepWalk 实际上是分解矩阵 $\mathbf{M}\in {\mathbb{R}}^{|V|\times |V|}$$\mathbf M\in \mathbb R^{|V|\times |V|}$，其中每一项 $M_{i,j}$$M_{i,j}$ 是顶点 $v_i$$v_i$ 以固定 steps 随机游走到顶点 $v_j$$v_j$ 的平均概率的对数。下图 (a) 展示了 MF 风格的 DeepWalk：将矩阵 $\mathbf{M}$$\mathbf M$ 分解为两个低维矩阵 $\mathbf{W}\in {\mathbb{R}}^{k\times |V|},\mathbf{H}\in {\mathbb{R}}^{k\times |V|}$$\mathbf W\in \mathbb R^{k\times |V| }, \mathbf H\in \mathbb R^{ k\times |V| }$ ，其中 $k\ll |V|$$k\ll |V|$ 。DeepWalk 将矩阵 $\mathbf{W}$$\mathbf W$ 作为顶点 representation。我们将在后面进一步详细介绍。

   

   DeepWalk 的矩阵分解视角启发了作者将文本信息引入到 NRL 的 MF 中。如上图 (b) 展示了论文方法的主要思想：将矩阵 $\mathbf{M}$$\mathbf M$ 分解为三个矩阵的乘积：$\mathbf{W}\in {\mathbb{R}}^{k\times |V|},\mathbf{H}\in {\mathbb{R}}^{k\times f_t},\mathbf{T}\in {\mathbb{R}}^{f_t\times |V|}$$\mathbf W\in \mathbb R^{k\times |V|}, \mathbf H\in \mathbb R^{k\times f_t}, \mathbf T\in \mathbb R^{f_t\times |V|}$ ，其中 $\mathbf{T}$$\mathbf T$ 为文本特征矩阵。然后论文拼接 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}\mathbf{T}$$\mathbf H\mathbf T$ 作为每个顶点的 $2k$$2k$ 维的 representation 。

   论文在三个数据集上针对多个 baseline 测试了 TADW 算法。当训练集比率 training ratio在 10% ~ 50% 的范围内时，TADW 的representation 的分类准确率比其它 baseline 高达 2% ~ 10% 。当训练集比率小于 10% 时，论文还使用半监督分类器 Transductive SVM: TSVM 测试这些方法。TADW 在 1% 的训练集比率下，相比其它 baseline 方法提升了 5% ~ 20% ，尤其是在网络信息包含噪音的情况下。

   论文主要贡献：

   • 论文证明了 DeepWalk 算法实际上分解了一个矩阵 $\mathbf{M}$$\mathbf M$，并找出了 $\mathbf{M}$$\mathbf M$ 的封闭形式 closed form 。

   • 论文将文本特征引入 NRL，并相比其它 baseline 获得了 5% ~ 20% 的优势，尤其是在训练集比率较小的情况下。

2. 相关工作：representation learning 广泛应用于计算机视觉、自然语言处理、knowledge representation learning 。一些研究集中在 NRL，但它们都无法泛化来处理顶点的其它特征。据作者所知，很少有工作致力于考虑 NRL 中的文本信息。

   有一些主题模型topic model ，如 NetPLSA，在主题建模时同时考虑了网络和文本信息，然后可以用主题分布（ topic distribution ）来表示每个顶点。在本文中，作者以 NetPLSA 作为 baseline 方法。

1.1 模型

1.1.1 DeepWalk 作为矩阵分解

1. 公式化 NRL ：给定网络 $G=(V,E)$$G=(V,E)$，我们希望为每个顶点 $v$$v$ 构建一个低维 representation 向量 ${\overrightarrow{\mathbf{w}}}_v\in {\mathbb{R}}^k$$\mathbf{\vec w}_v\in \mathbb R^k$ ，其中 $k\ll |V|$$k \ll |V|$ 。作为一种稠密的 real-valued representation，${\overrightarrow{\mathbf{w}}}_v$$\mathbf{\vec w}_v$ 可以缓解邻接矩阵等 network representation 的稀疏性。我们可以将 ${\overrightarrow{\mathbf{w}}}_v$$\mathbf{\vec w}_v$ 视为顶点 $v$$v$ 的特征，并将这些特征应用到许多机器学习任务中，如顶点分类。这些特征可以方便地提供给许多分类器，例如逻辑回归、SVM 。注意，representation 不是特定于任务（task-specific ）的，可以在不同任务之间共享。

   我们首先介绍 DeepWalk，然后给出 DeepWalk 和矩阵分解之间的等价证明。

a. DeepWalk

1. DeepWalk 首次将应用广泛的分布式 word representation 方法 SkipGram 引入到社交网络的研究中，从而根据网络结构来学习 vertex representation 。

   DeepWalk 首先生成短的随机游走（short random walk ）（短的随机游走也被用作相似性度量）。给定一条由随机游走生成的顶点序列 $\mathcal{S}=\{v_1,v_2,\cdots ,v_{|\mathcal{S}|}\}$$\mathcal S=\{v_1,v_2,\cdots,v_{|\mathcal S|}\}$，我们将顶点 $v\in \{v_{i-t},\cdots ,v_{i+t}\},v\ne v_i$$v \in \{v_{i-t},\cdots,v_{i+t}\},v\ne v_i$ 视为中心顶点 $v_i$$v_i$ 的上下文，其中 $t$$t$ 为窗口大小（window size） 。遵循 SkipGram 的思想，DeepWalk 旨在最大化随机游走顶点序列 $\mathcal{S}$$\mathcal S$ 中所有 vertex-context pair 的平均对数概率（ average log probability）：

   $$\frac{1}{|\mathcal{S}|}\sum _{i=1}^{|\mathcal{S}|}\sum _{-t\le j\le t,j\ne 0}\log p(v_{i+j}\mid v_i)$$

   其中 $p(v_j\mid v_i)$$p(v_j\mid v_i)$ 以 softmax 函数的方式来定义：

   $$p(v_j\mid v_i)=\frac{\exp \left({\overrightarrow{\mathbf{c}}}_{v_j}^{\mathrm{\top }}{\overrightarrow{\mathbf{w}}}_{v_i}\right)}{\sum _{v\in V}\exp \left({\overrightarrow{\mathbf{c}}}_v^{\mathrm{\top }}{\overrightarrow{\mathbf{w}}}_{v_i}\right)}$$

   其中 ：

   • ${\overrightarrow{\mathbf{w}}}_{v_i}$$\mathbf{\vec w}_{v_i}$ 为顶点 $v_i$$v_i$ 作为 center vertex 时的 represetation 向量。

   • ${\overrightarrow{\mathbf{c}}}_{v_j}$$\mathbf{\vec c}_{v_j}$ 为顶点 $v_j$$v_j$ 作为 context vertex 时的 representation 向量。

   即，每个顶点 $v$$v$ 有两个 representation 向量：当 $v$$v$ 作为 center vertex 时的 ${\overrightarrow{\mathbf{w}}}_v$$\mathbf{\vec w}_v$ 、当 $v$$v$ 作为 context vertex 时的 ${\overrightarrow{\mathbf{c}}}_v$$\mathbf{\vec c}_v$ 。

   之后，DeepWalk 使用 SkipGram 和 Hierarchical Softmax 从随机游走生成的序列中学习顶点的 representation。注意，Hierarchical Softmax 是用于加速的 softmax 的变体。

b. 等价性证明

1. 假设一个 vertex-context 集合 $\mathcal{D}$$\mathcal D$ 是从随机游走序列中生成，其中每个元素为一个 vertex-context pair $(v,c)$$(v,c)$ 。定义 vertex 集合为 $V$$V$，定义 context 集合为 $V_C$$V_C$ ，并且大多数情况下 $V=V_C$$V=V_C$ 。

   DeepWalk 将一个vertex $v$$v$ 嵌入到一个 $k$$k$ 维向量 ${\overrightarrow{\mathbf{w}}}_v\in {\mathbb{R}}^k$$\mathbf{\vec w}_v\in \mathbb R^k$。另外，一个 context $v\in V_C$$v\in V_C$ 被嵌入到一个 $k$$k$ 维向量 ${\overrightarrow{\mathbf{c}}}_v\in {\mathbb{R}}^k$$\mathbf{\vec c}_v\in \mathbb R^k$ 。令 $\mathbf{W}\in {\mathbb{R}}^{k\times |V|}$$\mathbf W\in \mathbb R^{k\times |V| }$ 为所有 vertex embedding 组成的矩阵，其中第 $i$$i$ 行表示顶点 $v_i$$v_i$ 的 vertex representation。令 $\mathbf{H}\in {\mathbb{R}}^{k\times |V|}$$\mathbf H\in \mathbb R^{k\times|V| }$ 为 所有 context embedding 组成的矩阵，其中第 $i$$i$ 行表示顶点 $v_i$$v_i$ 的 context representation。我们的目标是找出矩阵 $\mathbf{M}$$\mathbf M$ 的封闭形式 closed form，其中 $\mathbf{M}={\mathbf{W}}^{\mathrm{\top }}\mathbf{H}$$\mathbf M = \mathbf W^\top\mathbf H$ 。

2. 现在我们考虑一个 vertex-context pair $(v,c)$$(v,c)$ 。定义 $N(v,c)$$N(v,c)$ 为 $(v,c)$$(v,c)$ 出现在 $\mathcal{D}$$\mathcal D$ 中的次数，$N(v)=\sum _{c\in V_C}N(v,c)$$N(v)=\sum_{c\in V_C}N(v,c)$ 为vertex $v$$v$ 出现在 $\mathcal{D}$$\mathcal D$ 中的次数，$N(c)=\sum _{v\in V}N(v,c)$$N(c) = \sum_{v\in V}N(v,c)$ 为 context $c$$c$ 出现在 $\mathcal{D}$$\mathcal D$ 中的次数。

   《Neural word embedding as implicit matrix factorization》已经证明：当维度 $k$$k$ 足够大时，带负采样的 SkipGram （SkipGram with Negative Sampling: SGNS） 相当于隐式地分解 word-context 矩阵 $\mathbf{M}$$\mathbf M$ 。其中 $\mathbf{M}$$\mathbf M$ 的元素为：

   $$M_{i,j}=\log \frac{N(v_i,c_j)\times |\mathcal{D}|}{N(v_i)\times N(c_j)}-\log \lambda$$

   其中 $\lambda$$\lambda$ 为每个 word-context pair 的负样本数量。

   $M_{i,j}$$M_{i,j}$ 可以解释为 word-context pair $(v_i,c_j)$$(v_i,c_j)$ 的 Pointwise Mutual Information: PMI 的 $\log \lambda$$\log \lambda$ 偏移。

   类似地，我们可以证明带 softmax 的 SkipGram 相当于分解矩阵 $\mathbf{M}$$\mathbf M$，其中：

   $$M_{i,j}=\log \frac{N(v_i,c_j)}{N(v_i)}$$

3. 我们现在讨论 DeepWalk 中的 $M_{i,j}$$M_{i,j}$ 代表什么。显然， vertex-context pair 的采样方法会影响矩阵 $\mathbf{M}$$\mathbf M$ 。假设网络是连通（ connected ）和无向 （undirected ）的，窗口大小为 $t$$t$ 。我们将基于 DeepWalk 算法的理想的采样方法来讨论 $N(v)/|\mathcal{D}|$$N(v)/|\mathcal D|$，$N(c)/|\mathcal{D}|$$N(c)/|\mathcal D|$，以及 $N(v,c)/N(v)$$N(v,c)/N(v)$ ：

   • 首先我们生成一条足够长的随机游走序列 $RW$$RW$ 。令 $R{W}_i$$RW_i$ 表示随机游走序列 $RW$$RW$ 上位置 $i$$i$ 的顶点。

   • 然后我们将 vertex-context pair $(R{W}_i,R{W}_j)$$(RW_i,RW_j)$ 添加到 $\mathcal{D}$$\mathcal D$ 中，当且仅当 $0<|i-j|\le t$$0\lt |i-j|\le t$ 。

   $N(v_i)/|\mathcal{D}|$$N(v_i)/|\mathcal D|$ 就是顶点 $v_i$$v_i$ 在随机游走中出现的频率，也就是 $v_i$$v_i$ 的 PageRank 值。 $2tN(v_i,v_j)/N(v_i)$$2tN(v_i,v_j)/N(v_i)$ 为在 $v_i$$v_i$ 的左侧或右侧 $t$$t$ 个邻居中观察到 $v_j$$v_j$ 的期望次数。现在我们尝试基于这种理解来计算 $N(v_i,v_j)/N(v_i)$$N(v_i,v_j)/N(v_i)$ 。

   将 PageRank 中的转移矩阵表示为 $\mathbf{A}$$\mathbf A$ 。令 $d_i$$d_i$ 为顶点 $i$$i$ 的 degree，则有：

   $$\begin{array}{c}{A}_{i,j}=\{\begin{array}{ll}1/d_i,& (v_i,v_j)\in E\\ 0,& \text{else}\end{array}\end{array}$$

   我们使用 ${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ 来表示一个 $V$$V$ 维的行向量，其中除了第 $i$$i$ 项为 1 之外其它项均为零。假设我们从顶点 $i$$i$ 开始随机游走并使用 ${\overrightarrow{\mathbf{e}}}_i$$\mathbf{\vec e}_i$ 表示初始状态。那么 ${\overrightarrow{\mathbf{e}}}_i\mathbf{A}$$\mathbf{\vec e}_i \mathbf A$ 是所有顶点的分布，它的第 $j$$j$ 项是顶点 $i$$i$ 随机游走到顶点 $j$$j$ 的概率。因此，${\overrightarrow{\mathbf{e}}}_i{\mathbf{A}}^t$$\mathbf{\vec e}_i \mathbf A^t$ 的第 $j$$j$ 项是顶点 $i$$i$ 以恰好 $t$$t$ 步随机游走到顶点 $j$$j$ 的概率，其中 ${\mathbf{A}}^t$$\mathbf A^t$ 是矩阵 $\mathbf{A}$$\mathbf A$ 的 $t$$t$ 次幂。因此，$[{\overrightarrow{\mathbf{e}}}_i(\mathbf{A}+{\mathbf{A}}^2+\cdots +{\mathbf{A}}^t)]$$\left[\mathbf{\vec e}_i(\mathbf A + \mathbf A^2+\cdots+\mathbf A^t)\right]$ 的第 $j$$j$ 项是 $v_j$$v_j$ 出现在 $v_i$$v_i$ 的右侧 $t$$t$ 个邻居中的期望次数。因此我们有：

   $$\frac{N(v_i,v_j)}{N(v_i)}=\frac{{[{\overrightarrow{\mathbf{e}}}_i(\mathbf{A}+{\mathbf{A}}^2+\cdots +{\mathbf{A}}^t)]}_j}{t}$$

   上述证明也适用于有向图。因此，我们可以看到 $M_{i,j}=\log N(v_i,v_j)/N(v_i)$$M_{i,j} = \log N(v_i,v_j)/N(v_i)$ 为顶点 $v_i$$v_i$ 在 $t$$t$ 步中随机游走到顶点 $j$$j$ 的平均概率的对数。

   通过证明 DeepWalk 等价于矩阵分解，我们提出融合丰富的文本信息到基于 DeepWalk 派生的矩阵分解中。

1.1.2 TADW

1. 这里我们首先简要介绍低秩矩阵分解，然后我们提出从网络和文本信息中学习 representation 的方法。

a. 低秩矩阵分解

1. 矩阵是表示关系型数据（relational data） 的常用方法。矩阵分析的一个有趣主题是通过矩阵的一部分项来找出矩阵的内在结构。一个假设是矩阵 $\mathbf{M}\in {\mathbb{R}}^{b\times d}$$\mathbf M\in \mathbb R^{b\times d}$ 可以用低秩 $k$$k$ 的另一个矩阵来近似，其中 $k\ll \{b,d\}$$k \ll \{b,d\}$ 。然后我们可以在这个假设下用这样一个低秩近似来补全（ complete ）矩阵 $\mathbf{M}$$\mathbf M$ 的缺失值。然而，求解秩约束优化（ rank constraint optimization ）始终是 NP 难的。因此，研究人员求助于寻找矩阵 $\mathbf{W}\in {\mathbb{R}}^{k\times b}$$\mathbf W\in \mathbb R^{k\times b}$ 和 $\mathbf{H}\in {\mathbb{R}}^{k\times d}$$\mathbf H\in \mathbb R^{k\times d}$ ，从而最小化损失函数 $\mathcal{L}(\mathbf{M},{\mathbf{W}}^{\mathrm{\top }}\mathbf{H})$$\mathcal L(\mathbf M,\mathbf W^\top \mathbf H)$ ，并且带有迹范数的约束（ trace norm constraint ）（这个约束可以通过在损失函数中添加一个惩罚项从而进一步地移除）。在本文中，我们使用平方损失函数。

2. 低秩分解：形式上，令矩阵 $\mathbf{M}$$\mathbf M$ 的观察集为 $\mathbf{\Omega }$$\mathbf\Omega$ 。我们希望找到矩阵 $\mathbf{W}\in {\mathbb{R}}^{k\times b}$$\mathbf W\in \mathbb R^{k\times b}$ 和 $\mathbf{H}\in {\mathbb{R}}^{k\times d}$$\mathbf H\in \mathbb R^{k\times d}$ ，从而最小化损失函数：

   $$\underset{\mathbf{W},\mathbf{H}}{min}\sum _{(i,j)\in \mathbf{\Omega }}{(M_{i,j}-{\left({\mathbf{W}}^{\mathrm{\top }}\mathbf{H}\right)}_{i,j})}^2+\frac{\lambda }{2}(\parallel \mathbf{W}{\parallel }_F^2+\parallel \mathbf{H}{\parallel }_F^2)$$

   其中 $\parallel \cdot {\parallel }_F$$\|\cdot\|_F$ 表示矩阵的 Frobenius 范数，$\lambda$$\lambda$ 为正则化系数。

3. 归纳矩阵补全：低秩矩阵分解仅基于 $\mathbf{M}$$\mathbf M$ 的低秩假设来补全矩阵 $\mathbf{M}$$\mathbf M$ 。如果矩阵 $\mathbf{M}$$\mathbf M$ 中的 item 具有附加特征（ additional feature），那么我们可以应用归纳矩阵补全（ inductive matrix completion ）来利用它们。归纳矩阵补全通过融合两个特征矩阵（ feature matrix） 到目标函数中从而利用更多行单元（ row unit ）和列单元（ column unit ）的信息。

   假设我们有特征矩阵 $\mathbf{X}\in {\mathbb{R}}^{f_x\times b}$$\mathbf X\in \mathbb R^{ f_x\times b}$ 和 $\mathbf{Y}\in {\mathbb{R}}^{f_y\times d}$$\mathbf Y\in \mathbb R^{f_y\times d}$ ，其中 $f_x,f_y$$f_x,f_y$ 分别为两个矩阵列向量的维度。我们的目标是求解矩阵 $\mathbf{W}\in {\mathbb{R}}^{k\times f_x}$$\mathbf W\in \mathbb R^{k\times f_x}$ 和 $\mathbf{H}\in {\mathbb{R}}^{k\times f_y}$$\mathbf H\in \mathbb R^{k\times f_y }$ ，从而最小化：

   $$\underset{\mathbf{W},\mathbf{H}}{min}\sum _{(i,j)\in \mathbf{\Omega }}{(M_{i,j}-{\left({\mathbf{X}}^{\mathrm{\top }}{\mathbf{W}}^{\mathrm{\top }}\mathbf{H}\mathbf{Y}\right)}_{i,j})}^2+\frac{\lambda }{2}(\parallel \mathbf{W}{\parallel }_F^2+\parallel \mathbf{H}{\parallel }_F^2)$$

   注意，归纳矩阵补全最初是为了补全具有基因特征和疾病特征的 “基因-疾病”矩阵，其目标与我们的工作有很大不同。受归纳矩阵补全思想的启发，我们将文本信息引入 NRL 。

b. TADW

1. 给定一个网络 $G=(V,E)$$G=(V,E)$ 以及它对应的文本特征矩阵 $\mathbf{T}\in {\mathbb{R}}^{f_t\times |V|}$$\mathbf T\in \mathbb R^{ f_t\times |V|}$ ，我们提出了文本相关的 DeepWalk （text-associated DeepWalk: TADW ）从网络结构 $G$$G$ 和文本特征 $\mathbf{T}$$\mathbf T$ 中学习每个顶点 $v\in V$$v\in V$ 的 representaion 。

2. 回想一下，DeepWalk 分解矩阵 $\mathbf{M}$$\mathbf M$，其中 $M_{i,j}=\log {[{\overrightarrow{\mathbf{e}}}_i(\mathbf{A}+{\mathbf{A}}^2+\cdots +{\mathbf{A}}^t)]}_j/t$$M_{i,j} = \log \left[\mathbf{\vec e}_i(\mathbf A + \mathbf A^2+\cdots+\mathbf A^t)\right]_j/t$ 。 当 $t$$t$ 较大时，准确地计算 $\mathbf{M}$$\mathbf M$ 的计算复杂度为 $O(|V{|}^3)$$O(|V|^3)$ 。实际上，DeepWalk 使用基于随机游走的采样方法来避免显式地、精确地计算矩阵 $\mathbf{M}$$\mathbf M$ 。当 DeepWalk 采样更多的随机游走序列时，性能会更好，但是计算效率会更低。

   在 TADW 中，我们找到了速度和准确性之间的 tradeoff：分解矩阵 $\mathbf{M}=(\mathbf{A}+{\mathbf{A}}^2)/2$$\mathbf M = (\mathbf A + \mathbf A^2)/2$ 。在这里，为了计算效率，我们分解矩阵 $\mathbf{M}$$\mathbf M$ 而不是 $\log \mathbf{M}$$\log \mathbf M$。原因是 $\log \mathbf{M}$$\log \mathbf M$ 比 $\mathbf{M}$$\mathbf M$ 具有更多的非零项，并且具有平方损失的矩阵分解的复杂度与矩阵 $\mathbf{M}$$\mathbf M$ 中非零元素的数量成正比。由于大多数现实世界的网络都是稀疏的，即 $O(|E|)=O(|V|)$$O(|E|) = O(|V|)$ ，因此计算矩阵 $\mathbf{M}$$\mathbf M$ 需要 $O(|V{|}^2)$$O(|V|^2)$ 的时间。如果网络是稠密的，我们甚至可以直接分解矩阵 $\mathbf{A}$$\mathbf A$ 。

   即使是 $O(|V{|}^2)$$O(|V|^2)$ 的计算复杂度，对于百万甚至亿级顶点的网络而言，这个计算复杂度仍然无法接受。

   我们的任务是求解矩阵 $\mathbf{W}\in {\mathbb{R}}^{k\times |V|}$$\mathbf W\in \mathbb R^{k\times |V| }$ 和 $\mathbf{H}\in {\mathbb{R}}^{k\times f_t}$$\mathbf H\in \mathbb R^{k\times f_t }$，从而最小化：

   $$\underset{\mathbf{W},\mathbf{H}}{min}\sum _{(i,j)\in \mathbf{\Omega }}{(M_{i,j}-{\left({\mathbf{W}}^{\mathrm{\top }}\mathbf{H}\mathbf{T}\right)}_{i,j})}^2+\frac{\lambda }{2}(\parallel \mathbf{W}{\parallel }_F^2+\parallel \mathbf{H}{\parallel }_F^2)$$

   为了优化 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}$$\mathbf H$，我们交替最小化 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}$$\mathbf H$，因为它是 $\mathbf{W}$$\mathbf W$ 或 $\mathbf{H}$$\mathbf H$ 的凸函数。虽然 TADW 可能收敛到局部最小值而不是全局最小值，但我们的方法在实践中效果很好，如我们的实验所示。

   也可以直接应用随机梯度下降法来优化。

3. 不同于低秩矩阵分解（ low-rank matrix factorization ）和归纳矩阵补全（inductive matrix completion）（它们聚焦于补全矩阵 $\mathbf{M}$$\mathbf M$），TADW 的目标是结合文本特征从而获得更好的 network representation 。此外，归纳矩阵补全直接从原始数据中获得矩阵 $\mathbf{M}$$\mathbf M$，而我们从 MF 风格的 DeepWalk 的推导中人为地构建矩阵 $\mathbf{M}$$\mathbf M$ 。

   由于从 TADW 获得的 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{T}\mathbf{H}$$\mathbf T\mathbf H$ 都可以视为顶点的低维 representation，因此我们可以通过拼接它们为 network representation 构建一个统一的、$2k$$2k$ 维的矩阵。在实验中，我们将证明统一的 representation 显著优于将 network representation 和文本特征（即矩阵 $\mathbf{T}$$\mathbf T$） 的简单组合。

4. 复杂度分析：在 TADW 中，计算 $\mathbf{M}$$\mathbf M$ 的过程需要 $O(|V{|}^2)$$O(|V|^2)$ 的时间。我们使用 《Large-scale multi-label learning with missing labels》 引入的快速过程来求解 TADW 的优化问题。

   最小化 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}$$\mathbf H$ 的每次迭代的复杂度为 $O(\text{nnz}(\mathbf{M})k+|V|f_{t}k+|V|k^2)$$O(\text{nnz}(\mathbf M)k + |V|f_t k + |V|k^2)$ ，其中 nnz(.) 为矩阵非零元素的个数。作为比较，传统矩阵分解的复杂度（即低秩矩阵分解的优化问题） 为 $O(\text{nnz}(\mathbf{M})k+|V|k^2)$$O(\text{nnz}(\mathbf M)k + |V|k^2)$ 。在我们的实验中，优化在 10 次迭代中收敛。

5. 未来工作：针对大规模网络数据场景的 TADW 在线学习和分布式学习。另外，还可以研究矩阵分解的其它技术，例如 matrix co-factorization，从而包含来自其它来源的丰富信息。

1.2 实验

1. 我们使用顶点分类问题来评估 NRL 的质量。正式地，我们得到顶点的低维 representation 作为顶点特征，然后我们的任务是基于顶点特征用标记顶点集合 $\mathbb{L}$$\mathbb L$ 来预测未标记顶点集合 $\mathbb{U}$$\mathbb U$ 的 label 。

   机器学习中的许多分类器可以处理这个任务。我们分别选择 SVM 和 transductive SVM 从而进行监督的、半监督的学习和测试。注意，由于 representation learning 过程忽略了训练集中的顶点 label ，因此 representation learning 是无监督的。

   我们使用三个公开可用的数据集，并使用 representation learning 的五种 baseline 方法来评估 TADW 。我们从文档之间的链接或引用，以及这些文档的 term frequency-inverse document frequency: TF-IDF 矩阵（即矩阵 $\mathbf{T}$$\mathbf T$）中学习 representation 。

2. 数据集：

   • Cora 数据集：包含来自七个类别的 2708 篇机器学习论文。论文之间的链接代表引用关系，共有 5429个链接。每篇文档映射为一个 1433 维的binary 向量，每一位为0/1 表示对应的单词是否存在。

   • Citeseer数据集：包含来自六个类别的 3312 篇公开发表出版物。文档之间的链接代表引用关系，共4732个链接。每篇文档映射为一个 3703 维的binary 向量，每一位为0/1 表示对应的单词是否存在。

   • Wiki 数据集：包含来自十九个类别的 2405篇维基百科文章。文章之间的链接代表超链接，共 17981 个链接。我们移除了没有任何超链接的文档。每篇文章都用内容单词的 TFIDF 向量来表示，向量维度为 4973 维。

   Cora 和 Citeseer 数据集从标题、摘要中生成短文本作为文档，并经过停用词处理、低频词处理（过滤文档词频低于 10 个的单词），并将每个单词转化为 one-hot 向量。 Cora、Citeseer 数据集平均每篇文档包含 18~32 个单词，数据集被认为是有向图。

   Wiki 数据集是长文本，平均每篇文档包含640 个单词，数据集被认为是无向图。

3. baseline 方法及其配置：

   • TADW ：通过SVD 分解 TFIDF 矩阵到 200 维的文本特征矩阵 $\mathbf{T}\in {\mathbb{R}}^{200\times |V|}$$\mathbf T\in \mathbb R^{200\times |V|}$ ，这是为了降低矩阵 $\mathbf{H}$$\mathbf H$ 的规模。我们也将文本特征矩阵 $\mathbf{T}$$\mathbf T$ 视为一个 content-only 的 baseline 。

     对于 Cora,Citeseer 数据集 $k=80,\lambda =0.2$$k = 80,\lambda = 0.2$ ；对于 Wiki 数据集 $k=100,200,\lambda =0.2$$k = 100,200,\lambda = 0.2$ 。

     注意：最终每个顶点的representation 向量的维度为 $2k$$2k$ 。

   • DeepWalk：DeepWalk 是一种 network-only representation learning 方法。我们选择参数为：窗口尺寸 $t=10$$t=10$，每个顶点的游走序列数量 $\gamma =80$$\gamma = 80$。对于 Cora,Citeseer 数据集维度 $k=100$$k=100$，对于 Wiki 数据集维度 $k=200$$k=200$ ，这些是在 50 ~200 之间选择的性能最佳的维度。

     我们还通过求解“低秩分解”方程并将 $\mathbf{W}$$\mathbf W$ 和 $\mathbf{H}$$\mathbf H$ 拼接起来作为顶点 representation 从而评估 MF-style DeepWalk 的性能。结果与 DeepWalk 相比差不多，因此我们仅报告了原始 DeepWalk 的性能。

   • pLSA：我们使用 PLSA 通过将每个顶点视为一个文档来从 TF-IDF 矩阵训练主题模型。因此，PLSA 是 content-only baseline 方法。PLSA 通过 EM 算法估计文档的主题分布和主题的 word 分布。我们使用文档的主题分布作为顶点 representation。

   • Text Features：使用文本特征矩阵 $\mathbf{T}\in {\mathbb{R}}^{200\times |V|}$$\mathbf T\in \mathbb R^{200\times |V| }$ 作为每篇文档的 200 维 representation，这也是一种 content-only baseline 方法。

   • Naive Combination：直接拼接 DeepWalk 的embedding 向量和文本特征向量。对于 Cora,Citeseer 数据集这将得到一个300 维向量；对于Wiki 数据集这将得到一个 400 维向量。

   • NetPLSA ：NetPLSA 将文档之间的链接视为网络正则化来学习文档的主题分布，存在链接的文档应该共享相似的主题分布。我们使用网络增强的文档主题分布作为 network representation 。

     NetPLSA 可以视为一种兼顾网络和文本信息的 NRL 方法。我们将 Cora,Citeseer 数据集主题数量设置为 160，将 Wiki 数据集主题数量设置为 200 。

4. 评估方式：对于监督分类器，我们使用由 Liblinear 实现的linear SVM。对于半监督分类器，我们使用 SVM-Light 实现的 transductive SVM 。我们对 TVSM 使用线性核。我们为每个类别训练一个 one-vs-rest 分类器，并选择 linear SVM 和 transductive SVM 中得分最高的类别。

   我们将顶点的 representation 作为特征来训练分类器，并以不同的训练比率 training ratio来评估分类准确性。训练比率从 linear SVM 的 10% ~ 50% ，以及从 TSVM 的 1% ~ 10% 不等。对于每个训练比率，我们随机选择文档作为训练集，剩余文档作为测试集。我们重复试验 10 次并报告平均准确率。

5. 实验结果：下表给出了 Cora 数据集、Citeseer 数据集、Wiki 数据集的分类准确率。这里 - 表示 TSVM 不能在 12 小时内收敛，因为 representation 的质量较低（对于 TADW，TADM 总是可以在 5 分钟内收敛）。我们没有在 Wiki 数据集上展示半监督学习的结果，因为监督 SVM 已经在这个数据集上以较小的训练比率获得了有竞争力的、甚至更好的性能。因此，我们仅报告 Wiki 数据集的有监督 SVM 的结果。Wiki 数据集的类别要比其它两个数据集多得多，这需要更多的数据来进行足够的训练，因此我们将最小训练比率设为 3%。

   从这些表中我们可以看到：

   • TADW 在所有三个数据集上始终优于所有其它 baseline。此外，TADW 可以在 Cora 数据集和 Citeseer 数据集上减少 50% 的训练数据从而击败其它 baseline 。这些实验证明 TADW 是有效且鲁棒的。

   • TADW 对于半监督学习有更显著的提升。TADW 的表现优于最佳的 baseline （即 naive combination），在 Cora 数据集上提升 4%、在 Citeseer 数据集上提升 10% ~ 20%。这是因为在 Citeseer 上的 network representation 质量很差，而 TADW 从噪音的数据中学习比 naive combination 更鲁棒。

   • TADW 在训练比率较小时有更好的表现。大多数 baseline 的准确率随着训练比率的降低而迅速下降，因为它们的vertex representation 对于 training 和 testing 而言非常 noisy 和 inconsistent 。相反，由于 TADW 从网络和文本信息中联合学习 representation，因此 representation 具有更少的噪音并且更加一致。

   这些观察结果证明了 TADW 生成的高质量 representation。此外，TADW 不是 task-specific 的，representation 可以方便地用于不同的任务，例如链接预测、相似性计算、顶点分类等等。TADW 的分类准确性也与最近的几种 collective 分类算法相媲美，尽管我们在学习representation 时没有对任务执行特别的优化。

   

   

   

6. 参数敏感性：TADW 有两个超参数：维度 $k$$k$ 和正则化系数 $\lambda$$\lambda$ 。我们将训练比率固定为 10%，并使用不同的 $k$$k$ 和 $\lambda$$\lambda$ 测试分类准确率。对于 Cora 数据集和 Citeseer 数据集，我们让 $k$$k$ 在 40 ~ 120 之间变化，而 $\lambda$$\lambda$ 在 0.1 ~ 1 之间变化。对于 Wiki 数据集，我们让 $k$$k$ 在 100 ~ 200 之间变化，而 $\lambda$$\lambda$ 在 0.1 ~ 1 之间变化。下图显示了不同 $k$$k$ 和 $\lambda$$\lambda$ 下分类准确率的变化。

   可以看到：

   • 对于 Cora, Citeseer, Wiki 上的固定 $k$$k$，不同 $\lambda$$\lambda$ 对应的准确率分别在 1.5%, 1%, 2% 的波动范围内。

   • 当 Cora 和 Citeseer 上的 $k\ge 80$$k\ge 80$ 、Wiki 上的 $k\ge 140$$k\ge 140$ 时，准确率具有竞争性 competitive 。因此，当 $k$$k$ 和 $\lambda$$\lambda$ 在合理范围内变化时，TADW 可以保持稳定。

   

7. 案例研究：为了更好地理解 NRL 文本信息的有效性，我们在 Cora 数据集中提供了一个案例。document 标题为 Irrelevant Features and the Subset Selection Problem（不相关特征和子集选择问题）。我们将这篇论文简称为 IFSSP。IFSSP 的类别标签为 Theory。如下表所示，使用 DeepWalk 和 TADW 生成的 representation，我们找到了 5 篇最相似的论文，并基于余弦相似度来排序。

   我们发现，所有这些论文都被 IFSSP 引用。然而，DeepWalk 发现的 5 篇论文中有 3 篇具有不同的类别标签，而 TADW 发现的前 4 篇论文具有相同的类别标签 Theory 。这表明：与单纯的基于网络的 DeepWalk 相比，TADW 可以借助文本信息学到更好的 network representation 。

   DeepWalk 发现的第 5 篇论文也展示了仅考虑网络信息的另一个限制。《MLC Tutorial A Machine Learning library of C classes》 （简称 MLC）是一个描述通用 toolbox 的论文，可以被不同主题的许多论文引用。一旦其中一些论文也引用了 IFSSP，DeepWalk 将倾向于给 IFSSP 一个与 MLC 类似的 representation，即使它们具有完全不同的主题。