Efficient Approximate Temporal Triangle Counting in Streaming with Predictions

• URL: http://arxiv.org/abs/2506.13173v1
• Date: Mon, 16 Jun 2025 07:34:54 GMT
• Title: Efficient Approximate Temporal Triangle Counting in Streaming with Predictions
• Authors: Giorgio Venturin, Ilie Sarpe, Fabio Vandin,
• Abstract summary: We introduce STEP, a scalable and efficient algorithm to approximate temporal triangle counts from a stream of temporal edges.<n> STEP combines predictions to the number of triangles a temporal edge is involved in, with a simple sampling strategy.<n>We analytically prove that, by using a sublinear amount of memory, STEP obtains unbiased and very accurate estimates.
• Score: 3.9623532668625576
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• Fast and Accurate Triangle Counting in Graph Streams Using Predictions [4.000869978312742]
  We present the first efficient and practical algorithm for estimating the number of triangles in a graph stream using predictions. Our algorithm combines waiting room sampling and reservoir sampling with a predictor for the heaviness of edges, that is, the number of triangles in which an edge is involved.
  arXiv  Detail & Related papers  (2024-09-23T16:52:11Z)
• Accurate and Fast Estimation of Temporal Motifs using Path Sampling [5.114632024458956]
  Counting the number of small subgraphs, called motifs, is a fundamental problem in social network analysis and graph mining. We propose an algorithm, TEACUPS, that addresses this problem using a novel technique of temporal path sampling. For a Bitcoin graph with hundreds of millions of edges, TEACUPS runs in less than 1 minute, while the exact counting algorithm takes more than a day.
  arXiv  Detail & Related papers  (2024-09-13T16:48:39Z)
• Learning Temporal Distances: Contrastive Successor Features Can Provide a Metric Structure for Decision-Making [66.27188304203217]
  Temporal distances lie at the heart of many algorithms for planning, control, and reinforcement learning.<n>Prior attempts to define such temporal distances in settings have been stymied by an important limitation.<n>We show how successor features learned by contrastive learning form a temporal distance that does satisfy the triangle inequality.
  arXiv  Detail & Related papers  (2024-06-24T19:36:45Z)
• TriDet: Temporal Action Detection with Relative Boundary Modeling [85.49834276225484]
  Existing methods often suffer from imprecise boundary predictions due to ambiguous action boundaries in videos. We propose a novel Trident-head to model the action boundary via an estimated relative probability distribution around the boundary. TriDet achieves state-of-the-art performance on three challenging benchmarks.
  arXiv  Detail & Related papers  (2023-03-13T17:59:59Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Correlating sparse sensing for large-scale traffic speed estimation: A Laplacian-enhanced low-rank tensor kriging approach [76.45949280328838]
  We propose a Laplacian enhanced low-rank tensor (LETC) framework featuring both lowrankness and multi-temporal correlations for large-scale traffic speed kriging. We then design an efficient solution algorithm via several effective numeric techniques to scale up the proposed model to network-wide kriging.
  arXiv  Detail & Related papers  (2022-10-21T07:25:57Z)
• Scalable Motif Counting for Large-scale Temporal Graphs [25.90869257290865]
  We propose a scalable parallel framework for exactly counting temporal motifs in large-scale temporal graphs. Based on the proposed counting algorithms, we design a hierarchical parallel framework that features both inter- and intra-node parallel strategies. Experiments on sixteen real-world temporal graph datasets demonstrate the superiority and capability of our proposed framework.
  arXiv  Detail & Related papers  (2022-04-20T05:41:38Z)
• Triangle and Four Cycle Counting with Predictions in Graph Streams [59.05440236993604]
  We propose data-driven one-pass streaming algorithms for estimating the number of triangles and four cycles. We use a trained oracle that can predict certain properties of the stream elements to improve on prior "classical" algorithms. Our methodology expands upon prior work on "classical" streaming algorithms, as previous multi-pass and random order streaming algorithms can be seen as special cases.
  arXiv  Detail & Related papers  (2022-03-17T19:26:00Z)
• Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data [0.0]
  Streaming framework is analogous to solving optimization problems using time-varying mini-batches that arrive sequentially. We provide non-asymptotic convergence rates of various gradient-based algorithms. We show how to accelerate convergence by choosing the learning rate according to the time-varying mini-batches.
  arXiv  Detail & Related papers  (2021-09-15T06:58:23Z)
• Spatio-Temporal Graph Scattering Transform [54.52797775999124]
  Graph neural networks may be impractical in some real-world scenarios due to a lack of sufficient high-quality training data. We put forth a novel mathematically designed framework to analyze-temporal data.
  arXiv  Detail & Related papers  (2020-12-06T19:49:55Z)
• Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version) [24.33313864327473]
  We propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. We also devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. Our algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.
  arXiv  Detail & Related papers  (2020-07-28T07:15:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.