Research map / Graph learning / GNN architectures
Provably Powerful Graph Neural Networks for Directed Multigraphs
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that GIN-style MPNNs augmented with reverse message passing, directed multigraph port numbering, and ego IDs can detect any directed subgraph pattern, and validates this on synthetic subgraph tasks and two financial crime datasets (AML and Ethereum phishing).
Problem
Standard message-passing GNNs cannot detect many directed subgraph patterns (e.g., cycles, fan-in/out, scatter-gather, bicliques) and are not designed for directed multigraphs such as financial transaction networks.
Approach
Combine three simple adaptations for MPNNs: reverse message passing (separate in/out aggregation), multigraph port numbering that attaches port numbers in both directions as edge features, and ego IDs; prove that together they let a GNN assign unique node IDs and so detect any directed subgraph pattern.
Key results
- Multi-GIN raises GIN's minority-class F1 on AML Small HI from 28.7% to 57.2%, a gain of almost 30 points.
- On synthetic tasks, GIN with reverse MP, ports, and ego IDs scores 97.42% F1 on scatter-gather, while standard GIN scores 69.31%.
- On ETH phishing, Multi-PNA and Multi-PNA+EU beat all baselines by more than 12 points in minority-class F1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add reverse message passing to GIN (ablation) | GIN · Synthetic degree-out | minority-class F1: 43.58 -> 99.08 | Helped |
| Add port numbering alone to GIN (ablation) | GIN · Synthetic fan-in | minority-class F1: 95.57 -> 99.59 | Helped |
| Add reverse message passing and port numbering to GIN (ablation) | GIN · Synthetic fan-out | minority-class F1: 35.91 -> 99.16 | Helped |
| Add ego IDs to reverse message passing and port numbering (ablation) | GIN · Synthetic scatter-gather | minority-class F1: 67.84 -> 97.42 | Helped |
| Add ego IDs alone (ablation) | GIN · Synthetic directed 6-cycle | minority-class F1: 48.59 -> 45.42 | No clear effect |
| Add reverse message passing, port numbering, and ego IDs (ablation) | GIN · AML Small HI | minority-class F1: 28.70 -> 57.15 | Helped |
| Add reverse message passing and port numbering (ablation) | GIN · AML Small HI | minority-class F1: 28.70 -> 56.85 | Helped |
| Add ego IDs to reverse message passing and port numbering (ablation) | GIN · AML Small HI | minority-class F1: 56.85 -> 57.15 | No clear effect |
| Add reverse message passing, port numbering, and ego IDs (ablation) | GIN · ETH | minority-class F1: 26.92 -> 42.86 | Helped |
| Add all three adaptations and edge updates to PNA (ablation) | PNA · ETH | minority-class F1: 51.49 -> 66.58 | Helped |
| Add edge updates to Multi-PNA (ablation) | PNA with all three adaptations · AML Small HI | minority-class F1: 64.59 -> 68.16 | Helped |
| Add edge updates to Multi-PNA (ablation) | PNA with all three adaptations · ETH | minority-class F1: 65.28 -> 66.58 | Helped |
Surprising findings
- Ego IDs alone do not enable 6-cycle detection; the proof in prior ID-GNN work is incorrect, and the authors give a counterexample.
- Ego IDs add little benefit on the AML and ETH financial datasets once reverse MP and port numbering are used.
Limitations
- Port numbering relies on transaction timestamps for ordering in the datasets, and the simulated AML data is synthetic.
- Lone illicit transactions not belonging to laundering patterns are hard to identify, capping scores.
- Only two GNN layers were used for AML experiments, so longer cycle detection was not evaluated there.
Experimental setup
Datasets: Synthetic random circulant graph pattern detection IBM AML simulated transaction datasets (Small/Medium, HI/LI) Ethereum phishing transaction network (Kaggle, enhanced with Ethereum ETL) Chameleon Squirrel Arxiv-Year
Benchmarks: Synthetic subgraph detection tasks AML Small HI AML Small LI AML Medium HI AML Medium LI ETH phishing
Metrics: minority class F1
Baselines: GIN GAT PNA GIN+EU R-GCN XGBoost+GFs LightGBM+GFs ID-GNN (GIN+EgoIDs) CPNGNN (GIN+Ports)
Builds on: GIN port numbering ego IDs (ID-GNN) reverse message passing (relational GNN) edge updates
Closest papers by meaning
- Partitioning Message Passing for Graph Fraud Detection (ICLR 2024 · similarity 0.88)
- DiG-In-GNN: Discriminative Feature Guided GNN-Based Fraud Detector against Inconsistencies in Multi-Relation Fraud Graph (AAAI 2024 · similarity 0.88)
- Unveiling the Threat of Fraud Gangs to Graph Neural Networks: Multi-Target Graph Injection Attacks Against GNN-Based Fraud Detectors (AAAI 2025 · similarity 0.87)
- A Flexible, Equivariant Framework for Subgraph GNNs via Graph Products and Graph Coarsening (NeurIPS 2024 · similarity 0.87)
- Can Graph Neural Networks Expose Training Data Properties? An Efficient Risk Assessment Approach (NeurIPS 2024 · similarity 0.86)
- Dynamic Neighborhood Modeling via Node-Subgraph Contrastive Learning for Graph-Based Fraud Detection (AAAI 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.