Spectral Perturbations of the Line Graph Laplacian

2019-10-21

The graph Laplacian is an important tool in Graph Signal Processing (GSP) as its eigenvalue decomposition acts as an analogue to the Fourier transform and is known as the Graph Fourier Transform (GFT). The line graph has a GFT that is a direct analogue to the Discrete Cosine Transform Type II (DCT-II). Leveraging Fourier transform properties, one can then define processing operations on this graph structure that is loosely analogous to processing operations encountered in Digital Signal Processing (DSP) theory. This raises the question of whether well defined DSP-like operations can be derived from the GFT for more complex graph structures. One potential approach to this problem is to perturb simple graph structures and study the perturbation's impact on the graph Laplacian. This paper explores this idea by examining the eigenvalue decomposition of the Laplacian of undirected line graphs that undergo a single edge weight perturbation. This single perturbation can perturb either an existing edge weight or create new edge between distant unconnected vertices. The eigenvalue bounds are expressed in closed form and agree with simulated examples. The theory can be extended to include multiple perturbations such that the GFT can be defined for a more general graph structure.

📄 PDF Abstract BibTeX arXiv:1910.09617

Code (0)

등록된 구현이 없습니다.

Average Sensitivity of Spectral Clustering

2020-06-07 · Pan Peng, Yuichi Yoshida

Spectral clustering is one of the most popular clustering methods for finding clusters in a graph, which has found many applications in data mining. However, the input graph in those applications may have many missing ed…

Clustering Sensitivity

From Eigenmodes to Proofs: Integrating Graph Spectral Operators with Symbolic Interpretable Reasoning

2025-09-07 · Andrew Kiruluta, Priscilla Burity arxiv

We introduce Spectral NSR, a fully spectral neuro-symbolic reasoning framework that embeds logical rules as spectral templates and performs inference directly in the graph spectral domain. By leveraging graph signal proc…

Adversarial Robustness Domain Adaptation Knowledge Graphs

Laplacian-Based Dimensionality Reduction Including Spectral Clustering, Laplacian Eigenmap, Locality Preserving Projection, Graph Embedding, and Diffusion Map: Tutorial and Survey

2021-06-03 · Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, Mark Crowley

This is a tutorial and survey paper for nonlinear dimensionality and feature extraction methods which are based on the Laplacian of graph of data. We first introduce adjacency matrix, definition of Laplacian matrix, and …

Clustering Dimensionality Reduction Graph Embedding

Spectral Sparsification of Laplacian-Constrained Gaussian and Hüsler-Reiss Graphical Models

2026-06-15 · Ignacio Echave-Sustaeta Rodríguez, Aida Abiad, Frank Röttger arxiv

Graph Laplacians encode graph structures in matrix form, and thus facilitate the application of linear algebra to graph theory. In statistics, two related families of probabilistic graphical models can be parameterized b…

Graph structure learning Graph Learning

On spectral partitioning of signed graphs

2017-01-05 · Andrew V. Knyazev

We argue that the standard graph Laplacian is preferable for spectral partitioning of signed graphs compared to the signed Laplacian. Simple examples demonstrate that partitioning based on signs of components of the lead…