Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, existing graph embedding models either fail to incorporate node attribute information during training or suffer from node attribute noise, which compromises the accuracy. Moreover, very few of them scale to large graphs due to their high computational complexity and memory usage. In this paper we propose GraphZoom, a multi-level framework for improving both accuracy and scalability of unsupervised graph embedding algorithms. GraphZoom first performs graph fusion to generate a new graph that effectively encodes the topology of the original graph and the node attribute information. This fused graph is then repeatedly coarsened into a much smaller graph by merging nodes with high spectral similarities. GraphZoom allows any existing embedding methods to be applied to the coarsened graph, before it progressively refine the embeddings obtained at the coarsest level to increasingly finer graphs. We have evaluated our approach on a number of popular graph datasets for both transductive and inductive tasks. Our experiments show that GraphZoom increases the classification accuracy and significantly reduces the run time compared to state-of-the-art unsupervised embedding methods.
Summary: This paper proposes GraphZoom, a framework for augmenting unsupervised graph embedding methods by (a) fusing feature information into the graph topology, (b) learning embeddings on a coarsened graph, and (c) refining the coarsened embeddings to obtain embeddings for the original graph nodes. In particular, a nearest neighbor graph over node features is computed and this adjacency matrix is linearly combined with the original adjacency matrix to obtain a graph with feature information "fused in". The graph is then coarsened using a spectral approach, embeddings are learned on the coarsened graph (via any strategy), and the embeddings are then refined back to the original nodes (again using a spectral approach). The authors take care to heed the advice of Maehara et al. and remove high-frequency information from the features.
Assessment: Overall, this is a borderline contribution with some interesting motivation, original ideas, and sound derivations. However, the primary limitation of this work is the empirical comparison. First, the empirical comparison includes DeepWalk and GraphSAGE as the two base models, and while these are reasonable models, they are known to no longer be state of the art in this area (e.g., see https://arxiv.org/pdf/1809.10341.pdf). It would be more appropriate to include a more recent and better performing method (e.g., DGI; linked previously), as the reported numbers are very far from state-of-the-art. In addition---and perhaps a more concerning issue---is that seems that a randomly initialized GCN can obtain similar or superior performance compared to the numbers reported in this work (again, see the DGI paper linked above). While it is possible that GraphZoom+DGI or GraphZoom+[some other more recent method] could achieve stronger results, the fact that the current results seem to be below performance of a randomly initialized GCN is a major issue. Stronger empirical results with better baselines and base models would drastically improve the paper. 
As another point regarding the empirical results, the datasets used are known to be problematic (e.g., see https://arxiv.org/abs/1811.05868). If these datasets are used, then multiple random splits should be employed and more robust summary statistics should be reported. 
Regarding the fusion step, there were also two points that should be addressed in the paper: 
1) It seems that this fusion setup is assuming that the network exhibits homophily (i.e., it assumes that nearby nodes have similar features). This is common in many networks (e.g., the benchmarks that are analyzed) but not always the case. Some commentary on when (if ever) this fusion process might *not* be appropriate would improve the paper.
2) The authors state the they use the coarsening process to compute the nearest neighbor graph in order to avoid the quadratic time complexity. However, there are numerous well-established approaches to deal with this issues (e.g., locality sensitive hashing). Why was one of these standard approaches not employed?
Reasons to accept:
- Original and well-motivated idea
- Clearly written paper
Reasons to reject:
- Problematic empirical evaluation (e.g., lacking recent baselines)
- Several performance numbers appear to be below random GCN baseline performance
- General applicability of the approach (e.g., to non-homophilous networks) is not clear