Title: GRAPHZOOM: A MULTI-LEVEL SPECTRAL APPROACH FOR ACCURATE AND SCALABLE GRAPH EMBEDDING

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. 1 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×, when compared to the state-of-the-art unsupervised embedding methods.

1. INTRODUCTION:

Recent years have seen a surge of 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 vertex classification, link prediction, and community detection (Zhou et al., 2018) ; (Cai et al., 2018) ; (Goyal & Ferrara, 2018) . However, current graph embedding methods have several drawbacks in terms of either accuracy or scalability. On the one hand, random-walk-based embedding algorithms, such as DeepWalk (Perozzi et al., 2014) and node2vec (Grover & Leskovec, 2016) , attempt to embed a 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 (Kipf & 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 in the initial node features, which compromises 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 as GraphSAGE (Hamilton et al., 2017) collectively aggregate feature information from the neighborhood. When stacking multiple GNN layers, the final embedding vector of a node involves the computation of a large number of intermediate 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 multilevel 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. Liang 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 a 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 GraphZoom, 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 a 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 a 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.2 Embedding refinement is then employed to refine the embeddings back to the original graph by applying a proper graph filter to ensure embeddings are 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 classification 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 classification 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 refinement to remove high-frequency noise. This results in a relative increase of the embedding accuracy over the prior arts by up to 19.4% while reducing the execution time by at least 2×. • 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.8× while producing a similar or better accuracy than state-of-the-art 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 plug-and-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 embedding methods. Due to the space limitation, we only summarize some of the recent efforts in these two areas.

Multi-level graph embedding attempts to coarsen the original graph into a series of smaller graphs with decreasing size where existing or new graph embedding techniques can be applied at different coarsening levels. For example, Chen et al. (2018) ; Lin et al. (2019) generate a hierarchy of coarsened 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, however, only focus on improving embedding quality but not the scalability. Later, Zhang et 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 embedding quality. However, MILE requires training a 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, 2011) and practically efficient so that it can improve both accuracy and scalability of the unsupervised graph embedding tasks. Maehara (2019) show the fundamental link between graph embedding and filtering by proving that GCN model implicitly exploits graph filter to remove high-frequency noise from the node feature matrix; a filter neural network (gfNN) is then proposed to derive a stronger graph filter to improve the embedding results. Li et al. (2019) 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.

3. GRAPHZOOM FRAMEWORK:



GraphZoom Framework:

Original Graph Topology 1. Graph Fusion 2. Spectral Coarsening 3. Graph Embedding 4. Embedding Refinement

! " Node Attributes … ! # ! $ ! % … & " & # & % & '

Graph w/ Node Embeddings Figure 1 shows 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), a spectral graph coarsening process is applied to form a 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 a finer graph using the mapping 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 are obtained. In the rest of this section, we describe 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 A topo ∈ R N ×N and its node attribute (feature) matrix X ∈ R N ×K , where K corresponds to the dimension of node attribute vector, graph fusion can be interpreted as a function f (•) that outputs a weighted graph G f usion = (V, E f usion ) represented by its adjacency matrix

A f usion ∈ R N ×N , namely, A f usion = f (A topo , X).

We first convert the initial attribute matrix X into a weighted node attribute graph G f eat = (V, E f eat ) by generating a k-nearest-neighbor (kNN) graph based on the l 2 -norm distance between the attribute vectors of each node pair. A straightforward implementation requires comparing all possible node pairs and then selecting top-k nearest neighbors. However, such a naïve approach has a worstcase time complexity of O(N 2 ), 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 coarsening scheme that is described in more detail in Section 3.2. More specifically, our approach starts with coarsening the original graph G to obtain a substantially reduced graph that has much fewer nodes with an O(|E|) 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 2 ) 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 O(M N ). When a proper coarsening ratio is chosen where M N (e.g., M = 50), the overall time complexity will become almost linear.

After the attribute graph is formed, we assign a weight to each edge based on the cosine similarity between the attribute vectors of the two incident nodes, namely w i,j = (X i,: • X j,: )/( X i,: X j,: ), where X i,: and X j,: 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: A f usion = A topo + βA f eat , where β 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 matrix3 ), 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 & Niyogi, 2003; Peng et al., 2015) . Next, the graph nodes that are close to 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 effective local spectral embedding scheme to 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 at 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, we 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 a random vector (graph signal) x that is expressed with a linear combination of eigenvectors u of the graph Laplacian. We adopt 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 x, we obtain a smoothed vector x, which is basically the linear combination of the first few eigenvectors:

EQUATION

More specifically, we apply a few (typically five to ten) Gauss-Seidel iterations for solving the linear system of equations L G x (i) = 0 to a set of t initial random vectors T = (x (1) , . . . , x (t) ) that are orthogonal to the all-one vector 1 satisfying 1 x (i) = 0, and L G is the Laplacian matrix of graph G or G f usion .

Based on the smoothed vectors in T , we embed each node into a t-dimensional space such that nodes p and q are considered spectrally similar if their low-dimensional embedding vectors x p ∈ R t and x q ∈ R t are highly correlated. Here the node distance is measured by the spectral node affinity a p,q for neighboring nodes p and q (Livne & Brandt, 2012; Chen & Safro, 2011):

a p,q = |(T p,: , T q,: )| 2 T p,: 2 T q,: 2 , (T p,: , T q,: ) = Σ t k=1 (x (k) p • x (k) q ) (2)

Once the node aggregation schemes are determined, we can easily obtain the graph mapping operator H i+1 i between two coarsening levels i and i + 1. More precisely,

H i+1 i is a matrix of size |V Gi+1 | × |V Gi |. (H i+1 i ) p,q = 1 if node q in graph G i is aggregated to (clustered) node p in graph G i+1 ;

otherwise, it is set to 0. Additional discussions on the properties of H i+1 i are available in Appendix F, which shows this operator a surjective mapping and locality preserving.

We leverage

H 1 0 , H 2 1 , • • • , H l l-1 for constructing a series of spectrally-reduced graphs G 1 , G 2 , • • • , G l .

Specifically, The coarser graph Laplacian L Gi+1 can be computed by Eq. (3). It is worth noting that G 0 (i.e., G f usion ) is the original fused graph and

|V 0 | = N > |V 1 | > • • • > |V l |. L Gi+1 = H i+1 i L Gi H i i+1 , H i i+1 = (H i+1 i ) T (3)

We emphasize that the aggregation scheme based on the above spectral node affinity calculations will have a (linear) complexity of O(|E f usion |) and thus allow preserving the spectral (global or structural) properties of the original graph in a highly efficient and effective way. As suggested in (Zhao & Feng, 2019; Loukas, 2019) , a spectral sparsification procedure can be applied to effectively control densities of coarse level graphs. In this work, a similarity-aware spectral sparsification tool "GRASS" (Feng, 2018) has been adopted for achieving a desired graph sparsity at the coarsest level.

3.3. PHASE 3: GRAPH EMBEDDING:

Embedding the Coarsest Graph. Once the coarsest graph G l is constructed, node embeddings E l on G l can be obtained by E l = g(G l ), where g(•) can be any unsupervised embedding methods.

3.4. PHASE 4: EMBEDDING REFINEMENT:

Given E i+1 , the node embeddings of graph G i+1 at level i + 1, we can use the corresponding projection operator H i i+1 to project E i+1 to G i , which is the finer graph at level i:

Êi = H i i+1 E i+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 if they are aggregated into a single node during the coarsening phase.

To further improve the quality of the mapped embeddings, we apply a local refinement process motivated by Tikhonov regularization to smooth the node embeddings over the graph by minimizing the following objective:

min Ei { E i -Êi 2 2 + tr(E i T L i E i )} (5)

where L i and E i 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 Ẽi by solving Eq. ( 5). Here the first term enforces the refined embeddings to agree with mapped embeddings, while the second term employs Laplacian smoothing to smooth Ẽi over the graph. By taking the derivative of the objective function in Eq. ( 5) and setting it to zero, we have:

EQUATION

)

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(N 3 ). Instead, we exploit a more efficient spectral graph filter to smooth the embeddings.

By transforming h(L) = (I + L) -1 into spectral domain, we obtain the graph filter: h(λ) = (1 + λ) -1 . To avoid the inversion term, we approximate h(λ) by its first-order Taylor expansion, namely, h(λ) = 1 -λ. We then generalize h(λ) to hk (λ) = (1 -λ) k , where k controls the power of graph filter. After transforming hk (λ) into the spatial domain, we have:

hk (L) = (I -L) k = (D -1 2 AD -1 2 ) k

, where A is the adjacency matrix and D is the degree matrix. It is not difficult to show that adding a proper self-loop for every node in the graph will allow hk (L) to more effectively filter out high-frequency noise components (Maehara, 2019) (see Appendix H). Thus, we modify the adjacency matrix as Ã = A + σI, where σ is a small value to ensure every node has its own self-loop. Finally, the low-pass graph filter can be utilized to smooth the mapped embedding matrix, as shown in ( 7):

EQUATION

We iteratively apply Eq. ( 7) to obtain the embeddings of the original graph (i.e., E 0 ). Note that our refinement stage does not involve training and can be simply considered as several (sparse) matrix multiplications, which can be efficiently computed.

4. EXPERIMENTS:

We have performed comparative evaluation of GraphZoom framework against several state-of-theart unsupervised graph embedding techniques and multi-level embedding frameworks on five standard graph-based datasets (transductive as well as inductive). In addition, we evaluate the scalability of GraphZoom on Friendster dataset, which contains 8 million nodes and 400 million edges. Finally, we conduct ablation study to understand the effectiveness of the major GraphZoom kernels. 

4.1. EXPERIMENTAL SETUP:



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 a new node is added. Here we compare GraphZoom with three transductive models: DeepWalk (Perozzi et al., 2014) , node2vec (Grover & Leskovec, 2016) , and Deep Graph Infomax (DGI) (Veličković et al., 2019) 4 . These methods have shown stateof-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 et al., 2018) and MILE (Liang et al., 2018) , which have reported improvement over DeepWalk 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 GraphSAGE (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 B. We optimize hyperparameters 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 a Linux machine with an 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., 2019) as embedding kernels. For inductive tasks, we compare GraphZoom with GraphSAGE using four different aggregation functions.

Tables 2 and 3 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 DeepWalk, 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. Similarly, we add up the CPU time for graph fusion, graph coarsening, graph embedding, and embedding refinement as the execution time of GraphZoom. In regard to hyperparameters, we use 10 walks with a walk length of 80, a window size of 10, and an embedding dimension of 128 for both DeepWalk and node2vec; we further set the return parameter p and the in-out parameter q in node2vec as 1.0 and 0.5, respectively. Moreover, we choose early stopping strategy for DGI with a learning rate of 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.

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 3 (blue curve), and the Appendix J. Our results demonstrate that GraphZoom is agnostic to underlying embedding methods and capable of boosting the accuracy and speed of state-of-the-art unsupervised embedding methods on various datasets.

More specifically, for transductive learning tasks, GraphZoom improves classification accuracy upon both DeepWalk and node2vec by a relative gain of 8.3%, 10.4%, and 19.4%5 on Cora, Pubmed, and Citeseer, respectively, while achieving up to 40.8× run-time reduction. In regard to comparing with DGI, GraphZoom achieves comparable or better accuracy with speedup up to 11.2×. Similarly, GraphZoom outperforms all the baselines by a margin of 3.4% and 3.3% on PPI and Reddit for inductive learning tasks, respectively, with speedup up to 7.6×. These results indicate that our 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, our 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 a few baseline embedding methods, the performance of MILE becomes 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 kernel. 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 a better embedding accuracy with much shorter CPU times. This further confirms GraphZoom can retain the key graph structure information to be utilized by underlying embedding models to boost embedding quality. More results of GraphZoom on non-attributed graph for both node classification and link prediction tasks are available in Appendix K.

GraphZoom for large graph embedding. To show GraphZoom can significantly improve performance and scalability of underlying embedding model on large graph, we test GraphZoom and MILE on Friendster dataset, which contains 8 million nodes and 400 million edges. For both cases, we use DeepWalk as the embedding kernel. As shown in Figure 2 , GraphZoom drastically boosts the Micro-F1 score up to 47.6% compared to MILE and 49.9% compared to DeepWalk with a speedup up to 119.8×. 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 to the underlying embedding model. When applying basic embedding model on coarsest graph, it can learn more global information from spectral domain, leading to 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 a large reduction ratio.

4.3. ABLATION ANALYSIS ON GRAPHZOOM KERNELS:

To study the effectiveness of our proposed GraphZoom kernels separately, we compare each of them against the corresponding kernel in MILE while fixing other kernels. As shown in Figure 3 , when fixing coarsening kernel and comparing refinement kernel of GraphZoom with that of MILE, Our re- 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 successfully filter out high-frequency noise from the graph to improve embedding quality. Similarly, when comparing coarsening kernels in 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 improve embedding result. Moreover, adding graph fusion improves classification accuracy by a 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 I.

5. CONCLUSIONS:

This work introduces GraphZoom, a 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 a 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 a 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.

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-1 means GraphZoom with 1 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 

∈ R N ×D 1 A 0 = graph f usion(A topo , X); 2 for i = 1...l do 3 A i , H i i-1 = spectral coarsening(A i-1 ); 4 end 5 E L = g(A l ); 6 for i = l...1 do 7 Êi-1 = (H i i-1 ) T E i ; 8 E i-1 = ref inement( Êi-1 ); 9 end 10 E = E 0 ; 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 i + 1, a surjection is defined between the original node set V i and the reduced node set V i+1 , where each node v ∈ V i+1 corresponds to a small set of adjacent vertices in the original node set V i . Mapping operator H i+1 i can be defined based on the mapping relationship between V i and V i+1 , Note that the operator H i+1 i ∈ {0, 1} |Vi+1|×|Vi| is a matrix containing only 0s and 1s. It has following properties:

• The row (column) index of H i+1 i corresponds to the node index in graph G i+1 (G i ).

• It is a surjective mapping of the node set, where (H i+1 i ) p,q = 1 if node q in graph G i is aggregated to super-node p in graph G i+1 , and (H i+1 i ) p ,q = 0 for all nodes p ∈ {v ∈ V i+1 : v = p}.

• It is a locality-preserving operator, where the coarsened version of G i induced by the non-zero entries of (H As shown in Figure 4 (note that the y axis is in logarithmic scale), the GraphZoom embedding kernel dominates the total CPU time, which can be more effectively reduced with a greater coarsening level L. All other kernels in GraphZoom are very efficient, which enable the GraphZoom framework to drastically reduce the total graph embedding time. 

i+1 i ) p,: is connected for each p ∈ V i+1 . [unaggregated node set] U ← p ∈ {p|z(p) == -1 ∀p ∈ V i }; 18 S ← p ∈ {p|a p,q ≥ δ • max s =p,q max (p,s)∈ E i a p,s , max (q,s)∈ E i a q,s ∀p ∈ V i }; 19 for each node p in S ∩ U do 20 if z(p) == -1 then 21 q = arg max (p,q)∈ E i a p,q ; 22 23 if z(q) == -1 then 24 z(q) = 0, z(p) = q, q = q; 25 else if z(q) == 0 then 26 z(p) = q, q = q; 27 else 28 z(p) = z(q), q = z(q); 29 end 30 update smoothed vectors in T with x (k) p = x (k) q for k = 1, • • • , t n c = n c -1;

:

In this work, we do not attempt to preserve node label information in the coarsened graph. Nonetheless, we believe that our approach can be extended to support supervised embedding models such as GAT(Gulcehre et al., 2019) and PPNP(Klicpera et al., 2019), as briefly discussed in Section 5.

Laplacian matrix L is defined as L = D -A, where D is degree matrix and A is adjacency matrix.

DGI also supports inductive tasks, although the authors have only released the source code for transductive learning at github.com/PetarV-/DGI, as of the date of this experiment.

GZoom(N2V, l=1) improves over node2vec on Citeseer by 19.4% = (54.7 -45.8)/45.8.

Figures and Tables:

Figure 1: Overview of the GraphZoom framework.

Figure 2: Comparisons of GraphZoom and MILE on Friendster dataset.

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 embedding kernel. GZoom F, GZoom C, GZoom R denote the fusion, coarsening, and refinement kernels proposed in GraphZoom, respectively; MILE C and MILE R denote the coarsening and refinement kernels in MILE, respectively; The blue curve is basically GraphZoom and the yellow one is MILE.

= n/n c , δ = 0.7 • δ ; 34 z(p) = p for node p ∈ {p|z(p) == 0} 35 end 36 form H i+1 i and A i+1 based on z APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL

Figure 4: CPU time of GraphZoom kernels

Figure 5: Distribution of graph laplacian eigenvalues with different self-loops on Cora

Graph filtering are direct analogs of classical filters in signal processing field, but intended for signals defined on graphs. Shuman et al. (2013) define graph filters in both vertex and spectral domains, and apply graph filter on image denoising and reconstruction tasks. Wu et al. (2019) leverage graph filter to simplify GCN model by removing redundant computation. More recently,

Table content: <table/>

Statistics of datasets used in our experiments.Datasets. Table1reports the statistics of the datasets used in our experiments. We include Cora, Citeseer, Pubmed, and Friendster for evaluation on transductive learning tasks, and PPI as well as Reddit for inductive learning. We split the training and testing data in the same way as suggested in Kipf & Welling (2016);Hamilton et al. (2017).

Table content: <table><tr><td>Dataset</td><td>Type</td><td>Task</td><td>Nodes</td><td>Edges</td><td colspan="2">Classes Features</td></tr><tr><td>Cora</td><td colspan="2">Citation network Transductive</td><td>2,708</td><td>5,429</td><td>7</td><td>1,433</td></tr><tr><td>Citeseer</td><td colspan="2">Citation network Transductive</td><td>3,327</td><td>4,732</td><td>6</td><td>3,703</td></tr><tr><td>Pubmed</td><td colspan="2">Citation network Transductive</td><td>19,717</td><td>44,338</td><td>3</td><td>500</td></tr><tr><td>PPI</td><td>Biology network</td><td>Inductive</td><td>14,755</td><td>222,055</td><td>121</td><td>50</td></tr><tr><td>Reddit</td><td>Social network</td><td>Inductive</td><td>232,965</td><td>57,307,946</td><td>210</td><td>5,414</td></tr><tr><td>Friendster</td><td>Social network</td><td colspan="3">Transductive 7,944,949 446,673,688</td><td>5,000</td><td>N/A</td></tr></table>

Summary of results in terms of mean classification accuracy and CPU time for transductive tasks, on Cora, Citeseer, and Pubmed datasets -DW, N2V, and GZoom denote DeepWalk, node2vec, and GraphZoom, respectively; l means the graph coarsening level; GZoom F+MILE represents the best performance achieved when adding GraphZoom fusion kernel into MILE.

Table content: <table><tr><td/><td/><td>Cora</td><td/><td>Citeseer</td><td/><td>Pubmed</td></tr><tr><td>Method</td><td colspan="2">Accuracy(%) Time(secs)</td><td colspan="2">Accuracy(%) Time(secs)</td><td colspan="2">Accuracy(%) Time(mins)</td></tr><tr><td>DeepWalk</td><td>71.4</td><td>97.8</td><td>47.0</td><td>120.0</td><td>69.9</td><td>14.1</td></tr><tr><td>HARP(DW)</td><td>71.3</td><td>296.7 (0.3×)</td><td>43.2</td><td>272.4 (0.4×)</td><td>70.6</td><td>33.9 (0.4×)</td></tr><tr><td>MILE(DW, l=1)</td><td>71.9</td><td>68.7 (1.4×)</td><td>46.5</td><td>53.7 (2.2×)</td><td>69.6</td><td>7.0 (2.0×)</td></tr><tr><td>MILE(DW, l=2)</td><td>71.3</td><td>30.9 (3.2×)</td><td>47.3</td><td>22.5 (5.3×)</td><td>66.7</td><td>4.4 (2.3×)</td></tr><tr><td>MILE(DW, l=3)</td><td>70.6</td><td>15.9 (6.1×)</td><td>47.1</td><td>9.9 (12.1×)</td><td>64.5</td><td>2.5 (5.8×)</td></tr><tr><td>GZoom F+MILE(DW)</td><td>73.8</td><td>70.6 (1.4×)</td><td>48.9</td><td>24.7 (4.9×)</td><td>72.1</td><td>7.0 (2.0×)</td></tr><tr><td>GZoom(DW, l=1)</td><td>76.9</td><td>39.6 (2.5×)</td><td>49.7</td><td>19.6 (2.1×)</td><td>75.3</td><td>4.0 (3.6×)</td></tr><tr><td>GZoom(DW, l=2)</td><td>77.3</td><td>15.6 (6.3×)</td><td>50.8</td><td>6.7 (6.0×)</td><td>75.9</td><td>1.7 (8.3×)</td></tr><tr><td>GZoom(DW, l=3)</td><td>75.1</td><td>2.4 (40.8×)</td><td>49.5</td><td>1.3 (30.8×)</td><td>77.2</td><td>0.6 (23.5×)</td></tr><tr><td>node2vec</td><td>71.5</td><td>119.7</td><td>45.8</td><td>126.9</td><td>71.3</td><td>15.6</td></tr><tr><td>HARP(N2V)</td><td>72.3</td><td>171.0 (0.7×)</td><td>44.8</td><td>174.3 (0.7×)</td><td>70.1</td><td>46.1 (0.3×)</td></tr><tr><td>MILE(N2V, l=1)</td><td>72.1</td><td>57.3 (2.1×)</td><td>46.1</td><td>60.9 (2.1×)</td><td>70.8</td><td>7.3 (2.1×)</td></tr><tr><td>MILE(N2V, l=2)</td><td>71.8</td><td>30.0 (4.0×)</td><td>45.7</td><td>28.8 (4.4×)</td><td>67.3</td><td>4.3 (3.6×)</td></tr><tr><td>MILE(N2V, l=3)</td><td>68.5</td><td>16.5 (7.2×)</td><td>45.2</td><td>15.6 (8.1×)</td><td>61.8</td><td>1.8 (8.0×)</td></tr><tr><td>GZoom F+MILE(N2V)</td><td>74.3</td><td>59.2 (2.0×)</td><td>48.3</td><td>62.3 (2.0×)</td><td>72.9</td><td>7.3 (2.1×)</td></tr><tr><td>GZoom(N2V, l=1)</td><td>77.3</td><td>43.5 (2.8×)</td><td>54.7</td><td>38.1 (3.3×)</td><td>77.0</td><td>3.0 (5.2×)</td></tr><tr><td>GZoom(N2V, l=2)</td><td>77.0</td><td>13.5 (8.9×)</td><td>51.7</td><td>15.3 (8.3×)</td><td>77.8</td><td>1.5 (10.4×)</td></tr><tr><td>GZoom(N2V, l=3)</td><td>75.3</td><td>3.0 (39.9×)</td><td>50.7</td><td>4.5 (28.2×)</td><td>77.4</td><td>0.4 (39.0×)</td></tr><tr><td>DGI</td><td>82.3</td><td>89.7</td><td>71.8</td><td>94.6</td><td>76.8</td><td>23.7</td></tr><tr><td>MILE(DGI, l=1)</td><td>80.9</td><td>45.9 (1.9×)</td><td>69.9</td><td>53.2 (1.8×)</td><td>76.1</td><td>10.4 (2.3×)</td></tr><tr><td>MILE(DGI, l=2)</td><td>80.3</td><td>27.5 (3.3×)</td><td>69.2</td><td>31.1 (3.0×)</td><td>74.3</td><td>4.3 (5.5×)</td></tr><tr><td>MILE(DGI, l=3)</td><td>79.2</td><td>15.6 (4.4×)</td><td>67.9</td><td>18.5 (5.1×)</td><td>74.4</td><td>2.7 (8.8×)</td></tr><tr><td>GZoom F+MILE(DGI)</td><td>81.3</td><td>45.9 (1.9×)</td><td>70.4</td><td>52.3 (1.8×)</td><td>75.9</td><td>10.4 (2.3×)</td></tr><tr><td>GZoom(DGI, l=1)</td><td>83.9</td><td>27.3 (3.3×)</td><td>71.1</td><td>29.3 (3.2×)</td><td>77.1</td><td>9.6 (2.5×)</td></tr><tr><td>GZoom(DGI, l=2)</td><td>83.8</td><td>15.2 (5.9×)</td><td>70.8</td><td>17.9 (5.3×)</td><td>77.6</td><td>4.4 (5.4×)</td></tr><tr><td>GZoom(DGI, l=3)</td><td>83.5</td><td>8.0 (11.2×)</td><td>70.7</td><td>9.6 (9.8×)</td><td>76.9</td><td>2.1 (11.2×)</td></tr></table>

Summary of results in terms of micro-averaged F1 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; l means the graph coarsening level.

Table content: <table><tr><td>PPI</td><td>Reddit</td></tr></table>

Adjacency matrix A topo ∈ R N ×N ; node feature matrix X ∈ R N ×K ; base embedding function g(•); coarsening level l Output: Node embedding matrix E

Table content: <table><tr><td>Cora</td><td>2,708</td><td>1,169</td><td>519</td><td>218</td><td>100</td><td>-</td></tr><tr><td>Citeseer</td><td>3,327</td><td>1,488</td><td>606</td><td>282</td><td>131</td><td>58</td></tr><tr><td>Pubmed</td><td>19,717</td><td>7,903</td><td>3,562</td><td>1,651</td><td>726</td><td>327</td></tr><tr><td>PPI</td><td>14,755</td><td>5,061</td><td>1,815</td><td>685</td><td>281</td><td>120</td></tr><tr><td>Reddit</td><td>232,965</td><td>84,562</td><td>30,738</td><td>11,598</td><td>4,757</td><td>2,117</td></tr><tr><td colspan="4">Friendster 7,944,949 2,734,483 1,048,288</td><td>409,613</td><td>134,956</td><td>44,670</td></tr><tr><td colspan="4">APPENDIX E GRAPHZOOM ALGORITHM</td><td/><td/><td/></tr><tr><td colspan="3">Algorithm 1: GraphZoom algorithm</td><td/><td/><td/><td/></tr><tr><td>Input:</td><td/><td/><td/><td/><td/><td/></tr></table>

Peer review (iclr2020):
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. Novelty: 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 models due to the transductive property of GCN*, can you clarify what this means? I guess one can easily replace GCNs? 2. 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? Results: 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. After 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 _x0008_eta in their fusion step is *very* important, and I don*t see any plots on the sensitivity of their procedure with respect to _x0008_eta. I kindly request the authors to include a plot or results showing the sensitivity of the final results with respect to the choice of _x0008_eta. Thanks!