How Graph Neural Networks Learn: Lessons from Training Dynamics

• URL: http://arxiv.org/abs/2310.05105v3
• Date: Tue, 18 Jun 2024 07:34:39 GMT
• Title: How Graph Neural Networks Learn: Lessons from Training Dynamics
• Authors: Chenxiao Yang, Qitian Wu, David Wipf, Ruoyu Sun, Junchi Yan,
• Abstract summary: We study the training dynamics in function space of graph neural networks (GNNs) We find that the gradient descent optimization of GNNs implicitly leverages the graph structure to update the learned function. This finding offers new interpretable insights into when and why the learned GNN functions generalize.
• Score: 80.41778059014393
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A long-standing goal in deep learning has been to characterize the learning behavior of black-box models in a more interpretable manner. For graph neural networks (GNNs), considerable advances have been made in formalizing what functions they can represent, but whether GNNs will learn desired functions during the optimization process remains less clear. To fill this gap, we study their training dynamics in function space. In particular, we find that the gradient descent optimization of GNNs implicitly leverages the graph structure to update the learned function, as can be quantified by a phenomenon which we call \emph{kernel-graph alignment}. We provide theoretical explanations for the emergence of this phenomenon in the overparameterized regime and empirically validate it on real-world GNNs. This finding offers new interpretable insights into when and why the learned GNN functions generalize, highlighting their limitations in heterophilic graphs. Practically, we propose a parameter-free algorithm that directly uses a sparse matrix (i.e. graph adjacency) to update the learned function. We demonstrate that this embarrassingly simple approach can be as effective as GNNs while being orders-of-magnitude faster.

Related papers

• Heuristic Learning with Graph Neural Networks: A Unified Framework for Link Prediction [25.87108956561691]
  Link prediction is a fundamental task in graph learning, inherently shaped by the topology of the graph. We propose a unified matrix formulation to accommodate and generalize various weights. We also propose the Heuristic Learning Graph Neural Network (HL-GNN) to efficiently implement the formulation.
  arXiv  Detail & Related papers  (2024-06-12T08:05:45Z)
• Graph Neural Networks Provably Benefit from Structural Information: A Feature Learning Perspective [53.999128831324576]
  Graph neural networks (GNNs) have pioneered advancements in graph representation learning. This study investigates the role of graph convolution within the context of feature learning theory.
  arXiv  Detail & Related papers  (2023-06-24T10:21:11Z)
• Simple yet Effective Gradient-Free Graph Convolutional Networks [20.448409424929604]
  Linearized Graph Neural Networks (GNNs) have attracted great attention in recent years for graph representation learning. In this paper, we relate over-smoothing with the vanishing gradient phenomenon and craft a gradient-free training framework. Our methods achieve better and more stable performances on node classification tasks with varying depths and cost much less training time.
  arXiv  Detail & Related papers  (2023-02-01T11:00:24Z)
• GNNInterpreter: A Probabilistic Generative Model-Level Explanation for Graph Neural Networks [25.94529851210956]
  We propose a model-agnostic model-level explanation method for different Graph Neural Networks (GNNs) that follow the message passing scheme, GNNInterpreter. GNNInterpreter learns a probabilistic generative graph distribution that produces the most discriminative graph pattern the GNN tries to detect. Compared to existing works, GNNInterpreter is more flexible and computationally efficient in generating explanation graphs with different types of node and edge features.
  arXiv  Detail & Related papers  (2022-09-15T07:45:35Z)
• Learning to Evolve on Dynamic Graphs [5.1521870302904125]
  Learning to Evolve on Dynamic Graphs (LEDG) is a novel algorithm that jointly learns graph information and time information. LEDG is model-agnostic and can train any message passing based graph neural network (GNN) on dynamic graphs.
  arXiv  Detail & Related papers  (2021-11-13T04:09:30Z)
• Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depth [57.10183643449905]
  Graph Neural Networks (GNNs) have been studied from the lens of expressive power and generalization. We study the dynamics of GNNs by studying deep skip optimization. Our results provide first theoretical support for the success of GNNs.
  arXiv  Detail & Related papers  (2021-05-10T17:59:01Z)
• Fast Learning of Graph Neural Networks with Guaranteed Generalizability: One-hidden-layer Case [93.37576644429578]
  Graph neural networks (GNNs) have made great progress recently on learning from graph-structured data in practice. We provide a theoretically-grounded generalizability analysis of GNNs with one hidden layer for both regression and binary classification problems.
  arXiv  Detail & Related papers  (2020-06-25T00:45:52Z)
• Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
  It is known that the current graph neural networks (GNNs) are difficult to make themselves deep due to the problem known as over-smoothing. Multi-scale GNNs are a promising approach for mitigating the over-smoothing problem. We derive the optimization and generalization guarantees of transductive learning algorithms that include multi-scale GNNs.
  arXiv  Detail & Related papers  (2020-06-15T17:06:17Z)
• XGNN: Towards Model-Level Explanations of Graph Neural Networks [113.51160387804484]
  Graphs neural networks (GNNs) learn node features by aggregating and combining neighbor information. GNNs are mostly treated as black-boxes and lack human intelligible explanations. We propose a novel approach, known as XGNN, to interpret GNNs at the model-level.
  arXiv  Detail & Related papers  (2020-06-03T23:52:43Z)

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.