一、SNE [2018]

《Attributed Social Network Embedding》

1. 社交网络是一类重要的网络，涵盖各种媒体，包括 Facebook 和 Twitter 等社交网站、学术论文的引文网络、移动通信的 caller–callee 网络等等。许多 application 需要从社交网络中挖掘有用的信息。例如，内容供应商（content provider）需要将用户分组从而用于定向广告投放 （targeted advertising），推荐系统需要估计用户对 item 的偏好从而进行个性化推荐。为了将通用机器学习技术应用于网络结构化数据，学习有信息量（informative ）的node representation 是有必要的。

   最近，人们对 representation learning 的研究兴趣已经从自然语言扩展到网络数据。人们已经提出了许多 network embedding 方法，并在各种 application 中展示出有前景的性能。然而，现有的方法主要集中在通用网络上，并且仅利用结构信息。对于社交网络，论文《Attributed Social Network Embeddin》指出：除了链接结构之外，几乎总是存在关于社交参与者（social actor） 的丰富信息。例如，社交网站上的用户可能拥有年龄、性别、文本评论等画像信息。我们将所有此类辅助信息称为属性（attribute ），这些辅助信息不仅包含人口统计学数据，还包括其它信息如附属文本、可能存在的标签等等。社交参与者的这些丰富的属性信息揭示了同质效应 （homophily effect），该效应对社交网络的形成产生了巨大的影响。

   本质上，属性对社交网络的组织产生巨大的影响。许多研究证明了属性的重要性，从客观的人口统计学数据，到主观的政治取向和个人兴趣等偏好数据。为了说明这一点，我们从三个视图绘制了 Facebook 数据集的 user-user 友谊矩阵。每一行或每一列代表一个用户，一个彩色点表示对应的用户是好友关系。每个视图是用户按照“年级” （class year） 、“专业” （major）、“宿舍” （dormitory ）等特定属性重新排序的结果。例如，图 (a) 首先按照 “年级” 属性对用户进行分组，然后按照时间顺序对 “年级” 进行排序。可以看到，每个视图中都存在清晰的块状结构（block structure），其中块内的用户的连接更紧密。每个块结构实际上都指向相同属性的用户，例如，图 (a) 的右下角对应于 2009 年毕业的用户。这个现实世界的例子支持了属性同质性 （attribute homophily）的重要性。通过共同考虑属性同质性和网络结构，我们相信可以学到更有信息量的 node representation。此外，通过利用辅助的属性信息，可以很大程度上缓解链接稀疏 （link sparsity）和冷启动 （cold-start）问题。

   

   在论文《Attributed Social Network Embedding》 中，作者提出了一个叫做 SNE 的神经网络框架，用于从社交网络数据中学习 node representation。SNE 是使用实值特征向量的通用machine learner ，其中每个特征表示节点的 ID （用于学习网络结构）或一个属性。通过这种方式，我们可以轻松地集成任何类型和数量的属性。在论文的 SNE 框架下，每个特征都关联一个 embedding，节点的 final embedding 是从节点的 ID embedding （保持结构邻近性structural proximity）和属性 embedding （保持属性邻近性attribute proximity ）聚合而成。为了捕获特征之间的复杂交互，论文采用多层神经网络来利用深度学习的强大的 representation 和 generalization 能力。

   总之，论文贡献如下：

   • 论文证明了集成网络结构和属性对于学习更有信息量的社交网络 node representation 的重要性。

   • 论文提出了一个通用框架 SNE，该框架通过保持社交网络的结构邻近性和属性邻近性来执行社交网络 embedding 。

   • 论文对四个数据集进行了广泛的实验，其中包括链接预测、节点分类这两个任务。实验结果和案例研究证明了 SNE 的效果和合理性。

2. 相关工作：这里我们简要总结了关于属性同质性 （attribute homophily ）的研究，然后我们讨论与我们的工作密切相关的 network embedding 方法。

   • 社交网络中的属性同质性：社交网络属于一类特殊的网络，其中社交关系的形成不仅涉及自组织的网络过程（self-organizing network process） ，还涉及基于属性的过程 （attribute-based process） 。在 embedding 过程中考虑属性邻近性的动机源自属性同质性的巨大影响，其中属性邻近性在基于属性的过程中起着重要作用。因此，我们在这里对同质性研究进行简要概述。

     一般而言，“同质性原则” （homophily principle）（即，“物以类聚，人以群分”）是社交生活中最引人注目和最强大的经验规律之一。

     • 相似的人倾向于成为好友的假设至少可以追溯到上世纪 70 年代。在社会科学中，人们普遍预期：个体与大约同龄的其他人建立好友关系（《“Friendships and friendly relations》）。

     • 在 《Homophily in voluntary organizations: Status distance and the composition of face-to-face groups》 中，作者研究了群体的同质构成 （homogeneous composition） 和同质性涌现 （the emergence of homophily ）的相互联系。

     • 在《Homophily in online dating: when do you like someone like yourself?》 中，作者试图找出同质性在用户做出的在线约会选择中的作用。他们发现，在线约会系统的在线用户寻找像他们一样的人的频率要比系统预测的要高得多，就像在离线世界中一样。

     • 近年来，《Origins of homophily in an evolving social network》 调查了大型大学社区中同质性的起源，该论文记录了随着时间推移的交互（interaction） 、属性（attribute ）、以及附属关系 （affiliation）。

     毫不奇怪，人们已经得出结论，除了结构邻近性之外，属性相似性的偏好也为社交网络的形成过程提供了一个重要因素。因此，为了获得更多关于社交网络的、有信息量的 representation，我们应该考虑属性信息。

   • network embedding：一些早期的工作，例如局部线性嵌入（Local Linear Embedding: LLE）、IsoMap、Laplacian Eigenmap 首先将数据转换为基于节点的特征向量的亲和图 （affinity graph）（例如节点的 k 近邻），然后通过求解亲和矩阵（affinity matrix ）的 top-n 的 eigenvector 来嵌入 graph 。

     最近的工作更侧重于将现有网络嵌入到低维向量空间中，从而帮助进一步的网络分析并实现比早期工作更好的性能。

     • 在 《Deepwalk: Online learning of social representations》 中，作者在网络上部署了截断的随机游走来生成节点序列。生成的节点序列在语言模型中被视为句子，并馈送到 SkipGram 模型来学习 node mebdding 。

     • 在 《node2vec: Scalable feature learning for networks》 中，作者通过平衡广度优先采样和深度优先采样，从而改变了生成节点序列的方式，最终实现了性能的提升。

     • 《Line: Large-scale information network embedding》 没有在网络上随机游走，而是提出了显式的目标函数来保持节点的一阶邻近性和二阶邻近性。

     • 《Structural deep network embedding》 也没有在网络上随机游走，并且引入了具有多层非线性函数的深度模型来捕获高度非线性的网络结构。

     然而，所有这些方法都只利用了网络结构。在社交网络中，存在大量的属性信息。单纯基于结构的方法无法捕获这些有价值的信息，因此可能会导致信息量少的 embedding。此外，当发生链接稀疏问题时，这些方法很容易受到影响。最近的一些工作探索了集成内容从而学习更好的 representation 的可能性。

     • 例如，TADW 提出了关联文本的 DeepWalk ，从而将文本特征融合到矩阵分解框架中。但是，TADW 仅能处理文本属性。

     • 面对同样的问题，TriDNR 提出从基于结构的 DeepWalk 和label-fused 的 Doc2Vec 模型中分别学习 embedding，学到的 embedding 以 iterative 的方式线性组合在一起。在这样的方案下，两个独立模型之间的知识交互（knowledge interaction ）只经过一系列的加权和运算，并且缺乏进一步的收敛约束（convergence constrain） 。

       相比之下，我们的方法以端到端的方式同时建模结构邻近性和属性邻近性，并且没有这些限制。此外，通过早期融合结构模型和属性模型，这两部分将相互补充从而产生足够好的知识交互。

     也有工作致力于探索用于 network embedding 的半监督学习。

     • 《Deep learning via semi-supervised embedding》 将基于 embedding 的正则化器与监督学习器结合起来，从而集成了标签信息。

     • 《Revisiting semi-supervised learning with graph embeddings》 没有强迫正则化，而是使用 embedding 来预测 graph 中的 context，并利用标签信息来构建 transductive 公式和 inductive 公式。在我们的框架中，标签信息可用的时候可以通过类似的方式融合。我们将这种扩展作为未来的工作，因为我们的工作聚焦于 network embedding 的属性建模。

1.1 模型

1.1.1 基本概念

1. 定义社交网络 $G=(\mathcal{U},\mathcal{E},\mathcal{A})$$G=(\mathcal U,\mathcal E,\mathcal A)$ ，其中 $\mathcal{U}=\{u_1,\cdots ,u_n\}$$\mathcal U=\{u_1,\cdots,u_n\}$ 为节点集合，代表用户；$\mathcal{E}=\{e_{i,j}\}$$\mathcal E=\{e_{i,j}\}$ 为边集合，代表用户之间的链接；$\mathcal{A}$$\mathcal A$ 为节点属性集合，如用户画像。

   每条边 $e_{i,j}$$e_{i,j}$ 可能关联一个权重 $s_{i,j}$$s_{i,j}$ ，代表节点 $u_i,u_j$$u_i, u_j$ 之间的连接强度。本文重点关注无权图，因此这里 $s_{i,j}=1$$s_{i,j} = 1$ 。实际上我们的方法也可以通过邻域采样策略来推广到带权图。

2. 社交网络embedding 的目的是将节点映射到低维向量空间中。由于网络结构和节点属性提供了不同的信息源，因此关键是要同时捕获这两者。

   如下图所示，数字代表节点编号，相同的颜色代表相同的属性。基于网络结构embedding 的方法通常假设连接紧密的节点在 embedding 空间中彼此靠近。如， $(u_1,u_2,u_3,u_4,u_5)$$(u_1,u_2,u_3,u_4,u_5)$ 应该彼此靠近， $(u_8,u_9,u_{11},u_{12})$$(u_8,u_9,u_{11},u_{12})$ 应该彼此靠近。然而，我们认为仅仅捕获网络结构信息是远远不够的。考虑到属性同质效应 ，$(u_2,u_9,u_{11},u_{12})$$(u_2,u_9,u_{11},u_{12})$ 也应该彼此靠近，因为他们都主修 computer science 。尽管 $u_2$$u_2$ 并未直接连接到 $u_9,u_{11},u_{12}$$u_9,u_{11},u_{12}$ ，我们可以预期 $(u_9,u_{11},u_{12})$$(u_9,u_{11},u_{12})$ 喜欢看的计算机科学类的文章， $u_2$$u_2$ 可能也会感兴趣。

   要学到用户的更有信息量的 representation，必须捕获属性信息。在这项工作中，我们努力开发 embedding 方法从而同时保持社交网络的结构邻近性和属性邻近性。

   

3. 我们首先定义结构邻近性和属性邻近性：

   • 结构邻近性（ Structural Proximity ）：以网络链接关系表示的节点邻近性。对于节点 $u_i$$u_i$ 和 $u_j$$u_j$ ，如果它们之间存在链接 $e_{i,j}$$e_{i,j}$ 则表示直接邻近；如果 $u_j$$u_j$ 在 $u_i$$u_i$ 的上下文内，则表示间接邻近。直观而言，直接邻近性对应于一阶邻近性，间接邻近性对应于高阶邻近性。产生上下文的一种流行方法是通过网络中执行随机游走，这里我们采用 node2vec 的随机游走策略。

   • 属性邻近性 （Attribute Proximity）：以属性表示的节点邻近性。对于节点 $u_i$$u_i$ 和节点 $u_j$$u_j$ ，我们将用户 $u_i$$u_i$ 的属性 ${\mathcal{A}}_i$$\mathcal A_i$ 和用户 $u_j$$u_j$ 的属性 ${\mathcal{A}}_j$$\mathcal A_j$ 的交集表示属性邻近性。通过属性邻近性的强制约束，我们可以建模属性同质效应，使得具有相似属性的用户在 embedding 空间中彼此靠近。

     这里假设用户属性特征都是离散型的（如果有连续型属性则可以离散化）。

1.1.2 SNE 模型

1. 结构建模（Structure Modeling） ：根据结构邻近性的定义，网络结构建模的关键在于定义节点的 pairwise 邻近性。

   令 $f(\cdot ,\cdot )$$f(\cdot,\cdot)$ 为节点 $u_i,u_j$$u_i,u_j$ 的邻近性得分函数，我们定义给定 $u_i$$u_i$ 的条件下，节点 $u_j$$u_j$ 和 $u_i$$u_i$ 存在链接的概率为：

   $$p(u_j\mid u_i)=\frac{\exp (f(u_i,u_j))}{\sum _{j^{\prime }=1}^n\exp (f(u_i,u_{j^{\prime }}))}$$

   令节点 $u_i$$u_i$ 的邻居集合为 ${\mathcal{N}}_i$$\mathcal N_i$（包括了直接邻居、高阶邻居），我们假设链接存在概率的条件独立性，则有：

   $$p({\mathcal{N}}_i\mid u_i)=\prod _{j\in {\mathcal{N}}_i}p(u_j\mid u_i)$$

   通过最大化所有节点上的这种条件概率，我们可以实现保持网络结构邻近性的目标。具体而言，我们建模全局网络结构的目标函数为：

   $$\mathcal{L}=\prod _{i=1}^{n}p({\mathcal{N}}_i\mid u_i)=\prod _{i=1}^n\prod _{j\in {\mathcal{N}}_i}p(u_j\mid u_i)$$

   建立了学习的目标函数之后，现在我们需要设计一个 embedding 模型来估计 pairwise 邻近性函数 $f(u_i,u_j)$$f(u_i,u_j)$ 。先前的大多数工作都是采用浅层模型来建模节点邻近性，如矩阵分解、单层神经网络。这些方法将两个节点的邻近性建模为 embedding 向量的内积。但是，众所周知，简单地将 embedding 向量内积会限制模型的表达能力，并导致较大的 ranking loss 。为了捕获现实世界网络的复杂非线性，我们建议采用一种深度架构来对节点的 pairwise 邻近性建模：

   $$f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\sigma }_L({\mathbf{W}}^{(L)}(\cdots {\sigma }_1({\mathbf{W}}^{(1)}{\overrightarrow{\mathbf{u}}}_i+{\overrightarrow{\mathbf{b}}}^{(1)})\cdots )+{\overrightarrow{\mathbf{b}}}^{(L)})$$

   其中：

   • ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 为节点 $u_i$$u_i$ 的 embedding 向量。

   • ${\widetilde{\overrightarrow{\mathbf{u}}}}_i$$\tilde{\mathbf{\vec u}}_i$ 为节点 $u_i$$u_i$ 作为上下文时的 context embedding 向量。

   • $L$$L$ 为神经网络的层数， ${\mathbf{W}}^{(l)},{\overrightarrow{\mathbf{b}}}^{(l)}$$\mathbf W^{(l)},\mathbf{\vec b}^{(l)}$ 为第 $l$$l$ 层的参数， ${\sigma }_l(\cdot )$$\sigma_l(\cdot)$ 为第 $l$$l$ 层的激活函数。

   注意：在我们的方案中，每个节点 $u_i$$u_i$ 都有两个潜在的 embedding 表示形式：节点 embedding ${\overrightarrow{\mathbf{u}}}_i$$\mathbf{\vec u}_i$ 、作为上下文时的 context embedding ${\widetilde{\overrightarrow{\mathbf{u}}}}_i$$\tilde{\mathbf{\vec u}}_i$ 。最终我们可以直接拼接或相加这两个 embedding，从而作为节点 $u_i$$u_i$ 在下游任务中的 embedding 。根据经验，这种方式效果更好。

   浅层 embedding 模型到深层 embedding 模型是一种很自然的想法。

2. 属性编码（Encoding Attributes） ：很多现实世界的社交网络包含丰富的属性信息，这些属性信息可能是异质并且多样化的。为了避免人工特征工程，我们将所有属性转化为通用的 feature vector 的形式，从而有助于设计一种从属性数据中学习的通用方法。无论属性的语义如何，我们都可以将属性分为两类：

   • 离散属性：我们通过 one-hot encoding 将离散属性转换为一组 binary feature 。如：性别属性的取值集合为 {male, female}，那么对于一位女性用户，我们用 $\overrightarrow{\mathbf{v}}=(0,1)$$\mathbf{\vec v} = (0,1)$ 来表示其性别为 female 。

   • 连续属性：社交网络上自然地存在连续属性，如图像原始特征和音频原始特征。或者也可以通过离散变量人为地转换生成连续属性，如通过 TF-IDF 将文档的 bag-of-words representation 转换为实值向量。另一个例子是历史特征，如用户购买 item 历史行为特征、用户 checkin 地点的历史行为特征，它们总是被归一化为实值向量从而减少可变长度的影响。

   假设属性特征向量 $\overrightarrow{\mathbf{v}}$$\mathbf{\vec v}$ 中有 $S$$S$ 项，对于第 $s$$s$ 个特征项，我们关联一个低维的 embedding 向量 ${\overrightarrow{\mathbf{e}}}_s$$\mathbf{\vec e}_s$ ，它对应于权重矩阵 ${\mathbf{W}}^{\text{att}}$$\mathbf W^\text{att}$ 的第 $s$$s$ 列，如下图

   所示。然后我们聚合用户所有的属性特征embedding ：

   $${\overrightarrow{\mathbf{u}}}^{\prime }=\sum _{s=1}^S{v}_s{\overrightarrow{\mathbf{e}}}_s={\mathbf{W}}^{\text{att}}\overrightarrow{\mathbf{v}}$$

   这里没有进行连续特征离散化，而是将连续特征直接嵌入并乘以特征取值。此外，这里直接均值聚合，可以结合 attention 机制进行聚合。

   类似于网络结构建模，节点属性建模的目标是采用深度模型来近似属性之间的复杂的相互作用，从而对属性邻近性建模：

   $$f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j^{\prime }\cdot {\sigma }_K({\mathbf{W}}^{(K{)}^{\prime }}(\cdots {\sigma }_1({\mathbf{W}}^{(1{)}^{\prime }}{\overrightarrow{\mathbf{u}}}_i^{\prime }+{\overrightarrow{\mathbf{b}}}^{(1{)}^{\prime }})\cdots )+{\overrightarrow{\mathbf{b}}}^{(K{)}^{\prime }})$$

   其中 $K$$K$ 为神经网络层数，${\widetilde{\overrightarrow{\mathbf{u}}}}_j$$\tilde{\mathbf{\vec u}}_j$ 为节点 $u_j$$u_j$ 作为上下文时的 context embedding 向量。

   pair-wise 属性邻近性建模从直觉上需要馈入两个节点的内容，但是这里只有一个节点内容和另一个节点的 context embedding ？

   

3. SNE 模型：为了结合网络结构建模和节点属性建模，一种直观的方法是：将各自模型学到的 embedding 拼接起来，即后期融合（late fusion）方案。这种方法的主要缺点是：各个模型在彼此不知道对方的情况下单独训练，训练之后简单地组合各模型的 embedding 从而得到结果。相反，早期融合（early fusion）方案允许同时优化所有参数，因此属性建模和结构建模相互补充，使得两个部分密切交互。从本质上讲，早期融合方案在端到端深度学习方法中更为可取，因此，我们提出了如下所示的通用社交网络嵌入框架 SNE，它通过在输入层之后进行早期融合来集成网络结构建模和节点属性建模。

   • 输入层：

     • 网络结构建模的输入层为节点的 one-hot 。

     • 节点属性建模的输入层为节点的属性特征向量 $\overrightarrow{\mathbf{v}}$$\mathbf{\vec v}$ 。

   • embedding 层：

     • 网络结构建模的 embedding 层将 one-hot 映射到捕获了网络结构信息的稠密向量 $\overrightarrow{\mathbf{u}}$$\mathbf{\vec u}$ 上。

     • 节点属性建模的 embedding 层对属性特征向量进行编码，并生成聚合了属性信息的稠密向量 ${\overrightarrow{\mathbf{u}}}^{\prime }$$\mathbf{\vec u}^\prime$ 。

   • 隐层：我们选择了 $L$$L$ 层隐层，每一层隐层为 ${\overrightarrow{\mathbf{h}}}^{(1)},\cdots ,{\overrightarrow{\mathbf{h}}}^{(L)}$$\mathbf{\vec h}^{(1)},\cdots,\mathbf{\vec h}^{(L)}$ 。其中：

     $$\begin{array}{c}{\overrightarrow{\mathbf{h}}}^{(0)}=\left[\begin{array}{c}\overrightarrow{\mathbf{u}}\\ \lambda {\overrightarrow{\mathbf{u}}}^{\prime }\end{array}\right]\\ {\overrightarrow{\mathbf{h}}}^{(k)}={\sigma }_k({\mathbf{W}}^{(k)}{\overrightarrow{\mathbf{h}}}^{(k-1)}+{\overrightarrow{\mathbf{b}}}^{(k)}),k=1,2,\cdots ,L\end{array}$$

     $\lambda \in \mathbb{R}$$\lambda\in \mathbb R$ 用于调整属性信息的重要性。我们将最后一层隐层的表示 ${\overrightarrow{\mathbf{h}}}_i^{(L)}$$\mathbf{\vec h}_i^{(L)}$ 作为用户 $u_i$$u_i$ 的embedding 向量。

     注意：一种常见的网络架构设计是使用塔式结构，即每层的神经元数量从底部到顶部依次减少。我们也遵循该设计原则，如下图所示。

   • 输出层：定义邻居 $u_j$$u_j$ 作为上下文时的 context embedding 为 ${\widetilde{\overrightarrow{\mathbf{u}}}}_j$$\tilde{\mathbf{\vec u}}_j$，它对应于权重矩阵 $\tilde{\mathbf{U}}$$\tilde{\mathbf U}$ 的第 $j$$j$ 行。因此定义 $u_i$$u_i$ 和 $u_j$$u_j$ 的邻近性为：

     $$f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)}$$

     context embedding 中缺乏节点的属性信息。

     因此节点 $u_j$$u_j$ 和节点 $u_i$$u_i$ 存在链接的概率为：

     $$p(u_j\mid u_i)=\frac{\exp ({\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)})}{\sum _{j^{\prime }=1}^n\exp ({\widetilde{\overrightarrow{\mathbf{u}}}}_{j^{\prime }}\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)})}$$

     输出层将最后一层隐层 ${\overrightarrow{\mathbf{h}}}_i^{(L)}$$\mathbf{\vec h}_i^{(L)}$ 映射为一个概率向量 ${\overrightarrow{\mathbf{o}}}_i$$\mathbf{\vec o}_i$，它给出了节点 $u_i$$u_i$ 链接到其它所有节点的概率：

     $${\overrightarrow{\mathbf{o}}}_i=(p(u_1\mid u_i),\cdots ,p(u_n\mid u_i){)}^{\mathrm{\top }}$$

   

4. 优化（Optimization） ：为求解模型参数，我们需要选择一个目标函数来进行优化。我们的目标函数是：使得所有节点上的条件链接概率最大化。即：

   $$\begin{array}{c}{\mathrm{\Theta }}^{\ast }=\arg \underset{\mathrm{\Theta }}{max}\prod _{i=1}^n\prod _{j\in {\mathcal{N}}_i}p(u_j\mid u_i)=\arg \underset{\mathrm{\Theta }}{max}\sum _{i=1}^n\sum _{j\in {\mathcal{N}}_i}\log p(u_j\mid u_i)\\ =\arg \underset{\mathrm{\Theta }}{max}\sum _{i=1}^n\sum _{j\in {\mathcal{N}}_i}\log \frac{\exp ({\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)})}{\sum _{j^{\prime }=1}^n\exp ({\widetilde{\overrightarrow{\mathbf{u}}}}_{j^{\prime }}\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)})}\end{array}$$

   其中： $\mathrm{\Theta }$$\Theta$ 为网络需要学习的参数， ${\mathcal{N}}_i$$\mathcal N_i$ 为节点 $u_i$$u_i$ 的邻居集合（包括了直接邻居、高阶邻居）。

   这个目标函数有两个效果：强化 $u_i$$u_i$ 以及 $u\in {\mathcal{N}}_i$$u\in \mathcal N_i$ 之间的相似性，削弱 $u_i$$u_i$ 以及 $u\notin {\mathcal{N}}_i$$u\notin \mathcal N_i$ 之间的相似性。但是这带来两个问题：

   • 两个用户之间没有链接，并不意味着他们是不相似的。如，社交网络中很多用户之间没有链接，不是因为他们不相似，而是因为他们没有彼此认识的机会。因此，迫使 $u_i$$u_i$ 和 $u\notin {\mathcal{N}}_i$$u\notin \mathcal N_i$ 之间用户不相似是不合适的。

   • 目标函数中，为了计算单个概率 $p(u_j\mid u_i)$$p(u_j\mid u_i)$ ，我们需要遍历所有节点。这种计算效率非常低下。

   为避免这些问题，我们使用负采样，从整个社交网络中采样一小部分负样本。主要思想是在梯度计算过程中进行近似，即：

   $$\mathrm{\nabla }\log p(u_j\mid u_i)=\mathrm{\nabla }f(u_i,u_j)-\sum _{j^{\prime }\in \mathcal{M}}p(u_j^{\prime }\mid u_i)\mathrm{\nabla }f(u_i,u_{j^{\prime }})$$

   其中：$f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\overrightarrow{\mathbf{h}}}_i^{(L)}$$f(u_i,u_j) = \tilde{\mathbf {\vec u}}_j\cdot \mathbf{\vec h}_i^{(L)}$ ，$\mathcal{M}$$\mathcal M$ 为负采样的节点集合。

   注意，给定用户 $u_i$$u_i$，上式第二项实际上是 $\mathrm{\nabla }f(u_i,u_{j^{\prime }})$$\nabla f(u_i,u_{j^\prime})$ 的期望，记作 $\mathbb{E}[\mathrm{\nabla }f(u_i,u_{j^{\prime }})]$$\mathbb E\left[\nabla f(u_i,u_{j^\prime})\right]$。对用户集合采样的关键思想是：逼近这一期望从而降低计算复杂度，并且避免对用户 $u_i$$u_i$ 未链接到的其它用户节点施加过强的约束。

   为优化上述框架，我们使用了 Adam 优化算法。此外，我们还使用了 batch normalization 。在 embedding layer 和每个隐层中，我们还使用了 dropout 。最终我们使用 ${\overrightarrow{\mathbf{h}}}^{(L)}+\widetilde{\overrightarrow{\mathbf{u}}}$$\mathbf{\vec h}^{(L)} + \tilde{\mathbf{\vec u}}$ 来作为节点的final embedding 。

1.1.3 与其它模型关联

1. 这里我们讨论 SNE 框架与其它相关模型的联系。我们展示了 SNE 包含了 SOTA 的 network embedding 方法 node2vec，也包含了线性潜在因子模型 SVD++。具体而言，这两个模型可以视为浅层 SNE 的一个特例。为便于进一步讨论，我们首先给出单层 SNE 的预测模型为：

   $$\begin{array}{c}f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\sigma }_1({\mathbf{W}}^{(1)}\left[\begin{array}{c}{\overrightarrow{\mathbf{u}}}_i\\ \lambda {\overrightarrow{\mathbf{u}}}_i^{\prime }\end{array}\right]+{\overrightarrow{\mathbf{b}}}^{(1)})\end{array}$$

   • 当选择：$\lambda =0$$\lambda = 0$ 、${\sigma }_1$$\sigma_1$ 为恒等映射、${\mathbf{W}}^{(1)}$$\mathbf W^{(1)}$ 为单位矩阵、${\overrightarrow{\mathbf{b}}}^{\mathbf{(}\mathbf{1}\mathbf{)}}=\overrightarrow{\mathbf{0}}$$\mathbf{\vec b^{(1)}} = \mathbf{\vec 0}$ 时，上式退化为：

     $$f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\overrightarrow{\mathbf{u}}}_i$$

     此时 SNE 退化为 node2vec 。

   • 当选择：$\lambda =1$$\lambda =1$ 、${\sigma }_1$$\sigma_1$ 为恒等映射、${\overrightarrow{\mathbf{b}}}^{\mathbf{(}\mathbf{1}\mathbf{)}}=\overrightarrow{\mathbf{0}}$$\mathbf{\vec b^{(1)}} = \mathbf{\vec 0}$ 、 ${\mathbf{W}}^{(1)}=[\mathbf{I},\mathbf{I}]$$\mathbf W^{(1)} = [\mathbf I, \mathbf I]$ 为两个单位矩阵拼接而成时，上式退化为：

     $$\begin{array}{c}f(u_i,u_j)={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot {\mathbf{W}}^{(1)}\left[\begin{array}{c}{\overrightarrow{\mathbf{u}}}_i\\ {\overrightarrow{\mathbf{u}}}_i^{\prime }\end{array}\right]={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot ({\overrightarrow{\mathbf{u}}}_i+{\overrightarrow{\mathbf{u}}}_i^{\prime })={\widetilde{\overrightarrow{\mathbf{u}}}}_j\cdot ({\overrightarrow{\mathbf{u}}}_i+\sum _{s=1}^S{v}_s{\overrightarrow{\mathbf{e}}}_s)\end{array}$$

     此时 SNE 退化为 SVD++ 。

   通过 SNE 与一系列浅层模型的联系，我们可以看到我们设计 SNE 背后的合理性。具体而言，SNE 加深了浅层模型，从而捕获网络结构和属性之间的底层交互。在建模可能具有复杂的、非线性固有结构的真实世界数据时，我们的 SNE 更有表达能力，并且可以更好地拟合真实世界数据。

1.2 实验

1. 这里我们对四个可公开访问的社交网络数据集进行实验，旨在回答以下研究问题。

   • 与 SOTA 的 network embedding 相比，SNE 能否学到更好的 node representation？

   • 导致 SNE 学到更好 representation 的关键原因是什么？

   • 更深的隐层是否有助于学到更好的社交网络 embedding ？

2. 数据集：

   • 社交网络：我们使用 Facebook 的两个网络，分别包含来自两所美国大学的学生： University of Oklahoma（OKLAHOMA）、University of North Carolina at Chapel Hill（UNC） 。除了用户 ID 之外，还有七个用户属性：状态、性别、专业、第二专业、宿舍、高中、入学年份。注意，并非所有学生都有这七个属性，如在 UNC 数据集中的 18163 个学生中只有 4018 个学生包含所有属性。

   • 引文网络：我们使用 DBLP 和 CITESEER 数据集，每个节点代表一篇论文。属性为去除停用词以及词干化之后每篇论文的标题和内容。DBLP 数据集由计算机科学四个研究方向的会议论文组成。CITESEER 数据集由来自十个不同研究领域的科学出版物组成。这些研究方向或研究领域在节点分类任务中被视为标签。

   

3. 评估方式：我们采用了链接预测和节点分类任务。链接预测任务评估 node representation 在重建网络结构中的能力，节点分类评估 node representation 是否包含足够的信息用于下游应用。

   • 链接预测任务：我们随机将 10% 的链接作验证集来调整超参数，随机将 10% 的链接作为测试集，剩下 80% 的链接作为训练集来训练 SNE 。由于测试集/验证集仅包含正样本，因此我们随机选择数量相等、不存在的边作为负样本。我们使用 AUROC 作为评估指标（ROC 曲线的面积），该指标越大越好。

   • 节点分类任务：我们首先在训练集上训练模型（包含所有节点、所有边、所有属性，但是没有节点 label ），从而获得node embedding 。其中模型的超参数通过链接预测任务来选取。然后我们将 node embedding 输入到 LIBLINEAR 分类器进行节点分类。我们随机选择 $\rho \in \{10\mathrm{\%},30\mathrm{\%},50\mathrm{\%}\}$$\rho\in \{10\%,30\%,50\%\}$ 的标记节点作为训练集，然后剩余的标记节点作为测试集。

     根据链接预测任务获取节点分类任务的超参数，这种做法可能不是最佳的，应该根据节点分类任务来得到模型超参数。但是这里是两阶段的，因此如何根据第二阶段的标签信息来得到第一阶段的模型超参数，这是一个问题。

     我们重复该过程十次并报告平均的 Macro-F1 和 Micro-F1 得分。注意：由于只有 DBLP 和 CITESEER 数据集包含节点的类别标签，因此仅针对这两个数据集执行节点分类任务。

4. baseline 方法：这里我们将 SNE 和若干个 SOTA 的network embedding 方法进行比较。

   • node2vec：基于有偏的随机游走产生节点序列，然后对节点序列应用 SkipGram 模型来学习 node embedding 。有两个关键的超参数 $p$$p$ 和 $q$$q$ 控制随机游走，我们以原始论文相同的方式调优它们。注意，当 $p$$p$ 和 $q$$q$ 设置为 1.0 时，node2vec 降级为 DeepWalk 。

   • LINE：分别通过保持网络的一阶邻近性和二阶邻近性来为每个节点学习一阶邻近性 embedding 和 二阶邻近性 embedding 。节点的 final embedding 为二者的拼接。

   • TriDNR：通过耦合多个神经网络来联合建模网络结构、node-content 相关性、label-content 相关性，从而学习 node embedding 。我们搜索文本权重超参数 $tw$$tw$ 的范围为 $[0.0,0.2,\cdots ,1.0]$$[0.0,0.2,\cdots,1.0]$ 。

   所有的 baseline 都采用原始作者发布的实现。注意，node2vec/LINE 都是仅考虑结构信息，为了和利用属性信息的 SNE 进行公平的比较，我们将它们学到的 node embedding 和属性向量拼接起来，从而扩展为包括属性的形式。我们称这类变体为 node2vec+attr 和 LINE+attr 。此外，我们了解到最近的 network embedding 工作 《Label informed attributed network embedding》 也考虑了属性信息，但是由于他们的代码不可用，因此我们没有进一步比较它。

5. SNE参数配置：

   • 和node2vec/LINE方法一致，我们选择 embedding 维度 $d=128$$d=128$ 。用于控制随机游走的超参数 p/q 和 node2vec 相同。

   • 我们的实现基于 tensorflow ，选择 mini-batch 的 Adam 优化器，搜索的batch size 范围从 [8,16,32,64,128,256] ，搜索的学习率从 [0.1,0.01,0.001,0.0001] 。

   • 我们搜索超参数 $\lambda$$\lambda$ 的搜索空间为 $[0.0,0.2,\cdots ,1.0]$$[0.0,0.2,\cdots,1.0]$ ，当 $\lambda =0$$\lambda=0$ 时SNE 退化为仅考虑网络结构。

   • 我们使用 softsign 函数作为隐层激活函数。我们尝试了多种激活函数，最终发现 softsign的效果最好。

   • 我们使用均值 0.0、标准差 0.01 的高斯分布来随机初始化模型参数。

   • 如无特殊说明，我们选择两个隐层，即 $L=2$$L=2$ 。

   下表给出了通过验证集择优的每种方法的最佳超参数。

   

6. 不同方法在四个数据集上链接预测任务的效果如下图所示。为探索不同网络稀疏性条件下各方法的鲁棒性，我们改变了训练链接的比例并研究了性能的变化。

   结论：

   • SNE 在所有方法中效果最佳。值得注意的是：和单纯的基于网络结构的 node2vec/LINE 相比，SNE 在使用一半链接的条件下，性能更好。这证明了节点属性在链接预测方面的有效性，以及 SNE 通过节点属性学到更好的 node embedding 的合理性。

     此外，我们观察到 node2vec/LINE 在 DBLP 和 CITESEER 上的性能随着训练比例越低，性能下降的更为明显。原因是 DBLP/CITESEER 数据集本身的链接就很少，因此当训练链接的比例降低时，链接的稀疏问题变得更加严重。相反，当我们使用更少的链接进行训练时，我们的 SNE 表现出更高的稳定性。这证明了对属性建模是有效的。

   • 聚焦于带属性的方法，我们发现集成属性的方式对于性能起着关键作用。

     • 带属性的 node2vec+attr/LINE+attr 相比 node2vec/LINE 略有改进，但是改进的幅度不大。这表明简单地将节点属性和 embedding 向量进行拼接的方式，无法充分利用属性中丰富的信号。这说明了将节点属性融合到网络 embedding 过程中的必要性。

     • SNE 始终优于 TriDNR。尽管 TriDNR 也是联合训练节点属性，但是我们的方法是在模型早期（输入层之后）就无缝地融合了属性信息，使得随后的非线性隐层可以捕获复杂的 ”网络结构-节点属性“ 交互信息，并学习更有效的 node embedding 。

   • 在基于结构的 embedding 方法中，我们观察到 node2vec 在四个数据集中都优于 LINE。一个合理的原因是：通过在社交网络上执行随机游走，node2vec 可以捕获更高阶的邻近信息。相比之下，LINE 仅对一阶邻近性和二阶邻近性建模，无法为链接预测捕获足够的信息。为验证这一点，我们进一步探索了一个额外的 baseline：在随机游走时，选择和当前节点共享最多邻居的节点，从而直接利用二阶邻近性（即选择二阶邻近性最大的节点来游走）。不出所料，该baseline 在所有数据集上的表现都很差（低于每个子图的底线）。这再次表明需要建模网络的高阶邻近性。

     由于 SNE 使用和 node2vec 相同的随机游走过程，因此它可以从高阶邻近性中学习，并通过属性信息得到进一步补充。

   

7. 不同方法在两个数据集上的节点分类任务效果如下表所示。性能趋势和链接预测任务中的趋势一致。

   • 在所有情况下，SNE 方法均超越了所有 baseline 。

   • 仅使用网络结构的 node2vec 和 LINE 表现最差，这进一步证明了社交网络上建模节点属性的有效性，并且正确建模属性信息可以导致更好的 representation learning 并有利于下游 application。

   

8. 超参数 $\lambda$$\lambda$ 调节了顶点属性的重要性。为进一步探索 $\lambda$$\lambda$ 的影响，我们考察了 $\lambda \in \{0,0.01,0.1,1,10,100\}$$\lambda\in \{0,0.01,0.1,1,10,100\}$ 时，SNE 模型的效果。我们以相同的方式来评估链接预测任务、节点分类任务，其中链接预测任务采用 80% 的链接作为训练集，节点分类任务采用 50% 的标记节点作为训练集。

   注意：当 $\lambda =0$$\lambda = 0$ 时意味着仅考虑网络结构而不考虑节点属性信息，当 $\lambda$$\lambda$ 较大时会近似于单纯的属性建模而不考虑网络结构信息。

   • 最佳结果通常在 $\lambda \in [0,1]$$\lambda\in [0,1]$ 之间取得。当 $\lambda$$\lambda$ 很大时，节点属性的重要性严重超过网络结构信息，此时性能甚至要比单纯的网络结构建模更差。因此，我们将 $\lambda$$\lambda$ 的探索集中于 $[0,1]$$[0,1]$ ，探索的步长为 0.2 。

   • 通常属性信息在 SNE 中起着重要作用，这一点可以通过 $\lambda$$\lambda$ 增加时 SNE 性能得到提升得以证明。当 $\lambda$$\lambda$ 从 0.0增加到 0.2时，我们观察到 CITESEER 的性能显著提高。由于该数据集的链接较少，因此性能的提升表明属性有助于缓解链接稀疏问题。

   • 当 $\lambda =0$$\lambda =0$ 时（仅考虑网络结构信息）SNE 的效果优于 node2vec。由于我们使用和 node2vec 相同的游走过程以及超参数 $p,q$$p,q$ ，因此我们认为性能的提升来自于隐层引入的非线性。

   

9. 为了解 SNE 为什么要比其它方法效果好，这里我们对 DBLP 数据集进行研究。我们首先用每种方法学习每个节点的 embedding，然后给定 query paper 我们利用 node embedding 检索最相似的三篇论文。其中，相似性是通过 embedding 的余弦相似度来衡量。

   为了和基于结构的方法进行公平比较，我们选择了 KDD 2006 的一篇热门论文 Group formation in large social networks: membership, growth, and evolution ，该论文引用量达到 1510 。根据这篇论文的内容，我们预期相关结果应该是关于社交网络中群体或社区的结构演变。不同embedding 方法检索到的最相关论文如下表。

   结论：

   • SNE 返回了非常相关的结果：三篇论文都是关于动态社交网络分析和社区结构的。

   • 仅利用结构信息，node2vec 返回的结果似乎与 query 不太相似。node2vec 似乎倾向于找到相关性较低、但是引用率较高的论文。这是因为随机游走过程可能容易偏向于具有更多链接的热门节点。尽管 SNE 也依赖于随机游走，但是 SNE 可以通过利用属性信息在一定程度上纠正这种偏差。

   • LINE 也返回了和 query 不太相似的结果。这可能是由于仅建模一阶邻近性和二阶邻近性，忽略了丰富的属性信息。

   通过以上定性分析我们得出结论：使用网络结构和节点属性都有利于检索相似节点。和单纯的基于结构的 embedding 方法相比，SNE 返回的结果与 query 更为相关。值得注意的是，对于本次研究，我们特意选择了一个热门的节点来缓解稀疏性问题，这实际上有利于基于结构的方法。即便如此，基于结构的方法也无法识别相关的结果。这揭示了仅依赖网络结构进行社交网络 embedding 的局限性，也证明了对节点属性进行建模的重要性。

   

10. 最后我们探索隐层对于 SNE 的影响。众所周知，增加神经网络的深度可以提高模型的泛化能力，但是由于优化困难这也可能降低模型性能。因此我们迫切想知道：使用更深层的网络是否可以提升 SNE 的性能。我们在 DBLP 上验证了SNE 模型不同数量的隐层对应的链接预测、节点分类任务的性能。在其它数据集上的结论也是类似的，因此我们仅以 DBLP 为例。由于最后一层隐层的大小决定了 SNE 模型的表达能力，因此我们将所有模型的最后一层隐层都设为 128 维从而公平地比较。对每个比较的模型，我们都重新调优超参数从而充分发挥模型的能力。

    结论：

    • 可以看到一个趋势：隐层越多模型性能越好。这表明在 SNE 中使用更深的网络效果更好。但是，其代价是更多的训练时间。在普通的商用服务器上（2.4GHz 的 Intel Xeon CPU），单层SNE 耗时 25.6秒/epoch、三层 SNE 耗时 81.9秒/epoch 。

    • 我们停止探索更深层的模型，因为当前的 SNE 使用全连接层，而深层的全连接层很难优化。并且很容易随着层的加深出现过拟合 over-fitting 和退化 degrading 。表中效果提升的衰减也暗示了这一点。

      为了解决该问题，我们建议采用现代的神经网络设计方法，如残差单元 residual unit 或highway network 。我们将该工作留给未来的工作。

    • 值得注意的是：当没有隐层时SNE 的性能会很差，与 TriDNR 处于同一水平。当增加了一层隐层时，模型效果大幅提升。这证明了以非线性方式学习 “网络结构 -- 节点属性” 交互的有效性。为证明这一点，我们进一步尝试在隐层使用恒等函数 identity 替代 softsign 激活函数，最终效果要比非线性 softsign 激活函数差得多。