Manifold structure in graph embeddings

Patrick Rubin-Delanchy

TL;DR

This paper provides a theoretical bridge between graph theory and manifold learning, proving that spectral embeddings of graphs—even when they appear high-dimensional—actually concentrate around low-dimensional manifolds. By establishing that the "intrinsic" dimension of a graph is often much lower than its "ambient" spectral dimension, the author explains why we can successfully apply machine learning to complex networks without falling victim to the curse of dimensionality.

What Problem Does This Paper Address?

In graph representation learning, we often "embed" nodes into a vector space so we can use standard machine learning tools. A common question arises: What is the "true" dimension of a graph?

If you use spectral embedding (looking at the top eigenvectors of the graph's adjacency matrix), the math might suggest you need a very high, or even infinite, number of dimensions ($D$) to represent the graph perfectly. However, in practice, we find that simple models often work surprisingly well on these embeddings. This paper addresses this paradox by investigating the "Manifold Hypothesis" for graphs: the idea that while data can exist in a high-dimensional space, it actually lives on a much simpler, low-dimensional "shape" or manifold.

Methods

The author focuses on Latent Position Models (LPMs). In these models, every node $i$ has a hidden position $Z_i$ in a $d$-dimensional space, and the probability of an edge between two nodes is a function of their positions (a "kernel").

Key technical contributions include:

  • Operator Theory: The paper treats the graph's kernel as a mathematical operator. By assuming the operator is "trace-class" (a technical way of saying its total energy is finite), the author links the latent positions $Z_i$ to high-dimensional vectors $X_i$ in a Hilbert space.
  • Hausdorff Dimension: The core proof uses the concept of Hausdorff dimension to show that these high-dimensional vectors $X_i$ cluster onto a manifold whose dimension is determined by $d$ (the latent dimension) and the smoothness of the kernel.
  • Spectral Consistency: The paper leverages existing proofs of "strong consistency" to show that the points we actually calculate via spectral embedding ($X̂_i$) converge to these theoretical manifold positions as the graph grows.

Datasets

The paper validates its theory using both simulations and large-scale real-world data:

  • Simulated Graphs: Three models with $d=1$ but infinite ambient dimension: a "Sociability" kernel, a branching "Graphon" model, and a Gaussian radial basis kernel.
  • Los Alamos National Laboratory (LANL) Data: Two separate graphs representing computer-to-computer network flows and authentication events (up to 18,000 nodes and 400,000 edges).
  • Yelp Dataset: A massive user-restaurant rating graph (5 million edges), specifically looking at the embedding of restaurants.

Key Insights and Ideas

  • Ambient vs. Intrinsic Dimension: A graph might have an infinite "ambient" dimension ($D$), but its "intrinsic" dimension ($d$)—the dimension of the manifold it sits on—is what actually matters for learning.
  • Curvature is Key: The dimension of the resulting manifold isn't just $d$; it's governed by the curvature of the kernel along its diagonal. If a kernel is less smooth (lower $\alpha$), the manifold dimension can expand up to $d/\alpha$.
  • The "Aha" Moment for Graphons: For graphons (models on a 1D interval), the paper shows that common smoothness assumptions limit the manifold dimension to $2/\alpha$. This explains why even 1D latent models can produce complex, multi-dimensional-looking embeddings.
  • Explaining ML Success: This theory explains why non-linear methods like Neural Networks or Random Forests perform so well on graph embeddings—they are effectively performing manifold regression.

Key Results

  • Theorem 3: The primary result proves that under specific smoothness conditions, the graph embedding lives on a manifold of Hausdorff dimension $d/\alpha$.
  • Regression Performance: In a prediction task, the author showed that non-linear models (Random Forest MSE: 1.11, Neural Net MSE: 1.25) significantly outperformed linear models (Lasso MSE: 1.58) because they could "see" the one-dimensional manifold structure hidden in a 100-dimensional embedding.
  • Visualization: By applying non-linear dimension reduction (like t-SNE or UMAP) after spectral embedding, the author produced clear visualizations where nodes clustered by real-world attributes (like US states in the Yelp data or network ports in the LANL data), confirming that the geometric structure is meaningful.

Limitations and Future Work

  • Structural Completeness: While the paper establishes the dimension of the manifold, it doesn't fully characterize other properties like its specific topological structure or global smoothness.
  • Sparsity: The theory relies on certain asymptotic regimes for sparse graphs. While it covers many cases, the most extreme "projective" sparsity models remain a challenge for theoretical consistency.
  • Inference Tools: The paper suggests we could use this to test hypotheses (e.g., "Is this social network actually driven by 3D geography?"), but the specific statistical tests for "manifold-ness" in graphs are still an area for future development.

Summary updated

Abstract

Statistical analysis of a graph often starts with embedding, the process of representing its nodes as points in space. How to choose the embedding dimension is a nuanced decision in practice, but in theory a notion of true dimension is often available. In spectral embedding, this dimension may be very high. However, this paper shows that existing random graph models, including graphon and other latent position models, predict the data should live near a much lower-dimensional set. One may therefore circumvent the curse of dimensionality by employing methods which exploit hidden manifold structure.
BibTeX
@inproceedings{rubindelanchy2020manifold,
  author = {Patrick Rubin-Delanchy},
  title = {{Manifold structure in graph embeddings}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=j7n1UMCxN0},
}
Figure