面向复杂网络关键节点识别的结构排序图神经网络

《Physica A: Statistical Mechanics and its Applications》：Structure Ranking Graph Neural Networks for Critical Node Identification in Complex Networks

　　

摘要

关键节点识别在增强复杂网络系统的鲁棒性和抗毁性方面发挥着关键作用。然而，现有的图神经网络（GNN）方法往往过度依赖节点属性，并且通常将该问题简单地表述为回归任务，因此无法捕捉节点相对重要性之间的细微差异。为了应对这些挑战，本文提出了一种名为结构排序图神经网络（SGNN）的框架。该模型仅依赖网络拓扑，将关键节点识别重新表述为一种学习排序问题。具体而言，SGNN采用了一种由拓扑驱动的节点初始化方案，利用节点度、平均邻居度、聚类系数和k-core信息构建固定维度的结构表示。随后使用GCN和GAT架构来学习高阶结构表示。SGNN不直接回归节点影响力值，而是采用成对间隔排序损失，以显式约束具有不同传播影响力的节点的相对排序。训练完成后，一种基于结构熵的重排序策略将预测分数在局部邻域中的分布纳入考量，以优化初始排序。SIR传播影响力被用作监督信号。在九个真实世界网络和三个BA合成网络上与十一种基线方法进行实验表明，SGNN在最大连通分量（LCC）、网络效率（NE）和曲线下面积（AUC）方面在大多数数据集上达到了具有竞争力或更优的性能，同时保持了良好的分数区分能力。消融研究进一步证实了排序损失和基于结构熵的后处理所带来的贡献。

引言

复杂网络广泛存在于各种领域，包括电力系统、交通网络、社交网络和生物网络，其中其结构特征直接影响功能性能和运行安全。在这些网络中，一小部分节点通常在信息扩散、能量传输或故障传播等过程中发挥着主导作用；这些节点通常被称为关键节点[1]、[2]、[3]、[4]。例如，在航运网络中，识别关键港口对于保障国际贸易安全至关重要[5]。在疾病传播网络中，识别传染源可以有效遏制疫情的蔓延[6]。类似地，在电力系统中，准确定位关键变电站有助于防止由局部故障引发的级联故障和大规模停电[7]。因此，高效准确地识别关键节点仍然是复杂网络分析领域的核心问题。

尽管已提出了许多关键节点识别方法，但在复杂网络背景下，该问题仍面临重大挑战。在现有研究中，最常见的基于节点中心性指标的方法，如度中心性（DC）、介数中心性（BC）和接近中心性（CC）[8]、[9]、[10]。这些方法通过刻画节点在网络中的局部或全局位置来量化节点重要性，具有计算简单和可解释性强的优点。然而，其核心假设往往依赖于单一或低阶的拓扑特征，难以有效捕捉复杂网络中普遍存在的高阶结构依赖和非线性相关性。同时，不同类型的网络在规模、连接模式和拓扑异质性方面存在显著差异，这使得具有固定形式的中心性指标在不同网络间应用时往往表现出较弱的泛化能力[11]、[12]。

近年来，尽管图神经网络（GNN）凭借其卓越的非线性结构表征能力在关键节点识别领域备受关注，但现有研究范式仍受限于两个核心瓶颈。首先，关于结构与属性解耦的两难困境，主流框架主要依赖于丰富的显式节点属性，从而限制了其在仅具有拓扑信息的真实场景中的适用性，例如匿名社交网络。其次，关于优化目标与任务性质之间的不匹配，现有方法频繁地将关注相对序关系的排序问题建模为针对高度嘈杂模拟值的绝对回归任务。这种回归与排序的不匹配不仅引入了不必要的拟合噪声，还严重削弱了模型在关键节点排序任务中的泛化鲁棒性[13]、[14]、[15]。

为解决上述挑战，本文提出了一种名为结构排序图神经网络（SGNN）的框架。与传统方法不同，SGNN仅依赖拓扑结构，并将关键节点识别重新表述为学习排序问题。本文的主要贡献总结如下：

• (1)
  提出了一种拓扑驱动的节点初始化与表征学习机制。直接从网络拓扑构建固定维度的结构描述符，包括归一化节点度、归一化平均邻居度、聚类系数和归一化k-core值。所得结构表示通过共享映射进行投影，随后输入GCN-GAT骨干网络，以进一步捕捉局部邻域关系和高阶拓扑依赖。
• (2)
  将关键节点识别从数值影响力回归重新表述为关注节点相对重要性的学习排序问题。采用基于SIR的传播影响力作为监督信号，并使用成对间隔排序损失来直接约束节点对的预测排序。进一步引入了随机节点对采样以避免穷举配对带来的计算开销。此外，在相同的网络架构、输入特征和训练设置下，与MSE、RankNet和ListMLE进行了对照比较，以考察不同优化目标对节点排序性能的影响。
• (3)
  在模型训练后引入了一种基于结构熵的拓扑感知重排序策略。结构熵不参与损失计算或模型参数更新，而是在SGNN原始输出的基础上，通过纳入预测分数在局部邻域中的分布来调整节点的相对排序。消融实验结果表明，该后处理策略在不改变模型训练过程的情况下，进一步提升了LCC-AUC和NE-AUC。
• (4)
  在九个真实世界网络和三个不同规模的BA网络上进行了大量实验。将SGNN与包括传统基于中心性的方法以及AGNN、CGNN、CNT、GCN-MB、GNNE和GNR在内的11种基线方法进行比较。从LCC、NE、AUC和单调性方面评估节点排序性能。此外，进行了十次独立运行、损失函数消融实验、结构熵消融实验和随机节点重标记实验，以进一步评估性能稳定性和置换等变性。

本文其余部分组织如下。第2节回顾相关工作。第3节阐述问题定义。第4节详细介绍所提出的方法。第5节提供相关实验结果。第6节总结全文并展望未来的研究方向。

章节摘要

传统方法

基于网络拓扑的中心性指标是关键节点识别领域最经典且最广泛使用的方法[16]。最直观的指标是度中心性（DC），其核心假设是连接数越多的节点重要性越大。尽管该方法计算复杂度低，适用于大规模网络的快速分析，但它仅依赖于局部邻接信息，无法……

问题定义

本节介绍必要的符号，并正式定义基于网络拓扑结构的关键节点识别问题。设 G = (V, E) 表示一个无向无权复杂网络，其中 V = {v₁,v₂,…,v_n} 表示包含 N 个节点的集合，E 表示边集。网络拓扑结构由邻接矩阵 A∈{0,1}^N×N 描述。如果节点 v_i 和 v_j 之间存在边，则 A_ij=1；否则，A_ij=0。具体而言，本研究……

所提出的方法

本节详细介绍所提出的结构排序图神经网络（SGNN）。该框架旨在通过网络拓扑学习节点的高维表示，以解决节点排序问题。

实验

所提出的算法和基线算法使用Python语言和PyTorch 2.3.1版本实现。硬件配置包括一台运行频率为3.40 GHz的Intel Core i7-14700 KF处理器，64 GB内存，以及一块配备12 GB显存的NVIDIA 4070 Ti GPU。

结论

本研究提出了一种面向无属性复杂网络关键节点识别的结构排序图神经网络（SGNN）。SGNN构建了基于拓扑的节点特征，包括度、平均邻居度、聚类系数和k-core，并采用GCN-GAT骨干网络学习高阶拓扑表示。SGNN不直接拟合绝对的SIR传播影响力，而是使用成对间隔排序损失来约束节点的相对重要性……

CRediT作者贡献声明

黄旭颖（Huang XuYing）：初稿撰写、验证、软件、方法学、调查、数据整理。黄康正（Kangzheng Huang）：审稿与编辑、初稿撰写、可视化、验证、指导、软件、资源、项目管理、方法学、调查、获取资金、形式化分析、数据整理、概念构思。

利益冲突声明

作者声明不存在已知的可能影响本文所述工作的竞争性经济利益或个人关系。

致谢

本工作得到了中央高校基本科研业务费（104972025YJS0119）和中国科协青年科技人才培养计划博士生项目的资助。

黄旭颖 | 黄康正

重庆交通大学江河与海洋工程学院，重庆，402247，中国