Asymmetry in Spectral Graph Theory: Harmonic Analysis on Directed Networks via Biorthogonal Bases

Abstract

The operator-theoretic dichotomy underlying diffusion on directed networks is symmetry versus non-self-adjointness of the Markov transition operator. In the reversible (detailedbalance) regime, a directed random walk P is self-adjoint in a stationary π-weighted inner product and admits orthogonal spectral coordinates; outside reversibility, P is genuinely non-self-adjoint (often non-normal), and stability is governed by biorthogonal geometry and eigenvector conditioning. In this paper, we develop an original harmonic-analysis framework for directed graphs anchored on the random-walk transition matrix P = Dout−1A and the random-walk Laplacian Lrw = I−P. Using biorthogonal left/right eigenvectors, we define a Biorthogonal Graph Fourier Transform (BGFT) adapted to directed diffusion, propose a diffusion-consistent frequency ordering based on decay rates ℜ(1 −λ), and derive operator norm stability bounds for iterated diffusion and for BGFT spectral filters. We prove sampling and reconstruction theorems for P-bandlimited (equivalently Lrw -bandlimited) signals and quantify noise amplification through the conditioning of the biorthogonal eigenbasis. A simulation protocol on directed cycles and perturbed non-normal digraphs demonstrates that asymmetry alone does not dictate instability, whereas non-normality and eigenvector illconditioning drive reconstruction sensitivity, making BGFT the correct analytical language for directed diffusion processes.