九、CANE

1. 一个顶点在和不同的邻居顶点交互时，通常表现出不同的形象aspect 。例如：

   • 一个学者可以和不同的合作者partner 就不同的研究方向进行合作。

     如下图所示：红色、蓝色、绿色字体分别表述左侧学者、右侧学者以及所有学者都关注的研究方向。

   • 一个自媒体作者可以和不同的朋友就不同的兴趣进行分享。

   • 一个网页可以可以因为不同的目的而链接到不同的其它网页。

   

2. 目前的大多数 GraphEmbedding 方法忽略了顶点交互过程中每个顶点的各种角色，仅为每个顶点分配一个统一的向量，这带来两个问题：

   • 它们无法处理顶点针对不同的邻居交互呈现不同aspect 的问题。

   • 它们往往强迫顶点的不同邻居之间的 embedding 也是彼此靠近的，然而事实并非总是如此。

     如上图所示：左侧学者和中间学者的距离较近，右侧学者和中间学者的距离也较近。但是，事实上左侧学者和右侧学者的距离是较远的，因为二者之间共同关注的主题很少。而传统的模型认为它们是彼此接近的，仅仅因为它们都和中间顶点相连。

   这使得顶点的 embedding 没有区分度，无法区分顶点的链接是刻画哪个 aspect 。

   为解决该问题，论文 《CANE: Context-Aware Network Embedding for Relation Modeling》 提出了 Context-Aware Network Embedding:CANE 框架来精确建模顶点之间的关系。

   CANE 假设一个顶点在和不同的邻居顶点交互时表现出不同的角色从而产生不同的 embedding。

   具体而言，CANE 考虑每个顶点包含的丰富的外部信息，如：文本、标签以及其它元数据。传统的Graph embedding 模型忽略了这些上下文信息，因此每个顶点都是静态的embedding 向量。CANE 根据和顶点交互的不同邻居为顶点动态分配一个embedding 向量，这被称作 context-aware embedding 上下文感知向量。CANE 通过attentioin 机制学习顶点的上下文感知向量，从而精确的建模顶点之间的语义关系。

3. 本文仅考虑外部信息为文本的文本信息网络，但是 CANE 可以轻松扩展到其它类型的信息网络。

9.1 模型

1. 给定信息网络 ，其中 为顶点集合、 为边的集合、 为顶点的文本信息集合。边 表示顶点 的关系，并且它关联权重 。

   每个顶点 的文本信息为一个单词序列 ，其中 ， 为词汇表中的单词。

   网络 Representation learning 学习的任务是：根据网络结构和关联的文本信息为每个顶点 学到一个低维 embedding 向量 ，其中 。

   有两种类型的 embedding 向量：

   • 上下文无关 embedding：学到的 embedding 向量是上下文无关的。即：每个顶点学到的 embedding 向量是唯一的，不会因为上下文信息（即与顶点交互的邻近顶点）的改变而改变。
   • 上下文感知embedding：学到的 embedding 向量随着上下文的不同而不同。

2. 为了充分利用网络的结构信息和文本信息，CANE 提出两种类型的 embedding：

   • 结构 embedding ：捕获网络的结构信息。
   • 文本 embedding ：捕获顶点的文本信息。

   给定顶点 ，结构 embedding 用 来表示，文本 embedding 用 来表示。顶点 的 embedding 可以通过简单的拼接这些 embedding 来实现： ，其中 表示向量拼接操作。

   文本 embedding 可以是上下文相关的，也可以是上下文无关的。当文本 embedding 是上下文相关时，顶点的整体 embedding 也是上下文相关的。

3. CANE 的目标函数为：

   

   其中 由两部分组成： 表示基于结构的目标函数， 表示基于文本的目标函数。

   • 基于结构的目标函数：假设网络是有向的（无向边可以视为两个方向相反、权重相等的有向边），基于结构的目标函数旨在通过结构embedding 来最大化有向边的对数似然：

     

     和 LINE 一样，我们定义已知顶点 的条件下存在边 的概率为：

     

   • 基于文本的目标函数：现实世界网络中的顶点通常会伴随关联的文本信息，因此我们可以利用这些文本信息来学习基于文本的顶点 embedding 。

     基于文本的目标函数 有多种形式。为了和 保持一致，我们定义 为：

     

     其中：

     • 控制了对应部分的权重

     • 条件概率 将两种类型的顶点 embedding 映射到相同的表达空间中，其计算公式也采用类似 的 softmax 。

       考虑到结构embedding 和文本 embedding 的特定，理论上不需要强制将它们映射到同一个表达空间。

4. 网络的结构 embedding 的学习和传统网络 embedding 相同，但是网络的文本 embedding 直接从顶点的关联文本中学习。

   我们可以用上下文无关的方式学习文本 embedding ，也可以用上下文相关的方式学习文本 embedding 。

9.1.1 上下文无关文本 embedding

1. 有很多神经网络模型可以从单词序列中获取文本 embedding，包括 CNN,RNN 等。论文中作者研究了多个模型，包括 CNN 、双向 RNN、GRU ，最终选择了效果最好的 CNN，因为 CNN 能够捕获单词之间的语义依赖性。

   CNN 将顶点的单词序列作为输入，通过三层神经网络获取顶点的文本 embedding 。这三层依次为 looking-up 层、卷积层、池化层。

   • looking-up 层：给定单词序列 ，looking-up 层将单词 转换成对应的词向量 ，最终得到输入对应的word embedding 序列：

     

     其中 为词向量的维度。

   • 卷积层：卷积层提取word embedding 序列 的局部特征。

     卷积层在一个长度为 的滑动窗口上使用卷积核 对 执行卷积操作：

     

     其中 表示 word embedding 序列的第 个滑动窗口内的 个词向量， 表示卷积， 为偏置向量。

     注意：这里对句子边缘添加了零填充词向量。

   • 最大池化层：为获取文本embedding ，我们采用了一个最大池化层以及一个非线性映射：

     

     其中 表示第 个向量的第 个分量。

     最终得到文本 embedding 向量为： 。

   这种方式得到的 和其它顶点无关，因此称之为上下文无关的文本 embedding 。

9.1.2 上下文相关文本embedding

1. 如前所述，我们假设顶点和不同的邻居顶点交互时扮演不同的角色。即：每个顶点都应该针对不同的目标顶点产生不同的焦点。这将产生上下文相关的文本embedding 。

   为实现该目的，论文提出了 mutual attention 来获取上下文相关的文本embedding。mutual attention 机制使得 CNN 池化层能够感知到链接对端的顶点，从而使得链接对端顶点的文本信息能够直接影响当前顶点的文本embedding 。

2. 给定一条边 以及顶点 的文本序列 和顶点 的文本序列 ，假设从顶点 卷积层得到的句子为 、从顶点 卷积层得到的句子为 ，其中 分别代表两个序列的长度。

   定义注意力矩阵 attentive matrix 为 ，则我们得到相关性矩阵 correlation matrix 为：

   

   其中 表示两个隐向量 的成对相关性得分pair-wise correlation score 。

   • 我们沿着 的行、列分别进行池化操作，从而得到重要性向量 importance vector，分别称作行池化 row pooling 、列池化 column pooling 。根据经验，均值池化的效果优于最大池化，因此有:

     

     其中：

     • 表示行池化向量，它就是 的重要性向量。
     • 表示列池化向量，它就是 的重要性向量。

   • 然后我们将重要性向量转化为注意力向量：

     

     最终顶点 和 的上下文相关文本 embedding 分别为：

     

   • 给定边 中顶点 和 的结构 embedding，则最终得到顶点 和 的上下文相关 embedding 为：

     

     其中 表示向量拼接操作。

   

9.1.3 最优化

1. CANE 的目标函数为：

   

   这里存在多个条件概率，且这些条件概率都是以 softmax 函数的形式，计算复杂度太高。CANE 采用负采样来降低计算复杂度，将目标函数转化为以下形式：

   

   其中 为负采样的样本数， 为 sigmoid 函数， 为顶点的概率分布， 为顶点的degree 。

2. CANE 采用 Adam 优化器来优化目标函数。

3. 对于新顶点，CANE 可以通过训练好的 CNN 来产生文本embedding 从而实现 zero-shot 。

9.2 实验

1. 数据集：

   • Cora ：一个典型的论文引用网络数据集。在过滤掉没有文本信息的论文之后，网络中包含 2277 篇机器学习论文，涉及 7 个类别。
   • HepTh：另一个论文引用网络数据集。在过滤掉没有文本信息的论文之后，网络中包含 1038 篇高能物理方面的论文。
   • Zhihu：一个大型的在线问答网络，用户可以相互关注并在网站上回答问题。我们随机抽取了1万 名活跃用户，并使用他们关注主题的描述作为文本信息。

   

2. 基准模型：

   • 仅考虑网络结构的基准模型：

     • Mixed Membership Stochastic Blockmodel:MMB: 是关系数据的一个传统图模型，它允许每个顶点在形成边的时候随机选择一个不同的topic 。
     • DeepWalk：使用截断的随机游走将图结构转化为线性结构，然后使用层次 softmax 的 SkipGram 模型处理序列。
     • LINE：分别定义损失函数来保留一阶邻近度和二阶邻近度来求解一阶邻近度representation 和二阶邻近度 representation，然后将二者拼接一起作为 representation 。
     • Node2Vec：通过一个有偏随机游走过程biased random walk procedure 来将图结构转化为线性结构，然后使用层次 softmax 的 SkipGram 模型处理序列。

   • 考虑结构和文本的模型：

     • Naive Combination：用两个模型分别计算结构 embedding 和 文本 embedding ，然后简单的将结构 embedding 和 文本embedding 拼接起来。
     • TADW：采用矩阵分解的方式将顶点的文本特征融合到网络 embedding 中。
     • CENE：将文本内容视为一种特殊的顶点来利用结构和文本信息，并优化异构链接的概率。

3. 评估指标：链接预测任务： AUC 指标；顶点分类任务：分类准确率。

4. 模型超参数：为公平起见，所有模型的 embedding 维度都是 200 维。

   • LINE 模型中，负采样数设置为 5 ；一阶embedding 和 二阶 embedding 维度都是 100 维，使得拼接后的向量有 200 维。

   • node2vec 模型中，我们使用网格搜索并选择最佳的超参数。

   • 在 CANE 中，我们通过超参数搜索选择最佳的 。并且为了加速训练过程，我们选择负采样数 。

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

     • CANE with text only：仅仅包含文本 embedding （包含 attention）
     • CANE without attention：包含结构 embedding 以及上下文无关的文本 embedding
     • CANE：完整的 CANE 模型

9.2.1 链接预测任务

1. 我们分别移除了 Cora,HepTh,Zhihu 等网络不同比例的边，然后评估预测的 AUC 指标。

   注意到：当仅保留 5% 的边来训练时，大多数顶点是没有链接的，此时所有方法的效果都较差。因此我们不考虑 5% 以下比例的情况。

   • Cora 的结果如下，其中 。

     

   • HepTh 的结果如下，其中 。

     

   • 知乎的结果如下，其中 。

     

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

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

   • 在不同的训练比例下，CENE 和 TADW 的效果不稳定。

     • CENE 在训练比例较小时效果比 TADW 较差，因为相比 TADW ，CENE 使用了更多的参数（如卷积核和word embedding），因此 CENE 需要更多的训练数据。
     • CANE 在各种情况下，效果都很稳定。
   • 通过引入注意力机制，学到的上下文相关embedding 比上下文无关embedding 效果更好。这验证了我们的假设：顶点和其它顶点交互时扮演了不同的角色。这有利于链接预测任务。

9.2.2 顶点分类任务

1. 网络分析任务（如顶点分类和聚类）需要得到该顶点的整体 embedding，而不是顶点的很多个上下文感知embedding。为了得到整体embedding，我们简单的将每个顶点的所有上下文感知embedding 取平均：

   

   其中 为顶点 存在链接的顶点的数量。

2. 我们在 Cora 数据集上执行顶点分类任务，采用 2-fold 交叉验证并报告平均准确率。

   结论：

   • CANE 可以取得最先进的 CENE 相当的性能。这表明：学到的上下文相关embedding 可以通过简单的取平均操作转化为高质量的上下文无关embedding，并进一步应用于其它网络分析任务。
   • 通过引入注意力机制，CANE 的性能比没有注意力的版本得到提升。

   

9.2.3可视化

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

   • 首先，对于每对顶点pair，我们获取每个卷积窗口的注意力权重：

     

   • 然后，在这个窗口内我们为每个单词分配注意力权重。

   • 最后，考虑到一个单词可能会出现在多个窗口内，我们将该单词的多个权重相加，得到单词的注意力权重。

   如下图所示，我们选择 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 精确建模关系的能力。