2024 | Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, Liwei Wang
This paper introduces a novel framework for quantitatively analyzing the expressive power of Graph Neural Networks (GNNs), addressing the limitations of the Weisfeiler-Lehman (WL) hierarchy. The framework defines homomorphism expressivity, which measures a GNN's ability to count graphs under homomorphism. This provides a complete and practical assessment of GNN expressiveness, enabling direct comparisons between models and revealing their concrete capabilities, such as subgraph counting. The framework is applied to four classes of prominent GNNs, deriving simple, unified, and elegant descriptions of their homomorphism expressivity for both invariant and equivariant settings. The results unify different subareas in the GNN community, answer open questions, and provide novel insights into previous work. Empirical experiments on synthetic and real-world tasks validate the framework, showing that the practical performance of GNN models aligns well with the proposed metric. The framework is extended to node-level and edge-level expressivity for equivariant GNNs and to higher-order GNNs, demonstrating its flexibility and applicability. The results provide a systematic way to compare the expressive power of GNNs, analyze their subgraph counting capabilities, and understand their polynomial expressivity. The framework also has implications for subgraph counting and polynomial expressivity, offering a new toolbox for studying these aspects. The experiments show that the proposed models perform well in various tasks, including cycle counting and real-world benchmarks. The paper concludes that the homomorphism expressivity framework provides a valuable tool for systematically and quantitatively studying the expressive power of GNNs.This paper introduces a novel framework for quantitatively analyzing the expressive power of Graph Neural Networks (GNNs), addressing the limitations of the Weisfeiler-Lehman (WL) hierarchy. The framework defines homomorphism expressivity, which measures a GNN's ability to count graphs under homomorphism. This provides a complete and practical assessment of GNN expressiveness, enabling direct comparisons between models and revealing their concrete capabilities, such as subgraph counting. The framework is applied to four classes of prominent GNNs, deriving simple, unified, and elegant descriptions of their homomorphism expressivity for both invariant and equivariant settings. The results unify different subareas in the GNN community, answer open questions, and provide novel insights into previous work. Empirical experiments on synthetic and real-world tasks validate the framework, showing that the practical performance of GNN models aligns well with the proposed metric. The framework is extended to node-level and edge-level expressivity for equivariant GNNs and to higher-order GNNs, demonstrating its flexibility and applicability. The results provide a systematic way to compare the expressive power of GNNs, analyze their subgraph counting capabilities, and understand their polynomial expressivity. The framework also has implications for subgraph counting and polynomial expressivity, offering a new toolbox for studying these aspects. The experiments show that the proposed models perform well in various tasks, including cycle counting and real-world benchmarks. The paper concludes that the homomorphism expressivity framework provides a valuable tool for systematically and quantitatively studying the expressive power of GNNs.