Research map / Graph learning / GNN architectures
Improved Expressivity of Hypergraph Neural Networks through High-Dimensional Generalized Weisfeiler-Leman Algorithms
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.
Proposes high-dimensional generalized Weisfeiler-Leman (k-GWL) tests for hypergraphs, proves hierarchy and reduction to k-WL on graphs, and builds k-HNNs that are upper-bounded by k-GWL and outperform prior HNNs on hypergraph classification.
Problem
Hypergraph isomorphism tests and hypergraph neural networks are limited to the expressive power of 1-dimensional generalized WL (1-GWL), with no systematic higher-order analogue of k-WL for hypergraphs.
Approach
Generalize k-WL to hypergraphs by coloring k-tuples via isomorphism types of induced sub-hypergraphs (after deleting singleton hyperedges), building folklore and oblivious k-tuple hypergraphs, and running 1-GWL on them; the resulting k-GWL reduces to k-WL on simple graphs and yields a strict expressivity hierarchy, which is used to design k-HNNs with local k-set neighborhoods.
Key results
- On Steam-Player, 2-FHNN reaches 67.53% accuracy, about 6% above the runner-up AllSetTransformer (61.87%).
- 3-HNN with vertex sampling (size 10) reaches 57.50% on IMDB-WRI-GENRE versus 54.09% for AllSetTransformer, per the reported table.
- Removing singleton-hyperedge deletion (the -S variants) drops 2-FHNN on IMDB-DIR-FORM from 68.11% to 58.55%.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use 2-FHNN instead of the runner-up baseline | Steam-Player classification · Steam-Player | accuracy: 61.87±1.87 -> 67.53±1.23 | Helped |
| use 2-FHNN instead of 2-OHNN | IMDB-DIR-FORM classification · IMDB-DIR-FORM | accuracy: 67.25±2.35 -> 68.11±2.46 | Mixed |
| use 2-OHNN instead of 2-FHNN | IMDB-DIR-GENRE classification · IMDB-DIR-GENRE | accuracy: 78.52±1.07 -> 79.75±1.14 | Helped |
| use 2-FHNN instead of 2-OHNN | IMDB-WRI-FORM classification · IMDB-WRI-FORM | accuracy: 55.35±3.74 -> 55.36±3.30 | No clear effect |
| use 3-OHNN with vertex sample size 10 instead of the runner-up baseline | IMDB-WRI-GENRE classification · IMDB-WRI-GENRE | accuracy: 54.09±2.41 -> 57.50±3.55 | Helped |
| use 2-OHNN instead of AllSetTransformer | Twitter-Friend classification · Twitter-Friend | accuracy: 64.03±1.34 -> 64.12±1.30 | No clear effect |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · IMDB-DIR-FORM | accuracy: 58.55±1.5 -> 68.11±2.4 | Helped |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · IMDB-DIR-GENRE | accuracy: 76.33±1.2 -> 78.52±1.0 | Helped |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · IMDB-WRI-FORM | accuracy: 53.06±2.9 -> 55.36±3.3 | Helped |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · IMDB-WRI-GENRE | accuracy: 36.38±1.5 -> 45.44±1.2 | Helped |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · Steam-Player | accuracy: 59.56±1.0 -> 67.53±1.2 | Helped |
| remove singleton hyperedges when extracting induced sub-hypergraphs (ablation) | 2-FHNN · Twitter-Friend | accuracy: 60.89±1.6 -> 62.75±2.1 | Helped |
Surprising findings
- 2-GOWL is strictly more powerful than 1-GWL, unlike the graph case where 2-OWL is equivalent to 1-WL.
- Transforming hypergraphs to graphs (star/line expansion) and applying k-WL does not match k-GWL's power.
Limitations
- Computational cost grows exponentially with k, requiring vertex sampling for k=3.
- 2-FHNN vs 2-OHNN shows mixed results across datasets, with no consistent winner.
- Vertex-label extension (k,l)-GWL is computationally impractical and only tested on a small experiment.
Experimental setup
Datasets: IMDB-DIR-FORM IMDB-DIR-GENRE IMDB-WRI-FORM IMDB-WRI-GENRE Steam-Player Twitter-Friend
Benchmarks: IMDB-DIR-FORM IMDB-DIR-GENRE IMDB-WRI-FORM IMDB-WRI-GENRE Steam-Player Twitter-Friend
Metrics: classification accuracy
Baselines: MLP HyperGCN HNHN UniGCNII AllSetTransformer ED-HNN HIC
Builds on: k-WL 1-GWL UniGNN k-IGN (k,l)-WL
Closest papers by meaning
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.89)
- Weisfeiler-Leman at the margin: When more expressivity matters (ICML 2024 · similarity 0.89)
- Beyond Graphs: Can Large Language Models Comprehend Hypergraphs? (ICLR 2025 · similarity 0.89)
- When Hypergraph Meets Heterophily: New Benchmark Datasets and Baseline (AAAI 2025 · similarity 0.89)
- Training-Free Message Passing for Learning on Hypergraphs (ICLR 2025 · similarity 0.88)
- K-hop Hypergraph Neural Network: A Comprehensive Aggregation Approach (AAAI 2025 · similarity 0.88)
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.