One-sentence Summary

Researchers from Peking University and Beijing Academy of Artificial Intelligence introduce homomorphism expressivity, a quantitative framework that measures GNN expressiveness by counting graphs under homomorphism, overcoming the coarse and qualitative limitations of the Weisfeiler-Lehman hierarchy and unifying expressivity comparisons across both invariant and equivariant architectures.

Key Contributions

• Homomorphism expressivity is introduced as a quantitative framework for assessing Graph Neural Networks by measuring their ability to count graphs under homomorphism, providing complete expressivity comparisons beyond the qualitative Weisfeiler-Lehman hierarchy.

• Exact homomorphism expressivity descriptions are derived for four prominent GNN families in invariant and equivariant settings, establishing model hierarchies, graph, node, and edge-level subgraph counting capabilities, and resolving several open questions.

• Extensive synthetic and real-world experiments support the theoretical results and show that empirical GNN performance correlates with the homomorphism expressivity metric.

Introduction

Graph neural networks are widely used for graph-structured data, but their ability to distinguish different graph structures is often limited. A common way to measure this limitation is the Weisfeiler-Lehman hierarchy, especially the 1-WL bound for message-passing GNNs. However, this yardstick is too coarse for practical models: higher-order methods can be expensive, and 1-WL-based proof results may rely on small example graphs and fail to explain real-world performance. The authors leverage homomorphism counting to study which graph substructures a GNN can encode, and they give precise descriptions of the expressive power of MPNNs, Subgraph GNNs, Local GNNs, and Folklore-type GNNs, along with extensions to node-level, edge-level, and higher-order variants.

Method

The method establishes a unified analytical framework for measuring the expressive power of graph neural network architectures through homomorphism counting. For a graph representation model $M$M with representation $\chi_G^M(\cdot)$χGM​(⋅), the core idea is to characterize exactly which substructures are invisible to the model. A graph family $\mathcal{F}^M$FM is defined as a maximal family of labeled graphs such that two graphs receive the same representation if and only if all homomorphism counts from graphs in $\mathcal{F}^M$FM are identical. Formally, the equivalence condition is written as:

Maximality means that if a graph $F$F is outside $\mathcal{F}^M$FM, there exist graphs $G$G and $H$H with identical representations under $M$M but different homomorphism counts from $F$F. This makes $\mathcal{F}^M$FM a complete quantitative expressivity measure. Comparing two models $M_1$M1​ and $M_2$M2​ reduces to comparing families: if $\mathcal{F}^{M_2}\subsetneq \mathcal{F}^{M_1}$FM2​⊊FM1​, then $M_1$M1​ is strictly more expressive, and the gap is given by the family difference $\mathcal{F}^{M_1}\setminus \mathcal{F}^{M_2}$FM1​∖FM2​.

The central module for deriving these families is a nested ear decomposition framework. For a graph, a decomposition partitions the edge set into simple paths called ears. Initial ears correspond to disjoint starting paths for connected components. Later ears must be nested on earlier ears, meaning one or both endpoints of a new ear attach to an earlier ear, while the interior vertices are new. When both endpoints attach to the same parent ear, the corresponding subpath in the parent ear defines a nested interval. The global structure can be viewed as a forest of ears, where each ear has a parent ear through its nesting relation. Variants of this structure correspond to different model classes:

• Endpoint-shared nested ear decomposition requires all ears with nonempty nested intervals to share one endpoint.
• Strong nested ear decomposition requires child intervals of the same parent ear to be nested by inclusion.
• Almost-strong nested ear decomposition weakens the condition by considering only child intervals of length greater than one.

The organization of ears, parent relationships, and nested intervals is illustrated below.

Using these decomposition variants, the framework gives exact characterizations for major GNN architectures. MPNNs can count forests, Subgraph GNNs correspond to graphs admitting an endpoint-shared nested ear decomposition, Local 2-GNNs correspond to strong nested ear decompositions, Local 2-FGNNs correspond to almost-strong nested ear decompositions, and 2-FGNNs correspond to general nested ear decompositions. An equivalent description for Subgraph GNNs is that a graph belongs to its expressive family if deleting one suitable vertex leaves a forest.

The proof pipeline behind the characterization is itself a modular method. First, an unfolding-tree perspective identifies graph structures whose homomorphism counts determine the model representation, yielding a lower-bound family based on tree decomposition. Second, the decomposition characterization is translated into the nested ear decomposition language, providing a compact description that aligns with practical GNN operations. Third, maximality is shown by constructing graph pairs that remain indistinguishable to the model but differ in homomorphism counts for excluded structures, using connections among tree decomposition, pebble games, and specially constructed indistinguishable graph families.

The framework also extends to node-level and edge-level expressivity. For node-level analysis, the relevant family consists of connected rooted graphs $F^w$Fw, where one vertex in $F$F is marked and compared against a vertex in the input graph. The representation equivalence becomes

For MPNNs, the node-level family is trees. For Subgraph GNNs, a rooted graph is expressible when removing the root leaves a forest. For 2-FGNN-like models, the root must be an endpoint of the first ear in a suitable nested ear decomposition, and the edge-level variant marks two vertices and corresponds to endpoints of the first ear.

The method generalizes naturally to higher-order GNN families. Subgraph $k$k-GNNs are characterized by allowing the removal of up to $k$k vertices so that the remaining graph is a forest. Local $k$k-GNNs require a higher-order analogue of nested ear decomposition. A $k$k-order ear is formed from a small core graph of at most $k$k vertices together with $k$k paths connecting that core to external endpoints. Nested intervals and strong nesting conditions are then defined over these higher-order ears. The shape of these higher-order building blocks and their nested interval structure is shown below.

With these tools, the framework also yields a complete qualitative hierarchy. The base families satisfy strict inclusions:

Higher-order variants expand the picture into an infinite hierarchy. Subgraph $k$k-GNNs gain expressivity with $k$k, Local $k$k-GNNs gain expressivity with $k$k, and Local $(k+1)$(k+1)-GNNs lie between $k$k-FWL and $(k+1)$(k+1)-FWL. The expressive power of Subgraph $k$k-GNNs is generally incomparable with $k$k-FWL when $k>1$k>1, but it is contained within $(k+1)$(k+1)-FWL. The resulting architecture hierarchy is summarized below.

A major application of the framework is subgraph counting. Subgraph counts are not direct homomorphism counts, but they can be expressed as linear combinations of homomorphism counts over homomorphic images of the target pattern. Given a pattern $F$F, let $\mathsf{Spasm}(F)$Spasm(F) denote its homomorphic images, and let $\mathsf{Spasm}^{\neq}(F)$Spasm=(F) be a maximal set of pairwise non-isomorphic images. Then for any graph $G$G,

where $\alpha(F,\tilde{F})$α(F,F~) is a nonzero constant depending only on $F$F and $\tilde{F}$F~, not on $G$G. Therefore, a model can subgraph-count $F$F whenever every homomorphic image $\tilde{F}\in\mathsf{Spasm}(F)$F~∈Spasm(F) lies in its homomorphism expressivity family. Conversely, if some homomorphic image is outside the family, a pair of graphs can be constructed where the model representations agree but the subgraph counts differ. This gives a complete counting criterion at graph, node, and edge levels. The homomorphic-image decomposition for cyclic patterns is illustrated below.

The same characterization also connects to polynomial expressivity. Membership in $\mathcal{F}^M$FM or $\mathcal{F}_{\mathfrak{n}}^M$FnM​ and $\mathcal{F}_{\mathfrak{e}}^M$FeM​ determines whether invariant or equivariant graph polynomials associated with patterns or rooted patterns can be computed by the model. This turns the nested ear decomposition framework into a practical tool for reasoning about which structural polynomials are available to different architectures, including standard message passing, subgraph-based, local higher-order, and global higher-order variants.

Experiment

The experiments evaluate MPNN, Subgraph GNN, Local 2‑GNN, and Local 2‑FGNN under matched GIN-based designs to test the proposed homomorphism expressivity theory on synthetic substructure counting, cycle counting, and real-world graph benchmarks. The results show that model capability broadly follows the theoretical hierarchy, with Local 2‑FGNN consistently encoding more structures, counting diverse cycles more effectively, and achieving the strongest performance on practical datasets. Overall, the findings support the conclusion that stronger homomorphism expressivity translates into measurable advantages in both controlled and applied graph learning tasks.

The example characterizes which cycles and paths different GNN architectures can count at graph, node, and edge levels. More expressive models broaden the class of countable structures, with MPNN showing the strongest limitations and Local 2-(F)GNN models showing stronger cycle counting power. MPNN can count only very short simple paths and no cycles at the shown levels Subgraph GNNs and Local 2-(F)GNN models expand cycle and path counting capacity, with Local 2-(F)GNN models consistent with the strongest practical cycle counting performance

The results show that models with stronger local subgraph processing generally achieve lower normalized test error when counting homomorphism information. Local 2-FGNN is consistently accurate across graph-level, node-level, and edge-level tasks, while MPNN fails to capture any tested substructure. Subgraph GNN performs well on some cases but is less stable than Local 2-GNN and Local 2-FGNN, especially on harder substructures. Local 2-FGNN maintains low error across all tested homomorphism counting tasks. MPNN shows substantially worse performance than the subgraph-based models. Local 2-GNN improves over Subgraph GNN and provides more consistent low errors. Performance trends match the expected expressivity ordering among the compared GNN models.

The real-world benchmark results show that models with stronger theoretical expressivity generally achieve better performance on chemical graph tasks. Across the evaluated GNN variants, performance improves as the architecture moves from MPNN to Subgraph GNN and further to Local 2-GNN. Local 2-FGNN attains the best results on all reported tasks, indicating that its expressivity advantage can translate into practical gains. Expressiveness gains correlate with lower benchmark error on ZINC and Alchemy tasks. Local 2-FGNN consistently outperforms MPNN, Subgraph GNN, and Local 2-GNN.

Cycle-counting results show a clear expressive hierarchy among the compared GNN architectures when model size and training budget are matched. MPNN has the largest errors and cannot count edge-level cycles reliably, while Subgraph GNN improves substantially but still struggles with several longer and chordal cycles. Local 2-GNN and Local 2-FGNN achieve consistently lower errors, with Local 2-FGNN showing the strongest overall performance across graph, node, and edge levels. MPNN fails to count cycles effectively at all levels, especially at edge level. Local 2-FGNN achieves the best or near-best cycle counting errors despite comparable computational cost.

The experiments compare GNN architectures across synthetic cycle and path counting, homomorphism counting, and chemical benchmark tasks under matched model size and training budget. They validate that stronger local subgraph processing expands the class of countable structures and improves practical performance. MPNN is the most limited, while Subgraph GNN offers partial gains, and Local 2 GNN and especially Local 2 FGNN consistently count more complex cycles and paths with lower errors. These results show that theoretical expressivity translates into more accurate and stable performance at the graph, node, and edge levels.