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

2. Preliminaries: directed diffusion operators

2.1 Directed graphs, adjacency, and out-degree

Let G = (V, E,w) be a directed weighted graph with |V | = n and adjacency A ∈ Rⁿ×n:

$A_{ij}=\{\begin{array}{ll}w(i,j),\hfill & (i,j)\in E\hfill \\ 0,\hfill & otherwise \hfill \end{array}$

Define out-degrees d^outi

$={\text{P}}_j{A}_{ij} and D_{out }=\text{diag}\left(d_1^{out },\dots ,d_n^{out }\right).$

2.2 Transition matrix and random-walk Laplacian

Definition 2.1 (Random-walk transition matrix). Assume d^outi > 0 for all  (no sinks). Define

P: = Dout−1A.

Then P is row-stochastic: P1 = 1.

Definition 2.2 (Random-walk Laplacian). Define

L_rw = I−P

Proposition 2.3 (Basic properties). (i) P1 = 1 and L_rw1 = 0. (ii) If P is irreducible and aperiodic, then the diffusion x_t+1 = Px_t converges to the stationary component (Markov mixing perspective).

Proof. (i) Row-stochasticity gives P1 = 1, hence(I − P)1 = 0.

2.3 Asymmetry and non-normality indices

Definition 2.4 (Asymmetry index). For any matrix M, define $\alpha (M):=\Vert M-M^{\top }{\Vert }_F/\Vert M{\Vert }_F$  (with α(0) = 0).

Definition 2.5 (Departure from normality). For any matrix M, define $\delta (M):=M{M}^{\text{*}}-M^{\text{*}}{M}_F/\Vert M{\Vert }^2{ }_F$ (with δ(0) = 0).

Such non-normality measures (and related bounds) are classical in matrix analysis; see [3,11-14].

We will use these for M = P and M = L_rw to separate structural directedness from numerical instability drivers.

3. Reversibility as the symmetry regime for directed diffusion

Let P ∈ Rⁿ×n be row-stochastic (P1 = 1). Assume P has a stationary distribution π ∈ Rⁿ with π_i > 0 π⊤P = π^⊤. Let Π:= diag(π).

Define the p-weighted inner product and norm by

$\langle x,{y\rangle }_{\pi }:=x^{\top }\text{Π}y\Vert x{\Vert }_{\pi }^2:=\langle x,{x\rangle }_{\pi }$

The adjoint of P with respect to ⟨·,·⟩π is

$P^{†}:={\text{Π}}^{-1}{P}^{\top }\text{Π}, \text{so that} \langle Px,{y\rangle }_{\pi }=x,P^{†}{y}_{\pi }$

Definition 3.1 (Reversibility / detailed balance). P is reversible (w.r.t. p) if

$\text{Π}P=P^{\top }\text{Π},\text{ equivalently}, P=P†.$

This detailed-balance condition is standard in reversible Markov chain theory; see [2,9,15].

Theorem 3.2 (Weighted symmetry equivalences). The following are equivalent:

1. P is reversible ΠP = P^⊤Π.
2. P is self-adjoint in 〈. , .〉 _π: P = P^†.
3. The similarity transform S: = Π^1/2PΠ^−1/2 .is symmetric: S = S^†.

In this case, P has a complete p-orthonormal eigenbasis, and all eigenvalues are real.

Proof. (i) ⇔ (ii) is the definition of P†. For (i) ⇒ (iii), multiply ΠP = P⊤Π on the left by Π^−1/2 and on the right by Π^−1/2 to get Π^1/2PΠ^−1/2 = (Π^1/2PΠ^−1/2)⊤. Conversely, (iii) ⇒ (i) follows by reversing the steps. If S is symmetric, it is orthogonally diagonalizable with real eigenvalues, hence so is P by similarity.

See also [9,10] for related equivalences and consequences.

Remark 3.3 (Symmetry/asymmetry interpretation for this paper). Undirected diffusion is symmetric in the standard Euclidean inner product. Directed diffusion can still be symmetric in the weighted p-inner product exactly in the reversible regime. Non-reversibility is the correct notion of asymmetry for random-walk harmonic analysis.

4. Biorthogonal Graph Fourier Transform (BGFT) for randomwalk diffusion

4.1 Left/right eigenvectors and BGFT

Assumption 4.1 (Diagonalizability). Assume P is diagonalizable over C:

$P=V\text{Λ}{V}^{-1},\text{ Λ}=\text{diag}\left({\lambda }_1,\dots ,{\lambda }_n\right),$

with right eigenvectors V = [v¹ ··· v_n].

Remark 4.2 (Non-diagonalizable operators). While Assumption 4.1 holds for almost all transition matrices (diagonalizable matrices are dense in Cⁿ×n), certain highly symmetric digraph structures can yield non-diagonalizable P. In such cases, the BGFT can be generalized using the Jordan canonical form or the Schur decomposition. However, the biorthogonal framework presented here focuses on the most common case where a complete set of eigenvectors exists, providing a direct physical link to decay modes.

Definition 4.3 (BGFT (diffusion version)). For a graph signal x ∈ Cn, define BGFT coefficients

$x \text{b}:=U^{\text{*}}X,x {\text{b}}_k=u^{\text{*}}kX\text{ (1)}$

and synthesis

$x=V\widehat{x}={\displaystyle \sum }_{k=1}^n{v}_k{\widehat{x}}_k\text{ (2)}$

Theorem 4.4 (Perfect reconstruction). Under Assumption 4.1, for all x ∈ Cⁿ,

$\begin{array}{rr}\hfill n& \hfill n\\ \hfill I=\text{X}vku\text{*}k,& \hfill x=\text{X}vku\text{*}kX\\ \hfill k=1& \hfill k=1\end{array}$

Proof. Since U+V = I, we have V U+ = I; expand V U+ in columns/rows.

4.2 Diffusion dynamics are diagonal in BGFT coordinates

Theorem 4.5 (BGFT-domain diffusion). Let x_t+1 = Px_t  with x₀ ∈ Cⁿ. Then

$x \text{b}t=U_{\text{*}}{X}_t=\text{Λ}tx \text{b}0,xt=V{\text{Λ}}_t{U}_{\text{*}X0}$

Equivalently, for L_rw = I − P,

$(\widehat{L_{\text{rw}}x})=(I-\text{Λ})\widehat{x}$

Proof. Use P = V ΛU∗ and U+V = I. Then U+(Px) = Λ(U+x) and iterate.

4.3 Diffusion-consistent frequency ordering

For diffusion, the mode with eigenvalue l evolves as lt. If |λ| < 1, it decays; if λ ≈ 1, it is slowly varying (low frequency). We define the diffusion decay rate:

${\omega }_{diff }(\lambda ):=\Re (1-\lambda ).$

Low ωdiff corresponds to persistent/slow modes; high ωdiff  corresponds to fast decay. Compared to the imaginary-part ordering (phase) often used in adjacency-based GFTs, ℜ(1 − λ) provides a direct measure of spectral energy dissipation. This choice aligns with the variational property of the random-walk Laplacian, where ℜ(1 − λ) quantifies the smoothness of a mode relative to the one-step diffusion process.

5. Directed diffusion filtering and stability bounds

5.1 Spectral filters

Definition 5.1 (BGFT spectral filter for diffusion). Let h: C → C. Define

$H:=Vh(\text{Λ})U^{\text{*}}.$

Proposition 5.2 (Diagonal action in BGFT domain). For x = U⁺x, b

$H{x}_{\text{d}}=U^{\text{*}}Hx=h(\text{Λ})x.\text{b} Proof. Compute U^{\text{*}}Vh(\text{Λ})U^{\text{*}}x=h(\text{Λ})x.$

5.2 Operator-norm stability: diffusion and filtering

Theorem 5.3 (Norm bound for diffusion iterates). Assume P = V ΛV −1. Then for every t ∈N,

$P_k^t{}_2\le \text{cond}(V)\text{max}{\left|{\lambda }_k\right|}^t,\text{ cond}($

Proof. $P^t=V{\text{Λ}}^t{V}^{-1}$ , hence $P^t{}_2\le \Vert V{\Vert }_2{\text{Λ}}^t{}_2{V}^{-1}{}_2=\text{cond}(V)\underset{k}{\text{max}}{\left|{\lambda }_k\right|}^t$ .

Theorem 5.4 (Norm bound for spectral filters). Let $H=Vh(\text{Λ})V^{-1}$ . Then $\Vert H{\Vert }_2\le$

$\text{cond}(V)\text{max}\left|h\left({\lambda }_k\right)\right|.$

Proof. $\Vert H{\Vert }_2\le \Vert V{\Vert }_2\Vert h(\text{Λ}){\Vert }_2{V}^{-1}{}_2=\text{cond}(V)\underset{k}{\text{max}}\left|h\left({\lambda }_k\right)\right|$ .

Remark 5.5 (Symmetry/asymmetry and Instability). When  is normal and diagonalizable by a unitary basis, cond(V) = 1, and the bounds become tight and symmetry-like. It is critical to distinguish between structural asymmetry (α(P) > 0) and numerical instability (cond(V) ≫ 1). Asymmetry is a prerequisite for the loss of orthogonality, but it does not necessitate instability; for instance, the directed cycle is maximally asymmetric but remains normal and perfectly stable. For non-normal P, cond(V) can be large, creating instability even if |λk| ≤ 1. Our numerical experiments in Section 9 confirm that this ill-conditioning, rather than directedness per se, drives the reconstruction error.

6 BGFT energy in the stationary metric and its symmetry limit

Assume P is diagonalizable over C: P = V ΛV ⁻¹ and define U∗ := V ⁻¹. Let xb: = U+x be BGFT coefficients so that x = V x.

Theorem 6.1 (p-metric Parseval identity). For any x ∈ Cⁿ,

$\Vert x{\Vert }_{\pi }^2={\widehat{x}}^{*}{G}_{\pi }\widehat{x},G_{\pi }:=V^{\text{*}}\text{Π}V$

Proof. Since $x=Vx \text{b},\Vert x{\Vert }^2{ }_{\pi }=x^{\text{*}}\text{Π}x=x \text{b*}(V\text{*Π}V)x \text{b}$ .

Corollary 6.2 (Two-sided bounds via conditioning in p). Let W: = Π1/2V. Then

${\sigma }_{\text{min}}{(W)}^2\Vert \widehat{x}{\Vert }_2^2\le \Vert x{\Vert }_{\pi }^2\le {\sigma }_{\text{max}}{(W)}^2\Vert \widehat{x}{\Vert }_2^2$

Equivalently, energy distortion is controlled by $\kappa (W)={\sigma }_{\text{max}}(W)/{\sigma }_{\text{min}}(W)$ .

6.1 Diffusion variation and frequency ordering

Define the random-walk Laplacian L_rw:= I − P and the diffusion variation

${\text{TV}}_{\pi }(x):=L_{\text{rw}}{x}_{\pi }^2=\Vert (I-P)x{\Vert }_{\pi }^2$

Theorem 6.3 (BGFT-domain bounds for diffusion variation). With x = V x and W = Π^1/2V , b n n

${\sigma }_{\text{min}}{(W)}_2\text{X}\left|1-{\lambda }_k\right|2\left|x \text{b}k\right|2\le \text{TV}\pi (x)\le {\sigma }_{\text{max}}{(W)}_2\text{X}\left|1-{\lambda }_k\right|2\left|x \text{b}k\right|2$

Proof. $(I-P)x=V(I-\text{Λ})x \text{b}$ . Then $\Vert (I-P)x{\Vert }_{\pi }={\text{Π}}^{1/2}V(I-\text{Λ})x {\text{b}}_2=\Vert W(I-\text{Λ})x \text{b}{\Vert }_2$ . Apply ${\sigma }_{\text{min}}(W)\Vert z{\Vert }_2\le \Vert Wz{\Vert }_2\le {\sigma }_{\text{max}}(W)\Vert z{\Vert }_2$ to and $z=(I-\text{Λ})x \text{b}$ square.

Remark 6.4 (Exact symmetry limit). If P is reversible, one can choose Vp-orthonormal, hence W = Π^1/2V is unitary and σ_min(W) = σ_max(W) = 1. Then the inequalities become equalities, and |1 − λk| becomes an exact diffusion frequency.

7 Sampling and reconstruction for diffusion-bandlimited signals

Let Ω ⊂ {1,...,n} with |Ω| = K represent the “low diffusion-frequency” modes (e.g. smallest ω_diff(λ) or largest ℜ(λ)). Let V_Ω ^∈ Cⁿ×K contain {v_k}_k∈Ω.

Definition 7.1 (Diffusion-bandlimited signals). A signal x is Ω-bandlimited (relative to P) if x = V_Ωc for some c ∈ C^K.

Bandlimited sampling on graphs has a substantial literature; see, e.g., [16-18]. Let M ⊂ V, |M| = m, and P_M ∈ {0,1}m×n be the restriction operator.

Theorem 7.2 (Exact recovery). If x = V_Ωc and P_MV_Ω has full column rank K, then x is uniquely determined by samples y = P_Mx and recovered by

$\text{b}c={\left(P_M{V}_{\text{Ω}}\right)}^{†}y,x \text{b}=V_{\text{Ω}}\text{b}c$

Proof. Full column rank makes P_MV_Ω injective; solve the linear system in least squares. Related sampling-set conditions and reconstruction stability on graphs are discussed in [16-19].

Theorem 7.3 (Noise sensitivity). If y = P_Mx+η, then the least-squares reconstruction satisfies.

$\Vert \widehat{x}-x{\Vert }_2\le V_{\text{Ω}}{}_2{\left(P_M{V}_{\text{Ω}}\right)}^{†}{}_2\Vert \eta {\Vert }_2=V_{\text{Ω}}{}_2\frac{\Vert \eta {\Vert }_2}{{\sigma }_{\text{min}}\left(P_M{V}_{\text{Ω}}\right)}$

Proof. b c − c = (PMVΩ)^†η and x_b − x = VΩ(_bc − c).

8 Algorithms

Algorithm 1 BGFT for random-walk diffusion

Require: A (directed adjacency), D_out invertible, signal x

Ensure: BGFT coefficients x, eigenpairs (L, V)

1: P← , $D_{out}^{-1}A$ L_rw ← I-P

2: Compute eigendecomposition P = V Λ V^-1 (complex arithmetic)

3: U*← V^-1

4: x ← U* xb

5: return (x,Λ,V) b

Algorithm 2: Diffusion filtering and bandlimited reconstruction

Require: P = V ΛV ⁻¹, response h(·), bandlimit Ω, sample set M, samples y Ensure: filtered signal Hx or reconstructed x

1: Filtering: H ← V h(Λ)V ⁻¹, output Hx ← Hx

2: Reconstruction: form VΩ, solve bc ← argmin ${}_c||\text{PMVWc }–\text{ y}|{|}_2^2$

3: $\widehat{x}\leftarrow V\Omega \widehat{c}$

9 Experiments: directed cycle vs perturbed non-normal digraphs

9.1 Graphs

Use n ∈ {32,64,128} and compare: (Table 1)

1. Undirected cycle C_n (convert to diffusion by symmetrizing and normalizing).
2. Directed cycle   $\overrightarrow{C_n}$ : P is a permutation shift (asymmetric but normal/unitary).
3. Perturbed directed cycle $\overrightarrow{C_n}(\epsilon )$ : add a directed chord, then renormalize rows to keep P stochastic; this typically yields non-normal P and large cond (V).

9.2 Tasks and metrics

• Diffusion filtering: low-pass via h(λ) = exp(−τ(1 − λ)) (BGFT-defined), compare smoothing strength on the three graphs.
• Forecasting: iterate diffusion x_t+1 = Pxt and compare || x_t ||2 trends with Theorem 5.3.
• Sampling/reconstruction: generate W-bandlimited signals and recover from m samples; report RelErr and σ_min(P_MV_Ω).
• Perturbed directed cycle  : add a directed chord from node 0 to node n/2 with weight ε = 20, then renormalize rows to keep P stochastic; this typically yields non-normal P and large cond (V).

Report tables/figures:

$\alpha (P),\delta (P),\text{cond}(V),\text{cond}\left(P_M{V}_{\text{Ω}}\right),\text{RelErr}=\frac{\Vert \widehat{x}-x{\Vert }_2}{\Vert x{\Vert }_2}$

Observed separation. The directed cycle is asymmetric (α(P) > 0) but normal (δ(P) = 0) with a well-conditioned eigenbasis (κ(V ) = 1), whereas the perturbed digraph remains asymmetric but becomes non-normal (δ(P) > 0) and strongly ill-conditioned (κ(V ) ≫ 1), leading to markedly larger reconstruction error, consistent with the stability bounds.

10 Conclusion

We developed an original diffusion-centered harmonic analysis for directed graphs using the random-walk transition matrix P and Laplacian L_rw = I − P. The BGFT provides exact analysis/synthesis, diagonalizes diffusion dynamics, motivates a diffusion-consistent frequency ordering, and yields explicit stability bounds for iterated diffusion and spectral filtering governed by eigenvector conditioning. Sampling and reconstruction theorems quantify how non-normality amplifies noise through σ_min(P_MV_Ω) and cond(V). This establishes a principled symmetry/asymmetry narrative: symmetry yields orthogonality and stability; asymmetry forces biorthogonal geometry; non-normality determines practical robustness.

Appendix-file