Community recovery in non-binary and temporal stochastic block models

• URL: http://arxiv.org/abs/2008.04790v5
• Date: Tue, 30 Aug 2022 09:15:32 GMT
• Title: Community recovery in non-binary and temporal stochastic block models
• Authors: Konstantin Avrachenkov, Maximilien Dreveton, Lasse Leskel\"a
• Abstract summary: This article studies the estimation of latent community memberships from pairwise interactions in a network of $N$ nodes. We introduce a block model with a general measurable interaction space $mathcal S$, for which we derive information-theoretic bounds for the minimum achievable error rate. We also present fast online estimation algorithms which fully utilise the non-binary nature of the observed data.
• Score: 0.17188280334580194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article studies the estimation of latent community memberships from pairwise interactions in a network of $N$ nodes, where the observed interactions can be of arbitrary type, including binary, categorical, and vector-valued, and not excluding even more general objects such as time series or spatial point patterns. As a generative model for such data, we introduce a stochastic block model with a general measurable interaction space $\mathcal S$, for which we derive information-theoretic bounds for the minimum achievable error rate. These bounds yield sharp criteria for the existence of consistent and strongly consistent estimators in terms of data sparsity, statistical similarity between intra- and inter-block interaction distributions, and the shape and size of the interaction space. The general framework makes it possible to study temporal and multiplex networks with $\mathcal S = \{0,1\}^T$, in settings where both $N \to \infty$ and $T \to \infty$, and the temporal interaction patterns are correlated over time. For temporal Markov interactions, we derive sharp consistency thresholds. We also present fast online estimation algorithms which fully utilise the non-binary nature of the observed data. Numerical experiments on synthetic and real data show that these algorithms rapidly produce accurate estimates even for very sparse data arrays.

Related papers

• Generalization error of min-norm interpolators in transfer learning [2.7309692684728617]
  Min-norm interpolators emerge naturally as implicit regularized limits of modern machine learning algorithms. In many applications, a limited amount of test data may be available during training, yet properties of min-norm in this setting are not well-understood. We establish a novel anisotropic local law to achieve these characterizations.
  arXiv  Detail & Related papers  (2024-06-20T02:23:28Z)
• Graph-based Forecasting with Missing Data through Spatiotemporal Downsampling [24.368893944128086]
  Stemporal graph neural networks achieve striking results by representing relationships across time series as a graph. Most existing methods rely on the often unrealistic assumption that inputs are always available and fail to capture hidden dynamics when part of the data is missing.
  arXiv  Detail & Related papers  (2024-02-16T12:33:31Z)
• Online Algorithm for Node Feature Forecasting in Temporal Graphs [12.667148739430798]
  In this paper, we propose an online mspace for forecasting node features in temporal graphs. We show that mspace performs at par with the state-of-the-art and even surpasses them on some datasets. We also propose a technique to generate synthetic datasets to aid in evaluating node feature forecasting methods.
  arXiv  Detail & Related papers  (2024-01-30T07:31:51Z)
• Correlation-aware Spatial-Temporal Graph Learning for Multivariate Time-series Anomaly Detection [67.60791405198063]
  We propose a correlation-aware spatial-temporal graph learning (termed CST-GL) for time series anomaly detection. CST-GL explicitly captures the pairwise correlations via a multivariate time series correlation learning module. A novel anomaly scoring component is further integrated into CST-GL to estimate the degree of an anomaly in a purely unsupervised manner.
  arXiv  Detail & Related papers  (2023-07-17T11:04:27Z)
• 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)
• Continuous time recurrent neural networks: overview and application to forecasting blood glucose in the intensive care unit [56.801856519460465]
  Continuous time autoregressive recurrent neural networks (CTRNNs) are a deep learning model that account for irregular observations. We demonstrate the application of these models to probabilistic forecasting of blood glucose in a critical care setting.
  arXiv  Detail & Related papers  (2023-04-14T09:39:06Z)
• 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)
• Interpretable Additive Recurrent Neural Networks For Multivariate Clinical Time Series [4.125698836261585]
  We present the Interpretable-RNN (I-RNN) that balances model complexity and accuracy by forcing the relationship between variables in the model to be additive. I-RNN specifically captures the unique characteristics of clinical time series, which are unevenly sampled in time, asynchronously acquired, and have missing data. We evaluate the I-RNN model on the Physionet 2012 Challenge dataset to predict in-hospital mortality, and on a real-world clinical decision support task: predicting hemodynamic interventions in the intensive care unit.
  arXiv  Detail & Related papers  (2021-09-15T22:30:19Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• OR-Net: Pointwise Relational Inference for Data Completion under Partial Observation [51.083573770706636]
  This work uses relational inference to fill in the incomplete data. We propose Omni-Relational Network (OR-Net) to model the pointwise relativity in two aspects.
  arXiv  Detail & Related papers  (2021-05-02T06:05:54Z)
• Learning interaction kernels in stochastic systems of interacting particles from multiple trajectories [13.3638879601361]
  We consider systems of interacting particles or agents, with dynamics determined by an interaction kernel. We introduce a nonparametric inference approach to this inverse problem, based on a regularized maximum likelihood estimator. We show that a coercivity condition enables us to control the condition number of this problem and prove the consistency of our estimator.
  arXiv  Detail & Related papers  (2020-07-30T01:28:06Z)

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.