Universality and Approximation Rates of Graph Neural Networks with Random Features

• URL: http://arxiv.org/abs/2607.26699v1
• Date: Wed, 29 Jul 2026 09:46:07 GMT
• Title: Universality and Approximation Rates of Graph Neural Networks with Random Features
• Abstract summary: Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically.<n>We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function.
• Score: 5.394466899760558
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We investigate message-passing graph neural networks with random node features. Random node features are known to enhance the expressiveness of graph neural networks (GNNs) both theoretically and empirically. Here, we establish a novel universality result focusing on permutation-equivariant neural networks (PENNs), a class of GNNs built from feedforward neural network components that subsumes many prominent GNN architectures. We show that PENNs, combined with partially random node features, can approximate arbitrarily well in probability any measurable permutation-invariant or permutation-equivariant function on directed graphs of fixed size with multidimensional node and edge features. For $k$-times continuously differentiable functions, $k\geq 2$, we also derive upper bounds on the approximation rates, relating the complexity of the feedforward components of a PENN in terms of layer depth and number of nonzero weights to the desired approximation accuracy.

Related papers

• Non-convolutional Graph Neural Networks [46.79328529882998]
  We design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network. RUM achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.
  arXiv  Detail & Related papers  (2024-07-31T21:29:26Z)
• Graph Neural Networks for Learning Equivariant Representations of Neural Networks [55.04145324152541]
  We propose to represent neural networks as computational graphs of parameters. Our approach enables a single model to encode neural computational graphs with diverse architectures. We showcase the effectiveness of our method on a wide range of tasks, including classification and editing of implicit neural representations.
  arXiv  Detail & Related papers  (2024-03-18T18:01:01Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• Separable Gaussian Neural Networks: Structure, Analysis, and Function Approximations [2.17301816060102]
  We propose a new feedforward network - Separable Gaussian Neural Network (SGNN) SGNN takes advantage of the separable property of Gaussian functions, which splits data into multiple columns and sequentially feeds them into parallel layers. experimentally demonstrated that SGNN can achieve 100 times speedup with a similar level of accuracy over GRBFNN.
  arXiv  Detail & Related papers  (2023-08-13T03:54:30Z)
• Permutation Equivariant Neural Functionals [92.0667671999604]
  This work studies the design of neural networks that can process the weights or gradients of other neural networks. We focus on the permutation symmetries that arise in the weights of deep feedforward networks because hidden layer neurons have no inherent order. In our experiments, we find that permutation equivariant neural functionals are effective on a diverse set of tasks.
  arXiv  Detail & Related papers  (2023-02-27T18:52:38Z)
• Equivariant Neural Network for Factor Graphs [83.26543234955855]
  We propose two inference models: Factor-Equivariant Neural Belief Propagation (FE-NBP) and Factor-Equivariant Graph Neural Networks (FE-GNN) FE-NBP achieves state-of-the-art performance on small datasets while FE-GNN achieves state-of-the-art performance on large datasets.
  arXiv  Detail & Related papers  (2021-09-29T06:54:04Z)
• Enhance Information Propagation for Graph Neural Network by Heterogeneous Aggregations [7.3136594018091134]
  Graph neural networks are emerging as continuation of deep learning success w.r.t. graph data. We propose to enhance information propagation among GNN layers by combining heterogeneous aggregations. We empirically validate the effectiveness of HAG-Net on a number of graph classification benchmarks.
  arXiv  Detail & Related papers  (2021-02-08T08:57:56Z)
• 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)
• Permutation-equivariant and Proximity-aware Graph Neural Networks with Stochastic Message Passing [88.30867628592112]
  Graph neural networks (GNNs) are emerging machine learning models on graphs. Permutation-equivariance and proximity-awareness are two important properties highly desirable for GNNs. We show that existing GNNs, mostly based on the message-passing mechanism, cannot simultaneously preserve the two properties. In order to preserve node proximities, we augment the existing GNNs with node representations.
  arXiv  Detail & Related papers  (2020-09-05T16:46:56Z)

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.