# Provably Powerful Graph Neural Networks for Directed Multigraphs

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 53 of its 79 references that are in the map.
- First posted on arXiv 20 Jun 2023.

## Builds on (most cited first, 30 of 53)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [XGBoost: A Scalable Tree Boosting System](https://mlsanity.com/paper/1603.02754/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Deep Graph Infomax](https://mlsanity.com/paper/1809.10341/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Forecasting Global Weather with Graph Neural Networks](https://mlsanity.com/paper/2202.07575/) (2022)
- [Anti-Money Laundering in Bitcoin: Experimenting with Graph Convolutional Networks for Financial Forensics](https://mlsanity.com/paper/1908.02591/) (2019)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)

## Built on by (most cited first, 27 of 27)

- [Realistic Synthetic Financial Transactions for Anti-Money Laundering Models](https://mlsanity.com/paper/2306.16424/) (2023)
- [Network Analytics for Anti-Money Laundering -- A Systematic Literature Review and Experimental Evaluation](https://mlsanity.com/paper/2405.19383/) (2024)
- [Learning Graph Foundation Models on Riemannian Graph-of-Graphs](https://mlsanity.com/paper/2605.09993/) (2026)
- [Towards Data-centric Machine Learning on Directed Graphs: a Survey](https://mlsanity.com/paper/2412.01849/) (2024)
- [TeMP-TraG: Edge-based Temporal Message Passing in Transaction Graphs](https://mlsanity.com/paper/2503.16901/) (2025)
- [Privacy-Preserving Graph-Based Machine Learning with Fully Homomorphic Encryption for Collaborative Anti-Money Laundering](https://mlsanity.com/paper/2411.02926/) (2024)
- [MEGA: Message Passing Neural Networks for Multigraphs with EdGe Attributes](https://mlsanity.com/paper/2412.00241/) (2024)
- [Graph machine learning for flight delay prediction due to holding manouver](https://mlsanity.com/paper/2502.04233/) (2025)
- [Towards Collaborative Anti-Money Laundering Among Financial Institutions](https://mlsanity.com/paper/2502.19952/) (2025)
- [Deep Learning Approaches for Anti-Money Laundering on Mobile Transactions: Review, Framework, and Directions](https://mlsanity.com/paper/2503.10058/) (2025)
- [Advances in Continual Graph Learning for Anti-Money Laundering Systems: A Comprehensive Review](https://mlsanity.com/paper/2503.24259/) (2025)
- [ATM-GAD: Adaptive Temporal Motif Graph Anomaly Detection for Financial Transaction Networks](https://mlsanity.com/paper/2508.20829/) (2025)
- [Multi-Class and Multi-Task Strategies for Neural Directed Link Prediction](https://mlsanity.com/paper/2412.10895/) (2024)
- [GARG-AML against Smurfing: A Scalable and Interpretable Graph-Based Framework for Anti-Money Laundering](https://mlsanity.com/paper/2506.04292/) (2025)
- [HSG-12M: A Large-Scale Benchmark of Spatial Multigraphs from the Energy Spectra of Non-Hermitian Crystals](https://mlsanity.com/paper/2506.08618/) (2025)
- [FD4QC: Application of Classical and Quantum-Hybrid Machine Learning for Financial Fraud Detection A Technical Report](https://mlsanity.com/paper/2507.19402/) (2025)
- [A Tight Expressivity Hierarchy for GNN-Based Entity Resolution in Master Data Management](https://mlsanity.com/paper/2603.27154/) (2026)
- [Extracting Money Laundering Transactions from Quasi-Temporal Graph Representation](https://mlsanity.com/paper/2604.02899/) (2026)
- [TransXion: A High-Fidelity Graph Benchmark for Realistic Anti-Money Laundering](https://mlsanity.com/paper/2604.17420/) (2026)
- [Federated Layer-Wise Exchange for Cross-Client Money Laundering Pattern Detection](https://mlsanity.com/paper/2605.06433/) (2026)
- [Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networks](https://mlsanity.com/paper/2605.26243/) (2026)
- [Choosing a parallel heterogeneous ensemble method for tabular classification](https://mlsanity.com/paper/2607.05103/) (2026)
- [SALT-GNN: Handling Dense Neighborhoods in Anti-Money Laundering Graphs via Statistics-Aware Attention](https://mlsanity.com/paper/2607.10131/) (2026)
- [Population-Calibrated Graph Screening at 835-Million-Address Scale, with Label-Free Transfer to New Chains](https://mlsanity.com/paper/2609.03036/) (2026)
- [Dual-Scale Relational Graph Transformers for Ecosystem-Aware Fraud Detection](https://mlsanity.com/paper/2610.04138/) (2026)
- [Privacy-Preserving GNN Inference on Financial Transaction Graphs via Homomorphic Encryption](https://mlsanity.com/paper/2610.18054/) (2026)
- [Random Probing for Structural Self-Interactions in Graph Neural Networks](https://mlsanity.com/paper/2610.18164/) (2026)

## Abstract (arXiv)

This paper analyses a set of simple adaptations that transform standard message-passing Graph Neural Networks (GNN) into provably powerful directed multigraph neural networks. The adaptations include multigraph port numbering, ego IDs, and reverse message passing. We prove that the combination of these theoretically enables the detection of any directed subgraph pattern. To validate the effectiveness of our proposed adaptations in practice, we conduct experiments on synthetic subgraph detection tasks, which demonstrate outstanding performance with almost perfect results. Moreover, we apply our proposed adaptations to two financial crime analysis tasks. We observe dramatic improvements in detecting money laundering transactions, improving the minority-class F1 score of a standard message-passing GNN by up to 30%, and closely matching or outperforming tree-based and GNN baselines. Similarly impressive results are observed on a real-world phishing detection dataset, boosting three standard GNNs' F1 scores by around 15% and outperforming all baselines.