Towards Efficient and Expressive GNNs for Graph Classification via Subgraph-Aware Weisfeiler-Lehman

Zhaohui Wang, Qi Cao, Huawei Shen, Xu Bingbing, Muhan Zhang, Xueqi Cheng
Proceedings of the First Learning on Graphs Conference, PMLR 198:17:1-17:18, 2022.

Abstract

The expressive power of GNNs is upper-bounded by the Weisfeiler-Lehman (WL) test. To achieve GNNs with high expressiveness, researchers resort to subgraph-based GNNs (WL/GNN on subgraphs), deploying GNNs on subgraphs centered around each node to encode subgraphs instead of rooted subtrees like WL. However, deploying multiple GNNs on subgraphs suffers from much higher computational cost than deploying a single GNN on the whole graph, limiting its application to large-size graphs. In this paper, we propose a novel paradigm, namely Subgraph-aware WL (SaWL), to obtain graph representation that reaches subgraph-level expressiveness with a single GNN. We prove that SaWL has beyond-WL capability for graph isomorphism testing, while sharing similar runtime to WL. To generalize SaWL to graphs with continuous node features, we propose a neural version named Subgraph-aware GNN (SaGNN) to learn graph representation. Both SaWL and SaGNN are more expressive than 1-WL while having similar computational cost to 1-WL/GNN, without causing much higher complexity like other more expressive GNNs. Experimental results on several benchmark datasets demonstrate that fast SaWL and SaGNN significantly outperform competitive baseline methods on the task of graph classification, while achieving high efficiency.

Cite this Paper

BibTeX
@InProceedings{pmlr-v198-wang22b, title = {Towards Efficient and Expressive GNNs for Graph Classification via Subgraph-Aware Weisfeiler-Lehman}, author = {Wang, Zhaohui and Cao, Qi and Shen, Huawei and Bingbing, Xu and Zhang, Muhan and Cheng, Xueqi}, booktitle = {Proceedings of the First Learning on Graphs Conference}, pages = {17:1--17:18}, year = {2022}, editor = {Rieck, Bastian and Pascanu, Razvan}, volume = {198}, series = {Proceedings of Machine Learning Research}, month = {09--12 Dec}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v198/wang22b/wang22b.pdf}, url = {https://proceedings.mlr.press/v198/wang22b.html}, abstract = {The expressive power of GNNs is upper-bounded by the Weisfeiler-Lehman (WL) test. To achieve GNNs with high expressiveness, researchers resort to subgraph-based GNNs (WL/GNN on subgraphs), deploying GNNs on subgraphs centered around each node to encode subgraphs instead of rooted subtrees like WL. However, deploying multiple GNNs on subgraphs suffers from much higher computational cost than deploying a single GNN on the whole graph, limiting its application to large-size graphs. In this paper, we propose a novel paradigm, namely Subgraph-aware WL (SaWL), to obtain graph representation that reaches subgraph-level expressiveness with a single GNN. We prove that SaWL has beyond-WL capability for graph isomorphism testing, while sharing similar runtime to WL. To generalize SaWL to graphs with continuous node features, we propose a neural version named Subgraph-aware GNN (SaGNN) to learn graph representation. Both SaWL and SaGNN are more expressive than 1-WL while having similar computational cost to 1-WL/GNN, without causing much higher complexity like other more expressive GNNs. Experimental results on several benchmark datasets demonstrate that fast SaWL and SaGNN significantly outperform competitive baseline methods on the task of graph classification, while achieving high efficiency. } }
Endnote
%0 Conference Paper %T Towards Efficient and Expressive GNNs for Graph Classification via Subgraph-Aware Weisfeiler-Lehman %A Zhaohui Wang %A Qi Cao %A Huawei Shen %A Xu Bingbing %A Muhan Zhang %A Xueqi Cheng %B Proceedings of the First Learning on Graphs Conference %C Proceedings of Machine Learning Research %D 2022 %E Bastian Rieck %E Razvan Pascanu %F pmlr-v198-wang22b %I PMLR %P 17:1--17:18 %U https://proceedings.mlr.press/v198/wang22b.html %V 198 %X The expressive power of GNNs is upper-bounded by the Weisfeiler-Lehman (WL) test. To achieve GNNs with high expressiveness, researchers resort to subgraph-based GNNs (WL/GNN on subgraphs), deploying GNNs on subgraphs centered around each node to encode subgraphs instead of rooted subtrees like WL. However, deploying multiple GNNs on subgraphs suffers from much higher computational cost than deploying a single GNN on the whole graph, limiting its application to large-size graphs. In this paper, we propose a novel paradigm, namely Subgraph-aware WL (SaWL), to obtain graph representation that reaches subgraph-level expressiveness with a single GNN. We prove that SaWL has beyond-WL capability for graph isomorphism testing, while sharing similar runtime to WL. To generalize SaWL to graphs with continuous node features, we propose a neural version named Subgraph-aware GNN (SaGNN) to learn graph representation. Both SaWL and SaGNN are more expressive than 1-WL while having similar computational cost to 1-WL/GNN, without causing much higher complexity like other more expressive GNNs. Experimental results on several benchmark datasets demonstrate that fast SaWL and SaGNN significantly outperform competitive baseline methods on the task of graph classification, while achieving high efficiency.
APA
Wang, Z., Cao, Q., Shen, H., Bingbing, X., Zhang, M. & Cheng, X.. (2022). Towards Efficient and Expressive GNNs for Graph Classification via Subgraph-Aware Weisfeiler-Lehman. Proceedings of the First Learning on Graphs Conference, in Proceedings of Machine Learning Research 198:17:1-17:18 Available from https://proceedings.mlr.press/v198/wang22b.html.

Related Material