Reinterpreting Hypergraph Kernels: Insights Through Homomorphism Analysis

Yifan Zhang

doi:10.1109/TPAMI.2025.3608902

Reinterpreting Hypergraph Kernels: Insights Through Homomorphism Analysis

2025-09-11

0

PRE

AI

DOI：10.1109/TPAMI.2025.3608902

Original

Original request for help

Save

Abstract

En 中文

Designing expressive hypergraph kernels that can effectively capture high-order structural information is a fundamental challenge in hypergraph learning. In this paper, we propose a novel comparison framework based on hypergraph homomorphisms to evaluate and compare the expressive ability of existing hypergraph kernels. We revisit classical kernels such as Hypergraph Weisfeiler-Lehman (HG WL) and Hypergraph Rooted kernels, providing theoretical conditions under which they fail to distinguish non-isomorphic hypergraphs. Motivated by these insights, we introduce the Hypergraph Subtree-Cycle Kernel, which augments subtree-based features with cycle-based structural patterns to enhance expressiveness. We propose two variants: HG SCKernelv1 and HG SCKernelv2. Extensive experiments on five graph and ten hypergraph classification benchmarks demonstrate the superior performance of our methods, confirming the effectiveness of integrating homomorphism-guided design into hypergraph kernels.

Keywords:

Hypergraph kernel

expressive ability

hypergraph homomorphism

Weisfeiler-Lehman

cycle modeling

Reinterpreting Hypergraph Kernels: Insights Through Homomorphism Analysis

Abstract

Journal

Organization