论文解读：复杂网络的多尺度动态嵌入技术

导语

传统的复杂网络研究大部分都是基于矩阵的分析。而随着机器学习在众多领域取得的卓越成果，将网络表示成适合机器学习算法处理的数据形式迫在眉睫，而这一类工作被称为网络嵌入。最近基于卷积的网络嵌入技术（GCN）和注意力的嵌入技术（GAT）的效果都优于传统的技术（如Node2Vec），但是这些技术都只能表征网络静态拓扑结构，无法表征网络上的动力学过程。而此文介绍的方法，便是处理这一问题的有力尝试。

1.何为网络嵌入？

复杂系统由大量可动态交互的个体组成，不管是在空间还是时间尺度上，经常表现出丰富的特性和行为。作为耦合动力学的实体（coupled dynamical entities），复杂系统的动力学轨迹可以反映底层的图拓扑结构如何约束和塑造系统的局部动力学。

有些网络并没有内在定义的动力学，比如由关系型数据生成的复杂网络，但是可以把我们感兴趣的网络功能看作是其上的某种动力学过程，比如扩散过程。因此，理解网络连通性如何影响动力学特性，对于很多涉及复杂系统研究的学科来说，都是一项重要任务。



图1：Internet主干网络便是典型的复杂网络

但是，想要全面描述系统的动力学和网络结构，相当的不现实。很多时候，你都不知道怎么去详尽的描述这些系统，或者不知道这些冗长的描述信息是否是画蛇添足。因此，很多研究都以降低系统复杂度为宗旨，只对系统进行低维的粗粒化描述。虽然感觉比较粗糙，但都能解释清楚网络上有趣的现象。

经典的降维方法要求系统具有对称性或者有均匀连接的团簇，而在实际系统中，这些条件几乎不可能满足。虽然有人用统计学理论为这些方法辩护，将实际系统的不规则性解释为理想模型的随机波动，但是这些理论又建立在了更加严格的局部假设基础上。实际上系统的很多全局特征，例如循环结构（cyclic structures）和高阶耦合动力学，并不能在经典的结构范式下解决。

最近，网络嵌入技术的发展可谓是风生水起。这种技术将网络和其上的节点映射到向量空间（通常是低维），让数据分析领域那些牛哄哄的算法也能直接用到网络分析中。迄今为止，大多的嵌入技术都只表征了网络的拓扑信息，比如由扩散得到的拓扑结构，但是实际网络的动力学远比扩散过程复杂，而且遇着包含带符号的边和有向边的网络时，要定义一个扩散过程也很难。

图2：Graph Convolution Network(GCN) 是最近比较流行的网络嵌入方法，该方法借鉴CNN中的卷积思想，嵌入效果很好

为了解决上面提到的实际系统的非对称性和复杂动力学特性，MIT 的 Michael 等人最近提出了一种复杂网络的多尺度动态嵌入技术。



图3：复杂网络的多尺度动态嵌入技术

如上图所示左半部分所示，该嵌入技术用低维信号空间中的点，来表示各节点在特定时刻t对于脉冲的响应。一段时间以后，还可以得到每一个点在信号空间的随着时间的移动轨迹。这样在每个时刻t，所有的点都映射到了相同的（信号）向量空间，在定义了相似性和距离之后，又可以用经典的分析方法来处理。但是此时的向量空间不仅是基于网络的拓扑结构，还直接基于其上的动力学过程。

下面我们逐步的分析该技术怎么实现的。

2.节点的动态嵌入

为了直观起见，将复杂网络的动力学表示成多元微分方程，网络的节点和方程的变量一一对应：

X矩阵表示当前各节点的状态，u表示对各节点的脉冲刺激，而y表示我们实际观察到的各节点的转态。

有了这个方程，我们在 t=0 时给定初值，也就是对系统给定一个输入刺激，便很容易解得在任意节点i在任何时间t时个节点的状态 y_i(t)，也就是该节点此时对于输入的响应，这样便得到了关于节点到向量空间的映射：



其中，

 

于是，在不同时间尺度上的网络动态嵌入的基本框架便搭起来了！

细心的读者肯定会问，微分方程中的 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

推荐阅读

---

集智QQ群｜292641157
商务合作｜[e-mail]
投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

加入“没有围墙的研究所”

让苹果砸得更猛烈些吧！