Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons

• URL: http://arxiv.org/abs/2306.13926v3
• Date: Fri, 06 Jun 2025 15:58:22 GMT
• Title: Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons
• Authors: Wei Huang, Yuan Cao, Haonan Wang, Xin Cao, Taiji Suzuki,
• Abstract summary: Graph networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data.<n>There remains a lack of analysis comparing GNNs and generalizations from an optimization and generalization perspective.
• Score: 50.33260238739837
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph neural networks (GNNs) have demonstrated remarkable capabilities in learning from graph-structured data, often outperforming traditional Multilayer Perceptrons (MLPs) in numerous graph-based tasks. Although existing works have demonstrated the benefits of graph convolution through Laplacian smoothing, expressivity or separability, there remains a lack of quantitative analysis comparing GNNs and MLPs from an optimization and generalization perspective. This study aims to address this gap by examining the role of graph convolution through feature learning theory. Using a signal-noise data model, we conduct a comparative analysis of the optimization and generalization between two-layer graph convolutional networks (GCNs) and their MLP counterparts. Our approach tracks the trajectory of signal learning and noise memorization in GNNs, characterizing their post-training generalization. We reveal that GNNs significantly prioritize signal learning, thus enhancing the regime of {low test error} over MLPs by $D^{q-2}$ times, where $D$ denotes a node's expected degree and $q$ is the power of ReLU activation function with $q>2$. This finding highlights a substantial and quantitative discrepancy between GNNs and MLPs in terms of optimization and generalization, a conclusion further supported by our empirical simulations on both synthetic and real-world datasets.

Related papers

• 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)
• CNN2GNN: How to Bridge CNN with GNN [59.42117676779735]
  We propose a novel CNN2GNN framework to unify CNN and GNN together via distillation. The performance of distilled boosted'' two-layer GNN on Mini-ImageNet is much higher than CNN containing dozens of layers such as ResNet152.
  arXiv  Detail & Related papers  (2024-04-23T08:19:08Z)
• Learning to Reweight for Graph Neural Network [63.978102332612906]
  Graph Neural Networks (GNNs) show promising results for graph tasks. Existing GNNs' generalization ability will degrade when there exist distribution shifts between testing and training graph data. We propose a novel nonlinear graph decorrelation method, which can substantially improve the out-of-distribution generalization ability.
  arXiv  Detail & Related papers  (2023-12-19T12:25:10Z)
• Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNS [0.0]
  We analyze the performance of graph neural network (GNN) architectures from the perspective of random graph theory. We show how both specific higher-order structures in synthetic data and the mix of empirical structures in real data have dramatic effects on GNN performance.
  arXiv  Detail & Related papers  (2023-10-11T17:16:33Z)
• Label Deconvolution for Node Representation Learning on Large-scale Attributed Graphs against Learning Bias [75.44877675117749]
  We propose an efficient label regularization technique, namely Label Deconvolution (LD), to alleviate the learning bias by a novel and highly scalable approximation to the inverse mapping of GNNs. Experiments demonstrate LD significantly outperforms state-of-the-art methods on Open Graph datasets Benchmark.
  arXiv  Detail & Related papers  (2023-09-26T13:09:43Z)
• Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs [71.93227401463199]
  This paper pinpoints the major source of GNNs' performance gain to their intrinsic capability, by introducing an intermediate model class dubbed as P(ropagational)MLP. We observe that PMLPs consistently perform on par with (or even exceed) their GNN counterparts, while being much more efficient in training.
  arXiv  Detail & Related papers  (2022-12-18T08:17:32Z)
• Neighborhood Convolutional Network: A New Paradigm of Graph Neural Networks for Node Classification [12.062421384484812]
  Graph Convolutional Network (GCN) decouples neighborhood aggregation and feature transformation in each convolutional layer. In this paper, we propose a new paradigm of GCN, termed Neighborhood Convolutional Network (NCN) In this way, the model could inherit the merit of decoupled GCN for aggregating neighborhood information, at the same time, develop much more powerful feature learning modules.
  arXiv  Detail & Related papers  (2022-11-15T02:02:51Z)
• 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)
• Parameter Convex Neural Networks [13.42851919291587]
  We propose the exponential multilayer neural network (EMLP) which is convex with regard to the parameters of the neural network under some conditions. For late experiments, we use the same architecture to make the exponential graph convolutional network (EGCN) and do the experiment on the graph classificaion dataset.
  arXiv  Detail & Related papers  (2022-06-11T16:44:59Z)
• Graph Partner Neural Networks for Semi-Supervised Learning on Graphs [16.489177915147785]
  Graph Convolutional Networks (GCNs) are powerful for processing graphstructured data and have achieved state-of-the-art performance in several tasks such as node classification, link prediction, and graph classification. It is inevitable for deep GCNs to suffer from an over-smoothing issue that the representations of nodes will tend to be indistinguishable after repeated graph convolution operations. We propose the Graph Partner Neural Network (GPNN) which incorporates a de- parameterized GCN and a parameter-sharing scheme.
  arXiv  Detail & Related papers  (2021-10-18T10:56:56Z)
• Increase and Conquer: Training Graph Neural Networks on Growing Graphs [116.03137405192356]
  We consider the problem of learning a graphon neural network (WNN) by training GNNs on graphs sampled Bernoulli from the graphon. Inspired by these results, we propose an algorithm to learn GNNs on large-scale graphs that, starting from a moderate number of nodes, successively increases the size of the graph during training.
  arXiv  Detail & Related papers  (2021-06-07T15:05:59Z)
• Variational models for signal processing with Graph Neural Networks [3.5939555573102853]
  This paper is devoted to signal processing on point-clouds by means of neural networks. In this work, we investigate the use of variational models for such Graph Neural Networks to process signals on graphs for unsupervised learning.
  arXiv  Detail & Related papers  (2021-03-30T13:31:11Z)
• Node2Seq: Towards Trainable Convolutions in Graph Neural Networks [59.378148590027735]
  We propose a graph network layer, known as Node2Seq, to learn node embeddings with explicitly trainable weights for different neighboring nodes. For a target node, our method sorts its neighboring nodes via attention mechanism and then employs 1D convolutional neural networks (CNNs) to enable explicit weights for information aggregation. In addition, we propose to incorporate non-local information for feature learning in an adaptive manner based on the attention scores.
  arXiv  Detail & Related papers  (2021-01-06T03:05:37Z)
• How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks [80.55378250013496]
  We study how neural networks trained by gradient descent extrapolate what they learn outside the support of the training distribution. Graph Neural Networks (GNNs) have shown some success in more complex tasks.
  arXiv  Detail & Related papers  (2020-09-24T17:48:59Z)

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.