近日，华东师范大学计算机学院张凯团队、药学院/人工智能新药创智中心李洪林团队、复旦大学类脑智能科学与技术研究院张捷团队在人工智能领域顶刊TPAMI (IEEE Transactions on Pattern Analysis and Machine Intelligence, IF = 23.6)上发表了文章《A Transformative Topological Representation for Link Modelling, Prediction and Cross-Domain Network Analysis》（《链路建模、预测与跨域网络分析的新型拓扑表征》），提出了一种变革性的链路建模方法，为链路预测和跨域分析带来巨大优势。该方法基于随机游走和自适应核密度估计，将目标链路形成所需局部离散拓扑结构巧妙变换为连续分布函数，不但解决了传统图神经网络可解释性低和拓扑信息损失等问题，提高了链路预测精度，还使跨域链路分析成为可能，在科技、生物、通讯、合作等多元化现实世界网络中发掘了链路形成的三类共性模式，为拓扑特征工程和复杂网络分析提供了新的视角和方法。
｜研究背景
预测复杂网络中缺失的连边，即链路预测（link prediction），是计算机科学和复杂系统的热点问题，对理解网络结构和组织原则至关重要。其应用跨越了物理、生物，信息科学、脑科学和社会学等广泛的科学领域，及推荐系统，药物研发等实际应用。网络的连接往往“嵌入”在包含任意数量节点和高度异质性拓扑结构的子图中。因此，如何准确高效的表征网络链路仍是一项巨大挑战。
目前链路预测的方法主要分为三种：基于矩阵分解预测边的存在概率；基于节点相似度如共同邻居数来估计链路存在的可能性；基于深度学习特别是图卷积神经网络（GNN）的模型，通过节点信息传递机制进行预测。其中，基于分解的方法或者node2vec提取节点的拓扑特征是针对每个网络独立计算的，因由此产生的链路表征也
是依赖于特定于网络的，无法跨多个网络定义。图神经网络是链路预测的最好方法，但仍存在可解释性差，子图对齐困难，池化信息损失和非监督跨域表征受限等难题。另一方面，基于深度学习的方法通常更适合区分链路的存在与否，而不太适合用无监督手段描述跨网络中链路的分布。因此，为不同网络中的链路找到一个普适的表征方法，使其既能捕捉到网络链路的共性，又能适应不同网络的特点，仍然是一个挑战。
｜研究内容
为解决这些问题，本文在提出了一种新的链路表征和预测模型—偶极子空间密度网络（Dipole Space Density Network，DSDN）。该网络的构架如图1所示。首先，通过配对随机游走（Paired Random Walk with Restart）计算待研究链路(X-Y)所在局部封闭子图中，任意节点与链路端点X,Y的关联程度，并将这些关联分数对映射到以X,Y为轴的二维平面（既偶极子空间），形成点云。注意这里的局部子图的阶数（即距离目标节点的跳数）需事先指定，一般为1-2阶。其次，通过在该平面自适应地学习一系列“landmark”，以感知点云在这些位置的密度，从而将链路拓扑转化为固定维度的密度向量，有效避免了传统池化操作可能导致的信息损失；最后，将所有标志点处的密度值形成的密度向量作为紧凑的链路表征，用于下游分类和预测任务。
图1偶极子空间密度网络（Dipole Space Density Network）构架图；（a）抽取目标节点（X-Y）对应的h-阶封闭子图，并利用配对随机游走刻画邻居节点与X，Y之间的距离分数；（b）利用随机游分数将节点投影至二维平面，并在一系列自适应学习的标志点（黄色高斯函数中心）处估计点云分布的密度值；（c）将所有标志点对应的密度作为输入链路的向量表征，用于后续预测任务。
DSDN允许将任何感兴趣的链路投影并转换为二维点云，从而将复杂而难以理解的拓扑信息转换为形象而易于处理的密度分布。在图2中，我们给出了几个链路转化为点云的实例。可以看到，偶极子平面中，点云的对称性、分组方式和形状与链路的拓扑特性密切相关。其中，X，Y两个目标节点往往分布在偶极子平面的反对角线两端；子图其他的节点一般分布在对角线附近，坐标轴附近，或两者之间。数学上，我们可以证明点云的分布能够区分具有不同拓扑结构的子图，为提取链路特征提供了理论基础。理想情况下，任意两个非同构的局部封闭子图都具有不同的点云分布。更有趣的是，通过自适应核密度估计中高斯函数的光滑特性，能够进一步增强链路表征的稳定性，对于克服链路预测中的过拟合现象尤为有益。
图2 链路（X-Y）对应的局部封闭子图转化为二维点云分布的具体实例。
｜模型优势
DSDN具有高度解释性、节点排序不变性、泛化性和跨域建模等一系列优点。
首先，它为高度异质性的子图结构（不同节点个数、连接模式）提供了更加精细且固定维度的表征，同时避免了传统图池化图神经网络通过坍塌式池化引起的信息损失。它对局部子图节点排列顺序具有不变性。由于密度估计函数对样本集合具有排序不变性，提出的密度表征可以方便处理异构子图而无需对齐。
其次，通过将局部拓扑关系转化为低维密度，所提出的表征系统地反映了链路模式的拓扑特性，使模型不再是黑盒模，更易于解释。尤其是密度向量的每一个元素都明确量化了局部邻居节点距离目标节点对（X，Y）的距离分布模式，对于复杂网络分析中的知识发现有重要的指导作用。再次，模型达到了最先进的预测性能。表1和表2汇报了在两种人工生成网络（WS小世界网络、BA无标度网络）和13种现实世界网络（社交、合作、生物和基建网络）上，各类方法的链路预测精度。与强大的GNN模型相比，模型容量可以缩小至2-300倍（表3），运行速度快数十倍（图3）。
表1 各种链路预测方法在人工生成网络中的预测表现
表2 各种链路预测方法在实际网络中的预测表现
表3 各种链路预测方法参数规模
图3 各种链路预测方法训练时间。
最后，模型提供了一个用于跨领域分析链路形成模式的通用平台。由于该表征是无监督的，意味着得到的特征向量可以完全不受下游正负标签的影响，能够忠实地保留链路的多样化模式分布。这使得我们可以构建一个全局的链路模式图谱，揭示了一些有趣的链路形成共同模式，以及隐藏在原始领域之外的网络相似性，对于理解网络的组织结构规律具有重要意义（图4）。
图4 跨领域网络链路的多样性图谱。搜集了10个网络中30，000条存在的连边，通过DSDN转换为64-维向量，并采用TSNE进行可视化。左图：10个网络中各自连边实例的分布，被划分为三类典型模式：即桥状网络（Cluster-A），放射状网络（Cluster-B）和社团网络（Cluster-C）。右图：典型连边模式的实例（X-Y）黄色节点对，以及其对应的封闭子图（灰色），点云分布（蓝色）。
｜研究总结
总体而言，一个比现有图神经网络更准确、高效、容量可缩小数百倍的新型链路表征方法被提出，代表了链路预测问题拓扑表示学习中的一个重要进展。它提供了一个通用平台，建立了一个链路模式图谱，来研究和比较不同领域的链路模式。以促进科学、社会、生物和技术网络中链路模式的全球理解，揭示了性质高度不同的网络之间的有趣隐藏相似性。通过对链路模式进行全面的统计分析，推导跨领域假设，或将它们与网络功能相关联。这可能激发从链路模式特征或分布的角度理解结构-功能关系的新发现。
华东师范大学药学院/人工智能新药创智中心李洪林教授、复旦大学类脑智能科学与技术研究院张捷研究员为该文章共同通讯作者，华东师范大学计算机系张凯教授为第一作者，该研究得到了科技部重点研发项目（2022YFC3400501），国家自然科学基金委的经费支持（62276099，81825020）。
参考文献：[1] Zhang K, Shen J, He G, et al. A Transformative Topological Representation for Link Modeling, Prediction and Cross-Domain Network Analysis[J].IEEE Trans Pattern Anal Mach Intell.2024. doi:10.1109/TPAMI.2024.3378729
原文链接：https://ieeexplore.ieee.org/document/10475559
研究
