Geometry of Similarity Comparisons

• URL: http://arxiv.org/abs/2006.09858v4
• Date: Thu, 29 Jul 2021 00:22:18 GMT
• Title: Geometry of Similarity Comparisons
• Authors: Puoya Tabaghi, Jianhao Peng, Olgica Milenkovic, Ivan Dokmani\'c
• Abstract summary: We show that the ordinal capacity of a space form is related to its dimension and the sign of its curvature. More importantly, we show that the statistical behavior of the ordinal spread random variables defined on a similarity graph can be used to identify its underlying space form.
• Score: 51.552779977889045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many data analysis problems can be cast as distance geometry problems in \emph{space forms} -- Euclidean, spherical, or hyperbolic spaces. Often, absolute distance measurements are often unreliable or simply unavailable and only proxies to absolute distances in the form of similarities are available. Hence we ask the following: Given only \emph{comparisons} of similarities amongst a set of entities, what can be said about the geometry of the underlying space form? To study this question, we introduce the notions of the \textit{ordinal capacity} of a target space form and \emph{ordinal spread} of the similarity measurements. The latter is an indicator of complex patterns in the measurements, while the former quantifies the capacity of a space form to accommodate a set of measurements with a specific ordinal spread profile. We prove that the ordinal capacity of a space form is related to its dimension and the sign of its curvature. This leads to a lower bound on the Euclidean and spherical embedding dimension of what we term similarity graphs. More importantly, we show that the statistical behavior of the ordinal spread random variables defined on a similarity graph can be used to identify its underlying space form. We support our theoretical claims with experiments on weighted trees, single-cell RNA expression data and spherical cartographic measurements.

Related papers

• Reconstructing the Geometry of Random Geometric Graphs [9.004991291124096]
  Random geometric graphs are random graph models defined on metric spaces. We show how to efficiently reconstruct the geometry of the underlying space from the sampled graph.
  arXiv  Detail & Related papers  (2024-02-14T21:34:44Z)
• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Alignment and Outer Shell Isotropy for Hyperbolic Graph Contrastive Learning [69.6810940330906]
  We propose a novel contrastive learning framework to learn high-quality graph embedding. Specifically, we design the alignment metric that effectively captures the hierarchical data-invariant information. We show that in the hyperbolic space one has to address the leaf- and height-level uniformity which are related to properties of trees.
  arXiv  Detail & Related papers  (2023-10-27T15:31:42Z)
• Geometric Neural Diffusion Processes [55.891428654434634]
  We extend the framework of diffusion models to incorporate a series of geometric priors in infinite-dimension modelling. We show that with these conditions, the generative functional model admits the same symmetry.
  arXiv  Detail & Related papers  (2023-07-11T16:51:38Z)
• Emergent spacetime from purely random structures [0.0]
  We study the geometrical properties such as the dimensionality and the curvature emerging out of the connectivity properties of uniform random graphs. Our approach leads to a unification of space and matter-energy, for which we propose a mass-energy-space equivalence.
  arXiv  Detail & Related papers  (2022-10-03T14:24:24Z)
• Geometry Interaction Knowledge Graph Embeddings [153.69745042757066]
  We propose Geometry Interaction knowledge graph Embeddings (GIE), which learns spatial structures interactively between the Euclidean, hyperbolic and hyperspherical spaces. Our proposed GIE can capture a richer set of relational information, model key inference patterns, and enable expressive semantic matching across entities.
  arXiv  Detail & Related papers  (2022-06-24T08:33:43Z)
• A Unifying and Canonical Description of Measure-Preserving Diffusions [60.59592461429012]
  A complete recipe of measure-preserving diffusions in Euclidean space was recently derived unifying several MCMC algorithms into a single framework. We develop a geometric theory that improves and generalises this construction to any manifold.
  arXiv  Detail & Related papers  (2021-05-06T17:36:55Z)
• Identifying the latent space geometry of network models through analysis of curvature [7.644165047073435]
  We present a method to consistently estimate the manifold type, dimension, and curvature from an empirically relevant class of latent spaces. Our core insight comes by representing the graph as a noisy distance matrix based on the ties between cliques.
  arXiv  Detail & Related papers  (2020-12-19T00:35:29Z)
• Representation of 2D frame less visual space as a neural manifold and its information geometric interpretation [0.0]
  The origin of hyperbolic nature of the visual space is investigated using evidences from neuroscience. The processing of spatial information in the human brain can be modeled in a parametric probability space endowed with Fisher-Rao metric.
  arXiv  Detail & Related papers  (2020-11-27T07:21:43Z)
• Measuring spatial uniformity with the hypersphere chord length distribution [0.7310043452300736]
  This article introduces a novel measure to assess data uniformity and detect uniform pointsets on high-dimensional Euclidean spaces. The imposed connection between the distance distribution of uniformly selected points and the hyperspherical chord length distribution is employed to quantify uniformity.
  arXiv  Detail & Related papers  (2020-04-12T20:48:50Z)

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.