Sketching Complexity of Graph Cuts and Compression Techniques

The Sketching Complexity of Graph Cuts Robert Krauthgamer, Weizmann Institute of Science Bertinoro workshop, May 2014 Joint work with Alexandr Andoni and David Woodruff

Compressing Graphs Vast literature on compression (succinct representation) of graphs We focus on preserving specific features distances, cuts, etc. exactly/approximately Edge sparsification: Cut and spectral sparsifiers [Benczur-Karger, , Batson-Spielman- Srivastava, ] Spanners and distance oracles [Peleg-Schaffer, , Thorup-Zwick, ] data structure (w/fast query) graphical representation Lossy Compression 2 The Sketching Complexity of Graph Cuts

Sketching Cuts Network G with edge weights ?:? ? ?+. ( huge network) Care about cuts: ? ?, ? = weight of edges between ? and ? = ? ?. G: query preprocess ? ?, ? S S data structure Goal: Small data structure that can answer cut queries (quickly) 3 The Sketching Complexity of Graph Cuts

Known Solutions Denote ? = |?(?)|. Naive: store a table of 2? cut values Fast query time O(1), but prohibitive storage Graphical: store ? itself Simple, but not fast or succinct Compute (1 + ?) cut-sparsifier ? (has approximately same cuts) Introduced by [Benczur-Karger 96], several followups [Spielman- Teng 04, Spielman-Srivastava 08, Batson-Spielman-Srivastava 09, Fung-Hariharan-Harvey-Panigrahi 11, Kapralov-Panigrahy 12] Storage: ?( ? ?2) words (using best sparsifier) Q: Improve dependence on ?? Negative evidence: ? is complete graph, ? is d-regular [Alon 97] Also for spectral sparsifiers [Batson-Spielman-Srivastava] 4 The Sketching Complexity of Graph Cuts

Our Results We achieve storage ?( ? ?) linear dependence on 1/? ? ? log? 1? , Theorem 1. There is a randomized sketch of size ? that given any ? ?, outputs w.h.p. (1 + ?)-approximation to ? ?, ? Can be viewed as a relaxation of usual cut-sparsifier A sketch, not a graph A for each guarantee, not for all We further show the second relaxation is necessary Theorem 2. Every randomized sketching achieving w.h.p. (1 + ?)- approximation for all cuts, must have size (?/?2) bits Generalizes known lower bounds: For cut-sparsifiers (even if ? is not regular) For spectral-sparsifier (even if sketch is not graphical) 5 The Sketching Complexity of Graph Cuts

UB: First Attempt Edge Sampling Suppose ? is the complete graph Standard approach: subsample edges with probability ? 1/?2 ?. Smaller probability fails: 1 ?2 1 Even for singleton cuts ? ,? ? , we now expect deg x = ? 1 Concrete difficult case: ? = ? For a random graph ??,1/2, Above argument for singleton cuts still holds They seem most difficult 1 ? ? ? Because for large sets, relative deviation (from expectation) is But vertex degrees can be stored using O(n) words And this info handles all small sets (whenever ?2 ? ? ?) 6 The Sketching Complexity of Graph Cuts

UB: Core Idea Suppose ? is unweighted, and let s handle cuts of weight 1/?2 ? ?,? ? 1 Repeatedly cut the graph along cuts of sparsity ? ? Store all cut edges Their contribution to any desired ? ?, ? is easy to compute Focus now on cuts inside one part ? ? ? Sample ? = 1/? edges out of every vertex Store additionally deg(?) for all vertices ? Assuming w.l.o.g. ? ? , estimate ? ?, ? by the difference ??= deg ? 2 ? ?,? ? ? Observation: Total sketch size is ?(?/?) Observation: The estimator is unbiased, need to analyze variance 7 The Sketching Complexity of Graph Cuts

Variance Analysis Let ??? be the degree of ? ? into ? ?, and ?? be the sample of ? = 1/? edges out of ?, and write ??? ??(?) ??= 1? ?(?,?) ? ? ? ? ? ?? The variance comes from sampling of edges 2 ??? ??? ? ??? Var ?? ? ? ? ? ? = ? ? ? ???? ?? ? ? ? ? ? ? ? ???? ? ? ? ? ? ?, ? ? + 2 ? ?2 Plugging ? ? ? ? ? ?, ? ? and ? ? ?, ? ? 1/?2, Var ?? 3?2? ? ?, ? ? 2 8 The Sketching Complexity of Graph Cuts

General Case (Polynomial Weights) Compute 2-cut-sparsifer graph ? Proceed in parallel for every guess ? = power of 2 Assume for normalization ? = 1, thus ? ?, ? 4 Importance sampling Discard edges of weight ??> 5 Surely not relevant ?? ?2,1 and assign them Sample other edges with probability ??= min new weight ??=?? ?? [?2,5] An unbiased estimator, with variance ?2? ?, ? W.h.p. the cut contains 1/?2 edges Break edges into ? log1 each level separately (using sparse-cuts), and sum up In each level, use weights they are similar and thus our variance analysis still applies ? levels ?? where ?? 2?,2?+1, estimate 9 The Sketching Complexity of Graph Cuts

Further Extensions Polynomial time: use ? Rao-Vazirani 04] (or polylog-approximation w/faster runtime) log? -approximation of sparse cuts [Arora- Two passes Unbounded weights: Compute a maximum-weight spanning tree (or Gomory-Hu tree) This tree yields a poly(?)-approximation of ? ?, ? Proceed in parallel for each such guess, by contracting very heavy edges and discarding very light ones, and applying the basic sketch 10 The Sketching Complexity of Graph Cuts

Example Application Theorem 3. A (1 + ?)-approximation of minimum-cut by a 2-pass algorithm using ?( ? ?) space ? ?2) space Known: one pass (streaming/incremental) using ?( Idea: Compute 1 + 1/log? cut-sparsifier (using known algorithm), and identify all ?(?2) candidates approximate min-cuts [Karger 00] Space ?(?) In parallel, apply our sketching algorithm, implemented in 2 passes Success probability amplified by ?(log?) repetitions Space ?( ? ?) Use our sketch to (1 + ?)-approximate each of the ?(?2) candidates, and report minimum one 11 The Sketching Complexity of Graph Cuts

LB: First Attempt One-way Comm. Theorem 2. Every randomized sketching achieving w.h.p. (1 + ?)- approximation for all cuts, must have size (?/?2) bits Natural attempt: Alice ? Bob ? ?(?) But we ve just seen Alice can send only ?(?/?) bits Must then use multiple cuts (sets ?) Assume for simplicity ? = 1/ ? 12 The Sketching Complexity of Graph Cuts

LB: Outline Alice is given a random bipartite graph ? = (?,?,?) with ? = ? = ? and edge probability Bob is given a random vertex ? ?and a random subset? ?, and has to decide whether ? ? ? is > 1 ? 1 ? ? or < 4?+ 4? ? Essentially a Gap-Hamming Distance, even for small constant ? > 0, thus requires ? communication Suppose Alice sends to Bob a sketch of all cuts of ? Bob enumerates over all ? ? of size ?/2, and estimates ?(? ?), and finds a maximizer ???? 1 4?+ and its estimator should stand out More precisely, ???? will mostly agree with ? , hence Bob can just test whether ? ???? ? ? is 1 + ? factor larger than typical ?, ? = ? ? ? ? ? > 13 The Sketching Complexity of Graph Cuts

Concluding Remarks Concrete: One pass? Avoid sparse-cut computations? Handle an (adaptive) sequence of queries? A sketch for spectral queries, i.e., quadratic forms ????? ? Abstract: Understand tradeoffs between different representations (graphical vs. data structure) Connections between distances/cuts/flows? Preserve other combinatorial features (graphs)? Thank You! 14 The Sketching Complexity of Graph Cuts