More Like this

1. Reliable Spanners for Metric Spaces

   https://doi.org/10.1145/3563356  

   Har-Peled, Sariel; Mendel, Manor; Oláh, Dániel (January 2023, ACM Transactions on Algorithms)

   A spanner is reliable if it can withstand large, catastrophic failures in the network. More precisely, any failure of some nodes can only cause a small damage in the remaining graph in terms of the dilation. In other words, the spanner property is maintained for almost all nodes in the residual graph. Constructions of reliable spanners of near linear size are known in the low-dimensional Euclidean settings. Here, we present new constructions of reliable spanners for planar graphs, trees, and (general) metric spaces. 

   more » « less
2. On the Complexity of Sequence to Graph Alignment

   https://doi.org/10.1007/978-3-030-17083-7  

   Jain, Chirag; Zhang, Haowen; Gao, Yu; Aluru, Srinivas (April 2019, Lecture Notes in Computer Science)

   Availability of extensive genetics data across multiple individuals and populations is driving the growing importance of graph based reference representations. Aligning sequences to graphs is a fundamental operation on several types of sequence graphs (variation graphs, assembly graphs, pan-genomes, etc.) and their biological applications. Though research on sequence to graph alignments is nascent, it can draw from related work on pattern matching in hypertext. In this paper, we study sequence to graph alignment problems under Hamming and edit distance models, and linear and affine gap penalty functions, for multiple variants of the problem that allow changes in query alone, graph alone, or in both. We prove that when changes are permitted in graphs either standalone or in conjunction with changes in the query, the sequence to graph alignment problem is NP -complete under both Hamming and edit distance models for alphabets of size ≥2 . For the case where only changes to the sequence are permitted, we present an O(|V|+m|E|) time algorithm, where m denotes the query size, and V and E denote the vertex and edge sets of the graph, respectively. Our result is generalizable to both linear and affine gap penalty functions, and improves upon the run-time complexity of existing algorithms. 

   more » « less
3. A NEW COARSELY RIGID CLASS OF BANACH SPACES

   https://doi.org/10.1017/S1474748019000732  

   Baudier, F.; Lancien, G.; Motakis, P.; Schlumprecht, Th. (January 2020, Journal of the Institute of Mathematics of Jussieu)

   We prove that the class of reflexive asymptotic-$$c_{0}$$ Banach spaces is coarsely rigid, meaning that if a Banach space $$X$$ coarsely embeds into a reflexive asymptotic-$$c_{0}$$ space $$Y$$, then $$X$$ is also reflexive and asymptotic-$$c_{0}$$. In order to achieve this result, we provide a purely metric characterization of this class of Banach spaces. This metric characterization takes the form of a concentration inequality for Lipschitz maps on the Hamming graphs, which is rigid under coarse embeddings. Using an example of a quasi-reflexive asymptotic-$$c_{0}$$ space, we show that this concentration inequality is not equivalent to the non-equi-coarse embeddability of the Hamming graphs. 

   more » « less
4. Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks

   Chuang, C; Jegelka, S (January 2022, Neural Information Processing Systems (NeurIPS))

   Understanding generalization and robustness of machine learning models funda- mentally relies on assuming an appropriate metric on the data space. Identifying such a metric is particularly challenging for non-Euclidean data such as graphs. Here, we propose a pseudometric for attributed graphs, the Tree Mover’s Distance (TMD), and study its relation to generalization. Via a hierarchical optimal transport problem, TMD reflects the local distribution of node attributes as well as the distri- bution of local computation trees, which are known to be decisive for the learning behavior of graph neural networks (GNNs). First, we show that TMD captures properties relevant to graph classification: a simple TMD-SVM performs competi- tively with standard GNNs. Second, we relate TMD to generalization of GNNs under distribution shifts, and show that it correlates well with performance drop under such shifts. 

   more » « less
5. Embedding Signals on Graphs with Unbalanced Diffusion Earth Mover’s Distance

   https://doi.org/10.1109/ICASSP43922.2022.9746556  

   Tong, Alexander; Huguet, Guillaume; Shung, Dennis; Natik, Amine; Kuchroo, Manik; Lajoie, Guillaume; Wolf, Guy; Krishnaswamy, Smita (April 2022, EEE International Conference on Acoustics, Speech and Signal Processing (ICASSP))

   In modern relational machine learning it is common to encounter large graphs that arise via interactions or similarities between observations in many domains. Further, in many cases the target entities for analysis are actually signals on such graphs. We propose to compare and organize such datasets of graph signals by using an earth mover’s distance (EMD) with a geodesic cost over the underlying graph. Typically, EMD is computed by optimizing over the cost of transporting one probability distribution to another over an underlying metric space. However, this is inefficient when computing the EMD between many signals. Here, we propose an unbalanced graph EMD that efficiently embeds the unbalanced EMD on an underlying graph into an L1 space, whose metric we call unbalanced diffusion earth mover’s distance (UDEMD). Next, we show how this gives distances between graph signals that are robust to noise. Finally, we apply this to organizing patients based on clinical notes, embedding cells modeled as signals on a gene graph, and organizing genes modeled as signals over a large cell graph. In each case, we show that UDEMD-based embeddings find accurate distances that are highly efficient compared to other methods. 

   more » « less