Manifold Learning: Introduction and Foundational Algorithms in Python

After I was unable to find a thorough investigation of manifold learning methods, I decided to try and learn from a wide variety of sources and then attempt to synthesize an in-depth explanation of the core algorithms, along with their implementations within sklearn.manifold.

Note: the notebooks are best viewed through the jupyter nbviewer links below. github

Contents

• Introduction: nbviewer
  • Overview of manifolds and the basic topology of data
  • Statistical learning and instrinsic dimensionality
  • The manifold hypothesis
• Chapter 1: Multidimensional Scaling nbviewer
  • Classical, metric, and non-metric MDS algorithms
  • Example applications to quantitative psychology and social science
• Chapter 2: ISOMAP nbviewer
  • Geodesic distances and the isometric mapping algorithm
  • Implementation details and applications with facial images and coil-100 object images
• Chapter 3: Local Linear Embedding nbviewer
  • Locally linear reconstructions and optimization problems
  • Example applications with image data
• Chapter 4: Laplacian Eigenmaps/Spectral Embedding nbviewer
  • From the general to the discrete Laplacian operators
  • Visualizing spectral embedding with the networkx library
  • Spectral embedding with NLTK and the Brown text corpus

hyperbolic-learning

It has been recently established that many real-world networks have a latent geometric structure that resembles negatively curved hyperbolic spaces. Therefore, complex networks, and particularly the hierarchical relationships often found within, can often be more accurately represented by embedding graphs in hyperbolic geometry, rather than flat Euclidean space.

The goal of this project is to provide Python implementations for a few recently published algorithms that leverage hyperbolic geometry for machine learning and network analysis. Several examples are given with real-world datasets, however; the time complexity is far from optimized and this repository is primarily for research purposes - specifically investigating how to integrate downstream supervised learning methods with hyperbolic embeddings.

Note: the notebooks are best viewed through the jupyter nbviewer links below. github

Contents

Models

• Poincaré Embeddings:
  • Mostly an exploration of the hyperbolic embedding approach used in [1].
  • Available implementation in the gensim library and a PyTorch version released by the authors here.
• Hyperbolic Multidimensional Scaling: nbviewer
  • Finds embedding in Poincaré disk with hyperbolic distances that preserve input dissimilarities [2].
• K-Means Clustering in the Hyperboloid Model: nbviewer
  • Optimization approach using Frechet means to define a centroid/center of mass in hyperbolic space [3, 4].

  

• Hyperbolic Support Vector Machine - nbviewer
  • Linear hyperbolic SVC based on the max-margin optimization problem in hyperbolic geometry [5].
  • Uses projected gradient descent to define decision boundary and predict classifications.

• Embedding Graphs in Lorentzian Spacetime - nbviewer
  • An algorithm based on notions of causality in the Minkowski spacetime formulation of special relativity [6].
  • Used to embed directed acyclic graphs where nodes are represented by space-like and time-like coordinates.

Datasets

• Zachary Karate Club Network
• WordNet
• Enron Email Corpus
• Polbooks Network
• arXiv Citation Network
• Synthetic generated data (sklearn.make_datasets, networkx.generators, etc.)

Dependencies

• Models are designed based on the sklearn estimator API (sklearn generally used only in rare, non-essential cases)
• Networkx is used to generate & display graphs

References

[1] Nickel, Kiela. “Poincaré embeddings for learning hierarchical representations” (2017). arXiv.
[2] A. Cvetkovski and M. Crovella. Multidimensional scaling in the Poincaré disk. arXiv:1105.5332, 2011.
[3] “Learning graph-structured data using Poincaré embeddings and Riemannian K-means algorithms”. Hatem Hajri, Hadi Zaatiti, Georges Hebrail (2019) arXiv.
[4] Wilson, Benjamin R. and Matthias Leimeister. “Gradient descent in hyperbolic space.” (2018).
[5] “Large-margin classification in hyperbolic space”. Cho, H., Demeo, B., Peng, J., Berger, B. CoRR abs/1806.00437 (2018).
[6] Clough JR, Evans TS (2017) Embedding graphs in Lorentzian spacetime. PLoS ONE 12(11):e0187301. https://doi.org/10.1371/journal.pone.0187301.