odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks

• URL: http://arxiv.org/abs/2108.08734v1
• Date: Thu, 19 Aug 2021 15:06:05 GMT
• Title: odeN: Simultaneous Approximation of Multiple Motif Counts in Large Temporal Networks
• Authors: Ilie Sarpe and Fabio Vandin
• Abstract summary: 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.
• Score: 7.025709586759655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Counting the number of occurrences of small connected subgraphs, called temporal motifs, has become a fundamental primitive for the analysis of temporal networks, whose edges are annotated with the time of the event they represent. One of the main complications in studying temporal motifs is the large number of motifs that can be built even with a limited number of vertices or edges. As a consequence, since in many applications motifs are employed for exploratory analyses, the user needs to iteratively select and analyze several motifs that represent different aspects of the network, resulting in an inefficient, time-consuming process. This problem is exacerbated in large networks, where the analysis of even a single motif is computationally demanding. As a solution, in this work we propose and study the problem of simultaneously counting the number of occurrences of multiple temporal motifs, all corresponding to the same (static) topology (e.g., a triangle). Given that for large temporal networks computing the exact counts is unfeasible, we propose odeN, a sampling-based algorithm that provides an accurate approximation of all the counts of the motifs. We provide analytical bounds on the number of samples required by odeN to compute rigorous, probabilistic, relative approximations. Our extensive experimental evaluation shows that odeN enables the approximation of the counts of motifs in temporal networks in a fraction of the time needed by state-of-the-art methods, and that it also reports more accurate approximations than such methods.

Related papers

• Scalable network reconstruction in subquadratic time [0.0]
  We present a general algorithm applicable to a broad range of reconstruction problems that significantly outperforms this quadratic baseline. Our algorithm relies on a second neighbor search that produces the best edge candidates with high probability. We show that our algorithm achieves a performance that is many orders of magnitude faster than the quadratic baseline.
  arXiv  Detail & Related papers  (2024-01-02T19:00:13Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  We discuss the problem of bounding partially identifiable queries, such as counterfactuals, in Pearlian structural causal models. A recently proposed iterated EM scheme yields an inner approximation of those bounds by sampling the initialisation parameters. We show how a single symbolic knowledge compilation allows us to obtain the circuit structure with symbolic parameters to be replaced by their actual values.
  arXiv  Detail & Related papers  (2023-10-05T07:10:40Z)
• 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)
• 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)
• Temporal and Object Quantification Networks [95.64650820186706]
  We present a new class of neuro-symbolic networks with a structural bias that enables them to learn to recognize complex relational-temporal events. We demonstrate that TOQ-Nets can generalize from small amounts of data to scenarios containing more objects than were present during training and to temporal warpings of input sequences.
  arXiv  Detail & Related papers  (2021-06-10T16:18:21Z)
• 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)
• Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
  We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
  arXiv  Detail & Related papers  (2021-05-06T08:48:02Z)
• A Survey of Quantization Methods for Efficient Neural Network Inference [75.55159744950859]
  quantization is the problem of distributing continuous real-valued numbers over a fixed discrete set of numbers to minimize the number of bits required. It has come to the forefront in recent years due to the remarkable performance of Neural Network models in computer vision, natural language processing, and related areas. Moving from floating-point representations to low-precision fixed integer values represented in four bits or less holds the potential to reduce the memory footprint and latency by a factor of 16x.
  arXiv  Detail & Related papers  (2021-03-25T06:57:11Z)
• 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)
• 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)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
  arXiv  Detail & Related papers  (2020-02-06T19:56:15Z)

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.