Spectral Sparsification of Hypergraphs

My talk slide at ISMP 2024. A part of it is presented in IPCO 2024 for our paper "Online Algorithms for Spectral Hypergraph Sparsification".

Transcript

1. Spectral Sparsification of Hypergraphs Tasuku Soma (Institute of Statistical Mathematics; Tokyo) Joint work with Kam Chuen Tung (Univerisity of Waterloo) Yuichi Yoshida (Natinal Institute of Informatics; Tokyo) 1 / 20
2. 1 Overview 2 Algorithm 3 Summary 2 / 20
3. Graph Laplacian G = (V, E, w): (undirected) graph with edge weight w ∈ RE + Graph Laplacian Matrix LG = e={i,j}∈E we (ei − ej )(ei − ej )⊤ 3 / 20
4. Graph Laplacian G = (V, E, w): (undirected) graph with edge weight w ∈ RE + Graph Laplacian Matrix LG = e={i,j}∈E we (ei − ej )(ei − ej )⊤ Quadratic form x⊤LG x = e={i,j}∈E we (xi − xj )2 Energy of G (as circuit) with potential x 3 / 20
5. Graph Laplacian G = (V, E, w): (undirected) graph with edge weight w ∈ RE + Quadratic form x⊤LG x = e={i,j}∈E we (xi − xj )2 Cut function For a vertex set X ⊆ V , κG (X) = {i,j}∈E:|{i,j}∩X|=1 we = 1⊤ X LG 1X . X The cut function is the quadratic form of Laplacian. 3 / 20
6. Spectral Graph Sparsification [Spielman, Teng 2011] A weighted subgraph ˜ G = (V, ˜ E , ˜ w ) of G is an ε-spectral sparsifier △ ⇐⇒ (1 − ε)x⊤LG x ≤ x⊤L ˜ G x ≤ (1 + ε)x⊤LG x (∀x ∈ RV ) edge weight can be modified edge subset ˜ E ⊆ E G ˜ G • Spectral spasifier =⇒ all cuts are preserved (i.e., cut sparsifier) • Current best: O(n/ε2) edges [Batson, Spielman, Srivastava 2014; Y. T. Lee, Sun 2015] 4 / 20
7. Hypergraph Cut H = (V, E): hypergraph with edge weight w ∈ RE + Hypergraph cut function For vertex subset X ⊆ V , κH (X) = e∈E:0<|e∩X|<|e| we Hypergraph cut functions are NOT quadratic forms! 5 / 20
8. Spectral Hypergraph Sparsification [Soma, Yoshida 2019] Energy function QH (x) = e we max i,j∈e (xi − xj )2 Especially, QH (1X ) = κH (X) for X ⊆ V . 6 / 20
9. Spectral Hypergraph Sparsification [Soma, Yoshida 2019] Energy function QH (x) = e we max i,j∈e (xi − xj )2 Especially, QH (1X ) = κH (X) for X ⊆ V . A weighted subhypergraph ˜ H of H is an ε-spectral sparsifier △ ⇐⇒ (1 − ε)QH (x) ≤ Q ˜ H (x) ≤ (1 + ε)QH (x) (∀x ∈ RV ) spectral sparsifier =⇒ cut sparsifier [Kogan, Krauthgamer 2015] 6 / 20
10. Our Result Our result (Soma, Yoshida SODA’19) For any hypergraph H and ε ∈ (0, 1), we can construct an ε-spectral sparsifier ˜ H with O n3 log n ε2 many hyperedges in polynomial time w.h.p. (n = |V |) Applications • Speeding up algorithms for cuts/flows in hypergraphs; • Semi-supervised learning on hypergraphs [Zhang, Hu, Tang, Chan 2017]. • Agnostic learning of hypernetwork type submodular functions 7 / 20
11. Known bounds for offline sparsification reference cut spectral Kogan, Krauthgamer (2015) O(n(r+log n) ε2 ) Soma, Yoshida (2019) O(n3 ε2 log n) Bansal, Svensson, Trevisan (2019) O(nr3 ε2 log n) Chen, Khanna, Nagda (2020) O( n ε2 log n) Kapralov, Krauthgamer, Tardos, Yoshida (2021) ˜ O( nr εO(1) ) Kapralov, Krauthgamer, Tardos, Yoshida (2022) O( n ε4 log3 n) J. R. Lee (2023) Jambulapati, Liu, Sidford (2023) O( n ε2 log n log r) n = |V |, r = maxe∈E |e| 8 / 20
12. Drawbacks of offline sparsification algorithms To store an input hypergraph, we need space of size exponential in n in the worst case. On the other hand, output sparsifiers have only O(ε−2n log n log r) hyperedges, which is nearly linear! Q. Is it possible to construct a spectral sparsifier of hypergraphs using only polynomial space? 9 / 20
13. Online hypergraph spectral sparsification • Hyperedges and weights (e1 , w1 ), (e2 , w2 ), . . . , (em , wm ) arrive in stream • When (ei , wi ) arrives, we must irrevocably decide whether to include ei as well as its weight in ˜ H • Only poly(n) working space is available 10 / 20
14. Online hypergraph spectral sparsification • Hyperedges and weights (e1 , w1 ), (e2 , w2 ), . . . , (em , wm ) arrive in stream • When (ei , wi ) arrives, we must irrevocably decide whether to include ei as well as its weight in ˜ H • Only poly(n) working space is available A weighted subhypergraph ˜ H of H is an (ε, δ)-spectral sparsifier △ ⇐⇒ (1 − ε)QH (x) − δ∥x∥2 2 ≤ Q ˜ H (x) ≤ (1 + ε)QH (x) + δ∥x∥2 2 (∀x ∈ RV ) 10 / 20
15. Online hypergraph spectral sparsification • Hyperedges and weights (e1 , w1 ), (e2 , w2 ), . . . , (em , wm ) arrive in stream • When (ei , wi ) arrives, we must irrevocably decide whether to include ei as well as its weight in ˜ H • Only poly(n) working space is available A weighted subhypergraph ˜ H of H is an (ε, δ)-spectral sparsifier △ ⇐⇒ (1 − ε)QH (x) − δ∥x∥2 2 ≤ Q ˜ H (x) ≤ (1 + ε)QH (x) + δ∥x∥2 2 (∀x ∈ RV ) Theorem (Soma, Tung, and Yoshida IPCO’24) There is an online algorithm that outputs an (ε, δ)-spectral sparsifier with O(n log n log r ε2 log(εW/δn)) many hyperedges using O(n2) space. (Here, W = i wi) 10 / 20
16. 1 Overview 2 Algorithm 3 Summary 11 / 20
17. Edge sampling algorithm Algorithm 1: Compute edge sampling probability pe ∈ [0, 1] for every hyperedge e ∈ E. 2: for each hyperedge e : 3: Add a copy of e to ˜ H with weight we /pe w.p. pe . Properties • E ˜ H [Q ˜ H (x)] = QH (x) (i.e., unbiased) • Expected total # of hyperedges = e pe 12 / 20
18. Challenge small pe large pe # edges sparse dense variance large small Need to carefully design pe that balances both! 13 / 20
19. Reweighting [Kapralov, Krauthgamer, Tardos, Yoshida 2022; J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] Clique expansion: G = (V, F), each hyperedge being replaced with clique 14 / 20
20. Reweighting [Kapralov, Krauthgamer, Tardos, Yoshida 2022; J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] Clique expansion: G = (V, F), each hyperedge being replaced with clique Lemma ([Kapralov, Krauthgamer, Tardos, Yoshida 2022; J. R. Lee 2023]) There is an edge weight ce,u,v ≥ 0 on F such that • u,v∈e ce,u,v = we (e ∈ E) • ce,u,v > 0 =⇒ ru,v = maxu′,v′∈e ru′,v′ , where ru,v is the effective resistance between u, v. Effective resistance: ru,v = (eu − ev)⊤L+ G (eu − ev) 14 / 20
21. Reweighting [Kapralov, Krauthgamer, Tardos, Yoshida 2022; J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] Clique expansion: G = (V, F), each hyperedge being replaced with clique Lemma ([Kapralov, Krauthgamer, Tardos, Yoshida 2022; J. R. Lee 2023]) There is an edge weight ce,u,v ≥ 0 on F such that • u,v∈e ce,u,v = we (e ∈ E) • ce,u,v > 0 =⇒ ru,v = maxu′,v′∈e ru′,v′ , where ru,v is the effective resistance between u, v. Effective resistance: ru,v = (eu − ev)⊤L+ G (eu − ev) Given {ce,u,v }, setting pe ∝ we maxu,v∈e ru,v yields ε-spectral sparsifier with O(ε−2n log n log r) hyperedges. [J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] Graph case: effective registance sampling [Spielman, Srivastava 2011] 14 / 20
22. Convex optimization for reweighting [J. R. Lee 2023] The edge weight {ce,u,v } can be found by convex optimization: max log det   e∈E u,v∈V ce,u,v Lu,v + J   sub. to u,v∈e ce,u,v = we (e ∈ E) ce,u,v ≥ 0 (e ∈ E, u, v ∈ e) Lu,v := (eu −ev )(eu −ev )⊤ J: all-one matrix KKT condition =⇒ the required conditions for reweighting. 15 / 20
23. Our online algorithm (cf. online spectral sparsification of graphs [Cohen, Musco, Pachocki 2020]) Let η = δ/ε > 0. (regularization parameter) Define matrix Li (i = 0, 1, . . . ) as follows: • L0 = On , • Li = Li−1 + u,v∈ei wi ci,u,v Lu,v , where ci,u,v is the solution of the following convex optimization: max ci∈∆ei log det Li−1 + u,v∈ei wi ci,u,v Lu,v + ηIn Laplacian matrix up to i − 1 ridge regularizer ∆e : probability simplex in R (e 2 ) 16 / 20
24. Our online algorithm Let η = δ/ε > 0. 1: ˜ H0 := ∅, L0 := On 2: for i = 1, 2, . . . : 3: Solve the following convex optimization: max ci∈∆ei log det Li−1 + u,v∈ei wi ci,u,v Lu,v + ηIn 4: Li ← Li−1 + u,v∈ei wi ci,u,v Lu,v 5: pe ∝ wi maxu,v∈ei ∥(Li + ηI)−1/2(eu − ev )∥2 2 . 6: Add ei with weight wi /pe to ˜ Hi−1 with probability pe and obtain ˜ Hi . Laplacian matrix for reweighted clique expansion ridge regularizer ridged effective resistance ∆e : prob. simplex in R (e 2 ) Lu,v := (eu −ev )(eu −ev )⊤ 17 / 20
25. Analysis Hi : input hypergraph up to time i Our algorithm satisfies: • Li depends only on Hi , not on algorithm’s random choice. −→ Sampling of each ei is independent • ˜ Hi is an (ε, δ)-spectral sparsifier of Hi w.h.p. The expected # of hyperedges = O(n log n log r ε2 log(εW/δn)) (application of chaining analysis by [J. R. Lee 2023] ) • maintains only sparsifier ˜ Hi and Laplacian matrix Li −→ O(n2) space 18 / 20
26. 1 Overview 2 Algorithm 3 Summary 19 / 20
27. Summary • Introduced the concept of spectral sparsification of hypergraphs. [Soma, Yoshida 2019] • Current best: O n log n log r ε2 hyperedges. [J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] • Online algorithm: O(n log n log r ε2 log(εW/δn)) hyperedges with O(n2) space • We also show the number of hyperedges is tight for online setting 20 / 20
28. Summary • Introduced the concept of spectral sparsification of hypergraphs. [Soma, Yoshida 2019] • Current best: O n log n log r ε2 hyperedges. [J. R. Lee 2023; Jambulapati, Liu, Sidford 2023] • Online algorithm: O(n log n log r ε2 log(εW/δn)) hyperedges with O(n2) space • We also show the number of hyperedges is tight for online setting Thanks! Questions? 20 / 20