 Award ID(s):
 2017980
 NSFPAR ID:
 10422652
 Editor(s):
 Chambers, Erin W.
 Date Published:
 Journal Name:
 39th International Symposium on Computational Geometry (SoCG 2023)
 Page Range / eLocation ID:
 64:164:5
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

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 NPhard, 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 permutationbased greedy searches. Here, we provide the first consistency guarantees, both uniform and highdimensional, of a greedy permutationbased search. This search corresponds to a simplexlike algorithm operating over the edgegraph 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

In this work, we present a novel method for constructing a topological map of biological hotspots in an aquatic environment using a Fast Marchingbased 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 greedycoverage 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 realworld 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 greedycoverage algorithm in the informative path planning problem by guiding it to different informative areas to help it escape from local maxima.more » « less

Keil, Mark ; Mondal, Debajyoti (Ed.)We adapt and generalize a heuristic for kcenter clustering to the permutation case, where every prex of the ordering is a guaranteed approximate solution. The onehop 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 GarciaDiaz et al. and their algorithm required O(n2 log n) time for a fixed 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

Abstract Data from highenergy 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 call
Seeded 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, whichSRGonG then coalesces using a greedy algorithm where adjacent segments are merged to minimize a model comparison statistic; we use the Bayesian Information Criterion. UsingSRGonG we are able to identify pointlike and diffuse extended sources in the data with equal facility. We validateSRGonG using simulations, demonstrating that it is capable of discerning irregularly shaped lowsurfacebrightness emission structures as well as pointlike sources with strengths comparable to that seen in typical Xray data. We demonstrateSRGonG ’s use on the Chandra data of the Antennae galaxies and show that it segments the complex structures appropriately. 
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 eigendecompositionbased 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 edgeweight 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