|
Abstract
|
Directed acyclic graphs (DAGs) are used for modeling causal relationships, dependencies, and ows in various
systems. However, spectral analysis becomes impractical in this setting because the eigendecomposition of the
adjacency matrix yields all eigenvalues equal to zero. This inherent property of DAGs results in an inability
to differentiate between frequency components of signals on such graphs. This problem can be addressed by
alternating the Fourier basis or adding edges in a DAG. However, these approaches change the physics of the
considered problem. To address this limitation, we propose a graph zero-padding approach. This approach involves
augmenting the original DAG with additional vertices that are connected to the existing structure. The added
vertices are characterized by signal values set to zero. The proposed technique enables the spectral evaluation of
system outputs on DAGs (in almost all cases), that is the computation of vertex-domain convolution without the
adverse effects of aliasing due to changes in a graph structure, with the ultimate goal of preserving the output of
the system on a graph as if the changes in the graph structure were not performed.
|