Matrix factorisation and the interpretation of geodesic distance

Nick Whiteley; Annie Gray; Patrick Rubin-Delanchy

doi:10.48550/arXiv.2106.01260

Matrix factorisation and the interpretation of geodesic distance

Nick Whiteley^*, Annie Gray^*, Patrick Rubin-Delanchy^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

7 Citations (Scopus)

68 Downloads (Pure)

Abstract

Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems
Subtitle of host publication	NeurIPS 2021
Editors	Marc'Aurelio Ranzato, Alina Beygelzimer, Yann Dauphin, Percy S. Liang, Jenn Wortman Vaughan
Publisher	Neural Information Processing Systems Foundation
Pages	24-38
Number of pages	15
ISBN (Electronic)	9781713845393
DOIs	https://doi.org/10.48550/arXiv.2106.01260
Publication status	Published - 12 Jun 2021
Event	35th Conference on Neural Information Processing Systems, NeurIPS 2021 - Virtual, Online Duration: 6 Dec 2021 → 14 Dec 2021

Publication series

Name	Advances in Neural Information Processing Systems
Volume	1
ISSN (Print)	1049-5258

Conference

Conference	35th Conference on Neural Information Processing Systems, NeurIPS 2021
City	Virtual, Online
Period	6/12/21 → 14/12/21

Bibliographical note

Publisher Copyright:
© 2021 Neural information processing systems foundation. All rights reserved.

Keywords

stat.ML
cs.LG
62G05, 62H20, 62H12, 62H30

Access to Document

10.48550/arXiv.2106.01260Licence: CC BY

https://arxiv.org/pdf/2106.01260v2Licence: CC BY
https://proceedings.neurips.cc/paper/2021/hash/007ff380ee5ac49ffc34442f5c2a2b86-Abstract.htmlLicence: Unspecified

Handle.net

Persistent link

Cite this

Whiteley, N., Gray, A., & Rubin-Delanchy, P. (2021). Matrix factorisation and the interpretation of geodesic distance. In MA. Ranzato, A. Beygelzimer, Y. Dauphin, P. S. Liang, & J. Wortman Vaughan (Eds.), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems: NeurIPS 2021 (pp. 24-38). (Advances in Neural Information Processing Systems; Vol. 1). Neural Information Processing Systems Foundation. https://doi.org/10.48550/arXiv.2106.01260

Whiteley, Nick ; Gray, Annie ; Rubin-Delanchy, Patrick. / Matrix factorisation and the interpretation of geodesic distance. Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems: NeurIPS 2021. editor / Marc'Aurelio Ranzato ; Alina Beygelzimer ; Yann Dauphin ; Percy S. Liang ; Jenn Wortman Vaughan. Neural Information Processing Systems Foundation, 2021. pp. 24-38 (Advances in Neural Information Processing Systems).

@inproceedings{46e48d41db064c8b8d5d4203486e2656,

title = "Matrix factorisation and the interpretation of geodesic distance",

abstract = "Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.",

keywords = "stat.ML, cs.LG, 62G05, 62H20, 62H12, 62H30",

author = "Nick Whiteley and Annie Gray and Patrick Rubin-Delanchy",

note = "Publisher Copyright: {\textcopyright} 2021 Neural information processing systems foundation. All rights reserved.; 35th Conference on Neural Information Processing Systems, NeurIPS 2021 ; Conference date: 06-12-2021 Through 14-12-2021",

year = "2021",

month = jun,

day = "12",

doi = "10.48550/arXiv.2106.01260",

language = "English",

series = "Advances in Neural Information Processing Systems",

publisher = "Neural Information Processing Systems Foundation",

pages = "24--38",

editor = "Marc'Aurelio Ranzato and Alina Beygelzimer and Yann Dauphin and Liang, \{Percy S.\} and \{Wortman Vaughan\}, Jenn",

booktitle = "Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems",

address = "United States",

}

Whiteley, N, Gray, A & Rubin-Delanchy, P 2021, Matrix factorisation and the interpretation of geodesic distance. in MA Ranzato, A Beygelzimer, Y Dauphin, PS Liang & J Wortman Vaughan (eds), Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems: NeurIPS 2021. Advances in Neural Information Processing Systems, vol. 1, Neural Information Processing Systems Foundation, pp. 24-38, 35th Conference on Neural Information Processing Systems, NeurIPS 2021, Virtual, Online, 6/12/21. https://doi.org/10.48550/arXiv.2106.01260

Matrix factorisation and the interpretation of geodesic distance. / Whiteley, Nick; Gray, Annie; Rubin-Delanchy, Patrick.
Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems: NeurIPS 2021. ed. / Marc'Aurelio Ranzato; Alina Beygelzimer; Yann Dauphin; Percy S. Liang; Jenn Wortman Vaughan. Neural Information Processing Systems Foundation, 2021. p. 24-38 (Advances in Neural Information Processing Systems; Vol. 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Matrix factorisation and the interpretation of geodesic distance

AU - Whiteley, Nick

AU - Gray, Annie

AU - Rubin-Delanchy, Patrick

PY - 2021/6/12

Y1 - 2021/6/12

N2 - Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.

AB - Given a graph or similarity matrix, we consider the problem of recovering a notion of true distance between the nodes, and so their true positions. We show that this can be accomplished in two steps: matrix factorisation, followed by nonlinear dimension reduction. This combination is effective because the point cloud obtained in the first step lives close to a manifold in which latent distance is encoded as geodesic distance. Hence, a nonlinear dimension reduction tool, approximating geodesic distance, can recover the latent positions, up to a simple transformation. We give a detailed account of the case where spectral embedding is used, followed by Isomap, and provide encouraging experimental evidence for other combinations of techniques.

KW - stat.ML

KW - cs.LG

KW - 62G05, 62H20, 62H12, 62H30

U2 - 10.48550/arXiv.2106.01260

DO - 10.48550/arXiv.2106.01260

M3 - Conference Contribution (Conference Proceeding)

T3 - Advances in Neural Information Processing Systems

SP - 24

EP - 38

BT - Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems

A2 - Ranzato, Marc'Aurelio

A2 - Beygelzimer, Alina

A2 - Dauphin, Yann

A2 - Liang, Percy S.

A2 - Wortman Vaughan, Jenn

PB - Neural Information Processing Systems Foundation

T2 - 35th Conference on Neural Information Processing Systems, NeurIPS 2021

Y2 - 6 December 2021 through 14 December 2021

ER -

Whiteley N, Gray A, Rubin-Delanchy P. Matrix factorisation and the interpretation of geodesic distance. In Ranzato MA, Beygelzimer A, Dauphin Y, Liang PS, Wortman Vaughan J, editors, Advances in Neural Information Processing Systems 34 - 35th Conference on Neural Information Processing Systems: NeurIPS 2021. Neural Information Processing Systems Foundation. 2021. p. 24-38. (Advances in Neural Information Processing Systems). doi: 10.48550/arXiv.2106.01260

Matrix factorisation and the interpretation of geodesic distance

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Handle.net

Fingerprint

Cite this