Random Features Strengthen Graph Neural Networks

2020/02/08 by Ryoma Sato, Makoto Yamada, Sato, Ryoma +3 · 1 voice · 19 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Ferroelectric and Negative Capacitance Devices #Graph Theory and Algorithms #Machine Learning (cs.LG) #Machine Learning (stat.ML) #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.2002.03155

Accepted to SDM 2021

openalex publication_date 2020/02/08 · arxiv published 2020/02/08 · arxiv created 2021/01/18 · arxiv updated 2021/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Graph neural networks (GNNs) are powerful machine learning models for various graph learning tasks. Recently, the limitations of the expressive power of various GNN models have been revealed. For example, GNNs cannot distinguish some non-isomorphic graphs and they cannot learn efficient graph algorithms. In this paper, we demonstrate that GNNs become powerful just by adding a random feature to each node. We prove that the random features enable GNNs to learn almost optimal polynomial-time approximation algorithms for the minimum dominating set problem and maximum matching problem in terms of approximation ratios. The main advantage of our method is that it can be combined with off-the-shelf GNN models with slight modifications. Through experiments, we show that the addition of random features enables GNNs to solve various problems that normal GNNs, including the graph convolutional networks (GCNs) and graph isomorphism networks (GINs), cannot solve.

Cited by

• CondPSE: A Polynomial-Filtered Structural Encoder with Conditional Modulation for Graphs
• Plain Transformers are Surprisingly Powerful Link Predictors
• Enhancing Graph Representations with Neighborhood-Contextualized Message-Passing
• Enhancing Logical Expressiveness in Graph Neural Networks via Path-Neighbor Aggregation
• Sketch-Augmented Features Improve Learning Long-Range Dependencies in Graph Neural Networks
• On The Expressive Power of GNN Derivatives
• GraphPFN: A Prior-Data Fitted Graph Foundation Model
• Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices
• Persistent Gaussian Perturbations Prevent Oversmoothing in Recurrent Graph Neural Networks
• From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
• Invariant Graph Transformer for Out-of-Distribution Generalization
• MILP-SAT-GNN: Yet Another Neural SAT Solver
• Logical Expressiveness of Graph Neural Networks with Hierarchical Node Individualization
• Positional Encoding meets Persistent Homology on Graphs
• Flow-Attentional Graph Neural Networks
• Equivariant Subgraph Aggregation Networks
• Graph Neural Networks for Jamming Source Localization
• Graph Representational Learning: When Does More Expressivity Hurt Generalization?
• Relational Graph Transformer

Discussions

• graph isomorphism network (GIN) にランダム特徴量を食わせると universal になる，という結果が知られてる ( arxiv.org/abs/2002.03155 )．これを使ってランダム初期化した GIN にランダム特徴量を食わせて特徴量について期待値をとったら GI 解けるじゃん，サンプル数も Chernoff bound で押さえて多項式じゃん，ってなった [bsky, 0 points, 1 comments]

Related

• Graph Random Neural Network for Semi-Supervised Learning on Graphs
• On the Universality of Graph Neural Networks on Large Random Graphs
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding
• The Surprising Power of Graph Neural Networks with Random Node Initialization
• On the Effectiveness of Random Weights in Graph Neural Networks