Source-linked AI summary
Signal Processing over Product DAGs: Causal Shifts and Filters
Sundeep Prabhakar Chepuri, Antonio G. Marques, Maulik Devmurari, Gonzalo Mateos
TL;DR
Standard graph products do not yield factorized weighted transitive closures for product DAGs, complicating separable analysis across two domains. The paper introduces a product DAG with a sign-reversed cross term, establishing resolvent factorization and separable Fourier modes, causal shifts, and filters. Denoising experiments report benefits from the resulting filters, including stronger performance for a separable filter and faster factorized computation than a dense equivalent.
Problem
Method
Results
In denoising experiments, both filters outperform the unfiltered baseline; the separable filter consistently outperforms the unconstrained filter despite using far fewer parameters, and factorized filtering is markedly faster than its dense equivalent once N exceeds a few hundred nodes.
Source: §5 · p. 4Takeaways & Limitations
For the tested denoising task and DAG, rank-1 separability provides an effective inductive bias for better generalization.
Source: §5 · p. 4
Abstract
from arXiv · showhide
We develop a signal processing framework for signals indexed by the product of two directed acyclic graphs (DAGs) and described by a linear structural equation model (SEM). Such a setup arises whenever (linear) causal relations act along two domains, as in component versus manufacturing stage or gene versus experimental condition. Disregarding the factorization of the underlying graph and the native two-axis causal structure requires inverting a weighted transitive closure matrix whose size is the product of the two factor sizes for Fourier analysis. Recognizing that standard graph products fail to yield factorizable transitive closures, we introduce a new DAG product under which separability holds. We motivate the new operator in the vertex domain, and show that it also renders the SEM, the Fourier modes, the causal shifts, and the filters on the product DAG separable across its constituent graph factors.
1. INTRODUCTION
Graph signal processing faces particular difficulties on DAGs, where nilpotent adjacency matrices lack a meaningful spectrum. For product DAGs, standard graph products also fail to preserve the factor separability that can make processing across multiple domains scalable.
1. INTRODUCTION
- DAG adjacency matrices are nilpotent and lack a meaningful spectrum, motivating a DAG-specific framework based on weighted transitive closure.That framework constructs graph shift operators and convolutional filters from the closure, giving causal notions a Fourier interpretation for signals following a linear SEM.Source: §1 · p. 1
- Product graphs have N = N1N2 vertices, so naive processing and parameter estimation face scalability and sample-size challenges.Exploiting latent product structure can keep these demands in check: factor eigenvectors yield separable Fourier analysis, supporting scalable filtering, graph learning, and sample selection.Source: §1 · p. 1
- Standard Cartesian, Kronecker, and strong products do not make DAG weighted transitive closures separable across factors.The paper introduces a product DAG with a sign-reversed cross term to avoid duplicating ancestor information, enabling factorizable closures, Fourier modes, causal shifts, and filters.Source: §1 · p. 1
2. PRELIMINARIES
The preliminaries describe DAG signals through a linear SEM and weighted transitive closure, then interpret closure columns as Fourier modes and define causal shifts and filters.
2. PRELIMINARIES
- Topological ordering makes a DAG adjacency matrix strictly lower triangular and nilpotent; a linear SEM expresses its signal through independent exogenous causes and the weighted transitive closure.The closure series truncates at n = N − 1 by nilpotency.Source: §2 · p. 1
- Each weighted transitive-closure entry sums edge-weight products over directed paths, and its columns are DAG Fourier modes synthesized from root-cause coefficients.A mode is the signal response to a unit impulse cause at its vertex.Source: §2 · p. 2
- The causal shift T_q = W D_q W^-1 selects causes at or upstream of q and retains the signal component they explain.Its selected causes form the principal downset of q.Source: §2 · p. 2
- Causal shifts are diagonalized by the Fourier basis, and their binary frequency selectors make each shift idempotent.A single shift retains one band, while combinations of graph shift operators can merge several.Source: §2 · p. 2
- An admissible passband is a downset: if it contains q, it must also contain every vertex that reaches q.The corresponding indicator matrix is triangular with unit diagonal, so it can be inverted to compute filter coefficients.Source: §2 · p. 2
3. PRODUCT DAGS
The paper defines a product DAG whose negative diagonal-edge term makes its weighted transitive closure factorize across the two factor DAGs. This supports separable Fourier representations and causal shifts while avoiding duplicated ancestor information.
3. PRODUCT DAGS
- The diagonal-edge term is −A1 ⊗A2, which removes duplicated ancestor information while preserving the strong product’s edge structure.The negative cross term subtracts one of two length-2 paths carrying the same combined weight.Source: §3 · p. 2
- The resolvent factorizes as W× = W1 ⊗W2, enabling Fourier analysis through the two factor DAGs.The paper establishes I −A× = (I1 −A1) ⊗(I2 −A2), then applies the Kronecker inverse identity.Source: §3 · p. 2
3.1. Fourier Modes of the Product DAG
- The product-DAG SEM is s = A×s + c = W×c, so signals are synthesized from causes through the factor transitive closures W1 and W2.The signal and cause matrices are vectorized over the N1 × N2 product vertices.Source: §3.1 · p. 2
3.2. Product DAG Causal Shift Operator
- Product reachability and principal downsets factor componentwise, so a causal shift selects causes upstream of each factor vertex and discards the rest.The text distinguishes the structural factorization of downsets from the negative sign’s role in factorizing weights.Source: §3.2 · p. 3
4. PRODUCT DAG FILTERS
Product DAG filters combine Kronecker causal shifts, and separable filters act independently along the two factor DAGs. Their passbands must be rectangular products of factor passbands; general target responses can be fit by alternating least squares when separability is unavailable.
4. PRODUCT DAG FILTERS
- A product DAG filter combines Kronecker causal shifts and applies its response to the product-DAG signal.The filter acts as ˆs = H×s; in matrix form it operates on the cause representation and synthesizes the output.Source: §4 · p. 3
- A passband is separable only when it is a rectangular product K1 × K2; then H× = H1 ⊗H2 and the coefficients factor across the DAGs.An admissible downset need not be separable; a general target response is realized exactly, but a separable filter reproduces it exactly only when rank(H~) = 1.Source: §4 · p. 3
- The illustrated separable low-frequency passband K = {(1, 1), (2, 1)} is implemented by a single product causal shift.The example uses factor passbands K1 = {1, 2} and K2 = {1}.Source: §4 · p. 3
- For a general target response, the design fits the closest separable filter by minimizing squared output deviation with alternating least squares.The signal is analyzed as C = (I −A1)S(I −A2)T before fitting.Source: §4 · p. 3
5. NUMERICAL EXPERIMENTS1
Synthetic and Thames River denoising experiments compare unconstrained and rank-1 separable filters with unfiltered baselines; the study also compares factorized and dense filter application. The reported results favor the proposed filters over the baseline, with separable filtering using fewer parameters and running faster on larger product graphs.
5. NUMERICAL EXPERIMENTS1
- Factorized product-DAG filtering is markedly faster than dense application once the graph exceeds a few hundred nodes.The factorized implementation avoids forming the dense N × N operator.Source: §5 · p. 4, Figure 3 · p. 4
- On the synthetic test, separable ALS denoising is comparable to unconstrained denoising, and both significantly outperform the unfiltered baseline.The product has 30 nodes; filters are fit on 60 training pairs and evaluated on 80 held-out pairs at 4 dB SNR.Source: §5 · p. 4, Figure 2 · p. 4
- The Thames evaluation uses total dissolved phosphorus observations across 15 sites and 52 weekly positions, with 8-fold leave-one-year-out validation.The study covers 2010–2017; 94.1% of site-week entries are directly measured, and the remainder are linearly interpolated within each calendar year.Source: §5 · p. 4, Figure 4 · p. 4
- Both filters outperform the no-filter baseline at every SNR, and the separable filter consistently outperforms the unconstrained filter despite using far fewer parameters.The unconstrained response uses 780 parameters, versus 67 for the rank-1 separable response.Source: §5 · p. 4, Figure 4 · p. 4
6. CONCLUSIONS
The conclusion presents the new DAG product as preserving two-axis causal structure while enabling separable Fourier modes and filtering through resolvent factorization. Denoising experiments demonstrate benefits, while higher-rank filters, sampling, and spectral estimation remain future work.
6. CONCLUSIONS
- The introduced DAG product preserves two-axis causal structure and enables separable Fourier modes and filtering through resolvent factorization.Source: §6 · p. 4
- Denoising experiments demonstrate benefits from the resulting filters.Source: §6 · p. 4
- Future work will explore filters beyond rank one and extend sampling and spectral estimation to product DAGs.Source: §6 · p. 4
8. COMPLIANCE WITH ETHICAL STANDARDS
The section states that the work is a numerical simulation study and that no ethical approval was required.