Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis

• URL: http://arxiv.org/abs/2208.01365v1
• Date: Tue, 2 Aug 2022 11:16:58 GMT
• Title: Concentration inequalities for correlated network-valued processes with applications to community estimation and changepoint analysis
• Authors: Sayak Chatterjee, Shirshendu Chatterjee, Soumendu Sundar Mukherjee, Anirban Nath, Sharmodeep Bhattacharyya
• Abstract summary: We study the aggregate behavior of network sequences generated from network-valued processes. We demonstrate the usefulness of these concentration results in proving consistency of standard estimators in community estimation and changepoint estimation problems. We also conduct a simulation study to demonstrate the effect of the laziness parameter, which controls the extent of temporal correlation, on the accuracy of community and changepoint estimation.
• Score: 2.1953732467962315
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Network-valued time series are currently a common form of network data. However, the study of the aggregate behavior of network sequences generated from network-valued stochastic processes is relatively rare. Most of the existing research focuses on the simple setup where the networks are independent (or conditionally independent) across time, and all edges are updated synchronously at each time step. In this paper, we study the concentration properties of the aggregated adjacency matrix and the corresponding Laplacian matrix associated with network sequences generated from lazy network-valued stochastic processes, where edges update asynchronously, and each edge follows a lazy stochastic process for its updates independent of the other edges. We demonstrate the usefulness of these concentration results in proving consistency of standard estimators in community estimation and changepoint estimation problems. We also conduct a simulation study to demonstrate the effect of the laziness parameter, which controls the extent of temporal correlation, on the accuracy of community and changepoint estimation.

Related papers

• Inferring Dynamic Networks from Marginals with Iterative Proportional Fitting [60.915127259986306]
  A common network inference problem, arising from real-world data constraints, is how to infer a dynamic network from its time-aggregated adjacency matrix. We introduce a principled algorithm that guarantees IPF converges under minimal changes to the network structure.
  arXiv  Detail & Related papers  (2024-02-28T20:24:56Z)
• Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis [2.615648035076649]
  We propose a novel deep graph clustering framework with temporal consistency regularization on inter-community structures. MFC is a matrix factorization-based deep graph clustering algorithm that preserves node embedding. TopoReg is introduced to ensure the preservation of topological similarity between inter-community structures over time intervals.
  arXiv  Detail & Related papers  (2024-01-06T11:29:19Z)
• Distributed Continual Learning with CoCoA in High-dimensional Linear Regression [0.0]
  We consider estimation under scenarios where the signals of interest exhibit change of characteristics over time. In particular, we consider the continual learning problem where different tasks, e.g., data with different distributions, arrive sequentially. We consider the well-established distributed learning algorithm COCOA, which distributes the model parameters and the corresponding features over the network.
  arXiv  Detail & Related papers  (2023-12-04T10:35:46Z)
• Time-series Generation by Contrastive Imitation [87.51882102248395]
  We study a generative framework that seeks to combine the strengths of both: Motivated by a moment-matching objective to mitigate compounding error, we optimize a local (but forward-looking) transition policy. At inference, the learned policy serves as the generator for iterative sampling, and the learned energy serves as a trajectory-level measure for evaluating sample quality.
  arXiv  Detail & Related papers  (2023-11-02T16:45:25Z)
• Leveraging Low-Rank and Sparse Recurrent Connectivity for Robust Closed-Loop Control [63.310780486820796]
  We show how a parameterization of recurrent connectivity influences robustness in closed-loop settings. We find that closed-form continuous-time neural networks (CfCs) with fewer parameters can outperform their full-rank, fully-connected counterparts.
  arXiv  Detail & Related papers  (2023-10-05T21:44:18Z)
• Robust Detection of Lead-Lag Relationships in Lagged Multi-Factor Models [61.10851158749843]
  Key insights can be obtained by discovering lead-lag relationships inherent in the data. We develop a clustering-driven methodology for robust detection of lead-lag relationships in lagged multi-factor models.
  arXiv  Detail & Related papers  (2023-05-11T10:30:35Z)
• Efficient Estimation for Longitudinal Networks via Adaptive Merging [21.62069959992736]
  We propose an efficient estimation framework for longitudinal network, leveraging strengths of adaptive network merging, tensor decomposition and point process. It merges neighboring sparse networks so as to enlarge the number of observed edges and reduce estimation variance. A projected descent algorithm is proposed to facilitate estimation, where upper bound of the estimation error in each iteration is established.
  arXiv  Detail & Related papers  (2022-11-15T03:17:11Z)
• 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)
• Decentralized Local Stochastic Extra-Gradient for Variational Inequalities [125.62877849447729]
  We consider distributed variational inequalities (VIs) on domains with the problem data that is heterogeneous (non-IID) and distributed across many devices. We make a very general assumption on the computational network that covers the settings of fully decentralized calculations. We theoretically analyze its convergence rate in the strongly-monotone, monotone, and non-monotone settings.
  arXiv  Detail & Related papers  (2021-06-15T17:45:51Z)
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks [4.238478445823]
  Spectral inference on multiple networks is a rapidly-developing subfield of graph statistics. Recent work has demonstrated that joint, or simultaneous, spectral embedding of multiple independent networks can deliver more accurate estimation. We present a generalized omnibus embedding methodology and provide a detailed analysis of this embedding across both independent and correlated networks.
  arXiv  Detail & Related papers  (2020-08-01T03:43:52Z)
• Robust Learning Through Cross-Task Consistency [92.42534246652062]
  We propose a broadly applicable and fully computational method for augmenting learning with Cross-Task Consistency. We observe that learning with cross-task consistency leads to more accurate predictions and better generalization to out-of-distribution inputs.
  arXiv  Detail & Related papers  (2020-06-07T09:24:33Z)

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.