PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts

• URL: http://arxiv.org/abs/2101.07152v1
• Date: Mon, 18 Jan 2021 16:35:12 GMT
• Title: PRESTO: Simple and Scalable Sampling Techniques for the Rigorous Approximation of Temporal Motif Counts
• Authors: Ilie Sarpe, Fabio Vandin
• Abstract summary: 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.
• Score: 7.025709586759655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The identification and counting of small graph patterns, called network motifs, is a fundamental primitive in the analysis of networks, with application in various domains, from social networks to neuroscience. Several techniques have been designed to count the occurrences of motifs in static networks, with recent work focusing on the computational challenges provided by large networks. Modern networked datasets contain rich information, such as the time at which the events modeled by the networks edges happened, which can provide useful insights into the process modeled by the network. The analysis of motifs in temporal networks, called temporal motifs, is becoming an important component in the analysis of modern networked datasets. Several methods have been recently designed to count the number of instances of temporal motifs in temporal networks, which is even more challenging than its counterpart for static networks. Such methods are either exact, and not applicable to large networks, or approximate, but provide only weak guarantees on the estimates they produce and do not scale to very large networks. In this work 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. Our extensive experimental evaluation shows that our algorithm provides estimates of temporal motif counts which are more accurate than the state-of-the-art sampling algorithms, with significantly lower running time than exact approaches, enabling the study of temporal motifs, of size larger than the ones considered in previous works, on billion edges networks.

Related papers

• State-Space Modeling in Long Sequence Processing: A Survey on Recurrence in the Transformer Era [59.279784235147254]
  This survey provides an in-depth summary of the latest approaches that are based on recurrent models for sequential data processing. The emerging picture suggests that there is room for thinking of novel routes, constituted by learning algorithms which depart from the standard Backpropagation Through Time.
  arXiv  Detail & Related papers  (2024-06-13T12:51:22Z)
• How neural networks learn to classify chaotic time series [77.34726150561087]
  We study the inner workings of neural networks trained to classify regular-versus-chaotic time series. We find that the relation between input periodicity and activation periodicity is key for the performance of LKCNN models.
  arXiv  Detail & Related papers  (2023-06-04T08:53:27Z)
• Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs [51.51417735550026]
  Methods for machine learning on temporal networks generally exhibit at least one of two limitations. We present a simple method that avoids both shortcomings: construct the line graph of the network, which includes a node for each interaction, and weigh the edges of this graph based on the difference in time between interactions. Empirical results on real-world networks demonstrate our method's efficacy and efficiency on both edge classification and temporal link prediction.
  arXiv  Detail & Related papers  (2022-09-30T18:24:13Z)
• Graph-Survival: A Survival Analysis Framework for Machine Learning on Temporal Networks [14.430635608400982]
  We propose a framework for designing generative models for continuous time temporal networks. We propose a fitting method for models within this framework, and an algorithm for simulating new temporal networks having desired properties.
  arXiv  Detail & Related papers  (2022-03-14T16:40:57Z)
• Temporal Graph Network Embedding with Causal Anonymous Walks Representations [54.05212871508062]
  We propose a novel approach for dynamic network representation learning based on Temporal Graph Network. For evaluation, we provide a benchmark pipeline for the evaluation of temporal network embeddings. We show the applicability and superior performance of our model in the real-world downstream graph machine learning task provided by one of the top European banks.
  arXiv  Detail & Related papers  (2021-08-19T15:39:52Z)
• 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)
• Frequent Pattern Mining in Continuous-time Temporal Networks [0.0]
  We develop a series of algorithms for mining the complete set of frequent temporal patterns in a temporal network data set. Implementing the algorithm for three real-world data sets proves the practicality of the proposed algorithm.
  arXiv  Detail & Related papers  (2021-05-12T02:47:24Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• TempNodeEmb:Temporal Node Embedding considering temporal edge influence matrix [0.8941624592392746]
  Predicting future links among the nodes in temporal networks reveals an important aspect of the evolution of temporal networks. Some approaches consider a simplified representation of temporal networks but in high-dimensional and generally sparse matrices. We propose a new node embedding technique which exploits the evolving nature of the networks considering a simple three-layer graph neural network at each time step.
  arXiv  Detail & Related papers  (2020-08-16T15:39:07Z)
• 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)
• ESPN: Extremely Sparse Pruned Networks [50.436905934791035]
  We show that a simple iterative mask discovery method can achieve state-of-the-art compression of very deep networks. Our algorithm represents a hybrid approach between single shot network pruning methods and Lottery-Ticket type approaches.
  arXiv  Detail & Related papers  (2020-06-28T23:09:27Z)

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.