Learning Fourier-Sparse Functions on DAGs

Abstract

We show that the classical Moebius transform from combinatorics can be interpreted as a causal form of Fourier transform on directed acyclic graphs (DAGs). The associated Fourier basis, which is spanned by the columns of the zeta transform, enables us to make use of Fourier-sparse learning methods to learn functions on the vertices of DAGs from few observations. As a prototypical application example we construct a DAG from a dynamic contact tracing network, in which each vertex represents an individual at a given timestamp, and learn the function that indicates which of the vertices are infected by a disease.