Analysis of Graph Neural Networks with Theory of Markov Chains

• URL: http://arxiv.org/abs/2211.06605v1
• Date: Sat, 12 Nov 2022 08:03:57 GMT
• Title: Analysis of Graph Neural Networks with Theory of Markov Chains
• Authors: Weichen Zhao, Chenguang Wang, Congying Han, Tiande Guo
• Abstract summary: We study emphover-smoothing which is an important problem in GNN research. We give the conclusion that operator-consistent GNN cannot avoid over-smoothing at an exponential rate in the Markovian sense. We propose a regularization term which can be flexibly added to the training of the neural network.
• Score: 2.017675281820044
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: In this paper, we provide a theoretical tool for the interpretation and analysis of \emph{graph neural networks} (GNNs). We use Markov chains on graphs to mathematically model the forward propagation processes of GNNs. The graph neural networks are divided into two classes of operator-consistent and operator-inconsistent based on whether the Markov chains are time-homogeneous. Based on this, we study \emph{over-smoothing} which is an important problem in GNN research. We attribute the over-smoothing problem to the convergence of an arbitrary initial distribution to a stationary distribution. We prove the effectiveness of the previous methods for alleviating the over-smoothing problem. Further, we give the conclusion that operator-consistent GNN cannot avoid over-smoothing at an exponential rate in the Markovian sense. For operator-inconsistent GNN, we theoretically give a sufficient condition for avoiding over-smoothing. Based on this condition, we propose a regularization term which can be flexibly added to the training of the neural network. Finally, we design experiments to verify the effectiveness of this condition. Results show that our proposed sufficient condition not only improves the performance but also alleviates the over-smoothing phenomenon.

Related papers

• Graph neural networks and non-commuting operators [4.912318087940015]
  We develop a limit theory of graphon-tuple neural networks and use it to prove a universal transferability theorem. Our theoretical results extend well-known transferability theorems for GNNs to the case of several simultaneous graphs. We derive a training procedure that provably enforces the stability of the resulting model.
  arXiv  Detail & Related papers  (2024-11-06T21:17:14Z)
• Spiking Graph Neural Network on Riemannian Manifolds [51.15400848660023]
  Graph neural networks (GNNs) have become the dominant solution for learning on graphs. Existing spiking GNNs consider graphs in Euclidean space, ignoring the structural geometry. We present a Manifold-valued Spiking GNN (MSG) MSG achieves superior performance to previous spiking GNNs and energy efficiency to conventional GNNs.
  arXiv  Detail & Related papers  (2024-10-23T15:09:02Z)
• Non-convolutional Graph Neural Networks [46.79328529882998]
  We design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network. RUM achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.
  arXiv  Detail & Related papers  (2024-07-31T21:29:26Z)
• Understanding Oversmoothing in Diffusion-Based GNNs From the Perspective of Operator Semigroup Theory [12.327920883065238]
  This paper presents an analytical study of the oversmoothing issue in diffusion-based Graph Neural Networks (GNNs) We rigorously prove that oversmoothing is intrinsically linked to the ergodicity of the diffusion operator. Our experimental results reveal that this ergodicity-breaking term effectively mitigates oversmoothing measured by Dirichlet energy.
  arXiv  Detail & Related papers  (2024-02-23T13:44:57Z)
• Neural Tangent Kernels Motivate Graph Neural Networks with Cross-Covariance Graphs [94.44374472696272]
  We investigate NTKs and alignment in the context of graph neural networks (GNNs) Our results establish the theoretical guarantees on the optimality of the alignment for a two-layer GNN. These guarantees are characterized by the graph shift operator being a function of the cross-covariance between the input and the output data.
  arXiv  Detail & Related papers  (2023-10-16T19:54:21Z)
• Bregman Graph Neural Network [27.64062763929748]
  In node classification tasks, the smoothing effect induced by GNNs tends to assimilate representations and over-homogenize labels of connected nodes. We propose a novel bilevel optimization framework for GNNs inspired by the notion of Bregman distance.
  arXiv  Detail & Related papers  (2023-09-12T23:54:24Z)
• Demystifying Oversmoothing in Attention-Based Graph Neural Networks [23.853636836842604]
  Oversmoothing in Graph Neural Networks (GNNs) refers to the phenomenon where increasing network depth leads to homogeneous node representations. Previous work has established that Graph Convolutional Networks (GCNs) exponentially lose expressive power. It remains controversial whether the graph attention mechanism can mitigate oversmoothing.
  arXiv  Detail & Related papers  (2023-05-25T14:31:59Z)
• 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)
• Generalizing Graph Neural Networks on Out-Of-Distribution Graphs [51.33152272781324]
  Graph Neural Networks (GNNs) are proposed without considering the distribution shifts between training and testing graphs. In such a setting, GNNs tend to exploit subtle statistical correlations existing in the training set for predictions, even though it is a spurious correlation. We propose a general causal representation framework, called StableGNN, to eliminate the impact of spurious correlations.
  arXiv  Detail & Related papers  (2021-11-20T18:57:18Z)
• 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)
• Stochastic Graph Neural Networks [123.39024384275054]
  Graph neural networks (GNNs) model nonlinear representations in graph data with applications in distributed agent coordination, control, and planning. Current GNN architectures assume ideal scenarios and ignore link fluctuations that occur due to environment, human factors, or external attacks. In these situations, the GNN fails to address its distributed task if the topological randomness is not considered accordingly.
  arXiv  Detail & Related papers  (2020-06-04T08:00:00Z)

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.