PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully Dynamic Random-Walk Quantities on Undirected Expanders and $\kappa$-Uniform Directed Graphs

Richard Peng, Sushant Sachdeva, Junzhao Yang, Yibin Zhao

arXiv:2610.17712v1cs.DS

TL;DR

Fully dynamic data structures for random-walk quantities raise different challenges on undirected expanders and directed graphs. The paper maintains short random walks for undirected expanders, proves an OMv-based barrier for rapidly mixing directed graphs, and studies the more restricted κ-uniform setting. It reports efficient data structures in these settings, with the directed hardness conditional on OMv.

  • Problem

    Fully dynamic data structures for random-walk quantities on expanders are underexplored, while rapid mixing alone does not resolve the difficulty of estimating stationary distributions accurately in dynamic directed graphs.

    Source: §1 · p. 1, §1.1 · p. 2

  • Method

    The paper dynamically maintains short random walks for undirected expanders and uses stationary-distribution uniformity to extend random-walk approaches to κ-uniform directed graphs.

    Source: §1 · p. 1, §1.1 · pp. 2–3

  • Results

    The paper gives dynamic effective-resistance structures for undirected expanders, an OMv-based update/query lower bound for rapidly mixing directed graphs, and efficient algorithms for κ-uniform directed graphs.

    Source: §1 · p. 1, §1.1 · p. 3

  • Takeaways & Limitations

    The paper identifies stationary-distribution uniformity, beyond rapid mixing, as a condition under which efficient dynamic random-walk approaches are possible for directed graphs.

    Source: §1 · p. 2, §1.1 · p. 3

    The directed-graph lower bound is conditional on OMv and applies even when mixing time is O(log n) and all outdegrees are constant.

    Source: §1 · p. 2, §2 · p. 4

Abstract

from arXiv · show

We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $\gamma$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(\gamma^{-4}\varepsilon^{-2}\log n\log^4(n/\varepsilon))$ and expected $O(1)$ query time. For directed graphs, somewhat surprisingly, the OMv conjecture precludes a fast data structure based on rapid mixing conditions alone. To address this, we introduce the notion of $\kappa$-uniform directed graphs, which requires the stationary distribution to $\kappa$-approximate the uniform distribution, and show that in this setting, random walk based data structures with $\text{poly}(\kappa, \log{n}, \varepsilon^{-1})$ update/query times are possible.

1 Introduction

The paper studies dynamic random-walk quantities, addressing the lack of fully dynamic data structures for expander graphs and the limits of rapid mixing alone for directed graphs. It develops dynamic short-walk methods for undirected expanders and κ-uniform directed graphs, alongside an OMv-based hardness result for directed graphs.

1 Introduction

  • The expander paradigm typically solves problems on general graphs through a sequence of expander problems stitched together at their boundaries.The paper identifies fully dynamic problems on graphs that always remain expanders as an underexplored setting.Source: §1 · p. 1
  • For undirected expanders, dynamically maintained short walks support approximate all-pairs effective-resistance queries, substantially improving on the general dynamic-graph runtime of about m^(2/3).The approach builds on Li and Sachdeva, whose static data structure answers queries in essentially constant time.Source: §1 · pp. 1–2, §1.1 · p. 2

1.1 Overview

  • The paper maintains short random walks dynamically on unweighted undirected graphs, using selective resampling and degree-bounded congestion to achieve eO(1) update time.Only roughly a 1/d_v fraction of walks incident to an affected vertex v need resampling; total walk steps are eO(n).Source: §1.1 · p. 2
  • Rapid mixing alone does not suffice for similarly efficient directed-graph data structures because hitting and commute times require high-accuracy stationary-distribution estimates.The paper establishes this obstacle through a conditional hardness result based on OMv.Source: §1.1 · p. 2, §1 · p. 2
  • The directed-graph reduction yields a roughly square-root update- and query-time lower bound, even on graphs that are O(log n)-mixing with constant outdegrees.It encodes matrix-vector multiplication in a graph of size O(n^2), with path existence changing stationary probabilities at selected vertices.Source: §1.1 · pp. 2–3
  • For κ-uniform directed graphs, stationary-distribution uniformity bounds short-walk congestion by eO(κ^c), allowing efficient dynamic stationary-distribution and commute-time algorithms.The paper states that κ-mixing alone does not guarantee this congestion bound.Source: §1 · p. 2, §1.1 · p. 3

2 Preliminaries

The preliminaries specify the graph and random-walk settings, define mixing conditions, and state the OMv assumption used for the conditional hardness result.

2 Preliminaries

  • The preliminaries use the adjacency and degree matrices to specify the Laplacian for undirected graphs and the out-degree matrix for directed graphs.The supplied directed-walk definition identifies the lazy transition matrix, though its displayed expression is incomplete.Source: §2 · p. 3
  • A connected undirected graph is a γ-spectral expander when the second eigenvalue of its normalized Laplacian is at least γ; such expanders are O(γ^−1 log n)-mixing.The supplied proof passage gives the mixing-time bound from the spectral-gap condition.Source: §2 · p. 3
  • The paper defines κ-mixing for strongly connected directed graphs in terms of the stationary distribution of the lazy random walk.For κ-uniform graphs, it additionally requires the stationary distribution to be close to uniform.Source: §2 · pp. 3–4
  • For connected unweighted undirected graphs, commute time equals 2m times effective resistance, linking the random-walk and electrical quantities studied in the paper.Commute time is the sum of the two directed hitting times between a pair of vertices.Source: §2 · p. 4
  • The conditional hardness result invokes OMv, which conjectures that no randomized algorithm solves online Boolean matrix-vector multiplication in O(n^(3−δ)) total time for any constant δ > 0.The stated success probability threshold is at least 2/3.Source: §2 · p. 4

3 Fully Dynamic Effective Resistances on Expanders

The section turns short random walks into a fully dynamic effective-resistance data structure for unweighted undirected expanders, building on Li and Sachdeva’s static approach. Its walk-maintenance method controls update costs through sparse repairs and congestion bounds, while the maintained walks support resistance queries.

3 Fully Dynamic Effective Resistances on Expanders

  • Theorem 3.1 gives (1 + ε)-approximate effective resistance and commute-time queries in expected O(1) time, with expected update time O(γ^-4 ε^-2 log n log^4(n/ε)).The result is for fully dynamic unweighted undirected γ-expanders and succeeds with high probability.Source: §3 · p. 5

3.1 Fully Dynamic Short Random Walks

  • The method maintains uniform lazy random walks for every vertex and length k < ℓ; the walk-maintenance algorithm also applies to unweighted undirected graphs that are not expanders.The expander-specific resistance result applies this dynamic walk data structure to the static approach of Li and Sachdeva [LS23].Source: §3.1 · p. 5, §3 · p. 5
  • Vertex congestion is O(sℓ^2d_v), edge congestion is O(sℓ^2), and maintaining the walks costs expected O(sℓ^3) time and O(sℓ^2) recourse per update.The congestion bounds explain why only a limited number of walks need repair when an edge changes.Source: §3.1 · pp. 5–6
  • After an edge insertion or deletion, the algorithm repairs affected walks by resampling their suffixes, preserving fresh, mutually independent walks in the updated graph.For insertions, it samples affected incidences before repairing suffixes; for deletions, it retains only the earliest traversal of the deleted edge.Source: §3.1 · pp. 6–7

3.2 Proof of Theorem 3.1

  • The resistance estimator uses the difference hitting vector, for which 2D^-1h_uv solves Lx = e_u − e_v; only sparse hitting vectors need to be stored.The stationary terms cancel in the query expression, so the stationary term is used only in the approximation analysis.Source: §3.2 · p. 7
  • With the walk parameters required by, the maintained walks inherit its static approximation guarantee at any fixed time with very high probability, and queries take expected O(1) time.A query reads four hitting-vector coordinates and two current degrees.Source: §3.2 · p. 8

4 Conditional Hardness for κ-Mixing Graphs

The section proves that rapid mixing and bounded outdegree alone do not suffice for fast dynamic stationary-distribution queries under OMv. Its reduction encodes Boolean matrix–vector products in a rapidly mixing directed graph, while making product bits distinguishable from stationary probabilities.

4 Conditional Hardness for κ-Mixing Graphs

  • Assuming OMv, no randomized fully dynamic structure achieves both update and query time O(n^(1/2−δ)) for (1 + 0.5)-approximate stationary queries on O(log n)-mixing directed graphs of maximum outdegree four.The theorem assumes polynomial preprocessing and states the bound for every constant δ > 0.Source: §4 · p. 8, §4.2 · p. 12

4.2 Proof of Theorem 4.1

  • The reduction updates vector edges to encode each input vector, queries row vertices, and combines block products by OR to simulate OMv.Partitioning into blocks lets the argument bypass large polynomial preprocessing time and derive a contradiction from the online running time.Source: Figure 1 · p. 9, §4.1 · p. 10, §4.2 · pp. 11–12

4.1 From Matrix Vector Product to Fast Mixing Graphs

  • The graph GM,v has Θ(q²) vertices, outdegree at most four, and mixing time O(log q), yet its stationary mass at row vertex ri distinguishes whether [Mv]i = 1.The construction makes a product-bit path from s to ri when the bit is one; a (1 + 0.5)-approximation suffices for distinguishing the cases.Source: §4.1 · pp. 10–11

5 Fully Dynamic Algorithms for κ-Uniform Graphs

For directed κ-uniform graphs, the paper maintains dynamic short random walks to approximate stationary distributions and all-pairs commute times. The resulting structures support expected O(1) query time, with high-probability guarantees under the stated settings.

5 Fully Dynamic Algorithms for κ-Uniform Graphs

  • For κ-uniform directed graphs, dynamic short random walks yield entry-wise (1 + ε)-approximate stationary queries and (1 + ε)-approximate all-pairs commute-time queries, each in expected O(1) query time.The commute-time guarantee holds with high probability over an oblivious polynomial-length update sequence.Source: §5 · pp. 12–13

5.1 Dynamic Random Walks on κ-Uniform Graphs

  • The dynamic (ℓ, s)-walk structure uses expected O(κ²sℓ³) update time and O(κ²sℓ²) recourse per update, with O(m + nsℓ²) preprocessing time and space.The congestion guarantee for these walks is O(sℓ²κ²) in expectation for each vertex and edge.Source: §5.1 · p. 13

5.2 Dynamic Stationary Approximation

  • Stationary-distribution approximation uses short walks from uniform starting vertices and concentrates the sampled hitting vectors with s ≥ C′κε−2 log n walks per vertex.The resulting data structure supports entry-wise approximate stationary queries in expected O(1) time.Source: §5 · p. 12, §5.2 · pp. 13–14

5.3 Dynamic Commute Time Estimations

  • Commute-time estimation combines truncated hitting-vector estimates with an approximate stationary distribution; its queries read a constant number of counters and take expected O(1) time.The structure succeeds with high probability over an oblivious polynomial-length update sequence.Source: §5 · p. 13, §5.3 · p. 16
Loading 2610.17712v1…