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, 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 |
| Publication status | Published - 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.