Hypergraph Isomorphism Computation

作者：Yifan Feng, Jiashu Han, Shihui Ying, Yue Gao · 发表于：IEEE Transactions on Pattern Analysis and Machine Intelligence · 年份：2024 · DOI：10.1109/tpami.2024.3353199 · 被引用次数：15 · 研究领域：Computational Drug Discovery Methods、Bioinformatics and Genomic Networks、Advanced Graph Neural Networks

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 (Hypergraph WL Subtree Kernel) and Hypergraph Weisfeiler-Lehamn Hyperedge Kernel (Hypergraph WL Hyperedge Kernel). The Hypergraph WL Subtree Kernel counts different types of rooted subtrees and generates ...