How Powerful are Hypergraph Neural Networks?

Abstract

Isomorphism recognition is crucial for analyzing complex network structures. Traditional methods like Weisfeiler-Lehman (WL) kernels and various GNNs often overlook higher-order interactions essential for practical applications. Besides, hypergraph WL kernels struggle to distinguish uniform-regular hypergraphs due to their focus on neighborhood connectivity without effectively capturing unique higher-order structures. To overcome these issues, we introduce the Hypergraph Identity-Aware Subtree (IA Subtree) Kernel, which distinguishes uniform-regular hypergraphs by considering both neighborhood connectivity and connection density. This kernel detects subtle differences in hypergraph structures via variations in Closed Paths of different lengths. Additionally, we develop two Hypergraph Neural Networks: Hypergraph Isomorphism Networks (HGIN) and Identity-Aware Hypergraph Isomorphism Networks (IA-HGIN). These models combine the strengths of the Hypergraph WL subtree kernel with advanced neural architectures, improving classification by integrating features from closed-path distributions. We also provide the first comprehensive theoretical comparison of expressive power between kernel-based methods and neural networks, confirming IA-HGIN’s superior performance. Experimental results on eight synthetic and eight real hypergraph datasets validate the effectiveness of our methods over existing State-of-the-Art approaches.