【NSR特别专题】朱军：关于图的表达学习「全文翻译」

网络随处可见。常见的例子包括社交网、国际互联网、交通运输网，电力网以及生物基因网。网络可以表示成一个图，其顶点表示实体，边表示实体之间的联系或关系。随着网络的广泛普及、同时涉及的领域越来越多，从网络中开发统计模型来完成预测或其它有意义的任务已经并将继续收获巨大利益。

早期的工作聚焦于通过使用与图的某种拓扑结构相关的特征，例如公共邻点（common neighbors）、Jaccard系数，Adamic／Adar与Katz（【1】中提供了例子）等，设计出优秀的节点之间距离（或相似性）的度量方式。受到深度学习巨大成功的启发，从网络中学到一种好的表达的方式吸引了越来越多的注意，尽管这不是学习网络中潜在特征的第一次尝试（例如使用贝叶斯非参数技术（Bayesian nonparametric techniques）的尝试【2】）。

图1: 图的表达学习。

有人最近提出一种叫做Structure2Vec的方法【3】，它将实体（即节点）嵌入欧式空间中，这种方法融合了概率图模型和深度学习的想法。图1展示了其基本思想，其中每个节点X_i都与一个潜在变量H_i相关联。一般的，潜在变量H_i是随机的，整个H集合服从联合概率分布 p(H|X) 。还有一个问题是如何寻找单个变量或一组变量的边缘分布，解决类似这样的问题，我们需要在图上使用消息传递算法（message-passing algorithms）（例如mean-field以及信念传播），这种方法可以影响紧凑依赖结构（compact dependence structure）。Structure2Vec的思想来自于消息传递算法，不同于进行概率推导，它针对每个节点学习到一个特征向量 μ_i ∈ R^d，而后在局部更新规则下进行消息传递，这种算法是迭代进行的，开始时赋予 μ 初值。在进行第t次迭代时，它使用来自相邻节点的局部信息更新每个节点i的特征向量：

μ_i^(t) ← f(W, X_i, {μ_j^(t-1)}_j \in N_i) (1)

其中f是一个由深度神经网络定义的匹配函数，W是其参数。一个简单的单层神经网络可以定义为：

μ_i^(t) ← σ(W_1, X_i+W_2 Σ_j μ_j^(t-1)) (2)

其中σ是sigmoid函数。

有了特征向量μ，我们就可以定义一个用于预测任务的模型。例如，如果我们想要对每个节点进行分类，每个向量都可以作为分类器的输入。如果目标是关联预测，我们可以用一对向量μ_i和μ_j来定义一个表达关联E_{ij}的概率模型。如果预测是关于整个网络的，我们可以将所有的向量合为一个，送入分类器，而后，我们可以优化目标来寻找更优的特征向量，这与同时推测未知向量和更新参数的EM算法想法相似。当临时信息很重要时，这一框架可以推广到动态网络来处理临时信息【4】。

参考文献：

1. Liben-Nowell D and Kleinberg J. In: ACM Confer- ence of Information and Knowledge Management, New Orleans, USA, 2003, 556–9.

2. Zhu J. In: International Conference on Machine Learning, Edinburgh, Scotland, 2012, 1179–86.

3. Dai H, Dai B and Song L. In: International Conference on Machine Learning, New York City, USA, 2016, 2702–11.

4. Trivedi R, Dai H and Wang Y et al. In: International Conference on Machine Learning, Sydney, Australia, 2017, 3462–71.

• 《国家科学评论》（National Science Review, NSR）是我国第一份英文版自然科学综述性学术期刊，定位于全方位、多角度反映中外科学研究的重要成就，深度解读重大科技事件、重要科技政策，旨在展示世界（尤其是我国）前沿研究和热点研究的最新进展和代表性成果，引领学科发展，促进学术交流。NSR的报道范围涵盖数理科学、化学科学、生命科学、地球科学、材料科学、信息科学等六大领域。基于科睿唯安发布的2016年度的期刊引证报告（Journal Citation Reports，JCR），NSR的最新影响因子达到8.843，稳居全球多学科综合类期刊的第五名（8%，Q1）。NSR发表的所有论文全文可以在线免费阅读和下载。
• 本文经《National Science Review》(NSR,《国家科学评论》英文版）授权翻译，“机器学习”专题的更多翻译文章将陆续刊出。