Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs

• URL: http://arxiv.org/abs/2103.03561v1
• Date: Fri, 5 Mar 2021 09:45:56 GMT
• Title: Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
• Authors: Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
• Abstract summary: This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdos-Renyi graphs with edge weights distributed according to P. A numerical method is proposed to accurately estimate the Nishimori temperature from the eigenvalues of the Bethe Hessian matrix of the weighted graph.
• Score: 53.13327158427103
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdos-Renyi graphs with edge weights distributed according to P. Estimating the Nishimori temperature being a task of major importance in Bayesian inference problems, as a practical corollary of this new relation, a numerical method is proposed to accurately estimate the Nishimori temperature from the eigenvalues of the Bethe Hessian matrix of the weighted graph. The algorithm, in turn, is used to propose a new spectral method for node classification in weighted (possibly sparse) graphs. The superiority of the method over competing state-of-the-art approaches is demonstrated both through theoretical arguments and real-world data experiments.

Related papers

• von Mises Quasi-Processes for Bayesian Circular Regression [57.88921637944379]
  We explore a family of expressive and interpretable distributions over circle-valued random functions. The resulting probability model has connections with continuous spin models in statistical physics. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Markov Chain Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
  We study a random graph model for small-world networks which are ubiquitous in social and biological sciences. For both detection and recovery of the planted dense cycle, we characterize the information-theoretic thresholds in terms of $n$, $tau$, and an edge-wise signal-to-noise ratio $lambda$.
  arXiv  Detail & Related papers  (2024-02-01T03:39:01Z)
• Bayesian Metric Learning for Uncertainty Quantification in Image Retrieval [0.7646713951724012]
  We propose the first Bayesian encoder for metric learning. We learn a distribution over the network weights with the Laplace Approximation. We show that our Laplacian Metric Learner (LAM) estimates well-calibrated uncertainties, reliably detects out-of-distribution examples, and yields state-of-the-art predictive performance.
  arXiv  Detail & Related papers  (2023-02-02T18:59:23Z)
• An Energy-Based Prior for Generative Saliency [62.79775297611203]
  We propose a novel generative saliency prediction framework that adopts an informative energy-based model as a prior distribution. With the generative saliency model, we can obtain a pixel-wise uncertainty map from an image, indicating model confidence in the saliency prediction. Experimental results show that our generative saliency model with an energy-based prior can achieve not only accurate saliency predictions but also reliable uncertainty maps consistent with human perception.
  arXiv  Detail & Related papers  (2022-04-19T10:51:00Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Generative Learning With Euler Particle Transport [14.557451744544592]
  We propose an Euler particle transport (EPT) approach for generative learning. The proposed approach is motivated by the problem of finding an optimal transport map from a reference distribution to a target distribution. We show that the proposed density-ratio (difference) estimators do not suffer from the "curse of dimensionality" if data is supported on a lower-dimensional manifold.
  arXiv  Detail & Related papers  (2020-12-11T03:10:53Z)
• Learning Representations using Spectral-Biased Random Walks on Graphs [18.369974607582584]
  We study how much a probabilistic bias in this process affects the quality of the nodes picked by the process. We succinctly capture this neighborhood as a probability measure based on the spectrum of the node's neighborhood subgraph represented as a normalized laplacian matrix. We empirically evaluate our approach against several state-of-the-art node embedding techniques on a wide variety of real-world datasets.
  arXiv  Detail & Related papers  (2020-05-19T20:42:43Z)
• Generalized Gumbel-Softmax Gradient Estimator for Various Discrete Random Variables [16.643346012854156]
  Esting the gradients of nodes is one of the crucial research questions in the deep generative modeling community. This paper proposes a general version of the Gumbel-Softmax estimator with continuous relaxation.
  arXiv  Detail & Related papers  (2020-03-04T01:13:15Z)
• Bayesian Deep Learning and a Probabilistic Perspective of Generalization [56.69671152009899]
  We show that deep ensembles provide an effective mechanism for approximate Bayesian marginalization. We also propose a related approach that further improves the predictive distribution by marginalizing within basins of attraction.
  arXiv  Detail & Related papers  (2020-02-20T15:13:27Z)
• Statistical Analysis and Information Theory of Screened Kratzer-Hellmann Potential Model [0.0]
  The radial Schrodinger equation for a newly proposed screened Kratzer-Hellmann potential model was studied. Results were employed to evaluate the rotational-vibrational partition function and other thermodynamic properties for the screened Kratzer-Hellmann potential.
  arXiv  Detail & Related papers  (2020-01-23T10:04:34Z)

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.