ICLR 2021 | 演化图单纯复形中的高阶结构预测

今天给大家介绍一篇投稿于ICLR 2021上的文章“Higer-order structure prediction in evolving graph simplicial complexes”。动态图中包含了许多高阶相互作用，但是人们对成对链接预测问题中的高阶相互作用的关注较少。另外，现有的基于启发式的高阶结构预测方法缺乏理论支持，并且不能有效利用高阶结构中潜在结构包含的知识。针对这些问题，本文提出将相互作用看作单纯形拓扑结构并进行捕获，使用非参数核估计从时间处理（如图快照序列）角度来观察演化图。最后作者通过实验证明本文提出的方法相较于其它方法表现更好。

1

背景

许多类型的网络（如社交网络、生物网络和化学反应网络）都是高度动态的，网络中新增的相互作用在网络节点之间引入了新的边，使网络迅速发展和增长。通常，人们通过链路预测来观察网络随时间的演化。人们观察到，大多数真实世界的图表现出高阶的分组交互，同时涉及两个以上的节点。在自然界中，也可以同时观察到几种蛋白质在生物网络中相互作用。

目前，较少的工作研究了预测高阶集群之间相互作用的问题。Benson等人最初引入了一个单纯形来模拟图中节点之间的分组交互。他们提出预测一个相似的封闭事件，一个开放的单纯形（成员顶点之间只有成对的相互作用）将过渡到一个封闭的单纯形(其中所有成员顶点同时参与高阶关系）。图1（中）显示了从开放三角形到封闭三角形的过渡示例。图1（右）展示了超精度预测任务。

图1 时间变化时，开放单纯形到封闭单纯形演变

虽然基于相似闭包事件预测或超边距预测模型都能处理高阶结构，但它们都未能捕捉高阶结构随时间的高度复杂和非线性演化。这两种模型都有两个主要的局限性。首先，它们从图形的单个静态状态中预测结构，不会将添加新边的演化过程视为时间过程。其次，它们的特征提取主要基于流行的启发式方法，没有强有力的理论支持。此外，基于超图的方法还将高阶结构建模为超边，忽略了单个超边中存在的低维子结构。因此，无法区分各种子结构关系。

为了解决这些问题，本文将图1过程看作非参数时间序列预测框架下的一个时间过程，它模拟了高阶结构及其局部邻域（空间维数)在移动时间窗口(时间维数)上的演化。然后，推理问题就被建模为预测在时间t时，t’>t向高维单纯形的演化。而且仅需要一个子集就能预测它的演变过程，泛化能力更强。同时作者还设计了一个核估计量来推断未来向高维相似切片的演化，并证明了文中的估计量的一致性和渐近正态性。

作者的贡献主要有三点：1）提出了一个核估计量，预测进化网络中的高阶交互。2）证明了核估计量的一致性和渐近正态性。2）提出高阶链路预测基线来评估现实世界动态网络上的方法，并观察到与基线相比预测精度的显著提高。

2

模型

2.1 图形相似复合体(GSC)

文章从一个抽象单纯复形(ASC)的一般概念开始，使用ASCs定义一个单纯形。我们将这个定义专门用于图形，并定义了一个图形单纯复形(GSC)。

抽象单纯复形和单纯形

抽象单纯复形(ASC)是有限非空集的集合A，如果σ是A的元素，那么σ的每个非空子集也是如此。A的元素σ叫做A的单纯形；它的维度比它的元素个数少一个。基于此，设G=(V，E)是一个顶点集V和边集E的有限图。G上的图单纯复形(GSC)ɠ，是由V的子集组成的ASC，ɠ也是G的子图集。用σ(d)=[v0，v1，...，vd]表示GSC的d维单纯形(d-simplex）。σ(d)的每个非空子集称为σ(d)的面。

筛选GSC

对于I⊂N，在I上索引的筛选GSC是GSCs的一个成员(ɠt)t∈I，因此对于I中的每一个t≤t’，ɠt⊂ɠt’成立。ɠ_(d’) := {σ(d) ∈ɠ| d≤d’}。当顶点i和j在ɠ_(0)中相邻时，顶点i，j在ɠ_(0)中，i~kj，表示顶点j到i时k可达的，即存在一条长度最多为k的路径，在ɠ_(0)中连接i和j。

以顶点和单纯形为中心的k-ball

在时间t时，定义一个以顶点i为中心的k球Bt，Bt,k(i)：={j：i~kj和i，j∈ɠ_(0)}。定义了一个以单纯形σ(d)为中心的k球，

其中Vert(σ(d)）表示σ(d)中的所有顶点。

2.2 预测高阶单纯形

有了上面的描述，作者需要预测单纯形仍需要一些数学表达。考虑一个筛选GSC,ɠt,p。在时间t，给定一个d维单纯形σ(d)=[v0，...，vd]，我们预测了一个(d+1)维单纯形，τ(d+1)=[v0，...，vd，]的形成，它具有一个新的顶点∈Bt,k(σ(d))。在这里，我们限制是k-可达的σ(d)。为了找出在时间t+1时,τ(d+1)中最有可能出现哪些相似单纯形和顶点，我们需要为σ(d)和设计特征。

我们设计了一个与k球概念相关联的单纯形的特征设计。该设计分为两个主要元素：（1)具有子复形的面向量，(2）评分函数。ɠ的面向量定义为f(ɠ) = (f1, f0, . . . , fd’)， 其中fk=fk(ɠ)记录k维面向量σ(k)∈ɠ的数目。然后，定义了单纯形σ(d)在时间t处的特征，Nt(σ(d)) = f(ɠ’t(σ(d)))。

评分函数的目的是利用与σ(d)的邻居来提取的特征。首先描述两个顶点之间的相关性，给定两个顶点v，v’∈ɠ，我们用s(v，v’）表示σ(d)中顶点v和v‘的所有过去共现加权和，其中权重是d来自σ(d)。然后，我们设计了一个评分函数h（·，·），它为顶点可能引入d维单纯形σ(d)=[v0，....，vd]，评分函数描述了σ(d)和在时间t处的共现性。

对于给定的d-维单纯形σ(d)在时间t，可能引入新的顶点∈Bt，k(σ(d))分配了一个特征向量

对于预测模型和核估计量，也用函数式对其定义和表达。作者同时分析了估计量的时间复杂度，最后得到结果都是与参数线性相关的。说明该模型时间效率很高。

3.3 估计量的理论性质

估计量具有一致性和渐进正态性，作者给出了一系列公式证明了所提出的估计量的一致性和渐近正态性。同时证明了估计量的误差弱收敛于正态分布。此属性允许进行更详细的调查，例如纠正估计器中的错误或执行统计测试。利用渐进正态性这一性质，可以根据估计误差的分布进行详细的推断。例如，可以为预测创建置信区间，并执行统计测试来严格测试关于引进单纯形的假设。

3

实验

作者经验性地评估了提出的估计器在实际动态图上与基线相比的性能。在实验中，基本前提是捕获围绕d维单纯形的局部和高阶性质，以预测新的(d+1)维单纯形在时间t’>t处的到达状态，其中包含σ(d)作为它的面向量。

数据集

作者使用了来自Benson等人的真实世界动态图数据集的结果。每个数据集包含n个节点、m条边和x时间戳单纯形。有四个数据集，分别为Enron(n=143，m=1.8K，x=5K)，EU(n=998，m=29.3K，x=8K)，Contact(n=327，m=5.8K，x=10K)和NDC(n=1.1K，m=6.2K，x=12K)。

实验设置

作者首先按到达时间排序，并将时间戳单纯形分组为T时间片。对于大多数实验，T设为20，d=2；在EU和NDC数据集中，T分别设置为6和12的。然后，我们从[1，T-1]范围内的时间切片中随机采样了一组d维单纯形。第T时间切片中，那些d维单纯形成功的在（d+1）维单纯形与顶点配对的，就被设为正样本，否则为负样本。作者选择了相同数量的正负样本进行评估。利用K折交叉验证，我们将验证的第T时间切片与每个交叉验证的第T时间切片一一交换，K定为3。所有实验重复10次取平均值AUC进行评估。结果如表1所示：

作者对单边预测法的结果进行了平均，其中d-simplex中的每个节点与要配对的顶点之间形成一个新的边。具体来说，将我们的估计量与启发式(Adamic-Adar(AA)、Jaccard系数(JC))、偏好链接(PA)和基于深度学习(Node2vec(NV)和SEAL(SL)的链接预测方法进行了比较。作者注意到(Benson)预测“简单封闭”与我们的方法最接近，但目标不同，因此我们忽略了与他们的工作的比较。对于超边缘预测(HP)，我们选择了最近最有代表性的工作进行比较，虽然这项工作只适用于静态非进化超图。

4

总结

作者对估计量和基线的运行时间进行了平均，并对a(d+1)-simplex的到达进行了两组实验，并在表1中总结了d={1，2}时的实验结果。同时还通过交叉验证证明了估计器的带宽β对实验结果的影响。

预测2-simplex（d=1）

我们的方法比基于深度学习的方法(NV和SL)快近两个数量级，比超图预测方法(HP)快近一个数量级。虽然单边启发式方法相对较快，但它们的AUC分数与我们的方法的AUC分数不可比。此外，与上一个最佳的预测方法相比，我们实现了近30%（Enron）改进。与HP相比，我们取得了非常显著的改进。

预测2-simplex（d=2）

我们的方法和基线之间的AUC分数差距变得更加明显。我们的运行时间也有很大的改善，因为很少一部分单纯形的维度超过了3。我们还注意到，在HP中，AUC分数与d=1时的预测相比不变或略有下降。

传统的估计不能准确地捕捉随时间演变的高阶结构（及其子结构）中存在的丰富的潜在信息。而作者提出的估计器能简洁地捕捉这一信息。

作者提出了一种新的预测方法，用于高阶分组交互，并可以同时涉及两个以上的节点。一个高阶链路预测任务涉及预测给定群组在时间t处是否演化为在时间t’>t处更大的相互作用组群。我们将高阶相互作用建模为单纯形，提出了一种新的核估计量来解决高阶结构预测问题，并从理论上证明了我们的估计量的一致性和渐近正态性。最后通过实验证明，作者方法效果是最优的。

参考资料

https://openreview.net/forum?id=QSMvGB5j5-