Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913532040183808 |
|---|---|
| author | Zhou, Junru Zhang, Muhan |
| author_facet | Zhou, Junru Zhang, Muhan |
| contents | The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several existing works have investigated the homomorphism counting power of certain GNN families, a simple and unified framework for analyzing the problem is absent. In this paper, we first propose \emph{generalized folklore Weisfeiler-Leman (GFWL)} algorithms as a flexible design basis for expressive GNNs, and then provide a theoretical framework to algorithmically determine the homomorphism counting power of an arbitrary class of GNN within the GFWL design space. As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_03517 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective Zhou, Junru Zhang, Muhan Machine Learning Discrete Mathematics The ability of graph neural networks (GNNs) to count homomorphisms has recently been proposed as a practical and fine-grained measure of their expressive power. Although several existing works have investigated the homomorphism counting power of certain GNN families, a simple and unified framework for analyzing the problem is absent. In this paper, we first propose \emph{generalized folklore Weisfeiler-Leman (GFWL)} algorithms as a flexible design basis for expressive GNNs, and then provide a theoretical framework to algorithmically determine the homomorphism counting power of an arbitrary class of GNN within the GFWL design space. As the considered design space is large enough to accommodate almost all known powerful GNNs, our result greatly extends all existing works, and may find its application in the automation of GNN model design. |
| title | Fine-Grained Expressive Power of Weisfeiler-Leman: A Homomorphism Counting Perspective |
| topic | Machine Learning Discrete Mathematics |
| url | https://arxiv.org/abs/2410.03517 |