Asymmetry in Spectral Graph Theory: Harmonic Analysis on Directed Networks via Biorthogonal Bases (Random-Walk Laplacian Formulation)

Abstract

The operator-theoretic dichotomy underlying diffusion on directed networks is \emph{symmetry versus non-self-adjointness} of the Markov transition operator. In the reversible (detailed-balance) regime, a directed random walk $P$ is self-adjoint in a stationary $\pi$-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 a harmonic-analysis framework for directed graphs anchored on the random-walk transition matrix $P=D_{\mathrm{out}}^{-1}A$ and the random-walk Laplacian $L_{\mathrm{rw}}=I-P$. Using biorthogonal left/right eigenvectors we define a \emph{Biorthogonal Graph Fourier Transform} (BGFT) adapted to directed diffusion, propose a diffusion-consistent frequency ordering based on decay rates $\Re (1-\lambda )$, and derive operator-norm stability bounds for iterated diffusion and for BGFT spectral filters. We prove sampling and reconstruction theorems for $P$-bandlimited (equivalently $L_{\mathrm{rw}}$-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; rather, non-normality and eigenvector ill-conditioning drive reconstruction sensitivity, making BGFT a natural analytical language for directed diffusion processes.