SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements

• URL: http://arxiv.org/abs/2302.04384v1
• Date: Thu, 9 Feb 2023 00:33:19 GMT
• Title: SF-SGL: Solver-Free Spectral Graph Learning from Linear Measurements
• Authors: Ying Zhang, Zhiqiang Zhao, Zhuo Feng
• Abstract summary: 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.
• Score: 16.313489255657203
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work introduces a highly-scalable spectral graph densification framework (SGL) for learning resistor networks with linear measurements, such as node voltages and currents. We show that the proposed graph learning approach is equivalent to solving the classical graphical Lasso problems with Laplacian-like precision matrices. We prove that given $O(\log N)$ pairs of voltage and current measurements, it is possible to recover sparse $N$-node resistor networks that can well preserve the effective resistance distances on the original graph. In addition, the learned graphs also preserve the structural (spectral) properties of the original graph, which can potentially be leveraged in many circuit design and optimization tasks. To achieve more scalable performance, we also introduce a solver-free method (SF-SGL) that exploits multilevel spectral approximation of the graphs and allows for a scalable and flexible decomposition of the entire graph spectrum (to be learned) into multiple different eigenvalue clusters (frequency bands). Such a solver-free approach allows us to more efficiently identify the most spectrally-critical edges for reducing various ranges of spectral embedding distortions. Through extensive experiments for a variety of real-world test cases, we show that the proposed approach is highly scalable for learning sparse resistor networks without sacrificing solution quality. We also introduce a data-driven EDA algorithm for vectorless power/thermal integrity verifications to allow estimating worst-case voltage/temperature (gradient) distributions across the entire chip by leveraging a few voltage/temperature measurements.

Related papers

• Point Cloud Denoising With Fine-Granularity Dynamic Graph Convolutional Networks [58.050130177241186]
  Noise perturbations often corrupt 3-D point clouds, hindering downstream tasks such as surface reconstruction, rendering, and further processing. This paper introduces finegranularity dynamic graph convolutional networks called GDGCN, a novel approach to denoising in 3-D point clouds.
  arXiv  Detail & Related papers  (2024-11-21T14:19:32Z)
• Interpretable Lightweight Transformer via Unrolling of Learned Graph Smoothness Priors [16.04850782310842]
  We build interpretable and lightweight transformer-like neural networks by unrolling iterative optimization algorithms. A normalized signal-dependent graph learning module amounts to a variant of the basic self-attention mechanism in conventional transformers.
  arXiv  Detail & Related papers  (2024-06-06T14:01:28Z)
• Graph Generation via Spectral Diffusion [51.60814773299899]
  We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix. Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• ASWT-SGNN: Adaptive Spectral Wavelet Transform-based Self-Supervised Graph Neural Network [20.924559944655392]
  This paper proposes an Adaptive Spectral Wavelet Transform-based Self-Supervised Graph Neural Network (ASWT-SGNN) ASWT-SGNN accurately approximates the filter function in high-density spectral regions, avoiding costly eigen-decomposition. It achieves comparable performance to state-of-the-art models in node classification tasks.
  arXiv  Detail & Related papers  (2023-12-10T03:07:42Z)
• SGL: Spectral Graph Learning from Measurements [4.721069729610892]
  This work introduces a highly scalable spectral graph densification framework for learning resistor networks with linear measurements. We show that the proposed approach is highly scalable for learning ultra-sparse resistor networks without sacrificing solution quality.
  arXiv  Detail & Related papers  (2021-04-16T03:01:15Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• SF-GRASS: Solver-Free Graph Spectral Sparsification [16.313489255657203]
  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.
  arXiv  Detail & Related papers  (2020-08-17T21:37:19Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)
• Multipole Graph Neural Operator for Parametric Partial Differential Equations [57.90284928158383]
  One of the main challenges in using deep learning-based methods for simulating physical systems is formulating physics-based data. We propose a novel multi-level graph neural network framework that captures interaction at all ranges with only linear complexity. Experiments confirm our multi-graph network learns discretization-invariant solution operators to PDEs and can be evaluated in linear time.
  arXiv  Detail & Related papers  (2020-06-16T21:56:22Z)
• 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)

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.