For a metric space (X, d), a family ℋ of locality sensitive hash functions is called (r, cr, p₁, p₂) sensitive if a randomly chosen function h ∈ ℋ has probability at least p₁ (at most p₂) to map any a, b ∈ X in the same hash bucket if d(a, b) ≤ r (or d(a, b) ≥ cr). Locality Sensitive Hashing (LSH) is one of the most popular techniques for approximate nearest-neighbor search in high-dimensional spaces, and has been studied extensively for Hamming, Euclidean, and spherical geometries. An (r, cr, p₁, p₂)-sensitive hash function enables approximate nearest neighbor search (i.e., returning a point within distance cr from a query q if there exists a point within distance r from q) with space O(n^{1+ρ}) and query time O(n^ρ) where ρ = (log 1/p₁)/(log 1/p₂). But LSH for hyperbolic spaces ℍ^d remains largely unexplored. In this work, we present the first LSH construction native to hyperbolic space. For the hyperbolic plane (d = 2), we show a construction achieving ρ ≤ 1/c, based on the hyperplane rounding scheme. For general hyperbolic spaces (d ≥ 3), we use dimension reduction from ℍ^d to ℍ² and the 2D hyperbolic LSH to get ρ ≤ 1.59/c. On the lower bound side, we show that the lower bound on ρ of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving ρ ≥ 1/c².

Over the last few years Explainable Clustering has gathered a lot of attention. Dasgupta et al. [ICML’20] initiated the study of explainable k -means and k -median clustering problems where the explanation is captured by a threshold decision tree which partitions the space at each node using axis parallel hyperplanes. Recently, Laber et al. [Pattern Recognition’23] made a case to consider the depth of the decision tree as an additional complexity measure of interest. In this work, we prove that even when the input points are in the Euclidean plane, then any depth reduction in the explanation incurs unbounded loss in the k -means and k -median cost. Formally, we show that there exists a data set X ⊆ R 2 , for which there is a decision tree of depth k − 1 whose k -means/ k -median cost matches the optimal clustering cost of X , but every decision tree of depth less than k − 1 has unbounded cost w.r.t. the optimal cost of clustering. We extend our results to the k -center objective as well, albeit with weaker guarantees.

Change point detection aims to identify abrupt shifts occurring at multiple points within a data sequence. This task becomes particularly challenging in the online setting, where different types of change can occur, including shifts in both the marginal and joint distributions of the data. In this paper, we address these challenges by tracking the Riemannian geometry of correlation matrices, allowing Riemannian metrics to compute the geodesic distance as an accurate measure of correlation dynamics.

Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clustering involve sensitive user information, therefore motivating recent studies on differentially private hierarchical clustering under the rigorous framework of Dasgupta's objective. However, it has been shown that any privacy-preserving algorithm under edge-level differential privacy necessarily suffers a large error. To capture practical applications of this problem, we focus on the weight privacy model, where each edge of the input graph is at least unit weight. We present a novel algorithm in the weight privacy model that shows significantly better approximation than known impossibility results in the edge-level DP setting. In particular, our algorithm achieves $O(\log^{1.5}n/\varepsilon)$ multiplicative error for $\varepsilon$-DP and runs in polynomial time, where $n$ is the size of the input graph, and the cost is never worse than the optimal additive error in existing work. We complement our algorithm by showing if the unit-weight constraint does not apply, the lower bound for weight-level DP hierarchical clustering is essentially the same as the edge-level DP, i.e. $\Omega(n^2/\varepsilon)$ additive error. As a result, we also obtain a new lower bound of $\tilde{\Omega}(1/\varepsilon)$ additive error for balanced sparsest cuts in the weight-level DP model, which may be of independent interest. Finally, we evaluate our algorithm on synthetic and real-world datasets. Our experimental results show that our algorithm performs well in terms of extra cost and has good scalability to large graphs.

Given a weighted graph G = (V,E,w), a (β, ε)-hopset H is an edge set such that for any s,t ∈ V, where s can reach t in G, there is a path from s to t in G ∪ H which uses at most β hops whose length is in the range [dist_G(s,t), (1+ε)dist_G(s,t)]. We break away from the traditional question that asks for a hopset H that achieves small |H| and small diameter β and instead study the sensitivity of H, a new quality measure. The sensitivity of a vertex (or edge) given a hopset H is, informally, the number of times a single hop in G ∪ H bypasses it; a bit more formally, assuming shortest paths in G are unique, it is the number of hopset edges (s,t) ∈ H such that the vertex (or edge) is contained in the unique st-path in G having length exactly dist_G(s,t). The sensitivity associated with H is then the maximum sensitivity over all vertices (or edges). The highlights of our results are: - A construction for (Õ(√n), 0)-hopsets on undirected graphs with O(log n) sensitivity, complemented with a lower bound showing that Õ(√n) is tight up to polylogarithmic factors for any construction with polylogarithmic sensitivity. - A construction for (n^o(1), ε)-hopsets on undirected graphs with n^o(1) sensitivity for any ε > 0 that is at least inverse polylogarithmic, complemented with a lower bound on the tradeoff between β, ε, and the sensitivity. - We define a notion of sensitivity for β-shortcut sets (which are the reachability analogues of hopsets) and give a construction for Õ(√n)-shortcut sets on directed graphs with O(log n) sensitivity, complemented with a lower bound showing that β = Ω̃(n^{1/3}) for any construction with polylogarithmic sensitivity. We believe hopset sensitivity is a natural measure in and of itself, and could potentially find use in a diverse range of contexts. More concretely, the notion of hopset sensitivity is also directly motivated by the Differentially Private All Sets Range Queries problem [Deng et al. WADS 23]. Our result for O(log n) sensitivity (Õ(√n), 0)-hopsets on undirected graphs immediately improves the current best-known upper bound on utility from Õ(n^{1/3}) to Õ(n^{1/4}) in the pure-DP setting, which is tight up to polylogarithmic factors.

The Johnson-Lindenstrauss (JL) lemma is a cornerstone of dimensionality reduction in Euclidean space, but its applicability to non-Euclidean data has remained limited. This paper extends the JL lemma beyond Euclidean geometry to handle general dissimilarity matrices that are prevalent in real-world applications. We present two complementary approaches: First, we show how the JL transform can be applied to vectors in pseudo-Euclidean space with signature $(p,q)$, providing theoretical guarantees that depend on the ratio of the $(p, q)$ norm and Euclidean norm of two vectors, measuring the deviation from Euclidean geometry. Second, we prove that any symmetric hollow dissimilarity matrix can be represented as a matrix of generalized power distances, with an additional parameter representing the uncertainty level within the data. In this representation, applying the JL transform yields multiplicative approximation with a controlled additive error term proportional to the deviation from Euclidean geometry. Our theoretical results provide fine-grained performance analysis based on the degree to which the input data deviates from Euclidean geometry, making practical and meaningful reduction in dimensionality accessible to a wider class of data. We validate our approaches on both synthetic and real-world datasets, demonstrating the effectiveness of extending the JL lemma to non-Euclidean settings.

The hereditary discrepancy of a set system is a certain quantitative measure of the pseudorandom properties of the system. Roughly, hereditary discrepancy measures how well one can $2$-color the elements of the system so that each set contains approximately the same number of elements of each color. Hereditary discrepancy has well-studied applications e.g. in communication complexity and derandomization. More recently, the hereditary discrepancy of set systems of shortest paths has found applications in differential privacy [Chen et al.~SODA 23]. The contribution of this paper is to improve the upper and lower bounds on the hereditary discrepancy of set systems of unique shortest paths in graphs. In particular, we show that any system of unique shortest paths in an undirected weighted graph has hereditary discrepancy $\widetilde{O}(n^{1/4})$, and we construct lower bound examples demonstrating that this bound is tight up to hidden $\text{polylog } n$ factors. Our lower bounds apply even in the planar and bipartite settings, and they improve on a previous lower bound of $Ω(n^{1/6})$ obtained by applying the trace bound of Chazelle and Lvov [SoCG'00] to a classical point-line system of Erdős. As applications, we improve the lower bound on the additive error for differentially-private all pairs shortest distances from $Ω(n^{1/6})$ [Chen et al.~SODA 23] to $Ω(n^{1/4})$, and we improve the lower bound on additive error for the differentially-private all sets range queries problem to $Ω(n^{1/4})$, which is tight up to hidden $\text{polylog } n$ factors [Deng et al.~WADS 23].

We introduce \textbf{N}on-\textbf{Euc}lidean-\textbf{MDS} (Neuc-MDS), which extends Multidimensional Scaling (MDS) to generate outputs that can be non-Euclidean and non-metric. The main idea is to generalize the inner product to other symmetric bilinear forms to utilize the negative eigenvalues of dissimiliarity Gram matrices. Neuc-MDS efficiently optimizes the choice of (both positive and negative) eigenvalues of the dissimilarity Gram matrix to reduce STRESS, the sum of squared pairwise error. We provide an in-depth error analysis and proofs of the optimality in minimizing lower bounds of STRESS. We demonstrate Neuc-MDS's ability to address limitations of classical MDS raised by prior research, and test it on various synthetic and real-world datasets in comparison with both linear and non-linear dimension reduction methods.

Structural balance theory studies stability in networks. Given a $n$-vertex complete graph $G=(V,E)$ whose edges are labeled positive or negative, the graph is considered \emph{balanced} if every triangle either consists of three positive edges (three mutual ``friends''), or one positive edge and two negative edges (two ``friends'' with a common ``enemy''). From a computational perspective, structural balance turns out to be a special case of correlation clustering with the number of clusters at most two. The two main algorithmic problems of interest are: $(i)$ detecting whether a given graph is balanced, or $(ii)$ finding a partition that approximates the \emph{frustration index}, i.e., the minimum number of edge flips that turn the graph balanced. We study these problems in the streaming model where edges are given one by one and focus on \emph{memory efficiency}. We provide randomized single-pass algorithms for: $(i)$ determining whether an input graph is balanced with $O(\log{n})$ memory, and $(ii)$ finding a partition that induces a $(1 + \varepsilon)$-approximation to the frustration index with $O(n \cdot \text{polylog}(n))$ memory. We further provide several new lower bounds, complementing different aspects of our algorithms such as the need for randomization or approximation. To obtain our main results, we develop a method using pseudorandom generators (PRGs) to sample edges between independently-chosen \emph{vertices} in graph streaming. Furthermore, our algorithm that approximates the frustration index improves the running time of the state-of-the-art correlation clustering with two clusters (Giotis-Guruswami algorithm [SODA 2006]) from $n^{O(1/\varepsilon^2)}$ to $O(n^2\log^3{n}/\varepsilon^2 + n\log n \cdot (1/\varepsilon)^{O(1/\varepsilon^4)})$ time for $(1+\varepsilon)$-approximation. These results may be of independent interest.

Full waveform inversion (FWI) is widely used in geophysics to reconstruct high-resolution velocity maps from seismic data. The recent success of data-driven FWI methods results in a rapidly increasing demand for open datasets to serve the geophysics community. We present OpenFWI, a collection of large-scale multi-structural benchmark datasets, to facilitate diversified, rigorous, and reproducible research on FWI. In particular, OpenFWI consists of $12$ datasets ($2.1$TB in total) synthesized from multiple sources. It encompasses diverse domains in geophysics (interface, fault, CO$_2$ reservoir, etc.), covers different geological subsurface structures (flat, curve, etc.), and contain various amounts of data samples (2K - 67K). It also includes a dataset for 3D FWI. Moreover, we use OpenFWI to perform benchmarking over four deep learning methods, covering both supervised and unsupervised learning regimes. Along with the benchmarks, we implement additional experiments, including physics-driven methods, complexity analysis, generalization study, uncertainty quantification, and so on, to sharpen our understanding of datasets and methods. The studies either provide valuable insights into the datasets and the performance, or uncover their current limitations. We hope OpenFWI supports prospective research on FWI and inspires future open-source efforts on AI for science. All datasets and related information can be accessed through our website at https://openfwi-lanl.github.io/

Applying Global Self-attention (GSA) mechanism over features has achieved remarkable success on Convolutional Neural Networks (CNNs). However, it is not clear if Graph Convolutional Networks (GCNs) can similarly benefit from such a technique. In this paper, inspired by the similarity between CNNs and GCNs, we study the impact of the Global Self-attention mechanism on GCNs. We find that consistent with the intuition, the GSA mechanism allows GCNs to capture feature-based vertex relations regardless of edge connections; As a result, the GSA mechanism can introduce extra expressive power to the GCNs. Furthermore, we analyze the impacts of the GSA mechanism on the issues of overfitting and over-smoothing. We prove that the GSA mechanism can alleviate both the overfitting and the over-smoothing issues based on some recent technical developments. Experiments on multiple benchmark datasets illustrate both superior expressive power and less significant overfitting and over-smoothing problems for the GSA-augmented GCNs, which corroborate the intuitions and the theoretical results.

The ability to capture relations within data can provide the much needed inductive bias for robust and interpretable Machine Learning algorithms. Variational Autoencoder (VAE) is a promising candidate for such purpose thanks to their power in data representation inference, but its vanilla form and common variations cannot process feature relations. In this paper, inspired by recent advances in relational learning with graph neural networks, we propose the Self-Attention Graph Variational AutoEncoder (SAG-VAE) model which can simultaneously learn feature relations and data representations in an end-to-end manner. The SAG-VAE is trained by jointly inferring the posterior distribution of two types of latent variables, which respectively represent the data and the feature relations. The feature relations are represented as a graph structure, and the presence of each edge is determined by a Gumbel-Softmax distribution. The generative model is accordingly parameterized by a graph neural network with a special attention mechanism we introduced in the paper. Therefore, the SAG-VAE model can generate via graph convolution and be trained via backpropagation. Experiments based on graphs show that SAG-VAE is capable of approximately retrieving edges and links between vertices based entirely on feature observations. Furthermore, experiments on image data illustrate that the learned feature relations can provide the SAG-VAE robustness against perturbations in image reconstruction and sampling. The learned feature relations as graph adjacency matrices are observed to be structured, which provides intuitive interpretability of the models.