GraphZoom: A Multi-level Spectral Approach for Accurate and Scalable Graph Embedding
Authors: Chenhui Deng
Zhiqiang Zhao
Yongyu Wang
Zhiru Zhang
Zhuo Feng
Venue:  (2020)
Keywords: graph embedding
unsupervised learning
multi-level optimization
spectral graph theory

Abstract: 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 much smaller graphs 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 can substantially increase the classification accuracy and significantly accelerate the entire graph embedding process by up to $40.8 \times$, when compared to the  state-of-the-art unsupervised embedding methods. 

Published as a conference paper at ICLR 2020
GRAPHZOOM: A MULTI-LEVEL SPECTRAL APPROACH FOR ACCURATE AND SCALABLE GRAPH EMBEDDING
Chenhui Deng"
Zhiqiang Zhao" Michigan Technological University, Houghton, USA qzzhao@mtu.cc edu
Cornell University, Ithaca, USA cd5748corne11..em edu
Yongyu Wang
Zhiru Zhang
Michigan Technological University, Houghton, USA yongyuwentu.c edu
Cornell University, Ithaca, USA
zhiruz@cornell.ee
Zhuo Feng
Stevens Institute of Technology, Hoboken, USA afeng12 (enngg2@steeess... edu
ABSTRACT
Graph embedding techniques have been increasingly deployed in a multitude of different applications that involve learning on non-Euclidean data. However, ex- isting graph embedding models either fail to incorporate node attribute informa- tion 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 com- putational complexity and memory usage. In this paper we propose GraphZoom. multi-level framework for improving both accuracy and scalability of unsuper- vised graph embedding algorithms[] GraphZoom first performs graph fusion to generate new graph that effectively encodes the topology of the original graph and the node attribute information. This fused graph is then repeatedly coars- ened into much smaller graphs by merging nodes with high spectral similarities. GraphZoom allows any existing embedding methods to be applied to the coars- ened 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 can substantially increase the classification accuracy and significantly accelerate the entire graph embedding process by up to 40.8 x, when compared to the state-of-the-an unsupervised embedding methods.
INTRODUCTION
Recent years have seen a surge interest in graph embedding, which aims to encode nodes, edges, or (sub)graphs into low dimensional vectors that maximally preserve graph structural information.
Graph embedding techniques have shown promising results for various applications such as ver- tex classification, link prediction, and community detection (Zhou et al., 2018); (Cai et al. 2018); (Goyal Ferraral 2018). However, current graph embedding methods have several drawbacks in terms of either accuracy scalability. On the one hand, random-wald -ainn--wlkl-basssse based embedding algorithms, such as DeepWalk (Perozzi et al. 2014) and node2vec (Grover & Leskoved (2016), attempt to embed graph based on its topology without incorporating node attribute information, which limits their embedding power. Later, graph convolutional networks (GCN) are developed with the basic notion that node embeddings should be smoothed over the entire graph (Kipt & Welling. 2016). While GCN leverages both topology and node attribute information for simplified graph convolution in each layer, it may suffer from high-frequency noise the initial node features, which compromises
"Equal contributions
Source code of GraphZoom freely available at: githan.com/ccoomelllaaa/ttaaoooo

---

Published as a conference paper at ICLR 2020
the embedding quality (Maehara 2019). On the other hand, few embedding algorithms can scale well to large graphs with millions of nodes due to their high computation and storage cost (Zhang et al. 2018a). For example, graph neural networks (GNNs) such GraphSAGE (Hamilton et al. 2017 collectively aggregate feature information from the neighborhood. When stacking multiple
GNN layers, the final embedding vector of node involves the computation of a large number of in- termediate embeddings from its neighbors. This will not only cause drastic increase in the amount of computation among nodes, but also lead to high memory usage for storing the intermediate results.
In literature, increasing the accuracy and improving the scalability of graph embedding methods are largely viewed as two orthogonal problems. Hence most research efforts are devoted to addressing only one of the problems. For instance, Chen et al. (2018) and Fu et al.] (2019) proposed multi- level methods to obtain high-quality embeddings by training unsupervised models at every level; but their techniques do not improve scalability due to the additional training overhead. [iian et al. (2018) developed a heuristic algorithm to coarsen the graph by merging nodes with similar local structures. They use GCN to refine the embedding results on the coarsened graphs, which is not only time consuming to train but also potentially degrading accuracy when the number of GCN layers increases. More recently, Akbas & Aktas (2019) proposed similar strategy to coarsen the graph, where certain useful structural properties of the graph are preserved (e.g.. local neighborhood proximity). However, this work lacks proper refinement methods to improve the embedding quality.
In this paper we propose GraphZZoom a multi-level spectral approach to enhancing both the quality and scalability of unsupervised graph embedding methods. More concretely, GraphZoom consists of four major kernels: (1) graph fusion, (2) spectral graph coarsening, (3) graph embedding, and (4) embedding refinement. The graph fusion kernel first converts the node feature matrix into feature graph and then fuses it with the original topology graph. The fused graph provides richer information to the ensuing graph embedding step to achieve higher accuracy. Spectral graph coarsening produces a series of successively coarsened graphs by merging nodes based on their spectral similarities. We show that our coarsening algorithm can effectively and efficiently retain the first few eigenvectors of the graph Laplacian matrix, which is critical for preserving the key graph structures. During the graph embedding step, any of the existing unsupervised graph embedding techniques can be applied to obtain node embeddings for the graph at the coarsest level. Embedding refinement is then employed to refine the embeddings back to the original graph by applying a proper graph filter to ensure embeddings smoothed over the graph.
We evaluate the proposed GraphZoom framework on three transductive benchmarks: Cora, Citeseer and Pubmed citation networks as well as two inductive dataset: PPI and Reddit for vertex classifi- cation task. We further test the scalability of our approach on friendster dataset, which contains 8 million nodes and 400 million edges. Our experiments show that GraphZoom can improve the clas- sification accuracy over all baseline embedding methods for both transductive and inductive tasks. Our main technical contributions are summarized as follows:
GraphZoom generates high-quality embeddings. We propose novel algorithms to encode graph structures and node attribute information in a fused graph and exploit graph filtering during finement to remove high-frequency noise. This results in a relative increase of the embedding accuracy over the prior arts by up 19.4% while reducing the execution time by at least 2x.
GraphZoom improves scalability. Our approach can significantly reduce the embedding run time by effectively coarsening the graph without losing the key spectral properties. Experiments show that GraphZoom can accelerate the entire embedding process by up to 40.8x while produc- ing a similar or better accuracy than state-of-the-ar techniques.
GraphZoom is highly composable. Our framework is agnostic to underlying graph embedding techniques. Any of the existing unsupervised embedding methods, either transductive or inductive, can be incorporated by GraphZoom in a auug-nnd-play manner.
2 RELATED WORK
There is a large and active body of research on multi-level graph embedding and graph filtering. from which GraphZoom draws inspiration to boost the performance and speed of unsupervised
IIn this work, we do not attempt to preserve node label information in the coarsened graph. Nonetheless, we helieve that our approach can be extended to support supervised embedding models such as GAT (Gulcehre al. 2019) and PPNP (Klicpera et al. (2019), as briefly discussed in Section
2

---

Published as a conference paper at ICLR 2020
embedding methods. Due to the space limitation, only summarize some of the recent efforts in these two areas.
Multi-level graph embedding attempts to coarsen the original graph into series of smaller graphs with decreasing size where existing or new graph embedding techniques can be applied at different coarsening levels. For example, Chen al. 20188; Lin et al. (2019) generate hierarchy of coars- ened graphs and perform embedding from the coarsest level to the original one. Fu et al. (2019) construct and embed multi-level graphs through hierarchical, and the resulting embedding vectors are concatenated to obtain the final node embeddings for the original graph. These methods, how- ever, only focus on improving embedding quality but not the scalability. Later, /Zhang al. (2018b); Akbas & Aktas (2019) attempt to make graph embedding more scalable by only embedding on the coarsest graph. However, their methods lack proper refinement methods to generate high-quality embeddings for the original graph. [Liang et al. (2018) propose MILE, which only trains the coarsest graph to obtain coarse embeddings, and leverages GCN as refinement method to improve embed- ding quality. However, MILE requires training GCN model which is very time consuming for large graphs and leading to poor performance when multiple GCN layers are stacked together (Li et al. 2018). In contrast to the prior arts, GraphZoom is motivated by theoretical results in spectral graph embedding (Tang & Liu (011)) and practically efficient so that it can improve both accuracy and scalability of the unsupervised graph embedding tasks.
Graph filtering are direct analogs of classical filters in signal processing field, but intended for signals defined graphs. (Shuman et al. (2013) define graph filters in both vertex and spectral domains, and apply graph filter on image denoising and reconstruction tasks. Ww et al.] (2019) leverage graph filter to simplify GCN model by removing redundant computation. More recently, Maehara (2019) show the fundamental link between graph embedding and filtering by proving that GCN model implicitly exploits graph filter to remove high-fregg high-rrquency noise from the node feature matrix: filter neural network (gfNN) is then proposed to derive a stronger graph filter to improve the embedding results. Li et al. (0119) further derive two generalized graph filters and apply them on graph embedding models to improve their embedding quality for various classification tasks. In GraphZoom we adopt graph filter to properly smooth the intermediate embedding results during the iterative refinement step, which is crucial for improving the quality of the final embedding.
GRAPHZOOM FRAMEWORK
1. Graph Fusion
0g
Gg
4. Embedding Refinement
Graph w/ Embeddings
Original Graph Topology
Node Attr butes
Spectral Coarsening
3. Graph Embedding
Figure 1: Overview of the GraphZoom framework.
Figure [howws the proposed GraphZoom framework, which consists of four key phases: Phase (1) is graph fusion, which combines the node attributes and topology information of the original graph to construct a fused weighted graph; In Phase (2), spectral graph coarsening process applied to form hierarchy of coarsened fused graphs with decreasing size; In Phase (3), any of the existing graph embedding methods can be applied to the fused graph at the coarsest level: In Phase (4), the embedding vectors obtained at the coarsest level are mapped onto finer graph using the mapping
3

---

Published as a conference paper at ICLR 2020
operators determined during the coarsening phase. This is followed by a refinement (or smoothing) procedure, where the procedure in Phase (4) is applied in an iterative manner to increasingly finer graphs; Eventually the embedding vectors for the original graph obtained. In the rest of this section, we descrihe each of these four phases in more detail.
3.1 PHASE 1: GRAPH FUSION
Graph fusion aims to construct a weighted graph that has the same number of nodes as the original graph but potentially different set of edges (weights) that encapsulate the original graph topology as well as node attribute information. Specifically, given an undirected graph g = (V, E) with N = [V] nodes, its adjacency matrix Atopo E R.NN and its node attribute (feature) matrix X E N where K corresponds to the dimension of node attribute vector, graph fusion can be interpreted as a function f(-) that outputs weighted graph G fusion (V, (V,&fusson fusion)) represented by its adjacency matrix A fetion E R XN namely, A fusson- f(Aropo, X).
We first convert the initial attribute matrix X into a weighted node attribute graph Geat = (V, feat) by generating k-nearest- neighbr (kNN) graph based on the 1 -nrom distance between the at- tribute vectors of each node pair. A straightforward implementation requires comparing all possible node pairs and then selecting top-k nearest neighbors. However, such a naive approach has a worst- case time complexity of O(N)), which certainly does not scale to large graphs. Our goal is to construct the attribute graph in nearly linear time by leveraging an efficient spectral graph coarsen- approach starts with coarsening the original graph G to obtain a substantially reduced graph that has much fewer nodes with an O(EE) time complexity. Note that this procedure bears similarity to spectral graph clustering, which aims to group nodes into clusters of high conductance (Peng et al., 2015). Once the node clusters are formed through spectral coarsening, we can select the top-k nearest neighbors within each cluster with O (M²) comparisons, where M is the average node count per cluster. Since we have roughly N/M clusters, the time complexity for constructing the approximate kNN graph is OM..). When proper coarsening ratio is chosen where M < N (c.g., M = 50), the overall time complexity will become almost linear.
ing scheme that is described in more detail in Section 3.2 More specifically,
After the attribute graph is formed, we assign weight to each edge based on the cosine similarity between the attribute vectors of the two incident nodes, namely Wi. = -X.:,X where X and X,,: are the attribute vectors of nodes i and j. Finally, we can construct the fused graph by combining the topology graph and the attribute graph using a weighted sum: Afusion Atopo + 3 33Afeet. where 3 allows us to balance the topological and node attribute information during the fusion process. This fused graph can be fed into any downstream graph embedding procedures.
3.2 PHASE 2: SPECTRAL COARSENING
Graph coarsening via global spectral embedding. To reduce the size of the original graph while preserving important spectral properties (e.g., the first few eigenvalues and eigenvectors of the graph Laplacian matrix F). a straightforward way is to first embed the graph into a k-dimensional space using the first k eigenvectors of the graph Laplacian matrix, which is also known as the spectral graph embedding technique (Belkin & Niyogil 2003; Peng et al.] 2013). Next, the graph nodes that are close each other in the low-dimensional embedding space can be aggregated to form the coarse-level nodes and subsequently the reduced graph. However, it is very costly to calculate the eigenvectors of the original graph Laplacian, especially for very large graphs.
Graph coarsening via local spectral embedding. In this work, we leverage an efficient yet ef- fective local spectral embedding scheme identify node clusters based on emerging graph signal processing techniques (Shuman et al., 2013). There are obvious analogies between the traditional signal processing (Fourier analysis) and graph signal processing:
(1) The signals different time points in classical Fourier analysis correspond to the signals at different nodes in an undirected graph; (2) The more slowly oscillating functions in time domain correspond to the graph Laplacian eigenvectors associated with lower eigenvalues or the more slowly varying (smoother) components across the graph. Instead of directly using the first few eigenvectors of the original graph Laplacian,
'I "pplacaa matrix I. is defined as J. D A, where D is degree matrix and A is adjacency matrix.
4

---

Published as a conference paper at ICLR 2020
apply the simple smoothing (low-pass graph filtering) function to k random vectors to obtain smoothed vectors for k-dimensional graph embedding, which can be achieved in linear time.
Consider random vector (graph signal) that is expressed with linear combination of eigenvec- tors u of the graph Laplacian. We l low-pass graph filters to quickly filter out the high-frequency components of the random graph signal or the eigenvectors corresponding to high eigenvalues of the graph Laplacian. By applying the smoothing function on œ, we obtain a smoothed vector ø, which basically the linear combination of the first few eigenvectors:
MN Cg34
smoothing
E a, N
More specifically, we apply a few (typically five to ten) Gauss-Seidel iterations for solving the linear system of equations Lgr(1) = 0 to set of t initial random vectors T = (x(1), ,...,.....,,... xx1) that are orthogonal to the all-one vector 1 satisfying 1 x0) = 0, and Lg is the Laplacian matrix of graph G or fusion.
Based on the smoothed vectors in T, we embed each node into a I-dimensional space such that nodes p and are considered spectrally similar if their low-dimensional embedding vectors 2p E R'' and Ty E R' are highly correlated. Here the node distance measured by the spectral node affinity ap.g for neighboring nodes and (Livne & Brandt 2012: Chen & Safro 2011
(Tp... T |Tp 1 T
(T Ta.) (a.) = Ex E
(x0) (1) (K)
ap.9
Once the node aggregation schemes are determined, we can easily obtain the graph mapping operator Hi+1 between two coarsening levels i and i+ 1. More precisely, H is a matrix of size (V x Ve.l (H!-") "p="))p.g 1..g = 1 if node g in graph Gj is aggregated (clustered) node p in graph Gi+1; otherwise, is set to O. Additional discussions on the properties of H15 are available in Appendix which shows this operator a surjective mapping and locality preserving.
We leverage Ha. HH. Hi for constructing a series of spectrally-reduced graphs G1,92.... Gr. Specifically, The coarser graph Laplacian Le.., can be computed by Eq. is worth noting that Go (i.e., Gynsion) is the original fused graph and (oo = N [V
3
M/
Le.. = H: Lg. Hi: H; = [ (
(3)
We emphasize that the aggregation scheme based on the above spectral node affinity caleulations will have (lincar) complexity of J([EJuston) }) and thus allow preserving the spectral (global or structural) properties of the original graph highly efficient and effective way. As suggested in (hao & Feng 2019 Loukas 2019)) spectral sparsification procedure can be applied to effectively control densities of coarse level graphs. In this work, a similarity- -waare spectral sparsification tool "GRASS" (Feng 2018) has been adopted for achieving desired graph sparsity at the coarsest level.
3.3 PHASE 3: GRAPH EMBEDDING
Embedding the Coarsest Graph. Once the coarsest graph Gi is constructed, node embeddings E; on GI can be obtained by E, (Gi), where g(-) can be any unsupervised embedding methods.
3.4 PHASE 4: EMREDDING REFINEMENT
Given E++1, the node embeddings of graph G:41 at level i + 1, we can use the corresponding projection operator Hi:1 to project E to G, which is the finer graph at level i:
E, H E+1
(4)
Due to the property of the projection operator, embedding of the node in the coarser graph will be directly copied to the nodes of the same aggregation set in the finer graph at the preceding level. In this case, spectrally- similar nodes in the finer graph will have the same embedding results they are aggregated into single node during the coarsening phase.
5

---

Published as a conference paper at ICLR 2020
To further improve the quality of the mapped embeddings, apply local refinement process motivated by Tikhonov regularization to smooth the node embeddings over the graph by minimizing the following objective:
mind E.
minl E Bi tr E,)
(5)
where L, and E; are the normalized Laplacian matrix and mapped embedding matrix of the graph at the i-th coarsening level, respectively. We obtain the refined embedding matrix E; by solving Eq. (5) Here the first term enforces the refined embeddings agree with mapped embeddings, while the second term employs Laplacian smoothing to smooth E, over the graph. By taking the derivative of the objective function in Eq. (5) and setting it to zero, we have:
E; (I
E.
where I is the identity matrix. However, obtaining refined embeddings in this manner can be very inefficient since it involves matrix inversion whose time complexity is O(N3). Instead, we exploit a more efficient spectral graph filter smooth the embeddings.
By transforming h(L) = (I + D)- into spectral domain, we obtain the graph filter: h(A) (1+ + A)- To avoid the inversion term, we approximate h(A) by its first-order Taylor expansion, namely, ((A)) 1 - A. We then generalize h(A) to h2 (A) (1 A)*, where k controls the power of graph filter. After transforming (A) into the spatial domain,
have: (..(L)
L.)*
(D-1AD + where the adjacency matrix and D is the degree matrix.
not difficult to
show that adding a proper self-loop for every node in the graph will allow hyg (L) to more effectively filter out high-frequency noise components (Machara (019) (see Appendix H Thus, modify the adjacency matrix as Á A + al, where is small value ensure every node has its own self-loop. Finally, the low-pass graph filter can utilized to smooth the mapped embedding matrix, shown in
E, = (D. (DD..AAD) A.D. 3 (D, A,D, b)* H
We iteratively apply Eq. to obtain the embeddings of the original graph (i.e., Eo). Note that our refinement stage does not involve training and can be simply considered several (sparse) matrix multiplications, which can be efficiently computed.
4 EXPERIMENTS
We have performed comparative evaluation of GraphZoom framework against several state-of-the- art unsupervised graph embedding techniques and multi-level embedding frameworks on five stan- dard graph-based datasets (transductive as well inductive). In addition, evaluate the scalability of GraphZoom on Friendster dataset, which contains 8 million nodes and 400 million edges. Finally, conduct ablation study to understand the effectiveness of the major GraphZoom kemnels.
4.1 EXPERIMENTAL SETUP
Table 1: Statisties of datasets used in our experiments.
Dataset
Type
Task
Nodes
Edges
Classes
Features
Cora
Citation network
Transductive
2,708
5,429
7
1,433
Citeseer
Citation network
Transductive
3,327
4.732
6
3,703
Pubmed
Citation network
Transductive
19,717
44,338
3
500
PPI
Biology network
Inductive
14,755
222,055
121
50
Reddit
Social network
Inductive
232,965
57,307,946
210
5,414
Friendster
Social network
Transductive
7,944.949
446.673,688
5,000
N/A
Table reports the statistics the datasets used in our experiments. We include Cora, Citeseer, Pubmed, and Friendster for evaluation transductive learning tasks, and PPI as well as
Datasets.

---

Published as a conference paper at ICLR 2020
Reddit for inductive learning. We split the training and testing data in the same way suggested in Kipf& & Welling 2016): Hamilton et al. (2017).
Transductive baseline models. A number of popular graph embedding techniques are transductive learning methods, which require all nodes in the graph be present during training. Hence such embedding models must be retrained whenever new node is added. Here we compare GraphZoom with three transductive models: Deep Walk (Perozzi et al. (014), node2vec (Grover & Leskovee) 2016), and Deep Graph Infomax (DGI) (Veličković et al. 2019 These methods have shown state- of-the-art unsupervised embedding results on the datasets used in our experiments. In addition, we compare GraphZoom with two multi-level graph embedding frameworks: HARP (Chen 2018) and MILE (Liang et al. (2018), which have reported improvement over Deep Walk and node2vec in either embedding quality or scalability.
Inductive baseline models. In contrast to transductive tasks, training an inductive graph embedding model does not require seeing the whole graph structure. Hence the resulting trained model can still be applied when new nodes are added to graph. To show GraphZoom can also enhance inductive learning, we compare it against GraphS (Hamilton et al. 2017) using four different aggregation functions including GCN, mean, LSTM, and pooling.
More details of datasets and baselines are available in Appendix A and We optimize hyperpa- rameters of DeepWalk, node2vec, DGI, and GraphSAGE to achieve highest possible accuracy on original datasets; we then choose the same hyperparameters to embed the coarsened graph in HARP, MILE, and GraphZoom. We run all the experiments on Linux machine with Intel Xeon Gold 6242 CPU (32 cores @ 2.40GHz) and 384 GB of RAM.
4.2 PERFORMANCE AND SCALABILITY OF GRAPHZOOM
Since HARP and MILE only support transductive learning, we compare them with GraphZoom using DeepWalk, node2vec, and DGI /Veličković et al.] (019) embedding kernels. For inductive tasks, we compare GraphZoom with GraphSAGE using four different aggregation functions.
Tables and report the mean classification accuracy for the transductive task and micro-averaged F1 score for the inductive task, respectively, as well as the execution time for all baselines and Graph- Zoom. Specifically, we use the CPU time for graph embedding as the execution time of Deep Walk, node2vec, DGI, and GraphSAGE. We further measure the execution time of HARP and MILE by summing up CPU time for graph coarsening, graph embedding, and embedding refinement. Simi- larly, we add up the CPU time for graph fusion, graph coarsening, graph embedding, and embedding refinement as the execution time of GraphZoom. In regard hyperparameters, we use 10 walks with walk length of 80, a window size of 10, and an embedding dimension of 128 for both Deep Walk and node2vec; we further set the return parameter p and the in-out parameter y in node2vec as 1.0 and 0.5, respectively. Moreover, 0.001 and an embedding dimension of 512. Apropos the configuration of GraphSAGE, we train a two-layer model for one epoch, with a learning rate of 0.00001, an embedding dimension of 128, and a batch size of 256.
DeepWalk,
choose early stopping strategy for DGI with a learning rate of
Comparing GraphZoom with baseline embedding methods. We show the results of GraphZoom with three coarsening levels for transductive learning and two levels for inductive learning. The size of coarsened graphs and results with larger coarsening level are available in Appendix [D] Figure (blue eurve), and the Appendix Our results demonstrate that GraphZoom is agnostic to underlying embedding methods and capable of boosting the accuracy and speed of state-of-the-an unsupervised embedding methods on various datasets.
More specifically, for transductive learning tasks, GraphZoom improves classification accuracy upon both Deep Walk and node2vee by a relative gain of 8.3%, 10.4%. and 19.4%[[oo. Cora, Pubmed, and Citeseer, respectively, while achieving up to 40.8x run-time reduction. In regard to comparing with DGI, GraphZoom achieves comparable or better accuracy with speedup up to 11.2x. Similarly, GraphZoom outperforms all the baselines by margin of 3.4% and 3.3% on PPI and Reddit for inductive learning tasks, respectively, with speedup up to 7.6x. These results indicate that our
*DGI also supports inductive tasks, although the authors have only released the source code for transductive learning at wwwggih.coo/Peeaaaa. V-DDG] as of the date of this experiment.
5G7oom(2VV, (=l) improves over node2vee Citeseer by 19.4% (54.7 44.8)/45.8.
7

---

Published as a conference paper at ICLR 2020
Table 2: Summary of results in terms of mean classification accuracy and CPU time for transduc- tive tasks, on Cora, Citeseer, and Pubmed datasets DW, N2V, and GZoom denote DeepWalk, node2vec, and GraphZoom, respectively; means the graph coarsening level; GZoom_F+Mi F.MILE rep- resents the best performance achieved when adding GraphZoom fusion kernll into MILE.
Cora
Citeseer
Pubmed
Method
Accuracy($5)
Time(sets)
Accuracy(5)) (%)
Time(secs)
Accuracy( (b)
Time(mins)
Welk
71.4
97.8
47.0
120.0
69.9
14.1
HARP(DW)
296.7 (0.3x)
43.2
272.4 (0.4x)
70.6
33.9 (0.4x)
MILE(DW, (=1)
71.9
68.7 (1.4x)
46.5
53.7 (2.2x)
69.6
7.0 (2.0x)
MILE(DW, (=2)
71.3
30,9 (3.2x)
47.3
22.5 (5.3x)
66.7
4.4 (2.3x)
MILB(DW; (=3)
70.6
15.9 (6.1x)
47.1
9.9 (12.1x)
64.5
(5.8x)
G7oom F+MILF(DW)
73.8
70.6 (1.4x)
48.9
24.7 (4.9x)
72.1
7.0 (2.0x)
GZo, [=1)
76.9
39.6 (2.5x)
49.7
19.6 (2.1x)
75.3
4.0 (3.6x)
GZo, (=2)
77.3
15.6 (6.3x)
6.7 (6.0x)
75.9
1.7 (8.3x)
GZoom(DW, /=3)
75.1
2.4 (40.8x)
49.5
1.3 (30.8x)
77.2
0.6 (23.5x)
node2vee
71.5
119.7
45.8
126.9
71.3
15.6
HARP(N2V)
72.3
171.0 (0.7x)
44,8
174.3 (0.7%)
70.1
46.1 (0.3x)
MILE(N2V, 1=1)
72.1
57.3 (2.1x)
46.1
60.9 x2.1x)
70.8
7.3 (2.1
MILE(N2Y, (=2)
71.8
30,0 (4.0x)
45.7
28.8 (4.4x)
67.3
(3.6x)
MILB(N2V, (=3)
68.5
16.5 (7.2x)
45.2
15.6 (8.1x)
61.8
1.8 (8.0x)
GZoom_ (C00O_F=MMLEEN2/)
74.3
59.2 (2.0x)
48.3
62.3 (2.0x)
72.9
7.3 (2.1
(N2,
77.3
43.5 (2.8x)
54.7
38.1 (3.3x)
77.0
3.0 (5.2x)
(NZom
77.0
13,5 (8.9x)
51.7
15.3 (8.3x)
77.8
1.5 (10.4x)
5ZZoomN2V
75.3
3,0 (39.9x)
50.7
4.5 (28.2x)
77.4
0,4 (39.0x)
DGI
71.8
76.8
MILE(DGI, [=1)
80.9
45,9 (1.9x)
69.9
53,2 (1.8x)
76.1
10.4 (2.3x)
MILE(DGI, 1=2)
80.3
27.5 (3.3x)
69.2
31.1 (3.0x)
74.3
4.3 (5.5x)
MILE/DGII, I=3)
79.2
15.6 (4.4x)
67.9
x5.
74.4
(8.8x)
GZoom F+MILE(DGI)
81.3
45.9 (1.9x)
70.4
$2.3 (18x)
75.9
10.4 (2.3x)
GZoom(DGI, (=1)
83.9
27.3 (3.3x)
71.1
29.3 (3.2x)
77.1
9.6 (2.5x)
GZoom(DGI, (=2)
15.2 (5.9x)
70.8
17.9 (5.3x)
77.6
4.4 (5.4x)
GZoom(DGI, (=3)
83.5
8.0 (11.2x)
70.7
9.6 (9.8x)
76.9
2.1 (11.2x)
multi-level spectral approach improves both embedding speed and quality GraphZoom runs much faster since we only train the embedding model on the smallest fused graph at the coarsest level. In addition to reducing the graph size, coarsening method further filters out redundant information from the original graph while preserving key spectral properties for the embedding. Hence we also observe improved embedding quality in terms of classification accuracy.
Comparing GraphZoom with multi-level frameworks. As shown in Table 2 HARP slightly improves the accuracy in several cases but increases the CPU time. Although MILE improves both accuracy and speed over few baseline embedding methods, the performance of MILE be- comes worse with increasing coarsening levels. For instance, the classification accuracy of MILE drops from 0.708 to 0.618 on Pubmed dataset with node2vec as the embedding kemel. GraphZoom achieves a better accuracy and speedup compared to MILE with the same coarsening level across all datasets. Moreover, when increasing the coarsening levels, namely, decreasing number of nodes on the coarsened graph, GraphZoom still produces comparable or even better embedding accuracy with much shorter CPU times. This further confirms GraphZoom retain the key graph structure information to be utilized by underlying embedding models boost embedding quality. More re- non-attributed graph for both node classification and link prediction tasks
sults of GraphZoom are available in Appendix
GraphZoom for large graph embedding. To show GraphZoom significantly improve per- formance and scalability of underlying embedding model on large graph, we test GraphZoom and MILE on Friendster dataset, which contains million nodes and 400 million edges. For both cases,
8

---

Published as a conference paper at ICLR 2020
Table 3: Summary results in terms of micro-averaged Fl score and CPU time for inductive tasks, on PPI and Reddit datasets - The baselines are GraphSAGE with four different aggregation functions. GZoom and GSAGE denote GraphZoom and GraphSAGE, respectively; means the graph coarsening level.
PPI
Reddit
Method
Micro-F1
Time(mins)
Micro-F1
Time(hours)
GraphSAGE--GN
0.601
9.6
0.908
10.1
GZoom(GSAGE-GGGO (=1)
0.621
4.8 (2.0x)
0.923
3.4 (3.0x)
GZoom(GSAAE-GGNN (=2)
0.612
1.8 (5.2x)
0.917
1.6 (6.3x)
GraphSAGF-mman
0.598
11.1
0.897
8.1
GZooom(GSAGE-mmann, (=1)
0.614
5.2 (2.2x)
0.925
2.6 (3.1x)
GZoom(GSAAGE-menn, (=2)
0.617
1.8 (6.2x)
0.919
1.2 (6.8x)
GraphSAGE-LSTM
0.596
387.3
0.907
92.2
G2o0m((GAAGB-LSTTM, (=1)
0.614
151.8 (2.6x)
0.920
39.8 (2.3x)
GZ00mm(SA4GE-LSTMM (=2)
0.615
52.5 (7.4x)
0.917
14.5 (6.4x)
GraphSAGGE-pol
0.602
144.9
0.892
84.3
GZoom(GSAAGE-poo.. 1=1)
0.611
66.0 (2.2x)
0.921
27.0 (3.1x)
GZooom(GSAGE-pool.. (=2)
0.614
23.4 (6.2x)
0.912
12.4 (6.8x)
GraphZoom(DW)
MILE(DW)
DeepWalk Friendster (Speedup)
Friendster (Micro-F1)
CPU time Speedup
0.6
100
Miero-F1
0.4
50
0.2
0
4
5
Coarsening Level
Coursering Level
Figure 2: Comparisons of GraphZoom and MILE Friendster dataset.
we use WeepWalk Walk as the embedding kernel. shown in Figure GraphZoom drastically boosts the Micro-F1 score up 47.6% compared MILE and 49.9% compared to DeepWalk with speedup up to 119.8x. When increasing the coarsening level, GraphZoom achieves a higher speedup while the embedding accuracy decreases gracefully. This shows the key strength of GraphZoom: it can effectively coarsen a large graph by merging many redundant nodes that are spectrally similar, thus preserving the graph spectral (structural) properties that are important the underlying embedding model. When applying basic embedding model on coarsest graph, it can learn more global infor- mation from spectral domain, leading high-quality node embeddings. On the contrary, heuristic graph coarsening algorithm used in MILE fails to preserve a meaningful coarsest graph, especially when coarsening graph by large reduction ratio.
4.3 ABLATION ANALYSIS GRAPHZOOM KERNELS
To study the effectiveness of proposed GraphZoom kernels separately, compare each of them against the corresponding kernel in MILE while fixing other kernels. As shown Figure B when fixing coarsening kernel and comparing refinement kernel of GraphZoom with that of MILE, Our

---

Published as a conference paper at ICLR 2020
GZoom F GZoem_ C GZoom R (DW)
GZoom C+ MILE R (DW)
MILE C- MILE R (DW)
(Zooom C+ (Zoom (DW)
MILE C++ GZoom R (DW)
Deep
Cora (Aceuracy)
Citeseer (Accuracy)
Pubmed (Accuracy)
78
.1
50
Accuraey
74-
Accuracy
49
Accuracy 60-
48
47
70
46
2
2
3
2
5
Coursening Level
Coarsening Level
Coarsening Level
Figure 3: Comparisons of different kernel combinations in GraphZoom and MILE in classification accuracy on Cora, Citeseer, and Pubmed datasets - We choose DeepWalk (DW) as the embed- ding kernel. GZoom_F, GZoom_C, GZoom_ JR denote the fusion, coarsening, and refinement kernels proposed in GraphZoom, respectively; MILE.C and MILE.R .R denote the coarsening and refinement kernels MILE, respectively; The blue curve is basically GraphZoom and the yellow one is MILE.
finement kernel can improve embedding results upon MILE refinement kernel, especially when the coarsening level is large. This indicates that our proposed graph filter in refinement kernel can suc- cessfully filter out high-frequency noise from the graph to improve embedding quality. Similarly, when comparing coarsening kernels GraphZoom and MILE with the refinement kernel fixed, GraphZoom coarsening kernel can also improve embedding quality upon MILE coarsening kernel, which shows that our spectral graph coarsening algorithm can indeed retain key graph structure for underlying graph embedding models to exploit. When combining the GraphZoom coarsening and refinement kernels, we can achieve a better classification accuracy compared to the ones using any other kernels in MILE. This suggests that the GraphZoom coarsening and refinement kernels play useful yet distinct roles to boost embedding performance and their combination can further im- prove embedding result. Moreover, adding graph fusion improves classification accuracy by large margin, which indicates that graph fusion can properly incorporate both graph topology and node attribute information that are crucial for lifting the embedding quality of downstream embedding models. Results of each kernel CPU time and speedup comparison are available in Appendix G and Appendix !
CONCLUSIONS
This work introduces GraphZoom, multi-level framework to improve the accuracy and scalability of unsupervised graph embedding tasks. GraphZoom first fuses the node attributes and topology of the original graph to construct new weighted graph. It then employs spectral coarsening to generate a hierarchy of coarsened graphs, where embedding is performed on the smallest graph at the coarsest level. Afterwards, proper graph filters are used to iteratively refine the graph embeddings to obtain the final result. Experiments show that GraphZoom improves both classification accuracy and embedding speed on number of popular datasets. An interesting direction for future work is to derive a proper way to propagate node labels to the coarsest graph, which would allow GraphZoom to support supervised graph embedding.
ACKNOWLEDGMENTS
This work is supported in part by Semiconductor Research Corporation and DARPA, Intel Corpo- ration under the ISRA Program, and NSF Grants #1350206, #1909105, and #1618364. We would like to thank Prof. Zhengfu Xu of Michigan Technological University for his helpful discussion on the formulation of the embedding refinement problem.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Esra Akbas and Mehmet Aktas. Network Emhedding: on compression and learning. arXiv
1epprint:907.0281.. 2019.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation (NC), 15(6):1773-3366 2003.
Hongyun Cai, Vincent W Zheng, and Kevin embedding: Problems, techniques, and applications. Transactions on Knowledge and Data Engi- neering (TKDE), 3099);11111111113 2018.
Chang. A comprehensive survey of graph
Haochen Chen, Bryan Perozzi, Yifan Hu, and Steven Skiena. HARP: Hierarchical representation learning for networks. The AAAI Conference on Artificial Intelligence (AAAT), 2018
Jie Chen and Ilya Safro. Algebraic distance on graphs. SIAM Journal on Scientific Computing (SISC), 33(6)34468-3490 2011.
Zhuo Feng. Similarity spectral sparsification by edge filterin. Design Automation Confer- ence (DAC). pp. 1-6, 2018.
Guoji Fu, Chengbin Hou, and Xin Yao. Learning topological representation for networks via hier- archical sampling. arXiv preprint: w9... 06684, 2019.
Hongyang Gao and Shuiwang Ji. Graph U-Nets. International Conference Machine Learning (ICML), pp. 2083-2092, 2019.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge-Baud Based Systems (KBS), 151:78-94, 2018
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. International 2016.
Conference on Knowledge Discovery and Data mining (KDD), pp.
Caglar Gulcehre, Misha Denil, Mateusz Malinowski, Ali Razavi, Razvan Pascanu, Karl Moritz Hermann, Peter Battaglia, Victor Bapst, David Raposo, Adam Santoro, and Nando de Freitas. Hyperbolic Attention Networks. International Conference Learning Representations (ICLR), 2019. URL
wwt.tee/teoooeee wwweee/foormmiddddromoe jRqFQ
Will Hamilton, Zhitao Ying. and Jure Leskovee. Inductive representation learning on large graphs. Neural Information Processing Systems (NeurlPS), pp. 1024- 1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. The Conference on Computer Vision and Pattern Recognition (CVPR), pp- 770-778, 2016.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference Learning Representations (ICLR), 2016. URL https:
7 //openreview. www. tett:fforummi=ssSuAaeae
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural net- works with personalized pagerank for classification on graphs. International Conference on Learning Representations (ICLR), 2019. URL
Qimai Li, Zhichao Han, and Xiao Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. The AAAI Conference Artificial Intelligence (AAAT), 2018.
Qimai Li, Xiao-Ming Wu, Han Liu, Xiaotong Zhang, and Zhichao Guan. Label efficient semi- supervised learning via graph filtering. The Conference on Computer Vision and Pattern Recog- nition (CVPR), pp. 9582-9591, 2019.
Jiongqian Liang, Saket Gurukar, and Srinivasan Parthasarathy. MILE: A multi-level framework for scalable graph embedding. arXiv preprint: 1802 090.09912, 2018.
Wenging Lin, Feng He, Faqiang Zhang, Xu Cheng, and Hongyun Cai. Effective and efficient net- work embedding initialization via graph partitioning. arXiv preprint: (ooprint:190..0 10697, 2019.
11

---

Published as a conference paper at ICLR 2020
Oren E Livne and Achi Brandt. Lean Algebraic Multigrid (LAMG): Fast graph laplacian linear solver. SIAM Journal on Scientific Computing (SISC), -499222299--52, 2012.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research (JMLR), 20(116):1-42 2019.
Takanori Maehara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint: 190500955000 2019.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! The Conference on Learning Theory (COLT), pp. 1423-1455, 2015.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. DeepWalk: Online learning of social representa- tions. International Conference on Knowledge Discovery and Data mining (KDD), pp. 701-710, 2014.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending dimeeniiiiinnl data analysis to net- works and other irregular domains. Signal Processing Mugazine (SPM), 30(3):83-98, 2013.
Lei Tang and Huan Liu. Leveraging social media networks for classification. Data Mining and Knowledge Discovery (DMKD), 23(3):447-478, 2011.
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep Graph Infomax. International Conference on Learning Representations (ICLR), 2019,
Felix Wu, Tianyi Zhang. Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. International Conference on Machine Learning (ICML), pp. 6861-6871, 2019.
Jacwon Yang and Jure Leskovec. Defining and evaluating network communities based ground- truth. Knowledge and Information Systems (KAIS), 42(1):181-22 2015.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv preprint:1603 08861, 2016.
Daokun Zhang, Jie Yin, Xingquan Zhu, and Chengqi Zhang. Network representation learning: A survey. Transactions on Big Data (TBD), 2018: 8a.
Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Maosong Sun, Zhichong Fang, Bo Zhang, and Leyu Lin. COSINE: Compressive network embedding on large-scale information networks. arXiv preprint: 111..int:112..88977. 2018b.
Zhiqiang Zhao and Zhuo Feng. Efficctive-resistacee preserving spectral reduction of graphs. Design Automation Conference (DAC), pp. 1-6, 2019.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. arXiv preprint: 1reprint:1812.00 1812.08434, 2018.
12

---

Published as a conference paper at ICLR 2020
APPENDIX A DETAILS OF DATASETS
Transductive task. We follow the experiments setup in Yang et al. (2016) for three standard cita- tion network benchmark datasets: Cora, Citeseer, and Pubmed. In all these three citation networks, nodes represent documents and edges correspond to citations. Fach node has a sparse bag-of-wol oood feature vector and a class label. We allow only 20 labels per class for training and 000 labeled nodes for testing. In addition, we further evaluate on Friendster dataset (Yang & Leskovec] 2015), which contains million nodes and 400 million edges, with 2. 2.5% of the nodes used for training and 0.3% nodes for testing. In Friendster, nodes represent users and pair of nodes are linked if they are friends; each node has a class label but is not associated with a feature vector.
Inductive task. We follow Hamilton et al. (2117) for setting up experiments both protein- protein interaction (PPI) and Reddit dataset. PPI dataset consists of graphs corresponding to human tissues, where nodes are proteins and edges represent interaction effects between proteins. Reddit dataset contains nodes corresponding to users' posts: two nodes are connected through an edge the same users comment both posts. We use 60% nodes for training, 40% for testing on PPI and 65% for training and 35% for testing on Reddit.
APPENDIX B DETAILS OF BASELINES
DeepWalk Walk first generates random walks based on graph structure. Then, walks are treated sen- tences a language model and Skip-Gram model is exploited to obtain node embeddings.
node2vec is different from DeepWalk in terms of generating random walks by introducing the return parameter p and the in-out parameter g, which can combine DFS-like and BFS-like neighborhood exploration.
Deep Graph Infomax (DGT) is an unsupervised approach that generates node embeddings by max- imizing mutual information between patch representations (local information) and corresponding high-level summaries (global information) of graphs.
GraphSAGE embeds nodes in an inductive way by learning an aggregation function that aggregates node features to obtain embeddings. GraphS AGE supports four different aggregation functions: GraphSAGE-LSTI and GraphSAGE-pon
GraphSAGE-GCo GraphSAGE-ment
HARP coarsens the original graph into several levels and apply underlying embedding model to train the coarsened graph each level sequentially obtain the final embeddings on original graph. Since the coarsening level is fixed in their implementation, we run HARP in our experiments without changing the coarsening level.
MILE is the state-of-the-ar multi-level unsupervised graph embedding framework and similar to our GraphZoom framework since also contains graph coarsening and embedding refinement ker- nels. More specifically, MILE first uses its heuristic-based coarsening kernel to reduce the graph size and trains underlying unsupervised graph embedding model on coarsest graph. Then, its refinement kernel employs Graph Convolutional Network (GCN) to refine embeddings the original graph. We compare GraphZoom with MILE on various datasets, including Friendster that contains mil- lion nodes and 400 million edges (shown in Table 2 and Figure] Moreover, we further compare each kernel in GraphZoom and MILE in Figure
APPENDIX C INTEGRATE GRAPHZOOM WITH GRAPHSAGE AND DGI
As both GraphSAGE and DGI require node features for embedding coarsest graph, map the initial node feature matrix Xa to the coarsened graph by iteratively performing X;+1 f7 X.. where fr;+11 11 is the mapping operator H1 with (2 ('-oommalization per row. When applying DGI to the coarsest graph (i.e., the 1-th coarsening level), the node embeddings Et may lose local information due to the property of DGL. Inspired by skip connection (He et al., 2016) and Graph U-nets (Gao & Ji 2019), we use É, = Ex||X, as the node embeddings on the coarsest graph, where || denotes Teaturewise concatenation.
13

---

Published as a conference paper at ICLR 2020
APPENDIX D GRAPH SIZE AT DIFFERENT COARSENING LEVEL
Table 4: Number of nodes at different GraphZoom coarsening levels. GZoom-0 means GraphZoom with 0 coarsening level (i.e., without coarsening), GZoom- means GraphZoom with coarsening level and so forth. means number of nodes is less than 50.
Dataset
GZoom-0
GZoom-1
GZoom-2
GZoom-3
GZoom-4
GZoom-5
Cora
2,708
1,169
519
218
100
Citeseer
3,327
1,488
606
282
131
58
Pubmed
19,717
7,903
3,562
1,651
726
327
PPI
14,755
5,061
1,815
685
281
120
Reddit
232,965
84,562
30,738
11,598
4,757
2,117
Friendster
7,944,949
2,734,483
1,048,288
409,613
134,956
44,670
APPENDIX E
GRAPHZOOM ALGORITHM
Algorithm 1: GraphZoom algorithm
Input: Adjacency matrix Atopo IR NxN, node feature matrix X base embedding function g(-); coarsening level /
RNNK
Output: Node embedding matrix E RVD
Ao = graph-fusion Atoopo X);
for 1.../ do
A, H: spectral.caurseningg (A
end
Er g(A1);
for
= I...1 do
E. = (HL))* E;;
E = re re finement E,-1);
end
10 E E=:::
APPENDIX F SPECTRAL COARSENING
Coarsening is one type of graph reduction whose objective is to achieve computational acceleration by reducing the size (i.e., number of nodes) of the original graphs while maintaining the similar graph structure between the original graph and the reduced ones. For each coarsen level + surjection is defined between the original node set V; and the reduced node set VI-1. where each node Vi+1 corresponds a small set of adjacent vertices in the original node set V, Mapping operator Hi*1 can be defined based the mapping relationship between V, and Vi+1. Note that the operator Hi+1 (0, M is matrix containing only Os and 1s. It has following properties:
The row (column) index of H!+t! corresponds to the node index in graph G:+1 (G.).
is surjective mapping of the node where (HI )p. if node g in graph G. aggregated to super-node p graph G:+1, and (H)+)) >y' for all nodes p' {u E V. : # p).
It is Docality-preserving operator, where the coarsened version of 9; induced by the non-zero entries of (H++1) pp: is connected for each p Ve+1-
14

---

Published as a conference paper at ICLR 2020
Algorithm 2: spectral coarsening algorithm
Input: Adjacency matrix A, R TR/ [+]
R - V of the reduced graph
Output: Adjacency matrix A,+1 E
Gi+1, mapping operator H
H+t1 1
E R
V
71 = - n2 = nı;
Igraph reduction ratio] Ymmas = 1.8, 5 = 0.9; for each edge (p, q) E & do [spectral node affinity set] C x- ap,9 defined in Eq. 2
end
for each node p V, do
d(p) = (Ai) p.i dm (p) = median (((A)).. for all q E {al(p, E &&)):
if d(p) 2 8 dm (p) then
[node aggregation flag] z =p) 0;
10
else
[node aggregation flag] (p) =-1; 1;
11
end 12
13 end
y
1;
15 while < "maz do
S 0, U - 0
16
[unaggregated node set] U + De (p1=())==-1)
= =- Vp E Vi}:
17
S - E {plaps 2 8 max
max (aps),, max (ans)) Vp E Vi}; (p.s)e &
18
spp.
(q.s)E E
for each node p in SnU do if (p) = then
20
21
= arg max (m.))E E,
ap.q
22
if (q) -1 then
=(q) = 0, xx(p) = -q q
24
else if (q)) 0 then
<p)) = 4, q = Ti
26
else
z =pp) = =q)) q = =x(g); end
28
(k) = v for k = -I....,"
(k)
update smoothed vectors in T with up
30
ne ne - 1;
31
end
end
32
7 n/ 8 = 0.7
2pp) p for node E {p|=(p) = 0}
34
35 end
form Hi+1 and A based on z
36
15

---

Published as a conference paper at ICLR 2020
APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL
CPU time of GraphZoom kernels Cora
CPU time of GraphZoom kernels Citeseer
10a
10a
Single CPU time (s)
10a
30524
Emoedd
10a
Gearsening
Embeddinng
Single CPU time
10
10a
3.0
109
109
10
10-1
10
10-7
m-1
m=2
m=3
m=4
m=5
m=1
M=2
mm3
m=4
m=5
m-th coarsening level
m-th coarsening level
GraphZoom with WeepWalk embedding kernel
(b) GraphZoom with DeepWalk embedding kernel
CPU time of GraphZoom kernels Pubmed
CPU time of GraphZoom kernels Reddit
3011-0
Fuiin
10a
Fuilin
Single CPU time (s)
10a
ALLYY
Single CPU time
10a
10a
10a
MA.3
123
109
10a
1.12
10-1
m=1
m=2
m=3
m=4
mm5
m=1
m=2
m=3
m=4
m=5
m-th coarsening level
m-th coarsening level
(c) GraphZoom with Deep as embedding kernel
(d) GraphZoom with GSAGE as embedding kernel
Figure 4: CPU time of GraphZoom kernels
As shown in Figure (note that the axis is in logarithmic scale), the GraphZoom embedding kernel dominates the total CPU time, which can be more effectively reduced with greater coarsening level L. All other kernels in GraphZoom drastically reduce the total graph embedding time.
very efficient, which enable the GraphZoom framework to
APPENDIX H GRAPH FILTERS AND LAPLACIAN EIGENVALUES
Figure 5a shows the original distribution of graph Laplacian eigenvalues which also can be inter- preted frequencies in graph spectral domain (smaller eigenvalue means lower frequency). The proposed graph filter for embedding refinement (as shown in Figure can be considered as band- stop filter that passes all frequencies with the exception of those within the middle stop band that is greatly attenuated. Therefore, the band-stop filter may not be very effective for removing high- frequency noises from the graph signals. Fortunately, has been shown that by adding self-loops to each node in the graph as follows the distribution of Laplacian eigenvalues can be squeezed to the left (towards zero) (Machara 2019
+ o (shown Figure 5b 5c 5d where o 0.5, 1.0. 2.0),
By properly choosing such that large eigenvalues will mostly lie in the stop band (e.g., o 1.0, 2.0 shown in Figure [5c and (dd]. the graph filter will be able to effectively filtered out higu-freyuency components (corresponding to high eigenvalues) while retaining low-frequency components, which
similar to low-pass graph filter as shown in Figure 5f is worth noting that if is too large, then most cigenvalues will very close to zero, which makes the graph filter less effective for removing noises. In this work, choose 2.0 for all our experiments.
APPENDIX SPEEDUP OF GRAPHZOOM KERNELS COMPARED TO MILE
As shown in F the combination of GraphZoom coarsening and refinement kernels always achieve the greatest speedups (green curves); adding GraphZoom fusion kernel (blue curves) will lower the speedups by small margin but further boost the embedding quality, showing clear trade-
16

---

Published as a conference paper at ICLR 2020
0.10
0.0
0.00
3.08
0.04
0.00
0.25
0.50
0.75
1.00
1.25
150
1.75
2.00
0.00
0.25
9.50
0.75
3.69
3.25
150
1.75
2.00
Elgenva uest))
(a) Original eigenvalues with
(b) Squeezed eigenvalues with Ā + 0.51
0.12
0.08
0.08
ProteMiry
ProjeMiiy
0.08
06
2.04
3.04
2.02
0.00
0.25
0:50
0.75
1.00
1.25
130
1.15
2.00
0.00
0.23
0.50
0.75
1.00
1.25
150
1.15
2.00
Sigensalussii
Elgenra usstA)
(c) Squeezed cigenvalues with Á A + 1.01
(d) Squeczod cigenvalues with Å A 2.01
1.0
14
0.4
0.4
02-
0.2
0.50
1.23
1.75
2.00
0.75 Bipensluefi)
3.00
2.00
Eggenaluetii
(e) Filters for original laplacian eigenvalues
(1) Filters for squeezed laplacian eigenvalues
Figure 5: Distribution of graph laplacian eigenvalues with different self-loops on Cora
off between embedding quality and runtime efficiency: achieve the highest graph embedding quality, the graph fusion kernel should be included.
APPENDIX MORE RESULTS ON PPI DATASETS
As shown in Figure the embedding results by GraphZoom with increasing number of coarsening levels are still better than the ones by GraphSAGE with different aggregation functions. It is worth noting that although the level-5 (coarsened) graph contains only 120 nodes (as shown in D). Graph-
17

---

Published as a conference paper at ICLR 2020
GZeam_ F + GZoom_ C+ GZoom_R & (DW)
GZoom_ _ + MILE R (DW)
MILE + MILE R (DW)
GZoom GZoom, (DW)
MILE GZoom (DW)
Cora (Speedup)
Citeseer (Speedup)
Pubmed (Speedup)
250
400
CPU time spentiu
200
CPU time Speaduup
150
300
150-
100
100-
CPU
50
100
0-
Coarsening Level
Coarsening Level
Coarsening Level
Figure 6: Comparisons of different combinations of kernels in GraphZoom and MILE in terms of CPU time speedup on Cora, Citeseer, and Pubmed datasets - We choose DeepWalk (DW) as basic embedding method. GZoom_F, GZoom_C GZoom_ R, MILE_C and MILE_K represent GraphZoom fusion kernel, GraphZoom coarsening kernel, GraphZoom refinement kernel, MILE coarsening ker- nel and MILE refinement kernel, respectively.
Comparison GraphZoem Graph5AGE-GCN
GraphZoom GraphSAGF
0.64
0.64
0.62
0.82
0.60
0.60
0.58
0.58
0.55
0.56
0.54
0.54
0.52
Grashizcom Grashsace OCN
0.52
Gruphizeam
OraptSA2E
0.50
0.50
5000
4000
3000
2000
1000
5200
4000
3200
2000
1000
shodes in Coarsened Grash
+hodes in Coarsoned draph
GraphSAGE with GCN aggregation function
(b) GraphSAGE with aggregation function
Comparison GraphZoom and GraphSAGE- on PPI
Comparison GraphZoom and GraphSAGE on PPI
0.64
0.64
0.56
0.56
0.54
0.54
0.52
GraphZzom
0.52
Grap GZom
GrapiSAGE 1zm
G5AP pool
0.50
0.50
Graph
(c) GraphSAGE with LSTM as aggregation function
(d) GraphSAGE with pool as aggregation function
Figure 7: Comparisons of GraphZoom and GraphSAGE on PPI
Zoom embedding results can still beat the GraphSAGE baseline obtained with the original graph containing 14, 755 nodes.
18

---

Published as a conference paper at ICLR 2020
APPENDIX K
MORE RESULTS ON NON-ATTRIBUTED DATASETS
Table 5: Node classification results on PPI and Wiki datasets.
PPI(Homo Sapiens)
Wiki
Method
Mircro-Fl
Time(mins)
Mircro-F1
Time(s)
DeepWalk
0.231
2.3
0.705
94.4
MILE(DW, 1=1)
0.256
1.1 (2.1x)
0.703
42.5 (2.2x)
MILE(DW, 1=2)
0.253
0.7 (3.3x)
0.639
20.9 (4.5x)
GZoom(DW, (=1)
0.261
0.6 (3.8x)
0.726
29.4 (3.2x)
GZoom(DW, (=2)
0,255
0.2 (11.5x)
0.678
6.7 (14.1x)
Table 6: Link prediction results on PPI and Wiki datasets.
PPI(Homo Sapiens)
Wiki
Method
AUC
Time(mins)
AUC
Time(mins)
Deep Walk
0.721
5.2
0.774
3.0
MILE(DW, /=1)
0.772
3.7 (1.4x)
0.877
1.6 (1.8x)
MILE(DW, (=2)
0.701
2.3 (2.3x)
0.868
0.9 (3.3x)
MILE(DW, 1=3)
0.723
1.2 (4.3x)
0.842
0.5 (6.0x)
GZ.om (DW, 1=1)
0.818
2.1 (2.5x)
0.901
1.2 (2.5x)
GZoom (=2)
0.834
0.7 (7.4x)
0.902
0.4 (7.5x)
GZoom(DW, (=3)
0.855
0.1 (52.0x)
0.908
0.1 (30.0x)
To further show that GraphZoom can work on non-attributed datasets, we evaluate it on PPI(Homo Sapiens) and Wiki datasets, following the same dataset configuration as used in Grover & Leskoved (2016); [iang et al. (2018). As shown in Table 5] GraphZoom (without fusion kernel) improves the performance of basic embedding model (i.c., DeepWalk) at the first coarsening level. When further increasing coarsening level, GraphZoom achieves much larger speedup while its performance may drop little bit. For link prediction task, follow Grover & Leskovec (2016) by choosing Hadamard operator to transform node embeddings into edge embeddings. Our link prediction results show that GraphZoom significantly improve performance by a margin of 18.5% with speedup up to 52.0x, showing GraphZoom can generate high-quality embeddings for various tasks.
APPENDIX L SENSITIVITY ANALYSIS OF GRAPH FUSION KERNEL
GZoom(DW, 1=1)
GZoom(DW, (=2)
GZoom(DW, (=3)
Cora (Accuracy)
Citeseer (Accuracy)
Pubmed (Accuracy)
52
77
Accuracy
Accuracy
51
76
50
75
49
74
73
74.0
48
0
2
3
0
1
2
0
Figure 8: Comparisons of classification accuracy using various 3 values in the graph fusion kernel for the Cora, Citeseer, and Pubmed datasets. represents the 1-th coarsening level.
As graph fusion kernel fuses node attribute with graph topology via A Afssio Atopo BAAeatt the value of 3 plays a critical role in balancing attribute and topological information. On the one hand, if 3 is too small, we may lose much node attribute information. On the other hand, if ( is too
19

---

Published as a conference paper at ICLR 2020
large, the node attribute information will dominate the fused graph and therefore graph topoloiial information is undermined. As shown in Figure we vary from 0.1 to 3 in graph fusion kernel and evaluate it on Cora, Citeseer, and Pubmed datasets. The results indicate that B achieves the best performance on Cora and Pubmed, while 3 = 0.5 is the best configuration on Citeseer. We choose | 1 in all our experiments.
20


Reviews:
[{"review_id": "SylX3XyW5B", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nAssessment: 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. \n\nAs 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. \n\nRegarding the fusion step, there were also two points that should be addressed in the paper: \n1) 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.\n2) 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?\n\nReasons to accept:\n- Original and well-motivated idea\n- Clearly written paper\n\nReasons to reject:\n- Problematic empirical evaluation (e.g., lacking recent baselines)\n- Several performance numbers appear to be below random GCN baseline performance\n- General applicability of the approach (e.g., to non-homophilous networks) is not clear ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SklP0HP8oS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides a multi-level graph-coarsening approach that can improve the predictive and computational performances of numerous existing unsupervised graph embedding models. The proposed approach is a pipeline consisting of 4 steps, viz: 1) Graph Fusion - that fuses attribute similarity graph with network topology, 2> Graph Coarsening - that reduces the graph size iteratively, 3> Graph embedding - using existing models and 4> Embedding refinement. While such a pipeline for scaling using a graph coarsening and refinement based approach is not new, the authors have carefully designed the pipeline to be effective and be scalable such as without any costly learning components (as in mile). The effectiveness of the proposed approach is evaluated with the node classification task on 6 datasets.\n\n\nStrengths:\n- The paper addresses a very important problem. The paper proposes a well-designed pipeline to scale existing embedding models.\n- Experimental results support that the proposed approach is effective, especially in terms of reducing computation complexity. \n\nWeaknesses:\n- While the experimental results are convincing on the computation front, I have few concerns on the performance front. \n   a) 'MILE with the fused graph' baseline is missing. It can been seen from Figure 3 that the incorporation of the attribute graph provides a significant performance benefit. Thus it is necessary to have this baseline to understand the improvement gap w.r.t to MILE. I believe this is a fair comparison to make as the graph fusion component is a commonly used technique in the last decade.\n  b) Improvements are inconclusive without additional results on other standard non-attributed graph datasets. In Figure 3, ignoring the model with the fused graph, MILE seems to be comparable to GraphZoom overall. As with the existing results, it's not conclusive whether GraphZoom is better than MILE. Also, add variance and report t-test results. \n  c) That said, it can be seen from Figure 2, that GraphZoom significantly outperforms both DW and MILE(DW) on a large non-attributed dataset. However, it is not clear where the significant increase in performance benefits stems from. More analysis is required here.\n- Results on other unsupervised embedding task missings. It is important to evaluate the embeddings additionally for the link prediction task at the least. \n\nAdditional comment:\n- It would be helpful to incorporate one if not some of the attributed graph embedding model as a base model and baseline, such as Deep Graph Infomax (DGI). \n- It should be easy to use a mini-batch version of GCN with MILE and use it for inductive learning. \n- It would interesting to see what the performance will be without the refinement step. \n\nIf my concerns regarding the experiments are positively addressed, I'm willing to improve the score. \n\n-----------------\nAfter the rebuttal, I have updated my score from 3 to 8 as the authors have satisfactorily responded to the concerns raised. \n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lQ2mwCKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: The authors propose a way to fuse information on nodes of a graph with the topology of the graph in the large scale setting. The proposed approach is done in four phases where (i) the covariates in the nodes of the graph is first mapped in the graph space for fusion and fused using linear combination of the topological graph and feature graph, (ii) the resulting \"adjacency\" matrix will almost surely not be sparse even if the original graph space, so they use eigenvalues of the graph laplacian to coarsen the graph -- remove edges; (iii) they then propose to embed the coarsened graph using \"any\" unsupervised learning technique; (iv) then the embedded representation is refined using iterative procedures. Cheap procedures are introduced to do Phases (i) and (iv). Experimentally the authors see improvements in the performance using their approach compared to the baselines considered.\n\nNovelty: 1. The approach suggested in this paper is already there in MILE Fig 1., the authors mention that MILE requires training GCN but I am not sure why this is critical. The authors mention that \"MILE cannot support inductive embedding\nmodels due to the transductive property of GCN\", can you clarify what this means? I guess one can easily replace GCNs?\n\n2. Covariate adjusted clustering is known to work only when when the features are independent like Stochastic Block Model, see  Covariate-assisted spectral clustering by Binkiewicz et al, 2014. Is there a reason why the features that we see on nodes are not correlated?\n\nResults: It is hard to see where the performance improvement actually comes from, if at all. It is interesting to see that the proposed approach saves time and is more accurate in the variety of settings considered, but it is not clear why we see the improvement. \n\nAfter rebuttal: I have raised my score to 6 after going through the authors' response for my questions, and other reviewers' concerns. While the approach performs well in many datasets (thanks to the authors for providing more experimental evidence!), I'm still not convinced with the authors' response on their fusion step -- it seems to me that node attributes are \"side\" information, that can \"boost\" the signal on the original neighborhood graph. Recall that spectral approaches do have a fundamental barrier -- they fail on \"thin\" graphs (see https://arxiv.org/abs/1608.04845 ). Hence,  node covariance/fusion matrix being dense will be a blessing for spectral approaches since they make spectral methods work. However, is this what we want in *all* the cases? I'm not sure. This means that the choice of \\beta in their fusion step is *very* important, and I don't see any plots on the sensitivity of their procedure with respect to \\beta. I kindly request the authors to include a plot or results showing the sensitivity of the final results with respect to the choice of \\beta. Thanks!", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present an approach for learning graph embeddings by first fusing the graph to generate a new graph with encodes structural information as well as node attribution information. They then iteratively merge nodes based spectral similarities to  obtain coarser graphs. They then use existing methods to learn embeddings from this coarse graph and progressively refine the embeddings to finer graphs. They demonstrate the performance of their method on standard graph datasets. 

This paper has received positive reviews from all reviewers. The authors did a good job of addressing the reviewers' concerns and managed to convince the reviewers about their contributions. I request the authors to take the reviewers suggestions into consideration while preparing the final draft of the paper and recommend that the paper be accepted.
Decision: Accept (Talk)