Not too little, not too much: a theoretical analysis of graph (over)smoothing

• URL: http://arxiv.org/abs/2205.12156v1
• Date: Tue, 24 May 2022 15:39:31 GMT
• Title: Not too little, not too much: a theoretical analysis of graph (over)smoothing
• Abstract summary: We analyze graph smoothing with emphmean aggregation, where each node successively receives the average of the features of its neighbors. We show that graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together.
• Score: 8.7314407902481
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze graph smoothing with \emph{mean aggregation}, where each node successively receives the average of the features of its neighbors. Indeed, it has quickly been observed that Graph Neural Networks (GNNs), which generally follow some variant of Message-Passing (MP) with repeated aggregation, may be subject to the \emph{oversmoothing} phenomenon: by performing too many rounds of MP, the node features tend to converge to a non-informative limit. In the case of mean aggregation, for connected graphs, the node features become constant across the whole graph. At the other end of the spectrum, it is intuitively obvious that \emph{some} MP rounds are necessary, but existing analyses do not exhibit both phenomena at once: beneficial ``finite'' smoothing and oversmoothing in the limit. In this paper, we consider simplified linear GNNs, and rigorously analyze two examples for which a finite number of mean aggregation steps provably improves the learning performance, before oversmoothing kicks in. We consider a latent space random graph model, where node features are partial observations of the latent variables and the graph contains pairwise relationships between them. We show that graph smoothing restores some of the lost information, up to a certain point, by two phenomenon: graph smoothing shrinks non-principal directions in the data faster than principal ones, which is useful for regression, and shrinks nodes within communities faster than they collapse together, which improves classification.

Related papers

• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  We propose a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening.<n>We derive a faster variant NOPE*, which reduces O(dot d) interference evaluation to O(d) based on the local isotropy assumption.<n>Learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning.
  arXiv  Detail & Related papers  (2026-05-13T05:24:35Z)
• Semi-Supervised Learning on Graphs using Graph Neural Networks [7.3886152750469]
  Graph neural networks (GNNs) work remarkably well in semi-supervised node regression.<n>We study an aggregate-and-readout model that encompasses several common message passing architectures.<n>We prove a sharp non-asymptotic risk bound that separates errors approximation, convergence, and optimization.
  arXiv  Detail & Related papers  (2026-02-19T06:25:13Z)
• Oversmoothing as Loss of Sign: Towards Structural Balance in Graph Neural Networks [54.62268052283014]
  Oversmoothing is a common issue in graph neural networks (GNNs) Three major classes of anti-oversmoothing techniques can be mathematically interpreted as message passing over signed graphs. Negative edges can repel nodes to a certain extent, providing deeper insights into how these methods mitigate oversmoothing.
  arXiv  Detail & Related papers  (2025-02-17T03:25:36Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs [53.27010448621372]
  We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs with node attributes.<n>We prove a universal approximation theorem for GNNs and bounds generalization for GNNs on any data distribution of attributed graphs.<n>Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points.
  arXiv  Detail & Related papers  (2024-11-08T10:34:24Z)
• Generalization Bounds for Message Passing Networks on Mixture of Graphons [21.457225542391267]
  We study the generalization capabilities of Message Passing Neural Networks (MPNNs) We derive generalization bounds specifically for MPNNs with normalized sum aggregation and mean aggregation. Our results imply that MPNNs with higher complexity than the size of the training set can still generalize effectively.
  arXiv  Detail & Related papers  (2024-04-04T14:26:47Z)
• Random Geometric Graph Alignment with Graph Neural Networks [8.08963638000146]
  We show that a graph neural network can recover an unknown one-to-one mapping between the vertices of two graphs. We also prove that our conditions on the noise level are tight up to logarithmic factors. We demonstrate that when the noise level is at least constant this direct matching fails to have perfect recovery while the graph neural network can tolerate noise level growing as fast as a power of the size of the graph.
  arXiv  Detail & Related papers  (2024-02-12T00:18:25Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes. The efficient computation is enabled by a kernerlized Gumbel-Softmax operator. Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
  arXiv  Detail & Related papers  (2023-06-14T09:21:15Z)
• What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding [0.0]
  We aim to deepen the theoretical understanding of Graph Neural Networks (GNNs) on large graphs, with a focus on their expressive power. Recently, several works showed that, on very general random graphs models, GNNs converge to certains functions as the number of nodes grows.
  arXiv  Detail & Related papers  (2023-05-24T07:09:53Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  We propose a novel non-parametric subgraph matching framework, dubbed MatchExplainer, to explore explanatory subgraphs. It couples the target graph with other counterpart instances and identifies the most crucial joint substructure by minimizing the node corresponding-based distance. Experiments on synthetic and real-world datasets show the effectiveness of our MatchExplainer by outperforming all state-of-the-art parametric baselines with significant margins.
  arXiv  Detail & Related papers  (2023-01-07T05:14:45Z)
• Effects of Graph Convolutions in Deep Networks [8.937905773981702]
  We present a rigorous theoretical understanding of the effects of graph convolutions in multi-layer networks. We show that a single graph convolution expands the regime of the distance between the means where multi-layer networks can classify the data. We provide both theoretical and empirical insights into the performance of graph convolutions placed in different combinations among the layers of a network.
  arXiv  Detail & Related papers  (2022-04-20T08:24:43Z)
• Graph Denoising with Framelet Regularizer [25.542429117462547]
  This paper tailors regularizers for graph data in terms of both feature and structure noises. Our model achieves significantly better performance compared with popular graph convolutions even when the graph is heavily contaminated.
  arXiv  Detail & Related papers  (2021-11-05T05:17:23Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Towards Deeper Graph Neural Networks [63.46470695525957]
  Graph convolutions perform neighborhood aggregation and represent one of the most important graph operations. Several recent studies attribute this performance deterioration to the over-smoothing issue. We propose Deep Adaptive Graph Neural Network (DAGNN) to adaptively incorporate information from large receptive fields.
  arXiv  Detail & Related papers  (2020-07-18T01:11:14Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

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.