# Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 83 references that are in the map.
- First posted on arXiv 17 Feb 2024.

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

- [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)
- [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)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [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)
- [Hypergraph Convolution and Hypergraph Attention](https://mlsanity.com/paper/1901.08150/) (2019)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [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)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [UniGNN: a Unified Framework for Graph and Hypergraph Neural Networks](https://mlsanity.com/paper/2105.00956/) (2021)
- [You are AllSet: A Multiset Function Framework for Hypergraph Neural Networks](https://mlsanity.com/paper/2106.13264/) (2021)
- [Rethinking the Expressive Power of GNNs via Graph Biconnectivity](https://mlsanity.com/paper/2301.09505/) (2023)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [HNHN: Hypergraph Networks with Hyperedge Neurons](https://mlsanity.com/paper/2006.12278/) (2020)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Subgraph Neural Networks](https://mlsanity.com/paper/2006.10538/) (2020)
- [Hyper-SAGNN: a self-attention based graph neural network for hypergraphs](https://mlsanity.com/paper/1911.02613/) (2019)
- [Contact patterns in a high school: a comparison between data collected using wearable sensors, contact diaries and friendship surveys](https://mlsanity.com/paper/1506.03645/) (2015)

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

- [TopInG: Topologically Interpretable Graph Learning via Persistent Rationale Filtration](https://mlsanity.com/paper/2510.05102/) (2025)
- [Adversarial Label Invariant Graph Data Augmentations for Out-of-Distribution Generalization](https://mlsanity.com/paper/2604.08404/) (2026)

## Abstract (arXiv)

A hypergraph consists of a set of nodes along with a collection of subsets of the nodes called hyperedges. Higher-order link prediction is the task of predicting the existence of a missing hyperedge in a hypergraph. A hyperedge representation learned for higher order link prediction is fully expressive when it does not lose distinguishing power up to an isomorphism. Many existing hypergraph representation learners, are bounded in expressive power by the Generalized Weisfeiler Lehman-1 (GWL-1) algorithm, a generalization of the Weisfeiler Lehman-1 algorithm. However, GWL-1 has limited expressive power. In fact, induced subhypergraphs with identical GWL-1 valued nodes are indistinguishable. Furthermore, message passing on hypergraphs can already be computationally expensive, especially on GPU memory. To address these limitations, we devise a preprocessing algorithm that can identify certain regular subhypergraphs exhibiting symmetry. Our preprocessing algorithm runs once with complexity the size of the input hypergraph. During training, we randomly replace subhypergraphs identified by the algorithm with covering hyperedges to break symmetry. We show that our method improves the expressivity of GWL-1. Our extensive experiments also demonstrate the effectiveness of our approach for higher-order link prediction on both graph and hypergraph datasets with negligible change in computation.