A Note on Graphon-Signal Analysis of Graph Neural Networks

• URL: http://arxiv.org/abs/2508.18564v1
• Date: Mon, 25 Aug 2025 23:46:02 GMT
• Title: A Note on Graphon-Signal Analysis of Graph Neural Networks
• Authors: Levi Rauchwerger, Ron Levie,
• Abstract summary: 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.
• Score: 16.990615110732524
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A recent paper, ``A Graphon-Signal Analysis of Graph Neural Networks'', by Levie, analyzed message passing graph neural networks (MPNNs) by embedding the input space of MPNNs, i.e., attributed graphs (graph-signals), to a space of attributed graphons (graphon-signals). Based on extensions of standard results in graphon analysis to graphon-signals, the paper proved a generalization bound and a sampling lemma for MPNNs. However, there are some missing ingredients in that paper, limiting its applicability in practical settings of graph machine learning. In the current paper, we introduce several refinements and extensions to existing results that address these shortcomings. In detail, 1) we extend the main results in the paper to graphon-signals with multidimensional signals (rather than 1D signals), 2) we extend the Lipschitz continuity to MPNNs with readout with respect to cut distance (rather than MPNNs without readout with respect to cut metric), 3) we improve the generalization bound by utilizing robustness-type generalization bounds, and 4) we extend the analysis to non-symmetric graphons and kernels.

Related papers

• 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)
• A graphon-signal analysis of graph neural networks [8.423229632785025]
  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.
  arXiv  Detail & Related papers  (2023-05-25T12:27:35Z)
• 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)
• MentorGNN: Deriving Curriculum for Pre-Training GNNs [61.97574489259085]
  We propose an end-to-end model named MentorGNN that aims to supervise the pre-training process of GNNs across graphs. We shed new light on the problem of domain adaption on relational data (i.e., graphs) by deriving a natural and interpretable upper bound on the generalization error of the pre-trained GNNs.
  arXiv  Detail & Related papers  (2022-08-21T15:12:08Z)
• Signed Graph Neural Networks: A Frequency Perspective [14.386571627652975]
  Graph convolutional networks (GCNs) are designed for unsigned graphs containing only positive links. We propose two different signed graph neural networks, one keeps only low-frequency information and one also retains high-frequency information.
  arXiv  Detail & Related papers  (2022-08-15T16:42:18Z)
• 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)
• Graph Neural Networks with Learnable Structural and Positional Representations [83.24058411666483]
  A major issue with arbitrary graphs is the absence of canonical positional information of nodes. We introduce Positional nodes (PE) of nodes, and inject it into the input layer, like in Transformers. We observe a performance increase for molecular datasets, from 2.87% up to 64.14% when considering learnable PE for both GNN classes.
  arXiv  Detail & Related papers  (2021-10-15T05:59:15Z)
• 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)
• 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.