Union subgraph neural networks
Graph Neural Networks (GNNs) are widely used for graph representation learning in many application domains. The expressiveness of vanilla GNNs is upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) test as they operate on rooted subtrees through iterative message passing. In this paper, we empowe...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/173329 https://ojs.aaai.org/index.php/AAAI/article/view/29551 |
| _version_ | 1811676796362424320 |
|---|---|
| author | Xu, Jiaxing Zhang, Aihu Bian, Qingtian Dwivedi, Vijay Prakash Ke, Yiping |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Xu, Jiaxing Zhang, Aihu Bian, Qingtian Dwivedi, Vijay Prakash Ke, Yiping |
| author_sort | Xu, Jiaxing |
| collection | NTU |
| description | Graph Neural Networks (GNNs) are widely used for graph representation learning in many application domains. The expressiveness of vanilla GNNs is upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) test as they operate on rooted subtrees through iterative message passing. In this paper, we empower GNNs by injecting neighbor-connectivity information extracted from a new type of substructure. We first investigate different kinds of connectivities existing in a local neighborhood and identify a substructure called union subgraph, which is able to capture the complete picture of the 1-hop neighborhood of an edge. We then design a shortest-path-based substructure descriptor that possesses three nice properties and can effectively encode the high-order connectivities in union subgraphs. By infusing the encoded neighbor connectivities, we propose a novel model, namely Union Subgraph Neural Network (UnionSNN), which is proven to be strictly more powerful than 1-WL in distinguishing non-isomorphic graphs. Additionally, the local encoding from union subgraphs can also be injected into arbitrary message-passing neural networks (MPNNs) and Transformer-based models as a plugin. Extensive experiments on 18 benchmarks of both graph-level and node-level tasks demonstrate
that UnionSNN outperforms state-of-the-art baseline models, with competitive computational efficiency. The injection of our local encoding to existing models is able to boost the performance by up to 11.09%. Our code is available at https://github.com/AngusMonroe/UnionSNN. |
| first_indexed | 2024-10-01T02:27:10Z |
| format | Conference Paper |
| id | ntu-10356/173329 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:27:10Z |
| publishDate | 2024 |
| record_format | dspace |
| spelling | ntu-10356/1733292024-07-12T07:12:04Z Union subgraph neural networks Xu, Jiaxing Zhang, Aihu Bian, Qingtian Dwivedi, Vijay Prakash Ke, Yiping School of Computer Science and Engineering The 38th AAAI Conference on Artificial Intelligence (AAAI 2024) Computational Intelligence Lab (CIL) Computer and Information Science Graph Neural Networks Weisfeiler-Leman Test Message-Passing Neural Networks Graph Neural Networks (GNNs) are widely used for graph representation learning in many application domains. The expressiveness of vanilla GNNs is upper-bounded by 1-dimensional Weisfeiler-Leman (1-WL) test as they operate on rooted subtrees through iterative message passing. In this paper, we empower GNNs by injecting neighbor-connectivity information extracted from a new type of substructure. We first investigate different kinds of connectivities existing in a local neighborhood and identify a substructure called union subgraph, which is able to capture the complete picture of the 1-hop neighborhood of an edge. We then design a shortest-path-based substructure descriptor that possesses three nice properties and can effectively encode the high-order connectivities in union subgraphs. By infusing the encoded neighbor connectivities, we propose a novel model, namely Union Subgraph Neural Network (UnionSNN), which is proven to be strictly more powerful than 1-WL in distinguishing non-isomorphic graphs. Additionally, the local encoding from union subgraphs can also be injected into arbitrary message-passing neural networks (MPNNs) and Transformer-based models as a plugin. Extensive experiments on 18 benchmarks of both graph-level and node-level tasks demonstrate that UnionSNN outperforms state-of-the-art baseline models, with competitive computational efficiency. The injection of our local encoding to existing models is able to boost the performance by up to 11.09%. Our code is available at https://github.com/AngusMonroe/UnionSNN. Ministry of Education (MOE) National Research Foundation (NRF) Submitted/Accepted version This research/project is supported by the National Research Foundation, Singapore under its Industry Alignment Fund – Pre-positioning (IAF-PP) Funding Initiative, and the Ministry of Education, Singapore under its MOE Academic Research Fund Tier 2 (STEM RIE2025 Award MOE-T2EP20220-0006). 2024-03-06T02:04:39Z 2024-03-06T02:04:39Z 2024 Conference Paper Xu, J., Zhang, A., Bian, Q., Dwivedi, V. P. & Ke, Y. (2024). Union subgraph neural networks. The 38th AAAI Conference on Artificial Intelligence (AAAI 2024), 38, 16173-16183. https://dx.doi.org/10.1609/aaai.v38i14.29551 https://hdl.handle.net/10356/173329 10.1609/aaai.v38i14.29551 https://ojs.aaai.org/index.php/AAAI/article/view/29551 38 16173 16183 en IAF-PP MOE-T2EP20220-0006 © 2024 Association for the Advancement of Artifcial Intelligence. All rights reserved. This article may be downloaded for personal use only. Any other use requires prior permission of the copyright holder. The Version of Record is available online at https://doi.org/10.1609/aaai.v38i14.29551. application/pdf |
| spellingShingle | Computer and Information Science Graph Neural Networks Weisfeiler-Leman Test Message-Passing Neural Networks Xu, Jiaxing Zhang, Aihu Bian, Qingtian Dwivedi, Vijay Prakash Ke, Yiping Union subgraph neural networks |
| title | Union subgraph neural networks |
| title_full | Union subgraph neural networks |
| title_fullStr | Union subgraph neural networks |
| title_full_unstemmed | Union subgraph neural networks |
| title_short | Union subgraph neural networks |
| title_sort | union subgraph neural networks |
| topic | Computer and Information Science Graph Neural Networks Weisfeiler-Leman Test Message-Passing Neural Networks |
| url | https://hdl.handle.net/10356/173329 https://ojs.aaai.org/index.php/AAAI/article/view/29551 |
| work_keys_str_mv | AT xujiaxing unionsubgraphneuralnetworks AT zhangaihu unionsubgraphneuralnetworks AT bianqingtian unionsubgraphneuralnetworks AT dwivedivijayprakash unionsubgraphneuralnetworks AT keyiping unionsubgraphneuralnetworks |