Stability and Generalization of lp-Regularized Stochastic Learning for GCN

• URL: http://arxiv.org/abs/2305.12085v3
• Date: Tue, 20 Jun 2023 03:27:32 GMT
• Title: Stability and Generalization of lp-Regularized Stochastic Learning for GCN
• Authors: Shiyu Liu, Linsen Wei, Shaogao Lv and Ming Li
• Abstract summary: Graph convolutional networks (GCN) are viewed as one of the most popular representations among the variants of graph neural networks over graph data. This paper aims to quantify the trade-off of GCN between smoothness and sparsity, with the help of a general $ell_p$-regularized $ (1pleq 2)$ learning algorithm.
• Score: 9.517209629978057
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Graph convolutional networks (GCN) are viewed as one of the most popular representations among the variants of graph neural networks over graph data and have shown powerful performance in empirical experiments. That $\ell_2$-based graph smoothing enforces the global smoothness of GCN, while (soft) $\ell_1$-based sparse graph learning tends to promote signal sparsity to trade for discontinuity. This paper aims to quantify the trade-off of GCN between smoothness and sparsity, with the help of a general $\ell_p$-regularized $(1<p\leq 2)$ stochastic learning proposed within. While stability-based generalization analyses have been given in prior work for a second derivative objectiveness function, our $\ell_p$-regularized learning scheme does not satisfy such a smooth condition. To tackle this issue, we propose a novel SGD proximal algorithm for GCNs with an inexact operator. For a single-layer GCN, we establish an explicit theoretical understanding of GCN with the $\ell_p$-regularized stochastic learning by analyzing the stability of our SGD proximal algorithm. We conduct multiple empirical experiments to validate our theoretical findings.

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. 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)
• ResNorm: Tackling Long-tailed Degree Distribution Issue in Graph Neural Networks via Normalization [80.90206641975375]
  This paper focuses on improving the performance of GNNs via normalization. By studying the long-tailed distribution of node degrees in the graph, we propose a novel normalization method for GNNs. The $scale$ operation of ResNorm reshapes the node-wise standard deviation (NStd) distribution so as to improve the accuracy of tail nodes.
  arXiv  Detail & Related papers  (2022-06-16T13:49:09Z)
• RawlsGCN: Towards Rawlsian Difference Principle on Graph Convolutional Network [102.27090022283208]
  Graph Convolutional Network (GCN) plays pivotal roles in many real-world applications. GCN often exhibits performance disparity with respect to node degrees, resulting in worse predictive accuracy for low-degree nodes. We formulate the problem of mitigating the degree-related performance disparity in GCN from the perspective of the Rawlsian difference principle.
  arXiv  Detail & Related papers  (2022-02-28T05:07:57Z)
• Towards Efficient Graph Convolutional Networks for Point Cloud Handling [181.59146413326056]
  We aim at improving the computational efficiency of graph convolutional networks (GCNs) for learning on point clouds. A series of experiments show that optimized networks have reduced computational complexity, decreased memory consumption, and accelerated inference speed.
  arXiv  Detail & Related papers  (2021-04-12T17:59:16Z)
• Wide Graph Neural Networks: Aggregation Provably Leads to Exponentially Trainability Loss [17.39060566854841]
  Graph convolutional networks (GCNs) and their variants have achieved great success in dealing with graph-structured data. It is well known that deep GCNs will suffer from over-smoothing problem. Few theoretical analyses have been conducted to study the expressivity and trainability of deep GCNs.
  arXiv  Detail & Related papers  (2021-03-03T11:06:12Z)
• Revisiting Graph Convolutional Network on Semi-Supervised Node Classification from an Optimization Perspective [10.178145000390671]
  Graph convolutional networks (GCNs) have achieved promising performance on various graph-based tasks. However they suffer from over-smoothing when stacking more layers. We present a quantitative study on this observation and develop novel insights towards the deeper GCN.
  arXiv  Detail & Related papers  (2020-09-24T03:36:43Z)
• Regularization Matters: A Nonparametric Perspective on Overparametrized Neural Network [20.132432350255087]
  Overparametrized neural networks trained by tangent descent (GD) can provably overfit any training data. This paper studies how well overparametrized neural networks can recover the true target function in the presence of random noises.
  arXiv  Detail & Related papers  (2020-07-06T01:02:23Z)
• 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)
• 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)
• Better Theory for SGD in the Nonconvex World [2.6397379133308214]
  Large-scale non optimization problems are ubiquitous in modern machine learning. We perform experiments on the effects of a wide array of synthetic minibatch sizes on the Gradient Descent (SG) problem.
  arXiv  Detail & Related papers  (2020-02-09T09:56:06Z)

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.