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

arXiv: https://arxiv.org/abs/2606.12581 · HTML: https://mlsanity.com/paper/2606.12581/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 42 references that are in the map.
- First posted on arXiv 10 Jun 2026.

## Builds on (most cited first, 22 of 22)

- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Wiki-CS: A Wikipedia-Based Benchmark for Graph Neural Networks](https://mlsanity.com/paper/2007.02901/) (2020)
- [Self-supervised Heterogeneous Graph Neural Network with Co-contrastive Learning](https://mlsanity.com/paper/2105.09111/) (2021)
- [Privacy for Free: How does Dataset Condensation Help Privacy?](https://mlsanity.com/paper/2206.00240/) (2022)
- [Multilayer Networks](https://mlsanity.com/paper/1309.7233/) (2013)
- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [Graph Data Augmentation for Graph Machine Learning: A Survey](https://mlsanity.com/paper/2202.08871/) (2022)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [GC-Bench: An Open and Unified Benchmark for Graph Condensation](https://mlsanity.com/paper/2407.00615/) (2024)
- [Spreading processes in Multilayer Networks](https://mlsanity.com/paper/1405.4329/) (2014)
- [GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights](https://mlsanity.com/paper/2406.16715/) (2024)
- [Explaining reviews and ratings with PACO: Poisson Additive Co-Clustering](https://mlsanity.com/paper/1512.01845/) (2015)
- [Scaling R-GCN Training with Graph Summarization](https://mlsanity.com/paper/2203.02622/) (2022)
- [Algorithms for Large-scale Network Analysis and the NetworKit Toolkit](https://mlsanity.com/paper/2209.13355/) (2022)
- [GCondenser: Benchmarking Graph Condensation](https://mlsanity.com/paper/2405.14246/) (2024)
- [A multilayer network dataset of interaction and influence spreading in a virtual world](https://mlsanity.com/paper/1702.06373/) (2017)
- [Nearly-Linear Time Spectral Graph Reduction for Scalable Graph Partitioning and Data Visualization](https://mlsanity.com/paper/1812.08942/) (2018)
- [Influence Maximization in Social Networks: A Survey of Behaviour-Aware Methods](https://mlsanity.com/paper/2108.03438/) (2021)
- [Rank-Refining Seed Selection Methods for Budget Constrained Influence Maximisation in Multilayer Networks under Linear Threshold Model](https://mlsanity.com/paper/2405.18059/) (2024)
- [Network Diffusion -- Framework to Simulate Spreading Processes in Complex Networks](https://mlsanity.com/paper/2405.18085/) (2024)
- [Identifying Super Spreaders in Multilayer Networks](https://mlsanity.com/paper/2505.20980/) (2025)

## Abstract (arXiv)

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. AUCcutoff): 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.