SF-GRASS: Solver-Free Graph Spectral Sparsification

• URL: http://arxiv.org/abs/2008.07633v1
• Date: Mon, 17 Aug 2020 21:37:19 GMT
• Title: SF-GRASS: Solver-Free Graph Spectral Sparsification
• Authors: Ying Zhang, Zhiqiang Zhao, Zhuo Feng
• Abstract summary: This work introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing techniques. We show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks.
• Score: 16.313489255657203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent spectral graph sparsification techniques have shown promising performance in accelerating many numerical and graph algorithms, such as iterative methods for solving large sparse matrices, spectral partitioning of undirected graphs, vectorless verification of power/thermal grids, representation learning of large graphs, etc. However, prior spectral graph sparsification methods rely on fast Laplacian matrix solvers that are usually challenging to implement in practice. This work, for the first time, introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing (GSP) techniques. We introduce a local spectral embedding scheme for efficiently identifying spectrally-critical edges that are key to preserving graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. Since the key kernel functions in SF-GRASS can be efficiently implemented using sparse-matrix-vector-multiplications (SpMVs), the proposed spectral approach is simple to implement and inherently parallel friendly. Our extensive experimental results show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks when compared with the prior state-of-the-art spectral method.

Related papers

• 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)
• Spectral Graph Reasoning Network for Hyperspectral Image Classification [0.43512163406551996]
  Convolutional neural networks (CNNs) have achieved remarkable performance in hyperspectral image (HSI) classification. We propose a spectral graph reasoning network (SGR) learning framework comprising two crucial modules. Experiments on two HSI datasets demonstrate that the proposed architecture can significantly improve the classification accuracy.
  arXiv  Detail & Related papers  (2024-07-02T20:29:23Z)
• inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition [4.6193503399184275]
  inGRASS is a novel algorithm designed for incremental spectral sparsification of large undirected graphs. The proposed algorithm is highly scalable and parallel-friendly, having a nearly-linear time complexity for the setup phase. In experiments, inGRASS achieves up to over $200 times$ speedups while retaining comparable solution quality.
  arXiv  Detail & Related papers  (2024-02-26T19:49:54Z)
• 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)
• A Sparse Graph Formulation for Efficient Spectral Image Segmentation [0.0]
  Spectral Clustering is one of the most traditional methods to solve segmentation problems. We adopt a sparse graph formulation based on the inclusion of extra nodes to a simple grid graph. Applying the original Normalized Cuts algorithm to this graph leads to a simple and scalable method for spectral image segmentation.
  arXiv  Detail & Related papers  (2023-06-22T19:06:27Z)
• 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)
• SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements [16.313489255657203]
  spectral graph densification framework (SGL) for learning resistor networks with linear measurements. solver-free method (SF-SGL) that exploits multilevel spectral approximation of the graphs. EDA algorithm for vectorless power/thermal integrity verifications.
  arXiv  Detail & Related papers  (2023-02-09T00:33:19Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• Gaussian Processes on Graphs via Spectral Kernel Learning [9.260186030255081]
  We propose a graph spectrum-based Gaussian process for prediction of signals defined on nodes of the graph. We demonstrate the interpretability of the model in synthetic experiments from which we show the various ground truth spectral filters can be accurately recovered.
  arXiv  Detail & Related papers  (2020-06-12T17:51:22Z)
• Spectral Graph Attention Network with Fast Eigen-approximation [103.93113062682633]
  Spectral Graph Attention Network (SpGAT) learns representations for different frequency components regarding weighted filters and graph wavelets bases. Fast approximation variant SpGAT-Cheby is proposed to reduce the computational cost brought by the eigen-decomposition. We thoroughly evaluate the performance of SpGAT and SpGAT-Cheby in semi-supervised node classification tasks.
  arXiv  Detail & Related papers  (2020-03-16T21:49:34Z)
• Embedding Graph Auto-Encoder for Graph Clustering [90.8576971748142]
  Graph auto-encoder (GAE) models are based on semi-supervised graph convolution networks (GCN) We design a specific GAE-based model for graph clustering to be consistent with the theory, namely Embedding Graph Auto-Encoder (EGAE) EGAE consists of one encoder and dual decoders.
  arXiv  Detail & Related papers  (2020-02-20T09:53:28Z)

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.