arrow
返回

Hypergraph Isomorphism Computation

delete2024-01-01
delete0
delete
OA
AI
Y
Yifan Feng
J
Jiashu Han
S
Shihui Ying
Y
Yue Gao
DOI:10.1109/tpami.2024.3353199delete
delete原文链接
delete分享
delete收藏
查看原文
摘要

摘要

En 中文
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 the final feature vector for a given hypergraph by comparing the number of different types of rooted subtrees. The Hypergraph WL Hyperedge Kernel is developed to process hypergraphs with more degrees of hyperedges, which counts the vertex labels that are connected by each hyperedge to generate the feature vector. Mathematically, we prove the proposed Hypergraph WL Subtree Kernel can degenerate into the typical Graph Weisfeiler-Lehman Subtree Kernel when dealing with low-order graph structures. 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 graph classification datasets indicate that the Hypergraph WL Subtree Kernel can achieve the same performance compared with the classical Graph Weisfeiler-Lehman Subtree Kernel. 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. This significant speed advantage highlights the great potential of our methods in real-world applications.
AI总结

AI总结

对已上传原文的论文进行重点信息的提取,主要内容包括:简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。

期刊

IEEE Transactions on Pattern Analysis and Machine Intelligence 封面图
IEEE Transactions on Pattern Analysis and Machine Intelligence
IF:
18.6
论文数:
2.9K
被引数:
10.9W

机构

上海大学 封面图
上海大学
学者数:
3.3K
论文数: 1.1K
被引数: 2.1W
清华大学 封面图
清华大学
学者数:
1.1W
论文数: 4.0K
被引数: 9.9W
引用论文

引用论文

err分享
err收藏
Information network or social network?
err2014-04-07
err0
PREAI
errSeth A. Myers; Aneesh Sharma; Pankaj Gupta; Jimmy Lin
err分享
err收藏
PROTEIN STRUCTURE: INSIGHTS FROM GRAPH THEORY
err2012-01-25
err0
PREAI
errSARASWATHI VISHVESHWARA; K. V. BRINDA; N. KANNAN
err分享
err收藏
err分享
err收藏
Knowledge Graph Completion: A Review
err2020-01-01
err169
errOAAI
errChen, Zhe; Wang, Yuehan; Zhao, Bin; Cheng, Jing; Zhao, Xin; Duan, Zongtao
err分享
err收藏
Hypergraph Neural Networks
err2019-07-17
err0
errOAAI
errYifan Feng; Haoxuan You; Zizhao Zhang; Rongrong Ji; Yue Gao
err分享
err收藏
err分享
err收藏
学者 查看更多内容