用GNN快速近似节点中心性，跨图类型表现好且提速近百倍。
Graph Neural Networks for Scalable and Transferable Node Centrality Approximation
- 用消息传递GNN学习节点排名，以精确中心性值为监督信号。
- 在未见图上，介数中心性排序相关性达0.851，接近精确计算。
- 模型可在不同图结构间迁移，适合大规模网络分析场景。
图神经网络（GNN）为难以精确计算的图属性提供学习型近似框架。本文研究用GNN实现介数与接近中心性的可扩展近似，将其建模为节点排序问题。以精确中心性值作为监督信号，使用肯德尔τ相关系数评估排序质量。探究消息传递GNN能否在不同图拓扑间学习可迁移的结构表示，而非仅拟合训练分布。在未见过的Erdos-Renyi图上，模型对介数中心性的τ达0.851，对接近中心性的τ达0.894。在N=5,000节点的大规模图上训练的介数模型τ高达0.938，验证了可扩展性。在Erdos-Renyi、Barabasi-Albert和高斯随机分区图上混合训练，提升了介数中心性的跨图族迁移能力。相比之下，接近中心性对社区结构更敏感，在真实世界拓扑上的迁移能力下降。此外，GNN推理相比精确计算最高提速97.7倍。结果表明，混合分布训练可改善基于GNN的中心性近似的结构迁移性，同时揭示接近中心性对拓扑敏感是当前开放挑战。
原文摘要 · Abstract (English)
Graph Neural Networks (GNNs) provide a learning-based framework for approximating graph quantities that are expensive to compute exactly. This paper investigates GNNs for scalable approximation of betweenness and closeness centrality, formulated as a node-ranking problem. Exact centrality values are used as supervision, and ranking quality is evaluated using Kendall's tau rank correlation. We study whether message-passing GNNs can learn transferable structural representations across different graph topologies rather than only fitting the distribution used during training. On unseen Erdos renyi graphs, the proposed models achieve tau = 0.851 for betweenness and tau = 0.894 for closeness. A large-scale betweenness model trained on graphs with N = 5,000 nodes achieves tau = 0.938, demonstrating scalability. Mixed-distribution training on Erdos renyi, Barabasi-Albert, and Gaussian Random Partition graphs improves betweenness transfer across graph families. In contrast, closeness centrality remains more sensitive to community-structured graphs and shows reduced transfer to real-world topologies. Finally, GNN inference achieves up to a 97.7x speedup over exact computation. These results show that mixed-distribution training can improve structural transfer in GNN-based centrality approximation, while identifying closeness centrality's sensitivity to topology as an open challenge.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。