用度质量消息传递提升图节点中心性排序,轻量高效且支持有向无向图。
Degree-Mass Message Passing for Betweenness Ranking in Directed and Undirected Networks
- 基于多跳度质量设计不变尺寸的节点特征,实现轻量化建模。
- 在14个真实网络上,无向图性能提升24.6%,有向图提升10.9%。
- 参数量少56倍,推理速度最高快24.5倍,适合大规模图分析。
计算网络中节点重要性是长期存在的基础问题,催生了多种中心性度量。其中,介数中心性因精确计算在大规模网络中代价过高而难以应用。已有基于图神经网络(GNN)的方法虽能预测介数排名,但或存在与图规模相关的参数量,或仅限于无向图。本文提出一种轻量级GNN架构,利用介数中心性与多跳度质量之间的经验关联,将度质量作为尺寸无关的节点特征。为增强泛化能力,模型在合成图上训练,其度分布更贴近真实世界网络,涵盖有向与无向的尺度不变图及均匀有向双曲随机图。在14个真实世界网络(跨越社交、邮件、引用等八类领域)上评估,涵盖有向与无向情形。实验表明,该模型在无向图上提升肯德尔τ_b相关性达24.6%,有向图提升10.9%;相比最轻量基线,参数量减少56倍,推理时间相当,部分有向图上提速达24.5倍。
原文摘要 · Abstract (English)
Computing the importance of nodes in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures. A particularly well-known centrality measure is betweenness centrality, whose exact computation becomes prohibitive on large-scale networks. Graph Neural Network (GNN) models have thus been proposed to predict the ranking of nodes by betweenness centrality. However, existing GNN-based methods either have graph-size-dependent parameter counts or are limited to undirected graphs. We propose a lightweight GNN architecture that exploits the empirically observed relationship between betweenness centrality and multi-hop degree mass. This motivates the use of degree masses as size-invariant node features. To improve generalization, we train on synthetic graphs whose degree distributions more closely match those of real-world networks, including directed and undirected scale-free graphs and uniformly directed hyperbolic random graphs. We evaluate our model on 14 real-world networks spanning eight domains, including social, email, and citation networks, across both directed and undirected regimes. The experiments show that our model improves the Kendall $τ_b$ correlation by up to 24.6\% on undirected and 10.9\% on directed graphs, while using 56$\times$ fewer parameters than the lightest competing GNN baseline and achieving competitive inference time, with up to a 24.5$\times$ speedup on selected directed graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。