Conference item
The surprising power of graph neural networks with random node initialization
- Abstract:
- Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 149.9KB, Terms of use)
-
- Publisher copy:
- 10.24963/ijcai.2021/291
Authors
- Publisher:
- International Joint Conferences on Artificial Intelligence Organization
- Host title:
- Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, (IJCAI-21)
- Pages:
- 2112-2118
- Publication date:
- 2021-08-09
- Acceptance date:
- 2021-04-29
- Event title:
- 30th International Joint Conference on Artificial Intelligence
- Event location:
- Montreal-themed Virtual Reality
- Event website:
- https://ijcai-21.org/
- Event start date:
- 2021-08-19
- Event end date:
- 2021-08-26
- DOI:
- Language:
-
English
- Keywords:
- Pubs id:
-
1187429
- Local pid:
-
pubs:1187429
- Deposit date:
-
2021-07-24
- ARK identifier:
Terms of use
- Copyright holder:
- IJCAI
- Copyright date:
- 2021
- Rights statement:
- Copyright © 2021, IJCAI
- Notes:
- This paper was presented at the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), 19th -26th August, 2021.
If you are the owner of this record, you can report an update to it here: Report update to this record