Morris Greenberg

Headshot of Morris Greenberg

PhD Candidate, University of Toronto

Talk Title

Restricted Search Space MCMC Methods for Graph Inference


Inferring a directed acyclic graph (DAG) given data is computationally challenging due to the large search space needed to exhaustively consider all possible graphs. Current state-of-the-art MCMC methods for graph inference efficiently scan the space by first considering a restricted search space and iteratively expand the space until a stopping criterion is met. Here, we find conditions on iterative changes to the search space that allow for posterior convergence on the unrestricted space, and develop a novel MCMC method that satisfies these conditions. Our algorithm allows for both expansion and constriction of the search space at any iteration, and allows for larger expansion steps than previous methods allow for. Our expansion procedure is dictated by parameterizing the sparsity of the graph (the maximal number of parents observed), and considering how it induces realized parent sizes for individual vertices in the graph, and our constriction procedure is dictated by associating a weight (determined by previous steps in the MCMC chain) to each edge in the space, and only considering edges with large enough weights. We present extensive simulations that characterize the performance and computational efficiency of our algorithm, contrast this with existing methods, and consider applications in the field of imaging proteomics.