Signed Graph Neural Networks: A Frequency Perspective
- URL: http://arxiv.org/abs/2208.07323v1
- Date: Mon, 15 Aug 2022 16:42:18 GMT
- Title: Signed Graph Neural Networks: A Frequency Perspective
- Authors: Rahul Singh and Yongxin Chen
- Abstract summary: Graph convolutional networks (GCNs) are designed for unsigned graphs containing only positive links.
We propose two different signed graph neural networks, one keeps only low-frequency information and one also retains high-frequency information.
- Score: 14.386571627652975
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Graph convolutional networks (GCNs) and its variants are designed for
unsigned graphs containing only positive links. Many existing GCNs have been
derived from the spectral domain analysis of signals lying over (unsigned)
graphs and in each convolution layer they perform low-pass filtering of the
input features followed by a learnable linear transformation. Their extension
to signed graphs with positive as well as negative links imposes multiple
issues including computational irregularities and ambiguous frequency
interpretation, making the design of computationally efficient low pass filters
challenging. In this paper, we address these issues via spectral analysis of
signed graphs and propose two different signed graph neural networks, one keeps
only low-frequency information and one also retains high-frequency information.
We further introduce magnetic signed Laplacian and use its eigendecomposition
for spectral analysis of directed signed graphs. We test our methods for node
classification and link sign prediction tasks on signed graphs and achieve
state-of-the-art performances.
Related papers
- Geometric Graph Filters and Neural Networks: Limit Properties and
Discriminability Trade-offs [122.06927400759021]
We study the relationship between a graph neural network (GNN) and a manifold neural network (MNN) when the graph is constructed from a set of points sampled from the manifold.
We prove non-asymptotic error bounds showing that convolutional filters and neural networks on these graphs converge to convolutional filters and neural networks on the continuous manifold.
arXiv Detail & Related papers (2023-05-29T08:27:17Z) - 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) - A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphs [13.954735096637298]
We analyze how sparsity affects the graph spectra, and thus the performance of graph neural networks (GNNs) in node classification on dense and sparse graphs.
We show that GNNs can outperform spectral methods on sparse graphs, and illustrate these results with numerical examples on both synthetic and real graphs.
arXiv Detail & Related papers (2022-11-06T22:38:13Z) - Spectral Graph Convolutional Networks With Lifting-based Adaptive Graph
Wavelets [81.63035727821145]
Spectral graph convolutional networks (SGCNs) have been attracting increasing attention in graph representation learning.
We propose a novel class of spectral graph convolutional networks that implement graph convolutions with adaptive graph wavelets.
arXiv Detail & Related papers (2021-08-03T17:57:53Z) - Beyond Low-pass Filtering: Graph Convolutional Networks with Automatic
Filtering [61.315598419655224]
We propose Automatic Graph Convolutional Networks (AutoGCN) to capture the full spectrum of graph signals.
While it is based on graph spectral theory, our AutoGCN is also localized in space and has a spatial form.
arXiv Detail & Related papers (2021-07-10T04:11:25Z) - BiGCN: A Bi-directional Low-Pass Filtering Graph Neural Network [35.97496022085212]
Many graph convolutional networks can be regarded as low-pass filters for graph signals.
We propose a new model, BiGCN, which represents a graph neural network as a bi-directional low-pass filter.
Our model outperforms previous graph neural networks in the tasks of node classification and link prediction on most of the benchmark datasets.
arXiv Detail & Related papers (2021-01-14T09:41:00Z) - Graph Autoencoders with Deconvolutional Networks [32.78113728062279]
Graph Deconvolutional Networks (GDNs) reconstruct graph signals from smoothed node representations.
We motivate the design of Graph Deconvolutional Networks via a combination of inverse filters in spectral domain and de-noising layers in wavelet domain.
Based on the proposed GDN, we propose a graph autoencoder framework that first encodes smoothed graph representations with GCN and then decodes accurate graph signals with GDN.
arXiv Detail & Related papers (2020-12-22T09:49:39Z) - An Experimental Study of the Transferability of Spectral Graph Networks [5.736353542430439]
Spectral graph convolutional networks are generalizations of standard convolutional networks for graph-structured data using the Laplacian operator.
Recent works have proved the stability of spectral filters under graph benchmarks.
arXiv Detail & Related papers (2020-12-18T14:15:07Z) - Dirichlet Graph Variational Autoencoder [65.94744123832338]
We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors.
Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
arXiv Detail & Related papers (2020-10-09T07:35:26Z) - 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.