Weisfeiler and Lehman Go Categorical

• URL: http://arxiv.org/abs/2602.06787v1
• Date: Fri, 06 Feb 2026 15:45:29 GMT
• Title: Weisfeiler and Lehman Go Categorical
• Authors: Seongjin Choi, Gahee Kim, Se-Young Yun,
• Abstract summary: We introduce the categorical Weisfeiler-Lehman framework, which formalizes lifting as a functorial mapping.<n>We derive Hypergraph Isomorphism Networks, a family of neural architectures where the message passing topology is strictly determined by the choice of functor.<n>We theoretically characterize the expressivity of these models, proving that both the incidence-based and symmetric simplicial approaches subsume the expressive power of the standard Hypergraph Weisfeiler-Lehman test.
• Score: 35.34196814560212
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While lifting map has significantly enhanced the expressivity of graph neural networks, extending this paradigm to hypergraphs remains fragmented. To address this, we introduce the categorical Weisfeiler-Lehman framework, which formalizes lifting as a functorial mapping from an arbitrary data category to the unifying category of graded posets. When applied to hypergraphs, this perspective allows us to systematically derive Hypergraph Isomorphism Networks, a family of neural architectures where the message passing topology is strictly determined by the choice of functor. We introduce two distinct functors from the category of hypergraphs: an incidence functor and a symmetric simplicial complex functor. While the incidence architecture structurally mirrors standard bipartite schemes, our functorial derivation enforces a richer information flow over the resulting poset, capturing complex intersection geometries often missed by existing methods. We theoretically characterize the expressivity of these models, proving that both the incidence-based and symmetric simplicial approaches subsume the expressive power of the standard Hypergraph Weisfeiler-Lehman test. Extensive experiments on real-world benchmarks validate these theoretical findings.

Related papers

• Expressive Symbolic Regression for Interpretable Models of Discrete-Time Dynamical Systems [0.0]
  Symbolic Artificial Neural Network-Trained Expressions (SymANNTEx) architecture for this task. We show that our modified SymANNTEx model properly identifies single-state maps and achieves moderate success in approximating a dual-state attractor.
  arXiv  Detail & Related papers  (2024-06-05T05:05:29Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Homomorphism Counts for Graph Neural Networks: All About That Basis [8.25219440625445]
  We argue for a more fine-grained approach, which incorporates the homomorphism counts of all structures in the basis'' of the target pattern. This yields strictly more expressive architectures without incurring any additional overhead in terms of computational complexity.
  arXiv  Detail & Related papers  (2024-02-13T16:57:06Z)
• Sheaf Hypergraph Networks [20.91851106383122]
  We introduce cellular sheaves for hypergraphs, a mathematical construction that adds extra structure to the conventional hypergraph.<n> Drawing inspiration from existing Laplacians in the literature, we develop two unique formulations of sheaf hypergraph Laplacians.<n>We employ these sheaf hypergraph Laplacians to design two categories of models: Sheaf Hypergraph Neural Networks and Sheaf Hypergraph Convolutional Networks.
  arXiv  Detail & Related papers  (2023-09-29T10:25:43Z)
• Hypergraph Isomorphism Computation [20.21325386855039]
  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. Results on hypergraph classification datasets show significant improvements compared to other typical kernel-based methods.
  arXiv  Detail & Related papers  (2023-07-26T09:39:40Z)
• P-tensors: a General Formalism for Constructing Higher Order Message Passing Networks [5.257115841810258]
  We show that higher order graph neural networks can achieve better accuracy than their standard message passing counterparts. We formalize these structures as permutation equivariant tensors, or P-tensors, and derive a basis for all linear maps between arbitrary order equivariant P-tensors.
  arXiv  Detail & Related papers  (2023-06-19T08:21:30Z)
• From Hypergraph Energy Functions to Hypergraph Neural Networks [94.88564151540459]
  We present an expressive family of parameterized, hypergraph-regularized energy functions. We then demonstrate how minimizers of these energies effectively serve as node embeddings. We draw parallels between the proposed bilevel hypergraph optimization, and existing GNN architectures in common use.
  arXiv  Detail & Related papers  (2023-06-16T04:40:59Z)
• From axioms over graphs to vectors, and back again: evaluating the properties of graph-based ontology embeddings [78.217418197549]
  One approach to generating embeddings is by introducing a set of nodes and edges for named entities and logical axioms structure. Methods that embed in graphs (graph projections) have different properties related to the type of axioms they utilize.
  arXiv  Detail & Related papers  (2023-03-29T08:21:49Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Understanding Graph Neural Networks with Generalized Geometric Scattering Transforms [67.88675386638043]
  The scattering transform is a multilayered wavelet-based deep learning architecture that acts as a model of convolutional neural networks. We introduce windowed and non-windowed geometric scattering transforms for graphs based upon a very general class of asymmetric wavelets. We show that these asymmetric graph scattering transforms have many of the same theoretical guarantees as their symmetric counterparts.
  arXiv  Detail & Related papers  (2019-11-14T17:23:06Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.