一、CANE [2017]

《CANE: Context-Aware Network Embedding for Relation Modeling》

1. network embedding: NE （即 network representation learning: NRL）旨在根据顶点在网络中的结构角色 （structural role） ，从而将网络的顶点映射到低维空间中。network embedding 提供了一种高效（ efficient） 且有效 （effective） 的方法来表达和管理大型网络，缓解了传统基于符号的representation 的计算问题和稀疏性问题。因此，近年来 network embedding 吸引了人们的许多研究兴趣，并在包括链接预测、顶点分类、社区检测在内的许多网络分析任务上取得了可喜的表现。

   在现实世界的社交网络中，一个顶点在与不同的邻居顶点交互时可能表现出不同的方面（ aspect），这是很直观的。例如，研究人员通常与各种合作伙伴就不同的研究主题进行合作（如下图所示），社交媒体用户与分享不同兴趣的各种朋友联系，一个网页出于不同目的链接到多个其它网页。然而，现有的大多数 network embedding 方法只为每个顶点安排一个 single embedding 向量，并产生以下两个问题：

   • 这些方法在与不同邻居交互时，无法灵活转换不同的方面（aspect） 。

   • 在这些模型中，一个顶点倾向于迫使它的所有邻居之间的 embedding 彼此靠近，但事实上并非一直如此。例如下图中，左侧用户和右侧用户共享较少的共同兴趣，但是由于他们都链接到中间用户，因此被认为彼此接近。因此，这使得顶点 embedding 没有区分性。

     即：“朋友的朋友“ 不一定是朋友。

   

   为了解决这些问题，论文《CANE: Context-Aware Network Embedding for Relation Modeling》提出了一个 Context-Aware Network Embedding: CANE 框架，用于精确建模顶点之间的关系。更具体而言，论文在信息网络（ information network ）上应用 CANE。信息网络的每个顶点还包含丰富的外部信息，例如文本text、标签 label、或者其它元数据 meta-data。在这种场景下，上下文的重要性对 network embedding 更为关键。在不失一般性的情况下，论文在基于文本的信息网络中实现了 CANE，但是 CANE 可以很容易地扩展到其它类型的信息网络。

   在传统的 network embedding 模型中，每个顶点都表达为一个静态的 embedding 向量，即 context-free embedding 。相反，CANE 根据与当前顶点交互的不同邻居，从而将动态的 embedding 分配给当前顶点，称为 context-aware embedding 。以一个顶点 $u$$u$ 为例：当与不同的邻居交互时，$u$$u$ 的 context-free embedding 保持不变；而当面对不同的邻居时，$u$$u$ 的 context-aware embedding 是动态的。

   CANE 类似于 GAT，其中不同邻域顶点的 attention 权重是不同的。在 CANE 中，注意力权重是 hard 的（0 或者 1）；在 GAT 中，注意力权重是 soft 的（0 到 1 之间）。

   当顶点 $u$$u$ 与它的邻居顶点 $v$$v$ 交互时，它们彼此相关的 context embedding 分别来自它们的文本信息。对于每个顶点，我们可以轻松地使用神经模型（neural model ），例如卷积神经网络和循环神经网络来构建 context-free embedding 和 text-based embedding 。为了实现 context-aware text-based embedding，论文引入了 selective attention 方案，并在这些神经模型中建立了 $u$$u$ 和 $v$$v$ 之间的互注意力（ mutual attention ）。mutual attention 预期引导神经模型强调那些被相邻顶点 focus 的单词，并最终获得 context-aware embedding。每个顶点的 context-free embedding 和 context-aware embedding 都可以通过使用现有的 network embedding 方法学到（如 DeepWalk，LINE，node2vec）并拼接起来。

   论文对不同领域的三个真实数据集进行了实验。与其它 SOTA 方法相比，链接预测的实验结果展示了论文框架的有效性。结果表明，context-aware embedding 对于网络分析至关重要，特别是对于那些涉及顶点之间复杂交互的任务，如链接预测。论文还通过顶点分类和案例研究来探索论文框架的性能，这再次证实了 CANE 模型的灵活性和优越性。

   CANE 在链接预测方面比 SOTA 方法取得了显著的提升，在顶点分类方面与 SOTA 方法的性能相当。

2. 相关工作：随着大型社交网络的快速增长，network embedding（即 network representation learning）已被提出作为网络分析任务的关键技术。

   近年来，人们已经提出了大量的 network embedding 模型来学习有效的顶点 embedding 。例如：

   • DeepWalk 在网络上执行随机游走，并引入了一种有效的 word representation learning 模型 SkipGram 来学习 network embedding 。

   • LINE 优化大型网络中 edge 的联合概率和条件概率，从而学习顶点 representation。

   • node2vec 将 DeepWalk 中的随机游走策略修改为有偏的随机游走（ biased random walk ），从而更有效地探索网络结构。

   然而，这些 network embedding 模型中的大多数仅将结构信息编码为顶点 embedding，而没有考虑现实世界社交网络中伴随顶点的异质信息（ heterogeneous information ）。为解决这个问题，研究人员努力将异质信息整合到传统的 network embedding 模型中。例如：

   • text-associated Deep-Walk: TADW 使用文本信息改进了基于 DeepWalk 的矩阵分解。

   • max-margin DeepWalk: MMDW 利用顶点的 labeling 信息来学习 network representation 。

   • group enhanced network embedding: GENE 整合了 NE 中存在的 group 信息。

   • context-enhanced network embedding: CENE 将文本内容视为一种特殊的顶点，并同时利用结构信息和文本信息来学习 network embedding 。

   据我们所知，所有现有的 network embedding 模型都聚焦于学习 context-free embedding，但是忽略了顶点和其它顶点交互时的不同角色。相比之下，我们假设一个顶点根据与它交互的不同顶点而具有不同的 embedding ，并提出 CANE 来学习 context-aware embedding 。

1.1 模型

1.1.1 问题定义

1. 我们首先给出一些基本的符号和定义。给定信息网络（ information network ）$G=(V,E,T)$$G=(V,E,T)$，其中 $V$$V$ 为顶点集合，$E\subseteq V\times V$$E \sube V\times V$ 为边集合， $T$$T$ 为顶点的文本信息。每条边 $e_{u,v}\in E$$e_{u,v}\in E$ 表示顶点 $(u,v)$$(u,v)$ 之间的关系，并且关联一个权重 $w_{u,v}$$w_{u,v}$ 。这里顶点 $v\in V$$v\in V$ 的文本信息表达为单词序列 ${\mathcal{S}}_v=(t_1,t_2,\cdots ,t_{n_v})$$\mathcal S_v=(t_1,t_2,\cdots,t_{n_v})$ ，其中 $n_v=|{\mathcal{S}}_v|$$n_v = |\mathcal S_v|$ 为序列 ${\mathcal{S}}_v$$\mathcal S_v$ 的长度。

   network representation learning 旨在根据网络结构和关联信息（如文本和 label）为每个顶点 $v\in V$$v\in V$ 学习低维 embedding $\overrightarrow{\mathbf{v}}\in {\mathbb{R}}^d$$\mathbf{\vec v}\in \mathbb R^d$，其中 $d\ll |V|$$d\ll |V|$ 为 representation 空间的维度。

2. Context-free Embedding 的定义：传统的 network representation learning 模型为每个顶点学习 context-free embedding 。这意味着顶点的 embedding 是固定的，并且不会根据顶点的上下文信息（即与之交互的另一个顶点）而改变。

3. Context-aware Embedding 的定义：与现有的、学习 context-free embedding 的 network representation learning 模型不同，CANE 根据顶点不同的上下文来学习该顶点的各种 embedding 。具体而言，对于边 $e_{u,v}$$e_{u,v}$，CANE 学习 context-aware embedding ${\overrightarrow{\mathbf{v}}}_{(u)}$$\mathbf{\vec v}_{(u)}$ 和 ${\overrightarrow{\mathbf{u}}}_{(v)}$$\mathbf{\vec u}_{(v)}$ 。

   CANE 的模型容量要比传统的 network representation learning 模型容量大得多。传统 network representation learning 模型只需要计算 $O(|V|)$$O(|V|)$ 个 embedding，而 CANE 模型需要计算 $O(|E|)$$O(|E|)$ 个 embedding。更大的模型容量可能会导致严重的过拟合。

   此外，CANE 模型中每个顶点有可变数量的 embedding，在顶点分类任务中，如何利用这些 embedding 是个难点。

1.1.2 模型

1. 整体框架：为了充分利用网络结构和关联的文本信息，我们为顶点 $v$$v$ 提供了两种类型的 embedding：基于结构（structure-based） 的 embedding ${\overrightarrow{\mathbf{v}}}^s$$\mathbf{\vec v}^s$ 、基于文本text-based 的 embedding ${\overrightarrow{\mathbf{v}}}^t$$\mathbf{\vec v}^t$ 。structure-basedembeding 可以捕获网络结构中的信息，而 text-based embedding 可以捕获关联文本信息中的文本含义（textual meaning ）。使用这些 embedding，我们可以简单地拼接它们并获得顶点 embedding 为 $\overrightarrow{\mathbf{v}}={\overrightarrow{\mathbf{v}}}^s\oplus {\overrightarrow{\mathbf{v}}}^t$$\mathbf{\vec v} = \mathbf{\vec v}^s \oplus \mathbf{\vec v}^t$，其中 $\oplus$$\oplus$ 为拼接算子。

   CANE 并不是独立建模 structure-basedembeding 和 text-based embedding ，而是联合优化它们。

   注意， text-based embedding ${\overrightarrow{\mathbf{v}}}^t$$\mathbf{\vec v}^t$ 可以是 context-free 的、也可以是 context-aware 的，这将在后面详细介绍。当 ${\overrightarrow{\mathbf{v}}}^t$$\mathbf{\vec v}^t$ 是 context-aware 时，整个顶点 embedding $\overrightarrow{\mathbf{v}}$$\mathbf{\vec v}$ 也将是 context-aware 。

   通过上述定义，CANE 旨在最大化所有 edge 上的目标函数，如下所示：

   $$\mathcal{L}=\sum _{e\in E}L(e)$$

   这里每条 edge 的目标函数 $L(e)$$L(e)$ 由两部分组成：

   $$L(e)=L_s(e)+L_t(e)$$

   其中：$L_s(e)$$L_s(e)$ 表示基于结构的目标函数（structure-based objective），$L_t(e)$$L_t(e)$ 表示基于文本的目标函数（ text-based objective ）。接下来我们分别对这两个目标函数进行详细介绍。

   CANE 仅建模一阶邻近性（即观察到的直接链接），并没有建模高阶邻近性，因为 CANE 隐含地假设了 “朋友的朋友“ 不一定是朋友。仅建模一阶邻近性会遇到数据稀疏的不利影响。

2. 基于结构的目标函数：不失一般性，我们假设网络是有向的，因为无向边可以被认为是两个方向相反、且权重相等的有向边。因此，基于结构的目标函数旨在使用 structure-based embedding 来衡量观察到一条有向边的对数似然log-likelihood，即：

   $$L_s(e)=w_{u,v}\log p({\overrightarrow{\mathbf{v}}}^s\mid {\overrightarrow{\mathbf{u}}}^s)$$

   遵从 LINE，我们将上式中的条件概率定义为：

   $$p({\overrightarrow{\mathbf{v}}}^s\mid {\overrightarrow{\mathbf{u}}}^s)=\frac{\exp ({\overrightarrow{\mathbf{u}}}^s\cdot {\overrightarrow{\mathbf{v}}}^s)}{\sum _{z\in V}{\overrightarrow{\mathbf{u}}}^s\cdot {\overrightarrow{\mathbf{z}}}^s}$$

3. 基于文本的目标函数：现实世界社交网络中的顶点通常伴随着关联的文本信息。因此，我们提出了基于文本的目标函数来利用这些文本信息，并学习 text-based embedding 。

   基于文本的目标函数 $L_t(e)$$L_t(e)$ 可以通过各种度量指标来定义。为了与 $L_s(e)$$L_s(e)$ 兼容，我们将 $L_t(e)$$L_t(e)$ 定义如下：

   $$L_t(e)=\alpha L_{t,t}(e)+\beta L_{t,s}(e)+\gamma L_{s,t}(e)$$

   其中：

   • $\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$ 为对应部分的重要性，为超参数。

     如果仅仅最小化 $L_t(e)$$L_t(e)$，则只需要两个超参数即可。但是由于需要和 $L_s(e)$$L_s(e)$ 相加，因此 $L_t(e)$$L_t(e)$ 需要三个超参数。

   • $L_{t,t}(e),L_{t,s}(e),L_{s,t}(e)$$L_{t,t}(e),L_{t,s}(e),L_{s,t}(e)$ 定义为：

     $$\begin{array}{c}{L}_{t,t}(e)=w_{u,v}\log p({\overrightarrow{\mathbf{v}}}^t\mid {\overrightarrow{\mathbf{u}}}^t)\\ L_{t,s}(e)=w_{u,v}\log p({\overrightarrow{\mathbf{v}}}^t\mid {\overrightarrow{\mathbf{u}}}^s)\\ L_{s,t}(e)=w_{u,v}\log p({\overrightarrow{\mathbf{v}}}^s\mid {\overrightarrow{\mathbf{u}}}^t)\end{array}$$

     这里构建了 structure-based embedding 、 text-based embedding 之间的桥梁，使得信息在结构和文本之间流动。

   上式中的条件概率将两种类型的顶点 embedding 映射到相同的 representation 空间中，但是考虑到它们自身的特点，这里并未强制它们相同。类似地，我们使用 softmax 函数来计算概率，如公式 $p({\overrightarrow{\mathbf{v}}}^s\mid {\overrightarrow{\mathbf{u}}}^s)$$p\left(\mathbf{\vec v}^s\mid \mathbf{\vec u}^s\right)$ 所示。

   structure-based embedding 被视为 parameter，与传统的 network embedding 模型相同。但是对于 text-based embedding，我们打算从顶点的关联文本信息中获取它们。此外， text-based embedding 可以通过 context-free 的方式、或者 context-aware 的方式获取。接下来我们将详细介绍。

4. Context-Free Text Embedding：有多种神经网络模型可以从单词序列 word sequence 中获取 text embedding，如卷积神经网络 CNN、循环神经网络RNN。在这项工作中，我们研究了用于文本建模的不同神经网络，包括 CNN、Bidirectional RNN、GRU，并采用了性能最好的 CNN。CNN 可以在单词之间捕获局部语义依赖性（ local semantic dependency ）。

   CNN 以一个顶点的单词序列作为输入，通过 lookup、卷积、池化这三层得到基于文本的 embedding 。

   • lookup：给定一个单词序列 $\mathcal{S}=(t_1,t_2,\cdots ,t_n)$$\mathcal S =(t_1,t_2,\cdots,t_{n})$，lookup layer 将每个单词 $t_i\in \mathcal{S}$$t_i\in \mathcal S$ 转换为对应的 word embedding ${\overrightarrow{\mathbf{t}}}_i\in {\mathbb{R}}^{d^{\prime }}$$\mathbf{\vec t}_i\in \mathbb R^{d^\prime}$，并且获得 embedding 序列 $\mathbf{S}=({\overrightarrow{\mathbf{t}}}_1,\cdots ,{\overrightarrow{\mathbf{t}}}_n)$$\mathbf S = \left(\mathbf{\vec t}_1,\cdots, \mathbf{\vec t}_n\right)$ ，其中 $d^{\prime }$$d^\prime$ 为 word embedding 的维度。

   • 卷积：lookup 之后，卷积层提取输入的 embedding 序列 $\mathbf{S}$$\mathbf S$ 的局部特征 local feature 。具体而言，它使用卷积矩阵 $\mathbf{C}\in {\mathbb{R}}^{d\times (l\times d^{\prime })}$$\mathbf C\in \mathbb R^{d\times (l\times d^\prime)}$ 在长度为 $l$$l$ 的滑动窗口上进行卷积操作，如下所示：

     $${\overrightarrow{\mathbf{x}}}_i=\mathbf{C}\ast {\mathbf{S}}_{i:i+l-1}+\overrightarrow{\mathbf{b}}$$

     $\mathbf{C}$$\mathbf C$ 表示 $d$$d$ 个卷积核，每个卷积核的尺寸为 $l\times d^{\prime }$$l\times d^\prime$ 。$d$$d$ 为卷积核数量，也称作输出通道数。

     其中：

     • ${\mathbf{S}}_{i:i+l-1}\in {\mathbb{R}}^{l\times d^{\prime }}$$\mathbf S_{i:i+l-1}\in \mathbb R^{l\times d^\prime}$ 为第 $i$$i$ 个滑动窗口内所有 word embedding 拼接得到的矩阵。

     • $\overrightarrow{\mathbf{b}}\in {\mathbb{R}}^d$$\mathbf{\vec b} \in \mathbb R^d$ 为 bias 向量。

     注意，我们在单词序列的边缘添加了零填充向量。

   • 最大池化：为了获得 text embedding ${\overrightarrow{\mathbf{v}}}^t$$\mathbf{\vec v}^t$，我们对 $\{{\overrightarrow{\mathbf{x}}}_1,\cdots ,{\overrightarrow{\mathbf{x}}}_n\}$$\{\mathbf{\vec x}_1,\cdots,\mathbf{\vec x}_n\}$ 进行最大池化和非线性变换，如下所示：

     $$\begin{array}{c}{r}_i=\tanh (max(x_{1,i},x_{2,i},\cdots ,x_{n,i})),i=1,\cdots ,d\\ {\overrightarrow{\mathbf{v}}}^t=(r_1,\cdots ,r_d{)}^{\mathrm{\top }}\in {\mathbb{R}}^d\end{array}$$

     其中：max 是在 embedding 维度上进行的，tanh 为逐元素的函数。

5. Context-Aware Text Embedding：如前所述，我们假设顶点在与其它顶点交互时扮演不同的角色。换句话讲，对于给定的顶点，其它不同的顶点与它有不同的焦点，这将导致 context-aware text embedding 。

   为了实现这一点，我们采用 mutual attention 来获得 context-aware text embedding。mutual attention 使 CNN 中的池化层能够感知 edge 中的顶点 pair ，从而使得来自一个顶点的文本信息可以直接影响另一个顶点的 text embedding，反之亦然。

   加权池化，权重来自于当前顶点文本内容和另一个顶点文本内容的相关性。

   如下图所示，我们说明了 context-aware text embedding 的生成过程。给定一条边 $e_{u,v}$$e_{u,v}$ 和两个对应的文本序列 ${\mathcal{S}}_u$$\mathcal S_u$ 和 ${\mathcal{S}}_v$$\mathcal S_v$ ，我们可以通过卷积层得到矩阵 $\mathbf{P}\in {\mathbb{R}}^{d\times m}$$\mathbf P\in \mathbb R^{d\times m}$ 和 $\mathbf{Q}\in {\mathbb{R}}^{d\times n}$$\mathbf Q\in \mathbb R^{d\times n}$ 。这里 $m$$m$ 表示 ${\mathcal{S}}_u$$\mathcal S_u$ 的长度，$n$$n$ 表示 ${\mathcal{S}}_v$$\mathcal S_v$ 的长度。通过引入一个注意力矩阵（ attentive matrix ）$\mathbf{A}\in {\mathbb{R}}^{d\times d}$$\mathbf A\in \mathbb R^{d\times d}$ ，我们计算相关性矩阵（ correlation matrix） $\mathbf{F}\in {\mathbb{R}}^{m\times n}$$\mathbf F\in \mathbb R^{m\times n}$ 如下：

   $$\mathbf{F}=\tanh \left({\mathbf{P}}^{\mathrm{\top }}\mathbf{A}\mathbf{Q}\right)$$

   注意，$\mathbf{F}$$\mathbf F$ 中的每个元素 $F_{i,j}$$F_{i,j}$ 表示两个隐向量（即 ${\overrightarrow{\mathbf{p}}}_i,{\overrightarrow{\mathbf{q}}}_j$$\mathbf{\vec p}_i,\mathbf{\vec q}_j$）之间的 pair-wise 相关性得分 （correlation score） 。然后，我们沿 $\mathbf{F}$$\mathbf F$ 的行和列进行池化操作从而生成重要性向量 （importance vector），分别称作行池化（ row-pooling ）和列池化（ column-pooling ）。根据我们的实验，均值池化的性能优于最大池化。因此，我们采用如下的均值池化操作：

   $$\begin{array}{c}{g}_i^p=\text{mean}(F_{i,1},F_{i,2},\cdots ,F_{i,n})\\ g_i^q=\text{mean}(F_{1,i},F_{2,i},\cdots ,F_{m,i})\end{array}$$

   其中：

   • ${\overrightarrow{\mathbf{g}}}^p={(g_1^p,\cdots ,g_m^p)}^{\mathrm{\top }}\in {\mathbb{R}}^m$$\mathbf{\vec g}^p = \left(g_1^p,\cdots,g_m^p\right)^\top \in \mathbb R^m$ 表示行池化向量，它就是 $\mathbf{P}$$\mathbf P$ 的重要性向量。

   • ${\overrightarrow{\mathbf{g}}}^q={(g_1^q,\cdots ,g_n^q)}^{\mathrm{\top }}\in {\mathbb{R}}^n$$\mathbf{\vec g}^q = \left(g_1^q,\cdots,g_n^q \right)^\top \in \mathbb R^n$ 表示列池化向量，它就是 $\mathbf{Q}$$\mathbf Q$ 的重要性向量。

   接下来，我们使用 softmax 函数将重要性向量 ${\overrightarrow{\mathbf{g}}}^p$$\mathbf{\vec g}^p$ 和 ${\overrightarrow{\mathbf{g}}}^q$$\mathbf{\vec g}^q$ 转换为注意力向量 attention vector ${\overrightarrow{\mathbf{a}}}^p$$\mathbf{\vec a}^p$ 和 ${\overrightarrow{\mathbf{a}}}^q$$\mathbf{\vec a}^q$ ，其中：

   $$\begin{array}{c}{a}_i^p=\frac{\exp \left(g_i^p\right)}{\sum _{j=1}^m\exp \left(g_j^p\right)},a_i^q=\frac{\exp \left(g_i^q\right)}{\sum _{j=1}^n\exp \left(g_j^q\right)}\\ {\overrightarrow{\mathbf{a}}}^p={(a_1^p,\cdots ,a_m^p)}^{\mathrm{\top }}\in {\mathbb{R}}^m\\ {\overrightarrow{\mathbf{a}}}^q={(a_1^q,\cdots ,a_n^q)}^{\mathrm{\top }}\in {\mathbb{R}}^n\end{array}$$

   即：对重要性向量进行 softmax 归一化。

   最后，顶点 $u$$u$ 和 $v$$v$ 的 context-aware text embedding 计算为：

   $${\overrightarrow{\mathbf{u}}}_{(v)}^t=\mathbf{P}{\overrightarrow{\mathbf{a}}}^p,{\overrightarrow{\mathbf{v}}}_{(u)}^t=\mathbf{Q}{\overrightarrow{\mathbf{a}}}^q$$

   现在，给定一条边 $e_{u,v}$$e_{u,v}$，我们可以获得 context-aware embedding，它是 structure embedding 和 context-aware text embedding 的拼接：

   $${\overrightarrow{\mathbf{u}}}_{(v)}={\overrightarrow{\mathbf{u}}}^s\oplus {\overrightarrow{\mathbf{u}}}_{(v)}^t,{\overrightarrow{\mathbf{v}}}_{(u)}={\overrightarrow{\mathbf{v}}}^s\oplus {\overrightarrow{\mathbf{v}}}_{(u)}^t$$

   其中 $\oplus$$\oplus$ 为拼接算子。

   

6. CANE 优化过程：如前所述，CANE 旨在最大化若干个条件概率。直观而言，使用 softmax 函数优化条件概率在计算上代价太大。因此，我们使用负采样，并将目标函数转换为以下形式：

   $$\log \sigma (\overrightarrow{\mathbf{u}}\cdot \overrightarrow{\mathbf{v}})+k\times {\mathbb{E}}_{z\sim P(v)}[\log \sigma (-\overrightarrow{\mathbf{u}}\cdot \overrightarrow{\mathbf{z}})]$$

   其中：$k$$k$ 为负采样比例，$\sigma$$\sigma$ 为 sigmoid 函数，$P(v)\propto d_v^{3/4}$$P(v)\propto d_v^{3/4}$ 为负顶点的采样分布，$d_v$$d_v$ 为顶点 $v$$v$ 的 out-degree 。

   之后，我们使用 Adam 来优化新的目标函数。注意，CANE 通过使用训练好的 CNN 来为新顶点生成 text embedding，从而完全能够实现 zero-shot 场景。

1.2 实验

1. 为了研究 CANE 对顶点之间关系建模的有效性，我们在几个真实世界的数据集上进行了链接预测实验。此外，我们还使用顶点分类任务来验证顶点的 context-aware embedding 是否可以反过来组成高质量的 context-free embedding 。

2. 数据集：我们选择如下所示的、真实世界的三个数据集。

   • Cora ：一个典型的论文引用网络数据集。在过滤掉没有文本信息的论文之后，网络中包含 2277 篇机器学习论文，涉及 7 个类别。

   • HepTh：另一个论文引用网络数据集。在过滤掉没有文本信息的论文之后，网络中包含 1038 篇高能物理方面的论文。

   • Zhihu：一个大型的在线问答网络，用户可以相互关注并在网站上回答问题。我们随机抽取了10000 名活跃用户，并使用他们关注主题的描述作为文本信息。

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

   

3. baseline 方法：我们采用以下方法作为 baseline：

   • 仅考虑网络结构：

     • Mixed Membership Stochastic Blockmodel: MMB: 是关系数据的一个传统图模型，它允许每个顶点在形成边的时候随机选择一个不同的topic 。

     • DeepWalk：使用截断的随机游走将图结构转化为线性结构，然后使用层次 softmax 的 SkipGram 模型处理序列从而学习顶点 embedding 。

     • LINE：分别定义损失函数来保留一阶邻近性和二阶邻近性来求解一阶邻近representation 和二阶邻近 representation，然后将二者拼接一起作为 representation 。

     • Node2Vec：通过一个有偏随机游走过程（biased random walk procedure） 来将图结构转化为线性结构，然后使用层次 softmax 的 SkipGram 模型处理序列。

   • 同时考虑结构和文本：

     • Naive Combination：用两个模型分别计算 structure embedding 和 text embedding ，然后简单地将 structure embedding 和text embedding 拼接起来。

     • TADW：采用矩阵分解的方式将顶点的文本特征融合到 network embedding 中。

     • CENE：将文本内容视为一种特殊的顶点来利用结构和文本信息，并优化异质链接的概率。

4. 评估指标：对于链接预测任务，我们采用标准的评估指标 AUC。对于顶点分类任务，我们采用 L2 正则化的逻辑回归来训练分类器，并评估分类准确率指标。

5. 训练配置：

   • 为公平起见，我们将所有方法的 embedding 维度设为 200。

   • 对于LINE 方法，负采样系数设置为 5 。一阶embedding 和 二阶 embedding 维度都是 100 维，使得拼接后的向量有 200 维。

   • 对于 node2vec 方法，我们使用网格搜索并选择最佳的超参数。

   • 对于 CANE 方法，我们通过超参数搜索选择最佳的 $\alpha ,\beta ,\gamma$$\alpha,\beta,\gamma$ 。为了加速训练过程，我们选择负采样系数 $k=1$$k = 1$ 。

     为了说明文本 embedding 以及注意力机制的效果，我们设计了三个版本：

     • CANE with text only：仅包含 context-aware text embedding。

     • CANE without attention：包含 structure embedding 以及 context-free text embedding。

     • CANE：完整的 CANE 模型。

6. 链接预测实验：我们分别移除了 Cora,HepTh,Zhihu 等网络不同比例的边，然后评估预测的 AUC 指标。注意，当我们仅保留 5% 的边来训练时，大多数顶点是孤立的，此时所有方法的效果都较差而且毫无意义。因此我们不考虑 5% 以下比例的情况。

   Cora 的结果如下，其中 $\alpha =1.0,\beta =0.3,\gamma =0.3$$\alpha = 1.0,\beta = 0.3,\gamma = 0.3$ 。

   

   HepTh 的结果如下，其中 $\alpha =0.7,\beta =0.2,\gamma =0.2$$\alpha = 0.7,\beta = 0.2,\gamma = 0.2$ 。

   

   Zhihu 的结果如下，其中 $\alpha =1.0,\beta =0.3,\gamma =0.3$$\alpha = 1.0,\beta = 0.3,\gamma = 0.3$ 。

   

   从链接预测任务的实验结果可以看到：

   • CANE 在所有训练集、所有训练比例都取得最好的效果，这表明 CANE 在链接预测任务中的有效性，验证了 CANE 具备精确建模顶点之间关系的能力。

   • 在不同的训练比例下，CENE 和 TADW 的效果不稳定。具体而言：

     • CENE 在训练比例较小时效果比 TADW 较差，因为相比 TADW ，CENE 使用了更多的参数（如卷积核和word embedding），因此 CENE 需要更多的训练数据。

     • 与 CENE 不同，TADW 在较小的训练比例时表现得更好，因为基于 DeepWalk 的方法即使在边有限的情况下也可以通过随机游走很好地探索稀疏网络结构。然而，由于它的简单性和 bag-of-words 假设的局限性，TADW 在较大的训练比例时表现不佳。

     • CANE 在各种情况下，效果都很稳定。这展示了 CANE 的灵活性和鲁棒性。

   • 通过引入注意力机制，学到的 context-aware embedding 比没有注意力的 embedding 效果更好。这验证了我们的假设：顶点和其它顶点交互时应该扮演不同的角色，从而有利于相关的链接预测任务。

   综上所述，以上所有实验结果表明：CANE 可以学习高质量的 context-aware embedding，这有利于精确估计顶点之间的关系。此外，实验结果也表明了 CANE 的有效性和鲁棒性。

   实验可以看到：引入顶点的文本信息可以更好地提升 network embedding 的质量。因此，CANE 应该和带文本信息的 baseline 方法进行比较。如果 CANE 和 DeepWalk/LINE/node2vec 等纯结构的 network embedding 方法比较，则不太公平。

7. 顶点分类实验：网络分析任务（如顶点分类和聚类）需要得到该顶点的整体 embedding，而不是顶点的很多个context-aware embedding。为了得到整体embedding，我们简单的将每个顶点的所有 context-aware embedding 取平均，如下所示：

   $$\overrightarrow{\mathbf{u}}=\frac{1}{N}\sum _{(u,v)\text{or}(v,u)\in E}{\overrightarrow{\mathbf{u}}}_{(v)}$$

   其中 $N$$N$ 为顶点 $u$$u$ 的 context-aware embedding 数量。

   使用生成的整体 embedding ，我们在 Cora 数据集上执行顶点分类任务，采用 2-fold 交叉验证并报告平均准确率。实验结果如下图所示，可以看到：

   • CANE 的性能与 SOTA 的 CENE 相当。这表明：学到的 context-aware embedding 可以通过简单的取平均操作转化为高质量的 context-free embedding，并进一步应用于其它网络分析任务。

   • 通过引入 mutual attention 机制，CANE 的性能比没有注意力的版本得到较大的提升。这与链接预测的结果是一致的。

   综上所述，实验结果表明 CANE 可以灵活地完成各种网络分析任务。

   

8. 案例研究：为了说明 mutual attention 机制从文本信息中选择有意义特征的重要性，我们可视化了两个顶点的热力度。图中，每个单词都带有各种背景色，颜色越深该单词的权重越大。每个单词的权重根据注意力权重来计算，计算方式为：

   • 首先，对于每对顶点pair，我们获取其单词序列每个卷积窗口的注意力权重 $a_i^p,a_i^q$$a_i^p,a_i^q$ 。

   • 然后，在这个窗口内我们为每个单词分配注意力权重（窗口内的多个单词对应于该窗口的权重）。

   • 最后，考虑到一个单词可能会出现在多个窗口内（单个顶点的单词序列包含很多个窗口），我们将该单词的多个权重相加，得到单词的注意力权重。

   我们提出的注意力机制使得顶点之间的关系明确且可解释。如下图所示，我们选择 Cora 数据集存在引用关系的三篇论文 A,B,C 。可以看到：尽管论文 B,C 和论文 A 存在引用关系，但是论文 B 和论文 C 关注的是论文 A 的不同部分：

   • Edge #1 在论文 A 上重点关注 reinforcement learning。

   • Edge #2 在论文 A 上重点关注 machine learning, supervised learning algorithms,complex stochastic models 。

   另外，论文A 中的所有这些关键元素都可以在论文 B 和论文 C 中找到对应的单词。这些关键元素对引用关系给出了准确的解释，这很直观。这些挖掘出的顶点之间显著的相关性，反应了 mutual attention 机制的有效性，同时也表明 CANE 精确建模关系的能力。