Graphical model for tensor factorization by sparse sampling

• URL: http://arxiv.org/abs/2510.17886v1
• Date: Sat, 18 Oct 2025 06:06:21 GMT
• Title: Graphical model for tensor factorization by sparse sampling
• Abstract summary: We consider tensor factorizations based on sparse measurements of the tensor components.<n>We build message-passing algorithms and test them in a Bayes optimal teacher-student setting.
• Score: 0.695942427153803
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider tensor factorizations based on sparse measurements of the tensor components. The measurements are designed in a way that the underlying graph of interactions is a random graph. The setup will be useful in cases where a substantial amount of data is missing, as in recommendation systems heavily used in social network services. In order to obtain theoretical insights on the setup, we consider statistical inference of the tensor factorization in a high dimensional limit, which we call as dense limit, where the graphs are large and dense but not fully connected. We build message-passing algorithms and test them in a Bayes optimal teacher-student setting. We also develop a replica theory, which becomes exact in the dense limit,to examine the performance of statistical inference.

Related papers

• Parameterised graph theory for tensor networks: entanglement rerouting, structural simplification, and agnostic tomography [0.6117371161379209]
  We show that graph parameters determine whether a tensor-network state (TNS) admits a tractable matrix product state (MPS) or tree tensor network (TTN) representation, and which control the complexity of learning the state?<n>We derive graph-dependent upper bounds on the sample and computational complexity of realisable TNS tomography, with exponents that depend on cutwidth, tree-cutwidth, and a new graph parameter, learning complexity, which we bound in terms of degree and treewidth.
  arXiv  Detail & Related papers  (2026-09-03T17:50:38Z)
• Consistent spectral clustering in sparse tensor block models [0.0]
  High-order clustering aims to classify objects in multiway datasets that are prevalent in various fields.<n>This paper introduces a tensor block model specifically designed for sparse integer-valued data tensors.<n>We propose a simple spectral clustering algorithm augmented with a trimming step to mitigate noise fluctuations.
  arXiv  Detail & Related papers  (2025-01-23T16:41:19Z)
• Provable Tensor Completion with Graph Information [49.08648842312456]
  We introduce a novel model, theory, and algorithm for solving the dynamic graph regularized tensor completion problem. We develop a comprehensive model simultaneously capturing the low-rank and similarity structure of the tensor. In terms of theory, we showcase the alignment between the proposed graph smoothness regularization and a weighted tensor nuclear norm.
  arXiv  Detail & Related papers  (2023-10-04T02:55:10Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Statistical and computational rates in high rank tensor estimation [11.193504036335503]
  Higher-order tensor datasets arise commonly in recommendation systems, neuroimaging, and social networks. We consider a generative latent variable tensor model that incorporates both high rank and low rank models. We show that the statistical-computational gap emerges only for latent variable tensors of order 3 or higher.
  arXiv  Detail & Related papers  (2023-04-08T15:34:26Z)
• Low-Rank Tensor Function Representation for Multi-Dimensional Data Recovery [52.21846313876592]
  Low-rank tensor function representation (LRTFR) can continuously represent data beyond meshgrid with infinite resolution. We develop two fundamental concepts for tensor functions, i.e., the tensor function rank and low-rank tensor function factorization. Our method substantiates the superiority and versatility of our method as compared with state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-12-01T04:00:38Z)
• Unveiling the Sampling Density in Non-Uniform Geometric Graphs [69.93864101024639]
  We consider graphs as geometric graphs: nodes are randomly sampled from an underlying metric space, and any pair of nodes is connected if their distance is less than a specified neighborhood radius. In a social network communities can be modeled as densely sampled areas, and hubs as nodes with larger neighborhood radius. We develop methods to estimate the unknown sampling density in a self-supervised fashion.
  arXiv  Detail & Related papers  (2022-10-15T08:01:08Z)
• From Spectral Graph Convolutions to Large Scale Graph Convolutional Networks [0.0]
  Graph Convolutional Networks (GCNs) have been shown to be a powerful concept that has been successfully applied to a large variety of tasks. We study the theory that paved the way to the definition of GCN, including related parts of classical graph theory.
  arXiv  Detail & Related papers  (2022-07-12T16:57:08Z)
• Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
  In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model. This paper aims to paint an accurate picture of sparsely-connected distributed optimization when workers share the same data distribution. Our theory matches empirical observations in deep learning, and accurately describes the relative merits of different graph topologies.
  arXiv  Detail & Related papers  (2022-06-07T08:19:06Z)
• Learning Optical Flow from a Few Matches [67.83633948984954]
  We show that the dense correlation volume representation is redundant and accurate flow estimation can be achieved with only a fraction of elements in it. Experiments show that our method can reduce computational cost and memory use significantly, while maintaining high accuracy.
  arXiv  Detail & Related papers  (2021-04-05T21:44:00Z)
• Inference for Low-rank Tensors -- No Need to Debias [22.163281794187544]
  In this paper, we consider the statistical inference for several low-rank tensor models. For the rank-one PCA model, we establish the theory for inference on each individual singular tensor. Finally, simulations are presented to corroborate our theoretical discoveries.
  arXiv  Detail & Related papers  (2020-12-29T16:48:02Z)
• Low-Rank and Sparse Enhanced Tucker Decomposition for Tensor Completion [3.498620439731324]
  We introduce a unified low-rank and sparse enhanced Tucker decomposition model for tensor completion. Our model possesses a sparse regularization term to promote a sparse core tensor, which is beneficial for tensor data compression. It is remarkable that our model is able to deal with different types of real-world data sets, since it exploits the potential periodicity and inherent correlation properties appeared in tensors.
  arXiv  Detail & Related papers  (2020-10-01T12:45:39Z)

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.