2025· Advances in Neural Information Processing Systems 38· pp. 40931-40960· 0 citations· 47 references
TL;DR
The problem of approximating all-pair distances in a weighted undirected graph with differential privacy is studied, and efficient algorithms with significantly improved bounds are obtained on a broad class of graphs which are referred to as recursively separable.
Abstract
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 .
The Graph Edit Distance (GED) is a widely used graph similarity measure asking for the minimum cost of a sequence of edits transforming one (labeled) graph into another. The considered edit operations are deletion, insertion, and relabeling of nodes and edges. Special cases include the Graph Isomorphism problem, as well as many other graph problems that ask for the existence or minimum cost of a certain substructure, like the Traveling Salesman or Maximum Clique problem. We present a novel exponential time algorithm to compute the exact GED and a corresponding edit sequence in $O^*(4 + \varepsilon)^n$ time and polynomial space, provided one of the two graphs admits strictly sublinear balanced separators. In particular, the claimed runtime holds if one of the graphs is $K_h$-minor free (e.g., planar), or has bounded treewidth, which is the case for many real-world applications (e.g., all instances in GEDLIB). This substantially improves the best known worst-case running time bounds of $O^*(n!)$ for these graph classes.
L. Bülte, Philip Mayer, Lars Müller et al.· 0 citations
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new $\widetilde{O}(n^{3/2})$-bit protocol for computing a maximum matching in general graphs. While the same upper bound can be obtained by simulating the classic algorithms of Micali-Vazirani and Gabow, our protocol is conceptually simple and avoids the intricacies of finding a maximal set of shortest augmenting paths; (2) a new $\widetilde{O}(n)$-bit protocol for negative-cycle detection and negative-weight single-source shortest paths. Our protocol simplifies that of Blikstad et al. by replacing a long chain of reductions with a more direct approach based on vertex potentials; (3) a combinatorial $\widetilde{O}(n)$-bit protocol for computing a maximum matching in bipartite graphs, obtained by reinterpreting the near-linear communication protocol of Blikstad et al. through a discretized analysis. Together, these results provide simpler protocols for several basic graph problems. We hope they will inspire further advances on the communication complexity of a wide range of graph problems.
Yu Cheng, Tianle Jiang, Pachara Sawettamalya et al.· 0 citations
We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm\epsilon)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_{\epsilon}(n^2)$ and worst-case query time $\widetilde{O}_{\epsilon}(1)$. Thus, for dense graphs where $m = \Omega(n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\widetilde{O}(n/\epsilon)$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\widetilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
Investigating the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover, presents randomized distributed algorithms that achieve nearly exponentially smaller energy complexity.
Mohsen Ghaffari, Zi Song Yeoh· ACM Symposium on Parallelism...· 1 citation
The findings indicate that the Eppstein-Wang algorithm provides a practical and scalable solution for average distance estimation, with higher reliability on unipartite graphs compared to bipartite graphs.