On the Substructure Countability of Graph Neural Networks
- 23 November 2022
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 35 (11) , 11681-11692
Abstract
With the empirical success of Graph Neural Networks (GNNs) on graph-related tasks, it is intriguing to investigate their theoretical power on these tasks. In this paper, we focus on GNNs' theoretical power on substructure counting, a fundamental yet challenging task in many applications. Previous works have proven that the 2-dimensional Weisfeiler-Leman algorithm (2-WL) equivalent GNNs can only count limited substructures. However, the substructure counting ability of theoretically more powerful and computationally tractable GNNs remains unclear. In this paper, we study conditions for substructures to be theoretically countable by k-WL equivalent GNNs, and then focus on 3-WL equivalent ones, which are currently the most theoretically powerful instances with practical computational cost. Further, we propose an algorithm to determine the countability of substructures for 3-WL equivalent GNNs. Our results reveal that 3-WL equivalent GNNs can count considerably more substructures than 2-WL equivalent ones. However, the proportion of countable patterns and prediction performance decrease as the pattern size increases. Therefore, we propose a Layer Permutation Pooling (LPP) model for better substructure counting performance. LPP first decomposes the data graph into subgraphs. Then we propose a layer permutation scheme to represent each decomposed subgraph as a set of matrices. Finally, LPP utilizes a neural network to conduct predictions on matrices. We compare LPP with several state-of-the-art GNNs on various datasets. Experimental results show that LPP outperforms baselines by 84% on average with the RMSE metric.Keywords
Funding Information
- National Natural Science Foundation of China (61971283)
- Shanghai Municipal Science and Technology Major Project (2021SHZDZX0102)
- Ministry of Education - Singapore
- Academic Research Fund Tier 2 (MOE2019-T2-2-065)
- China Scholarship Council
- Singapore Management University
This publication has 36 references indexed in Scilit:
- Enumeration of 166 Billion Organic Small Molecules in the Chemical Universe Database GDB-17Journal of Chemical Information and Modeling, 2012
- Preventing bad plans by bounding the impact of cardinality estimation errorsProceedings of the VLDB Endowment, 2009
- Graphs-at-a-time2008
- Protein function prediction via graph kernelsBioinformatics, 2005
- Graph Minors. XX. Wagner's conjectureJournal of Combinatorial Theory, Series B, 2004
- A (sub)graph isomorphism algorithm for matching large graphsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Supervised neural networks for the classification of structuresIEEE Transactions on Neural Networks, 1997
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992
- Forbidden minors characterization of partial 3-treesDiscrete Mathematics, 1990
- Multilayer feedforward networks are universal approximatorsNeural Networks, 1989