Parallel Computation of Graph Embeddings

Chi Thang Duong 1 Hongzhi Yin 2 Thanh Dat Hoang 3 Truong Giang Le Ba 3 Matthias Weidlich 4 Quoc Viet Hung Nguyen 5 Karl Aberer 1 1 EPFL 2 The University of Queensland 3 HUST 5 Griffith University 4 Humboldt-Universit at zu Berlin Abstract Graph embedding aims at learning a vector-based representation of vertices that incorporates the structure of the graph. This representation then enables inference of graph properties. Existing graph embedding techniques, however, do not scale well to large graphs. We therefore propose a framework for parallel computation of a graph embedding using a cluster of compute nodes with resource constraints. We show how to distribute any existing embedding technique by first splitting a graph for any given set of constrained compute nodes and then reconciling the embedding spaces derived for these sub-graphs. We also propose a new way to evaluate the quality of graph embeddings that is independent of a specific inference task. Based thereon, we give a formal bound on the difference between the embeddings derived by centralised and parallel computation. Experimental results illustrate that our approach for parallel computation scales well, while largely maintaining the embedding quality. 1 Introduction Graphs are a natural representation of relations between entities in complex systems, such as social networks or information networks. To enable inference on graphs, a graph embedding may be learned.