Average Distance Approximation for Static Large Graphs

Scalable Graph Coreset Selection via Greedy Sampling

This work proposes a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule, well-suited for large-scale graphs where the full Laplacian cannot be stored in memory.

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Coreset selection reduces the cost of model training by replacing a large training set with a small representative subset. Existing gradient-approximation coreset methods such as CRAIG and cluster-based variants can preserve model accuracy. Still, their selection stages often rely on dense pairwise distances or large item-cluster bound matrices, leading to high time and memory costs on large datasets. This paper proposes KNNG-CS, a lightweight coreset selection method based on a $K$-nearest neighbor graph. KNNG-CS exploits local neighborhood structures to estimate the importance of each data item and greedily selects representative nodes without maintaining a quadratic distance matrix. The method requires only linear storage in the number of edges. Experiments on four real-world datasets show that KNNG-CS achieves accuracy comparable to representative gradient-approximation coreset methods, while reducing selection time by $2.3\times$-$41.2\times$ and peak memory to $0.3\%$-$7.5\%$ of the baselines.

Almost Navigable Graphs

Graph-based methods like HNSW, DiskANN, NSG, and others have become an increasingly popular choice for implementing approximate nearest neighbor search (ANNS) in Vector Databases (VecDBs). The success of these methods has motivated the study of how to best construct a search graph for a given dataset. To that end, \emph{navigability} has been identified as a desirable graph property which ensures good ANNS performance when combined with greedy search. However, for a dataset with $n$ vectors, the sparsest navigable graph requires $O(n\sqrt{n})$ edges in the worst-case, and we show empirically that, for typical billion node datasets, 100s of edges are needed per node. This leads to slow search and high memory requirements. Moreover, under standard complexity theoretical assumptions, it was recently established that constructing a sparse navigable graph requires $\Omega(n^{2-\epsilon})$ time, which is prohibitive for large datasets. We address these concerns by introducing a relaxed notation of navigability called ``$\gamma$-almost navigability''for any $\gamma \in [0,1]$, with $\gamma = 1$ corresponding to full navigability. We prove that any dataset (under any distance) admits a $\gamma$-almost navigable graph with just $O\left(\frac{n}{1-\gamma}\right)$ edges, linear in the dataset size. We present a randomized algorithm for constructing such a graph in near-linear time. While we prove that $\gamma$-almost navigability sacrifices the worst-case search guarantees enjoyed by navigability, we show empirically that greedy beam search still performs well in such graphs when $\gamma<1$. Indeed, we obtain improved recall-runtime tradeoffs on a variety of datasets compared to fully navigable graphs. Moreover, our graphs are more space efficient, with degree typically less than half that of a fully navigable graph for comparable performance.

A Generalized Binary Tree Mechanism for Private Approximation of All-Pair Shortest Distances

We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected graph, we treat the weights of edges as sensitive information, and two graphs are neighbors if their edge weights differ in one edge by at most one. We obtain efficient algorithms with significantly improved bounds on a broad class of graphs which we refer to as recursively separable . In particular, for any n -vertex K h -minor-free graph, our algorithm achieve an additive error of (cid:101) O ( h ( nW ) 1 / 3 ) , where W represents the maximum edge weight; For grid graphs, the same algorithmic scheme achieve additive error of (cid:101) O ( n 1 / 4 √ W ) . Our approach can be seen as a generalization of the celebrated binary tree mechanism for range queries, as releasing range queries is equivalent to computing all-pair distances on a path graph. In essence, our approach is based on generalizing the binary tree mechanism to graphs that are recursively separable .

A simple and practical $o(\sqrt{n})$-time algorithm for shortest paths in power law graphs

Computing shortest paths in large graphs is, and remains, a fundamental and practically motivated problem. While many algorithms were proposed to calculate shortest path between pairs of vertices efficiently, many of them (index-based methods) require substantial preprocessing, while others (traversal-based methods) have higher time complexity. In this paper, we propose and analyze Pruned Bidirectional Search (PBS), a simple sublinear approximation algorithm for power-law graphs with parameter $\beta\in[2,3)$: our algorithm does not require any preprocessing, yet exhibits performance comparable to light index-based algorithms (of linear or sublinear index size): that is, PBS runs in time $O(n^{(1-1/\log\log n)/2})$ and, with high probability, returns a path with length within $\frac{41}{32}$ of the shortest path. Moreover, if one does allow a $n^{\Theta(2-1/\log\log n)}$-time preprocessing step, its query time improves to $n^{\Theta(1/\log\log n})$. We complement our theoretical results by experiments on both real-world and synthetic power-law graphs, which show that PBS is typically $1.84\times$-$7.76\times$ times faster than existing alternatives, while achieving an approximation ratio at most 1.05.

HP-MC: Quickly Computing Maximum Clique Sizes of Large Sparse Graphs