2m ago

1 Views

0 Downloads

7.84 MB

64 Pages

Tags:

Transcription

Hyperbolic Distance Geometry ProblemsPuoya Tabaghia joint work with Ivan DokmanićUniversity of Illinois at Urbana-ChampaignCoordinated Science LabMini-symposium on Sensor Network Localization and DynamicalDistance GeometryThe Fields Institute, CanadaMay 20, 2021Puoya TabaghiHyperbolic Distance Geometry Problems1 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurementsPuoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurementsPuoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introductiondistance geometry problems (DGPs)to find a realization for a set of entities given a set of distance-relatedmeasurements when dissimilarities are Euclidean distances: metric multidimensional scaling, PCA, metric DGP manifold learning (preserve local distances)Puoya TabaghiHyperbolic Distance Geometry Problems2 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15]Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically treesPuoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically treesPuoya TabaghiHyperbolic Distance Geometry Problems3 / 31

introduction - cont. (1) real-world applications of Euclidean DGPs:1 molecular conformations [Hendrickson ’95, Liberti ’08]2 wireless sensor networks [Man-Cho So ’07, Biswas ’06]3 robotics [Cornejo ’15] but there exists other types of data associated with graphs,specifically trees taxonomies in biology, concept hierarchies in computationallinguistics, .Puoya TabaghiHyperbolic Distance Geometry Problems3 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11]Puoya TabaghiHyperbolic Distance Geometry Problems4 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11] the number of leaves of a tree can grow exponentially(constant branching factor) Euclidean space: vol BEd (r ) O(r d ) 2 hyperbolic space: vol BHd (r ) O(r d e (d 1)r )1Puoya TabaghiHyperbolic Distance Geometry Problems4 / 31

why hyperbolic spaces? hyperbolic spaces can embed hierarchical structures witharbitrarily low distortion [Sarkar, ’11] the number of leaves of a tree can grow exponentially(constant branching factor) Euclidean space: vol BEd (r ) O(r d ) 2 hyperbolic space: vol BHd (r ) O(r d e (d 1)r )1Figure: a weighted tree embedded in (a) hyperbolic space and (b) Euclidean spacePuoya TabaghiHyperbolic Distance Geometry Problems4 / 31

examples of hierarchical dataPuoya TabaghiHyperbolic Distance Geometry Problems5 / 31

examples of hierarchical dataPuoya TabaghiHyperbolic Distance Geometry Problems5 / 31

outline1. hyperbolic spaces2. hyperbolic distance geometryproblemsPuoya Tabaghi3. hyperbolic Procrustes analysis4. geometry of similaritiesHyperbolic Distance Geometry Problems6 / 31

models of hyperbolic space half-space (H), Poincaré (I), jemisphere (J), Klein (K), and’Loid (L) models there is a distance-preserving bijection between each pairPuoya TabaghiHyperbolic Distance Geometry Problems7 / 31

geodesics in hyperbolic spaces the shortest path between x, y Ld belongs tospan {x, y } Ld the stereographic projection gives the geodesics in PoincarémodelPuoya TabaghiHyperbolic Distance Geometry Problems8 / 31

Lorentzian spaceDefinitionLet x and y be vectors in Rd 1 with d 1. The Lorentzian innerproduct of x and y is defined as[x, y ] x Hy ,where H Puoya Tabaghi 1 0 0I R(d 1) (d 1) .Hyperbolic Distance Geometry Problems9 / 31

Lorentzian spaceDefinitionLet x and y be vectors in Rd 1 with d 1. The Lorentzian innerproduct of x and y is defined as[x, y ] x Hy ,where H 1 0 0I R(d 1) (d 1) . similarly, we can define H-adjoint, H-unitary operators, and .Puoya TabaghiHyperbolic Distance Geometry Problems9 / 31

’Loid model of hyperbolic spaceDefinitionThe ’Loid model of d-dimensional hyperbolic space is a Riemannianmanifold Ld (Ld , (gx )x ), wherenoLd x Rd 1 : [x, x] 1, x1 0and the Riemannian metric gx (u, v ) [u, v ] where u, v Tx Ld .Puoya TabaghiHyperbolic Distance Geometry Problems10 / 31

’Loid model of hyperbolic spaceDefinitionThe ’Loid model of d-dimensional hyperbolic space is a Riemannianmanifold Ld (Ld , (gx )x ), wherenoLd x Rd 1 : [x, x] 1, x1 0and the Riemannian metric gx (u, v ) [u, v ] where u, v Tx Ld . the Lorentzian inner product determines the distance betweenx, y Ld , asd(x, y ) acosh( [x, y ])Puoya TabaghiHyperbolic Distance Geometry Problems10 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0Puoya TabaghiHyperbolic Distance Geometry Problems11 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0 the exponential map expx : Tx Ld Ld can be used forgradient-based optimizationsexpx (v ) cosh kv k x sinh kv kPuoya Tabaghivkv kHyperbolic Distance Geometry Problems11 / 31

tangent space the tangent space at point x Ld is given bynoTx Ld v Rd 1 : [x, v ] 0 the exponential map expx : Tx Ld Ld can be used forgradient-based optimizationsexpx (v ) cosh kv k x sinh kv kPuoya Tabaghivkv kHyperbolic Distance Geometry Problems11 / 31

hyperbolic distance geometry problems hyperbolic DGPs 1 : to find an embedding for a set of entitiesin a hyperbolic space that realizes a given set of metric and/orsimilarity measurementsFigure: (a): encode the measurements in hyperbolic distance matrix(HDM), (b): complete the HDM, (c): estimate the point set positions1“Hyperbolic Distance Matrices”, KDD ’20Puoya TabaghiHyperbolic Distance Geometry Problems12 / 31

hyperbolic distance matrix & Gramian a hyperbolic distance matrix (HDM) D D(X ) encodesinter-point distances for a point set X Ld Nd(xi , xj ) acosh( gij ) where gij [xi , xj ] xi HxjPuoya TabaghiHyperbolic Distance Geometry Problems13 / 31

hyperbolic distance matrix & Gramian a hyperbolic distance matrix (HDM) D D(X ) encodesinter-point distances for a point set X Ld Nd(xi , xj ) acosh( gij ) where gij [xi , xj ] xi Hxj HDM is a non-linear function of the hyperbolic Gramian, i.e.,D acosh[ G ], where G X HXwhere acosh[·] is an elementwise acosh(·) operatorPuoya TabaghiHyperbolic Distance Geometry Problems13 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Puoya TabaghiHyperbolic Distance Geometry Problems14 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Then,G G G wherePuoya TabaghiG , G 0,rank G d, rank G 1, xn Rd,1ei Gei 1, i [N], xn Ld Ldei Gej 1, i, j [N]. xn LdHyperbolic Distance Geometry Problems14 / 31

semidefinite characterization of hyperbolic GramianspropositionLet G be the hyperbolic Gramian for a set of points x1 , · · · , xN Ld .Then,G G G whereG , G 0,rank G d, rank G 1, xn Rd,1ei Gei 1, i [N], xn Ld Ldei Gej 1, i, j [N]. xn LdConversely, any matrix G RN N that satisfies the above conditions is ahyperbolic Gramian for a set of N points in Ld .Puoya TabaghiHyperbolic Distance Geometry Problems14 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij )Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gijPuoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian.Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian. we can write non-metric measurements,d(xi1 , xi2 ) d(xi3 , xi4 ) acosh( gi1 i2 ) acosh( gi3 i4 )as a linear constraint in the form ofLi (G ) ei 1 Gei2 ei 3 Gei4 0Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

data-fidelity constraints for metric measurements, we want deij acosh( gij ) equivalently: cosh(deij ) gij Let W be a measurement mask. The quadratic constrainte GW cosh[D] 2F enforces the accuracy of the estimated hyperbolic Gramian. we can write non-metric measurements,d(xi1 , xi2 ) d(xi3 , xi4 ) acosh( gi1 i2 ) acosh( gi3 i4 )as a linear constraint in the form ofLi (G ) ei 1 Gei2 ei 3 Gei4 0“linear and quadratic data-fidelity constraints”Puoya TabaghiHyperbolic Distance Geometry Problems15 / 31

HDGP: semidefinite relaxationsemidefinite relaxation (SDR)for appropriate 1 , 2 0, solve for G :minimizeTr G Tr G trace is a surrogate for rankw.r.tG , G 0subject toG G G ,ei Gei 1, i [N]ei Gej 1,e GW cosh[D]Lk (G ) 2 ,Puoya Tabaghi i, j [N] 2F 1 , k K .Hyperbolic Distance Geometry Problems16 / 31

from SDR to the embedding H-Gramian estimated by the semidefinite relaxation does notnecessarily have the correct rank projection w/ Riemanniangradient descentPuoya TabaghiHyperbolic Distance Geometry Problems17 / 31

from SDR to the embedding H-Gramian estimated by the semidefinite relaxation does notnecessarily have the correct rank projection w/ Riemanniangradient descentproposition NLet G be a hyperbolic Gramian for X Ld , with eigenvalue decomposition G UΛU , and eigenvalues λ0 0 λ1 . . . λd .Then, there exists an H-unitary matrix R such that X R Λ 1/2 U.Puoya TabaghiHyperbolic Distance Geometry Problems17 / 31

embedding with missing measurements random hyperbolic point sets with sparse metric andnon-metric measurementsFigure: left: the probability of an accurate estimation for metric samplingdensity S, right: the empirical error for ordinal sampling density SPuoya TabaghiHyperbolic Distance Geometry Problems18 / 31

weighted tree embedding random weighted trees of size NFigure: Tree embedding in hyperbolic (red) and Euclidean (green) space.Discrete distribution of optimal embedding dimension.Puoya TabaghiHyperbolic Distance Geometry Problems19 / 31

hyperbolic Procrustes analysis we ask: how can we align two embedded trees that have a fewnodes in common?2“On Procrustes Analysis in Hyperbolic Space”, Signal Processing Letters,2021Puoya TabaghiHyperbolic Distance Geometry Problems20 / 31

hyperbolic Procrustes analysis we ask: how can we align two embedded trees that have a fewnodes in common? Procrustes analysis 2 : to find an isometry between two sets ofhyperbolic points to best superimpose them onto each otherFigure: tree alignment in Poincaré disk. (a) and (b) we center each pointset, and (c) estimate the unknown rotation map2“On Procrustes Analysis in Hyperbolic Space”, Signal Processing Letters,2021Puoya TabaghiHyperbolic Distance Geometry Problems20 / 31

hyperbolic isometries any hyperbolic isometry is a composition of two elementarymaps: translation and rotation (and reflection)Puoya TabaghiHyperbolic Distance Geometry Problems21 / 31

hyperbolic isometries any hyperbolic isometry is a composition of two elementarymaps: translation and rotation (and reflection)elementary isometriesThe function T : Ld Ld is an isometry if and only if it can be writtenas T (x) RU Rb x, where" q# 2 1 0 1 kbkbRU , Rb 10 Ub(I bb ) 2for a unitary matrix U O(d) and a vector b Rd . More over, Rb 1 R b and RU 1 RU .Puoya TabaghiHyperbolic Distance Geometry Problems21 / 31

hyperbolic isometries, visualizedFigure: (a) hyperbolic rotation, (b) hyperbolic translationPuoya TabaghiHyperbolic Distance Geometry Problems22 / 31

hyperbolic Procrustes analysis hyperbolic center mass of x1 , . . . , xN Ld ismx arg maxz RdPuoya Tabaghi1 X[xn , Q(z)] a notion of addition in LdNn [N]Hyperbolic Distance Geometry Problems23 / 31

hyperbolic Procrustes analysis hyperbolic center mass of x1 , . . . , xN Ld ismx arg maxz Rd1 X[xn , Q(z)] a notion of addition in LdNn [N]proposition: decoupling hyperbolic rotation and translationLet x1 , . . . , xN and x10 , . . . xN0 in Ld such that xn Rb RU xn0 , n [N].Then, R mx xn RV R mx 0 xn0 where RV is a hyperbolic rotation matrix.Puoya TabaghiHyperbolic Distance Geometry Problems23 / 31

hyperbolic Procrustes: rotation & reflection we estimate the unknown hyperbolic rotation by solvingUb arg maxXV O(d) n [N][R mx xn , RV R mx 0 xn0 ](1)propositionThe optimal unitary matrix that solves (1) is Ub Ul Ur ,where Ul ΣUr is the singular value decomposition ofP(R mx X )P(R mx 0 X 0 ) .Puoya TabaghiHyperbolic Distance Geometry Problems24 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare!Puoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domainPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrencesPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced dataPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced data3 biological dataPuoya TabaghiHyperbolic Distance Geometry Problems25 / 31

geometry of similarities in practice, truly hyperbolic distance measurements are rare! similarity measurements are typical in scientific domain1 correlations & co-occurrences2 perceptual and crowd-sourced data3 biological data can we reveal the geometry from similarity measurements only(no metric information)?Puoya TabaghiHyperbolic Distance Geometry Problems25 / 31

similarities orders similarity measurements: i, j [N] : yij φ d(xi , xj ) where φ(·) is an unknown monotonically decreasing function this model transforms similarities to ordinal measurements i, j, k, l [N] : yi,j yk,l d(xi , xj ) d(xk , xl )Puoya TabaghiHyperbolic Distance Geometry Problems26 / 31

ordinal spread consider similarity measurements {yi,j }i,j [6] with the followingsorted distance list,d(x1 , x2 ) d(x2 , x3 ) d(x1 , x3 ) d(x4 , x5 ) · · · d(x5 , x6 ) our proposal: the ranking of the first appearance of the k-thpoint in the sorted distance list — or the the ordinal spread αkα (α1 , α2 , α3 , α4 , α5 , α6 ) (1, 1, 2, 4, 4, 11)Puoya TabaghiHyperbolic Distance Geometry Problems27 / 31

random ordinal spread variable on similarity graphs we can compute the empirical PMF of αN for a large similaritygraph ( V N)Puoya TabaghiHyperbolic Distance Geometry Problems28 / 31

hyperbolicity of weighted trees our proposed hypothesis test:1 compute the empirical PαN from a randomly generatedweighted tree2 find the best match from random point sets in each space formH2 , E2 and S2Puoya TabaghiHyperbolic Distance Geometry Problems29 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic spacePuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problemsPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problems hyperbolic Procrustes analysis is (almost) identical to itsEuclidean versionPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

conclusion metric/non-metric trees can be faithfully embedded in ahyperbolic space a semidefinite relaxation can solve hyperbolic distancegeometry problems hyperbolic Procrustes analysis is (almost) identical to itsEuclidean version even non-metric measurements can encode geometricalinformationPuoya TabaghiHyperbolic Distance Geometry Problems30 / 31

Thank you!

Puoya Tabaghi Hyperbolic Distance Geometry Problems 4 / 31. examplesofhierarchicaldata Puoya Tabaghi Hyperbolic Distance Geometry Problems 5 / 31. examplesofhierarchicaldata Puoya Tabaghi Hyperbolic Distance Geometry Problems 5 / 31. outline 1. hyperbolicspaces 2. hyperbolicdistancegeometry

Related Documents: