Color Refinement, Homomorphisms, and Hypergraphs

Jan Böker

Abstract

Recent results show that the structural similarity of graphs can be characterized by counting homomorphisms to them: the Tree Theorem states that the well-known color-refinement algorithm does not distinguish two graphs G and H if and only if, for every tree T, the number of homomorphisms Hom(T,G) from T to G is equal to the corresponding number Hom(T,H) from T to H (Dell, Grohe, Rattan 2018). We show how this approach transfers to hypergraphs by introducing a generalization of color refinement. We prove that it does not distinguish two hypergraphs G and H if and only if, for every connected Berge-acyclic hypergraph B, we have Hom(B,G) = Hom(B,H). To this end, we show how homomorphisms of hypergraphs and of a colored variant of their incidence graphs are related to each other. This reduces the above statement to one about vertex-colored graphs.

Introduction

In the study of graph theory and machine learning, characterizing structural similarity is a fundamental challenge. This paper, authored by Jan Böker, provides a theoretical bridge between hypergraph symmetry and counting homomorphisms. It generalizes a celebrated result in graph theory—the "Tree Theorem"—to the more complex world of hypergraphs. The core finding is that a generalized "color refinement" algorithm for hypergraphs is exactly as powerful as counting homomorphisms from Berge-acyclic hypergraphs.

Background: The Graph Isomorphism Problem

Determining if two graphs are identical, known as the Graph Isomorphism problem, is computationally demanding. Researchers often rely on heuristics like color refinement (the 1-dimensional Weisfeiler-Leman algorithm). This algorithm iteratively colors vertices based on the colors of their neighbors until the coloring stabilizes. If two graphs result in different color distributions, they are guaranteed to be non-isomorphic.

A breakthrough in 2018 established that color refinement fails to distinguish two graphs if and only if they share the same number of homomorphisms from every possible tree. However, many real-world datasets, such as chemical reactions or social networks, are better represented as hypergraphs, where edges can connect more than two vertices. This research addresses whether a similar "Tree Theorem" exists for hypergraphs and identifies the appropriate definition of a "tree" in this context.

Methodology: Reductions and Incidence Graphs

The author employs a strategy of reduction to characterize hypergraph similarity.

Hypergraph Color Refinement

The paper introduces a specific version of color refinement for hypergraphs. A vertex's color is updated by examining the edges it belongs to, where each edge's "color" is a multiset of the colors of its constituent vertices.

Illustration of hypergraph color refinement steps for vertices $v_1, v_2, v_3$.

The Incidence Graph Bridge

To simplify the proof, hypergraphs are mapped to incidence graphs—bipartite graphs where one set of nodes represents the original vertices and the other represents the hyperedges.

An incidence graph representation of a hypergraph with vertices $v_i$ and hyperedges $e_j$.

By coloring the nodes in the incidence graph to distinguish "vertex-nodes" from "edge-nodes," the author proves that hypergraph color refinement is equivalent to standard color refinement on these colored incidence graphs. Furthermore, the author defines "incidence homomorphisms," a relaxed version where the mapping of vertices in an edge only needs to be a subset of the target edge, facilitating a mathematical alignment between the hypergraph and its incidence graph.

Key Insights and Results

The central contribution is the identification of Berge-acyclic hypergraphs as the natural generalization of trees. A hypergraph is Berge-acyclic if its incidence graph is a tree.

  • Theorem 1 (The Main Result): Two hypergraphs $G$ and $H$ are not distinguished by hypergraph color refinement if and only if for every connected Berge-acyclic hypergraph $B$, the number of homomorphisms from $B$ to $G$ equals the number of homomorphisms from $B$ to $H$.
  • Equivalence of Heuristics: The paper formally proves that color refinement on a hypergraph is equivalent to color refinement on its colored incidence graph.
  • The Power of Reduction: By showing that hypergraph homomorphisms can be counted via colored incidence graphs, the author "imports" the existing Tree Theorem for graphs to the hypergraph domain.

Limitations and Future Work

While this work provides a robust framework for 1-dimensional color refinement, generalizing to higher-order symmetries, such as $k$-dimensional Weisfeiler-Leman ($k$-WL) algorithms, remains non-trivial. Additionally, the author points out that the treewidth of an incidence graph may not be a meaningful notion for hypergraphs because merging vertices can increase treewidth. Finding a version of the theorem relating to a hypergraph's intrinsic treewidth remains an open challenge.

Summary updated

Abstract

Recent results show that the structural similarity of graphs can be characterized by counting homomorphisms to them: the Tree Theorem states that the well-known color-refinement algorithm does not distinguish two graphs G and H if and only if, for every tree T, the number of homomorphisms Hom(T,G) from T to G is equal to the corresponding number Hom(T,H) from T to H (Dell, Grohe, Rattan 2018). We show how this approach transfers to hypergraphs by introducing a generalization of color refinement. We prove that it does not distinguish two hypergraphs G and H if and only if, for every connected Berge-acyclic hypergraph B, we have Hom(B,G) = Hom(B,H). To this end, we show how homomorphisms of hypergraphs and of a colored variant of their incidence graphs are related to each other. This reduces the above statement to one about vertex-colored graphs.
BibTeX
@inproceedings{boker2019color,
  author = {Jan Böker},
  title = {{Color Refinement, Homomorphisms, and Hypergraphs}},
  booktitle = {WG},
  year = {2019},
  url = {https://openreview.net/forum?id=dzAhOEvhEf},
}
Figure