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.
In this submission, the authors propose a three-stage framework for large-scale graph embedding. The proposed method first constructs a small graph by graph coarsening, then applies any existing graph embedding method, and last refines the learned embeddings. It is useful, however, the experimental results are not convincing and cannot support the authors' claims about the proposed method.
First, in many places, the authors claim that the embedding quality of the proposed method is improved. For example, the last sentence of Section 1, and "MILE improves quality" paragraph on Page 7. However, the experimental results fail to support this. As the proposed method is for the large-scale graph, let's focus on the results of YouTube dataset and Yelp dataset first. For Youtube dataset ((d) of Table 2), when m is set to be 8, for all the cases, the performance drops. For Yelp dataset (Figure 3), the authors do not provide Micro-f1 for the original graph (m = 0) or m = 1, 2, so it is hard or impossible to demonstrate that the quality of the proposed method is still good. 
Second, the comparison with existing methods is not sufficient. For the most important Yelp dataset (as this dataset fits the motivation scenario (large-scale graph) of this submission), the authors fail to report any comparison. Thus it might not be weak to demonstrate the benefit of the proposed method.
Third, some experiment details are missing. For example, how the authors compute the running time of the proposed method? All the three stages are included? How the authors implement the existing methods? Are these implementations good enough to ensure a fair comparison? 
*******
Some other questions:
a) On page 2, the authors mention that the proposed method "can be easily extended to directed graph". However, based on my understanding, directly graph will affect both the graph coarsening and embedding refining steps, and it seems not so easy to extend. Do the authors have the solution and experiments for directed graph? It would be interesting to see such results, which enlarges the application scope of the proposed method.
b) The toy example on page 3 is very clear. However, for real-world graphs, does the proposed graph coarsening work well? For example, one property the proposed method utilizes is "structurally equivalent". What is the percentage of the nodes that can have such property for real-world graphs? 
********
Some other comments:
Generally speaking, this submission studies a very practical task. Although the authors claim that the proposed method has great efficiency while the embedding quality is comparable good or even better than the existing methods, I think that there is an efficiency-quality trade-off based on the experimental results in this submission. When m increases, the graph coarsening step causes more information loss, and thus the quality may decrease. Embedding refining step can be regarded as a procedure to reduce such information loss, but may not improve the embedding quality better than the original graph. So to me, it would be more meaningful to study such efficiency-quality trade-off for large-scale graph embedding.