# MILE: A Multi-Level Framework for Scalable Graph Embedding

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2018.

## Built on by (most cited first, 28 of 28)

- [Scaling Up Graph Neural Networks Via Graph Coarsening](https://mlsanity.com/paper/2106.05150/) (2021)
- [A Comprehensive Survey on Graph Reduction: Sparsification, Coarsening, and Condensation](https://mlsanity.com/paper/2402.03358/) (2024)
- [Graph coarsening: From scientific computing to machine learning](https://mlsanity.com/paper/2106.11863/) (2021)
- [Probabilistic Graph Rewiring via Virtual Nodes](https://mlsanity.com/paper/2405.17311/) (2024)
- [Graph Coarsening via Convolution Matching for Scalable Graph Neural Network Training](https://mlsanity.com/paper/2312.15520/) (2023)
- [A Topology-aware Graph Coarsening Framework for Continual Graph Learning](https://mlsanity.com/paper/2401.03077/) (2024)
- [Data Augmentation on Graphs: A Technical Survey](https://mlsanity.com/paper/2212.09970/) (2022)
- [Discourse-level Relation Extraction via Graph Pooling](https://mlsanity.com/paper/2101.00124/) (2021)
- [REFINE: Random RangE FInder for Network Embedding](https://mlsanity.com/paper/2108.10703/) (2021)
- [A Survey on Graph Condensation](https://mlsanity.com/paper/2402.02000/) (2024)
- [Diversified Multiscale Graph Learning with Graph Self-Correction](https://mlsanity.com/paper/2103.09754/) (2021)
- [MultiBiSage: A Web-Scale Recommendation System Using Multiple Bipartite Graphs at Pinterest](https://mlsanity.com/paper/2205.10666/) (2022)
- [FairMILE: Towards an Efficient Framework for Fair Graph Representation Learning](https://mlsanity.com/paper/2211.09925/) (2022)
- [A Comprehensive Analytical Survey on Unsupervised and Semi-Supervised Graph Representation Learning Methods](https://mlsanity.com/paper/2112.10372/) (2021)
- [Spectral Maps for Learning on Subgraphs](https://mlsanity.com/paper/2205.14938/) (2022)
- [StructComp: Substituting Propagation with Structural Compression in Training Graph Contrastive Learning](https://mlsanity.com/paper/2312.04865/) (2023)
- [The Role of Fibration Symmetries in Geometric Deep Learning](https://mlsanity.com/paper/2408.15894/) (2024)
- [SMGRL: Scalable Multi-resolution Graph Representation Learning](https://mlsanity.com/paper/2201.12670/) (2022)
- [CAPER: Coarsen, Align, Project, Refine - A General Multilevel Framework for Network Alignment](https://mlsanity.com/paper/2208.10682/) (2022)
- [HUGE: Huge Unsupervised Graph Embeddings with TPUs](https://mlsanity.com/paper/2307.14490/) (2023)
- [Scalable Hypergraph Embedding System](https://mlsanity.com/paper/2103.09660/) (2021)
- [Learning Large-scale Network Embedding from Representative Subgraph](https://mlsanity.com/paper/2112.01442/) (2021)
- [Learning node embeddings via summary graphs: a brief theoretical analysis](https://mlsanity.com/paper/2207.01189/) (2022)
- [AlignGraph: A Group of Generative Models for Graphs](https://mlsanity.com/paper/2301.11273/) (2023)
- [PolicyClusterGCN: Identifying Efficient Clusters for Training Graph Convolutional Networks](https://mlsanity.com/paper/2306.14357/) (2023)
- [Bypassing Skip-Gram Negative Sampling: Dimension Regularization as a More Efficient Alternative for Graph Embeddings](https://mlsanity.com/paper/2405.00172/) (2024)
- [Graph Sparsification for Enhanced Conformal Prediction in Graph Neural Networks](https://mlsanity.com/paper/2410.21618/) (2024)
- [ScaleNet: Scale Invariance Learning in Directed Graphs](https://mlsanity.com/paper/2411.08758/) (2024)

## Abstract (arXiv)

Recently there has been a surge of interest in designing graph embedding methods. Few, if any, can scale to a large-sized graph with millions of nodes due to both computational complexity and memory requirements. In this paper, we relax this limitation by introducing the MultI-Level Embedding (MILE) framework -- a generic methodology allowing contemporary graph embedding methods to scale to large graphs. MILE repeatedly coarsens the graph into smaller ones using a hybrid matching technique to maintain the backbone structure of the graph. It then applies existing embedding methods on the coarsest graph and refines the embeddings to the original graph through a graph convolution neural network that it learns. The proposed MILE framework is agnostic to the underlying graph embedding techniques and can be applied to many existing graph embedding methods without modifying them. We employ our framework on several popular graph embedding techniques and conduct embedding for real-world graphs. Experimental results on five large-scale datasets demonstrate that MILE significantly boosts the speed (order of magnitude) of graph embedding while generating embeddings of better quality, for the task of node classification. MILE can comfortably scale to a graph with 9 million nodes and 40 million edges, on which existing methods run out of memory or take too long to compute on a modern workstation. Our code and data are publicly available with detailed instructions for adding new base embedding methods: urlhttps://github.com/jiongqian/MILE.