Symmetry-driven embedding of networks in hyperbolic space

• URL: http://arxiv.org/abs/2406.10711v2
• Date: Thu, 24 Apr 2025 18:16:40 GMT
• Title: Symmetry-driven embedding of networks in hyperbolic space
• Authors: Simon Lizotte, Jean-Gabriel Young, Antoine Allard,
• Abstract summary: We present a Markov chain Monte Carlo algorithm that samples the posterior distribution of a hyperbolic random graph model.<n>We show that the samples are consistent with current algorithms while providing added credible intervals for the coordinates and all network properties.
• Score: 0.4779196219827508
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hyperbolic models are known to produce networks with properties observed empirically in most network datasets, including heavy-tailed degree distribution, high clustering, and hierarchical structures. As a result, several embeddings algorithms have been proposed to invert these models and assign hyperbolic coordinates to network data. Current algorithms for finding these coordinates, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo (MCMC) algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model. We show that the samples are consistent with current algorithms while providing added credible intervals for the coordinates and all network properties. We also show that some networks admit two or more plausible embeddings, a feature that an optimization algorithm can easily overlook.

Related papers

• Generic Multimodal Spatially Graph Network for Spatially Embedded Network Representation Learning [2.07180164747172]
  A Generic Multimodal Spatially Graph Convolutional Network (GMu-SGCN) is developed for efficient representation of spatially embedded networks. The developed GMu-SGCN can improve accuracy of the edge existence prediction task by 37.1% compared to a GraphSAGE model.
  arXiv  Detail & Related papers  (2025-02-01T19:05:48Z)
• On Cyclical MCMC Sampling [13.002470980542707]
  We show that cyclical MCMC converges to the desired probability distribution in settings where the Markov kernels used are fast mixing. We also show that cyclical MCMC estimates well the local shape of the target distribution around each mode, even when we do not have convergence to the target.
  arXiv  Detail & Related papers  (2024-03-01T02:20:44Z)
• Reverse Diffusion Monte Carlo [19.35592726471155]
  We propose a novel Monte Carlo sampling algorithm called reverse diffusion Monte Carlo (rdMC) rdMC is distinct from the Markov chain Monte Carlo (MCMC) methods.
  arXiv  Detail & Related papers  (2023-07-05T05:42:03Z)
• Semi-Supervised Clustering of Sparse Graphs: Crossing the Information-Theoretic Threshold [3.6052935394000234]
  Block model is a canonical random graph model for clustering and community detection on network-structured data. No estimator based on the network topology can perform substantially better than chance on sparse graphs if the model parameter is below a certain threshold. We prove that with an arbitrary fraction of the labels feasible throughout the parameter domain.
  arXiv  Detail & Related papers  (2022-05-24T00:03:25Z)
• Bayesian Structure Learning with Generative Flow Networks [85.84396514570373]
  In Bayesian structure learning, we are interested in inferring a distribution over the directed acyclic graph (DAG) from data. Recently, a class of probabilistic models, called Generative Flow Networks (GFlowNets), have been introduced as a general framework for generative modeling. We show that our approach, called DAG-GFlowNet, provides an accurate approximation of the posterior over DAGs.
  arXiv  Detail & Related papers  (2022-02-28T15:53:10Z)
• A Robust and Flexible EM Algorithm for Mixtures of Elliptical Distributions with Missing Data [71.9573352891936]
  This paper tackles the problem of missing data imputation for noisy and non-Gaussian data. A new EM algorithm is investigated for mixtures of elliptical distributions with the property of handling potential missing data. Experimental results on synthetic data demonstrate that the proposed algorithm is robust to outliers and can be used with non-Gaussian data.
  arXiv  Detail & Related papers  (2022-01-28T10:01:37Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• 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)
• What Are Bayesian Neural Network Posteriors Really Like? [63.950151520585024]
  We show that Hamiltonian Monte Carlo can achieve significant performance gains over standard and deep ensembles. We also show that deep distributions are similarly close to HMC as standard SGLD, and closer than standard variational inference.
  arXiv  Detail & Related papers  (2021-04-29T15:38:46Z)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies. We present a number of applications where the use of multiple geometric models improves accuracy. These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
  arXiv  Detail & Related papers  (2021-03-25T14:35:07Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Anomaly Detection on Attributed Networks via Contrastive Self-Supervised Learning [50.24174211654775]
  We present a novel contrastive self-supervised learning framework for anomaly detection on attributed networks. Our framework fully exploits the local information from network data by sampling a novel type of contrastive instance pair. A graph neural network-based contrastive learning model is proposed to learn informative embedding from high-dimensional attributes and local structure.
  arXiv  Detail & Related papers  (2021-02-27T03:17:20Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel [5.156484100374058]
  A novel spectral clustering algorithm is proposed for community detection under the degree-corrected blockmodel. Results show improved performance over competing methods in representing computer networks.
  arXiv  Detail & Related papers  (2020-11-09T16:55:38Z)
• Stacking for Non-mixing Bayesian Computations: The Curse and Blessing of Multimodal Posteriors [8.11978827493967]
  We propose an approach using parallel runs of MCMC, variational, or mode-based inference to hit as many modes as possible. We present theoretical consistency with an example where the stacked inference process approximates the true data. We demonstrate practical implementation in several model families.
  arXiv  Detail & Related papers  (2020-06-22T15:26:59Z)
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines [2.8021833233819486]
  We define a message-passing algorithm for computing magnetizations in Boltzmann machines. We prove the global convergence of the algorithm under a stability criterion and compute convergence rates showing excellent agreement with numerical simulations.
  arXiv  Detail & Related papers  (2020-05-04T15:19:31Z)
• Consistency of Spectral Clustering on Hierarchical Stochastic Block Models [5.983753938303726]
  We study the hierarchy of communities in real-world networks under a generic block model. We prove the strong consistency of this method under a wide range of model parameters. Unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude.
  arXiv  Detail & Related papers  (2020-04-30T01:08:59Z)
• Binarized Graph Neural Network [65.20589262811677]
  We develop a binarized graph neural network to learn the binary representations of the nodes with binary network parameters. Our proposed method can be seamlessly integrated into the existing GNN-based embedding approaches. Experiments indicate that the proposed binarized graph neural network, namely BGN, is orders of magnitude more efficient in terms of both time and space.
  arXiv  Detail & Related papers  (2020-04-19T09:43:14Z)
• Latent Poisson models for networks with heterogeneous density [0.0]
  Empirical networks are often globally sparse, with a small average number of connections per node, when compared to the total size of the network. We show how latent Poisson models which generate hidden multigraphs can be effective at capturing this density, while being more tractable mathematically than some of the alternatives that model simple graphs directly.
  arXiv  Detail & Related papers  (2020-02-18T18:58:13Z)

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.