Causal Fourier Analysis on Directed Acyclic Graphs and Posets

• URL: http://arxiv.org/abs/2209.07970v3
• Date: Wed, 9 Aug 2023 12:17:49 GMT
• Title: Causal Fourier Analysis on Directed Acyclic Graphs and Posets
• Authors: Bastian Seifert and Chris Wendler and Markus P\"uschel
• Abstract summary: 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. For a prototypical application we consider DAGs modeling dynamic networks in which edges change over time.
• Score: 11.000499414131324
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Scalable Variational Causal Discovery Unconstrained by Acyclicity [6.954510776782872]
  We propose a scalable Bayesian approach to learn the posterior distribution over causal graphs given observational data. We introduce a novel differentiable DAG sampling method that can generate a valid acyclic causal graph. We are able to model the posterior distribution over causal graphs using a simple variational distribution over a continuous domain.
  arXiv  Detail & Related papers  (2024-07-06T07:56:23Z)
• Convolutional Learning on Directed Acyclic Graphs [10.282099295800322]
  We develop a novel convolutional architecture tailored for learning from data defined over directed acyclic graphs (DAGs) We develop a novel convolutional graph neural network that integrates learnable DAG filters to account for the partial ordering induced by the graph topology.
  arXiv  Detail & Related papers  (2024-05-05T21:30:18Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process. An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• Geometric Graph Filters and Neural Networks: Limit Properties and Discriminability Trade-offs [122.06927400759021]
  We study the relationship between a graph neural network (GNN) and a manifold neural network (MNN) when the graph is constructed from a set of points sampled from the manifold. We prove non-asymptotic error bounds showing that convolutional filters and neural networks on these graphs converge to convolutional filters and neural networks on the continuous manifold.
  arXiv  Detail & Related papers  (2023-05-29T08:27:17Z)
• Convolutional Filtering on Sampled Manifolds [122.06927400759021]
  We show that convolutional filtering on a sampled manifold converges to continuous manifold filtering. Our findings are further demonstrated empirically on a problem of navigation control.
  arXiv  Detail & Related papers  (2022-11-20T19:09:50Z)
• Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs [16.88394293874848]
  We use cellular sheaf theory to show that the underlying geometry of the graph is deeply linked with the performance of GNNs. By considering a hierarchy of increasingly general sheaves, we study how the ability of the sheaf diffusion process to achieve linear separation of the classes in the infinite time limit expands. We prove that when the sheaf is non-trivial, discretised parametric diffusion processes have greater control than GNNs over their behaviour.
  arXiv  Detail & Related papers  (2022-02-09T17:25:02Z)
• BCDAG: An R package for Bayesian structure and Causal learning of Gaussian DAGs [77.34726150561087]
  We introduce the R package for causal discovery and causal effect estimation from observational data. Our implementation scales efficiently with the number of observations and, whenever the DAGs are sufficiently sparse, the number of variables in the dataset. We then illustrate the main functions and algorithms on both real and simulated datasets.
  arXiv  Detail & Related papers  (2022-01-28T09:30:32Z)
• Stratified Graph Spectra [0.0]
  This paper seeks a generalized transformation decoding the magnitudes of eigencomponents from vector-valued signals. Several attempts are explored, and it is found that performing the transformation at hierarchical levels of adjacency help profile the spectral characteristics of signals more insightfully.
  arXiv  Detail & Related papers  (2022-01-10T23:35:13Z)
• BCD Nets: Scalable Variational Approaches for Bayesian Causal Discovery [97.79015388276483]
  A structural equation model (SEM) is an effective framework to reason over causal relationships represented via a directed acyclic graph (DAG) Recent advances enabled effective maximum-likelihood point estimation of DAGs from observational data. We propose BCD Nets, a variational framework for estimating a distribution over DAGs characterizing a linear-Gaussian SEM.
  arXiv  Detail & Related papers  (2021-12-06T03:35:21Z)
• Sampling Signals on Graphs: From Theory to Applications [119.19108613761915]
  We review current progress on sampling over graphs focusing on theory and potential applications. Although most methodologies used in graph signal sampling are designed to parallel those used in sampling for standard signals, sampling theory for graph signals significantly differs from the theory of Shannon--Nyquist and shift-invariant sampling.
  arXiv  Detail & Related papers  (2020-03-09T07:49:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.