Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)

• URL: http://arxiv.org/abs/2007.14028v1
• Date: Tue, 28 Jul 2020 07:15:25 GMT
• Title: Efficient Sampling Algorithms for Approximate Temporal Motif Counting (Extended Version)
• Authors: Jingjing Wang and Yanhao Wang and Wenjun Jiang and Yuchen Li and Kian-Lee Tan
• Abstract summary: 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.
• Score: 24.33313864327473
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: A great variety of complex systems ranging from user interactions in communication networks to transactions in financial markets can be modeled as temporal graphs, which consist of a set of vertices and a series of timestamped and directed edges. Temporal motifs in temporal graphs are generalized from subgraph patterns in static graphs which take into account edge orderings and durations in addition to structures. Counting the number of occurrences of temporal motifs is a fundamental problem for temporal network analysis. However, existing methods either cannot support temporal motifs or suffer from performance issues. In this paper, we focus on approximate temporal motif counting via random sampling. We first propose a generic edge sampling (ES) algorithm for estimating the number of instances of any temporal motif. Furthermore, we devise an improved EWS algorithm that hybridizes edge sampling with wedge sampling for counting temporal motifs with 3 vertices and 3 edges. We provide comprehensive analyses of the theoretical bounds and complexities of our proposed algorithms. Finally, we conduct extensive experiments on several real-world datasets, and the results show that our ES and EWS algorithms have higher efficiency, better accuracy, and greater scalability than the state-of-the-art sampling method for temporal motif counting.

Related papers

• Temporal Aggregation and Propagation Graph Neural Networks for Dynamic Representation [67.26422477327179]
  Temporal graphs exhibit dynamic interactions between nodes over continuous time. We propose a novel method of temporal graph convolution with the whole neighborhood. Our proposed TAP-GNN outperforms existing temporal graph methods by a large margin in terms of both predictive performance and online inference latency.
  arXiv  Detail & Related papers  (2023-04-15T08:17:18Z)
• Scalable Spatiotemporal Graph Neural Networks [14.415967477487692]
  Graph neural networks (GNNs) are often the core component of the forecasting architecture. In most pretemporal GNNs, the computational complexity scales up to a quadratic factor with the length of the sequence times the number of links in the graph. We propose a scalable architecture that exploits an efficient encoding of both temporal and spatial dynamics.
  arXiv  Detail & Related papers  (2022-09-14T09:47:38Z)
• 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)
• Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs [65.18780403244178]
  We propose a continuous model to forecast Multivariate Time series with dynamic Graph neural Ordinary Differential Equations (MTGODE) Specifically, we first abstract multivariate time series into dynamic graphs with time-evolving node features and unknown graph structures. Then, we design and solve a neural ODE to complement missing graph topologies and unify both spatial and temporal message passing.
  arXiv  Detail & Related papers  (2022-02-17T02:17:31Z)
• Cluster-and-Conquer: A Framework For Time-Series Forecasting [94.63501563413725]
  We propose a three-stage framework for forecasting high-dimensional time-series data. Our framework is highly general, allowing for any time-series forecasting and clustering method to be used in each step. When instantiated with simple linear autoregressive models, we are able to achieve state-of-the-art results on several benchmark datasets.
  arXiv  Detail & Related papers  (2021-10-26T20:41:19Z)
• Novel Features for Time Series Analysis: A Complex Networks Approach [62.997667081978825]
  Time series data are ubiquitous in several domains as climate, economics and health care. Recent conceptual approach relies on time series mapping to complex networks. Network analysis can be used to characterize different types of time series.
  arXiv  Detail & Related papers  (2021-10-11T13:46:28Z)
• odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks [7.025709586759655]
  One of the main complications in studying temporal motifs is the large number of motifs that can be built. We propose odeN, a sampling-based algorithm that provides an accurate approximation of all the counts of the motifs.
  arXiv  Detail & Related papers  (2021-08-19T15:06:05Z)
• Pattern Sampling for Shapelet-based Time Series Classification [4.94950858749529]
  Subsequence-based time series classification algorithms provide accurate and interpretable models. These algorithms are based on exhaustive search for highly discriminative subsequences. Pattern sampling has been proposed as an effective alternative to mitigate the pattern explosion phenomenon.
  arXiv  Detail & Related papers  (2021-02-16T23:35:10Z)
• PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts [7.025709586759655]
  We present an efficient and scalable algorithm to obtain rigorous approximations of the count of temporal motifs. Our algorithm is based on a simple but effective sampling approach, which renders our algorithm practical for very large datasets.
  arXiv  Detail & Related papers  (2021-01-18T16:35:12Z)
• Multi-Temporal Convolutions for Human Action Recognition in Videos [83.43682368129072]
  We present a novel temporal-temporal convolution block that is capable of extracting at multiple resolutions. The proposed blocks are lightweight and can be integrated into any 3D-CNN architecture.
  arXiv  Detail & Related papers  (2020-11-08T10:40:26Z)
• From Static to Dynamic Node Embeddings [61.58641072424504]
  We introduce a general framework for leveraging graph stream data for temporal prediction-based applications. Our proposed framework includes novel methods for learning an appropriate graph time-series representation. We find that the top-3 temporal models are always those that leverage the new $epsilon$-graph time-series representation.
  arXiv  Detail & Related papers  (2020-09-21T16:48:29Z)

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.