Research map / Graph learning / Graph algorithms and clustering
The Map Equation Goes Neural: Mapping Network Flows with Graph Neural Networks
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.
Adapts the map equation community-detection objective into a differentiable tensor form so any (graph) neural network can be trained end-to-end with gradient descent to find communities (Neuromap).
Problem
Community detection with the map equation has relied on custom search algorithms (Infomap) and cannot easily use node features or deep learning, while deep graph clustering methods tend to overfit and report too many communities.
Approach
Express the map equation codelength as a differentiable function of a soft cluster assignment matrix S = softmax(GNN(A, X)) using flow matrix pooling C = S^T F S, so any neural architecture can be optimised with gradient descent; the MDL objective selects the number of clusters automatically up to a maximum s.
Key results
- On synthetic LFR networks, Neuromap with SAGE outperforms deep graph clustering baselines in most settings and detects close to the ground-truth number of communities, while baselines overfit with many more communities.
- On ten real-world datasets, Neuromap and NOCD are among the best performers in seven cases, e.g. Neuromap MLP achieves 78.1% AMI on Coauthor CS.
- Neuromap significantly outperforms Infomap in AMI on most real datasets when node features are used, while detecting far fewer communities.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Cora | AMI: 46.1 ± 2.0 vs 46.1 ± 1.1; p = 0.92 | No clear effect |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · CiteSeer | AMI: 23.1 ± 1.2 vs 34.8 ± 0.9; p = 3.3e^{-35} | Hurt |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · PubMed | AMI: 24.6 ± 1.7 vs 23.7 ± 1.5; p = 0.05 | No clear effect |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Amazon Computer (PC) | AMI: 52.1 ± 2.3 vs 51.9 ± 1.9; p = 0.69 | No clear effect |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Amazon Photo | AMI: 65.0 ± 3.8 vs 63.7 ± 1.6; p = 0.14 | No clear effect |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Coauthor CS | AMI: 78.1 ± 2.0 vs 73.9 ± 1.7; p = 4.4e^{-10} | Helped |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Coauthor Physics | AMI: 56.5 ± 1.2 vs 62.4 ± 3.6; p = 1.5e^{-08} | Hurt |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Cora ML | AMI: 39.1 ± 2.1 vs 46.5 ± 1.4; p = 5.7e^{-18} | Hurt |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · Wiki CS | AMI: 44.8 ± 2.2 vs 44.2 ± 0.6; p = 0.23 | No clear effect |
| Use Neuromap instead of the best baseline | Neuromap and strongest baseline · ogb-arxiv | AMI: 43.6 ± 1.0 vs 43.8 ± 0.4; p = 0.38 | No clear effect |
| Use SAGE architecture rather than other tested architectures (ablation) | Neuromap · Synthetic LFR networks | AMI | Helped |
| Use node features in Neuromap rather than topology alone as in Infomap | Neuromap · Real-world networks | AMI | Helped |
Surprising findings
- Simple non-GNN architectures (linear layer, MLP) perform competitively with GNNs on several real-world datasets, suggesting the map equation captures global flow information.
- Limiting the maximum number of communities to the true number often diminishes Neuromap's performance, contrary to the baselines which benefit.
Limitations
- Only first-order networks with two-level community structure are considered; higher-order and multi-level communities are left for future work.
- Overlapping community evaluation is limited to a single small synthetic network.
- Performance depends strongly on the chosen neural architecture, and the link between architecture and clustering performance is not understood.
Experimental setup
Datasets: LFR benchmark networks Cora CiteSeer PubMed Amazon Computer Amazon Photo Coauthor CS Coauthor Physics Cora ML Wiki CS ogb-arxiv
Benchmarks: LFR synthetic networks Cora CiteSeer PubMed Amazon Computer Amazon Photo Coauthor CS Coauthor Physics Cora ML Wiki CS ogb-arxiv
Metrics: adjusted mutual information (AMI) number of detected communities codelength
Baselines: Infomap DMoN NOCD DiffPool MinCut Ortho
Builds on: map equation Infomap DMoN smart teleportation
Closest papers by meaning
- Supervised Community Detection with Line Graph Neural Networks (ICLR 2019 · similarity 0.88)
- Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis (AAAI 2024 · similarity 0.87)
- DGCLUSTER: A Neural Framework for Attributed Graph Clustering via Modularity Maximization (AAAI 2024 · similarity 0.86)
- Community Detection Guarantees using Embeddings Learned by Node2Vec (NeurIPS 2024 · similarity 0.86)
- Learning on Large Graphs using Intersecting Communities (NeurIPS 2024 · similarity 0.86)
- LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering (ICML 2024 · 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.