Spectral analysis on directed graphs poses specific difficulties that are absent in the undirected case. Because the usual adjacency-based shift operators are generally non-normal, their eigenvectors do not necessarily form a basis, and for directed acyclic graphs (DAGs) every eigenvalue equals zero, which blocks a straightforward eigen-based spectral analysis. This chapter first frames these issues in the context of the main methods proposed so far for general digraphs, outlining how alternative shifts, Hermitian or Laplacian surrogates and variation-driven orderings attempt to bypass them. The discussion then turns to approaches adapted to DAGs—such as Möbius-poset bases, edge augmentation, and block-acyclic embeddings—and describes graph zero-padding as one additional, structurally simple option: by inserting a return path of zero-valued vertices it restores diagonalizability while preserving the original feed-forward flow. This modification, which leaves any finite-impulse response intact, provides a consistent platform for filtering and vertex-frequency inspection on acyclic data. The chapter closes by demonstrating how zero-padding enables vertex-domain implementation of frequency-domain filters, thus bridging spectral design and scalable computation on DAGs.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Spectral Analysis on Directed Acyclic Graphs

  • Miloš Brajović,
  • Isidora Stanković,
  • Ali Bagheri-Bardi,
  • Miloš Daković,
  • Ljubiša Stanković

摘要

Spectral analysis on directed graphs poses specific difficulties that are absent in the undirected case. Because the usual adjacency-based shift operators are generally non-normal, their eigenvectors do not necessarily form a basis, and for directed acyclic graphs (DAGs) every eigenvalue equals zero, which blocks a straightforward eigen-based spectral analysis. This chapter first frames these issues in the context of the main methods proposed so far for general digraphs, outlining how alternative shifts, Hermitian or Laplacian surrogates and variation-driven orderings attempt to bypass them. The discussion then turns to approaches adapted to DAGs—such as Möbius-poset bases, edge augmentation, and block-acyclic embeddings—and describes graph zero-padding as one additional, structurally simple option: by inserting a return path of zero-valued vertices it restores diagonalizability while preserving the original feed-forward flow. This modification, which leaves any finite-impulse response intact, provides a consistent platform for filtering and vertex-frequency inspection on acyclic data. The chapter closes by demonstrating how zero-padding enables vertex-domain implementation of frequency-domain filters, thus bridging spectral design and scalable computation on DAGs.