Directed Acyclic Graph Convolutional Networks

Technical Summary: Directed Acyclic Graph Convolutional Networks (DCN)

Problem Statement
Directed Acyclic Graphs (DAGs) are fundamental to applications involving causal inference, scheduling, and neural architecture design. However, learning from signals supported on DAGs presents unique challenges for Graph Neural Networks (GNNs). Standard GNNs rely on iterative message passing and spectral analysis based on graph shift operators (GSOs). In DAGs, the adjacency matrix is strictly lower-triangular and nilpotent, resulting in a collapsed spectrum (all eigenvalues are zero). This renders standard spectral graph theory tools vacuous and prevents the direct application of conventional convolutional GNNs. Furthermore, generic aggregation mechanisms in standard GNNs fail to explicitly account for the strong inductive bias of the partial ordering inherent to DAGs. Existing DAG-specific models, such as D-VAE and DAGNN, often rely on computationally intensive sequential operations (e.g., recurrent units) that do not scale well to large graphs.

Methodology
The authors propose the DAG Convolutional Network (DCN), a novel architecture grounded in Graph Signal Processing (GSP) principles tailored for DAGs. The core methodology relies on causal graph filters derived from the framework of weighted transitive closure.

1. Causal Graph Shift Operators (GSOs): Instead of using the adjacency matrix $A$, the DCN utilizes a set of causal GSOs $\{S_k\}_{k \in V}$. These operators are defined via the weighted transitive closure matrix $W = (I - A)^{-1}$, which corresponds to the reachability graph of the DAG. A causal GSO $S_k$ aggregates signal contributions from the common ancestors of a node $v_i$ and a reference node $v_k$.
2. Spectral Interpretation: The columns of $W$ serve as a Fourier basis for DAG signals. The causal GSOs are idempotent and share $W$ as their eigenvector matrix, allowing for a well-defined spectral-domain representation where filtering corresponds to pointwise scaling of Fourier coefficients.
3. DCN Architecture: The DCN implements layer-wise convolutions using a bank of these causal GSOs. For an input signal $X$, the output of layer $\ell$ is computed as:
   $$X^{(\ell)} = \sigma \left( \sum_{k \in V} S_k X^{(\ell-1)} \Theta^{(\ell)}_k \right)$$
   where $\Theta^{(\ell)}_k$ are learnable filter coefficients and $\sigma$ is a nonlinearity. This structure captures long-range ancestor dependencies efficiently via sparse matrix multiplications.
4. Parallel DCN (PDCN): To address scalability issues where the number of parameters in DCN grows linearly with the number of nodes $N$, the authors introduce PDCN. This variant processes shifted signals $\{S_k X\}$ in parallel branches through a shared Multi-Layer Perceptron (MLP), and the outputs are summed. This design decouples the number of learnable parameters from the graph size, making it scalable to large $N$.

Key Contributions

• Novel Architecture: The development of DCN, which formalizes convolutional operations on DAGs using causal graph filters, providing a spectral interpretation previously unavailable for DAG signals.
• Scalable Variant: The introduction of PDCN, which maintains predictive performance while ensuring the parameter count remains constant regardless of the DAG size.
• Theoretical Properties:
  • Permutation Equivariance: The authors prove that both DCN and PDCN are permutation equivariant, ensuring robustness to node relabeling.
  • Expressive Power: It is established that PDCN satisfies the conditions of the Weisfeiler-Lehman (WL) test, capable of distinguishing between non-isomorphic DAGs.
  • Uniqueness: Proposition 2 demonstrates that the set of causal GSOs uniquely identifies the underlying DAG structure.
• Efficiency: The architecture leverages sparse matrix operations and pre-computable shift operators, offering significant computational advantages over sequential DAG models.

Experimental Results
The paper evaluates (P)DCN on synthetic and real-world datasets against state-of-the-art baselines (including GCN, GIN, D-VAE, DAGNN, and DAG+NodeFormer).

• Synthetic Tasks:
  • Diffusion Learning: DCN achieves lower Normalized Mean Squared Error (NMSE) than baselines in predicting diffused signals, demonstrating superior robustness to noise and varying edge densities.
  • Source Identification: DCN variants (specifically using transposed GSOs) achieve high accuracy in tracing signal sources, outperforming DAG-agnostic models and showing better scalability than sequential models like DAGNN.
  • Scalability: As graph size increases (up to $N=1000$), DCN and PDCN maintain performance and reasonable training times, whereas models like DAGNN and D-VAE fail to finish (DNF) due to memory and time constraints.
• Real-World Applications:
  • Gene Expression Imputation: On an Arabidopsis Thaliana dataset, DCN and PDCN successfully impute missing gene expression levels, achieving NMSE comparable to D-VAE and DAGNN but with orders of magnitude fewer parameters and faster training times.
  • Hydrological Forecasting: On River Thames data, DCN outperforms all baselines in predicting chemical concentrations at unobserved sites, effectively leveraging the upstream-downstream flow structure.

Significance and Claims
The paper positions (P)DCN as a viable framework for deep learning on DAG-structured data, designed from first principles of graph signal processing. The authors claim that by incorporating the partial ordering of DAGs directly into the convolutional operators, the models achieve a strong inductive bias that improves accuracy, robustness, and computational efficiency compared to existing methods. The work bridges the gap between causal inference models and deep learning, offering a principled alternative to sequential aggregation methods. The authors acknowledge limitations, noting that the reliance on a large number of GSOs in the full DCN can still pose challenges for very large graphs, suggesting future work in adaptive GSO selection.