Source-linked AI summary
Random Features Strengthen Graph Neural Networks
Ryoma Sato, Makoto Yamada, Hisashi Kashima
TL;DR
GNNs have expressive limitations that hinder graph distinction and efficient graph algorithms. The paper adds random features to nodes, forming rGINs that can learn randomized algorithms. The resulting models achieve nearly optimal approximation ratios for minimum dominating set and maximum matching and solve tasks normal GNNs cannot.
Problem
GNNs are limited in distinguishing some non-isomorphic graphs and learning efficient graph algorithms.
Method
The paper adds a random value to each node and applies graph isomorphism networks with random features to learn randomized algorithms.
Results
rGINs distinguish local substructures with high probability, achieve nearly optimal approximation ratios for minimum dominating set and maximum matching, and solve three problems normal GINs cannot.
Takeaways & Limitations
Random features strengthen GINs while retaining applicability to arbitrarily large test graphs and enabling performance on tasks normal GINs cannot solve.
Takeaways & Limitations
The theoretical analysis assumes bounded-degree graphs and uses discrete random features for consistency, while continuous features are described as practical but not theoretically guaranteed to ensure consistency.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper proposes adding random node features to GNNs, allowing them to learn randomized algorithms and achieve near-optimal approximation ratios for combinatorial graph problems.
- Existing GNN approximation ratios for combinatorial problems were much higher than those of existing algorithms, and feature engineering remained far from optimal.
- The method adds a random feature to each node and is implemented as graph isomorphism networks with random features, or rGINs.Each node receives a new random value whenever the procedure is called.
- Random features can reveal local structures that identical node features cannot distinguish, such as distinguishing cycles of length three from six.A node can check whether its depth-three neighborhood contains the same random feature as itself.
- rGINs improve theoretical GNN capability by enabling learned randomized algorithms, whereas standard GNNs learn only deterministic algorithms.
- The analysis converts certain constant-time algorithms to rGINs and conversely converts rGINs to constant-time algorithms.This establishes a connection between GNN theory and constant-time algorithm theory.
2 Related Work
Related work establishes strong connections between GNN expressive power and 1-WL tests, distributed local algorithms, and logic, while exploring methods to overcome these limits.
- GNN expressive power is at most that of the 1-dimensional Weisfeiler-Leman test, limiting their ability to distinguish some graphs.
- Message-passing GNNs have representation power equivalent to distributed local algorithms and model logic.
- Higher-order tensor GNNs, relational pooling, and Janossy Pooling improve expressive power or construct universal invariant and equivariant networks.
- Prior analyses showed that message-passing GNNs cannot solve many tasks unless the product of depth and width depends polynomially on the number of nodes.
- The proposed random-feature approach differs from π-SGD by supporting variable-sized graphs through i.i.d. random variables with constant support.
3 Background and Notations
The paper formalizes bounded-degree graph problems, approximation guarantees, GIN message passing, and the role of local neighborhoods and node features in these definitions.
- Graph setting: Graphs may include node features from a finite support; when no features are present, degree features provide the initial embedding.
- Graph setting: The analysis considers connected simple graphs with maximum degree bounded by a fixed Δ, an assumption also used in constant-time algorithms.The bounded-degree assumption is weaker than bounded-size because bounded-degree graph families include all bounded-size graphs when Δ reaches the maximum graph size.
- Graph problems: A minimum dominating set contains vertices covering every vertex by membership or adjacency, and the objective is to minimize its size.
- Graph problems: Minimum dominating set and maximum matching are examples of monotone graph problems.
- Approximation: A consistent algorithm always outputs a feasible node or edge solution, including when its internal process is randomized.
- Approximation: An (α, β)-approximation bounds minimization objectives between OPTm and αOPTm + β, and maximization objectives between αOPTM − β and OPTM.
- GINs: GINs aggregate neighboring feature multisets and have the strongest expressive power among message-passing GNNs, matching 1-WL.
- Illustrative example: Identical features can make GNNs unable to distinguish nodes in three-node and six-node cycles, whereas random features enable that distinction.
4 Main Results
The paper strengthens GINs by assigning i.i.d. random features to nodes, enabling local-structure discrimination and near-optimal approximation algorithms for key combinatorial problems.
- Expressive power: Random features let rGINs distinguish local graph structures that ordinary message-passing GNNs may conflate, including triangle incidence.Theorem 4.1 separates rooted L-hop neighborhoods with high probability under bounded-degree and finite-feature assumptions.
- Combinatorial problems: rGINs can select nodes appropriately in combinatorial problems even when local-structure distinction alone is insufficient, such as minimum dominating set on cliques.This extends the role of random features beyond ordinary node classification to combinatorial selection.
- Random-feature GINs: rGINs assign random values to nodes and concatenate them with original features before applying GINs.The method is a slight modification of GINs; discrete random features support consistency guarantees, while continuous features can be used in practice.
- Minimum dominating set: H(∆+1)+ε is the proven approximation ratio for the minimum dominating set problem under the bounded-degree setting.The learned solution is always feasible and satisfies the bound with high probability.
- Maximum matching: 1+ε is the proven approximation ratio for maximum matching, with rGINs always returning a feasible matching.The guarantee holds with high probability for suitable depth and random-feature distributions.
- Connections to constant-time algorithms: The theory also gives a converse: a consistent rGIN approximation algorithm implies a constant-time algorithm estimating the optimum within (α, εn).This connects randomized GNN expressivity with the theory of constant-time graph algorithms.
5 Experiments
Experiments test whether random features improve GNNs on synthetic substructure tasks, real-world graph classification, and minimum dominating set learning. The results show stronger substructure recognition, size generalization, and competitive real-world performance, with a noted limitation involving suboptimal learned parameters.
- Learning Substructures: rGINs generalize from 20-node training graphs to 100-node TRIANGLE(X) and LCC(X) test graphs, demonstrating applicability to variable-size graphs.The extrapolation datasets use larger test graphs than the training graphs.
- Learning Substructures: rGINs and rGCNs learn local substructures in synthetic TRIANGLE and LCC datasets, whereas ordinary GINs and GCNs cannot distinguish them.The experiments evaluate triangle existence and local clustering coefficients, including extrapolation to larger test graphs.
- Learning Substructures: rGINs classify nodes using substructure information without explicitly adding triangles or local clustering coefficients as node features.This supports learning characteristic substructures from data rather than enumerating all potentially useful substructures manually.
- Learning Substructures: Figure 2 visualizes embeddings of positive and negative nodes across 20 random seeds, supporting classification that remains correct when random features change.Positive nodes contain a triangle, while negative nodes do not.
- Learning Algorithms: The learned parameters are reported as suboptimal, limiting the quality of the learned algorithm.This caveat is stated alongside the minimum dominating set experiments.
- Learning Algorithms: rGINs learn the sequential greedy algorithm for minimum dominating set on random 3-regular graphs, including tests with 100-node graphs.The experiment uses 20-node training graphs and 20-node or 100-node test graphs.
- Real World Datasets: rGINs and rGCNs are comparable to or slightly better than ordinary GINs on MUTAG, NCI1, and PROTEINS, with statistically significant gains on two tasks.The performance gain is less dramatic because degree signals already distinguish most nodes in these real-world datasets.
6 Conclusion
The paper concludes that adding random features strengthens GINs' theoretical and practical capabilities. rGINs distinguish local substructures with high probability, achieve nearly optimal approximation ratios for two graph problems, and solve tasks that ordinary GINs cannot.
- Conclusion: Adding random features theoretically strengthens the capability of GINs.The modification is presented as the paper's central theoretical contribution.
- Conclusion: rGINs distinguish any local substructures with high probability and solve minimum dominating set and maximum matching with nearly optimal approximation ratios.The theoretical guarantees apply even with arbitrarily large test graphs.
- Conclusion: Experiments show that rGINs solve triangle detection, local clustering coefficient computation, and minimum dominating set learning, which normal GINs cannot solve.The conclusion also reports slight outperformance by rGINs on biological real-world datasets.
A.1 Dataset Descriptions
The experiments use chemical, protein, and synthetic graph datasets, with standard GNN training settings and graph generation procedures. Dataset-specific descriptions define node meanings, labels, and evaluation contexts.
- Real-World Datasets: MUATG and NCI1 are chemical compound datasets whose nodes represent atoms, edges represent chemical bonds, and node features encode atom types.MUATG labels graphs by mutagenic effect, while NCI1 labels them using anti-cancer screening records.
- Real-World Datasets: PROTEINS represents secondary-structure elements as nodes, connects sequence or three-dimensional neighbors, and labels graphs as enzymes or non-enzymes.Node features encode helix, sheet, or turn structure types.
- General Setups: The general experiments use five-layer GNNs, Adam optimization, initial learning rate 0.01, batch size 32, and dropout rate 0.5 in the final layer.GCNs aggregate features by average pooling in these experiments.
- Setups for MDS: Minimum dominating set experiments use ten-layer GNNs with 1024 hidden dimensions and train with SGD at learning rate 0.1 for 50000 epochs.These settings differ because learning the greedy algorithm requires more expressive power.
- Graph Synthesis Process: TRIANGLE, LCC, and MDS graphs are generated with NetworkX's random graph function using different seeds.Figure 3 gives examples of test graphs from TRIANGLE(X).
B More Discussion on Assumptions
The theoretical discussion assumes fixed, potentially large feature dimension and a universal multilayer perceptron. It also states that the relevant distribution parameter depends on local neighborhoods rather than input-graph size.
- Assumptions: The theoretical results assume fixed feature dimension, a universal multilayer perceptron, and parameters whose existence includes an appropriate architecture.The universal approximation theorem is cited to justify the MLP assumption.
- Assumptions: The parameter p depends on the size of the local neighborhood R(G, v, L), not on the size of the input graph.The discussion notes that this neighborhood size is bounded when L and the degree bound are fixed.
C Proofs
The proofs show that random node features let GINs recover local rooted structures with high probability and simulate functions needed for approximation algorithms. This yields approximation guarantees for minimum dominating set and maximum matching, with solution sizes estimable from sampled nodes or edges.
- Random-feature recovery: Random features are unlikely to collide within bounded-radius neighborhoods, enabling local rooted-structure recovery with probability controlled by the feature distribution.Lemma C.1 bounds neighborhood collisions, while Lemma C.2 reconstructs the rooted labeled structure from the level-(L+1) tree when nearby random features are distinct.
- Random-feature recovery: GINs can simulate any function of the recovered bounded-radius neighborhood representation by choosing suitable parameters.The proof combines the GIN representation result with the recovery lemma to establish equivalent outputs for locally distinguishable rooted neighborhoods.
- Minimum dominating set: (H(∆ + 1) + ε)-approximation: rGINs simulate the dominating-set procedure that outputs a dominating set of this size with high probability.The constructed set combines locally problematic vertices, vertices selected by the sequential algorithm, and collision-related exceptions.
- Maximum matching: (1 + ε)-approximation: the random-feature matching procedure removes collision-affected edges, simulates the sequential algorithm locally, and retains this guarantee with high probability.The proof bounds the number of affected edges and shows that the resulting local edge decisions can be represented by node embeddings and their inner products.
- Approximation estimation: rGINs can estimate solution sizes within additive error εn with high probability by evaluating uniformly sampled nodes or edges.The required sample count is O(1/ε^2) for both node and edge problems, using the Hoeffding bound.