16 Jan 2024 | Bohang Zhang, Jingchu Gai, Yiheng Du, Qiwei Ye, Di He, Liwei Wang
This paper introduces a novel framework for quantitatively studying the expressiveness of Graph Neural Networks (GNNs), addressing the limitations of the traditional Weisfeiler-Lehman (WL) hierarchy. The authors propose a fundamental measure called *homomorphism expressivity*, which quantifies the ability of GNN models to count graphs under homomorphism. This measure offers a complete and practical assessment tool, enabling direct comparisons between different GNN models and understanding their concrete abilities, such as subgraph counting. The paper provides a unified and elegant description of the homomorphism expressivity for four prominent GNN classes: Message Passing GNNs (MPNNs), Subgraph GNNs, Local GNNs, and Folklore-type GNNs. The results are validated through extensive experiments on synthetic and real-world tasks, showing that the practical performance of GNN models aligns well with the proposed metric. The framework bridges different subareas in the GNN community, provides new insights into previous work, and answers several open questions.This paper introduces a novel framework for quantitatively studying the expressiveness of Graph Neural Networks (GNNs), addressing the limitations of the traditional Weisfeiler-Lehman (WL) hierarchy. The authors propose a fundamental measure called *homomorphism expressivity*, which quantifies the ability of GNN models to count graphs under homomorphism. This measure offers a complete and practical assessment tool, enabling direct comparisons between different GNN models and understanding their concrete abilities, such as subgraph counting. The paper provides a unified and elegant description of the homomorphism expressivity for four prominent GNN classes: Message Passing GNNs (MPNNs), Subgraph GNNs, Local GNNs, and Folklore-type GNNs. The results are validated through extensive experiments on synthetic and real-world tasks, showing that the practical performance of GNN models aligns well with the proposed metric. The framework bridges different subareas in the GNN community, provides new insights into previous work, and answers several open questions.