Generalization Bounds for Message Passing Networks on Mixture of Graphons

• URL: http://arxiv.org/abs/2404.03473v1
• Date: Thu, 4 Apr 2024 14:26:47 GMT
• Title: Generalization Bounds for Message Passing Networks on Mixture of Graphons
• Authors: Sohir Maskey, Gitta Kutyniok, Ron Levie,
• Abstract summary: We study the generalization capabilities of Message Passing Neural Networks (MPNNs) We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively.
• Score: 21.457225542391267
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the generalization capabilities of Message Passing Neural Networks (MPNNs), a prevalent class of Graph Neural Networks (GNN). We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our analysis is based on a data generation model incorporating a finite set of template graphons. Each graph within this framework is generated by sampling from one of the graphons with a certain degree of perturbation. In particular, we extend previous MPNN generalization results to a more realistic setting, which includes the following modifications: 1) we analyze simple random graphs with Bernoulli-distributed edges instead of weighted graphs; 2) we sample both graphs and graph signals from perturbed graphons instead of clean graphons; and 3) we analyze sparse graphs instead of dense graphs. In this more realistic and challenging scenario, we provide a generalization bound that decreases as the average number of nodes in the graphs increases. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively, as long as the graphs are sufficiently large.

Related papers

• Generalization of Geometric Graph Neural Networks [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs) We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN. The most important observation is that the generalization capability can be realized with one large graph instead of being limited to the size of the graph as in previous results.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks [84.01980526069075]
  We take a manifold perspective to establish the statistical generalization theory of GNNs on graphs sampled from a manifold in the spectral domain. We prove that the generalization bounds of GNNs decrease linearly with the size of the graphs in the logarithmic scale, and increase linearly with the spectral continuity constants of the filter functions.
  arXiv  Detail & Related papers  (2024-06-07T19:25:02Z)
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion [17.70434437597516]
  We present generalization bounds that scale with the largest singular value of the graph neural network's feature diffusion matrix. These bounds are numerically much smaller than prior bounds for real-world graphs. We measure the stability of graph neural networks against noise perturbations using Hessians.
  arXiv  Detail & Related papers  (2023-02-09T05:54:17Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• Graph Condensation via Receptive Field Distribution Matching [61.71711656856704]
  This paper focuses on creating a small graph to represent the original graph, so that GNNs trained on the size-reduced graph can make accurate predictions. We view the original graph as a distribution of receptive fields and aim to synthesize a small graph whose receptive fields share a similar distribution.
  arXiv  Detail & Related papers  (2022-06-28T02:10:05Z)
• Stability and Generalization Capabilities of Message Passing Graph Neural Networks [4.691259009382681]
  We study the generalization capabilities of MPNNs in graph classification. We derive a non-asymptotic bound on the generalization gap between the empirical and statistical loss. This is proven by showing that a MPNN, applied on a graph, approximates the MPNN applied on the geometric model that the graph discretizes.
  arXiv  Detail & Related papers  (2022-02-01T18:37:53Z)
• Transferability Properties of Graph Neural Networks [125.71771240180654]
  Graph neural networks (GNNs) are provably successful at learning representations from data supported on moderate-scale graphs. We study the problem of training GNNs on graphs of moderate size and transferring them to large-scale graphs. Our results show that (i) the transference error decreases with the graph size, and (ii) that graph filters have a transferability-discriminability tradeoff that in GNNs is alleviated by the scattering behavior of the nonlinearity.
  arXiv  Detail & Related papers  (2021-12-09T00:08:09Z)
• Towards Scale-Invariant Graph-related Problem Solving by Iterative Homogeneous Graph Neural Networks [39.370875358317946]
  Current graph neural networks (GNNs) lack generalizability with respect to scales (graph sizes, graph diameters, edge weights, etc.) when solving many graph analysis problems. We propose several extensions to address the issue. First, inspired by the dependency of the number of iteration of common graph theory algorithms on graph size, we learn to terminate the message passing process in GNNs adaptively according to the progress. Second, inspired by the fact that many graph theory algorithms are homogeneous with respect to graph weights, we introduce homogeneous transformation layers that are universal homogeneous function approximators, to convert ordinary G
  arXiv  Detail & Related papers  (2020-10-26T12:57:28Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• MathNet: Haar-Like Wavelet Multiresolution-Analysis for Graph Representation and Learning [31.42901131602713]
  We propose a framework for graph neural networks with multiresolution Haar-like wavelets, or MathNet, with interrelated convolution and pooling strategies. The proposed MathNet outperforms various existing GNN models, especially on big data sets.
  arXiv  Detail & Related papers  (2020-07-22T05:00:59Z)

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.