Predicting the Performance of Graph Convolutional Networks with Spectral Properties of the Graph Laplacian

• URL: http://arxiv.org/abs/2508.12993v2
• Date: Wed, 10 Sep 2025 15:06:14 GMT
• Title: Predicting the Performance of Graph Convolutional Networks with Spectral Properties of the Graph Laplacian
• Authors: Shalima Binta Manir, Tim Oates,
• Abstract summary: A common observation in the Graph Convolutional Network (GCN) literature is that stacking GCN layers may or may not result in better performance on tasks like node classification and edge prediction.<n>We have found empirically that a graph's algebraic connectivity, which is known as the Fiedler value, is a good predictor of GCN performance.
• Score: 3.7958475517455947
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A common observation in the Graph Convolutional Network (GCN) literature is that stacking GCN layers may or may not result in better performance on tasks like node classification and edge prediction. We have found empirically that a graph's algebraic connectivity, which is known as the Fiedler value, is a good predictor of GCN performance. Intuitively, graphs with similar Fiedler values have analogous structural properties, suggesting that the same filters and hyperparameters may yield similar results when used with GCNs, and that transfer learning may be more effective between graphs with similar algebraic connectivity. We explore this theoretically and empirically with experiments on synthetic and real graph data, including the Cora, CiteSeer and Polblogs datasets. We explore multiple ways of aggregating the Fiedler value for connected components in the graphs to arrive at a value for the entire graph, and show that it can be used to predict GCN performance. We also present theoretical arguments as to why the Fiedler value is a good predictor.

Related papers

• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph [19.222317334613162]
  Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes.<n>We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance.<n>We introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph.
  arXiv  Detail & Related papers  (2025-05-18T13:28:56Z)
• Disentangled Graph Representation Based on Substructure-Aware Graph Optimal Matching Kernel Convolutional Networks [4.912298804026689]
  Graphs effectively characterize relational data, driving graph representation learning methods.<n>Recent disentangled graph representation learning enhances interpretability by decoupling independent factors in graph data.<n>This paper proposes the Graph Optimal Matching Kernel Convolutional Network (GOMKCN) to address this limitation.
  arXiv  Detail & Related papers  (2025-04-23T02:26:33Z)
• A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
  We analyze how sparsity affects the graph spectra, and thus the performance of graph neural networks (GNNs) in node classification on dense and sparse graphs. We show that GNNs can outperform spectral methods on sparse graphs, and illustrate these results with numerical examples on both synthetic and real graphs.
  arXiv  Detail & Related papers  (2022-11-06T22:38:13Z)
• 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)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  Graph neural networks (GNNs) have been shown powerful capacity at modeling structural data. We present a novel Graph Matching based GNN Pre-Training framework, called GMPT. The proposed method can be applied to fully self-supervised pre-training and coarse-grained supervised pre-training.
  arXiv  Detail & Related papers  (2022-03-03T09:53:53Z)
• Graph Neural Networks for Graphs with Heterophily: A Survey [98.45621222357397]
  We provide a comprehensive review of graph neural networks (GNNs) for heterophilic graphs. Specifically, we propose a systematic taxonomy that essentially governs existing heterophilic GNN models. We discuss the correlation between graph heterophily and various graph research domains, aiming to facilitate the development of more effective GNNs.
  arXiv  Detail & Related papers  (2022-02-14T23:07:47Z)
• Benchmarking Graph Neural Networks on Link Prediction [80.2049358846658]
  We benchmark several existing graph neural network (GNN) models on different datasets for link predictions. Our experiments show these GNN architectures perform similarly on various benchmarks for link prediction tasks.
  arXiv  Detail & Related papers  (2021-02-24T20:57:16Z)
• Scalable Graph Neural Networks for Heterogeneous Graphs [12.44278942365518]
  Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks. In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities.
  arXiv  Detail & Related papers  (2020-11-19T06:03:35Z)
• Node Similarity Preserving Graph Convolutional Networks [51.520749924844054]
  Graph Neural Networks (GNNs) explore the graph structure and node features by aggregating and transforming information within node neighborhoods. We propose SimP-GCN that can effectively and efficiently preserve node similarity while exploiting graph structure. We validate the effectiveness of SimP-GCN on seven benchmark datasets including three assortative and four disassorative graphs.
  arXiv  Detail & Related papers  (2020-11-19T04:18:01Z)
• SAIL: Self-Augmented Graph Contrastive Learning [40.76236706250037]
  This paper studies learning node representations with graph neural networks (GNNs) for unsupervised scenario. We derive a theoretical analysis and provide an empirical demonstration about the non-steady performance of GNNs over different graph datasets.
  arXiv  Detail & Related papers  (2020-09-02T10:27:30Z)
• 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.