Graph Neural Networks Are Not Continuous Across Graph Resolutions

• URL: http://arxiv.org/abs/2605.31315v1
• Date: Fri, 29 May 2026 13:46:28 GMT
• Title: Graph Neural Networks Are Not Continuous Across Graph Resolutions
• Abstract summary: We show that graph neural networks (GNNs) are not continuous with respect to all natural modes of graph convergence.<n>We derive a principled modification to standard GNN architectures which equips models with continuity across scales.
• Score: 59.362933392877956
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We show that contrary to conventional wisdom in the community, graph neural networks (GNNs) are not continuous with respect to all natural modes of graph convergence. As a result, GNNs may generate substantially different latent representations for graphs that are very similar. In particular they assign vastly different latent embeddings to graphs that represent the same underlying object at different resolution scales. We trace this failure of continuity back to a structural obstruction arising from commonly used information-propagation schemes. Building on this insight we then derive a principled modification to standard GNN architectures which equips models with continuity across scales. The proposed modification enables consistent integration of distinct resolutions and reliable generalization between them. We systematically validate our theoretical findings in a wide range of numerical experiments.

Related papers

• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes.<n>We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs.<n>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 of Geometric Graph Neural Networks with Lipschitz Loss Functions [84.01980526069075]
  We study the generalization capabilities of geometric graph neural networks (GNNs)<n>We prove a generalization gap between the optimal empirical risk and the optimal statistical risk of this GNN.<n>We verify this theoretical result with experiments on multiple real-world datasets.
  arXiv  Detail & Related papers  (2024-09-08T18:55:57Z)
• Generalization of Graph Neural Networks is Robust to Model Mismatch [84.01980526069075]
  Graph neural networks (GNNs) have demonstrated their effectiveness in various tasks supported by their generalization capabilities. In this paper, we examine GNNs that operate on geometric graphs generated from manifold models. Our analysis reveals the robustness of the GNN generalization in the presence of such model mismatch.
  arXiv  Detail & Related papers  (2024-08-25T16:00:44Z)
• 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.<n>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)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Towards Better Generalization with Flexible Representation of Multi-Module Graph Neural Networks [0.27195102129094995]
  We use a random graph generator to investigate how the graph size and structural properties affect the predictive performance of GNNs. We present specific evidence that the average node degree is a key feature in determining whether GNNs can generalize to unseen graphs. We propose a multi- module GNN framework that allows the network to adapt flexibly to new graphs by generalizing a single canonical nonlinear transformation over aggregated inputs.
  arXiv  Detail & Related papers  (2022-09-14T12:13:59Z)
• Implicit vs Unfolded Graph Neural Networks [29.803948965931212]
  We show that implicit and unfolded GNNs can achieve strong node classification accuracy across disparate regimes.<n>While IGNN is substantially more memory-efficient, UGNN models support unique, integrated graph attention mechanisms and propagation rules.
  arXiv  Detail & Related papers  (2021-11-12T07:49:16Z)
• Generalization of graph network inferences in higher-order graphical models [5.33024001730262]
  Probabilistic graphical models provide a powerful tool to describe complex statistical structure. inferences such as marginalization are intractable for general graphs. We define the Recurrent Factor Graph Neural Network (RF-GNN) to achieve fast approximate inference on graphical models that involve many-variable interactions.
  arXiv  Detail & Related papers  (2021-07-12T20:51:27Z)

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.