预测复杂网络中缺失的连边，即链路预测（link prediction），是计算机科学和复杂系统的热点问题，对理解网络结构和组织原则至关重要。其应用跨越了物理、生物，信息科学、脑科学和社会学等广泛的科学领域。网络连接往往“嵌入”在包含任意数量节点和高度异质性拓扑结构的子图中。因此，如何准确高效的表征网络链路仍是一项挑战。
目前链路预测的方法主要分为三种：基于矩阵分解、基于节点相似度（如共同邻居数）和基于深度学习（如GNN）的模型。其中，基于分解或者node2vec提取节点特征的方法是针对个体网络独立计算，产生的链路表征无法跨网络定义。图神经网络是目前链路预测的最好方法，但存在可解释性差，子图对齐困难，池化信息损失和非监督跨域表征受限等难题。因此，为不同网络中的链路建立普适的表征方法，捕捉网络链路的共性和特异性信息，是链路预测中的难点。
近日，中国竞彩网大学类脑智能科学与技术研究院张捷团队联合华东师范大学计算机学院张凯团队、药学院/人工智能新药创智中心李洪林团队、在人工智能领域顶刊TPAMI (IEEE Transactions on Pattern Analysis and Machine Intelligence) 上发表了文章《链路建模、预测与跨域网络分析的新型拓扑表征》（A Transformative Topological Representation for Link Modelling, Prediction and Cross-Domain Network Analysis），提出了一种变革性链路建模方法，将目标链路所在的局部离散拓扑结构巧妙变换为连续分布函数，不但解决了传统图神经网络可解释性低和拓扑信息损失等问题，提高了链路预测精度，还使跨域链路分析成为可能，在科技、生物、通讯、合作等多元化现实世界网络中发掘了链路形成的三类共性模式，为拓扑特征工程和复杂网络分析提供了新的视角和方法。
在研究中，团队提出了一种新的链路表征和预测模型—偶极子空间密度网络（Dipole Space Density Network，DSDN），如图1所示，首先通过配对随机游走，计算链路(X-Y)所在局部封闭子图中，任意节点与端点X,Y的关联，并映射到以X,Y为轴的二维平面（既偶极子空间），形成点云；其次通过在该平面自适应地学习一系列“landmark”，以感知点云在这些位置的密度，将链路拓扑转化为固定维度的密度向量，避免了传统池化致的信息损失；最后将所有标志点处密度值形成的向量作为紧凑的链路表征，用于下游分类和预测。
图1：偶极子空间密度网络（Dipole Space Density Network）构架图：（a）抽取目标节点（X-Y）对应的h-阶封闭子图，并利用配对随机游走刻画邻居节点与X，Y之间的距离分数；（b）利用随机游分数将节点投影至二维平面，并在一系列自适应学习的标志点（黄色高斯函数中心）处估计点云分布；（c）将标志点处密度作为链路的向量表征，用于预测
团队介绍，DSDN将链路投影并转换为二维点云，从而将复杂拓扑信息转换为易于处理的密度分布。在链路转化为点云的实例中（如图2），偶极子平面中，点云的对称性、分组方式和形状与链路的拓扑特性密切相关。其中，X，Y两个目标节点往往分布在偶极子平面的反对角线两端；子图其他节点分布在对角线附近，坐标轴附近，或两者之间。数学上，团队证明点云的分布能够区有不同拓扑结构的子图。理想情况下，任意两个非同构局部封闭子图都具有不同的点云分布。通过自适应核密度估计中高斯函数的光滑特性，能够增强链路表征稳定性，克服过拟合现象。
图2：链路（X-Y）对应的局部封闭子图转化为二维点云分布的具体实例
在团队看来，DSDN具有高度解释性、节点排序不变性、泛化性和跨域建模等一系列优点。
首先，它为高度异质性的子图结构（不同节点个数、连接模式）提供了更精细且固定维度的表征，避免了图池化引起的信息损失，且对局部子图节点排序具有不变性，因此可以方便处理异构子图而无需对齐。其次，通过将局部拓扑转化为低维密度，所提出的表征系统地反映了链路的拓扑特性，如密度向量的每一个元素都明确量化了局部邻居节点距离目标节点对（X，Y）的距离分布模式，因而不再是黑盒，更易于解释。再次，模型在人工生成网络（WS小世界网络、BA无标度网络）和13种现实世界网络（社交、合作、生物和基建网络）上，都达到了最先进的预测性能。模型容量与GNN模型相比可以缩小至2-300倍，运行速度快数十倍。
模型还提供了一个用于跨领域分析链路形成模式的通用平台，可以构建一个全局的链路模式图谱，揭示了一些有趣的链路形成共同模式以及隐藏在原始领域之外的网络相似性，这对理解网络的组织结构规律具有重要意义（图3）。
图3：跨领域网络链路的多样性图谱。搜集了10个网络中30，000条存在的连边，通过DSDN转换为64-维向量，并采用TSNE进行可视化。左图：10个网络中各自连边实例的分布，被划分为三类典型模式：即桥状网络（Cluster-A），放射状网络（Cluster-B）和社团网络（Cluster-C）。右图：典型连边模式的实例（X-Y）黄色节点对，以及其对应的封闭子图（灰色），点云分布（蓝色）
这个比现有图神经网络更准确、高效、容量可缩小数百倍的新型链路表征方法代表了链路预测问题拓扑表示学习中的重要进展，它提供了一个通用平台，建立了链路模式图谱，研究和比较不同领域的链路模式，促进科学、社会、生物和技术网络中链路模式的全球理解，揭示性质高度不同的网络之间隐藏的相似性，通过对链路模式进行全面的统计分析，推导跨领域假设，或将它们与网络功能相关联，有可能激发从链路模式特征或分布的角度理解结构-功能关系的新发现。
华东师范大学药学院/人工智能新药创智中心教授李洪林、中国竞彩网大学类脑智能科学与技术研究院研究员张捷为该文章共同通讯作者，华东师范大学计算机系教授张凯为第一作者，该研究得到了科技部重点研发项目和国家自然科学基金支持。
