介绍
传统的复杂网络研究大多基于矩阵分析。随着机器学习在许多领域的显著成就，迫切需要将网络表示为适合机器学习算法处理的数据形式，这种工作称为网络嵌入。最近，基于卷积的网络嵌入技术(GCN)和注意力嵌入技术(GAT)优于传统技术(如Node2Vec)，但这些技术只能表示网络的静态拓扑，而不能表示网络上的动态过程。本文介绍的方法是处理这个问题的有力尝试。
1.什么是网络嵌入？
复杂系统由大量能够动态交互的个体组成，往往在空间和时间尺度上都表现出丰富的特征和行为。作为耦合的动态实体，复杂系统的动态轨迹可以反映底层图拓扑如何约束和塑造系统的局部动态。
有些网络没有内在定义的动力学，比如关系数据生成的复杂网络，但是我们感兴趣的网络函数可以看作是对它们的某种动态过程，比如扩散过程。因此，了解网络连通性如何影响动态特性，是许多参与复杂系统研究的学科的重要任务。
图1:互联网骨干网是典型的复杂网络。
然而，完全描述系统的动力学和网络结构是相当不现实的。很多时候，你不知道如何详细描述这些系统，或者冗长的描述信息是否多余。因此，很多研究都是为了降低系统的复杂度，只对低维粗粒度的系统进行描述。虽然感觉粗糙，但能把网上有趣的现象解释清楚。
的经典降维方法要求系统具有对称性或一致连通的簇，但在实际系统中，这些条件几乎不可能满足。虽然有人用统计理论来为这些方法辩护，并将实际系统的不规则性解释为理想模型的随机波动，但这些理论都是基于更严格的局部假设。事实上，系统的许多全局特征，如循环结构和高阶耦合动力学，在经典结构范式下是无法解决的。
近年来，网络嵌入技术发展迅猛。该技术将网络及其节点映射到向量空间(通常是低维的)，使得数据分析领域令人敬畏的算法也可以直接用于网络分析。到目前为止，大多数嵌入技术只表示网络的拓扑信息，如扩散得到的拓扑结构。然而，实际网络的动力学远比扩散过程复杂，当遇到有符号边和有向边的网络时，很难定义扩散过程。
图2:图卷积网络(GCN)是最近流行的网络嵌入方法。该方法借鉴了CNN中的卷积思想，嵌入效果非常好。
为了解决上述实际系统的不对称性和复杂动态特性，麻省理工学院的长期旅行者等人最近提出了一种复杂网络的多尺度动态嵌入技术。
图3:复杂网络的多尺度动态嵌入技术
如上图左半部分所示，嵌入技术使用低维信号空间中的点来表示每个节点在特定时间t对脉冲的响应，经过一段时间后，也可以得到信号空间中每个点随时间的运动轨迹。这样，在每个时间t，所有的点都映射到同一个(信号)向量空间，在定义了相似度和距离后，就可以用经典的分析方法进行处理。然而，此时的向量空间不仅基于网络的拓扑结构，还直接基于其动态过程。
我们来分析一下这项技术是如何一步步实现的。
2.节点的动态嵌入
为了直观起见，将复杂网络的动力学表示为多元微分方程，网络的节点与方程的变量一一对应：
x矩阵表示每个节点的当前状态，U表示对每个节点的脉冲刺激，Y表示每个节点实际观察到的跃迁状态。
其中，
从而建立了不同时间尺度下网络动态嵌入的基本框架！
细心的读者肯定会问，微分方程中的A和B应该如何确定？
A矩阵和B矩阵的设计必须由具体的系统动力学决定，并且不偏离具体的系统设计方法，这将在以后的大学排名应用中体现出来。
3.相似性和距离的定义
我们已经定义了不同时间节点的嵌入，那么如何度量这两者呢？
节点i和j在时间t的状态是否相似呢？因为我们已经把节点映射成了向量，所以有很多方法可以用来做这件事。因为简单且通用，我们直接选择标准双线性内积的相似性度量方法，得到各节点的相似性矩阵：更进一步，可以定义出各节点之间的距离矩阵：
值得注意的是，相似性矩阵和距离矩阵都是时间相关的。从另外一个角度看，节点嵌入、相似性矩阵和距离矩阵可以看做是对网络按照时间t的动态抽样，我们可以参照图4来理解这句话：
图4：网络连边的权重分布以及相似矩阵在时刻t=1、8、16时的取值
我们现在来看图4中 B 所示的网络，这是一个有向加权网络，而且权值不对称。我们考虑网络上的一个随机游走过程，相当于在其上定义个一个时间离散的动力学方程，也即一个微分方程：
M 是网络上无偏随机游走的转移矩阵。
观察图4的 C 图中，各节点的相似度矩阵随着时间不断的变化，这说明我们的嵌入方法能够用来发现动态的团簇模块，不同时间尺度表征的系统信息也不一样。换一个角度来看，T=1 时等效于只考虑一阶邻居的网络结构分析，而 t>1 时，类似于多步转移的网络结构分析。
4.如何对大学学科排名？
——降维：从距离矩阵得到低维节点嵌入
到这里我们已经构建好了一套网络动态嵌入的方法，但是我们怎么保证节点具有有效低维嵌入呢？下面我们结合一个应用实例说明。
考虑一个普遍关心的问题：怎样对不同大学的相同学科进行排名？一种合理的想法是：一所大学某系的老师应该来自于本学校或者更好的学校。按照这一朴素的想法，我们就可以建立一个各大学系所之间的有向加权网络，边的方向表示人员的流动，而权重表示人员流动的数量。
同时，我们还可以建立网络上的动力学模型：
其中，
由于网络上的性质具有短期不变形，我们可以对各动态量进行[0,1]上积分，从而消除时间依赖性，避免需要选择确定时间点的麻烦。另外，为逼近距离矩阵，我们对相似度矩阵进行谱分解：
然后定义新的节点向量‘dynamical fingerprints’ ,如下：
只用取个节点向量前面比较重要的维数，就可以比较好的逼近距离矩阵。但是效果如何呢？若只根据的第一维（也是最重要的）对学校进行排序（图5的 B 图），可以发现和权威机构给出的排序（括号内数字）相关性达到0.91，说明我们的基于动力学的低维嵌入保留了重要信息。
图5：A：截取节点嵌入向量前两维的可视化；
B:仅依据嵌入的第一维对各大学CS专业排名和权威结果的比较
另外，若取的前两维作为横纵坐标（如图5的 A 图），发现加拿大的学校在纵坐标上表现的异常突出，说明一维排名并不能很好的表征基于动力学的影响力。
5.结语
为解决实际系统的非对称性和复杂的动力学性质，论文作者提出了一套网络多尺度动态嵌入的框架。由上文可以看到，这套框架不仅可以提供不同时间尺度的嵌入，还能有效降低嵌入维数。除了学术机构的排名，作者还用该框架分析了 LIF 神经元模型的脉冲响应网络中的功能社团，也取得了相当好的效果。
图6：利用动态嵌入方法在LIF网络上进行功能社团发现
文中展示的是该框架的基本结构，读者也可通过调整动力学方程、相似性度量、距离矩阵甚至每一个点所代表的变量个数来解决不同的问题，特别是网络链路预测和节点分类等重要问题。
如果想要了解更多的细节，鼓励勤奋的读者阅读原论文，
论文地址：https://arxiv.org/abs/1804.03733
编辑：集智小仙女2.0