Conference item icon

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

Publisher copy:
10.24963/ijcai.2021/291

Authors

More by this author
Institution:
University of Oxford
Role:
Author


Engineering and Physical Sciences Research Council More from this funder
Grant:
EP/R013667/1


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


Views and Downloads

Views and downloads will return soon






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP