复杂网络动力学机器学习自动建模

导语对复杂网络动力学的学习是网络科学的重要命题，至今尚未完全解决，各种新方法层出不穷。
本文总结了康奈尔大学博士后臧承熙在集智-凯风研读营上的分享，介绍其一作论文《复杂网络上的神经微分方程》。该文被 KDD2020 接收。这项工作将图神经网络与微分方程结合，提出神经微分方程（NDCN）模型，将离散时间预测变为连续时间预测，在时间预测和分类任务中都有良好表现，并且大量节省参数。这为复杂网络的动力学学习、自动建模提供了新的思路。

背 景

复杂网络无处不在。受益于网络科学的发展，我们对网络的认识也在逐步深入。网络科学带给我们一种新的看待世界的视角：很多系统都可以被解释为网络结构上的相互作用。从人类的大脑网络，到社会的交通流网络，还有自然界的生物网等等。那么这些个体在网络上是如何相互作用的？它们的相互影响是否遵循着某种规则？答案是确定的，大多数网络上的个体都遵循着一定的相互作用法则，我们称之为网络上的动力学，学习网络上的动力学一直以来都是科学界十分关注的问题之一。

问 题

本文要介绍的论文《Neural Dynamics on Complex Networks》，由康奈尔大学臧承熙博士完成。论文的关注点便是网络上的动力学学习问题。这篇文章对动力学的学习方式也十分有趣：研究者借鉴了微分方程在系统动力学建模中的优势，引入微分方程，以数据驱动的方式，对网络上的动力学进行建模。

论文题目：

Neural Dynamics on Complex Networks

论文地址：

https://www.kdd.org/kdd2020/accepted-papers/view/neural-dynamics-on-complex-networks

具体来说，我们可以这样定义这篇文章想要解决的问题：在一个网络上，节点之间以遵循着某种动力学法则的方式相互影响，这使得节点上的信息会随着时间产生连续变化。我们可以对动力学进行这样的描述：

其中X(t)表示t时刻的节点信息，G表示网络，θ则表示管理动力学的参数。

而本文要做的事情，则是在已知某些观测时刻的网络上的节点状态的情况下，去建模网络上的动力学方程，为了证明建模的精确性，文章将会对未来任意时刻的节点状态做出预测。这里尤其需要注意的一点是，对已有的数据而言，观测时间并不是等间隔的。而对预测任务而言，也并不是预测t+1时刻或t+2时刻，而是预测“任意时刻”，比如t+1.5时刻的系统状态。例如，在一个热扩散过程中，热量沿着网络扩散到不同的节点，我们可以观测到某些时刻节点的热量，但这些观测时刻并不等间隔。现在让我们去预测未来某一时刻节点的热度值。

为什么网络上的动力学学习如此有意义，但直到今天人们还未完全的解决这一问题呢？从某种程度上来说，这要归因于问题的难度。这个问题“难”，难在两方面：首先，在现实生活中，网络的结构可以非常复杂，我们知道“小世界”，“无标度”网络模型普遍存在，不同的网络模型是节点互动，相互传递信息的舞台，不同的网络模型将会在底层机制上影响节点之间的相互作用。其次，我们常见的动力学也都是非线性的，非线性动力学所呈现的复杂程度也远超线性动力学，我们用一组动图来展示：

不同网络结构与动力学下的节点状态变化情况

如果我们可以完成模型的学习，自然地，我们会意识到曾经复杂网络建模中的两个问题也可以作为子问题被解决。

其一遍是结构化的序列预测问题，在这一问题中，我们拥有对系统在一段时间内节点状态的等间隔观测，而我们的任务则是通过机器学习，去预测未来的k时刻的系统状态，我们要求这里的k必然是一个整数，例如在一个交通网络上，我们有每个小时，每个路口的车流量状态，我们的任务是预测下一小时哪些路口会堵车。

另一个有趣的子问题则是半监督分类问题，这也是催化图网络研究兴起的一类经典问题。在半监督分类问题中，我们已知网络结构和节点特征，我们也知道一部分节点的标签，但我们并不知道全部节点的标签。在这种情况下，我们如何去预测未知节点的标签？这一问题的应用场景也很广泛，例如在数字电商的背景下，我们需要了解用户的画像：已知某些人喜欢购买运动产品，那么他们哪些朋友也有类似的喜好？针对半监督分类问题，科学家们研究了许多算法，例如经典的图卷积网络（GCN）便可用于处理这类问题，而我们将在后面的实验中看到，本文提出的算法可以通过对动力学进行精细控制，来达到这个任务下的最优效果。

相关工作

人类对复杂系统的探索从未停止，在熟练使用复杂网络这一套工具之前，我们就在探寻支配着我们这个世界的机制，通过对行星数据的分析发现万有引力定律便是一个极好的例子。而在探索系统动力学规则的道路上，微分方程的引入大大增强了我们对连续时间系统的表示能力，优美的洛伦茨蝴蝶作为第一个混沌模型，为我们认识混沌打开了一扇新的大门。近年来，网络和机器学习也被结合使用，来理解复杂系统。在时间间隔确定的数据驱动问题上，人们做了很多尝试，结合图网络和循环神经网络优势的GraphRNN便是一个很好的例子。然而，我们对世界的观察并不总是确定时间间隔的，实际上，确定时间间隔是特例，任意时间间隔才是更加普遍的情况。而本文将在上述的进展之上，提出一个统一的模型来解决网络上的连续时间动力学预测问题。同时也会在确定时间间隔的预测问题和半监督分类问题上取得优秀的效果。

基本思路

文章的基本思路并不复杂：我们常用微分方程来刻画动力系统。近几年以来，我们也常用图神经网络来描述网络结构上的系统动力学，因此，本篇文章将结合微分方程和图神经网络各自的优势，提出名为NDCN（Neural Dyanmics on Complex Networks）的模型。

具体而言，将微分方程与图神经网络结合最大的特点之一，便是将离散时间预测变为了连续时间预测。也就是说，在原神经网络的框架下，我们只能根据t时刻的状态去预测t+1时刻的节点状态。而在NDCN的框架下，我们可以根据初始时刻的状态，去预测未来任一时刻的节点状态，如下：

在上式中，X(0)表示初始时刻的节点状态，X(t)则表示t时刻的节点状态，在NDCN的框架下，从0时刻到t时刻无需经过多步迭代，而是需要对动力学进行从0到t的积分，如上式所示，而积分的内容，也就是动力学部分则会被图神经网络学习。

此外，本文的另一创新之处在于，文章没有直接显式的学习动力学，而是将信息投影到了隐藏空间进行学习，这样可以进一步增强模型的表达性。

算法框架

我们可以通过下图来展示本文所提出的算法框架：

图：NDCN的运转框架图示

上图描述了NDCN的算法框架运转流程，我们可以看到，算法的输入是t时刻的节点状态X(t)，而输出则是经过δ时间后的节点状态，算法首先会将输入状态映射到隐藏空间，然后在隐藏空间建模节点之间的影响和信息扩散的动力学，这一部分便是通过图神经网络来完成的，通过对t到t+δ这一段时间内的动力学进行积分，我们便能够得到输出状态。

实 验

可以注意到，本文所提出的模型，实际上是多种技术的组合：若不引入将原始特征空间映射到隐藏空间的encoding-decoding层的话，本模型将会退化为ODG-GNN模型，若不引入图结构的话，本模型将会退化成神经微分方程模型，而若不引入控制参数，本模型又会退化为物理中的确定性模型。因此，为了验证这种组合是否真正合理有效，本文将首先去“拆除”模型的一些组成模块，去观测它们是否影响了最终结果的准确性。

上表展示了去掉不同模块后，准确率的变化情况。表格的三行分别表示了三种典型的网络上的动力学，它们分别被常用于描述物理中的热扩散过程，生态系统中的物种影响和生物学中的基因调控过程。而表格的六列则表示了不同的底层网络结构。可以看到，无论去掉哪一个模块，无论在哪种网络结构或动力学方程的情况下，NDCN都将会呈现出准确率的下降，因此，NDCN的每个模块都有其意义，都对准确地建模网络上的动力学有所帮助。

实验：结构化的序列预测问题

结构化的序列预测问题是指我们在拥有对节点数据以相同时间间隔采样的数据下，去预测未来时刻的节点状态。而在这个实验中，本文选取的是非常适合这一类任务的图神经网络结合卷积神经网络的模型。我们知道，卷积神经网络有多种，其中RNN是最为基础的一种，GRU要稍稍复杂一些，LSTM的参数则会更多。在这里本文分别对比了以上三种循环神经网络和GNN结合的模型。实验结果如下表所示：

通过对上表的观察，我们会发现NDCN模型无论对标哪一种图网络结合循环神经网络的模型，都能够获得最有效果。此外，尤其值得一提的一点是，在这里的对比模型应用的参数量都是很多的（10⁵数量级），而NDCN所用到的参数数量相比而言却少了两个数量级（10³数量级）。这说明NDCN在使用较少的参数的情况下，达到了最优的效果。

最后，让我们来分享一个半监督分类的有趣实验。这个实验与其他实验的不同之处在于，在半监督分类的任务中，并不存在一个“显式”的动力学过程。在这个任务中，我们可以获得的信息有图结构，节点上的特征信息和一部分节点的标签信息，我们的目的是给未标签的节点打上标签。为了解决这种没有“显式”动力学的问题，本文将标签信息和节点信息共同作为新的节点信息输入给NDCN模型，让模型通过学习信息的扩散来将标签扩散到整个网络上。在这个实验中，对比模型部分本文选取了GCN、GAT等经典模型，它们都十分擅长通过网络结构聚合节点信息。

可以看到，在相同的训练次数下，NDCN模型再一次在准确率上取得了最优结果，我们可以这样解释这个结果，NDCN本身在连续的模型上运作，这允许我们以一种更精细的方式来建模动力学过程。在这个任务中，我们不需要特别深的网络结构来完成节点间的信息扩散，事实上，我们在T=1.2时达到了最优的效果（如果用传统的图网络语言来说，是在1.2层得到了最优的分类结果），而普通的图网络方法中，不存在“小数层”这一概念，由此，借用NDCN的方法，我们得以对动力学进行如此精细的控制。

总 结

本文提出了NDCN的框架，这个框架作为一个连续时间的图网络框架，结合了图网络和神经微分方程的优势，可以在连续时间预测、离散时间预测甚至半监督分类的任务中，都取得最优的结果。此外，值得注意的一点是NDCN模型是非常节省参数的，在大量的实验中，NDCN所用的参数数量都会比对比模型少约两个数量级。在NDCN的框架下，我们得以进一步建模和学习复杂系统的动力学变化，为我们以数据驱动的方式建模和理解系统提供了一个有效的新思路。

讲者：臧承熙整理：张章编辑：邓一雪

复杂科学最新论文

集智斑图收录来自 Nature、Science 等顶刊及arXiv预印本网站的最新论文，包括复杂系统、网络科学、计算社会科学等研究方向。每天持续更新，扫码即可获取：

推荐阅读

---

集智俱乐部QQ群｜877391004

商务合作及投稿转载｜[e-mail]

◆ ◆ ◆

搜索公众号：集智俱乐部

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

让苹果砸得更猛烈些吧！

👇点击“阅读原文”，追踪复杂科学顶刊论文