Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2303.10576 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913388780584960 |
|---|---|
| author | Yan, Zuoyu Zhou, Junru Gao, Liangcai Tang, Zhi Zhang, Muhan |
| author_facet | Yan, Zuoyu Zhou, Junru Gao, Liangcai Tang, Zhi Zhang, Muhan |
| contents | We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both \textbf{efficiently} and \textbf{provably}? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_10576 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | An Efficient Subgraph GNN with Provable Substructure Counting Power Yan, Zuoyu Zhou, Junru Gao, Liangcai Tang, Zhi Zhang, Muhan Machine Learning We investigate the enhancement of graph neural networks' (GNNs) representation power through their ability in substructure counting. Recent advances have seen the adoption of subgraph GNNs, which partition an input graph into numerous subgraphs, subsequently applying GNNs to each to augment the graph's overall representation. Despite their ability to identify various substructures, subgraph GNNs are hindered by significant computational and memory costs. In this paper, we tackle a critical question: Is it possible for GNNs to count substructures both \textbf{efficiently} and \textbf{provably}? Our approach begins with a theoretical demonstration that the distance to rooted nodes in subgraphs is key to boosting the counting power of subgraph GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we introduce precomputed structural embeddings that encapsulate this crucial distance information. Experiments validate that our proposed model retains the counting power of subgraph GNNs while achieving significantly faster performance. |
| title | An Efficient Subgraph GNN with Provable Substructure Counting Power |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2303.10576 |