The Surprising Power of Graph Neural Networks with Random Node Initialization

• URL: http://arxiv.org/abs/2010.01179v2
• Date: Fri, 4 Jun 2021 14:52:04 GMT
• Title: The Surprising Power of Graph Neural Networks with Random Node Initialization
• Authors: Ralph Abboud, \.Ismail \.Ilkan Ceylan, Martin Grohe, Thomas Lukasiewicz
• Abstract summary: Graph neural networks (GNNs) are effective models for representation learning on relational data. Standard GNNs are limited in their expressive power, as they cannot distinguish beyond the capability of the Weisfeiler-Leman graph isomorphism. In this work, we analyze the expressive power of GNNs with random node (RNI) We prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties.
• Score: 54.4101931234922
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch.
  arXiv  Detail & Related papers  (2024-08-25T16:00:44Z)
• GNN-Ensemble: Towards Random Decision Graph Neural Networks [3.7620848582312405]
  Graph Neural Networks (GNNs) have enjoyed wide spread applications in graph-structured data. GNNs are required to learn latent patterns from a limited amount of training data to perform inferences on a vast amount of test data. In this paper, we push one step forward on the ensemble learning of GNNs with improved accuracy, robustness, and adversarial attacks.
  arXiv  Detail & Related papers  (2023-03-20T18:24:01Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• On the Universality of Graph Neural Networks on Large Random Graphs [22.720758067273195]
  We study the approximation power of Graph Neural Networks (GNNs) on latent position random graphs. In the large graph limit, GNNs are known to converge to certain "continuous" models known as c-GNNs. We show that c-SGNNs are strictly more powerful than c-GNNs in the continuous limit.
  arXiv  Detail & Related papers  (2021-05-27T12:52:36Z)
• Identity-aware Graph Neural Networks [63.6952975763946]
  We develop a class of message passing Graph Neural Networks (ID-GNNs) with greater expressive power than the 1-WL test. ID-GNN extends existing GNN architectures by inductively considering nodes' identities during message passing. We show that transforming existing GNNs to ID-GNNs yields on average 40% accuracy improvement on challenging node, edge, and graph property prediction tasks.
  arXiv  Detail & Related papers  (2021-01-25T18:59:01Z)
• A Unified View on Graph Neural Networks as Graph Signal Denoising [49.980783124401555]
  Graph Neural Networks (GNNs) have risen to prominence in learning representations for graph structured data. In this work, we establish mathematically that the aggregation processes in a group of representative GNN models can be regarded as solving a graph denoising problem. We instantiate a novel GNN model, ADA-UGNN, derived from UGNN, to handle graphs with adaptive smoothness across nodes.
  arXiv  Detail & Related papers  (2020-10-05T04:57:18Z)
• Expressive Power of Invariant and Equivariant Graph Neural Networks [10.419350129060598]
  We show that Folklore Graph Neural Networks (FGNN) are the most expressive architectures proposed so far for a given tensor order. FGNNs are able to learn how to solve the problem, leading to much better average performances than existing algorithms.
  arXiv  Detail & Related papers  (2020-06-28T16:35:45Z)
• Eigen-GNN: A Graph Structure Preserving Plug-in for GNNs [95.63153473559865]
  Graph Neural Networks (GNNs) are emerging machine learning models on graphs. Most existing GNN models in practice are shallow and essentially feature-centric. We show empirically and analytically that the existing shallow GNNs cannot preserve graph structures well. We propose Eigen-GNN, a plug-in module to boost GNNs ability in preserving graph structures.
  arXiv  Detail & Related papers  (2020-06-08T02:47:38Z)
• Generalization and Representational Limits of Graph Neural Networks [46.20253808402385]
  We prove that several important graph properties cannot be computed by graph neural networks (GNNs) that rely entirely on local information. We provide the first data dependent generalization bounds for message passing GNNs. Our bounds are much tighter than existing VC-dimension based guarantees for GNNs, and are comparable to Rademacher bounds for recurrent neural networks.
  arXiv  Detail & Related papers  (2020-02-14T18:10:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.