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.

本文提出了超图 Weisfiler-Lehman 测试算法，以解决超图同构测试问题，并基于该算法提出了一般的超图 Weisfieler-Lehman 核框架。大量实验证明，所提方法在处理复杂超图结构时比其他基于核的方法快 80 倍以上，显著提升了超图分类任务的效果。