Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
Authors: Vincent Cohen-Addad
David Woodruff
Shenghao Xie
Samson Zhou
Venue: ICLR 2026 Poster (2026)
Keywords: streaming algorthms
graph sparsification
adversarial robustness
Primary area: optimization

Abstract: We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H=(V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$, and the goal is to compute a hypergraph $\widehat{H}$ that preserves the energy of each vector $x \in \mathbb{R}^n$ in $H$, up to a small multiplicative error. In this paper, we give a streaming algorithm that achieves a $(1+\varepsilon)$-approximation, using $\mathcal{O}\left(\frac{rn}{\varepsilon^2} \log^2 n \log r\right) \cdot$ poly $(\log \log m)$ bits of space, matching the sample complexity of the best known offline algorithm up to poly $(\log \log m)$ factors. Our approach also provides a streaming algorithm for graph sparsification that achieves a $(1+\varepsilon)$-approximation, using $\mathcal{O}\left(\frac{n}{\varepsilon^2} \log n\right)\cdot\text{poly}(\log\log n)$ bits of space, improving the current bound by $\log n$ factors. Furthermore, we give a space-efficient streaming algorithm for min-cut approximation. Along the way, we present an online algorithm for $(1+\varepsilon)$-hypergraph sparsification, which is optimal up to poly-logarithmic factors. Hence, we achieve $(1+\varepsilon)$-hypergraph sparsification in the sliding window model, with space optimal up to poly-logarithmic factors. Lastly, we give an adversarially robust algorithm for hypergraph sparsification using $\frac{n}{\varepsilon^2} \cdot $ poly $(r, \log n, \log r, \log \log m)$ bits of space.

Published as a conference paper at ICLR 2026
NEARLY SPACE-OPTIMAL GRAPH AND HYPERGRAPH SPARSIFICATION IN INSERTION-ONLY DATA STREAMS
Vincent Cohen-Addad
David P. Woodruff
Shenghao Xiel
Samson Zhou
ABSTRACT
We study the problem of graph and hypergraph sparsification in insertion-only data streams. The imput is hypergraph H (V, E, w) with nodes, m hyper- edges, and rank and the goal is to compute a hypergraph H that preserves the energy of each vector E IR" in H, up to a small multiplicative error. In this paper, we give a streaming algorithm that achieves a (1+ =pppropppooiiitiinnn using ( log n logr). poly (log log m) bits of space, matching the sample com- plexity of the best known offline algorithm up poly (log log m) factors. Our ap- proach also provides streaming algorithm for graph sparsification that achieves (1 + appprooxxitti,,, using - logn) poly(log log bits of space, im- proving the current bound by log factors. Furthermore, we give streaming algorithm for min-cut approximation. Along the way, we present an on- line algorithm for (1 + ehhyperggapp sparsification, which is optimal up to poly- logarithmic factors. Hence, we achieve (1 + =) -hhyeerggpph sparsification in the sliding window model, with space optimal up to poly-logarithmic factors. Lastly, " we give an adversarially robust algorithm for hypergraph sparsification using ş² poly (r, log n, log log log m) bits of space.
INTRODUCTION
Graphs are fundamental structures that naturally model complex relationships in real-world data, from social networks and transportation systems knowledge graphs and human brains. Because of their great expressive power, these relational models are fundamental to research in computer science, data science, and machine learning, in addition to many other fields. Graph cuts are used to partition graphs into distinct regions by minimizing cost function, thereby providing insight- ful information. For example, in image segmentation, graph cuts help separate objects from the background by modeling pixels nodes in a graph and optimizing the partitioning based on in- tensity or color differences (Boykov & Kolmogorov, 2004). In network clustering, graph cuts are used to detect communities within social networks by partitioning nodes into groups with strong internal connections while minimizing connections between different groups (Newman, 2006). In hierarchical clustering, sparse graph cuts used increasingly refine subgraphs achieve better performance for Dasgupta's objective (Dasgupta, 2016; Braverman et al., 2025; Deng et al., 2025). More generally, spectral methods not only preserve key quantities such sizes, but also accom- modate more complex partitioning, e.g., multi-way cuts, and consider other concepts such as the graph Laplacian and its eigenvalues.
With the explosive growth of large-scale databases and the increasing demand for scalable machine learning and AI systems, graphs have become more complex and massive than ever before. In many modern applications, the sheer volume of graphs create significant computational bottlenecks, mak- ing crucial obtain smaller approximate graphs while preserving key features. Cut sparsifiers and spectral sparsifiers are smaller, efficient representations of large-scale graphs that approximately preserve cut sizes and spectral properties, respectively. These techniques are therefore often used to accelerate graph-related algorithms and reduce computation overhead. For instance, graph spar-
Google Research. E-mail: cohenaddad@@ooglle com.
Carnegie Mellon University and Google Research. E-mail: dwoodrufães emu.edu.
Texas A&M University. E-mail: xsh13026 gmail. com.
6 Texas A&M University. E-mail: samsonzhoul con.

---

Published as a conference paper at ICLR 2026
sifiers have been used to enhance the performance of graph representation learning methods by ducing irrelevant information and preserving important structural features in the graph (Calandriello et al., 2018; Zhu et al., 2019; Zeng et al., 2020; Zheng et al., 2020; Braverman et al., 2021a; Chun- duru et al., 2022; Zhang et al., 2024), spectral sparsifiers have been used to construct lightweight graph neural networks while maintaining their overall effectiveness (Li et al., 2023; Xie al., 2024), and hypergraph sparsifiers have been used to produce efficient algorithms related to cuts and flows (Chekuri & Xu, 2017; Chandrasekaran al., 2018; Chekuri & Xu, 2018; Veldt al., 2023), which have been applied to hypergraph partitioning and clustering (Akbudak et al., 2013; Deveci et al., 2013: Ballard et al., 2016) and machine learning tasks (Li & Milenkovic, 2017; 2018; Veldt al., 2020). In addition, graph sparsification is key algorithmic component in theoretical computer sci- ence, e.g., computing the eigenvalues of the Laplacian matrix (Soma & Yoshida, 2019) and solving the Laplacian system, which produces fast symmetric diagonally dominant (SDD) system solvers (Koutis et al., 2014; Spielman & Teng, 2014; Soma & Yoshida, 2019).
Data streams. As datasets have grown dramatically in size in recent years, there is increasing interest in large-scale computational models that avoid storing the entire dataset or making multi- ple passes over it. This has led to the development of the streaming model, which processes data sequentially under strict memory constraints, making it well-suited for handling massive datasets efficiently, e.g., network activity logs, loT device streams, financial transactions, database event records, and real-time scientific observations. In this paper, we ask: Do graph sparsification prob- lems require additional space complexity in the streaming model, compared to the offline setting?
1.1 OUR CONTRIBUTIONS
In this paper, we resolve the above question, providing algorithms for eut and spectral sparsification problems, losing only poly-iterated logarithmic factors in space, i.e., polylog(log n.) factors for graph with n vertices.
Graph sparsification. The graph sparsification problem has been extensively studied (Spielman & Srivastava, 2008; Batson et al., 2014; Lee & Sun, 2017; Jambulapati & Sidford, 2018), and there are well-known constructions for spectral sparsifiers with O ( (() edges (Batson et al., 2014). We pro- vide efficient algorithms for graph spectral sparsification in insertion-only streams that have optimal space complexity compared to the best sample complexity of an offline algorithm, up to poly-iterated logarithmic factors in n. Here, we represent graph as a three-tuple G = (V, E, w), where V is the set of vertices with size n, E is the set of edges with size m = poly(n), and E - z+ is the weight assignment function, where the weights are positive integers upper bounded by poly(m), i.e., a fixed polynomial n. We give our formal statement as follows.
Theorem 1.1 (Streaming graph sparsification, informal version of Theorem E.3), Given a graph G = (V, F,, w) with n vertices defined by an insertion-only stream, there an algorithm that gives (1 + e)-spectral sparsifier with probability 1 poly(nj' storing ž poly(log logn) edges, i.e. n gz log n poly(log log n) bits, and using poly(n) update time.
By comparison, offline constructions for graph spectral sparsifiers can be combined with the merge-and-reduce framework (see Section 3) for coreset constructions to achieve algorithms with O ( log" n) edges in the insertion-only setting. Additionally, Cohen et al. (2020) produced a spec- tral sparsifier with O ( log" n) edges in the online model, and similarly, Kapralov et al. (2020) achieved spectral sparsifier with O (5 log n.) edges in the dynamic streaming model, where both insertions and deletions of edges are permitted; both of these results can also be applied to the insertion-only setting. Here, we note that storing each edge in the sparsifier uses O (log n) bits of space. Our result avoids the additional multiplicative log n factors in previous results, achieving a nearly-optimal space. We visualize the above comparison in Figure 1. Graph min-cut approximation. In addition, we construct space-efficient streaming algorithm that approximates the graph min-cut in insertion-only data streams.
Theorem 1.2 (Streaming min-cut approximation, informal version of Theorem E.18). Given graph G (V, F, wi) with vertices defined by an insertion-only stream, there is an algorithm which outputs a (1 + epppprroximation to the size of the min-cut of G with probability poly(ny
storing polylog(n, })) edges, ie, z. polylog(n, 2) bits, and using poly (T)) update time.
2

---

Published as a conference paper at ICLR 2026
Setting
Reference
Space (number of bits)
Offline
Batson et al. (2014)
log n)
Streaming
Kapralov et al. (2020)
O
( log" n)
Streaming
Theorem 1.1
(22 log poly log log
Comparison of our graph spectral sparsifier and the previous optimal results in different settings. Our sparsifier tight up poly log n) factors.
Fig. 1:
We remark that our result improves on the logarithmic dependence in n compared to the previous work (Ding al., 2024).The That is, our algorithm uses O (= llog log 2) bits of space, while the algorithm of Ding et al. (2024) uses O [ log (=)) bits of space. We illustrate this comparison in Figure 2.
Setting
Reference
Space (number of bits)
Offline
Ding et al. (2024)
O ( log" n))
Streaming
Ding et al. (2024)
O log*+1
++1+ nt)
Streaming
Theorem 1.2
O (a log log _)
Fig. 2: Comparison of our graph min-cut approximation algorithm and the previous optimal results in different settings.
Hypergraph sparsification. Hypergraphs are a generalization of graphs where each hyperedge can connect more than 2 nodes, enabling the representation of multi-way way relationships beyond pairwise connections. This ability to capture higher-order correlations makes hypergraphs particularly valu- able in various applications, such hypergraph neural networks (Feng et al., 2019; Gao al., 2023; Feng et al., 2024) and hypergraph clustering (Takai et al., 2020). Soma & Yoshida (2019) formalized the definition of (1 + () >hyperggapph spectral sparsifier and gave a construction with O log
hyperedges. Bansal et al. (2019) achieved an upper bound O m log where r max.5E
is the rank of the hypergraph. Kapralov et al. (2021) gave upper bound of O (nh log" n). Jambu- lapati al. (2023) and Lee (2023) simultancously improved the upper bound to O (#+ log log
Note that the above results are in the offline setting and it uncertain whether they can be adapted to our streaming setting. contrast, existing algorithms use O mr log² ri logr) hyperedges (Soma al., 2024) or 3/2 polylog(m)) hyperedges (Khanna al., 2025a). However, they are not tight in and log m factors, which is prohibitively large for streaming large-scale hypergraphs, since could be (2(n) and could be 22(2)) the worst case. Therefore, the goal of our work is to improve both the and log factors in the streaming setting. We give the first streaming algorithm that is optimal up to poly-iterated logarithmic factors in m, compared to the current best offline sample complexity.
Theorem 1.3 (Streaming hypergraph sparsification, informal version of Theorem E.11). Given hypergraph (V, E, w) with n vertices, m hyperedges, and rank defined by an insertion-only stream, there is an algorithm that gives a (1 + e)-spectral sparsifier with probubility poly(m) storing toe logn- poly r, log log m) hyperedges, i.e., m log" n -olyy r, log log m) bits, and using poly(n) (n. update time.
Here, we note that storing each hyperedge requires O (r log n) bits of space (see Remark D.7). Our algorithm only loses polylog and poly (log log m.) factors, which are most polylog in the worst case, removing off the undesirable poly (n) factors when m = (2(2)).
We note that the update times of streaming algorithms are poly(n). which could be potentially improved we relax the space constraint. The main bottleneck the calculation the online sam- pling probability, which requires matrix-multiplication time Ô (n²) (omitting E and polylogarithmic factors), where w 2.37 is the exponent for matrix multiplication runtime (Alman et al., 2025). While applying the standard merge-and-reduce directly offers faster Ô (r) update time (where
3

---

Published as a conference paper at ICLR 2026
is the rank), it incurs prohibitive polylog(m) space dependency. Our focus is optimizing space, which is often the primary bottleneck for processing massive datasets in streaming.
In addition, we give online sampling scheme for hypergraph spectral sparsification with efficient space. The online setting is a more restrictive setting that must immediately and irrevocably decide whether each arriving edge should be sampled or discarded, i.e., online algorithms cannot retract decisions. Online algorithms are particularly useful in settings where intermediate results must be reported as the stream continues and thus are beneficial in practice because downstream computation can begin immediately when an item is sampled, as the item will not be removed at a later time.
Theorem 1.4 (Online hypergraph sparsification, informal version of Theorem E.8). Given a hyper- graph H- = (V, E, w) with n vertices, m hyperedgee, and rank defined by an insertion-only stream, there is an online algorithm that uses n log n poly (log log m) bits of working memory and gives a (1 + e)- -pseccraall sparsifier with probability 1
with O ( log n log m lo hyperedges.
poly(m)
For comparison, Soma al. (2024) provided an online algorithm that outputs (1 + -hhyprggaa sparsifier using O (Tr (
log" n logr) hyperedges. However, they require O (n²) working mem- ory to store the sketch that defines their sampling probability. Our algorithm improves this bound to n log n pooy(log log m) bits, significantly reducing memory consumption. This result resolves Question 6.2 of Soma et al. (2024), which asks for improvements in space complexity. We summa- rize our results in Figure 3.
Setting
Reference
Space (number of bits)
Offline
Jambulapati et al. (2023); Lee (2023)
d² "log n log
Online
Khanna et al. (2025a)
polylog(m)
Online
Theorem 1.4
" log"
2 n log m logr
Streaming
Theorem 1.3
poly(log n, log log m)
Fig. 3: Comparison of our hypergraph sparsifiers and the optimal results in different settings. Our streaming algorithm is tight in both and polylog(m) factors.
Adversarial robustness. We also obtain hypergraph sparsifiers in the adversarially robust streaming model. This model is framed as a two-player game between an adaptive adversary, who generates the input stream, and a randomized algorithm, which processes the inputs and outputs an estimate. Unlike the standard streaming setting, future inputs may depend on previous interactions between the adversary and the algorithm. Specifically, the game proceeds in m rounds: in each round the adversary selects input based on past inputs and outputs and sends to the algorithm, then the algorithm responds with a new estimate. This formulation captures the adaptive nature of real-world data streams and parallels adversarial robustness research in machine learning, where inputs strategically chosen to exploit vulnerabilities in learning systems, such as adversarial examples in neural networks (Goodfellow et al., 2015), optimization-basee evasion attacks (Carlini & Wagner, 2017: Athalye et al., 2018), adversarial training (Madry et al., 2018), and trade-off's between accu- racy and robustness (Tsipras et al., 2019; Chen al., 2022). Importantly, adaptivity need not arise from malicious attacks: it can also result from interactive queries to large database or from iterative queries designed to optimize an underlying objective (Hassidim et al., 2020), settings where stan- dard streaming algorithms fail. Given these perspectives, the adversarially robust streaming model has attracted significant attention (Ben-Eliezer et al., 2020; Ben-Eliezer & Yogev, 2020; Hassidim et al., 2020; Alon et al., 2021; Braverman et al., 202 Kaplan et al., 2021: Woodruff & Zhou, 2021; Beimel et al., 2022; -en-Eliezer et al., 2022a;b; Chakrabarti et al., 2022; Avdiukhin et al., 2019; As- sadi et al., 2023; Attias et al., 2023; Cherapanamjeri et al., 2023; Dinur al., 2023; Woodruff et al., 2023a; Gribelyuk et al., 2024; Woodruff & Zhou, 2024; Gribelyuk et al., 2025; Lin et al., 2026).
We first extend streaming algorithm results to bighh-brbbbbiitty regime, obtaining success prob- ability 1 - ō with a space overhead of at most O (log log 1). and then use this result to achieve an adversarially robust algorithm for robust hypergraph sparsification.
Theorem 1.5 (Robust hypergraph sparsification, informal version of Theorem E.15). Given graph H = (V, E, w) with n vertices, m edges, and rank r defined by an insertion-one onlly stream, there exists an adversarially robust algorithm that constructs (1 + +e)-spectrall sparsifier with probability
4

---

Published as a conference paper at ICLR 2026
1 poly(m) storing 2/ poly(log n, n, log log log ")) hyperedges and 2 poly(r, log n, log log " edges in the associated graph, ie., _ poly(r, , log n, log r. log log +)) bits in total.
5
The sliding window model. An additional application of online algorithms is to the sliding window model. Since the streaming model remains oblivious to the times at which specific data points arrive, it is unable prioritize recent data over older data. By comparison, the more general sliding window model considers the most recent W updates {Tn-W*+ F5n-W11.... [nn to be the active data, which is crucial in situations where newer information more relevant or accurate, such as tracking trends in financial markets or analyzing recent Census data. Indeed, the sliding window model outperforms the streaming model in various applications (Babcock et al., 2002; Datar al., 2002; Papapetrou et al., 2015; Wei et al., 6), especially for time-sensitive settings such as data summarization (Chen et al., 2016; Epasto al., 2017), social media data (Osborne et al., 2),4), and network monitoring (Cormode & Muthukrishnan, 2005; Cormode & Garofalakis, 2008; Cormode, 2013). The sliding window model is particularly useful when computations must focus only on the most recent data. This is important in cases where data retention is limited by regulations. For example, Facebook stores user search histories for up to six months (Facebook, 2021). Google stores browser data for up to nine months (Google, 2021), and OpenAl retains API inputs and outputs for up to 30 days (OpenAl). The sliding window model captures the ability to expire data, in alignment with these time-hased retention policies, and consequently has received significant attention in various problems (Lee & Ting, 2006; Braverman & Ostrovsky, 2007; Braverman et al., 2012: 2018; 2021b; Woodruff & Zhou, 2021; Ajtai et al., 2022; Jayaram et al., 2022: Blocki al., 2023; Cohen-Addat et al., 2025). Applying our online algorithm, we utilize a framework for the sliding window model to achieve an algorithm for hypergraph sparsification:
Theorem 1.6 (Streaming hypergraph sparsification in the sliding window model, informal version of Theorem F.2). Given a hypergraph H = (V, E, w) with n vertices, m hyperedges, and rank r defined by the sliding window model, there is an algorithm that gives (1 + e)-spectral sparsifier with probability 1- poly(nj. storing şेt polylog log(m, r) hyperedges, i.e., e log n polylog(m, r) bits.
rm
We remark that the above space upper bound is worse than that of our streaming algorithm. This is because the sliding window model is more general than the standard streaming model, as the al- gorithm needs to maintain an accurate approximation of the most recent W items. In the standard streaming model, a newly-arrived edge with low overall contribution can be discarded. By compar- ison, in the sliding window model, the same edge may be critical to the most recent W items and must therefore be retained, which leads to a higher space complexity. Moreover, one can set the window size W as the stream length, in which case the entire stream is in the active window. Thus, the sliding window model can be parameterized to subsume the streaming model.
Concurrent and independent work. We remark that Goranci & Momeni (2025); Khanna et al. (2025a) recently also achieved online and dynamic algorithms for hypergraph sparsification that samples 2 polylog(m) hyperedges. Our algorithm has suboptimal update time, but we achieve better space complexity, which is prioritized in the streaming setting. In addition, Khanna et al. (2025b) recently showed that in an insertion-only stream, a hypergraph cut sparsifier can be com- puted using of polylog(n) bits of space, avoiding the additional multiplicative log factors. By comparison, our streaming algorithm for spectral sparsification, which generalizes a cut sparsifier, also avoids the log m dependency. We refer the reader to Appendix A for more detailed discussion.
1.2 PRELIMINARIES
In this section, we introduce several important definitions and techniques related to graphs and hypergraphs. We refer the reader to Appendix B for a comprehensive discussion. For an integer n > 0, we use the notation [n] = {l....,,) n2. We use poly(n) to denote a fixed polynomial of n, whose degree is determined by setting parameters in the algorithm accordingly. We use polylog(n) to denote poly(logn), n). We use Ô (F) = F polylog F to hide the polylogarithmic factors.
Hypergraphs. For hypergraph H = (V, E, w). its energy function QH IR + IR is (z) EeSr (z) E.E ((e). max (x,, - ), where (x) is the energy of a hyperedge A weighted hypergraph H is (1 + muuliipiccate spectral sparsifier for H if it preserves the energy of all vectors x up to an E-multiplicative error: [Q (x) - 1n(z)] < E Qn()), Vr e R". The definition of the associated graph relates a hypergraph to a graph with the same set of
5

---

Published as a conference paper at ICLR 2026
vertices. Given hypergraph H. its associated graph G = EV. is by replacing each hyperedge (WI,..., W,) E H with the (2) edges (u,, where S < j S r, each with weight w(e)).
Graph Laplacian. We review the graph Laplacian that encodes the structure of graph into a matrix. The graph Laplacian is an n X n matrix where its diagonal stores the weighted degree for each node, and the other entries store the weight of each edge (i,j) in G. The graph Laplacian provides way to view the graph spectral sparsifier problem as a matrix spectral approximation problem so that one can implement numerical linear algebra methods. The graph Laplacian LG can be written as the Gram matrix A A, where the incidence matrix A consists of binary row vectors representing each weighted row we in graph G. That is, a, == auv / /w(e)- - (Xa Xv), where Xi denotes the elementary row vector with a single nonzero entry in the i-th coordinate. In the graph spectral sparsification problem, the energy is defined be x LGx, which is x A Ar. This relates the graph sparsification problem to the matrix spectral approximation problem as follows.
Spielman & Srivastava (2008) introduced the notion of the effective resistance re w<(e) (Xu X=) (Xu Xx) of an edge in the graph, encoding the importance of e. They construct spar- sifier with O (++ edges by sampling each edge with probability proportional to r.- The effective resistance re turns out to be the leverage score of the row a; in the incidence matrix A, defined by 7i (A A)- where a, is the row representing e. Thus, sampling edges in the graph is equivalent to sampling rows from the incidence matrix A.
Online leverage score. Another core technical tool is online row sampling (Cohen al., 2020). In the online setting, we only have access to the prefix matrix A; that arrives before the current row a, Therefore, we consider the online variation of leverage scores: T. (A) == a, (A, (A,A,,) A.)_ Then, sampling with probability proportional (A) gives us an online spectral approximation.
2 ONLINE HYPERGRAPH SPECTRAL SPARSIFIER
We start with our online hypergraph sparsifier, which is a fundamental subroutine in our streaming hypergraph sparsifier. We first give a brief overview of previous methods in the offline setting in Section 2.1, where the entire hypergraph is given in advance. Then in Section 2.2, we explain the main technical challenges in extending them to the online setting and how we solve them. Our approach involves using novel local weight assignment subroutine, whose discussion is deferred to Section 2.3. Next, we briefly summarize our technical novelties.
Technical overview. Let A be the incidence matrix of the hypergraph's 's associated graph. For each hyperedge e, prior offline algorithms assigned a weight zuv to each edge (u, v) in the clique defined by e. Let Z denote the diagonal weight matrix, where its (i. iitt) entry the weight 2, of the edge represented by the i-th row in matrix A. The previous works then defined the sampling probability of e based on the leverage scores of 1/2 and chose Z wisely to reduce the sample complexity. However, this approach cannot be immediately applied since we do not have the entire hypergraph in the online setting. We introduce novel local weight assignment scheme to decide the weights Z, at each time t (see Section 2.3) and combine it with online row sampling to maintain a sketch matrix for Z /2 A,, to define a valid set of sampling probabilities with efficient memory (see Section 2.2). In particular, when the local weights Z, are defined, we fix these weights in the following updates. When the next hyperedge e arrives, we use / A, to compute the weights for each (u, v) E et+1, and then pass the re- s--eeggttdd edges an online row sampling subroutine and add the sampled edges to Z A, to define Z42AA Importantly, we decouple the randomness of these procedures ensure that the algorithm outputs valid sparsifier.
2.1 OFFLINE ALGORITHMS
In this section, we summarize the previous techniques in the offline setting. We begin with the method in (Kapralov et al., 2021) which achieves small sample complexity via the weight assign- ment scheme. For a hyperedge with weight w(e) in the hypergraph, we assign a weight zee to each edge (u,,) u) E e in the associated graph so that the weights satisfy E(u.ree Zue = w(e), that is, the edges in the clique defined by e sum up to w(e). Here, we abuse the notation (u, v) E e to denote that (u, v) is in the clique defined by e. We define the effective resistance of an edge in

---

Published as a conference paper at ICLR 2026
the re-weighted associated graph to be a=(2 where Ti (Z) is the leverage score of the i-th 2t
row in the weighted incidence matrix Z1/2A. Now, the weight matrix Z is chosen to satisfy that for all hyperedges e and edges in the clique defined by the ratios (z) are within a constant fraction of each other. The intuition is to "balance" the effective resistance of each edge in the clique to reduce the sample complexity (see the discussion in Appendix C.2). Let Pr be proportional the
balanced effective resistance of hyperedge then sampling each e with probability Pe and rescaling the sampled hyperedges by I gives a valid sparsifier.
p.
Sufficient conditions for sampling hyperedges. Jambulapati et al. (2023) stated more general definition of sampling probability called the "group leverage score overestimate", which still gives valid spectral sparsifier. Indeed, for any weight assignment with L(,,))e Zue = w(e), it suffices to
=((2/²A) of edges sample each hyperedge e with probability higher than the maximum of all ratios 21 i in the clique of e, as stated in the following definition. Then, we are left to choose proper Z that gives the desired sample complexity.
Definition 2.1 (Sampling probability for each hyperedge). Given a hypergraph H = (V, W)) and its associated graph G (V, where the weight assignment satisfies Elu,te Zwo w(e) for all E E. let A be the incidence matrix for G, and let Z be the weight matrix. Let P O (7z log m mmggr) be the amplification factor. We set the sampling probability of e to satisfy
Pe 2 p w(e) max(u, auv (A ZZA -'aT Here, ano (A T ZA) -aa a
Tue (2))
Jambulapati et al. (2023) applied refined chaining argument by leveraging Talagrand's 's growth function framework to achieve a tighter bound. Their analysis can be applied as a black-box the sampling probabilities satisfy the sufficient conditions stated in Definition 2.1: (1) They are an overestimate; (2) Their values are defined independently of whether other hyperedges are sampled.
2.2 OUR ONLINE ALGORITHMS
The above methods do not generalize to the online setting because at time 4, we can only define the weights Z, based on the sub-hypergraph that arrived before and its corresponding incidence matrix A,, as the entire hypergraph is not given. However, the sampling probabilities must satisfy Definition 2.1 for the entire hypergraph and its corresponding incidence matrix A. Thus, the chal- lenge here is to compute the correct weights under restricted information. We summarize our novel techniques that solve this problem as follows and defer the full analysis to Appendix C.I.
Online sampling probabilities. Notice that the re-weighted matrix Z ", is consistent along the way, and hence 1. A.)
is an overestimate of T,(2//2A) where / A is the re-weighted matrix of the entire hypergraph, due to the monotonicity of online leverage scores. Thus, it suffices to define the sampling probability Pe, as p w(ex) max ane A A, - which gives an overestimate of the offline sampling probability. Next, we state the guaranties of our local weight assignment scheme, which assigns the weights to a newly-arrived hyperedge Et+1 based on the prefix matrix /
2,
2 Ar, and we defer its discussion to Section 2.3. The first point shows that the weights of ex+1 sum up to w((++1), ensuring that Definition 2.1 is satisfied. The second point upper bounds the sampling probabilities, which is used to bound the number of sampled hyperedges.
Theorem 2.2 (Local weight assignment). Given graph G = (V, F) with weight Ze and incidence matrix A, and a newly-arrived, hyperedge et+1 C. V with weight w(er+1), ) then there is a procedure GET WEGHTASSIGNMEENT /22 "A,, e1+1) that assigns a weight zuv each edge (u, E elt1 such that it satisfies (I) E(u.)) Zuv = w(e), and (2) (a ano (A, Z,A a =
O Eiu.ejee (Z. AA))......))). where is the leverage score function.
Optimizing the working memory. If we sample each hyperedge based the sampling proba- bilities defined by the weight assignments in Theorem 2.2, we would get a valid sparsifier with a desirable sample complexity. However, cannot store the entire matrix each f, which uses prohibitively large working memory and exceeds the sample complexity. To solve this problem, we combine the local weight-assinnment subroutine with an online row sampling
i.e., / A, at
7

---

Published as a conference paper at ICLR 2026
subroutine (Cohen et al., 2020) to reduce working memory. Let B be matrix, and let B, denote the matrix formed by the first rows of B. In online row sampling, we sample the newly arrived row
by with probability P: x b, B,-1)-'b, where the prefix matrix B; consists of the rows sampled from previous steps, and we add b,/P; B if is sampled. We adapt this idea to our online sampling procedure in an iterative way. When a new hyperedge et+1 arrives: (1) We com- pute its weights 2t+1,uu using our local weight-assignment subroutine implementing on the current
sketch M, which is a 2-approximate spectral approximation of the prefix weighted matrix Z 2!/2 A (2) For each (u, v) E Et+-1, we feed the weighted row / auc into the online row-sampling procedure update M. Thus, the resulting matrix is still 2-approximate spectral approximation the matrix 21/2 A,11 which suffices for our purpose. Our algorithm is given in Algorithm 1.
Algorithm Online hyperedge spectral sparsifier
1: Require: Stream of m hyperedges for hypergraph H with rank r
2: Ensure: Spectral sparsifier H for H
3: H 0. e < O ( log mog r), M
4: for hyperedge éx do
5: 2t 2t-1 GETWEIGHTASSIGNNENT..M ex)
6: for (u,v) E do
7: Sample weighted row auv V M by online row sampling (Cohen al., 2020)
(M is a 2-spectral approximation to Z//² A, all times f, ie., M M A, Z,A, <
8:
2 M M)
9:
end for
for (u,v) e,
11: Que + auv w(es) (M M)-1 T
12: end for
13: Pe. min 11, 2p max(u,))E Pur}
14: With probability Pe., A + H Pei
15:
Return H
16:
end for
Decoupling technique. The second sufficient condition stated below Definition 2.1 requires the sampling probabilities to not depend on which hyperedges are sampled before. We show that the online sampling subroutine does not violate this requirement because the sketch M (built by online row sampling) and the sampling of hyperedges use independent randomness.
Lemma 2.3 (Decoupling). For each time t, the sampling probability Pe, defined by Algorithm is independent of the hyperedges that have been sampled previously
Specifically, consider a fixed stream G1, C.. and let M, denote the matrix M at time t. When the inner randomness of online row sampling fixed, the sequence of matrices M,,... M,, is also fixed. Then, the sampling probabilities pe, are defined independently, each based on the value of max a.. ((e)) (M') M Thus, the sampling of each e; independent of whether the previous hyperdges are sampled. Applying the chaining argument in (Jambulapati et al., 2023) and careful analysis on the sample complexity, we show Theorem 1.4.
2.3 OUR LOCAL WEIGHT ASSIGNMENT SCHEME
In this section, we show how to construct the local weight assignment in Theorem 2.2. The full analysis deferred to Appendix C.2. Given graph G (V, F) with weight Z and incidence matrix A and newiy-arrived hyperedge C V with weight wre), our goal is to assign weight an to each (u,w) E such that y defined as the ratio TZ=12 A) That is, the ratios of the clique defined by are within a y-fraction of each other. We remark that this property gives the upper bound on the sampling probability stated in the second point of Theorem 2.2 (see the discussion the beginning of Appendix C.2).
>0 Quv 2 max ee Tu'v' for some constant 7, where fuo
Kapralov et al. (2021) provided a greedy algorithm that shifts the weights from the edges with a higher ratio to the edges with lower ratio, as long they are not y-balanced. We propose
8

---

Published as a conference paper at ICLR 2026
localized version of their algorithm, i.e., only conduct the weight shift operation on the newly- arrived edge e without changing the previous assigned weights in G, to ensure the consistency of weight matrix. We show that local weight shift operations always increase the spanning tree potential of G by a certain amount, and since the potential is upper bounded, this process terminates in finite steps and results in 7-balanced weight assignment. The algorithm is given in Algorithm 2.
Algorithm 2 Online (y.e) e-bbaaaned weight assignment
1: Require: Given weighted graph G = (V, F, w), hyperedge C V with weight w(e)
2: Ensure: Online (7, e---baaanced weight assignment
3: Initialize: for all (u, v) E e, set Zuv w(e)//e)
4: G < (V, U U ((uw)eee (u, (u, 2)
5: While Gs is not online (7, e)-balanccdd weight assignment do
6: Select (u. v) * u', v E such that quv > Y qu'v' and uu'ed > {auo is the ratio in Definition 2.13
7-1 7: A f min min(Zuur 20.
8: Juan Tunn + X
9:
Zu''o to Zrelvl A
10:
Return G
STREAMING MODEL
In this section, present space-optimal streaming algorithms for both graph and hypergraph. We first introduce the classic merge-and-reduce method. Then we explain how we achieve space- optimal algorithms in Section 3.1. Next, we briefly summarize our technical novelties.
Technical overview. Coden-Addad et al. (2023) gave a streaming framework that achieved efficient space by filtering the stream using online sampling subroutine and then passing the sampled edges to the merge-and-reduce method. The main challenge of applying this framework is that we cannot afford to store the edges sampled by the online subroutine, which used to define the next online sampling probability in online row sampling (Cohen et al., 2020). We revisit the analysis of Cohen et al. (2020) and show that the output of the merge-and-reduce method suffices to accurately estimate the online sampling probabilities, ensuring the validity of the framework. In addition, we show that by carefully controlling the number of times we change the output of our algorithm, we achieve an ad adversarially robust algorithm.
gerge-and-reduce framework. Let S(-) + R=o denote mapping from input parameters the sample complexity of an online algorithm. The online graph sparisifier samples S'n,, log m, e, 6) edges for an input stream of length m on a graph with n nodes, accuracy E (0, 1), and failure probability 6, with high probability. We call a re- reightthted subgraph & C G an (1 + eocoreet it is a (1 e)-sparsifier of G. The merge-and-ree merge-and-rrduue approach partitions the stream into blocks of 5
size S (2, log m, Zlogima] poly(mm)) and builds [1
2 Zlog(ma] -coreset for each block, so that each coreset can be interpreted as the leaves of a binary tree with height at most log(mn), For each
node in the binary tree, a coreset of size (n., log m, Zlog(mm)) [mly( is built from the coresets representing the two children of the node. Assuming that the coreset construction admits merging procedure, i.e., by taking the graph consisting of the union of the weighted edges in each of the coresets, then the root of the tree represents coreset for the entire stream with distortion at most (mg(
(1 + E) and failure probability 5. A figure illustrating the merge-and- reduce approach is shown in Figure 4. Due to our choice of accuracy E' [log(mm] in each node, directly applying the merge-and-reduce approach to the input stream loses log m factors. Cohen- Addad et al. (2023) improved on these factors by adding an online sampling procedure ahead of the merge-and-ae and-ruuce approach. Suppose that the online sampling procedure is nearly optimal, then the input stream of the merge-and-reduce approach is significantly shorter. For instance, in the graph sparsification problem, there is online algorithm that samples O ( log n)) edges, so the coresets only have size S nn, log log n, 2log (og(n)' polylog(n) This turns polylog(n) factors into polylog log(n) factors, which is more space-efficient for huge graphs. Since we directly pass
(1 Flog(mn))

---

Published as a conference paper at ICLR 2026
the online coreset of O log n.) edges to the merge-ande -ngee-u framework and never store them entirely, we do not lose the log n from online sampling and achieve efficient space.
3.1 OUR STREAMING ALGORIHHMM
Unfortunately, the above streaming framework does not apply immediately, since in online row sampling (Cohen et al., 2020), we use the online coreset from the previous step to compute the sampling probability of the next edge. However, we cannot afford to store the online coreset in our streaming algorithms, and it remains to obtain an efficient sketch matrix to define those probabilities. Instead, use the coreset obtained in the last step of our streaming algorithm to compute the next online sampling probability. The algorithm is given in Algorithm 3.
Algorithm 3 Streaming framework inspired by (Cohen-Addad et al., 2023)
1: Require: Stream S, online sampling procedure for S, merge-and-reduue procedure
2: Ensure: Coreset on S
3: for each edge arrived in the stream S do
4: Sample e, based on the online sampling probability defined by $ (S is the output sparsifier)
5: If st is sampled by online sampling, add the corresponding update to S"
6: Run merge-and-redie reduce on S' and return S on the root node
7: end for
We apply a refined analysis based on Cohen et al. (2020) to show that our approach to define the online sampling probability still gives valid online coreset, stated follows. Using this result, we obtain the streaming algorithm in Theorem 1.1. The full analysis is deferred to Appendix E.I.
Theorem 3.1 (Online Coreset). Let graph G (V, F,, w) with vertices and m edges be defined by an insertion-only stream, let A be the incidence matrix of G, and let a, be the i-th row A. We define an online sampling scheme as follows. Let &g be the ridge-leverage score for online row sampling: i,- = (1) af (Af_,A--1+ AI) a, where X poly(n) S - and Ai- is the output of our streaming algorithm the last round (see Algorithm 3). We set the sampling probability of row a, as P. min(cl., 1}, where c =0 log 6²
and if a; is sampled, we store the re-weighted row Vo: Then, let A, be the matrix outputted by our sampling scheme for each E [m]] with probability at least poly(m) we have (1 e)AJA; < AÇ', (1+e)ATA The algorithm samples O (3' log m logn) edges and uses poly(n) update time.
For our hypergraph sparsifier, recall that our online algorithm keeps sketch M of the weighted matrix / A,, which is obtained by online row sampling. To optimize the working memory of this procedure such that it satisfies the streaming memory constraint, we further pass M to the merge- and-reduce method as in Algorithm 3 and use the resulted sketch matrix in the following subroutines. We show that this modification does not violate the decoupling argument in Section 2.2. The full analysis is deferred to Appendix E.2 and Appendix E.3.
Adversarial robustness. We observe that the streaming framework provides a hypergraph sparsifi- cation algorithm with probability
poly(m) with only an additional log log m factor in space (see Appendix E.4), which further gives a space-efficient adversarially robust algorithm. We generalize the computational path framework in Ben-Eliezer et al. (2020) that transforms high-probability streaming algorithm into an adversarially robust algorithm as long as it has small e-flip number. Suppose that an algorithm estimates a target function on input stream {2+)== the e-fipp number is defined as the number of times f [#11--- .2. increases by an g-fraction. In the stream, the algorithm fixes its output when f is within an e-fraction, and so we can union bound across all possible inputs given by the adversary if the failure probability d is sufficiently small. In our hypergraph sparsifi- cation algorithm, we use the Laplacian matrix of the input hypergraph's 's associated graph to control when we switch the output, i.c., we switch only if its eigenvalues increase by an e-fraction. Since its eigenvalues increase by an f-arction at most log times, the e-fiip number is n alog Then our high-proba gigghprbbbbility result gives an adversarially robust algorithm with efficient space complexity; defer the complete discussion to Appendix E.5.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
David P. Woodruff is supported in part by Office of Naval Research award number N0001421 12644 and Simons Investigator Award. Shenghao Xie is supported in part by NSF CCF-2335411. Samson Zhou is supported in part by NSF CCF-2335411. Samson Zhou gratefully acknowledges funding provided by the Oak Ridge Associated Universities (ORAU) Ralph Powe Junior Faculty Enhance- ment Award.
REFERENCES
Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun. David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS '22: International Conference on Management of Data, 2022, pp. 15-27, 2022. 5
Kadir Akbudak, Enver Kayaaslan, and Cevdet Aykanat. Hypergraph partitioning based models and methods for exploiting cache locality in sparse matrix-vector multiplication. SIAM Sci. Comput., 35(3), 2013." 2
Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. More asymmetry yields faster matrix multiplication. In Proceedings of the 2025 Annual ACM- SIAM Symposium on Discrete Algorithms, SODA, pp. 2005-2039, 2025.
Noga Alon, Omri Bln-eeiezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In STOC: 53rd Annual ACM
SIGACT Symposium on Theory of Computing, pp. 447-455, 2021. 4
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Coloring in graph streams via deterministic and adversarially robust algorithms. In Proceedings of the 42nd ACM SIGMOD- SIGACT-SIGAL Symposium on Principles of Database Systems, PODS, pp. 141-153, 2023.
Anish Athalye, Logan Engstrom, Andrew Ilyas, and Kevin Kwok. Synthesizing robust adversarial examples. In Proceedings of the 35th International Conference on Machine Learning, ICML, volume 80 of Proceedings of Machine Learning Research, pp. 284-293. PMLR, 2018. 4
Idan Attias, Edith Cohen, Moshe Shechner, and Uri Stemmer. A framework for adversarial stream- ing via differential privacy and difference estimators. In 14th Innovations in Theoretical Computer Science Conference, ITCS, pp. 8:1-8:19, 2023. 4
Dmitrii Avdiukhin, Slobodan Mitrovic, Grigory Yaroslavtsev, and Samson Zhou. Adversarially robust submodular maximization under knapsack constraints. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pp. 148-156.
ACM, 2019.
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, and Jennifer Widom. Models and issues in data stream systems. In Proceedings of the Twenty-frrs ACM SIGACT-SIGMOD-SIGARR Symposium on Principles of Database Systems, pp. 1-16, 2002.
Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. Hypergraph partitioning for sparse matrix-matrix multiplication. ACM Trans. Parallel Comput., 3(3):18:1118:33 2016. 2
Nikhil Bansal, Ola Svensson, and Luca Trevisan. New notions and constructions of sparsification for graphs and hypergraphs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 910-928, 2019. 24, 25, 26
Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. Twice- raiic-ramanujan sparsifiers. SIAM Rev, 56(2):315 334, 2014. 3,
Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer. Dynamic algorithms against adaptive adversary: generic constructions and lower bounds. STOC '22: 54th Anmual ACM SIGACT Symposium on Theory of Computing. pp- 1671-1684, 2022. 4
11

---

Published as a conference paper at ICLR 2026
Omri Ben-Eliezer and Eylon Yogev. The adversarial robustness of sampling, In Proceedings of the 39th ACM 49-62, 2020.
Symposium on Principles of Database Systems, PODS, pp-
Omri
Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adver- sarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACC-SICAA symposium on Principles of Datahase Systems PODS20, 2020. 4, 10, 34, 35
Omri Ben-Eliezer, Talya Eden, and Krzysztof Onak. Adversarially robust streaming via dense- sparse trade-offs. In 5th Symposium on Simplicity in Algorithms, 2022a. 4
pp. 214-227,
Omri Ben-Eliezz Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A framework for adver- sarially robust streaming algorithms. J. ACM, 6902):1:1-117:33, 2022b. 4
Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, and Samson Zhou. Differentially private 12- heavy hitters in the sliding window model. In The Eleventh International Conference on Learning Representations, ICLR, 2023. 5
Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min-cut/max- -eww/ algo- rithms for energy minimization vision. IEEE Trans. Puttern Anal. Mach. Intell., 26(9): 1124 2004.
Vladimir Braverman and Rafail Ostrovsky. Smooth histograms for sliding windows. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Proceedings, pp. 283-293, 2007.
Vladimir Braverman, Rafail Ostrovsky, and Carlo Zaniolo. Optimal sampling from sliding windows. J. Comput. Syst. Sci., 78(1):260-25)) 272, 2012. 5
Vladimir Braverman, Elena Grigorescu, Harry Lang. David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Random- ization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM, pp- 7:1-7:22, 2018. 5
Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upadhyay, David P. Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In 61st IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. 517-528, 2020. 19
Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Sam- son Zhou. Adversarial robustness of streaming algorithms through importance sampling. In Ad- vances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems, NeurIPS, pp. 3544-3551 2021a. 2.4
Vladimir Braverman, Viska Wei, and Samson Zhou. Symmetric norm estimation and regression on sliding windows. In Computing and Combinatorics 27th International Conference, COCOON, Proceedings, pp. 528-539, 2021b. 5
Vladimir Braverman, Jon C. Ergun. Chen Wang, and Samson Zhou. Learning auggented hierarchi- clustering. In Proceedings of the 42nd International Conference on Machine Learning, ICML., 2025.
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. In Proceedings of the 35th International Conference Machine Learning, ICML., volume 80, pp. 687-696. PMLR, 2018.
Nicholas Carlini and David A. Wagner. Towards evaluating the robustness of neural networks. In 2017 IEEE Symposium on Security and Privacy, SP, pp. 39-57. IEEE Computer Society, 2017. 4
Amit Chakrabarti, Prantar Ghosh, and Manuel Stoeckl. Adversarially robust coloring for graph streams. In 13th Innovations in Theoretical Computer Science Conference, ITCS, pp. 37:1-37:23, 2022. 4
12

---

Published as a conference paper at ICLR 2026
Karthekeyan Chandrasekaran, Chao Xu, and Xilin Yu. Hypergraph k-cut in randomized polynomial time. In In Proceedings of the 2018 Anmual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1426-1438, 2018.
Chandra Chekuri and Chao Xu. Computing minimum cuts in hypergraphs. In Proceedings of the Twehty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1085-1100, 2017.2
Chandra Chekuri and Chao Xu. Minimum cuts and sparsification in hypergraphs. SIAM J. Comput., 47(6):2118 18-216,, 2018. 2
Jiecao Chen, Huy Nguyen, and Qin Zhang. Submodular maximization over sliding windows. CoRR, abs/161 1. 100119, 2016. 5
Jiefeng Chen, Xi Wu, Yang Guo, Yingyu Liang, and Somesh Jha. Towards evaluating the robustness of neural networks learned by transduction. In The Tenth International Conference on Learning Representations, ICLR. OpenReview.net, 2022. 4
Yuhan Chen, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge, and Nishil Talati. Demystifying Graph Sparsification Algorithms in Graph Properties Preservation. In 50th International Conference on Very Large Databases (VLDB 2024). ACM, 2024. 39
Yeshwanth Cherapananjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, and Samson Zhou Robust algorithms on adaptive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representations, ICLR, 2023. 4
Chandan Chunduru, Chun Jiang Zhu, Blake Gains, and Jinbo Bi. Heterogeneous graph sparsification for efficient representation learning. In IEEE International Conference Bioinformatics and Biomedicine, B/BM, pp. 1891-1896, 2022. 2
Michael B. Cohen, Cameron Musco, and Jakub Pachocki. Online row sampling. Theory Comput, 16:1-25, 2020. 2, 6, 8, 9, 10, 19, 20, 22, 24, 30
Vincent Cohen-Addad, David P. Woodruff, and Samson Zhou. Streaming euclidean k-median and k-means with o(log rı) space. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 883- 2023. 9, 10, 28, 29,33
Vincent Cohen-Addad, Shaofeng H.-C. Jiang, Qiaoyuan Yang, Yubo Zhang, and Samson Zhou. Fair clustering in the sliding window model. In The Thirteenth International Conference on Learning Representations, ICLR, 2025. 5
Graham Cormode. The continuous distributed monitoring model. SIGMOD Rec., 42(1):5-14, 2013.
Graham Cormode and Minos N. Garofalakis. Streaming a connected world: querying and tracking distributed data streams. In EDBT 2008, 11th International Conference on Extending Database Technology, Proceedings, pp. 745, 2008.
Graham Cormode and S. Muthukrishnan. What's new: finding significant differences network data streams. IEFF/ACM Trans. Netw,, 13(6): 2005. 5
Sanjoy Dasgupta. A cost function for similarity-based hierarchical clustering, In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pp. 118-127. ACM, 2016. 1
Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. Maintaining stream statistics over sliding windows. SIAM J. Comput., 3164)11794-111,, 2002.
Chengyuan Deng, Jie Gao, Jalaj Upadhyay, Chen Wang, and Samson Zhou. On the price of differ- ential privacy for hierarchical clustering. In The Thirteenth International Conference on Learning Representations, ICLR, 2025.
Mehmet Deveci, Kamer Kaya, and Ümit V. Çatalyürek. Hypergraph sparsification and its application to partitioning. In 42nd International Conference on Parallel Processing, ICPP 2013, pp. 200- 209, 2013. 2
13

---

Published as a conference paper at ICLR 2026
Matthew Ding, Alexandro Garces, Honghao Lin Jason Li, Jelani Nelson, Vihan Shah, and David P. Woodruff. Space complexity of minimum cut problems single-pase pass streams. arXiv preprint arXiv: 2412.01143, 2024. 3, 36
Itai Dinur, Uni Stemmer, David P. Woodruff, and Samson Zhou. On differential privacy and adap- tive data analysis with bounded space. In Advances in Cryptology EUROCRYPT 2023 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings, Part III, pp. 35-65, 2023. 4
Alessandro Epasto, Silvio Lattanzi, Sergei Vassilvitskii, and Morteza Zadimoghaddam, Submodular optimization over sliding windows. In Proceedings the Wide Web, WWW, pp. 421-430, 2017.
the 26th International Conference on World
Facebook. https///www.faccbboo.cco/opppppp 2021.
Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In The Thirty- -hird AAAI Conference Artificial Intelligence, AAAI, pp. 2019.
Yifan Feng, Yihe Luo, Shihui Ying, and Yue Gao. Lighthgnn: Distilling hypergraph neural net- works into mlps for 100x faster inference. In The Twelfth International Conference on Learning Representations, ICLR, 2024. 3
David A. Freedman. On tail probabilities for martingales. The Annals of Probability, pp. 100-118, 1975. 31
Yue Gao, Yifan Feng, Shuyi Ji, and Rongrong Ji. Hgnn*: General hypergraph neural networks. IEEE Trans. Pattern Anal. Mach. Intell., 45(3):111-33199 2023.
Ian J. Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In Yoshua Bengio and Yann LeCun (eds.), 3rd International Conference on Learning Representations, ICLR, 2015. 4
Google.
wtt.oo/ww...occccooooooo//reenno 2021. 5
Gramoz Goranci and Ali Momeni. Fully dynamic spectral sparsification of hypergraphs. CoRR, abs/2502.01421, 2025. 5, 17
Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou A strong sep- aration for adversarially robust lo estimation for linear sketches. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 2318 2343, 2024. 4
Elena Gribelyuk, Honghao Lin, David Woodruff, Huacheng Yu, and Samson Zhou, Lifting linear sketches: Optimal bounds and adversarial robustness. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC, pp. 395-406, 2025.
Avinatan Hassidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. In Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems, NeurIPS, 2020.
Arun Jambulapati and Aaron Sidford. Efficient Ó(nlE) spectral sketches for the laplacian and its pseudoinverse. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2487-2503, 2018.
Arun Jambulapati, Yang P. Liu, and Aaron Sidford. Chaining, group leverage score overestimates, and fast spectral hypergraph sparsification. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pp. 196-206, 2023. 3, 4, 7, 8, 19, 20, 21, 33, 34
Rajesh Jayaram, David P. Woodruff, and Samson Zhou. Truly perfect samplers for data streams and sliding windows. In PODS '22: International Conference on Management of Data, pp. 29-40, 2022. 5
14

---

Published as a conference paper at ICLR 2026
Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming using the bounded storage model. Advances in Cryptology CRYPTO 41st Annual International Cryptology Conference, CRYPTO Proceedings, Part III, pp. 94-121, 2021. 4
Michael Kapralov. Aida Mousavifar, Cameron Musco, Christopher Musco, Navid Nouri, Aaron Sidford, and Jakab Tardos. Fast and space efficient spectral sparsification in dynamic streams. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 1814-1833, 2020. 2,3
Michael Kapralov, Robert Krauthgamer, Jakab Tardos, and Yuichi Yoshida. Spectral hypergraph sparsifiers of nearly linear size. In 62nd IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. 1159-1170, 2021. 3, 6, 8, 23
David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, 2000. 36
Sanjeev Khanna, Huan Li, and Aaron Putterman. Near-optimal linear sketches and fully-dynamic algorithms for hypergraph spectral sparsification. arXiv preprint arXiv:2502.03313, 2025a. 3, 4, 5, 17
Sanjeev Khanna, Aaron (Louie) Putterman, and Madhu Sudan. Near-optimal hypergraph sparsifica- tion in insertion-only and bounded-deletion streams, 2025b. 5, 17, 18
Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337-333 2014.
James R. Lee. Spectral hypergraph sparsification via chaining. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pp. 207-218, 2023. 4, 18, 33
Lap-Kei Kei Lee and H. Ting. Maintaining significant stream statistics over sliding windows. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 724-732, 2006.
Yin Tat Lee and He Sun. An sdp-based algorithm for linear- spectral sparsification. In Proceed- ings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 678-687, 2017.2 2
Gaotang Li, Marlena Duda, Xiang Zhang, Danai Koutra, and Yujun Yan. Interpretable sparsification of brain graphs: Better practices and effective designs for graph neural networks. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD) 2023, pp. 1223-1234, 2023. 2
Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. In Ad- vances Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems, pp. 2308-22802 -2088 2017.
Pan Li and Olgica Milenkovic. Submodular hypergraphs: p-laplacians, cheeger inequalities and spectral clustering. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pp. 3020-3029, 2018. 2
Honghao Lin, David P. Woodruff, Shenghao Xie, and Samson Zhou. I, sampling in distributed data streams with applications to adversarial robustness. Proceedings of the ACM-SIAM Symposium on Discrete Algorithums, SODA, 2026. 4
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In 6th International Conference on Learning Representations, ICLR. OpenReview.net, 2018. 4
Julian J. McAuley and Jure Leskovec. Learning to discover social circles ego networks. In Pe- ter L. Bartlett, Fermando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger (eds.), Advances in Neural Information Processing Systems 25: 26th Annual Confer- ence on Neural Information Processing Systems NIPS, pp. 548-556, 2012. 39
15

---

Published as a conference paper at ICLR 2026
Mark EJ Newman. Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23):577788822 2006. 1
OpenAl.
privacy/, 2025. 5
Miles Osborne, Sean Moran, Richard McCreadie, Alexander von Lünen, Martin D. Sykora, Am- paro Elizabeth Cano, Neil Ireson, Craig Macdonald, ladh Ounis, Yulan He, Tom Jackson, Fabio Ciravegna, and Ann O' Brien. Real-time detection, tracking, and monitoring of automatically dis- covered events in social media. In Proceedings of the 52nd Anmual Meeting of the Association for Computational Linguistics, ACL. pp. 37-42, 2014.
Odysseas Papapetrou, Minos N. Garofalakis, and Antonios Deligiannakis. Sketching distributed sliding-window data streams. VLDB J. 24(3):355-368, 2015. 5
Tasuku Soma and Yuichi Yoshida. Spectral sparsification of hypergraphs. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 2570-2581, 2019. 2, 3, 18
Tasuku Soma, Kam Chuen Tung, and Yuichi Yoshida. Online algorithms for spectral hypergraph sparsification. In Integer Programming and Combinatorial Optimization 25th International Conference, IPCO, Proceedings, pp. 405-417, 2024. 3, 4
Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. In Proceed- ings of the 40th Annual ACM Symposium on Theory of Computing STOC, pp. 563-568. ACM, 2008. 2, 6, 18, 19
Daniel A. Spielman and Shang-Huu Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Anal. Appl., 35(3):835- 885, 2014.2 2
Yuuki Takai, Atsushi Miyauchi, Masahiro Ikeda, and Yuichi Yoshida. Hypergraph clustering based pagerank. In KDD 20: The 26th ACM SIGKDD Conference Knowledge Discovery and Data Mining, pp. 1970-1978, 2020. 3
Dimitris Tsipras, Shibani Santurkar, Logan Engstrom, Alexander Turner, and Aleksander Madry. Robustness may be at odds with accuracy. In 7th International Conference on Learning Repre- sentations, ICLR. OpenReview.net, 2019. 4
Nate Veldt, Austin R. Benson, and Jon M. Kleinberg. Minimizing localized ratio cut objectives in hypergraphs. In KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1708-1718, 2020. 2
Nate Veldt, Austin R. Benson, and Jon M. Kleinberg. Augmented sparsifiers for generalized hyper- graph cuts. J. Mach. Learn. Res., 24:207:1-207:50, 2023. 2
Zhewei Wei, Xuancheng Liu, Feifei Li, Shuo Shang, Xiaoyong Du, and Ji-Rong Wen, Matrix sketch- ing over sliding windows. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference, pp. 1465-1480. ACM, 2016.
David P. Woodruff and Taisuke Yasuda. Online lewis weight sampling. In Proceedings of the 2023 ACM-SIAM Symposium Discrete Algorithms,, SODA, pp. 4622 4666, 2023. 19
David Woodruff and Samson Zhou Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1183-1196, 2021. 4,5
David P. Woodruff and Samson Zhou. Adversarially robust dense-sparse tradeoffs via heavy-hitters. In Advances in Neural Information Processing Systems 38: Annual Conference on Neural Infor- mation Processing Systems, NewrIPS, 2024. 4
David P. Woodruff, Fred Zhang, and Samson Zhou. On robust streaming for learning with experts: Algorithms and lower bounds. In Advances in Neural Information Processing Systems 36: Annual Conference on Newral Information Processing Systems, NeurIPS, 2023a. 4
16

---

Published as a conference paper at ICLR 2026
David P. Woodruff, Peilin Zhong, and Samson Zhou. Near-optimal k-clustering in the sliding win- dow model. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems, NeurlPS, 2023b. 37, 38
Beini Xie, Heng Chang, Ziwei Zhang, Zeyang Zhang, Simin Wu, Xin Wang, Yuan Meng, and Wenwu Zhu. Towards lightweight graph neural network search with curriculum graph sparsifica- tion. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 3563-3573, 2024. 2
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR, 2020. 2
Xikun Zhang, Dongjin Song, and Dacheng Tao. Ricci curvature-based graph sparsification for con- tinual graph representation learning. IEEE Trans. Neural Networks Learn. Syst., 35(12):17398- 17410, 2024.7
Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In Proceedings of the 37th International Conference on Machine Learning, ICML, volume 119, pp. 11458-11468, 2020. 2
Chun Jiang Zhu, Sabine Storandt, Kam-yiu Lam, Song Han, and Jinbo Bi. Improved dynamic graph learning through fault-tolerant sparsification. In Proceedings of the 36th International Conference on Machine Learning, ICML, volume 97, pp. 7622-76333 2019.
A CONCURRENT AND INDEPENDENT WORK
We summarize several relevant results from concurrent and independent work.
Online algorithms. We remark that Khanna et al. (2025a) recently also achieved an online al- gorithm for hypergraph sparsification that samples 2 polylog(m) hyperedges. Their approach is based on maintaining logarithmic number of spanners and adding arriving hyperedges to a spanner based on connectivity within the spanner and a geometrically decreasing probability. In fact, due to efficient subroutines for these algorithms,, their update time is near-linear. Our algorithm has suboptimal update time, but we achieve better sample complexity and efficient working memory. By comparison, our approach is based computing balanced solution an optimization problem, and it is not clear whether there exists an efficient algorithm to achieve a fast update time. We also achieve an algorithm for online spectral sparsification with fast update time while losing poly(r) factors, which suffices for the remainder of our applications.
Dynamic algorithms. The framework in (Khanna et al., 2025a) also solves hypergraph sparsifi- cation in the fully-dynamic setting, where both insertions and deletions are allowed and time effi- ciency is prioritized. Their algorithm maintains a sparsifier with 3 polylog(m) hyperedges while requiring sublinear update time in Similarly, Goranci & Momeni (2025) provided dynamic al- gorithms for hypergraph sparsification using nr poly (log n, 2) space and r poly (log n, ! update time. These results naturally generalize the insertion-only streaming setting. Although they achieve better time efficiency, their space bounds lose polynomial factors r and log m. As we mentioned earlier, their sub-optimal space usage hinders the applications in the streaming setting, where the space efficiency is prioritized. On the contrary, our algorithm reduces the polylog(m)) factors to pooy log m) factors while maintaining a poly(n) update time, making significant improvements for dense hypergraphs (c.g.. m = 9)2")).
Hypergraph cut sparsifier. In addition, we note that Khanna et al. (2025b) recently showed that in an insertion-only stream, hypergraph cut sparsifier can be computed using " polyyog(n)) bits of space, establishing an S(log m) separation from hypergraph cut sparsification in dynamic streams. Their algorithm estimates the strength of components in the hypergraph, and whenever component gets sufficiently large strength, it contracts the component to a single vertex to save space. This idea extends their result more general bounded-deletion setting: if the stream has at most k
17

---

Published as a conference paper at ICLR 2026
hyperedge deletions, then 2 log k polylog(n) bits of space suffice for hypergraph eut sparsification. By comparison, our approach is based on a streaming framework that implements merge-and-redd coreset construction to the output of an online algorithm. We achieve algorithm that solves hypergraph spectral sparsification in insertion-only streams using ž log" log poly (log log( ()) bits of space, which generalizes the hypergraph cut sparsification result. Assuming there are no multi-hhperedges in the hypergraph, i.e., of space, and hence avoids extraneous dependence on polylog(m) (m) factors, i.e. we have the same dependencies as Khanna et al. (2025b) in the log m factors. In addition, in terms of the dependence on log n, space bound has factor of Ô (log" n), opposed to polylog(n) in Khanna et al. (2025b), and thus we achieve better space complexity when m is relatively small.
O (2*), algorithm uses 2 log r polylog(n) bits
B PRELIMINARIES
In this section, we introduce several important definitions and techniques related to graphs and hypergraphs. For integer n O, the notation [nx] to denote the set {1, f n... We use poly(n) to denote a fixed polynomial of n, whose degree can be determined by setting parameters in the algorithm accordingly. We use polylog(n) to denote poly(log n). We use Ô (F) = polylog F hide the polylogarithmic factors.
Hypergraphs. We state the formal definition of the hypergraph energy function and the hyper- graph spectral sparsifier.
Definition B.1 (Energy). For a hypergraph H (V, w). we define QH R. R to be the following analog of the Laplacian quadratic form Qu = EeEE w(e) max( _ xz,²² We define the energy Qx( of hyperedge e to be Qe(z) = wo(e) (ux( zo)², such that (H))) = =<<)=>>ERF Qe(z).
The above definition carries physical interpretation the potential energy of family of rubber bands. One can consider a hyperedge e as a rubber band stretched to encircle several locations {æe, V e), so maX(u (I. )2)² 2 is proportional to its potential energy Lee (2023). Soma & Yoshida (2019) introduced the following notion of the hypergraph spectral sparsifier, generalizing the definition for graphs (Spielman & Srivastava, 2008). The hypergraph spectral sparsifier is defined as a re- weighted subset F of the original hypergraph H, which preserves the energy of on H up to + e) -aprrxximation for all vectors x E R..
Definition B.2 (Hypergraph spectral sparsifier). A weighted hypergraph H is malipliitie spectral sparsifier for H if
( Se Qn(x), Va ER"
natural way to relate a hypergraph to multi- gulti- to replace a hyperedge with nodes by a clique of (5) edges formed by the nodes in that hyperedge, which is stated in the following definition of associated graph.
Definition B.3 (Associated graph). Given hypergraph H, define a multi-graph G (V, E) to be the associated graph of H by replacing each hyperedge = (U1...., U,) E H with the (2) edges (us Uz). where < < S r, each with weight w(e).
Graph Laplacian. We review the graph Laplacian that encodes the structure of graph into a matrix. The graph Laplacian is n X n matrix where its diagonal stores the weighted degree for each node, and the other entries store the weight of each edge (i.j) in G. The graph Laplacian provides way to view the graph spectral sparsifier problem a matrix spectral approximation problem so that one can implement numerical linear algebra methods to solve it.
Definition B.4 (Graph Laplacian). Given a weighted graph G (V, E,,)) w) with n vertices, the graph Laplacian matrix LG E Rax= is defined as
LG Σ w(e) (Xu Xv) Txx Xx),
where Xi denotes the elementary row vector with a single nonzero entry in the i-th coordinate.
18

---

Published as a conference paper at ICLR 2026
The graph Laplacian be written as the Gram matrix A ATA, A, where the incidence matrix A consists of binary vectors representing each weighted row in graph G.
Fact B.5. The graph Laplacian LG has the following properties:
(1) Let Luv be the graph Laplacian for an edge ue, so that
Law ro(c) (Xu xo)T(xe Xv).
Then LG = -o= Luv.
(2) For each i,j E [n], the (i,j)-th entry of La is the weighted degree deg(i) = EusjEEEev w(ij) for i 3 and -w(ij) for i # where w(ij) is the weight of edge (i,3).
(3) Let A E x) be the incidence matrix of G. where each row a, of A corresponds to edge (u, v) E E, that auv a Vw(e) (Xu -x). Then La = A
We remark that the matrix A sometimes denotes the adjacency matrix, an X square matrix with Aur = w(e) (u, v) E. in some other definitions of the graph Laplacian, e.g., L D-A A. Here, we stick to the notion of the incidence matrix A in (Jambulapati et al., 2023), which is different from the definition of the adjacency matrix. In addition, we sometimes abuse the subscript in this paper, e.g., a; = aue if e = (u, v)) is represented by the i-th row in the incidence matrix A.
In the graph spectral sparsification problem, the energy is defined be x LG which is x A Thus, sampling the edges of the graph is equivalent to sampling rows from the matrix A. In the hypergraph spectral sparsification problem, the definition of energy is slightly different. However, can still relate it to the graph Laplacian of its associated graph as follows.
Fact B.6. Let H = (V, E, w) be a hypergraph, let G = FV, w) be its associated graph, and let Lu be the graph Laplacian for edge (u, 1) in graph G. The energy Qe(z) of hyperedge satisfies
Qe(x)= = max I TT Luvo
(u,v)Ee
Spielman & Srivastava (2008) introduced the following definition of the effective resistance of an edge in the graph, and they sample the edge with probability proportional to its effective resistance, which results in sample complexity O (a log n). Due the equivalence mentioned above between spectral sparsification and matrix spectral approximation, the effective resistance of an edge turns out be the leverage score of the row a, in the incidence matrix A, where a; the row representing
Lemma B.7 (Effective resistance and leverage score). For graph G = =V. the effective
resistance of an edge e = (u, v) E E is the quantity re = w(e) (X, - - (xu Xx) where X; denotes the elementary row vector with single non-zero entry in the i-th coordinate, Given
matrix A E Raxd, the leverage score of row is the quantity incidence matrix of G. Let a, the row that represents the edge e. Then, we have Te T3.
(, (A -) Let A be the
Online leverage scores. We introduce core technical tool given by (Cohen et al., 2020), which gives the matrix spectral approximation in the online setting, i.c., the rows arrive sequentially in a stream. When that arrives before a, Therefore, we consider the following online variation of leverage scores to approximate the real leverage scores.
a; arrives, we only have access to matrix A,, which is part of the matrix A
Definition B.8 (Online leverage scores). Given matrix A E Raxd let A; denote the first i rows of A, i.e., A; ai o... a; where denotes the row-wise concatenation operator. The online leverage score of row a, is the quantity aA -a,
The next statement shows that the online leverage score is in fact an overestimate of the leverage score of a, in the whole matrix A.
Lemma B.9 (Monotonicity of leverage scores). (Braverman et al., 2020; Cohen et al., 2020; Woodruff & Yasuda, 2023) Given a matrix A E Rmxn, let T(a;) denote the leverage score of a; and let (L.))) denote the online leverage score of row a, Then 7 (a)(), 2 r(a:).
19

---

Published as a conference paper at ICLR 2026
The next statement bounds the sum of online leverage scores, which bounds the sample complexity.
Theorem B.10 (Sum of online leverage scores), (Cohen el al., 2020) Given a matrix E RRux,, let (a:) denote the online leverage score of row a;. Then Li=1 (oL(): O (n log ki), where the online condition number of A.
|| max
|A
||
With the above properties of monotonicity and bounded sum, one can generalize the following result for the online matrix spectral approximation.
Theorem B.11 (Online row sampling). (Cohen al., 2020) Given matrix A Ruxn defined by an insertion-only stream, let l (a,) denote the online leverage score of row a, Then sampling O (n log n log k)) rows with probability proportional TlL (a.) gives a 2-spectral approximation to A at all times.
C ONLINE HYPERGRAPH SPECTRAL SPARSIFIER
In this section, we present the complete analysis for our online sparsifier.
C.I MISSING PROOFS IN SECTION 2.2
We provide the missing proofs in Section 2.2. For simplicity, we paste our algorithm in Algorithm 4.
Algorithm Online hyperedge spectral sparsifier (restatement of Algorithm 1)
1: Require: Stream of m hyperedges for hypergraph H with rank
2: Ensure: Spectral sparsifier A for
3: Á + 0. p + O (1z log m log r), M + 0
4: for hyperedge e; do
5: 2t < 24-1 GETWEIGHHAASIGNNEETT.M et) (See Theorem 2.2)
6: for (u,
do
7: Sample weighted row auv 'v to M by online row sampling (Cohen et al., 2020)
{M is a 2-spectral approximation to z A, at all times t, i..., M TM 3 A, Z,A, 1
8:
2 M M}
9:
end for
10: for (u, v) E do
11:
Oue +- auv w(ee)) (MTM) a
12:
end for
13:
Pe, + min (1, 2p- ua)(e, }
14: With probability Pe,, H +- H U Det
Return A
16:
end for
We next show the correctness and bound the sample complexity of our algorithm. To begin with, we state the result of the chaining argument from (Jambulapati al., 2023).
Theorem C.1 (Correctness,
Theorem 10 in (Jambulapati al., 2023)). Given hypergraph H = (V. F, w) and its associated graph G = (V, F) with valid weight assignment 2, let Pe be chosen independently according to Definition 2.1. Let p = O (22 log m logr). Suppose that we sample each hyperedge e in H with probability Pe = min(1,pe P} and scale by + if is sampled. Then, the resulting hypergraph H. is a (1+ t)seettpttaall sparsifier for H with probability 1 11
poly(m))
Next, we assume that there is way to define the weight matrix Z, locally such that the sampling probability Pe, defined by Pe, 2 w(e) (ax anu (A, - aT satisfies Definition 2.1 and smaller than the sum of online leverage scores of /2// A. We state the result as follows and defer the discussion A Appendix C.2.
20

---

Published as a conference paper at ICLR 2026
Theorem C.2. [Restatement of Theorem 2.2] Given a graph G (V, with weight Z, and inci- dence matrix A and a newly-arrived hyperedge Et+1 C V with weight w(e+1)), then there is pro- As, that assigns a weight zuv to each edge (u.
cedure GET WeeTEEGHHASSGNNMMNTT e++1 such that it satisfies (1) ((,,))ee+: Zuo = w(e), and (2) max(u,)ee ( Z,A,) a
O Elurojee Tuo (Z) where is the leverage score function.
A.)).
Then, by Theorem C.I and Theorem 2.2, sampling each hyperedge with probability defined by Pe, 2 w(e) (.)e age (A, Z,A,)= 'aa,v gives a valid sparsifier with desired sample com- plexity. Recall that this approach implies suboptimal working memory. We apply the online row sampling scheme to sample from 2 A, reducing the rows we store.
Notice that the chaining argument in (Jambulapati et al., 2023) requires that the sampling probabili- ties be assigned independently. The following statement shows that pe, is defined independently of whether the previous hyperedges are sampled.
Lemma C.3. [Restatement of Lemma 2.3] For each time t, the sampling probability Pe, is indepen- dent of the hyperedges that have been sampled previously.
Proof. First, we stress that the construction of M by online row sampling from Z1/2 A and sampling the hyperedges separate procedures with independent inner randomness. Consider fixed stream of hyperedges e,, ... cm Let M, denote the matrix M at time t. When the inner randomness of online row sampling procedure is fixed, the sequence of matrices MI, Mn is also fixed. Then, the sampling probabilities Pe, are defined independently, each based on the value of (ax((.)) Aue" w(ex)-(M) -M---aT.. Thus, is independent of the hyperedges that have been sampled previously.
Next, show the correctness of Algorithm 4. Lemma C.4. Algorithm 4 outputs (1 + hyyeergag spectral sparsifier with probability 1 (mly(m))
Proof. By the guarantee of Theorem B.1 M is 2-spectral approximation to / A, all times 1. Then, the estimated quadratic form Quo satisfies qae 2 22 (A -A)- In addition, by Theorem 2.2, weight assignment satisfies E(,,))e Zur w(e) for each e, so the sampling probabilities Pe, satisfy Definition 2.1. Moreover, by Lemma C.3, the sampling probabilities are defined independently of previously sampled hyperedges. Thus, we can apply Theorem C.I directly to show that is (1 e)hhyeergg spectral sparsifier with probability poly(m)
Next, we upper bound the sample complexity and the working memory, where the latter is the number of rows that we store in M to compute the sampling probabilities of the hyperedges.
Lemma C.5. With probability edges. Moreover, it uses O (n log² n log m) bits of working memory.
poly(m)' Algorithm samples O (+x log n log m logr) hyper-
Proof. To bound the sample complexity, we only need to bound Σ Pe., where Pe, < (aX(e,)) 9av due our definition. Notice that the local weight assignment Ze41 defined by the sparsified graph with weighted incident matrix M at time f,, then by Theorem 2.2, our weight
assignment guarantees that (a,ee, dut = O ((uuviee (M)).
Since M is a 2-spectral
approximation 2 A, all times f, we have
X72
m
max Que O (u,u)Ee
Tuo (M.)
(a,e)EE
0
Σ
Ti
TL (Z (2/1
21

---

Published as a conference paper at ICLR 2026
where M, is the matrix M defined at time |F] is the number of rows in the incidence matrix A, and 70L denotes the online leverage score operator. Utilizing Theorem B.10, we bound the sum of online leverage scores the RHS of the above equation by O Ing r)). Therefore, we have
max Quo O (n logk). (u,n)Ee,
where |||| maX)e(1) ||,7" on the online condition number.
lla is the online condition number of A. We state upper bound
Fact C.6 (see Corollary 2.4 in (Cohen et al., 2020)). Suppose that all hyperedge weights integers from (poly(n),, then we have log K O (logn)
Suppose that the condition in Fact C.6 is satisfied, have
Σ
max (u,e)
Jue = O l)..
Then, due our choice of overestimate parameter p. we have
Σ
max quv = Yt log n log m logr)
Pe.
(u,0)Ee,
1=1
Thus, sample O (5 log log logr) hyperedges in expectation. Note that the inner random- ness of sampling each hyperedge with probability Pe is independent, then by standard concentra- tion inequalities, the number of sampled hyperedges is O (# log n log logr) with probability
poly(n)
In addition, by the guarantee of online row sampling in Theorem B.II, suffices to sample O (n logn log m) rows in Z A construct the 2-approximation M. Since we only need to store M compute the sampling probabilities, Algorithm 4 uses O (n log" n log m) bits of working memory.
Combining Lemma C.4 and Lemma C.5, we have the following result for hypergraph spectral spar- sification.
Theorem C.7 (Online hypergraph spectral sparsifier). Given hypergraph (V, E, w) with n vertices, m hyperedges, and rank r, there exists an online algorithm with O (n log n log m) bits of working memory that constructs a (1 + ---ppectall sparsifier with probability 1 poly(m) by sampling (a Bognlogm mlorr) hyperedges.
C.2 EXISTENCE OF ONLINE (7, e) BALANCED WEIGHT ASSIGNMENT
In this section, we show how construct the local weight assignment in Theorem C.2, In the offline setting, the "balancing weight" method mentioned previously is used to upper bound the number of samples. Suppose that for a hyperedge e, all edges (u, v) E have the same ratio (2 Then,
Pc. w(e) and (A ZAZZA-1 a = w(e)) Two 12
Zur
Here, (u, v)) can be any edge in Hence, have Zuv Pe w(e) Tuv- Recall that weight assignment satisfies E(u,o)e Znp = wee), then summing up the previous equation for all (u, v) e
gives Pe E(,,v)e Tao (Z 122 A), which is exactly the sum of the leverage scores as desired. Since exact balanced weights are hard to find, we turn the definition of 7y-balanced weight assign- ment, where the ratios 7x(2
within y fraction of each other. This only loses constant
2;
factor to the sample complexity.
We extend this definition to the online setting. Now, we have a weight matrix Z. an incidence matrix A, and incoming hyperedge Here, omit the subscript t in the previous sections for simplicity. We assign weights to each edge in e such that they satisfy the definition of y- balanced weights.
22

---

Published as a conference paper at ICLR 2026
Definition C.8 (Online (y, c-llanncd weight assignment), Given weighted graph G FV. and a hyperedge C V with weight w(e), we assign a weight Zuy to each edge (u, v) E e such that Eiunee Zue w(e) and add (u, v) G. We call it an online (%, e) -balanced weight assignment it satisfies
Tuv (Z
Tu' (Z
7
min (m
Suv
Su'v'
Kapralov et al. (2021) provided a greedy algorithm that shifts the weights from the edges with higher ratio to the edges with lower ratio. They prove that such weight shift operations always increase the spanning tree potential (ST-potential)) of the graph by certain amount, which is defined as follows.
(G) log
I Zuv
TET(G) (u,v)ET
Here, T(G) is the set of all spanning trees of G. Since the ST-potential is upper bounded, this process terminates in finite steps and results in a valid set of weights. We demonstrate that the be applied in the online setting by showing that weight shift operations still
greedy algorithm increase the ST-potential. Now, we formalize the definition of the weight shift operation.
Definition C.9 (Weight shift). Given weighted graph G = (V, F, F,z), an edge (u. v) F, and weight shift factor À E R. the graph G + X we is the weighted graph G' = (V, F,22) such that max (0, wwo }} and z'yor = of for all v'), E & F(((u,)):
Algorithm Online (y, -bbllanced weight assignment (restatement of Algorithm 2)
1: Require: Given weighted graph = (V. P. w). hyperedge C V with weight w(e)
2: Ensure: Online (y. e--balanced weight assignment
3: Initialize: for all (u, v) E e, set 2uv = w(e)/le)
4: G < (V, F (V,FUU(m. ((..))Ee(u U))
5: While G is not online (y; (r,e)- balancee weight assignment do
6: Select (u, v) # u', E such that yuo 7 qu'n' and ond {yro is the ratio in Definition 2.1}
7: f min(Zuvs 27-guu
1-1
8: Zav f- Zuv + A
9:
2''''' +- "n
10:
Return G
The following lemma upper bounds the ratio que (see Definition 2.1) of a bridge in a graph, which later used prove that we never the weight of bridge O; thus, the connectivity ensures that the ST-potential is always well-defined.
Lemma C.10 (Upper bound, see Fact 2.8 in (Kapralov et al., 2021)), For any weighted graph G = (V, =) and any edge (u, v) E F, we have Zuo Yun S 1, with equality if and only if (u, v) is a bridge.
The following lemma states the increment in the ST ST-potential when operate weight shift.
Lemma C.11 (Reduction lemma, see Lemma 5.7 in (Kapralov et al., 2021)). Given a weighted graph F,2) 2) and real number Y > 1, let (u, v) & (u',e') be two edges in F such that quv > Ja'v". Then for any X S Zuv- shifting X weight from (u, v) to (u', v') results in an increment of at least log (1 + Xyy Quo -.v X2r.. (aw) of the ST-pptential of G.
With the above results, we show that the greedy algorithm terminates finite number of steps. Theorem C.12. Algorithm 5 terminates in a finite number of steps.
Proof. This proof follows closely from the proof of Theorem 5.8 in (Kapralov et al., 2021), except that we have prefix-grape G and we only assign weights to the newly arrived hyperedge
First, we note that G is never disconnected. Otherwise, we need to set X = Zuv for some bridge (u, v) E so that it has zero weight after the weight shift. By Lemma C. 10, have zur Ruo
1
23

---

Published as a conference paper at ICLR 2026
7-1 So, would set À to 2-1 instead, which is contradiction. Therefore, the ST ST-potential 2y-9av (G) is always well-defined.
2yr
From Lemma C.II, whenever we make a weight shift in an unbalanced pair, the ST-potential of G increases by
log (1 + xy que - X que X2y girr
Next, classify our weight shift operation into two types. When X 2n-qus> the increment is at
least Cy := log 1- > O. When = Zuzs the increment is positive, and auter is set to zero. We specify these two cases as follows:
47
. 1. (G') at least increases by a constant Cy > 0.
. 2. (G) increases by positive amount, and Zw'v' is set to zero.
Now, we define Go to the weighted graph at the initialization stage Algorithm 5, and we define G to be complete graph with node set V with uniform weight wi(e) + 2 (v,))FF Fuv. where F is the edge set before adding hyperedge e. Note that E(,,)) Zur = w(e) by definition, then by the monotonicity of V, (G) S (G) for all obtained in Algorithm Therefore, there can be at most (((G)))-W1CG steps of weight shifts of the first type.
For the second type, if Zue O, then the number of zeros in the weight assignment for increases by 1, which only happens a finite number of times. Therefore, we only need to consider Suv 0. In this case, we switch the weight of (u, and (u', v'), and Ulu.))ee Zue remains the same. Then, the weight assignment can only be in finite stages without reverse. Thus, the number of weight shifts of type two is finite, and hence Algorithm terminates in finite steps.
Due to the algorithm's construction, it must output an online (7, ebbblanced weight assignment when it terminates. Therefore, we show the existence of such weight assignment.
Theorem C.13. Given weighted graph G (V, F,) and a hyperedge C V with weight w(e). there exists an online (y, e)-balanced weight assignment.
D FAST ONLINE HYPERGRAPH SPECTRAL SPARSIFIER
In this section, we give an online algorithm with a faster update time based on (Bansal al., 2019). We also include result with success probability 1 - poly(m)' which is used to give a streaming algorithm later, and show that the dependence on 8 only increases the space by a log log 1 factor.
As we mentioned previously, Bansal et al. (2019) constructed the associated graph by assigning weight w(e) to each edge the hyperedge e, and they sample e with probability
Tuvs where Fav w(e) (Xu X.) La (Xa Xv). (u,r)Ee
Pe
We extend this procedure to the online setting by maintaining a 2-spectral approximation Lo (t) to the graph Laplacian Lo(t) all times using online row sampling (Cohen al., 2020). Then, we use (t) to define the sampling probabilities. Our algorithm is displayed in Algorithm 6.
The energy of the hypergraph reported by Algorithm 6 can be written as random variable Exer (x). where X, is 1/p. with probability pe and 0 otherwise. Then, the error of our approximation is Ees (X. - -e) Bansal et al. (2019) simplified this term to sub-Gaussiae random process Vg. Then, they bound its increment by a simpler Gaussian process Ug, which can be further bounded by Talagrand's is chaining theorems. We show that their bound on the supremum of V2 can be directly applied prove our results. Intuitively, this is because the approximation
Lt( always gives overestimate of the effective resistance, which means that over-sample the hyperedges.
We remark that to show that the output A of Algorithm 6 satisfies the spectral sparsification guar- antee in Eq. (1), suffices to show its correctness for hypergraphs where all hyperedges have size
24

---

Published as a conference paper at ICLR 2026
Algorithm 6 Online hyperedge spectral sparsifier with faster update time
1: Require: Stream of m hyperedges for hypergraph H with rank r
2: Ensure: Spectral sparsifier H for H
3: + 0. p O log
log )
4: Let G be the associated graph of H. Let $ La(() 3 La(() = 2- Lol() for all E [m]] {Use online row sampling in Theorem B.113
5: for hyperedge e, do
6: for (u, e do
7: T(u,") t w(e)) (Xa x²) La(t)
(Xu Xv)
8: end for
9:
Pe. < min P (ux)e))) ((uu))
With probability pe,: A t AU 1
Ct
Pet
11:
end for
between [r/2, r| (see Lemma 5.2 of (Bansal et al., 2019)). In addition, we have (see Lemma 5.5 of (Bansal al., 2019))
4 Lax for all x R", 2 T Lox S Qu())
r(r rrr-1) 1)
all hyperedges have size between [r/ Thus, we only need to show that
(0(())-Q(zz) E - Laæ for all x E RR.
Next, we introduce normalized version of Qz(z).
Definition D.1 (Normalized energy, implicitly defined in Section 5.2 of (Bansal et al., 2019)). For hyperedge in H, let Pe denote its sampling probability, and let X be random variable that is 1/p. with probability Pe and 0 otherwise. Setting _ x and Yuu L/ Lue 1-12 gives
Qe(x)
max (u,u)EE
T Lao max Yuu (u,u)Ee
We define Wx(2) max Ee = Yuuz and (z(2)= = =EEE Wz(2). Let H be constructed with sampling distribution pe and rescaled factor X then
X.We(s).
With the normalized definition, desired equation becomes
( W (=())l < 72
for all 2 E B2
where Bg is the unit-Ez-ball in the subspace restricted the image of L We prove Eq. (2) in the following statements. First, we draw an equivalence between [|Yue and the effective resistance Tan- Fact D.2. Let || denote the spectral norm of matrix, we have ||well Tav-
Proof.
Notice that Yuv T 1/2 T.uu
T. 112
so we have
Yau = w(e) T.G 1/2 1/2 (Xa - Xo) (Xu Xo) I.G 1/2
To)TT(Xn X=) =((e) ((x- -x) 1. (Xu - Xo) 1-21/2
where e the weight of the corresponding hyperedge in H. Notice You is a rank-1 matrix spanned by vector (Xa Xx) LGs 1/2 thus, we have
||Ywell = Amax (Ywv) = w(e) (Xa - Xxv) La 11/2 (Ixa - Xx) Lo 12)
=((e) (Xu - -xx) Lg¹ (Xu [x)] Tuv.
xx)
25

---

Published as a conference paper at ICLR 2026
Now, state the bound on the supremum of the random process V2 defined in (Bansal al., 2019).
Theorem D.3 (Supremum of random process, Theorem 5.15 in (Bansal et al., 2019)). For hyperedge e in H, let G be the associated graph of H, we define the effective resistance of as Te maxxaxxuaaa vyee Tun, where Tun is measured in graph G. Let S E(H) be a subset of hyperedges such that [Yuell b for all (u,v) E and S, where I is some constant. For independent Rademacher variables & and vector 2 E IR" let
V2 Σ (Z).
EES
Then, we have E BB Vi] O (Vblogn), and for all u 2 0, we have
V 2 O (Vblogn + 2nvb) s 2e_na
Pr
sup Le
With the above lemmas, we show the correctness of our online algorithm.
Lemma D.4. Let H be the output of Algorithm 6, it is (1 + c)-uutiiplccative spectral sparsifier for H with probability 1 poly(m))
Proof. Fix time in the stream, let H be the hypergraph, and let H be the sparsifier. Notice that the sampling probability of each hyperedge is solely determined by the calculation of the online leverage scores , which is independent of the hyperedges sampled from previous arrivals. Therefore, can view the sampling procedure as a re-ordered procedure.
We state iterative sampling process introduced by (Bansal al., 2019). Let TO OLL (u) uu where Tue is calculated at the time that is sampled. We round each sampling probability Pe up to the nearest integer powers of 2. This ensures pe 2 _ doubling the expected sample complexity. Notice that hyperedges with Pe 1 not contribute to the sampling error, so can assume T.0L p for all
while most
E(H). Let Cj = {e E(H) Pe )). Now, we view the process of sampling in the following way. Let Ho = H, let = O (log and for i [1]. H; is obtained from H,-1 by sampling each hyperedge from the set (, independently with probability 1/2 and doubling the weight of if it is sampled. Thus, an edge E Cj that survives in H₃ is sampled with probability pe 2 and has weight X. 1/pc-
Cj
Now, for each
[t]. we define
(n.
Σ
Σ max (1, Wa(z).
(EC
Since Ho H and H1 H. by triangle inequality have
W (z) - WH(2)) S
(x) - (=)
Taking the supremum over all in Bg gives
sup
(T(()) (n( =
sup (H, (H) =EB,
sEB.
From our definition of the iterative sampling procedure, we have
WR. H. (2) W WH... (2) Σ
Σ
E.2 2-245---1
j=8- eEC,ne 1)
where Eo'S are independent Rademacher variables. m)X 2 Yuuz. Then, for any e UjE(U-it1,,- C₁, we have
Recall that we define Wc(x) =
| = = max Tue S T 2 3/1p (0.0)E
26

---

Published as a conference paper at ICLR 2026
where the first step follows from Fact D.2, the second step follows from the equivalence between effective resistance and leverage score (see Lemma B.7), and the third step follows from the over-
sampling property of online leverage score (see Lemma B.9). So, || uv |l s 2'-1 1/.ppp.. Applying Theorem D.3 with V WH, (z) WH,,((2) and Vlog 5 gives
(1 /p- log 3 )
Pr
sup V: O 21 B2
poly(m)
Recall that we set p
r 22
log th 8
Taking union bound over the I = O (logn) groups, we have
m Σ 2-11/0 1p- log EV2-1
sup [W Wn(=)] so 2e B2
0 73
8
with probability 1 1
poly(m) Taking union bound over arrivals in the stream, the same bound
5
still holds with probability poly(m) Thus, we show the correctness of our algorithm.
The next statement bounds the sample complexity, which mainly follows by the upper bound on the sum of online leverage scores.
Lemma D.5. With probability (oly(m)) Algorithm 6 samples O (rr In addition, it uses O (n log log m) bits of working memory and poly(n) update time.
("r² log log 7/) hyperedges.
Pe. Proof. It suffices to upper bound the expected number of samples EeEE(H) Pe. By our definition of Per is upper bounded by
Tue S p eEF(I) (u.N)En
Σ P. max
Σ
7 (awo),
(M,))E
where A the incidence matrix of the associated graph G. By Theorem B.10, the sum of online leverage score is bounded by O log k), where x ||ll/ max ||A I|2 is the online condition number of A. Therefore, the expected number of samples is O (pn log k)
// Note that the inner randomness of sampling each hyperedge with probability Pe independent, then by standard concentration inequalities, the number of sampled hyperedges O [rr log k log / with probability 1 poly(m). Suppose that the condition of Fact C.6 is satisfied, then we have log k = O (log n).
e O ny
log n log
In addition, by the guarantee of online row sampling in Theorem B.11, suffices to sample O (n log log m) rows in the incidence matrix A to construct the 2-approximation Lo(() to the graph Laplacian Lt(t)= = ATA. A. Since we only need to store Lo(t) to compute the sampling prob- abilities, Algorithm uses O (n log" n log m) bits of working memory. Moreover, the calculation of the sampling probabilitics only requires poly(n) time.
With Lemma D.4 and Lemma D.5, we have the following result for the online hypergraph spectral sparsifier.
Theorem D.6 (Online hypergraph spectral sparsifier). Given hypergraph (V, E, w) with vertices and rank there exists an online algorithm that constructs (1+))-xpectrul sparsifier with probability 1 poly(m) by sampling O ( (=r#t log n log 7 hyperedges, using O (n log² log m) bits of working memory and poly(n) update time.
Now, we specify the number bits needed to store each sampled hyperedge. Remark D.7 (Bits of precision). Suppose that all hyperedge weights are integers from [poly(n)), need O (r log n)) bits store each sampled hyperedge.
27

---

Published as a conference paper at ICLR 2026
Proof. First, note that it requires r log n bits to store the nodes included in the hyperedge. Sec- ond, for each reweighted hyperedge hypereed sampled by our algorithm, we round its weight w(e) to the near- est power of (1+0 (E)). Recall that the energy of a vector in hypergraph H is an additive function: (n) = EEER to(e)- (o(e))max(u,u) (In ), therefore perturbing each w(e) by a (1+O (e) )fraction only has an additional (1+ (e) muultiplicaaee error in our approximation guarantee, Note that we
sample each hyperedge with probability p proportional to w((e)) - (X., -x.) Lt(() (Xu--x), where (t) is a 2-spectral sparsifier of the associated graph G of the hypergraph H, and we rescale each sampled hyperedge by 1 p Thus, assuming that all hyperedge weights are integers from [p)] all eigenvalues in (t) are at most poly(m), and so the sampling probability p is then at most poly(m). there is at least poly(m) for each hyperedge. The rescaling factor p
are O loga choices of powers that we need to store. Therefore, we need O (log log m) bits to
store each sampled hyperedge, assuming that & S polylog(m). Since S (:) S ( then log log m < O (logr+ log log n) S O (rlogg)) and so the desired claim follows.
E STREAMING MODEL
In this section, we provide streaming algorithms for sparsification problems with nearly optimal space. We start by introducing the well-known merge-ande serge-and-reduce approach in achieving (1 + E)- coresets in data stream. An online (1 -ccorese for graph sparsification for graph G' defined by stream of edges e 6m is subset G of weighted edges of G such that for any IR and any t E [m]) we have (1 - -e-eea (x) s QG. (a) & (1 + e)QG, (I), where G2 is the set of hyperedges of G that have arrived by time t.
Let S(-) Ry0 denote mapping from input parameters the sample complexity of online algorithm. The online coresets for graph sparsification sample S(n, log m, e, d) edges for an in- put stream of length m on graph with nodes, accuracy E (0, and failure probability 6, with high probability. The merge-and-reduce approach partitions the stream into blocks of size
n2, log m, 2 log( poly(mm)) and builds a [1+ Togimms) -coreset for each block, so that each coreset can be interpreted as the leaves of binary tree with height most log(mn)) as the binary tree is balanced and has at most yn leaves corresponding to the edges that arrive in the data stream.
For each node in the binary tree, a coreset of size S n, log m, 2log(mnn' poly(mn) is built from the coresets representing the children of the node. Assuming that the coreset construction admits merging procedure, i.e., by taking the graph consisting of the union of the weighted edges in each of the coresets, then the root of the tree represents a coreset for the entire stream with distortion at log(mm)
most (1 2 [n]]
< (1 + e) and failure probability 5.
Cohen-Addad al. (2023) improved the above framework by adding an online sampling procedure ahead of the herge-and-reduce approach. Suppose that the online sampling procedure is nearly optimal. Then the input stream of the merge-and-redue approach is significantly shorter. In the graph sparsification problem, there is online algorithm that samples O ( n) edges, so the
6 coresets only have size S (n, log log n., 2log log(n] polylog(n) This turns polylog(1) factors into polylog log(n) factors, which is more space-efficient for huge graphs. We summarize this frame- work in Algorithm 7 and provide an illustration of the merge-and ponge--nd-reddus reducce framework in Figure 4.
E GRAPH SPECTRAL SPARSIFIER
We show that the streaming framework produces space-optimal streaming algorithms for construct- ing graph and hypergraph sparsifiers. First, in the offline setting, an efficient way to construct (1 + -o-resstsss for graph sparsifier is given by Batson et al. (2014), using only O (²² edges. We provide the formal statement below.
Theorem E.1 (Offline algorithm for graph spectral sparsifier). Batson et al. (2014) Given a graph G G= (V, E, w) with vertices, there exists an algorithm that constructs (1 (1+))-spectral sparsifier with probability 1 poly(x) using O (3) edges in poly(n) time.
28

---

Published as a conference paper at ICLR 2026
Algorithm 7 Streaming framework of (Cohen-Addad et al., 2023), using online sampling and merge-and-reduce (restatement of Algorithm 3)
1: Require: Stream S, online sampling procedure for S, merge-and-reduce procedure
2: Ensure: Coreset on S
3: for each update s; in the stream do
4: if' s, is sampled by online sampling then
5: Add the corresponding update to S'
6: end if
7: Run merge-and-reduce on S'
8: end for
Level 3:
Level 2:
Level 1:
Data stream:
Stream length
Fig. Merge and reduce framework on a stream of length m. The coresets level are precisely the hyperedges in the block, while the coresets at level L are (1 Zlog(m)) -coresets of the hyperedges contained in the coresets of the children nodes in level é - 1.
We then state the result for the online graph spectral sparsifier in Cohen et al. (2020).
Theorem F.2 (Online algorithm for graph spectral sparsifier). Cohen al. (2020) Given a graph G (V, E, w) with vertices and edges defined by an insertion-only stream, there exists 1 online algorithm that constructs a (1 + ++)==sppcctte sparsifier with probability 1 poly(ay. The algo- rithmn samples O n log² n) edges and uses (n log² n)) words of working memory and poly(n) update time.
Using the above subroutines, we show that our streaming algorithm has an optimal space up poly(log log n) factor, assuming poly(n) in the graph.
Theorem E.3 (Streaming algorithm for graph spectral sparsifier). Given a graph = (V, E,w w) with n vertices and m edges defined by insertion-only stream, there exists algorithm that constructs a (1 + e)-spectral sparsifier with probability 1 poly(n]' The algorithm stores a poly(log log n) edges, ie,, z log poly log n) bits, and has poly(n) update time.
Proof. The proof relies on the decomposability of the coresets, i.e., if Gj is an e-sparsifier of G1 and G2 is e'-sparsifier of G2, then G, U G2 is e' ssparsiifier of G, U G2. This is simply because the energy of a vector x on the graph G is the sum of the energy of all edges in G: Qc(x) = binary tree
Eeec (z). Then, the edges in the stream at level I + 1 in the merge-and-reduus construct a e' -sparsifier of the edges in the stream at level 1. Thus, the accumulative error of the coreset on the roof of tree of height & e'h.
In our online framework Algorithm 7, the hyperedges at the bottom level are the output S' of the online algorithm, which contains |S'| = O (53 log 2 n) edges by Theorem E.2. Thus, the height of the mergo-and-reduce data structure is h O [log (et). where |C| is the size of each coreset in the werge-and-reduce structure. We define C' by Theorem E.1, which selects O hyperedges. achieves accumulative error of most O (s'h =), which implies (1 + -paasssiiierr Then, |C| O (.) O ( log log" rz).
Hence, h O (log n.). Therefore, taking E' = = log log
So, we need at most O ([C) h) = O (= log log n) words of memory in total. The update time of streaming algorithm directly follows from the results from Theorem E.2 and Theorem E.
29

---

Published as a conference paper at ICLR 2026
Last, remark that the online row sampling procedure in Theorem E.2 requires sketch matrix of O (n log" 1a) rows to define the online sampling probabilities, which exceeds our desired space complexity. We note that it suffices to use the matrix consisting of the edges in the roof our merge- and-reduce tree structure, i... the output of our streaming algorithm. This gives the same guarantees for correctness and complexity as Theorem E.2 since our output is always a 2-spectral approxi- mation each step i. We defer the formal proof to Theorem E.7. Then, since we only need to store our streaming output to define the online sampling probabilities, which has _ poly(log (ng( edges, use f log ri poly (log log(n)) bits of working memory.
Optimizing the Working Memory. We introduce the method to optimize the size of the sketch matrix. In online sampling, when row a, arrives, the algorithm samples a, with probability proportional to the "A-ridge leverage score":
:= af
AT) a;,
where A is the prefix matrix containing all the rows arrived before a; and À is some parame- ter defined in advance. However, storing each A; explicitly requires a prohibitively large working memory. Instead, it suffices to use a 2-spectral approximation to A, define the sampling proba- bility, so Cohen et al. (2020) used A;, which is the approximation given by their online algorithm (see Algorithm 1 in Cohen et al. (2020)). However, A, still has O (n log" n) rows, which is pro- hibitively large for our purpose, we replace by the matrix consisting the edges in the roof of our merge-and-reduce tree structure, i.e., the output of our streaming algorithm. Next, we show that this modified online sampling scheme still gives the guaranties Theorem E.2. First, we state that oversampling gives valid graph sparsifier, i.e., the online sampling probabilities only need to be defined by & 2 E;
Theorem E.4 (Online Sampling Probability, Cohen et al. (2020)). Let A E Rmxa be incidence matrix of (multi- Igraph with n vertices and m edges, whose edge weights are integers in [poly(n)], let a be the i-th row A, and let A;-1 be the prefix matrix containing all the rows arrived before aa We define an online sampling scheme as follows. Let Eg satisfies
2 2 af AI a.
where X poly(n)
We set the sampling probability of row a, as P: min fol, 1}. and if a; is sampled, we store the re-weighted row D_ Then, let A, be the vp. 1
" (A)'
where c O log
matrix outputted by our sampling scheme for each E [m]] with probability least poly(m) we have
(1- (1-8)AJA, A,A. (1++)A
We remark that we set e = O logm g²
instead of c O logn in Algorithm 1 in Cohen et al.
(2020), to achieve a high success probability 1- poly(m) enabling us to condition on the correctness upon each arrival a, Next, we state upper bound on the sum of ridge leverage scores.
Theorem E.5 (Sum of ridge leverage scores, Cohen et al. (2020)). In the sampling schemed de- scribed in Theorem E.4, we define
e, - at (A AI) a,
where X-
min (A) Then we have Eie(m) ls = O logn).
[oly[n]
The upper bound Theorem E.5 gives an upper bound on the sum of sampling probabilities; how- ever, we cannot apply standard concentration inequalities to bound the number of sampled rows. This is because in the online subroutine, the sample probability of the current a; depends on whether the previous rows sampled, which is still the case after replace the sketch matrix in the online subroutine by our output from the merge-ane sarge-and-oa aeeee-nd--rddeee reduce process. Thus, we need to apply the following Freedman's inequality, which does not assume the independence of each sample.
30

---

Published as a conference paper at ICLR 2026
Theorem E.6 (Freedman's 's inequality, Freedman (1975)). Let Yu, .i.....B .y, be scalar martingale with difference sequence XI....,Xi Xn. i.e. Yo = and Y, Yı-1 11-1+22 +X, for all E [n]. Let Xel I R for all t E [n] with high probability. We define the predictable quadratic variation process of the martingale by wk = Ei [
for is E [n]. Then for all 2 0 and o² > 0, and every
k E [n].
2/2
Yi > and wh S o² S 2xxp 0² + Re/3
Pr
max [E(R]
Now, we show that the modified online subroutine satisfies the guaranties in Theorem E.2. Thus, only need store sketch matrix of O (5= poly(log log(n)) rows define the online sampling probabilities, which achieves the desired space complexity.
Theorem E.7. Let graph G = (V.E, w) with n vertices and m edges be defined by an insertion- only stream, let A be the incidence matrix of G, and let a; be the i-th row in A. We define an online sampling scheme as follows. Let l, satisfies
01) a. (AI XI)
a,
min min and A is the output of our streaming algorithm the last round (see the description in Theorem E.3). We set the sampling probability of row a, as Pt minfcl,, 1}, and if a; is sampled, we store the re-weighted row a. vp. Then, let A, be the 1 matrix outputted by our sampling scheme for each E [m], with probability least poly(m) we have
where X (oly(n)
where O log m
(1-E)AJ A = A (1+))A A..
The algorithm samples O ( log mn log n) edges and uses poly (n) update time.
Proof. First, we prove the correctness of our algorithm by applying Theorem E.5 in an iterative way. For initial stage, since is sampled by the online subroutine, A is (specrsl approximation of A₁, and A₁ is a 2-spectral approximation of A₁, Now, conditioning on that A;- a 2-spectral approximation A, Thus, the eigenvalues of A A + Al and , + AI are within constant fraction. Then, by our construction, we have
(1) a
a 2 a (A. + AI) a.
Now, consider the next arrival a,, by the guarantee of Theorem E.5, the output A, of the online procedure is still (1 approxximttoo with probability poly(m)) Condition this event, by the analysis in Theorem E.3, the output A, of our streaming algorithm probability mm) Following this induction, we prove that A, is a (1 + apappoxximnai for each E [m]. Since for each step, the success probability is at least 1 (m))
2-approximation with
union bound
across the arrivals.
Next, we bound the number of sampled rows. From our induction, we also prove that A, is a (1 +))- approximation for each i [m] with probability (oly(m)) By our construction of the scores C, we have
01) af A AI) a; = af AII) a.
Then, by the upper bound in Theorem E.5, have 2 (1). 20 (nlogn). Moreover, have Eie(m) Pt S Eie(m) 7, (+ m logmlogn..
Next, for each row a,, we define X, the indicator variable for a; shifted pt i.e., X, 1-p; if is sampled and X; -P otherwise. Thus, E [X,] = O. Then we define the martingale as Yo
[-1
and Y, Ejem X, for each i E [m), which is the difference between the number of sampled
31

---

Published as a conference paper at ICLR 2026
rows and EiElm Pi- For each i E [m], we have [X,] 1 and
E
pe(1 -Ps) S Pi, so
wy = EjE(1 E j-1 [ S Ezelg (eelg?? Py- Now, applying the Freedman's inequality (c.f. Theorem F.6)
with e log / Cigim] Pr and x² Eiefm) Pi, we have
Pr
|mll > logm m
Σ
Pi S
1 poly(m)
LE km(m]
That is, the number of sampled rows is ( log m log
n) with high probability.
E.2 OPTIMIZING THE WORKING MEMORY OF ONLINE HYPERGRAPH SPARSIFICATION
In this section, we optimize the working memory required in online hypergraph sparsifier, which is applied as black-box in our streaming algorithm for hypergraph sparsification in Algorithm 7. Recall that both algorithms in Theorem C.7 and Theorem D.6 store a sketch matrix obtained by online row sampling the associated graph, which is used to define the sampling probabilities of the hyperedges. We show that the sketch matrix can be replaced by the output of the streaming algorithm introduced in Appendix E. with fewer rows. The construction is based on the subroutine in Theorem E. The following
improved statement of Theorem C.7.
EV, w) with n vertices, m hyperedges and rank there exists an online algorithm with nr log n poly log m) bits of working memory that constructs a (L++)-sppecrrll sparsifier with probability poly(m) by sampling O [ log log m logr) hyperedges.
Theorem E.8 (Online hypergraph spectral sparsifier). Given hypergraph
Proof. Recall that we maintain a matrix M that is 2-approximate spectral approximation of the re-weighted incidence matrix A, in Algorithm 4. We slightly change the procedure define M: when hyperedge e++1 arrives, we run SEIWEIGHHASSIGNNENTT (M, e) to obtain the weight assignment vector 2++1; Then, for each edge uv in the clique of ct+1 we sample a V2t+1, by online row sampling and push it to the merge-and werge-and-reduce data structure if sampled (see Figure 4); then we set M to be the weighted matrix obtained by the merge-and aeee-and--rduuce procedure.
By the guarantee of Theorem E.3, sampling poly log m) rows to M by the wonge-and-redwce Z," process still gives a 2-approximation Z,/² AA, Moreover, we can optimize the working memory by the subroutine in Theorem E.7. That is, we can use M itself to define the online sampling probability for the next row in matrix 2//2
Then, it suffices to show that the updated procedure still satisfies the independence guarantees in the conditions of Theorem C.I. The analysis follows from the decoupling technique in Lemma C.3. The above procedure that constructs the sketch matrix M, which includes the online row sampling pro- cess and the merge-and wonge--nddreddee and-reduce process, and the sampling of the hyperedges are separate procedures with independent inner randomness. So, if we fix the inner randomness in the online row sampling process and the merge-and-reduce process in the construction of M, then the sampling probabilities are fixed. Then, given these fixed sampling probabilities, the sampling of the hyperedges can be viewed as an offline procedure, and for each the sampling of e, is independent of whether the previous hyperedges are sampled.
We next show the improved statement of Theorem D.6.
Theorem E.9 (Online hypergraph spectral sparsifier). Given hypergraph H (V, E, with n vertices and rank r. there exists an online algorithm that constructs a (1+ s)-spcctall sparsi- fier with probability - (mly(m) by sampling O nr poly log m) bits of working memory and (oly(n) update time.
(nr² log log 7) hyperedges, using nr log n
Proof. We the same construction in Theorem E.8. Recall that we do online row sampling the incidence matrix A and obtain a 2-approximation (t) to the Laplacian (t) = A A of the associated graph. Now, when edge a; is sampled by the online row sampling procedure, we again
32

---

Published as a conference paper at ICLR 2026
push it to the merge-and-reduce structure, and use the output to define the next online sampling probability. By Theorem E.3 and Theorem E.7, the output is still a 2-approximation to A, and hence it suffices for our amalysis in Appendix D.
E.3 HYPERGRAPH SPECTRAL SPARSIFIER
For the hypergraph sparsification problem, we apply the offline algorithms introduced by (Jambula- pati et al., 2023; Lee, 2023) to merge the coresets in the two child nodes.
Theorem E.10 (Offline algorithm for hypergraph spectral sparsifier). Jambulapati et al. (2023); Lee (2023) Given a hypergraph H = (V, E, w) with n vertices. m hyperedges and rank there exists an algorithm that constructs a (1 + s--spctla sparsifier with probability 1 poly(m) using
O ( logn log hyperedges in Ô (mr) time.
Notice that there no guarantee that we can find a (7,e) -yalaanal weight assignment in Defini- tion C.8 in polynomial time, so using the online algorithm given by Theorem E.8 as a subroutine does not imply a fast update time. Therefore, we instead apply Theorem E.9 with poly(n) update time the online sampling subroutine. This will lose a poly(r) factor in the online sample com- plexity; however, is acceptable since the streaming framework reduces to polylog(r). We also include the result by applying Theorem E.8 in statement, which has a better space bound.
Theorem E.11 (Streaming algorithm for hypergraph spectral sparsifier). Given hypergruph H (V, E, w) with a vertices, mn edges and rank r defined by an insertion-only stream, there exists an algorithm that with probability 1- paly(m]. constructs (1+=)- sparsifier. storing 2h logn- rn log" pooly poly(logr, log log bits, and using poly(n)
poly (log r, log log m) hyperedges, i.e., Ez update time. There is also an algorithm that stores 2/- log n logr poly(log logm) hyperedges, i.e.
go log" logr poly (log log m) bits, and uses exponential update time.
0 ( log logr) by O (logr + log log m). Taking e' = z/h, our total space usage is at most O (IC) h) = O = log ni logr (logr + log log m))) words.
Proof. We have |S'| 0 1r -
log n logm) by Theorem E.9 and |C| =0
Theorem E.10. Thus, the height h O log
SS [C|
Each time a hyperedge arrives, the online algorithm needs poly(n) time process by Theorem E.9. In addition, we at most need to merge 2h coresets each with m' = |C| edges, which takes Ô (m'r). h = (nly(n) update time by Theorem 10 Thus, we need poly(n) update time in total.
If we use Theorem E.8 instead, then S = = (5x log n log m logr) and = O (log log.). Hence, need O (IC)- h) O ( log log log log" m) words of memory in total.
Notice that the failure probabilities of both the offline and the online subroutines are poly(m) thus, the failure probability of our streaming algorithm follows by a union bound across all times.
E.4 HYPERGRAPH SPECTRAL SPARSIFIER HIGH PROBABILITY
In this section, we provide streaming algorithm that succeeds with probability at least 1- poly(m)) In our online algorithm in Theorem D.6, we lose a log 1/ factor in the sample complexity to boost the failure probability to 6, which may be prohibitively large if 5 of (Cohen- CCohen-Addad et al., 2023), we reduce it to log log? 3 factor.
With the streaming framework
Theorem E.12 (Small failure probability). Given hypergraph H = (V, E, w) with n vertices, m hyperedges, and rank r defined by an insertion-only stream, there exists an algorithm that constructs (1 + ep-specaall sparsifier with probability 1 poly(m) storing 2 log n. poly r, log log ") hyperedges, ie., z log" n. polyyloogrr log log T)) bits.
Proof. First, we describe a deterministic offline algorithm that constructs a (1 +++) (1-e--ypeeggraph spec- tral sparsifier. loses more poly(n) factors at runtime while it does not fail. Since Theorem 1. gives randomized algorithm that finds the sparsifier with O (a log logr) hyperedges given any
33

---

Published as a conference paper at ICLR 2026
hypergraph with non-zero probability, there must exist such a sparsifier. Let m denote the total num- ber of hyperedges. We simply traverse through all possible groups of O ( log n logr) hyperedges, where there are (o( 2 logr)) of them. For each group, we test it on the net of points z E IR"
mn
given by the chaining argument in (Jambulapati et al., 2023) and report this group of hyperedges it successfully approximates the energy of the hypergraph QH(2).
Then, we use the online algorithm in Theorem E.9 with failure probability (ml) to construct the stream S' and the offline deterministic algorithm mentioned above to construct the coresets. The calculation of space complexity follows from the same argument in Theorem E.11. Here, we have nr' |S = e/2 log n log m by Theorem E.9 and |C| = θ e log n logr) by Theorem E. Thus,
the height h = O (log
= O (logr + log log )) Taking e' = e/h, our total space usage is at most O (ICI h) = O gz log n logr (logr + log log )) words. Unfortunately, we do not have the (nly(n) update time guarantee due to the offline deterministic algorithm.
LS C
Notice that the failure probability of the online subroutines is ppllymm and the offline subroutine is deterministic, thus, the failure probability of our streaming algorithm follows by union bound across all times.
8
E.5 ADVERSARIALLY ROBUST HYPERGRAPH SPARSIFICATION
In this section, we apply the result in Appendix E.4 to achieve an adversarially robust streaming al- gorithm. The adversarially robust model can be captured by the following two-player game between a streaming algorithm P and an adversary A that produces adaptive inputs to P. Given a query function Q, the game proceeds over m rounds, and in the t-th round:
(1) A determines an input 8t, which possibly depends on previous outputs from P.
(2) P processes 8 and outputs its answer Zμ to the query function Q.
(3) A receives and records the response Zr.
The goal of P is to produce a correct answer Ze to the query function Q based on the previously arrived data stream { } sent by the adaptive adversary A, at all times t E [m]] We now provide an adversarially robust streaming algorithm for hypergraph sparsification.
We begin with the definition of the e-flip number, which upper bounds the number of multiplicative increments of the output of a streaming algorithm.
Definition E.13 (E-flip number). Let E 2 O and let y = (yo, .i...., ym)) be a sequence of real numbers. Then, the e-flip number de,m (v) of the sequence is the maximum ls for which there exists O S h < < i S m so that yi & (1 + =E)yi, for every j = 2.3..... k. In particular, for a function g R + R and class of data stream S C [n]m, the (E, m-fppp number (g) of g over S is the maximum s-flip number of the sequence y = (yo, y1,.... ymm) defined by yr = 9 ( (81,...,8.) St), over all choices of data streams S (s1, 8m) E S.
Ben-Eliezer et al. (2020) introduced framework for vector-based problems, i.e., one computes target function on the frequency vector induced by the data stream, which transforms any non- robust streaming algorithm an adversarially robust streaming algorithm. The core idea is that we only change the estimate I when it increases by an s-fraction, so if the E-flip number is small, then the total number of input streams that we need to handle is also relatively small, and we can union bound across them by setting a sufficiently small failure probability 5 for the non-robust streaming algorithm. We adapt their framework to solve the sparsification problems.
Robust Graph and Hypergraph Sparsification. We start by introducing an adversarially robust streaming algorithm for graph sparsification. A challenge in our problem is that our output is sparsified graph that preserves the energy of all vectors, which is not a real number, so we need to define proper way to change the output. Recall that the energy of vector on G is the quadratic form x" LG where LG is the graph Laplacian. Thus, we use the eigenvalues of LG to decide whether change the output. We state the formal algorithm and its guarantees as follows.
34

---

Published as a conference paper at ICLR 2026
Theorem E.14 (Robust graph sparsification). Given (multi-)grappl G (V, E, w) with vertices and m edges defined by an insertion-onll ootl stream, there exists an adversarially robust algorithm that constructs a sspecrsp sparsifier with probability 1- poly(m) storing _ -poly (log n, log log ) edges, i.e., - -poly(log n, log log % bits.
Proof. First, bound the s-fiip numher in our problem, which is the number of times that L 7 (1 + +e) Lgg where G' is a graph later in the data stream. Recall that our stream is insertion-only, so all the eigenvalues of G are increasing. Note that the flip does not occur if none of the eigenvalues of G increases by an e-fraction. Here, without loss of generality, we assume that all eigenvalues are non-zero, since we can consider it a flip when the eigenvalue first becomes non-zero, and there are at most such flips. Assuming that all edge weights are within poly(n), the eigenvalues at the end of the stream are upper bounded by mn poly(n), and so each eigenvalue can increases by an e-fraction for at most
times. Thus, the E-flip number is at most Am (G)
log 122
We next state the formal algorithm for robust graph sparsification. We run non-robust streaming algorithm with parameters e = and 8' = poly(mm) (x)) where À == X Xg.m (,m(()) (G) and log T are the
bits of precision. For the sequence of outputs GI,.... Gm. let 91 = G1 we set G. = - when all eigenvalues of LGG are within a (1 + )-fractinn of that of Lg..., otherwise we set Gt G.. The output to the adversary is the sequence GI.... Gm.
We prove the correctness of the algorithm as follows. Consider fixed time when we change the output, and let 1' be any time after / before the next output change. Note that Gp is a g E-sparsifier
of Gp and all eigenvalues of T. are within a (1 + g --rraction of that of L. so all eigenvalues
of LG., are within a (1 + ))-fraction of that of LG,- This implies that LG,, = (1 + 5) LG., and (1+ 55)xz² x= "L,, for all vectors x E RR. Therefore, Gr = G. is an E-sparsifier of Gr. Moreover, we can assume the adversary to be deterministic (see the proof of Lemma 3.5 in (Ben-Eliezer et al., 2020). Then, the number of output sequences is at most (*)TA and they at most determine (T)TA choices of input streams. Since we the failure probability 8'
so x LG, x S (1 +
(oly(m)((7)T)) we can union bound across all choices of input streams, ensuring the correctness of our algorithm.
By Theorem E.12, have that the non-robust streaming algorithm with parameters E, 6 stores ftr logn . poly log Th) edges. Therefore, since we require log T = O (log n + log log m) bits of precisions, the robust algorithm stores ş log n poll log yo = .t log" 2 n poly(log log z edges.
Next, we apply the above result to construct robust hypergraph sparsification algorithm. Note that the energy of a vector x on a hyperedge e is defined as the maximum energy of x on each edge (u, v) in the clique of e, so we cannot directly define the s-flip number by the sparsified hypergraph. Instead, we run a separated robust subroutine that constructs a sparsifier for the associated graph with higher accuracy, then we decide whether to change the output by the eigenvalues of the sparsified associated graph. We introduce the formal algorithm and analyze its guarantees as follows.
Theorem E.15 (Robust hypergraph sparsification). Given graph H (V, EVE,w) with n ver- tices, m edges, and rank defined by an insertion-only stream, there exists an adversarialyy ro- bust algorithm that constructs a (1 + e)-spectral sparsifier with probability 1 poly(m) storing
= poly (log n, log r, log log /h) hyperedges and pr poly(log n, log log 3) edges in the associated graph, i.e., 2 polyyloo n, logr, log log )) bits total.
Proof. We first state the formal algorithm for robust hypergraph sparsification. We run the ro- bust streaming graph sparsification algorithm Theorem 1. on the associated graph G of the hypergraph H defined by the stream with parameters = ş and å ō, and we have the out- puts G1.... Gm- Here, we note that G' is defined by the standard associated graph definition in Definition B.3, but not the lllanced-weight version introduced in Section 2. We run a non non-robust hypergraph sparsification algorithm separately with parameters e' š and 8'
(al((m)-TTTr where X = >= mm m (G) and log T are the bits of precision, and we have the outputs A fh,... Am. Let
35

---

Published as a conference paper at ICLR 2026
1/1 H1, set H4 H4-1 if 9: 91-1, otherwise set M4 Hy. The output to the adversary is the sequence H1.... Hmm
We prove the conrectness of the algorithm as follows. Consider fixed time when we change the output, and let be any time after before the next output change. We note that is also the time when the robust graph sparsification algorithm changes its output. Then, from the analysis in
Theorem 14, we have La = (1+ 2Tz LG. and x LG, 1 (1+ ))) ) La, x for all vectors
E R". Recall that the energy of x on the hypergraph H is (z) EEEg max(, x' Luo
which is at least + EeEE ((,,)ee x² Luv a x LGE, since there are at most (2) edges (u, v) E e. Then, we have
QH(T) & QH)(x) + 2, x La. s (1+ (H)
Therefore, Hy H, is an e-sparsifier of Hy. Since we the failure probability 8' (aly(m)-(()rx we can union bound across all (T)T* choices of input streams, ensuring the cor- rectness of our algorithm.
By Theorem E.12, we have that the non-robust streaming algorithm with parameters e',8' stores ZZ log poly(log r, log log m) edges. Note that the number of times that we change O nr log(ma)
the output hypergraph is A
Therefore, since require log
O (r logn + log log m) bits of precisions, our algorithm stores /ht log n- poly r log log 3)) = n E poly(log n, log r, log log / hyperedges. In addition, by Theorem E. the robust graph sparsi- fication algorithm for G with parameters É, stores uud 2 poly((og n, log log / edges.
E.6 GRAPH MIN-CUT APPROXIMATION
In this section, we apply the streaming framework to solve the graph min-cut approximation prob- lem, which asks for (1 + -)approximationn the size of the min-cut. First, we introduce relax- ation to the graph spectral sparsifier called the graph for-each spectral sparsifier, which a graph G that satisfies, for any given vector IR", it preserves the energy of in the original graph G with probability
Theorem E.16 (Offline algorithm for graph for-each sparsifier). (Ding et al., 2024) Given a graph
G= (V, E, w) with vertices and edges, there exists an algorithm that constructs (1 + e)-for- each spectral sparsifier with probability 1 of working memory and Ô (m) update time.
poly(n) p- samples Ô (=) edges and uses Ô (2) words
Ding et al. (2024) proposed an algorithm for min-cut approximation in the offline setting using the above procedure and graph for-all sparsifiers: We first utilize the graph spectral sparsifier to give 2-approximation to all cuts. Then, let c* denote the minimum cut the sparsifier, we select set S that contains all cuts within a factor of 4 of c", so S contains the actual minimum cut. It is known that there are at most n (CC) cuts that are within C-factor the min-cut (Karger, 2000) for any C> which means that S has most 011) items. Thus, we can obtain (1 + e)-graph for-each sparsifier and select the cut in S that has the minimum energy on the for-each sparsifier. We can union bound over the failure events of the graph for-each sparsifier across each cut query S, so we obtain a (1 + eesttmmaaion to the min-cut with high probability.
Theorem E.17 (Offline algorithm for min-cut approximation). (Ding et al., 2024) Given a graph G = (V, E, w) with n vertices and m edges, there exists an algorithm that provides a (1 + s)- approximation to the min-cut with probability 1 - poly(n)- It samples Ö (m) edges and uses ① m words of working memory and (nly(n)) update time.
Ding et al. (2024) applied merge-and-reduce directly to the input data stream to achieve streaming algorithm, which loses an extra log factor. We show that using the aforementioned framework, where we first obtain online graph spectral sparsifier and then run the offline algorithm in each coreset, we can improve this log n factor to a log while maintaining a (oly(n) update time, achiev- ing more efficient space.
36

---

Published as a conference paper at ICLR 2026
Theorem E.18 (Streaming algorithm for graph min-cut approximation). Given graph G (V. E, w) with n vertices and m edges defined by an insertion-only stream, there exists a streaming algorithm that provides a approxxmattiiinn to the min-cut with probability 1 1- poly(n] It stores - polylog(n, 2) edges, i.e., -polylog(n, !) bits, and uses poly(n) update time.
Proof. We use the online algorithm in Theorem E.2 to generate the stream S'. It produces an online for-all sparsifier, which generalizes an online cut sparsifier for the graph. We use the offline algorithm for for-each sparsifier in Theorem E.16 to construct the coresets. Then, the coreset on the roof of the binary tree (1 + e--for-each sparsifier by setting
e/h. Then, we can use the same method in Theorem E.17 to select a set S that contains the min-cut and output the cut with the minimum energy on the (1 + e)-for-each sparsifier. The union bound argument Theorem E.17
gives the correctness of our streaming algorithm.
The calculation of the space complexity and the update time is similar to that of Theorem E.11.
From Theorem 1,16 and Theorem E.2, we have |S' = O ( log" n) and |C| = θ (3 polylog "). so the height of the merge- merge-and-reduce data structure is log [c] o (log 1 Thus, we require O (IC) h) A polylog(n, !) words of space in total. The update time of the streaming algorithm is upper bounded by the bounds Theorem E.2 and Theorem E.
is')
F SLIDING WINDOW MODEL
In this section, we consider the sliding window model. Although the merge-and-reduce procedure produces coreset for an insertion-only stream in straightforward way, it fails for the sliding win- dow model due to the expiration of elements at the beginning of the data stream by the sliding win- dow. Since coresets carlier blocks of the streams are no longer valid, then the coreset at the root of the stream would no longer be accurate. To resolve this issue, Woodruff et al. (2023b) observed that
we can once again partition the stream into blocks consisting of S n, log m, 2 Tog[mmn]+ poly(mmn) hyperedges. However, instead of creating an offline coreset for the hyperedges in each block of up- dates, we create an online coreset for the elements in the reverse order of their arrival. Specifically, the hyperedges in each block and each coreset stream that consists of the hyperedges in the reverse order and then we can feed the synthetic stream as input to the online coreset construction. In this way, this effectively reverses the stream, so that the sliding window always corresponds to the beginning of the stream. Crucially, the online coreset construction implies correctness over any prefix of the reversed stream, which translates to correct- ness over any suffix of the input stream, including the sliding window. For the sake of completeness, we present this approach Algorithm 8.
explicitly stored, can create synthetic data
The following proof shows the correctness of the framework in Algorithm 8. It uses induction and is entirely standard, adapting the approach in (Woodruff et al., 2023b).
Theorem F.1. Let ei. em be a stream of hyperedges, let E (0, 1) be an approximation param- eter, and let H = (eem---1.-.. Cm } be hypergraph defined by the W most recent hyperedges. Suppose there exists a randomized algorithm that with probability at least 1 8, outputs an on- line coreset algorithm for hypergraph sparsification using S(n, log m, hyperedges. Then there exists a randomized algorithm that with probability at leust - 6, outputs a (1 + + 3>-hypergruph
sparsification in the sliding window model, using O (s (n, log m, 2 2lgg(mn) (mn]a) log(mn)) hy- peredges.
6
Proof. Consider Algorithm 8, where CORESET H,, e, 6) is randomized algorithm that, with prob- ability at least computes a (1 + a)appoooiiaaee online coreset for hypergraph sparsification on an input hypergraph H that has nodes and m hyperedges.
We first claim that for each index i. C2 a (1+ 2log(mmn] online coreset for hypergraph spar- sification for 2 M hyperedges. Indeed, note that C2 can only be non-empty if some time, the coreset Co contains M hyperedges and the coresets Ci...., C are all non-empty. Then by
the correctness of the subroutine CORESET, C₁ is a + 2 [lo online coreset for the hyper-
37

---

Because each subroutine has failure probability at most 4 imajz then the total failure probability is at Published as a conference paper at ICLR 2026
Algorithm Algorithm for hypergraph sparsification in the sliding window model via merge-and-
reduce and online coresets, adapted from (Woodruff et al., 2023b)
1: Require: Hyperedges e1.-.., 6m on n. vertices, accuracy parameter E (0, 1), failure proba-
bility ó E (0, 1), and window size W > 0
2: Ensure: Hypergraph sparsification of the W most recent hyperedges
3: Let CORESET(H, 6) be online coreset construction that samples S(n, log(mn)) e,)) hy- peredges, where H has n vertices and m hyperedges
4: M O (n, log(m)),, 2ogimm))
(1773))
5: Initialize coresets Co, Ci...., (og(())))
6: for each hyperedge ez with E [m]] do
7: if' Co does not contain M hyperedges then
8: Prepend e, Co. i.e., Cu {a)UCs
9: else
Let i be the smallest index such that C; = 0
11:
C; < CORESET H, log(mm)) (mn)²) where H = U.U...UCH-
12:
{H is an ordered set of weighted hyperedges)
13:
For j 0 to j 1, reset Cj= f
14:
Co + {er}
15:
end if
16: Return the ordered set Co U... 1og(mn)> in reverse
17:
end for
edges in Co U U....UC-1 at some point during the stream. It follows that by induction, C is
1 mlo 2 M hyperedges.
+ Tlg((mm)
(1+ [og online coreset for M + - 20-1 M
Observe that Algorithm 8 inserts the latter hyperedges to the beginning of Co. Hence, the stream is fed in reverse to the merge-and- perge-and-reduce procedure. In other words, for any W E [2'-1,2] 2'), the reverse of Co U...UU U, provides (1 + e)-hypergraph sparsifier for the W most recent hyperedges in the data stream.
Moreover, there are most m hyperedges in the data stream. For each hyperedge, there are at most log(mm) coresets constructed by the subroutine CORESET, corresponding the height of the tree.
most 5 by union bound. This completes the argument for correctness.
remains to justify the space complexity. To that end, observe that there are at most O (log(mn) (mn) online coreset constructions Co...., Clog(mmn) simultaneously stored by the algorithm. Since each hyperedges, then the total num- ber of stored hyperedges is O (5 (n, log m, Tlg((mn] [mn)) log (og(m as claimed.
online coreset construction samples S (n, log m, 2 2og log[m))) (mmn)²
5
We give the following result for hypergraph sparsification in the sliding window using the above framework.
Theorem F.2. Given hypergraph = (V, E) with n vertices, m hyperedges, and rank defined by an insertion-only stream, there exists an algorithm that constructs (1 ---spectaal sparsifier in the sliding window model with probability polyiny- ez log polylog(m, r) bits.
1 It stores 2 polylog(m,, hyperedges, i.e.
38

---

Published as a conference paper at ICLR 2026
G EXPERIMENTS
In this section, we perform a number of empirical evaluations to complement our theoretical results.' The experiments are conducted using an Apple M2 CPU, with 16 GB RAM and 8 cores.
Experiment setup. We compare the performance between three algorithms: the online algorithm, the ande--uud-eddeee approach applying directly to the input stream, and our streaming algorithm. In each comparison, we set a budget for the number of sampled edges and compare the multiplicative error of the three algorithms. For each experiment, mean. We first test synthetic graphs. Given inputs n. and m, we randomly generate a graph with n vertices and m edges: for each edge, we uniformly sample two vertices from [r] and select its weight from the distribution ( 10). We allow multi-edges in the graph. We then test the Facebook ego social network from the Stanford Large Network Dataset Collection (SNAP) (McAuley & Leskovec, 2012). We choose the graph from user 107 with n = 1034 and m = 53498, and we also select its weight from the distribution (1, 1, 10) since the original graph unweighted.
iterate 5 10 times and take the arithmetic
Graph metric. Let LG and Lg be the graph Laplacian of the original graph and the sparsified graph, respectively. We note that the multiplicative error of the sparsifier is maX
x ="Iميo-Laa which >"T.g
is the generalized Rayleigh quotient of matrices LG and LG. To measure this quantity, we solve the generalized eigenvalue problem (Lg - La)x = A- Loa and obtain the maximum eigenvalue, which equals to the multiplicative error by the properties of generalized Rayleigh quotient.
Fine-tuning the parameters. Given a budget L, we fine-tune the parameters for each method such that they output roughly edges, and thus ensure that they have the same space budget. In the online algorithm, we sample each edge e with probability p Te,, where Te, is the effective resistance of e, in the graph Lt(t) constructed by the previously arrived edges. Since we do not have a fixed relationship between the sum of online leverage scores and we fine-tune the parameter such that the mean 10 trials is within + 200. Note that the second approach and our streaming algorithm includes implementing offline algorithm to construct the merge-and seerge-and-reducee coresets. In the offline algorithm, we sample each edge e with probability p Te. where re is its effective resistance. Due to the equivalence between the effective resistance and the leverage score of the incidence matrix, we have Eeeo Te = n, and so the expected number of sampled edges is pn. Thus, we set = 1/n such that we sample 1 edges in expectation, and the actual number of samples only varies little due to the concentration. Then, we use the same parameter P for the offline algorithm in the second approach and our streaming algorithm ensure fair comparison. In our streaming algorithm, recall that we run an online algorithm to obtain the prefix substream S' (which is not stored), we tune the length of S' to have the optimal error bound. We explicitly list our choice of parameters below.
We adapt the code for efficiently estimating the effective resistances in the experiments of Chen et al. (2024). In the online algorithm, we do batch implementation to save time. We partition the stream into batches with 100 edges and use the same Lt(t) to compute the effective resistances for a batch, so we do not have to re-construct the Laplacian within a batch.
Experimental parameters. We provide the choices of the hyperparameters of our experiments. We use C.., Cat, and Cotair to denote the constant factors of the online algorithm, the offline algorithm that constructs the coresets, and the prefix online substream in our streaming algorithm, respectively. The values of them are shown in Table 1.
We also include the (amortized) run-time of our algorithm in Table 2, showing that our algorithm is time-efficient in practice.
Results and discussion. In the first experiment, we fix the number of vertices and edges in the graph and compare the performance under different budgets L. For the synthetic graph, we set 100, m 50000, and & e (500, 1000, 1500, 2000, 2500, 3000). For the Facebook graph, set I E (10000, 15000, 20000, 25000]. The results are displayed in Figure 5.
For both graphs, the merge-and-reduce methods obtain 0.3 multiplicative error using < 50% budget, and our streaming algorithm (blue line) has the lowest multiplicative eтror under various budgets. This occurs because our algorithm applies the merge-and-reduce method to the online
'The code is available at https: /ttp:///ttttt/// com / eShenghaol s/graph_sparas fication_
i 1c1r_200 2_226.
39

---

Published as a conference paper at ICLR 2026
Synthetic Graph (n
100, m 50000)
Budget
500
1000
1500
2000
2500
3000
Cal
0.001
0.01
0.15
0.35
0.55
0.75
Coff
1.1
2.2
3.3
4.4
5.5
6.6
CoLstr
2.0
2.5
5.5
8.0
11.5
15.0
Facebook Graph (n 1034, m 53498)
Budget
10000
15000
20000
25000
Cot
0.145
0.35
Coff
1.333
2.333
3.333
4.5
Col.str 1.0
1.8
5.5
Comparison under Different m, Synthetic Graph (n
100, Budget=15000
m
10000
20000
30000
40000
50000
60000
70000
80000
90000
100000
Cal
0.3
0.08
0.05
0.04
0.02
0,005
0.002
Cott
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
3.3
CoLar
15.0
7.0
5.5
4.8
4.3
4.05
3.75
3,75
3.7
3.2
Table 1: Constant factors (Col, Cott, CoLSu) for the three experiments.
Note
n
m
Budget
Batched online
Merge-and-reduce
Our algorithm
Synthetic graph
50
2500
750
2.0 x 10
2.9 10 10-4s 2
4.9 x 10 g
Synthetic graph
100
10000
2500
6.1 10
3.0 10
5.6 10-4
Synthetic graph
200
40000
10000
7.6 X 10
4.7 x 10-1
6.1 x 10-1
Facebook graph
1034
53498
15000
4.0 x 10 2
2.3 10 2
9.6 x 10
Table 2: Comparison of running times in different experiments.
Comparison rison Methods
100, 50000)
our 2ky- the
mer.ggetther
meipe, 415 ars_redice pedice
3.0
(util Lookie
Huspiiatte Srow
231CE
0.7
0.8
3.6
0.5
0.4
0.
0.
35000
Budgst
Fig. 5: Comparison under different budgets. The x-axis shows the space budget and the y-axis shows the multiplicative error. The left is the synthetic graph and the right is the Facebook graph. We include the result of the online algorithm as a baseline.
substream S', resulting in shorter tree height compared directly applying merge-and-reduce to the original stream. Since errors accumulate at each tree level, our algorithm generally outperforms others. However, its advantage diminishes as the budget increases. This is because with large budgets, we set large coreset sizes; and so the heights of the two methods are roughly the same, reducing the advantage our algorithm. In addition, at extremely low budgets (e.g., / 500 the synthetic graph), our algorithm performs similarly to the merge-and and-r-uuu- algorithm. This implies a trade-off between the accuracy of the online substream and the tree height, when the budget is extremely low compared n. If set small budget for S', the accuracy of the prefix online
40

---

Published as a conference paper at ICLR 2026
algorithm is suboptimal; on the contrary, if a large budget for S', then it increases the tree height. Both situations hinder the performance of our algorithm.
Comparisan of Mathods in 100, Budget 1500)
algorithm morge_and, mrrdgce reduce
0.30
Medhupccetvve trree
0.49
0.40
0.33
20000
20000
30030
4000C
00000 Number of Edges (m))
50000
70000
80000
90000
300000
Fig. 6: Comparison under different numbers of edges
In the second experiment, we fix the budget and compare the performance under different numbers of edges m. We use the synthetic graph; and we set 100, 1500, and m E (i. 10000, E [10]]- The results are displayed in Figure 6, showing that our algorithm generally outperforms the merge- and-reduce method as vn increases. This advantage because we set our budget as = 1500, which is substantial compared to enabling the prefix online substream S' to have a high-quality approximation while maintaining a small tree height. Consequently, this enhances our algorithm's performance. In summary, experiments demonstrate the optimality of our streaming algorithm under dense graphs and limited budgets, matching the theoretical guarantecs.
41


Reviews:
[{"review_id": "2BPUmg7Th1", "reviewer": "Reviewer_wsKb", "summary": "This work proposes an improved algorithm for both cut and spectral sparsification of hypergraphs in the insertion-only data stream model. In particular, they remove the $\\log m$ factors that can grow up to $n$ for hypergraphs of arbitrarily high rank. They achieve this by proposing an online weight assignment following the strategy of Jambulapati et al. (2023), and improve the computational cost of the sampling process by leveraging the online row sampling idea of Cohen et al. 2020. They also employ their techniques to obtain better bounds (in terms of number of edges stored, or overall space complexity) for other settings, such as online, sliding window model, and for robust hypergraph sparsification. They also demonstrate the performance of their algorithm through empirical evaluations.", "questions": "1. What are the technical challenges and novel approaches involved in the work? Possibly provide a technical overview.\n\n2. The sliding window model result (Theorem 1.6) seems to have higher space complexity than the streaming model, which is a weaker model. Am I missing something here?\n\nRemark/Typos:\n\n3. Fix the “additive $\\log n$ factor” to “additional (multiplicative) $\\log n$ factor”\n\n4. It seems the reference in Line 119 should be Khanna et al. 2025a.", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "The paper improves the bound for the insertion-only streaming model by a multiplicative factor that can grow up to $n$, the number of vertices. \n\nThey also propose better bounds for several other models, including resolving an open question of Soma et al. (2024) in the online hypergraph case.", "weaknesses": "The paper is structured poorly and difficult to read. The main results are not presented clearly. The comparison with other works (Appendix A, Fig. 3) should have been presented in the main paper. \n\nThe absence of a technical overview or a clear presentation of the main technical challenges and proposed solutions makes it difficult to comprehend the core ideas of the paper.\n\nThe comparison with Khanna et al. 2025a seems a bit unfair, given that their algorithm is for the dynamic setting, although this has been addressed in the concurrent and independent work section.\n\nThe improvements demonstrated in the experimental section, even in the limited resources setting, do not seem significant. Although this is not a major issue, given the theoretical nature of the work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SUgRotbcpX", "reviewer": "Reviewer_Tgfe", "summary": "The paper considers the problem of graph and hypergraph sparsification in a streaming setting. The input is a (hyper)graph where the edges arrive online in a stream, and the goal of the algorithm is to maintain a spectral sparsifier of the graph with few edges. For graph sparsification, they obtain an algorithm that gives an $(1+\\varepsilon)$ sparsifier with high probability in $n$ storing only $n/\\varepsilon^2\\cdot poly(\\log\\log(n))$ edges with $poly(n)$ update time (Theorem 1.1). This improves by several logarithmic factors over what one can obtain using algorithms for  offline spectral sparsification combined with the merge-and-reduce framework and is in fact optimal within $\\log\\log n$ factors. Additionally, they provide an algorithm for streaming min-cut which stores $n/\\varepsilon\\cdot poly(\\log(n),1/\\varepsilon)$ edges and returns a $(1+\\varepsilon)$ approximation to the min-cut improving by a $\\log n$ factor on previous work. I don't know how impressive this improvement is, since it's not quite clear to me on page 2, how big a polynomial dependence on $\\log n$ past work (Ding et al., 2024) incurred. \n\nNext, the paper considers algorithms for hypergraph sparsification. The number of edges needed to store in past work had factors of either $\\log m$, where $m$ is the number of edges, or $r$, where $r$ is the rank of the hypergraph. Both of these are unpleasant, since $m$ could be exponential in $n$ and $r$ could be as large as $n$. In contrast, the present paper provides a streaming algorithm that only stores $n/\\varepsilon^2 poly(\\log n,\\log r\\log\\log m)$, removing these unpleasant dependencies. \nThe paper provides a related algorithm in the online setting where edges have to be either included or not irrevocably upon arrival.\n\nFinally, the paper provides related results in the setting where the edge arrivals are adversarial and can be based on past decisions of the algorithm, and results in the well-motivated sliding window model, where the algorithm only cares about maintaining a sparsifier of the graph defined by the edge arrivals in a past window of time in the past, and all updates that occurred before the window, should be disregarded.\n\nThe techniques seem to be quite sophisticated modifications of past work that aim to sample edges according to effective resistances in the final graph (which turns out to be the right thing to do when constructing spectral sparsifiers). I am quite unfamiliar with these techniques and got quite lost in the matrix algebra, so while the paper seems to be mathematically precisely written, I can't vouch for correctness.", "questions": "What is the update time of your algorithm? I'm aware that it's $poly(n)$, but do you have a bound on the degree of the polynomial? Do previous works also have polynomial update time?\n\nIs it always the case that you can construct a spectral sparsifier by sampling edges, or do you also need to reweight them? I was a little unsure about this, and it might be useful to the reader to discuss this.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Spectral sparsification of graphs and hypergraphs are important problems from both a theoretical and practical perspective and studying these problems in streaming and online settings seem quite natural. It is impressive that the paper gets improved algorithms for so many of these problems. Especially Theorem  1.1 (nearly tight bounds) and 1.3 (removing dependencies on $\\log m$ and $r$) seem nice. The paper provides experiments that demonstrate that a version of their algorithm performs quite favorably in on real and synthetic data sets.", "weaknesses": "The paper might be difficult to read as the techniques are quite technical. It was somewhat difficult for me to assess the novelty of the ideas due to this technical opacity. It is however quite possible that people stronger in linear algebra and spectral methods find it more understandable.\n\nAnother weakness is that the polynomial update time in $n$ might be a little disappointing, but I don't think this is a big issue.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kTQBbc0XXd", "reviewer": "Reviewer_2k1R", "summary": "The paper shows that in insertion-only streams one can build $(1\\pm\\varepsilon)$ spectral sparsifiers at essentially offline sample complexity: for graphs it stores $\\tilde O(n/\\varepsilon^{2})$ edges with $\\mathrm{poly}(n)$ update time, and for hypergraphs it stores $O\\big(n/\\varepsilon^{2}\\cdot \\log n\\cdot \\mathrm{poly}(\\log r,\\log\\log m)\\big)$ hyperedges; it also gives a $(1\\pm\\varepsilon)$ min-cut estimator using $O\\big(n/\\varepsilon\\cdot \\mathrm{polylog}(n,1/\\varepsilon)\\big)$ space. The key idea is an online, for-all sparsification scheme combined with merge-and-reduce coresets, and the framework extends to sliding-window and adversarially robust settings.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The problem is important, and the paper delivers near–space-optimal $(1\\pm\\varepsilon)$ sparsification in insertion-only streams for graphs and hypergraphs, shaving prior $\\log n$ factors and extending to min-cut, adversarially robust, and sliding-window settings—useful breadth for streaming theory and practice.", "weaknesses": "The problem is important, but the results feel incremental—they mainly tighten log factors and integrate known techniques, with the novelty lying more in careful refinement and synthesis than in new methods. Experiments are light: few/small datasets, no hypergraph or min-cut evaluations, no sliding-window/adversarial tests, limited comparisons, and few metrics ( no throughput or memory-per-update reporting).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)