Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Efficient Approximate Temporal Triangle Counting in Streaming with Predictions

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read STEP is a single-pass streaming algorithm that estimates all eight temporal triangle counts at once; with a good predictor it is unbiased, sublinear-memory, and epsilon-accurate even when predictions are noisy.

desk verdict Genuinely new streaming estimator for all eight temporal triangle counts with an unbiased guarantee, but the practical predictor's future-looking definition breaks the advertised single-pass claim. read the letter →

arxiv 2506.13173 v1 pith:R2ZTQGSI submitted 2025-06-16 cs.DS cs.LGcs.SI

Giorgio Venturin , Ilie Sarpe , Fabio Vandin This is my paper · ORCID
classification cs.DScs.LGcs.SI
keywords temporalgraphstrianglecountingstreamingalgorithmswithpredictionsunbiasedestimationsublinearmemoryrandomizedsamplingmotifs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

STEP is a one-pass streaming algorithm that estimates how often each of the eight temporal triangle patterns occurs in a temporal graph, using a small sample of edges guided by a predictor of which edges matter. The paper claims that the estimates are unbiased no matter how good or bad the predictor is, and that a good predictor shrinks the variance so much that a relative-$\varepsilon$ approximation can be achieved with sublinear memory. The analysis shows the gain is governed by $\rho_K$, the true triangle weight of the first edge the predictor fails to keep: if triangle occurrences are concentrated on the predicted top-$K$ edges, the variance drops from a bound involving $|\mathcal{T}_i|^2$ to one involving $|\mathcal{T}_i|$. Experiments on graphs up to 3.3 billion edges report mean absolute errors mostly below 0.1, with large memory and time savings over exact and streaming approximate methods.

What carries the argument

The mechanism is inverse-probability reweighting over wedges, where a wedge is a pair of edges sharing a vertex. STEP keeps two stores: heavy edges $H$ (predicted by the predictor $Q(\cdot)$ to participate in many triangles) and light edges $S_L$, each kept with probability $p$. When an edge $e$ arrives, STEP enumerates the wedges it closes with stored edges, partitions them by whether the wedge's two earlier stream edges are both heavy, one heavy and one light, or both light, and updates counters $c_{i,0}$, $c_{i,1}$, $c_{i,2}$. The final estimate $c_i = c_{i,0}/p^2 + c_{i,1}/p + c_{i,2}$ is unbiased because a triangle whose first two stream edges are both light is retained with probability $p^2$, one light and one heavy with probability $p$, and both heavy with probability $1$. The variance reduction comes from the ranking predictor: with the top-$K$ edges classified heavy, the heaviest light edge has weight $\rho_K$, and this quantity enters the variance bound linearly.

What would settle it

Construct a temporal graph where triangle occurrences are spread evenly across edges, so the top-$K$ edges capture only a tiny share of the mass, and where each true count $|\mathcal{T}_i|$ is small; run STEP with a sampling probability $p$ of 0.01, as in the experiments, and compare many repeated estimates to exact counts from enumeration. If more than one run in three has relative error above the target $\varepsilon$ for any of the eight types, the claimed concentration guarantee fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that STEP solves the temporal triangle estimation problem in a single pass over a time-ordered stream: for every triangle type $\mathcal{T}_i$, $i \in [8]$, it outputs $c_i$ with $\mathbb{E}[c_i] = |\mathcal{T}_i|$, and this unbiasedness holds regardless of the predictor's quality. With a ranking predictor that correctly identifies the top-$K$ edges by total triangle participation, Theorem 1 gives a relative-$\varepsilon$ approximation with error probability at most $1/3$ using $O(\varepsilon^{-1} m_\delta^{3/2}/|\mathcal{T}_i|^{1/2-\gamma})$ expected memory, provided the sampling probability satisfies $p \ge C\sqrt{m_\delta}/(\varepsilon |\mathcal{T}_i|^{1/2-\gamma})$; Corollary 1 bounds the variance by $C p^{-2} \rho_K m_\delta |\mathcal{T}_i|$. An $\alpha$-noisy ranking predictor multiplies this variance bound by a factor $\sqrt{\nabla_\alpha}$, so even imperfect rankings help as long as the top and bottom of the ranking are roughly right. The practical temporal min-degree predictor ranks edges by the minimum temporal degree of their endpoints within $[t-\delta, t+\delta]$, and the experiments show it keeps mean absolute error mostly under 0.1 on graphs with up to 3.3 billion edges.

Load-bearing premise

The accuracy and memory guarantees depend on the true triangle counts being large and on most triangle occurrences involving the top-$K$ edges the predictor keeps; neither the true counts nor the heaviest light edge's weight is known while the stream runs, so the guaranteed operating regime is not verified in the experiments.

Editorial extensions

If this is right

  • If the concentration guarantee holds, STEP is the first single-pass streaming algorithm with sublinear memory and a relative-$\varepsilon$ approximation for all eight temporal triangle types simultaneously, on streams too large for exact methods.
  • A perfect ranking predictor gives a variance bound of order $p^{-2} \rho_K m_\delta |\mathcal{T}_i|$ instead of the $p^{-2} m_\delta |\mathcal{T}_i|^2$ bound of naive sampling, so the more triangle mass concentrates on the predicted top-$K$ edges, the closer the estimate is to ideal accuracy.
  • With an $\alpha$-noisy predictor, the variance bound is multiplied by $\sqrt{\nabla_\alpha}$, formalizing the paper's claim that even noisy predictions significantly reduce variance.
  • On the experimental side, the paper claims STEP is the only tested method that completes on the 3.3-billion-edge EquinixChicago graph, using under 65 GB of memory and under ten minutes while keeping average MAE below 0.1.
  • The online variant learns a threshold from the first 75% of the stream and applies it to the remaining 25%, and the paper reports it still often beats the predictor-free sampler on real datasets.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The theorem's threshold for the sampling probability depends on $|\mathcal{T}_i|$, $\rho_K$, and $m_\delta$, none of which is known while the stream runs; a deployment would need a data-dependent or adaptive choice of $p$, and the paper does not supply one, so the experiments' $p=0.01$ is an unverified operating point rather than a verified regime.
  • The temporal min-degree predictor as defined uses the future-closed window $[t-\delta, t+\delta]$, so a strict one-pass implementation cannot evaluate it at time $t$ without buffering edges or delaying the heavy/light decision; making the predictor causal (past-only window) would change the ranking and likely the variance bound.
  • The same reweighting scheme could be applied to other temporal motifs, such as butterflies or other 3-edge patterns, since the unbiasedness argument only needs a partition of the first-two-edges cases.
  • The accuracy-versus-$K$ curves reported in the appendix suggest an adaptive controller that increases $K$ until the estimated counts stabilize, turning the offline choice of $K$ into a runtime stopping rule.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces STEP, a single-pass streaming algorithm for simultaneously approximating all eight temporal triangle counts. STEP uses a predictor Q to classify edges as heavy (retained deterministically) or light (retained with probability p), collects wedges from the retained heavy and sampled-light edges, and reweights counters for triangles whose first two edges are heavy/light combinations. The paper proves an unbiasedness lemma (Lemma 1), a concentration/sublinear-memory theorem under a ranking predictor (Theorem 1), a variance reduction corollary (Corollary 1), and a noisy-predictor variant (Theorem 2). It also designs a practical temporal min-degree predictor and reports experiments on graphs up to 3.3 billion edges, claiming large memory and runtime savings over exact and approximate baselines.

Significance. If the claims hold, this would be a substantial contribution: a streaming algorithm with predictions that estimates all temporal triangle types simultaneously, with a clean parameter-free unbiasedness result for abstract predictors, and experiments demonstrating scalability on a graph where exact baselines run out of memory. The paper ships code, compares against several state-of-the-art methods, and includes ablations for its predictor. The unbiasedness proof for the abstract STEP mechanism is elegant and independent of predictor quality, and the empirical MAE values on the largest datasets are impressive. However, two load-bearing gaps currently block the central claim: the practical temporal min-degree predictor is not implementable in the advertised single-pass sublinear streaming model without violating the unbiasedness mechanism, and the theoretical sublinear-memory guarantee is parameterized by unobservable ground-truth quantities whose hypotheses are never checked in the experiments.

major comments (3)
  1. [Section 3.4 and Algorithm 1, with Section 4.3 footnote] The temporal min-degree predictor defined in Section 3.4 uses w_{m-d}(e) = min{d(u,t-delta,t+delta), d(v,t-delta,t+delta)}, which requires the future interval (t, t+delta]. Algorithm 1 classifies edge e at Line 9 when it arrives, so in a genuine single pass the future edges are not available. The footnote in Section 4.3 says the predictor evaluates whether e is retained at time t+delta. That deferral breaks the proof of Lemma 1: a delta-instance whose third edge arrives between t and t+delta has e as one of its first two edges, but e is not yet in H or S_L when the later edges are processed, so the wedge is never collected and the instance is missed. The only fixes are buffering all in-window edges for delta time (Theta(m_delta) memory, not sublinear) or making a second pass, both contradicting the single-pass sublinear claim. The experimental section does not state which fix was used, so the advertised combination of single-pass streaming, sublinear memory, and unbiased estimates for STEP_TMD is unsupported.
  2. [Section 3.3, Theorem 1 and Corollary 1] The 'sublinear memory with rigorous concentration guarantees' claim is not operational. Theorem 1 requires p >= C sqrt(m_delta)/(epsilon |T_i|^{1/2-gamma}), a threshold that depends on the unknown |T_i|, and the memory bound O(epsilon^{-1} m_delta^{3/2}/|T_i|^{1/2-gamma}) is sublinear only under the event E that |T_i|^{1/2-gamma} is sufficiently large relative to sqrt(m_delta)/epsilon. Corollary 1's variance bound contains rho_K, the ground-truth weight of the (K+1)-th edge, also unknown at runtime. The experiments fix p = 0.01 (or 0.1) and K = m/100 without ever checking these thresholds; moreover K = m/100 is not guaranteed to be o(m_delta) as required by the theorem. Thus the tested configurations do not instantiate the theorem's hypotheses, and the paper should either provide a data-dependent rule for setting p and K or explicitly state the guarantee as conditional on unobservable quantities.
  3. [Section 3.3 and Section 4.2] The perfect predictor STEP_P is built from the exact ground-truth weights W(e), which are exactly the quantities the algorithm is supposed to estimate. The paper explicitly labels this predictor impractical and uses it as a lower bound, which is acceptable as an ablation, but the sentence in Section 4.2 that the perfect predictor 'provides a lower bound on the error' should not be read as evidence for the practical guarantee in Theorem 1. The theoretical results should be framed more carefully: they show what happens conditionally on having access to the target weights, not how to obtain such access efficiently.
minor comments (4)
  1. [Appendix B, Lemma 2] Please check the displayed identity: as typeset it appears to be missing the leading factor alpha on the summation, even though the proof text appears to count that factor. The theorem survives, but the display should match the proof.
  2. [Section 4.3, footnote] The footnote stating that the predictor evaluates whether e is retained at time t+delta should be moved into the algorithm description and reconciled with the streaming model; currently it directly contradicts the single-pass claim asserted in Section 3.4.
  3. [Algorithm 1, Line 5] The notation '∨H,H', '∨H,SL', and '∨SL,SL' for wedge sets is nonstandard and is not defined in the table of notation; please define it in the caption or in Table 4.
  4. [Section 4.1, Table 3] The text says STEP_TMD 'consistently outperforms' the baselines in runtime, but on BI with delta = 259200 EWS is faster; the sentence should be qualified to match the table.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: STEP's estimator re-weights sampled edges with standard inverse-probability factors, and the perfect predictor is an explicitly impractical oracle, not the fitted output.

full rationale

Score 0. STEP's central derivation is self-contained: Lemma 1 (Appendix B) proves unbiasedness by partitioning each T_i according to the predictor's labels on the first two stream edges and re-weighting by p^{-2}, p^{-1}, and 1; no step identifies the estimate with the predictor's input. The 'perfect predictor' of Section 3.3 is explicitly impractical and is used only as an experimental lower bound; it outputs top-K membership by aggregate weight W(e), not the type-specific counts |T_i|, so the estimates are not read off the oracle. The temporal min-degree predictor (Section 3.4) uses node temporal degrees, not triangle counts, and the online evaluation (Section 4.3) uses a genuine train/test split on the first 75% of edges, so it is not a fitted input renamed as a prediction. Two limitations are real but are not circularity: Theorem 1's sampling probability p is required to satisfy p >= C sqrt(m_delta)/(epsilon |T_i|^{1/2-gamma}) and Corollary 1's variance bound uses the unknown rho_K, so the sublinear-memory guarantee is non-constructive (one cannot set p from the answer); and Section 4.3's footnote that the min-degree predictor 'evaluates if e should be retained or not at time t+delta' conflicts with the single-pass execution of Algorithm 1, a streaming-model correctness issue. These should be addressed as rigor and experimental concerns, not as equivalence of input and output. The citation to Boldrin and Vandin 2024 (a co-author's prior work) is contextual and contrastive, not load-bearing.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The ledger is small because STEP introduces no new physical or mathematical entities; it rests instead on four data-dependent assumptions about the input (count comparability across the eight types, concentration of triangle mass on a few heavy edges, the size of |T_i| relative to m_delta, and exact-count computability for the largest dataset) plus one implementation premise (future-window availability for the predictor). The three fitted values are the sampling probability p, the heavy-edge budget K, and the online threshold phi; all three are declared in the paper, but none of the theory's thresholds are verified to hold for the chosen values.

free parameters (3)
  • sampling probability p = 0.1 (SO), 0.01 (BI, RE, EC)
    Chosen per dataset (Appendix E, Table 5). STEP's memory-accuracy trade-off depends on p, but the theorem's required threshold p >= C sqrt(m_delta)/(epsilon |T_i|^{1/2-gamma}) is not verified for the chosen values.
  • heavy-edge budget K = m/100 (1% of edges)
    Hand-selected budget for the predictor's heavy set; the sensitivity analysis in Appendix E shows a MAE-versus-runtime trade-off across K/m from 0.01 to 0.10, so the choice is not derived from the theory.
  • online threshold phi = K-th temporal min-degree weight on the training stream
    Learned from the first 75% of edges (Section 4.3) and used to classify heavy edges on the test stream; it is a fitted value from historical data, though not fitted to the target triangle counts.
assumptions (5)
  • domain assumption All eight triangle counts are comparable: there exists 'an arbitrary large constant C for which |T_i| = C. |T_j|, i, j in [8]', used inside Theorem 1's proof as |T_hat| = C_1 |T_i|.
    Section 3.3 states this before Theorem 1, and the proof of Theorem 1 (Appendix B) uses |T_hat|/|T_i|^2 = C_1/|T_i| to derive the sampling threshold; the paper adds 'this is often the case in practice' and defers better bounds to future work. If counts across the eight types differ by orders of magnitude, the per-type epsilon-approximation guarantee weakens.
  • domain assumption The heaviest-edge ranking W concentrates the triangle mass: rho_K = W(e_{prec K+1}), the ground-truth weight of the (K+1)-th ranked edge, is small, and 'rho_K in practice is generally rho_K = |T_i|^{gamma prime}, gamma prime much less than 1'.
    Corollary 1's variance improvement factor |T_i|/rho_K and Theorem 1's sublinear memory bound both collapse when rho_K is large; the gamma-prime statement is asserted without proof or empirical check. This is the load-bearing premise that predictions help at all.
  • domain assumption The concentration event E ('the triangle count |T_i|^{1/2-gamma} is sufficiently large, for all eight triangle types') holds in the experimental regime.
    Theorem 1's sublinear-memory conclusion is conditional on E. The paper's fallback, that if E fails 'the counts |T_i| are small enough so they can be obtained with high accuracy using the set H', is asserted without derivation: small counts need not be concentrated on predictable heavy edges.
  • domain assumption Exact counts |T_i| for the MAE ground truth are obtainable by 'a naive enumeration algorithm' on all four datasets, including the 3.3-billion-edge EC graph where every exact baseline ran out of memory (Table 2).
    Section 4 (Metrics and parameters) states this without describing the implementation, time, or memory used for EC; without it, the reported EC MAE values cannot be audited.
  • ad hoc to paper The temporal min-degree weight w_{m-d}(e) = min{d(u,t-delta,t+delta), d(v,t-delta,t+delta)} can be evaluated inside a single-pass streaming model.
    Section 3.4 defines the predictor over the future-closed window [t-delta, t+delta], yet Algorithm 1 classifies each edge at its arrival (Line 9). Appendix H computes the predictor on the whole input graph, confirming lookahead; a faithful streaming implementation must buffer edges for delta time before classification, which is not described. This weakens the single-pass framing.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Efficient Approximate Temporal Triangle Counting in Streaming with Predictions." pith.science (2026). https://pith.science/paper/R2ZTQGSI

@misc{pith2026250613173,
  author       = {Pith},
  title        = {Pith review of: Efficient Approximate Temporal Triangle Counting in Streaming with Predictions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R2ZTQGSI}},
  note         = {Machine review of arXiv:2506.13173}
}
read the original abstract

Triangle counting is a fundamental and widely studied problem on static graphs, and recently on temporal graphs, where edges carry information on the timings of the associated events. Streaming processing and resource efficiency are crucial requirements for counting triangles in modern massive temporal graphs, with millions of nodes and up to billions of temporal edges. However, current exact and approximate algorithms are unable to handle large-scale temporal graphs. To fill such a gap, we introduce STEP, a scalable and efficient algorithm to approximate temporal triangle counts from a stream of temporal edges. STEP combines predictions to the number of triangles a temporal edge is involved in, with a simple sampling strategy, leading to scalability, efficiency, and accurate approximation of all eight temporal triangle types simultaneously. We analytically prove that, by using a sublinear amount of memory, STEP obtains unbiased and very accurate estimates. In fact, even noisy predictions can significantly reduce the variance of STEP's estimates. Our extensive experiments on massive temporal graphs with up to billions of edges demonstrate that STEP outputs high-quality estimates and is more efficient than state-of-the-art methods.

Figures

Figures reproduced from arXiv: 2506.13173 by the authors.

Figure 1
Figure 1. (𝑎): temporal graph 𝐺 = (𝑉 , 𝐸), with 𝑉 = {𝑣1, . . . , 𝑣5} and temporal edges 𝐸 = {(𝑣2, 𝑣3, 1), . . . }: each temporal edge is a triplet (𝑢, 𝑣, 𝑡) with 𝑡 being the time of occurrence. (𝑏): stream over time of the temporal edges of 𝐺. (𝑐): the sequence 𝑆 = ⟨(𝑣2, 𝑣3), (𝑣3, 𝑣4), (𝑣4, 𝑣2)⟩ is a 𝛿-instance of temporal triangle 𝑇4 (𝛿 = 20). (𝑑): all distinct temporal triangles and the number of their 𝛿-instances in 𝐺 (𝛿 =… view at source ↗
Figure 2
Figure 2. MAE and standard deviation for STEP, NAIVE-S and EWS on SO, BI and RE datasets from [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. MAE and standard deviation for STEP, NAIVE-S and EWS on EC dataset from [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (9 more)
Figure 4
Figure 4. Figure 4: MAE and standard deviation for online estimation on the stream [PITH_FULL_IMAGE:figures/full_fig_p017_4.png]
Figure 5
Figure 5. Figure 5: MAE and standard deviation for STEP (with different predictors) and NAIVE-S on the RE dataset, for the largest values of 𝛿 considered and for each temporal triangle (see [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: Left: MAE obtained by STEPTMD averaged over the eight type of triangles (see [PITH_FULL_IMAGE:figures/full_fig_p036_6.png]
Figure 7
Figure 7. Figure 7: MAE and standard deviation of STEP and baseline algorithms (NAIVE-S and EWS) on SO and BI datasets from [PITH_FULL_IMAGE:figures/full_fig_p038_7.png]
Figure 8
Figure 8. Figure 8: MAE and standard deviation of STEP and baseline algorithms (NAIVE-S and EWS) on RE and EC dataset from [PITH_FULL_IMAGE:figures/full_fig_p039_8.png]
Figure 9
Figure 9. Figure 9: MAE and standard deviation for online estimation on the stream [PITH_FULL_IMAGE:figures/full_fig_p040_9.png]
Figure 10
Figure 10. Figure 10: MAE and standard deviation for online estimation on the stream [PITH_FULL_IMAGE:figures/full_fig_p041_10.png]
Figure 11
Figure 11. Figure 11: Correlation between perfect predictor and temporal min-degree predictor on all [PITH_FULL_IMAGE:figures/full_fig_p042_11.png]
Figure 12
Figure 12. Figure 12: Left: Jaccard similarity between the set [PITH_FULL_IMAGE:figures/full_fig_p043_12.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Triadic First-Order Logic Queries in Temporal Networks

    cs.DB 2025-07 conditional novelty 7.0 of 10

    FOLTY is the first algorithm for thresholded FOL triadic motif queries on temporal networks, with O(m α log σ_max) running time matching the best temporal triangle counters.

Reference graph

Works this paper leans on

62 extracted references · 44 canonical work pages · cited by 1 Pith paper

  1. [1]

    Aamand, J

    A. Aamand, J. Y. Chen, H. L. Nguyen, S. Silwal, and A. Vakilian. Improved frequency estimation algorithms with and without predictions, 2023

    work page 2023

  2. [2]

    Antoniadis, H

    A. Antoniadis, H. Broersma, and Y. Meng. Online graph coloring with predictions. In International Symposium on Combinatorial Optimization, pages 289--302. Springer, 2024

    work page 2024

  3. [3]

    Y. Azar, D. Panigrahi, and N. Touitou. Online graph algorithms with predictions. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 35--66. SIAM, 2022

    work page 2022

  4. [4]

    Banerjee, V

    S. Banerjee, V. Cohen-Addad, A. Gupta, and Z. Li. Graph searching with predictions. arXiv preprint arXiv:2212.14220, 2022

    arXiv 2022

  5. [5]

    Belth, X

    C. Belth, X. Zheng, and D. Koutra. Mining persistent activity in continually evolving networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20. ACM, Aug. 2020. doi:10.1145/3394486.3403136

    arXiv 2020

  6. [6]

    Bernardini, A

    G. Bernardini, A. Lindermayr, A. Marchetti-Spaccamela, N. Megow, L. Stougie, and M. Sweering. A universal error measure for input predictions applied to online graph problems. Advances in Neural Information Processing Systems, 35: 0 3178--3190, 2022

    work page 2022

  7. [7]

    Fast and Accurate Triangle Counting in Graph Streams Using Predictions

    C. Boldrin and F. Vandin. Fast and accurate triangle counting in graph streams using predictions. arXiv preprint arXiv:2409.15205, 2024

    work page Pith review arXiv 2024

  8. [8]

    Boucheron, G

    S. Boucheron, G. Lugosi, and O. Bousquet. Concentration Inequalities, pages 208--240. Springer Berlin Heidelberg, 2004. ISBN 9783540286509. doi:10.1007/978-3-540-28650-9_9

    work page doi:10.1007/978-3-540-28650-9_9 2004

Show all 62 references
  1. [9]

    J. v. d. Brand, S. Forster, Y. Nazari, and A. Polak. On dynamic graph algorithms with predictions. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3534--3557. SIAM, 2024

    2024

  2. [10]

    J. Chen, S. Silwal, A. Vakilian, and F. Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583--3602. PMLR, 2022 a

    2022

  3. [11]

    J. Y. Chen, T. Eden, P. Indyk, H. Lin, S. Narayanan, R. Rubinfeld, S. Silwal, T. Wagner, D. P. Woodruff, and M. Zhang. Triangle and four cycle counting with predictions in graph streams. arXiv preprint arXiv:2203.09572, 2022 b

    2022 arXiv

  4. [12]

    Davies, B

    S. Davies, B. Moseley, S. Vassilvitskii, and Y. Wang. Predictive flows for faster ford-fulkerson, 2023

    2023

  5. [13]

    Debrouvier, E

    A. Debrouvier, E. Parodi, M. Perazzo, V. Soliani, and A. Vaisman. A model and query language for temporal graph databases. The VLDB Journal, 30 0 (5): 0 825--858, May 2021. ISSN 0949-877X. doi:10.1007/s00778-021-00675-4

    2021 doi

  6. [14]

    A. F. DePavia, E. Tani, and A. Vakilian. Learning-based algorithms for graph searching problems. In International Conference on Artificial Intelligence and Statistics, pages 928--936. PMLR, 2024

    2024

  7. [15]

    J. C. Ergun, Z. Feng, S. Silwal, D. P. Woodruff, and S. Zhou. Learning-augmented k -means clustering, 2021

    2021

  8. [16]

    Ferragina and G

    P. Ferragina and G. Vinciguerra. The pgm-index: a fully-dynamic compressed learned index with provable worst-case bounds. Proceedings of the VLDB Endowment, 13 0 (8): 0 1162--1175, Apr. 2020. ISSN 2150-8097. doi:10.14778/3389133.3389135

    2020

  9. [17]

    C. Gao, Y. Zheng, N. Li, Y. Li, Y. Qin, J. Piao, Y. Quan, J. Chang, D. Jin, X. He, and Y. Li. A survey of graph neural networks for recommender systems: Challenges, methods, and directions. ACM Transactions on Recommender Systems, 1 0 (1): 0 1--51, Mar. 2023. ISSN 2770-6699. d...

    2023 doi

  10. [18]

    Z. Gao, C. Cheng, Y. Yu, L. Cao, C. Huang, and J. Dong. Scalable motif counting for large-scale temporal graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE), pages 2656--2668. IEEE, 2022

    2022

  11. [19]

    Gionis, L

    A. Gionis, L. Oettershagen, and I. Sarpe. Mining temporal networks. In Companion Proceedings of the ACM on Web Conference 2024, WWW '24. ACM, May 2024. doi:10.1145/3589335.3641245

    2024

  12. [20]

    Heeg and I

    F. Heeg and I. Scholtes. Using causality-aware graph neural networks to predict temporal centralities in dynamic graphs, 2023

    2023

  13. [21]

    Henzinger, A

    M. Henzinger, A. Lincoln, B. Saha, M. P. Seybold, and C. Ye. On the complexity of algorithms with predictions for dynamic graph problems. arXiv preprint arXiv:2307.16771, 2023

    2023 arXiv

  14. [22]

    Hessel, C

    J. Hessel, C. Tan, and L. Lee. Science, AskScience, and BadScience: On the Coexistence of Highly Related Communities . In Proceedings of the Tenth International AAAI Conference on Web and Social Media, pages 171--180, 2016

    2016

  15. [23]

    Holme and J

    P. Holme and J. Saram \"a ki. Temporal networks. Physics Reports, 519 0 (3): 0 97--125, Oct. 2012. ISSN 0370-1573. doi:10.1016/j.physrep.2012.03.001

    2012 doi

  16. [24]

    Holme and J

    P. Holme and J. Saram \"a ki. Temporal Network Theory. Springer International Publishing, 2023. ISBN 9783031303999. doi:10.1007/978-3-031-30399-9

    2023 doi

  17. [26]

    X. Hu, S. Sintos, J. Gao, P. K. Agarwal, and J. Yang. Computing complex temporal join queries efficiently. In Proceedings of the 2022 International Conference on Management of Data, SIGMOD/PODS '22. ACM, June 2022. doi:10.1145/3514221.3517893

    2022

  18. [27]

    Hulovatyy, H

    Y. Hulovatyy, H. Chen, and T. Milenkovi \'c . Exploring the structure and function of temporal networks with dynamic graphlets. Bioinformatics, 31 0 (12): 0 i171--i180, June 2015. ISSN 1367-4803. doi:10.1093/bioinformatics/btv227

    2015 doi

  19. [28]

    S. H. C. Jiang, E. Liu, Y. Lyu, Z. G. Tang, and Y. Zhang. Online facility location with predictions, 2021

    2021

  20. [29]

    Kondor, I

    D. Kondor, I. Csabai, J. Sz \"u le, M. P \'o sfai, and G. Vattay. Inferring the interplay between network structure and market effects in bitcoin. New Journal of Physics, 16 0 (12): 0 125003, 2014

    2014

  21. [30]

    Kumar and T

    R. Kumar and T. Calders. 2scent: An efficient algorithm to enumerate all simple temporal cycles. Proceedings of the VLDB Endowment, 11 0 (11): 0 1441--1453, 2018

    2018

  22. [31]

    Lattanzi, S

    S. Lattanzi, S. Ola, and V. Sergei. Speeding up bellman ford via minimum violation permutations. Proceedings of the 40th International Conference on Machine Learning, 2023

    2023

  23. [32]

    D. Lei, X. Chen, L. Cheng, L. Zhang, S. V. Ukkusuri, and F. Witlox. Inferring temporal motifs for travel pattern analysis using large scale smart card data. Transportation Research Part C: Emerging Technologies, 120: 0 102810, Nov. 2020. ISSN 0968-090X. doi:10.1016/j.trc.2020.102810

    2020

  24. [33]

    J. Li, J. Qi, Y. Huang, L. Cao, Y. Yu, and J. Dong. Motto: Scalable motif counting with time-aware topology constraint for large-scale temporal graphs. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 1195--1204, 2024

    2024

  25. [34]

    L. Lin, P. Yuan, R.-H. Li, C. Zhu, H. Qin, H. Jin, and T. Jia. Qtcs: Efficient query-centered temporal community search. Proceedings of the VLDB Endowment, 17 0 (6): 0 1187--1199, Feb. 2024. ISSN 2150-8097. doi:10.14778/3648160.3648163

    2024

  26. [35]

    J. Liu, J. Chen, J. Wu, Z. Wu, J. Fang, and Z. Zheng. Fishing for fraudsters: Uncovering ethereum phishing gangs with blockchain data. IEEE Transactions on Information Forensics and Security, 19: 0 3038--3050, 2024. ISSN 1556-6021. doi:10.1109/tifs.2024.3359000

    2024

  27. [36]

    P. Liu, A. R. Benson, and M. Charikar. Sampling methods for counting temporal motifs. In Proceedings of the twelfth ACM international conference on web search and data mining, pages 294--302, 2019

    2019

  28. [37]

    P. Liu, V. Guarrasi, and A. E. Sariyuce. Temporal network motifs: Models, limitations, evaluation. IEEE Transactions on Knowledge and Data Engineering, pages 1--1, 2021. ISSN 2326-3865. doi:10.1109/tkde.2021.3077495

    2021

  29. [38]

    Mackey, K

    P. Mackey, K. Porterfield, E. Fitzhenry, S. Choudhury, and G. Chin. A chronological edge-driven approach to temporal subgraph isomorphism. In 2018 IEEE International Conference on Big Data (Big Data). IEEE, Dec. 2018. doi:10.1109/bigdata.2018.8622100

    2018

  30. [39]

    Q. Mang, J. Chen, H. Zhou, Y. Gao, Y. Zhou, R. Peng, Y. Fang, and C. Ma. Efficient historical butterfly counting in large temporal bipartite networks via graph structure-aware index. arXiv preprint arXiv:2406.00344, 2024

    2024 arXiv

  31. [40]

    D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM), 30 0 (3): 0 417--427, 1983

    1983

  32. [41]

    McGregor

    A. McGregor. Graph stream algorithms: a survey. ACM SIGMOD Record, 43 0 (1): 0 9--20, 2014

    2014

  33. [42]

    Mitzenmacher

    M. Mitzenmacher. A model for learned bloom filters, and optimizing by sandwiching, 2019

    2019

  34. [43]

    Mitzenmacher and S

    M. Mitzenmacher and S. Vassilvitskii. Algorithms with predictions. Communications of the ACM, 65 0 (7): 0 33--35, 2022

    2022

  35. [44]

    Muthukrishnan et al

    S. Muthukrishnan et al. Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science , 1 0 (2): 0 117--236, 2005

    2005

  36. [45]

    Y. Pan, O. Bhalerao, C. Seshadhri, and N. Talati. Accurate and fast estimation of temporal motifs using path sampling. arXiv preprint arXiv:2409.08975, 2024

    2024

  37. [46]

    Paranjape, A

    A. Paranjape, A. R. Benson, and J. Leskovec. Motifs in temporal networks. In Proceedings of the tenth ACM international conference on web search and data mining, pages 601--610, 2017

    2017

  38. [47]

    Pashanasangi and C

    N. Pashanasangi and C. Seshadhri. Faster and generalized temporal triangle counting, via degeneracy ordering. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1319--1328, 2021

    2021

  39. [48]

    Porter, B

    A. Porter, B. Mirzasoleiman, and J. Leskovec. Analytical models for motifs in temporal networks. In Companion Proceedings of the Web Conference 2022, WWW '22. ACM, Apr. 2022. doi:10.1145/3487553.3524669

    2022

  40. [49]

    J. Pu, Y. Wang, Y. Li, and X. Zhou. Sampling algorithms for butterfly counting on temporal bipartite graphs, 2023

    2023

  41. [50]

    Qin, R.-H

    H. Qin, R.-H. Li, Y. Yuan, G. Wang, L. Qin, and Z. Zhang. Mining bursting core in large temporal graphs. Proceedings of the VLDB Endowment, 15 0 (13): 0 3911--3923, Sept. 2022. ISSN 2150-8097. doi:10.14778/3565838.3565845

    2022

  42. [51]

    Sarpe and F

    I. Sarpe and F. Vandin. Oden: simultaneous approximation of multiple motif counts in large temporal networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1568--1577, 2021 a

    2021

  43. [52]

    Sarpe and F

    I. Sarpe and F. Vandin. Presto: Simple and scalable sampling techniques for the rigorous approximation of temporal motif counts. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pages 145--153. SIAM, 2021 b

    2021

  44. [53]

    Sarpe, F

    I. Sarpe, F. Vandin, and A. Gionis. Scalable temporal motif densest subnetwork discovery. In Proceedings of the 30th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '24, 2024

    2024

  45. [54]

    Seshadhri and S

    C. Seshadhri and S. Tirthapura. Scalable subgraph counting: The methods behind the madness. In Companion Proceedings of The 2019 World Wide Web Conference, WWW '19. ACM, May 2019. doi:10.1145/3308560.3320092

    2019

  46. [55]

    J. Tang, M. Musolesi, C. Mascolo, and V. Latora. Temporal distance metrics for social network analysis. In Proceedings of the 2nd ACM workshop on Online social networks, SIGCOMM '09. ACM, Aug. 2009. doi:10.1145/1592665.1592674

    2009

  47. [56]

    K. Tu, J. Li, D. Towsley, D. Braines, and L. D. Turner. gl2vec: learning feature representation using graphlets for directed networks. In Proceedings of the 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, ASONAM '19. ACM, Aug. 2019. d...

    2019

  48. [57]

    J. Wang, Y. Wang, W. Jiang, Y. Li, and K.-L. Tan. Efficient sampling algorithms for approximate motif counting in temporal graph streams. arXiv preprint arXiv:2211.12101, 2022

    2022 arXiv

  49. [58]

    P. Wang, Y. Qi, Y. Sun, X. Zhang, J. Tao, and X. Guan. Approximately counting triangles in large graph streams including edge duplicates with a fixed memory usage. Proceedings of the VLDB Endowment, 11 0 (2): 0 162--175, 2017

    2017

  50. [59]

    H. Wu, J. Cheng, S. Huang, Y. Ke, Y. Lu, and Y. Xu. Path problems in temporal graphs. Proceedings of the VLDB Endowment, 7 0 (9): 0 721--732, May 2014. ISSN 2150-8097. doi:10.14778/2732939.2732945

    2014

  51. [60]

    J. Wu, J. Liu, W. Chen, H. Huang, Z. Zheng, and Y. Zhang. Detecting mixing services via mining bitcoin transaction network with hybrid motifs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 52 0 (4): 0 2237--2249, Apr. 2022. ISSN 2168-2232. doi:10.1109/tsmc.2021.3049278

    2022

  52. [61]

    J. Yu, H. Yin, J. Li, Q. Wang, N. Q. V. Hung, and X. Zhang. Self-supervised multi-channel hypergraph convolutional network for social recommendation. In Proceedings of the Web Conference 2021, WWW '21. ACM, Apr. 2021. doi:10.1145/3442381.3449844

    2021

  53. [62]

    Zhang, J

    T. Zhang, J. Fang, Z. Yang, B. Cao, and J. Fan. Tatkc: A temporal graph neural network for fast approximate temporal katz centrality ranking. In Proceedings of the ACM on Web Conference 2024, WWW '24. ACM, May 2024. doi:10.1145/3589334.3645432

    2024

  54. [63]

    J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: A review of methods and applications. AI Open, 1: 0 57--81, 2020. ISSN 2666-6510. doi:10.1016/j.aiopen.2021.01.001

    2020 doi

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.