How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing

• URL: http://arxiv.org/abs/2405.12474v1
• Date: Tue, 21 May 2024 03:28:45 GMT
• Title: How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing
• Authors: Keke Huang, Yu Guang Wang, Ming Li, and Pietro Liò,
• Abstract summary: Spectral Graph Networks (GNNs) have gained increasing prevalence for heterophily graphs. In an attempt to avert prohibitive computations, numerous filters have been proposed. We demystify the correlation between the spectral property of desired vectors and the heterophily degrees. We develop a novel adaptive heterophily basis wherein the basis mutually form angles reflecting the heterophily degree of the graph.
• Score: 24.857304431611464
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Spectral Graph Neural Networks (GNNs), alternatively known as graph filters, have gained increasing prevalence for heterophily graphs. Optimal graph filters rely on Laplacian eigendecomposition for Fourier transform. In an attempt to avert prohibitive computations, numerous polynomial filters have been proposed. However, polynomials in the majority of these filters are predefined and remain fixed across different graphs, failing to accommodate the varying degrees of heterophily. Addressing this gap, we demystify the intrinsic correlation between the spectral property of desired polynomial bases and the heterophily degrees via thorough theoretical analyses. Subsequently, we develop a novel adaptive heterophily basis wherein the basis vectors mutually form angles reflecting the heterophily degree of the graph. We integrate this heterophily basis with the homophily basis to construct a universal polynomial basis UniBasis, which devises a polynomial filter based graph neural network - UniFilter. It optimizes the convolution and propagation in GNN, thus effectively limiting over-smoothing and alleviating over-squashing. Our extensive experiments, conducted on a diverse range of real-world and synthetic datasets with varying degrees of heterophily, support the superiority of UniFilter. These results not only demonstrate the universality of UniBasis but also highlight its proficiency in graph explanation.

Related papers

• Addressing Heterogeneity and Heterophily in Graphs: A Heterogeneous Heterophilic Spectral Graph Neural Network [48.05273145974434]
  We propose a Heterogeneous Heterophilic Spectral Graph Neural Network (H2SGNN) H2SGNN employs a dual-module approach: local independent filtering and global hybrid filtering. Extensive empirical evaluations on four real-world datasets demonstrate the superiority of H2SGNN compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2024-10-17T09:23:53Z)
• GrassNet: State Space Model Meets Graph Neural Network [57.62885438406724]
  Graph State Space Network (GrassNet) is a novel graph neural network with theoretical support that provides a simple yet effective scheme for designing arbitrary graph spectral filters. To the best of our knowledge, our work is the first to employ SSMs for the design of graph GNN spectral filters. Extensive experiments on nine public benchmarks reveal that GrassNet achieves superior performance in real-world graph modeling tasks.
  arXiv  Detail & Related papers  (2024-08-16T07:33:58Z)
• Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach [36.06398179717066]
  We develop an adaptive graph filter based on Krylov subspaces to filter complex graphs. We conduct extensive experiments across a series of real-world datasets.
  arXiv  Detail & Related papers  (2024-03-12T06:26:17Z)
• Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction [55.57072563835959]
  spectral graph neural networks are characterized by filters. We propose an eigenvalue correction strategy that can free filters from the constraints of repeated eigenvalue inputs.
  arXiv  Detail & Related papers  (2024-01-28T08:12:00Z)
• An Effective Universal Polynomial Basis for Spectral Graph Neural Networks [12.725906836609811]
  Spectral Graph Neural Networks (GNNs) have gained increasing prevalence for heterophily graphs. We develop an adaptive heterophily basis by incorporating graph heterophily degrees. We then integrate this heterophily basis with the homophily basis, creating a universal basis UniBasis.
  arXiv  Detail & Related papers  (2023-11-30T01:48:42Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• Spectral Heterogeneous Graph Convolutions via Positive Noncommutative Polynomials [34.74726720818622]
  We present Positive Spectral Heterogeneous Graph Convolutional Network (PSHGCN) PSHGCN offers a simple yet effective method for learning valid heterogeneous graph filters. PSHGCN exhibits remarkable scalability, efficiently handling large real-world graphs comprising millions of nodes and edges.
  arXiv  Detail & Related papers  (2023-05-31T14:09:42Z)
• Specformer: Spectral Graph Neural Networks Meet Transformers [51.644312964537356]
  Spectral graph neural networks (GNNs) learn graph representations via spectral-domain graph convolutions. We introduce Specformer, which effectively encodes the set of all eigenvalues and performs self-attention in the spectral domain. By stacking multiple Specformer layers, one can build a powerful spectral GNN.
  arXiv  Detail & Related papers  (2023-03-02T07:36:23Z)
• Stability to Deformations of Manifold Filters and Manifold Neural Networks [89.53585099149973]
  The paper defines and studies manifold (M) convolutional filters and neural networks (NNs) The main technical contribution of the paper is to analyze the stability of manifold filters and MNNs to smooth deformations of the manifold.
  arXiv  Detail & Related papers  (2021-06-07T15:41:03Z)
• Stacked Graph Filter [19.343260981528186]
  We study Graph Convolutional Networks (GCN) from the graph signal processing viewpoint. We find that by stacking graph filters with learnable solution parameters, we can build a highly adaptive and robust graph classification model.
  arXiv  Detail & Related papers  (2020-11-22T11:20:14Z)

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.