Multigraph Message Passing with Bi-Directional Multi-Edge Aggregations

Graph Neural Networks (GNNs) have seen significant advances in recent years, yet their application to multigraphs, where parallel edges exist between the same pair of nodes, remains under-explored. Standard GNNs, designed for simple graphs, compute node representations by combining all connected edges at once, without distinguishing between edges from different neighbors. There are some GNN architectures proposed specifically for multigraphs, yet these architectures perform only node-level aggregation in their message passing layers, which limits their expressive power. Furthermore, these approaches either lack permutation equivariance when a strict total edge ordering is absent, or fail to preserve the topological structure of the multigraph. To address all these shortcomings, we propose MEGA-GNN, a unified framework for message passing on multigraphs that can effectively perform diverse graph learning tasks. Our approach introduces a two-stage aggregation process in the message passing layers: first, parallel edges are aggregated, followed by a node-level aggregation of messages from distinct neighbors. We show that MEGA-GNN is not only permutation equivariant but also universal given a strict total ordering on the edges. Experiments show that MEGA-GNN significantly outperforms state-of-the-art solutions by up to 13% on Anti-Money Laundering datasets and is on par with their accuracy on real-world phishing classification datasets in terms of minority class F1 score. Graph Neural Networks (GNNs) (Xu et al. (2019); Gilmer et al. (2017); Veličković et al. (2018); Corso et al. (2020); Hamilton et al. (2017)) have become Swiss Army knives for learning on graphstructured data. However, their widespread adoption has primarily focused on simple graphs, where only a single edge can connect a given pair of nodes. This simplification overlooks a crucial aspect of many real-world scenarios, where multigraphs, graphs that feature parallel edges between the same pair of nodes, are common. For instance, financial transaction networks, communication networks and transportation systems are often modeled as multigraphs, allowing multiple different interactions between the same two nodes.