Adaptive and Interpretable Graph Convolution Networks Using Generalized Pagerank

• URL: http://arxiv.org/abs/2108.10636v1
• Date: Tue, 24 Aug 2021 10:39:14 GMT
• Title: Adaptive and Interpretable Graph Convolution Networks Using Generalized Pagerank
• Abstract summary: We propose AdaGPR to learn generalized Pageranks at each layer of a GCNII network. We show that the generalization bound for AdaGPR is bounded by the eigenvalue spectrum of the normalized adjacency matrix.
• Score: 44.22407074673142
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate adaptive layer-wise graph convolution in deep GCN models. We propose AdaGPR to learn generalized Pageranks at each layer of a GCNII network to induce adaptive convolution. We show that the generalization bound for AdaGPR is bounded by a polynomial of the eigenvalue spectrum of the normalized adjacency matrix in the order of the number of generalized Pagerank coefficients. By analysing the generalization bounds we show that oversmoothing depends on both the convolutions by the higher orders of the normalized adjacency matrix and the depth of the model. We performed evaluations on node-classification using benchmark real data and show that AdaGPR provides improved accuracies compared to existing graph convolution networks while demonstrating robustness against oversmoothing. Further, we demonstrate that analysis of coefficients of layer-wise generalized Pageranks allows us to qualitatively understand convolution at each layer enabling model interpretations.

Related papers

• Topology-Aware PAC-Bayesian Generalization Analysis for Graph Neural Networks [21.139538521229273]
  We propose a topology-aware PAC-Bayesian norm-based generalization framework for graph convolutional networks (GCNs)<n>By imposing different structures on sensitivity matrices from both spatial and spectral perspectives, we derive a family of generalization error bounds with graph structures embedded.<n> Notably, the proposed framework explicitly integrates graph structural properties into the generalization analysis, enabling a unified inspection of GNN generalization behavior.
  arXiv  Detail & Related papers  (2026-04-12T09:52:27Z)
• 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. 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)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• GRANOLA: Adaptive Normalization for Graph Neural Networks [28.993479890213617]
  We propose a graph-adaptive normalization layer, GRANOLA, for Graph Neural Network (GNN) layers. Unlike existing normalization layers, GRANOLA normalizes node features by adapting to the specific characteristics of the graph. Our empirical evaluation of various graph benchmarks underscores the superior performance of GRANOLA over existing normalization techniques.
  arXiv  Detail & Related papers  (2024-04-20T10:44:13Z)
• A Unified Approach to Controlling Implicit Regularization via Mirror Descent [18.536453909759544]
  Mirror descent (MD) is a notable generalization of gradient descent (GD) We show that MD can be implemented efficiently and enjoys fast convergence under suitable conditions.
  arXiv  Detail & Related papers  (2023-06-24T03:57:26Z)
• 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)
• Graph Polynomial Convolution Models for Node Classification of Non-Homophilous Graphs [52.52570805621925]
  We investigate efficient learning from higher-order graph convolution and learning directly from adjacency matrix for node classification. We show that the resulting model lead to new graphs and residual scaling parameter. We demonstrate that the proposed methods obtain improved accuracy for node-classification of non-homophilous parameters.
  arXiv  Detail & Related papers  (2022-09-12T04:46:55Z)
• SLGCN: Structure Learning Graph Convolutional Networks for Graphs under Heterophily [5.619890178124606]
  We propose a structure learning graph convolutional networks (SLGCNs) to alleviate the issue from two aspects. Specifically, we design a efficient-spectral-clustering with anchors (ESC-ANCH) approach to efficiently aggregate feature representations from all similar nodes. Experimental results on a wide range of benchmark datasets illustrate that the proposed SLGCNs outperform the stat-of-the-art GNN counterparts.
  arXiv  Detail & Related papers  (2021-05-28T13:00:38Z)
• Generalization bounds for graph convolutional neural networks via Rademacher complexity [0.3553493344868413]
  We study the sample complexity of graph convolutional networks (GCNs) with a single hidden layer. Theses derived complexity bounds explicitly depend on the largest eigenvalue of graph convolution filter and the degree distribution of the graph.
  arXiv  Detail & Related papers  (2021-02-20T02:51:13Z)
• When Does Preconditioning Help or Hurt Generalization? [74.25170084614098]
  We show how the textitimplicit bias of first and second order methods affects the comparison of generalization properties. We discuss several approaches to manage the bias-variance tradeoff, and the potential benefit of interpolating between GD and NGD.
  arXiv  Detail & Related papers  (2020-06-18T17:57:26Z)
• Infinitely Wide Graph Convolutional Networks: Semi-supervised Learning via Gaussian Processes [144.6048446370369]
  Graph convolutional neural networks(GCNs) have recently demonstrated promising results on graph-based semi-supervised classification. We propose a GP regression model via GCNs(GPGC) for graph-based semi-supervised learning. We conduct extensive experiments to evaluate GPGC and demonstrate that it outperforms other state-of-the-art methods.
  arXiv  Detail & Related papers  (2020-02-26T10:02:32Z)

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.