Spectral GNN via Two-dimensional (2-D) Graph Convolution

• URL: http://arxiv.org/abs/2404.04559v1
• Date: Sat, 6 Apr 2024 08:53:26 GMT
• Title: Spectral GNN via Two-dimensional (2-D) Graph Convolution
• Authors: Guoming Li, Jian Yang, Shangsong Liang, Dongsheng Luo,
• Abstract summary: We show that existing spectral GNNs remain critical drawbacks in performing the spectral graph convolution. We propose a new convolution paradigm, named 2-D graph convolution. We prove that 2-D graph convolution unifies existing graph convolution paradigms, and is capable to construct arbitrary target output.
• Score: 26.79625547648669
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Spectral Graph Neural Networks (GNNs) have achieved tremendous success in graph learning. As an essential part of spectral GNNs, spectral graph convolution extracts crucial frequency information in graph data, leading to superior performance of spectral GNNs in downstream tasks. However, in this paper, we show that existing spectral GNNs remain critical drawbacks in performing the spectral graph convolution. Specifically, considering the spectral graph convolution as a construction operation towards target output, we prove that existing popular convolution paradigms cannot construct the target output with mild conditions on input graph signals, causing spectral GNNs to fall into suboptimal solutions. To address the issues, we rethink the spectral graph convolution from a more general two-dimensional (2-D) signal convolution perspective and propose a new convolution paradigm, named 2-D graph convolution. We prove that 2-D graph convolution unifies existing graph convolution paradigms, and is capable to construct arbitrary target output. Based on the proposed 2-D graph convolution, we further propose ChebNet2D, an efficient and effective GNN implementation of 2-D graph convolution through applying Chebyshev interpolation. Extensive experiments on benchmark datasets demonstrate both effectiveness and efficiency of the ChebNet2D.

Related papers

• Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks [6.080095317098909]
  Graph Neural Networks (GNNs) have shown great promise in modeling relationships between nodes in a graph. Previous studies have primarily attempted to utilize the information from higher-order neighbors in the graph. We make a fundamental observation: the regular and the Hadamard power of the Laplacian matrix behave similarly in the spectrum. We propose a novel graph convolutional operator based on the sparse Sobolev norm of graph signals.
  arXiv  Detail & Related papers  (2024-11-07T09:53:11Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  The ubiquity of large-scale graphs in node-classification tasks hinders the real-world applications of Graph Neural Networks (GNNs) This paper studies graph coresets for GNNs and avoids the interdependence issue by selecting ego-graphs based on their spectral embeddings. Our spectral greedy graph coreset (SGGC) scales to graphs with millions of nodes, obviates the need for model pre-training, and applies to low-homophily graphs.
  arXiv  Detail & Related papers  (2024-05-27T17:52:12Z)
• Graph Distillation with Eigenbasis Matching [43.59076214528843]
  We propose Graph Distillation with Eigenbasis Matching (GDEM) to replace the real large graph. GDEM aligns the eigenbasis and node features of real and synthetic graphs. It directly replicates the spectrum of the real graph and thus prevents the influence of GNNs.
  arXiv  Detail & Related papers  (2023-10-13T15:48:12Z)
• 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)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
  Graph Neural Networks (GNNs) rely on graph convolutions to exploit meaningful patterns in networked data. We propose to learn GNNs on very large graphs by leveraging the limit object of a sequence of growing graphs, the graphon.
  arXiv  Detail & Related papers  (2022-10-27T16:00:45Z)
• How Powerful are Spectral Graph Neural Networks [9.594432031144715]
  Spectral Graph Neural Network is a kind of Graph Neural Network based on graph signal filters. We first prove that even spectral GNNs without nonlinearity can produce arbitrary graph signals. We also establish a connection between the expressive power of spectral GNNs and Graph Isomorphism (GI) testing.
  arXiv  Detail & Related papers  (2022-05-23T10:22:12Z)
• Adaptive Kernel Graph Neural Network [21.863238974404474]
  Graph neural networks (GNNs) have demonstrated great success in representation learning for graph-structured data. In this paper, we propose a novel framework - i.e., namely Adaptive Kernel Graph Neural Network (AKGNN) AKGNN learns to adapt to the optimal graph kernel in a unified manner at the first attempt. Experiments are conducted on acknowledged benchmark datasets and promising results demonstrate the outstanding performance of our proposed AKGNN.
  arXiv  Detail & Related papers  (2021-12-08T20:23:58Z)
• Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning [63.97983530843762]
  Graph Neural Networks (GNNs) have achieved great success in graph representation learning. GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order tests, are inefficient as they cannot sparsity of underlying graph structure. We propose Distance Depiction (DE) as a new class of graph representation learning.
  arXiv  Detail & Related papers  (2020-08-31T23:15:40Z)
• Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks [8.563354084119062]
  We show some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. The proposed framework is used to design new convolutions in spectral domain with a custom frequency profile while applying them in the spatial domain.
  arXiv  Detail & Related papers  (2020-03-26T01:49:24Z)
• Graphon Pooling in Graph Neural Networks [169.09536309161314]
  Graph neural networks (GNNs) have been used effectively in different applications involving the processing of signals on irregular structures modeled by graphs. We propose a new strategy for pooling and sampling on GNNs using graphons which preserves the spectral properties of the graph.
  arXiv  Detail & Related papers  (2020-03-03T21:04:20Z)

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.