# Ironing the Graphs: Toward a Correct Geometric Analysis of Large-Scale Graphs

arXiv: https://arxiv.org/abs/2407.21609 · HTML: https://mlsanity.com/paper/2407.21609/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 31 Jul 2024.

## Builds on (most cited first, 12 of 12)

- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Optimal Transport for structured data with application on graphs](https://mlsanity.com/paper/1805.09114/) (2018)
- [Beltrami Flow and Neural Diffusion on Graphs](https://mlsanity.com/paper/2110.09443/) (2021)
- [Community Detection on Networks with Ricci Flow](https://mlsanity.com/paper/1907.03993/) (2019)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [Wasserstein Embedding for Graph Learning](https://mlsanity.com/paper/2006.09430/) (2020)
- [Ricci Curvature of the Internet Topology](https://mlsanity.com/paper/1501.04138/) (2015)
- [Network Alignment by Discrete Ollivier-Ricci Flow](https://mlsanity.com/paper/1809.00320/) (2018)
- [Forman-Ricci flow for change detection in large dynamic data sets](https://mlsanity.com/paper/1604.06634/) (2016)
- [Clustering, factor discovery and optimal transport](https://mlsanity.com/paper/1902.10288/) (2019)
- [Geometric Sampling of Networks](https://mlsanity.com/paper/2010.15221/) (2020)

## Abstract (arXiv)

Graph embedding approaches attempt to project graphs into geometric entities, i.e, manifolds. The idea is that the geometric properties of the projected manifolds are helpful in the inference of graph properties. However, if the choice of the embedding manifold is incorrectly performed, it can lead to incorrect geometric inference. In this paper, we argue that the classical embedding techniques cannot lead to correct geometric interpretation as they miss the curvature at each point, of manifold. We advocate that for doing correct geometric interpretation the embedding of graph should be done over regular constant curvature manifolds. To this end, we present an embedding approach, the discrete Ricci flow graph embedding (dRfge) based on the discrete Ricci flow that adapts the distance between nodes in a graph so that the graph can be embedded onto a constant curvature manifold that is homogeneous and isotropic, i.e., all directions are equivalent and distances comparable, resulting in correct geometric interpretations. A major contribution of this paper is that for the first time, we prove the convergence of discrete Ricci flow to a constant curvature and stable distance metrics over the edges. A drawback of using the discrete Ricci flow is the high computational complexity that prevented its usage in large-scale graph analysis. Another contribution of this paper is a new algorithmic solution that makes it feasible to calculate the Ricci flow for graphs of up to 50k nodes, and beyond. The intuitions behind the discrete Ricci flow make it possible to obtain new insights into the structure of large-scale graphs. We demonstrate this through a case study on analyzing the internet connectivity structure between countries at the BGP level.