arXiv:2606.12581cs.SIcs.AI2026-06

提出评估图简化对传播预测影响的标准化框架,揭示不同网络类型下简化策略的差异。

Graph Reduction in Multirelational Networks: A Spreading-Oriented Reduction Benchmark

  • 构建SORB基准框架,系统评估图简化对传播任务的影响。
  • 单层网络简化可保持种子集质量,多关系网络简化则导致排名显著退化。
  • 适合研究复杂网络传播与图分析的学者,尤其关注预处理影响者。

现实世界网络普遍存在不完整、噪声和动态演化问题,其规模常使直接分析计算成本过高。尽管影响力最大化(IM)被广泛研究,但图简化作为预处理步骤及其对IM准确率的影响仍缺乏深入探讨。本文提出传播导向的图简化基准(SORB),一个开源、标准化的评估框架,用于在多种任务设置下系统比较IM模型。SORB提供可扩展的流水线,涵盖单层与多层结构的真实网络,并将图简化直接纳入评估流程。该设计将研究重点从孤立分析IM算法转向量化图简化对预测性能的影响。通过SORB,我们研究了稀疏化与粗化在多种IM场景下的效果。结果表明,简化影响强烈依赖于网络类型(单层 vs. 多关系)和下游任务(Gain@k vs. AUC_cutoff):单层网络中稀疏化能保持种子集质量,而扁平化的多层网络无论采用何种简化策略均出现系统性排名退化。这些发现强调了在复杂网络传播研究中采用减少感知、多任务评估的重要性。

原文摘要 · Abstract (English)

Real-world networks are inherently incomplete, noisy, and dynamically evolving, making it difficult to capture all actors and their relationships. Their scale often renders direct analysis computationally demanding. While influence maximisation (IM) has been widely studied, the role of graph reduction as a preprocessing step, and its impact on IM accuracy, remains underexplored. In this work, we introduce the Spreading-Oriented Reduction Benchmark (SORB), an open-source, standardised framework for systematically evaluating IM models across diverse task settings. SORB provides an extensible pipeline operating on a representative collection of real-world networks, including single- and multilayer structures, and accounts for graph reduction directly into the evaluation process. This design shifts the focus from analysing IM algorithms in isolation to quantifying how graph reduction alters predictive performance. Using SORB, we study the effects of sparsification and coarsening across multiple IM scenarios. Our results show that the impact of reduction is strongly dependent on both the network type (single-layer vs. multirelational) and the downstream task ($Gain@k$ vs. $\mathrm{AUC}_{\mathrm{cutoff}}$): sparsification preserves seed set quality on single-layer networks, whereas flattened multilayer networks exhibit systematic ranking degradation regardless of reduction strategy. These findings highlight the importance of reduction-aware, multi-task evaluation when studying spreading processes in complex networks.

图神经网络传播模型网络简化

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。