Proves generic existence of spectral networks for many cases.
problem Existence of spectral networks for a broad range of spectral data.
method Generic existence proof for spectral networks.
result Proves existence for a large class of spectral data.
Graph convolutional networks fail to use eigenvectors beyond the first, unlike spectral embedding.
problem Understanding when graph convolutional networks fail compared to spectral embedding.
method Presented a simple generative model to illustrate failure.
result Graph convolutional networks fail to use eigenvectors beyond the first in certain graphs.
Introduces Spectral Graph Network combining spatial and spectral message passing.
problem Relational reasoning in graph structured data.
method Applies message passing to both spatial and spectral domains of a graph.
result Promotes efficient training with fewer iterations and robustness to edge dropout.
Graph convolutional networks(GCNs) have become the most popular approaches for graph data in these days because of their powerful ability to extract features from graph. GCNs approaches are divided into two categories, spectral-based and spatial-based. As the earliest convolutional networks for graph data, spectral-bas…
The paper bridges spectral and spatial graph convolutions, improving model capacity and transferability.
problem Improving graph neural networks by bridging spectral and spatial design.
method Theoretical demonstration and general framework for spectral analysis, new spectral convolutions, and depthwise separable convolutions.
result General framework allows spectral analysis of ConvGNNs, showing their performance and limits, and proposing new spectral convolutions.
SpGAT learns graph representations using spectral attention for efficiency.
problem Efficiently capturing global graph patterns with minimal parameters.
method Introduces Spectral Graph Attention Network (SpGAT) using spectral domain attention mechanisms and a fast Chebychev approximation.
result SpGAT achieves better global pattern recognition with fewer parameters compared to GAT.
Novel Haar-Laplacian for directed graphs enhances spectral graph applications.
problem Lack of suitable Laplacian for directed graphs in spectral graph theory.
method Inspired by Haar-like transformation, introduces a Hermitian matrix preserving direction and weight.
result HaarNet outperforms in weight prediction and denoising on directed graphs.
Spectral Graph Convolutional Networks (GCNs) are a generalization of convolutional networks to learning on graph-structured data. Applications of spectral GCNs have been successful, but limited to a few problems where the graph is fixed, such as shape correspondence and node classification. In this work, we address thi…
Paper revisits graph-CNNs using Laplace-Beltrami spectral filters and polynomials.
problem Improving spectral graph convolutional neural networks (graph-CNNs).
method Developed Laplace-Beltrami CNN (LB-CNN) by replacing graph Laplacian with LB operator and approximating spectral filters using Chebyshev, Laguerre, and Hermite polynomials.
result Classification accuracy of LB-CNN is not dependent on the type of polynomials or operators.
New neural architectures invariant to sign flips and basis symmetries for graph representation learning.
problem Learning invariant graph representations from eigenvectors.
method SignNet and BasisNet neural architectures that are invariant to sign flips and basis symmetries.
result Proven to be universal, approximating any continuous function of eigenvectors with desired invariances.
New methods for clustering graphs using spectral analysis.
problem Graph clustering for complex systems.
method Transfer operators and spectral properties.
result Spectral clustering can be interpreted using Koopman operators.
New spectral clustering method for graphs with uneven node degrees.
problem Challenges in community detection for graphs with heterogeneous degree distributions.
method Spectral clustering on spherical coordinates with degree correction.
result Improved performance in representing computer networks.
New equivariant filters improve graph classification.
problem Designing deep learning models for graph symmetries.
method Nonlinear spectral filters (NLSFs) that are equivariant to graph functional shifts.
result NLSFs outperform existing spectral GNNs in graph classification.
Study identifies cancer genes through graph anomaly analysis of protein interactions.
problem Insufficient modeling of biological information in protein interaction networks for cancer gene identification.
method Proposes HIerarchical-Perspective Graph Neural Network (HIPGNN) to detect weight heterogeneity and spectral flattening in cancer gene nodes.
result HIPGNN detects weight heterogeneity and spectral flattening, leading to improved cancer gene identification.
This study bridges the gap between spatial and spectral GNNs.
problem Lack of direct comparison and cross-reference of existing GNNs.
method Systematically categorizes and examines GNNs into spatial and spectral domains.
result Establishes a strong relationship between spatial and spectral GNNs.
Enhances graph neural networks with spectral and topological information.
problem Improving graph neural networks' expressivity beyond Weisfeiler-Leman hierarchy.
method Integrates spectral information into Persistent Homology diagrams.
result SpectRe is strictly more expressive than PH and spectral information alone.
Spectral graph sparsification preserves geometry of GNN embeddings.
problem Maintaining geometric properties of graph neural network embeddings during sparsification.
method Proving spectral sparsification preserves squared pairwise distances, class means, and covariance structure in embedding space.
result Spectral sparsification preserves the geometry of learned embeddings in GNNs.
Graph embedding method captures both local and global network structure.
problem Representing and analyzing complex graph networks.
method Spectral embedding based on a generalized graph Laplacian.
result Significant improvement in data analysis tasks.
New centrality-based graph shift operators improve graph neural networks.
problem Improving graph neural networks by enhancing graph shift operators.
method Proposed Centrality Graph Shift Operators (CGSOs) using global centrality metrics.
result CGSOs lead to improved performance in graph neural networks on real-world datasets.
Spectro-Riemannian Graph Neural Networks integrate spectral and curvature signals for better graph representation learning.
problem Enhance graph representation learning by leveraging spectral and curvature signals.
method Proposes Spectro-Riemannian Graph Neural Networks (CUSP) that combines spectral and curvature insights.
result Empirical evaluation shows CUSP outperforms state-of-the-art models by up to 5.3%.
Developed a framework for designing filters in spectral GCNNs with improved performance.
problem Designing effective filters for spectral GCNNs with regularization properties.
method Exploring regularization properties of graph Laplacian and proposing a generalized framework for filter design.
result New filters derived from the framework outperform state-of-the-art techniques in semi-supervised node classification.
FoSR adds edges to graphs to prevent oversquashing and oversmoothing in GNNs.
problem Oversquashing and oversmoothing in graph neural networks (GNNs).
method First-order spectral rewiring to add edges based on spectral expansion, combined with a relational architecture.
result Our algorithm outperforms existing graph rewiring methods in graph classification tasks.
IGT learns graph representations without supervision.
problem Building deep unsupervised graph representations.
method Generic complex-valued spectral graph architecture from Fourier transform generalization, greedy concave objective for discriminative and invariant features.
result IGT learns both discriminative and invariant features from graph topology.
KCoreMotif clusters large networks efficiently by exploiting k-core decomposition and motifs.
problem Efficiently clustering large networks for trust evaluation.
method Exploits k-core decomposition and motifs to perform motif-based spectral clustering on k-core subgraphs.
result The proposed algorithm is accurate and efficient for large networks.
Dual regularized graph Laplacian improves spectral clustering for community detection.
problem Detecting clusters in networks with improved spectral clustering methods.
method Proposes dual regularized graph Laplacian for three spectral clustering approaches.
result Theoretical analysis shows DRSC and DRSLIM yield stable consistent community detection.
We present graph wavelet neural network (GWNN), a novel graph convolutional neural network (CNN), leveraging graph wavelet transform to address the shortcomings of previous spectral graph CNN methods that depend on graph Fourier transform. Different from graph Fourier transform, graph wavelet transform can be obtained …
Graph convolutional networks (GCNs) are powerful tools for graph-structured data. However, they have been recently shown to be vulnerable to topological attacks. To enhance adversarial robustness, we go beyond spectral graph theory to robust graph theory. By challenging the classical graph Laplacian, we propose a new c…
Novel GNN for signed and directed networks using magnetic signed Laplacian.
problem Efficiently modeling signed and directed networks for tasks like clustering and link prediction.
method Introduced a magnetic signed Laplacian for directed signed graphs, used it to construct a spectral GNN.
result Demonstrated effective performance on tasks involving signed and directional information.
This paper explains GNNs using graph signal denoising.
problem Understanding how GNNs work for node representation learning.
method Spectral graph convolutional networks and graph attention networks are analyzed from the perspective of graph signal denoising.
result GNNs implicitly solve graph signal denoising problems.
Graph pruning improves neural network performance by addressing squashing and smoothing issues.
problem Over-squashing and over-smoothing in Graph Neural Networks.
method Proposes edge deletions to simultaneously address over-squashing and over-smoothing, optimizing spectral gap.
result Edge deletions improve generalization and distinguishability of nodes of different classes.
This paper develops a coreset method for GNNs that speeds up training on large graphs.
problem Training Graph Neural Networks (GNNs) on large-scale graphs is computationally expensive.
method The paper proposes a spectral greedy coreset (SGGC) method that selects ego-graphs based on spectral embeddings.
result SGGC significantly speeds up GNN training on large graphs and outperforms other coreset methods.
Graphon pooling preserves spectral properties in GNNs, reducing overfitting.
problem Unclear pooling and sampling strategies in GNNs that alter graph structure.
method Modeling graph layers as elements of a sequence converging to a graphon.
result Graphon pooling GNNs reduce overfitting and improve performance.
Graph classification improved using spectral features and wavelet filters.
problem Categorizing graphs based on their structure and node attributes.
method Derived spectral features from graph signal processing, designed two Gaussian process models: one simple and one sophisticated.
result Simple and sophisticated Gaussian process models yield competitive performance, including well-calibrated uncertainty estimates.
New method clusters evolving networks using spatio-temporal graph Laplacian.
problem Clustering communities in time-varying graphs.
method Extends spectral clustering to dynamic graphs using CCA and spatio-temporal graph Laplacian.
result The spatio-temporal graph Laplacian clearly interprets cluster evolution over time.
Paper introduces a new metric to select optimal Graph Shift Operator for GNNs.
problem Empirical selection of Graph Shift Operator remains challenging.
method Introduces a novel alignment gain metric connecting geometric distortion to generalization bounds via spectral proxy.
result Provides a principled, computation-efficient criterion to rank and select optimal GSO.
FastGAT reduces GNN computation time by 10x using graph sparsification.
problem High computational burden in attention-based GNNs.
method Spectral sparsification to generate optimal graph pruning.
result Per-epoch time is almost linear in graph nodes, reducing computational time by up to 10x.
LASE learns graph embeddings by unrolling GD iterations into a neural network.
problem Learning graph embeddings from graph inputs.
method Truncating and interpreting GD iterations as layers in a GNN.
result LASE outperforms eigendecomposition routines and GNNs in link prediction and node classification.
Fiedler regularization uses spectral graph theory to improve neural network performance.
problem Improving neural network performance by penalizing weights based on connectivity.
method Uses the Fiedler value of the neural network's graph as a regularization tool, providing theoretical and computational methods.
result Demonstrates Fiedler regularization's effectiveness in improving neural network performance.
Graph neural networks can be adapted to new graphs with a limit object called graphon NNs.
problem Transferability of graph neural networks across different graphs.
method Introduced graphon NNs as limit objects of GNNs and proved a bound on the difference between GNN and graphon-NN outputs.
result The bound on the difference between GNN and graphon-NN outputs vanishes with growing number of nodes if the graph convolutional filters are bandlimited.
Unified framework for analyzing graph neural operators converging to graph limits.
problem Analyzing convergence of graph neural operators to graph limits.
method Develops a unified spectral framework for graph neural operators under various graphon assumptions.
result Unified framework enables direct comparison of convergence rates and tradeoffs.
Detects graph topology changes from noisy signals using prior spectral information.
problem Detecting changes in graph topology from graph signals.
method Leverages graph filtering and subspace detection to distill problem into a CUSUM-based algorithm.
result Demonstrates the effectiveness of incorporating prior spectral signatures for change-point detection.
The random dot product graph (RDPG) is an independent-edge random graph that is analytically tractable and, simultaneously, either encompasses or can successfully approximate a wide range of random graphs, from relatively simple stochastic block models to complex latent position graphs. In this survey paper, we describ…
A new method boosts graph neural networks by preventing over-smoothing and over-squashing.
problem Graph Neural Networks struggle with long-range signals and over-smoothing/over-squashing.
method Proposes PowerEmbed, a layer-wise normalization technique inspired by spectral graph embedding.
result PowerEmbed prevents over-smoothing and avoids over-squashing, improving performance on heterophilous graphs.
Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to reuse information of past cluster assignments to expedite computation. Our approach builds on a recent idea of sidestepping the main bottleneck of spectral clusterin…
Simplicial complexes are increasingly used to study complex system structure and dynamics including diffusion, synchronization and epidemic spreading. The spectral dimension of the graph Laplacian is known to determine the diffusion properties at long time scales. Using the renormalization group here we calculate the s…
Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social networks, representing people who communicate with each other, are one example. Communities or clusters of highly connected actors form an essential feature in the structure of several emp…
This paper focuses on spectral graph convolutional neural networks (ConvNets), where filters are defined as elementwise multiplication in the frequency domain of a graph. In machine learning settings where the dataset consists of signals defined on many different graphs, the trained ConvNet should generalize to signals…
Biological and social systems consist of myriad interacting units. The interactions can be represented in the form of a graph or network. Measurements of these graphs can reveal the underlying structure of these interactions, which provides insight into the systems that generated the graphs. Moreover, in applications s…