More Like this

1. Consistency Guarantees for Greedy Permutation-Based Causal Inference Algorithms

   https://doi.org/10.1093/biomet/asaa104  

   Solus, L ; Wang, Y ; Uhler, C ( January 2021 , Biometrika)

   null (Ed.)

   Abstract Directed acyclic graphical models are widely used to represent complex causal systems. Since the basic task of learning such a model from data is NP-hard, a standard approach is greedy search over the space of directed acyclic graphs or Markov equivalence classes of directed acyclic graphs. As the space of directed acyclic graphs on p nodes and the associated space of Markov equivalence classes are both much larger than the space of permutations, it is desirable to consider permutation-based greedy searches. Here, we provide the first consistency guarantees, both uniform and high-dimensional, of a greedy permutation-based search. This search corresponds to a simplex-like algorithm operating over the edge-graph of a subpolytope of the permutohedron, called a directed acyclic graph associahedron. Every vertex in this polytope is associated with a directed acyclic graph, and hence with a collection of permutations that are consistent with the directed acyclic graph ordering. A walk is performed on the edges of the polytope maximizing the sparsity of the associated directed acyclic graphs. We show via simulated and real data that this permutation search is competitive with current approaches. 

   more » « less
2. Topological hotspot identification for informative path planning with a marine robot

   McCammon, S. ; Hollinger, G. ( May 2018 , IEEE International Conference on Robotics and Automation)

   In this work, we present a novel method for constructing a topological map of biological hotspots in an aquatic environment using a Fast Marching-based Voronoi segmentation. Using this topological map, we develop a closed form solution to the scheduling problem for any single path through the graph. Searching over the space of all paths allows us to compute a maximally informative path that traverses a subset of the hotspots, given some budget. Using a greedy-coverage algorithm we can then compute an informative path. We evaluate our method in a set of simulated trials, both with randomly generated environments and a real-world environment. In these trials, we show that our method produces a topological graph which more accurately captures features in the environment than standard thresholding techniques. Additionally, We show that our method can improve the performance of a greedy-coverage algorithm in the informative path planning problem by guiding it to different informative areas to help it escape from local maxima. 

   more » « less
3. One Hop Greedy Permutations

   Sheehy, Donald R. ( January 2020 , Proceedings of the 32nd Canadian Conference on Computational Geometry)

   Keil, Mark ; Mondal, Debajyoti (Ed.)

   We adapt and generalize a heuristic for k-center clustering to the permutation case, where every prex of the ordering is a guaranteed approximate solution. The one-hop greedy permutations work by choosing at each step the farthest unchosen point and then looking in its local neighborhood for a point that covers the most points at a certain scale. This balances the competing demands of reducing the coverage radius and also covering as many points as possible. This idea first appeared in the work of Garcia-Diaz et al. and their algorithm required O(n2 log n) time for a fixed k (i.e. not the whole permutation). We show how to use geometric data structures to approximate the entire permutation in O(n log D
   ) time for metrics sets with spread D. Notably, this running time is asymptotically the same as the running time for computing the ordinary greedy permutation. 

   more » « less
4. Identifying Diffuse Spatial Structures in High-energy Photon Lists

   https://doi.org/10.3847/1538-3881/aca478  

   Fan, Minjie ; Wang, Jue ; Kashyap, Vinay L. ; Lee, Thomas C. M. ; van Dyk, David A. ; Zezas, Andreas ( January 2023 , The Astronomical Journal)

   Data from high-energy observations are usually obtained as lists of photon events. A common analysis task for such data is to identify whether diffuse emission exists, and to estimate its surface brightness, even in the presence of point sources that may be superposed. We have developed a novel nonparametric event list segmentation algorithm to divide up the field of view into distinct emission components. We use photon location data directly, without binning them into an image. We first construct a graph from the Voronoi tessellation of the observed photon locations and then grow segments using a new adaptation of seeded region growing that we callSeeded Region Growing on Graph, after which the overall method is namedSRGonG. Starting with a set of seed locations, this results in an oversegmented data set, whichSRGonGthen coalesces using a greedy algorithm where adjacent segments are merged to minimize a model comparison statistic; we use the Bayesian Information Criterion. UsingSRGonGwe are able to identify point-like and diffuse extended sources in the data with equal facility. We validateSRGonGusing simulations, demonstrating that it is capable of discerning irregularly shaped low-surface-brightness emission structures as well as point-like sources with strengths comparable to that seen in typical X-ray data. We demonstrateSRGonG’s use on the Chandra data of the Antennae galaxies and show that it segments the complex structures appropriately.

    

   more » « less
5. Learning Graph Structure from Convolutional Mixtures

   Wasserman, Max ; Sihag, Saurabh ; Mateos, Gonzalo ; Ribeiro, Alejandro ( June 2023 , Transactions on machine learning research)

   Machine learning frameworks such as graph neural networks typically rely on a given, fixed graph to exploit relational inductive biases and thus effectively learn from network data. However, when said graphs are (partially) unobserved, noisy, or dynamic, the problem of inferring graph structure from data becomes relevant. In this paper, we postulate a graph convolutional relationship between the observed and latent graphs, and formulate the graph structure learning task as a network inverse (deconvolution) problem. In lieu of eigendecomposition-based spectral methods or iterative optimization solutions, we unroll and truncate proximal gradient iterations to arrive at a parameterized neural network architecture that we call a Graph Deconvolution Network (GDN). GDNs can learn a distribution of graphs in a supervised fashion, perform link prediction or edge-weight regression tasks by adapting the loss function, and they are inherently inductive as well as node permutation equivariant. We corroborate GDN’s superior graph learning performance and its generalization to larger graphs using synthetic data in supervised settings. Moreover, we demonstrate the robustness and representation power of GDNs on real world neuroimaging and social network datasets. 

   more » « less