Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlations

• URL: http://arxiv.org/abs/2602.16145v1
• Date: Wed, 18 Feb 2026 02:36:33 GMT
• Title: Investigating GNN Convergence on Large Randomly Generated Graphs with Realistic Node Feature Correlations
• Authors: Mohammed Zain Ali Ahmed,
• Abstract summary: We will introduce a novel method to generate random graphs that have correlated node features.<n>The node features will be sampled in such a manner to ensure correlation between neighbouring nodes.<n>A theoretical analysis will strongly indicate that convergence can be avoided in some cases.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: There are a number of existing studies analysing the convergence behaviour of graph neural networks on large random graphs. Unfortunately, the majority of these studies do not model correlations between node features, which would naturally exist in a variety of real-life networks. Consequently, the derived limitations of GNNs, resulting from such convergence behaviour, is not truly reflective of the expressive power of GNNs when applied to realistic graphs. In this paper, we will introduce a novel method to generate random graphs that have correlated node features. The node features will be sampled in such a manner to ensure correlation between neighbouring nodes. As motivation for our choice of sampling scheme, we will appeal to properties exhibited by real-life graphs, particularly properties that are captured by the Barabási-Albert model. A theoretical analysis will strongly indicate that convergence can be avoided in some cases, which we will empirically validate on large random graphs generated using our novel method. The observed divergent behaviour provides evidence that GNNs may be more expressive than initial studies would suggest, especially on realistic graphs.

Related papers

• 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)
• Almost Surely Asymptotically Constant Graph Neural Networks [7.339728196535312]
  We show that the output converges to a constant function, which upper-bounds what these classifiers can uniformly express. This strong convergence phenomenon applies to a very wide class of GNNs, including state of the art models. We empirically validate these findings, observing that the convergence phenomenon appears not only on random graphs but also on some real-world graphs.
  arXiv  Detail & Related papers  (2024-03-06T17:40:26Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows.
  arXiv  Detail & Related papers  (2023-05-24T07:09:53Z)
• 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)
• Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification [14.112444998191698]
  We focus on graph classification using a graph neural network (GNN) model that precomputes the node features using a bank of neighborhood aggregation graph operators arranged in parallel. These GNN models have a natural advantage of reduced training and inference time due to the precomputations. We demonstrate via numerical experiments that the developed model achieves state-of-the-art performance on many diverse real-world datasets.
  arXiv  Detail & Related papers  (2021-11-22T19:19:40Z)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)
• 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)
• Explicit Pairwise Factorized Graph Neural Network for Semi-Supervised Node Classification [59.06717774425588]
  We propose the Explicit Pairwise Factorized Graph Neural Network (EPFGNN), which models the whole graph as a partially observed Markov Random Field. It contains explicit pairwise factors to model output-output relations and uses a GNN backbone to model input-output relations. We conduct experiments on various datasets, which shows that our model can effectively improve the performance for semi-supervised node classification on graphs.
  arXiv  Detail & Related papers  (2021-07-27T19:47:53Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.