# Hypergraph Isomorphism Computation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 53 references that are in the map.
- First posted on arXiv 26 Jul 2023.

## Builds on (most cited first, 10 of 10)

- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hypergraph Neural Networks](https://mlsanity.com/paper/1809.09401/) (2018)
- [Hypergraph Convolution and Hypergraph Attention](https://mlsanity.com/paper/1901.08150/) (2019)
- [Heterogeneous Hypergraph Embedding for Graph Classification](https://mlsanity.com/paper/2010.10728/) (2020)
- [Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation](https://mlsanity.com/paper/2207.05584/) (2022)
- [Hyperbolic Hypergraphs for Sequential Recommendation](https://mlsanity.com/paper/2108.08134/) (2021)

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

- [Beyond Graphs: Can Large Language Models Comprehend Hypergraphs?](https://mlsanity.com/paper/2410.10083/) (2024)
- [DHG-Bench: A Comprehensive Benchmark for Deep Hypergraph Learning](https://mlsanity.com/paper/2508.12244/) (2025)
- [Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking](https://mlsanity.com/paper/2402.11339/) (2024)
- [Weisfeiler and Lehman Go Categorical](https://mlsanity.com/paper/2602.06787/) (2026)
- [HWL-HIN: A Hypergraph-Level Hypergraph Isomorphism Network as Powerful as the Hypergraph Weisfeiler-Lehman Test with Application to Higher-Order Network Robustness](https://mlsanity.com/paper/2512.22014/) (2025)
- [Weisfeiler Lehman Test on Combinatorial Complexes: Generalized Expressive Power of Topological Neural Networks](https://mlsanity.com/paper/2605.00725/) (2026)
- [Hypergraph as Language](https://mlsanity.com/paper/2605.21858/) (2026)
- [Beyond Convolution: Advancing Hypergraph Neural Networks with Hypergraph U-Nets](https://mlsanity.com/paper/2606.09051/) (2026)
- [Instruction Set and Language for Hypergraphs](https://mlsanity.com/paper/2607.10194/) (2026)
- [Hyper-Fold: Exploring the Expressive Limit of Sequence-Geometry Learning for Proteins via Hypergraph Modeling](https://mlsanity.com/paper/2608.29207/) (2026)

## Abstract (arXiv)

The isomorphism problem is a fundamental problem in network analysis, which involves capturing both low-order and high-order structural information. In terms of extracting low-order structural information, graph isomorphism algorithms analyze the structural equivalence to reduce the solver space dimension, which demonstrates its power in many applications, such as protein design, chemical pathways, and community detection. For the more commonly occurring high-order relationships in real-life scenarios, the problem of hypergraph isomorphism, which effectively captures these high-order structural relationships, cannot be straightforwardly addressed using graph isomorphism methods. Besides, the existing hypergraph kernel methods may suffer from high memory consumption or inaccurate sub-structure identification, thus yielding sub-optimal performance. In this paper, to address the abovementioned problems, we first propose the hypergraph Weisfiler-Lehman test algorithm for the hypergraph isomorphism test problem by generalizing the Weisfiler-Lehman test algorithm from graphs to hypergraphs. Secondly, based on the presented algorithm, we propose a general hypergraph Weisfieler-Lehman kernel framework and implement two instances, which are Hypergraph Weisfeiler-Lehamn Subtree Kernel and Hypergraph Weisfeiler-Lehamn Hyperedge Kernel. In order to fulfill our research objectives, a comprehensive set of experiments was meticulously designed, including seven graph classification datasets and 12 hypergraph classification datasets. Results on hypergraph classification datasets show significant improvements compared to other typical kernel-based methods, which demonstrates the effectiveness of the proposed methods. In our evaluation, we found that our proposed methods outperform the second-best method in terms of runtime, running over 80 times faster when handling complex hypergraph structures.