![[2506.22095] Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2506.22095] Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs
Summary
This article presents novel graph neural network methods for multi-objective routing on multigraphs, addressing limitations of existing techniques and demonstrating competitive performance through empirical evaluation.
Why It Matters
Routing on multigraphs is crucial for various real-world applications where multiple edges with distinct attributes exist between node pairs. This research advances the field of machine learning by providing scalable solutions that enhance routing efficiency, which is vital for logistics, transportation, and network design.
Key Takeaways
- Proposes two graph neural network methods for multi-objective routing.
- First method selects edges autoregressively on the multigraph.
- Second method simplifies the multigraph before routing, enhancing scalability.
- Empirical evaluations show competitive performance against existing heuristics.
- Addresses a significant gap in routing techniques for multigraphs.
Computer Science > Machine Learning arXiv:2506.22095 (cs) [Submitted on 27 Jun 2025 (v1), last revised 20 Feb 2026 (this version, v5)] Title:Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs Authors:Filip Rydin, Attila Lischka, Jiaming Wu, Morteza Haghir Chehreghani, Balázs Kulcsár View a PDF of the paper titled Beyond Simple Graphs: Neural Multi-Objective Routing on Multigraphs, by Filip Rydin and 4 other authors View PDF HTML (experimental) Abstract:Learning-based methods for routing have gained significant attention in recent years, both in single-objective and multi-objective contexts. Yet, existing methods are unsuitable for routing on multigraphs, which feature multiple edges with distinct attributes between node pairs, despite their strong relevance in real-world scenarios. In this paper, we propose two graph neural network-based methods to address multi-objective routing on multigraphs. Our first approach operates directly on the multigraph by autoregressively selecting edges until a tour is completed. The second model, which is more scalable, first simplifies the multigraph via a learned pruning strategy and then performs autoregressive routing on the resulting simple graph. We evaluate both models empirically, across a wide range of problems and graph distributions, and demonstrate their competitive performance compared to strong heuristics and neural baselines. Comments: Subjects: Machine Learning (cs.LG); Artificial Intelligence (cs.AI) Cite a...
