Finding Nearly-Periodic Components in Digraphs and Markov Chains from the Spectrum of Rotated Laplacian Matrices

Jul 16, 2026

Spectral algorithms are developed for detecting periodic structures in directed graphs (digraphs) by using the spectrum of rotated Laplacian matrices. The paper generalizes the bipartiteness ratio via a periodicity ratio tied to rotated Laplacians, and proves that for a strongly connected digraph representing a Markov chain, this ratio quantitatively measures closeness to periodicity of order p. A randomized polynomial-time variant is analyzed to find many nearly periodic components with small periodicity ratios, yielding a higher-order Cheeger-type inequality. Additionally, a probabilistic result bounds mismatch indices for correlated complex Gaussian maximizers.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages43

Reading Time1 h 48 min

Abstract

Introduction

Background: Laplacian spectrum and Cheeger inequalities

Rotated adjacency matrices and z-rotated Laplacians

Goal: periodic structure detection in digraphs and Markov chains

Finding Nearly-Periodic Components in Digraphs and Markov Chains from the Spectrum of Rotated Laplacian Matrices Salil Vadhan ∗ Harvard University Jiyu Zhang† Bocconi University arXiv :2607 . 1 1333v 1 [ cs .DS] 13 Jul 2026 Abstract Inspired by recent advances in notions of spectral approximation of digraphs [Ahm+20], we study spectral algorithms for finding periodic structures in digraphs via the spectrum of a class of rotated Laplacian matrices. This class of Laplacian matrices was previously studied by Lange, Liu, Peyerimhoff, and Post [Lan+15] . We consider a notion of periodicity ratio that generalizes the bipartiteness ratio of Trevisan [Tre09], and show that it is closely related to the spectrum of rotated Laplacian matrices. In particular, if the digraph is strongly connected and represents a Markov chain, this periodicity ratio for a given p ∈ N is a quantitative measure of how close this Markov chain is to having periodicity p. We propose and analyze a periodicity-ratio variant of the spectral algorithm by Louis, Raghavendra, Tetali and Vempala [Lou+12] . We show that the algorithm runs in randomized polynomial time and can find many nearly periodic components (i.e, components with small periodicity ratio) . This also implies a new higher-order Cheeger-type inequality for periodicity in the spirit of that in [Lou+12; LOT14] . As part of our analysis, we prove a new theorem that upper bounds the probability that the largest magnitudes of two sequences of coordinate-wise correlated complex Gaussian random variables occur at different indices, which may be of independent interest. Previously, an analogous result was known only for real Gaussian random variables. 1 Introduction Spectral graph theory studies the combinatorial properties of a graph by studying its associated matrices, most commonly the Laplacian matrix. For a graph G = (V, E), the normalized Laplacian matrix associated with G is the matrix L = I − D −1/2AD −1/2, where D is the diagonal degree matrix and A is the adjacency matrix. In this introduction, for simplicity we will mostly restrict our discussion to unweighted graphs. However, all results presented in this paper extend to general weighted graphs, and proofs are provided for the weighted case. A common theme in spectral graph theory is that the spectrum of the Laplacian matrix encodes the connectivity of the graph, and the eigenvectors constitute a geometric embedding of the vertices. Formally, we define the edge expansion of a set S ⊆ V as ∗ salil [vadhan@harvard.edu](vadhan@harvard.edu) Supported in part by a Simons Investigator Award †[jiyu.zhang@phd.unibocconi.it](jiyu.zhang@phd.unibocconi.it) Part of the work was done while visiting EPFL ϕ (S) = | E (S, V − S)| Pv∈S dv where E (S, V − S) is the set of edges between S and V − S and dv is the degree, i.e, the number of edges connected to the vertex v. The fundamental Cheeger’s Inequality states that Theorem 1.1 . [AM85; Alo86] For a graph G = (V = [n], E) , let λ 1 = 0 ≤ λ2 ≤ · · · ≤ λn ≤ 2 bethe eigenvalues of its associated normalized Laplacian matrix L = I − D−1/2AD −1/2 . We have λ2 /2 ≤ min ϕ (S) ≤ p2λ2 S⊆V,|S|≤|V |/2 Cheeger’s Inequality shows that the first non-trivial eigenvalue (i.e, λ 2 ) of the Laplacian matrix associated with a graph is a quantitative measure of the disconnectivity of the graph. In particular, if λ2 = 0, then there exists a subset S such that ϕ (S) = 0, meaning that the vertices in S are disconnected with the rest ofthe graph. A line of work by Lee, Oveis-Gharan, Trevisan [LOT14] and Louis, Raghavendra, Tetali, Vempala [Lou+12] has established higher-order Cheeger’s Inequalities, relating higher eigenvalues of the Laplacian to the existence of partitions of the vertex set into many non-expanding pieces. This line of work has provided a theoretical justification for the success of spectral clustering techniques [NJW01; Von07], in which the spectral embedding of the vertices is comput

FAQs

What notion of periodicity does the paper introduce for digraphs?

It defines a periodicity ratio that generalizes the bipartiteness ratio, and relates this ratio directly to the spectrum of z-rotated Laplacian matrices.

How does the method connect to Markov chains?

When the digraph is strongly connected and represents a Markov chain, the periodicity ratio for a given p measures how close the chain is to having periodicity p.

What performance guarantees are proved for the proposed spectral algorithm?

The paper analyzes a periodicity-ratio variant of a previous spectral algorithm and shows it runs in randomized polynomial time while finding many nearly periodic components with small periodicity ratios.

Jul 16, 2026

Upload by Clementine