Squashed Shifted PMI Matrix: Bridging Word Embeddings and Hyperbolic Spaces

• URL: http://arxiv.org/abs/2002.12005v2
• Date: Sat, 26 Sep 2020 15:06:00 GMT
• Title: Squashed Shifted PMI Matrix: Bridging Word Embeddings and Hyperbolic Spaces
• Authors: Zhenisbek Assylbekov and Alibi Jangeldin
• Abstract summary: We show that removing sigmoid transformation in the skip-gram with negative sampling does not harm the quality of word vectors significantly. We also factorize a squashed shifted PMI matrix which, in turn, can be treated as a connection probabilities matrix of a random graph.
• Score: 7.855758501691244
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We show that removing sigmoid transformation in the skip-gram with negative sampling (SGNS) objective does not harm the quality of word vectors significantly and at the same time is related to factorizing a squashed shifted PMI matrix which, in turn, can be treated as a connection probabilities matrix of a random graph. Empirically, such graph is a complex network, i.e. it has strong clustering and scale-free degree distribution, and is tightly connected with hyperbolic spaces. In short, we show the connection between static word embeddings and hyperbolic spaces through the squashed shifted PMI matrix using analytical and empirical methods.

Related papers

• Symmetry-driven embedding of networks in hyperbolic space [0.4779196219827508]
  Hyperbolic models can reproduce the heavy-tailed degree distribution, high clustering, and hierarchical structure of empirical networks. Current algorithms for finding the hyperbolic coordinates of networks, however, do not quantify uncertainty in the inferred coordinates. We present BIGUE, a Markov chain Monte Carlo algorithm that samples the posterior distribution of a Bayesian hyperbolic random graph model.
  arXiv  Detail & Related papers  (2024-06-15T18:44:02Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Dynamic transition of the density-matrix topology under parity-time symmetry [1.5596062401801003]
  Density-matrix topology can undergo transitions in the corresponding open-system dynamics. We show that a hidden parity-time symmetry can further facilitate it. Remarkably, we find that the dynamic transition can also happen periodically in the parity-time symmetry broken regime.
  arXiv  Detail & Related papers  (2024-04-23T06:30:44Z)
• On Learning Gaussian Multi-index Models with Gradient Flow [57.170617397894404]
  We study gradient flow on the multi-index regression problem for high-dimensional Gaussian data. We consider a two-timescale algorithm, whereby the low-dimensional link function is learnt with a non-parametric model infinitely faster than the subspace parametrizing the low-rank projection.
  arXiv  Detail & Related papers  (2023-10-30T17:55:28Z)
• Bayesian Inference of Transition Matrices from Incomplete Graph Data with a Topological Prior [1.2891210250935143]
  We derive an analytically tractable Bayesian method that uses repeated interactions and a topological prior to infer transition matrices data-efficiently. We show that it recovers the transition probabilities with higher accuracy and that it is robust even in cases when the knowledge of the topological constraint is partial.
  arXiv  Detail & Related papers  (2022-10-27T13:17:47Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Hybrid Model-based / Data-driven Graph Transform for Image Coding [54.31406300524195]
  We present a hybrid model-based / data-driven approach to encode an intra-prediction residual block. The first $K$ eigenvectors of a transform matrix are derived from a statistical model, e.g., the asymmetric discrete sine transform (ADST) for stability. Using WebP as a baseline image, experimental results show that our hybrid graph transform achieved better energy compaction than default discrete cosine transform (DCT) and better stability than KLT.
  arXiv  Detail & Related papers  (2022-03-02T15:36:44Z)
• Compressing Heavy-Tailed Weight Matrices for Non-Vacuous Generalization Bounds [0.0]
  The compression framework of arXiv:1802.05296 is utilized to show that matrices with heavy-tail distributed matrix elements can be compressed. The action of these matrices on a vector is discussed, and how they may relate to compression and resilient classification is analyzed.
  arXiv  Detail & Related papers  (2021-05-23T21:36:33Z)
• 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)
• Distributed support-vector-machine over dynamic balanced directed networks [10.76210145983805]
  We consider the binary classification problem via distributed Support-Machines. We propose a continuous-time algorithm that incorporates network topology changes in discrete jumps.
  arXiv  Detail & Related papers  (2021-04-01T11:02:10Z)
• 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)
• Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
  We present a method inspired by spectral clustering where we instead use matrix sketches derived from random dimension-reducing projections. We show that our method produces embeddings that yield performant clustering results given a fully-dynamic block model stream. We also discuss the effects of block model parameters upon the required dimensionality of the subsequent embeddings, and show how random projections could significantly improve the performance of graph clustering in distributed memory.
  arXiv  Detail & Related papers  (2020-07-24T17:38:04Z)
• Semiparametric Nonlinear Bipartite Graph Representation Learning with Provable Guarantees [106.91654068632882]
  We consider the bipartite graph and formalize its representation learning problem as a statistical estimation problem of parameters in a semiparametric exponential family distribution. We show that the proposed objective is strongly convex in a neighborhood around the ground truth, so that a gradient descent-based method achieves linear convergence rate. Our estimator is robust to any model misspecification within the exponential family, which is validated in extensive experiments.
  arXiv  Detail & Related papers  (2020-03-02T16:40:36Z)

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.