PaperlayerView exact revision on arXiv

Source-linked AI summary

MILE: A Multi-Level Framework for Scalable Graph Embedding

Jiongqian Liang, Saket Gurukar, Srinivasan Parthasarathy

arXiv:1802.09612v2cs.AIcs.SI

TL;DR

Many graph embedding methods struggle to scale to large graphs because they require substantial computation and memory. MILE coarsens graphs, applies existing embedding methods at the coarsest level, and learns graph-convolution refinement. It improves scalability while often improving embedding quality.

  • Problem

    Many graph embedding methods do not scale to large datasets, limiting their use on graphs with over 1 million nodes amid high computational and memory requirements.

    Source: §1 · p. 1

  • Method

    MILE repeatedly coarsens the graph, applies an existing embedding method to the coarsest graph, then learns graph-convolution refinement back to the original graph.

    Source: §1 · p. 1, Graph Coarsening · p. 3, Refinement of Embeddings · p. 5

  • Results

    MILE improves scalability by up to 30-fold and improves embedding quality in many cases, sometimes by more than 10%.

    Source: §1 · pp. 1–2, §7 · p. 12

  • Takeaways & Limitations

    MILE’s learned refinement strategy depends on both graph properties and the embedding method in use.

    Source: §7 · p. 12

    The best coarsening level depends on the application and graph; 2–4 levels usually balance quality and speed below 1 million nodes, while larger graphs tend to retain high quality at 6–8 levels.

    Source: Graph Coarsening · p. 4

Abstract

from arXiv · show

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: \url{https://github.com/jiongqian/MILE}.

1 Introduction

Graph embedding methods offer competitive qualitative advantages but often do not scale to large datasets. MILE is proposed to apply existing methods at scale while seeking to improve embedding quality.

1 Introduction

  • Many embedding methods do not scale to graphs with over 1 million nodes, in part because they are computationally expensive and memory intensive.Source: §1 · p. 1
  • MILE combines repeated graph coarsening, base embedding on the coarsest graph, and learned graph-convolution refinement to the original graph.The framework is designed to work with existing embedding methods without modifying them.Source: §1 · p. 1
  • MILE improves scalability by up to 30-fold by reducing embedding methods’ running time and memory consumption.Source: §1 · p. 1
  • Embedding quality improves in many cases with MILE, sometimes by more than 10%.Source: §1 · p. 2

2 Related Work

Prior network embedding work spans random-walk, proximity-preservation, neural-network, and matrix-factorization methods. Few efforts address scalability, and the closest work, HARP, differs from MILE in both focus and generality.

2 Related Work

  • DeepWalk and Node2Vec use random walks and Skip Gram, LINE preserves first- and second-order proximities, SDNE uses deep neural networks, and GraRep and NetMF use matrix factorization.Source: §2 · p. 2
  • Earlier scalability efforts are method-specific and limited to moderately sized datasets, but could potentially complement MILE.Source: §2 · p. 2
  • HARP seeks better embeddings through iterative learning, whereas MILE targets scalable, embedding-method-agnostic use without modifying base methods.HARP’s learned initialization adds computational overhead, and extending it to other embedding techniques is not straightforward.Source: §2 · p. 2

3 Problem Formulation

The paper formulates graph embedding as mapping a graph’s adjacency matrix to lower-dimensional node representations. Its goal is to make an existing embedding method more scalable without sacrificing embedding quality.

3 Problem Formulation

  • Graph embedding learns a d-dimensional vector for each node so that graph properties are best preserved.Source: §3 · p. 2
  • An embedding method maps the adjacency matrix or graph to a lower-dimensional matrix, and the paper seeks to speed up existing methods without sacrificing quality.Source: §3 · p. 2
  • Given a graph and an embedding method, the objective is a more scalable method that produces embeddings of comparable or better quality.Source: §3 · p. 2

4 Methodology

MILE coarsens a graph, embeds its coarsest version with an existing method, and refines those embeddings back to the original graph. Its hybrid matching and learned graph-convolution refinement are intended to preserve structure while making embedding scalable.

4 Methodology

Graph Coarsening

  • Hybrid coarsening combines SEM, which matches nodes with the same neighborhoods, and NHEM, which matches along normalized heavy edges.Matched nodes collapse into supernodes, while unmatched nodes are copied forward; the approach is intended to retain global graph structure.Source: Graph Coarsening · p. 3
  • Coarsening level depends on the application and graph, with 2–4 levels usually balancing quality and speed for graphs under 1 million nodes.For graphs over 1 million nodes, quality tends to remain high at 6–8 levels while speedup increases.Source: Graph Coarsening · p. 4

Base Embedding on Coarsened Graph

Refinement of Embeddings

  • Refinement projects coarse embeddings to the finer graph, then uses a GCN to adjust them according to the finer graph’s structure.Simple projection alone can leave nodes collapsed into one supernode with identical embeddings.Source: Refinement of Embeddings · pp. 4, 6
  • The GCN propagates embeddings through the renormalized adjacency matrix, with each layer aggregating structural information from another hop.The paper reports that two layers worked best in practice.Source: Refinement of Embeddings · p. 5
  • MILE avoids double-base training’s extra coarsening and embedding by using a copied coarsest graph, keeping the paired embeddings in the same space.The alternative can incur overhead and produce independently learned embedding spaces that differ by orthogonal transformations.Source: Refinement of Embeddings · p. 5
  • The refinement model is trained on the coarsest graph and reuses its learned parameters across levels; shared parameters do better than alternatives during refinement.Training minimizes the difference between generated and refinement-model embeddings, and refinement uses sparse matrix multiplications.Source: Refinement of Embeddings · pp. 5–6

5 Experiments and Analysis

Experiments across real-world graph datasets show that MILE improves embedding scalability and often embedding quality across multiple base methods and downstream tasks. Comparisons also report benefits on Yelp, memory use, HARP, and Pytorch-biggraph.

5 Experiments and Analysis

  • The evaluation uses several base-embedding families and assesses embedding quality through multi-label node classification and link prediction.Experiments use real-world datasets; node classification reports average Micro-F1 and Macro-F1 from 10-fold cross-validation, while link prediction reports average AUROC from 5-fold cross-validation.Source: §5 · p. 6

MILE Framework Performance

  • At higher coarsening levels, MILE achieves up to 113× speedup for link prediction while quality remains comparable or improves, and node-classification speedups reach 14.4× with comparable Micro-F1.For node classification, single-level coarsening yields 1.5×–3.4× speedups on PPI, Blog, and Flickr; on YouTube, higher levels produce more than 10× speedups for several methods.Source: MILE Framework Performance · p. 7, Figure 4 · p. 8, Figure 5 · p. 8
  • For node classification, low coarsening levels often improve embedding quality, while higher levels trade some quality for speed; link-prediction AUROC also often improves as coarsening increases.On YouTube, MILE (DeepWalk) at m=1 raises Micro-F1 by 5.3% while taking half the original time; at m=7 it remains better than DeepWalk with 13× speedup.Source: MILE Framework Performance · pp. 7, 9

MILE: Large Graph Embedding

  • On Yelp, MILE with m=4 raises DeepWalk Micro-F1 from 0.640 to 0.643 and Line from 0.625 to 0.642, with speedups around 1.6×.Original DeepWalk and Line each take more than 80 hours; increasing DeepWalk coarsening from level 4 to 22 cuts runtime from 53 hours to 2 hours as Micro-F1 falls from 0.643 to 0.634.Source: MILE: Large Graph Embedding · p. 9, Figure 6 · p. 9

Memory Consumption

  • On Blog, one coarsening level reduces GraRep and NetMF memory consumption by 64% and 42%, respectively, with reductions continuing through level 4.At level 4, memory use is mainly from storing the graph and embeddings; the objective matrix dimensions nearly halve after one coarsening level.Source: Memory Consumption · pp. 9–10, Figure 7 · p. 9

Comparing MILE with HARP

  • MILE produces comparable-quality embeddings to HARP and is significantly faster on all four datasets, including a 31× speedup on YouTube.MILE performs much better than HARP on PPI and Blog, marginally better on Flickr, and marginally worse on YouTube.Source: Comparing MILE with HARP · p. 10, Table 3 · p. 10

Comparing MILE with Pytorch-biggraph

6 MILE Drilldown

The MILE variants test alternative coarsening and refinement choices against the proposed framework. Results favor its matching and trained graph-convolution refinement, while GraphSAGE and double-base refinement perform worse.

Results of MILE-variants

  • Across datasets and base methods, MILE consistently produces higher Micro-F1 than random matching, which is only slightly faster.The comparison covers both DeepWalk and NetMF base embeddings.Source: Results of MILE-variants · p. 11
  • Simple projection, neighborhood averaging, and untrained refinement perform much worse than MILE, supporting the importance of learning graph-specific refinement parameters.Simple projection copies super-node embeddings to original nodes; averaging propagates weighted neighborhood embeddings, while the untrained variant uses fixed randomly generated parameters.Source: Results of MILE-variants · p. 11, Design Choices · p. 11
  • Replacing MILE’s graph-convolution refinement with GraphSAGE yields lower performance and greater computational cost.The reported added cost is partly attributed to GraphSAGE’s concatenation-based propagation and higher model complexity.Source: Results of MILE-variants · p. 11, Design Choices · p. 11
  • MILE-2base performs worse than MILE; the authors attribute the gap as likely due to level-m and level-(m+1) embeddings occupying different spaces.The additional base-embedding round also adds overhead: on YouTube, MILE-2base takes 1.6 times as long as MILE.Source: Results of MILE-variants · pp. 11–12, Design Choices · p. 11, Table 4 · p. 11

7 Conclusion

MILE applies existing graph-embedding methods as black boxes within a multi-level framework, improving scalability without modifying those methods. It reduces runtime and memory use and often improves embedding quality.

6 Conclusion

  • MILE is a multi-level framework for scaling graph-embedding techniques without modifying them.It incorporates existing methods as black boxes.Source: §7 · p. 12
  • The framework reduces running time and memory consumption, while often improving node-embedding quality.Source: §7 · p. 12
  • MILE learns a refinement strategy that depends on both graph properties and the embedding method in use.Source: §7 · p. 12

Related papers

Loading 1802.09612v2…