Causal Fourier Analysis on Directed Acyclic Graphs and Posets

Abstract

We present a novel form of Fourier analysis, and associated signal processing concepts, for signals (or data) indexed by edge-weighted directed acyclic graphs (DAGs). This means that our Fourier basis yields an eigendecomposition of a suitable notion of shift and convolution operators that we define. DAGs are the common model to capture causal relationships between data values and in this case our proposed Fourier analysis relates data with its causes under a linearity assumption that we define. The definition of the Fourier transform requires the transitive closure of the weighted DAG for which several forms are possible depending on the interpretation of the edge weights. Examples include level of influence, distance, or pollution distribution. Our framework is different from prior GSP: it is specific to DAGs and leverages, and extends, the classical theory of Moebius inversion from combinatorics. For a prototypical application we consider DAGs modeling dynamic networks in which edges change over time. Specifically, we model the spread of an infection on such a DAG obtained from real-world contact tracing data and learn the infection signal from samples assuming sparsity in the Fourier domain.

arXiv comment13 pages, 11 figures

References in corpus (21)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Topological Signal Processing over Simplicial Complexes
• A Survey of Learning Causality with Data: Problems and Methods
• Identifiability of Gaussian structural equation models with equal error variances
• On the Graph Fourier Transform for Directed Graphs
• High-dimensional learning of linear causal networks via inverse covariance estimation
• Introducing Hypergraph Signal Processing: Theoretical Foundation and Practical Applications
• A Directed Graph Fourier Transform with Spread Frequency Components
• On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
• Graph Fourier Transform: A Stable Approximation
• Concave Penalized Estimation of Sparse Gaussian Bayesian Networks
• Graphon Signal Processing
• Signal Processing on Cell Complexes
• Digraph Signal Processing with Generalized Boundary Conditions
• DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization
• Discrete Signal Processing on Meet/Join Lattices
• Discrete Signal Processing with Set Functions
• CausalBench: A Large-scale Benchmark for Network Inference from Single-cell Perturbation Data
• Learning DAGs from Data with Few Root Causes
• Fast Möbius and Zeta Transforms