A graphon-signal analysis of graph neural networks

• URL: http://arxiv.org/abs/2305.15987v2
• Date: Fri, 8 Dec 2023 13:10:23 GMT
• Title: A graphon-signal analysis of graph neural networks
• Authors: Ron Levie
• Abstract summary: We present an approach for analyzing message passing graph neural networks (MPNNs) based on an extension of graphon analysis to a so called graphon-signal analysis. We prove that MPNNs are Lipschitz continuous functions over the graphon-signal metric space.
• Score: 8.423229632785025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an approach for analyzing message passing graph neural networks (MPNNs) based on an extension of graphon analysis to a so called graphon-signal analysis. A MPNN is a function that takes a graph and a signal on the graph (a graph-signal) and returns some value. Since the input space of MPNNs is non-Euclidean, i.e., graphs can be of any size and topology, properties such as generalization are less well understood for MPNNs than for Euclidean neural networks. We claim that one important missing ingredient in past work is a meaningful notion of graph-signal similarity measure, that endows the space of inputs to MPNNs with a regular structure. We present such a similarity measure, called the graphon-signal cut distance, which makes the space of all graph-signals a dense subset of a compact metric space -- the graphon-signal space. Informally, two deterministic graph-signals are close in cut distance if they ``look like'' they were sampled from the same random graph-signal model. Hence, our cut distance is a natural notion of graph-signal similarity, which allows comparing any pair of graph-signals of any size and topology. We prove that MPNNs are Lipschitz continuous functions over the graphon-signal metric space. We then give two applications of this result: 1) a generalization bound for MPNNs, and, 2) the stability of MPNNs to subsampling of graph-signals. Our results apply to any regular enough MPNN on any distribution of graph-signals, making the analysis rather universal.

Related papers

• A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation [13.843101157271034]
  Generalization and approximation capabilities of graph neural networks (MPNNs) are studied by defining a compact metric on a space of input graphs under which MPNNs are Hlder continuous.<n>We present a unified approach, defining a compact metric on the space of graphs of all sizes, both sparse and dense, under which MPNNs are Hlder continuous.
  arXiv  Detail & Related papers  (2026-02-09T15:25:36Z)
• A Note on Graphon-Signal Analysis of Graph Neural Networks [16.990615110732524]
  We introduce several refinements and extensions to existing results that address these shortcomings.<n>We improve the generalization bound by utilizing robustness-type generalization bounds.<n>We extend the analysis to non-symmetric graphons and kernels.
  arXiv  Detail & Related papers  (2025-08-25T23:46:02Z)
• Higher-Order Graphon Neural Networks: Approximation and Cut Distance [30.258169775217926]
  We extend the $k$-WL test for graphons to the graphon-signal space and introduce signal-weighted homomorphism densities as a key tool. As an exemplary focus, we generalize Invariant Graph Networks (IGNs) to graphons. We show that IWNs of order $k$ are at least as powerful as the $k$-WL test, and we establish universal approximation results for graphon-signals in $Lp$ distances.
  arXiv  Detail & Related papers  (2025-03-18T15:14:49Z)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [33.266521866968304]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes. We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs. Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points.
  arXiv  Detail & Related papers  (2024-11-08T10:34:24Z)
• Generalization Bounds for Message Passing Networks on Mixture of Graphons [21.457225542391267]
  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.
  arXiv  Detail & Related papers  (2024-04-04T14:26:47Z)
• Seq-HGNN: Learning Sequential Node Representation on Heterogeneous Graph [57.2953563124339]
  We propose a novel heterogeneous graph neural network with sequential node representation, namely Seq-HGNN. We conduct extensive experiments on four widely used datasets from Heterogeneous Graph Benchmark (HGB) and Open Graph Benchmark (OGB)
  arXiv  Detail & Related papers  (2023-05-18T07:27:18Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• From Local to Global: Spectral-Inspired Graph Neural Networks [28.858773653743075]
  Graph Neural Networks (GNNs) are powerful deep learning methods for Non-Euclidean data. MPNNs are message-passing algorithms that aggregate and combine signals in a local graph neighborhood. MPNNs can suffer from issues like over-smoothing or over-squashing.
  arXiv  Detail & Related papers  (2022-09-24T17:19:00Z)
• 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)
• Graph and graphon neural network stability [122.06927400759021]
  Graph networks (GNNs) are learning architectures that rely on knowledge of the graph structure to generate meaningful representations of network data. We analyze GNN stability using kernel objects called graphons.
  arXiv  Detail & Related papers  (2020-10-23T16:55:56Z)
• 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)
• Graph Neural Networks: Architectures, Stability and Transferability [176.3960927323358]
  Graph Neural Networks (GNNs) are information processing architectures for signals supported on graphs. They are generalizations of convolutional neural networks (CNNs) in which individual layers contain banks of graph convolutional filters.
  arXiv  Detail & Related papers  (2020-08-04T18:57:36Z)
• Graphon Pooling in Graph Neural Networks [169.09536309161314]
  Graph neural networks (GNNs) have been used effectively in different applications involving the processing of signals on irregular structures modeled by graphs. We propose a new strategy for pooling and sampling on GNNs using graphons which preserves the spectral properties of the graph.
  arXiv  Detail & Related papers  (2020-03-03T21:04:20Z)

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.