summaries: 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. 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. 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.
abstractText: 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.
authors.name: SCALABLE GRAPH EMBEDDING
authors.name: Chenhui Deng
authors.name: Zhiqiang Zhao
authors.name: Yongyu Wang
authors.name: Zhiru Zhang
references.authors: Esra Akbas Mehmet Aktas
references.title: Network Embedding: on compression and learning
references.venue: arXiv preprint:1907.02811,
references.authors: Mikhail Belkin Partha Niyogi
references.title: Laplacian eigenmaps for dimensionality reduction and data representation
references.venue: Neural Computation (NC),
references.authors: Hongyun Cai Vincent W Zheng Kevin Chen-Chuan Chang
references.title: A comprehensive survey of graph embedding: Problems, techniques, and applications
references.venue: Transactions on Knowledge and Data Engineering (TKDE),
references.authors: Haochen Chen Bryan Perozzi Yifan Hu Steven Skiena
references.title: HARP: Hierarchical representation learning for networks
references.venue: The AAAI Conference on Artificial Intelligence (AAAI),
references.authors: Jie Chen Ilya Safro
references.title: Algebraic distance on graphs
references.venue: SIAM Journal on Scientific Computing (SISC),
references.authors: Zhuo Feng
references.title: Similarity-aware spectral sparsification by edge filtering
references.venue: Design Automation Conference (DAC),
references.authors: Guoji Fu Chengbin Hou Xin Yao
references.title: Learning topological representation for networks via hierarchical sampling
references.venue: arXiv preprint:1902.06684,
references.authors: Palash Goyal Emilio Ferrara
references.title: Graph embedding techniques, applications, and performance: A survey
references.venue: Knowledge-Based Systems (KBS),
references.authors: Aditya Grover Jure Leskovec
references.title: node2vec: Scalable feature learning for networks
references.venue: International Conference on Knowledge Discovery and Data mining (KDD),
references.authors: Caglar Gulcehre Misha Denil Mateusz Malinowski Ali Razavi Razvan Pascanu Karl Moritz Hermann Peter Battaglia Victor Bapst David Raposo Adam Santoro Nando de Freitas
references.title: Hyperbolic Attention Networks
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Will Hamilton Zhitao Ying Jure Leskovec
references.title: Inductive representation learning on large graphs
references.venue: Neural Information Processing Systems (NeurIPS),
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.venue: The Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Johannes Klicpera Aleksandar Bojchevski Stephan Günnemann
references.title: Combining neural networks with personalized pagerank for classification on graphs
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Qimai Li Zhichao Han Xiao-Ming Wu
references.title: Deeper insights into graph convolutional networks for semi-supervised learning
references.venue: The AAAI Conference on Artificial Intelligence (AAAI),
references.authors: Qimai Li Xiao-Ming Wu Han Liu Xiaotong Zhang Zhichao Guan
references.title: Label efficient semisupervised learning via graph filtering
references.venue: The Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Jiongqian Liang Saket Gurukar Srinivasan Parthasarathy
references.title: MILE: A multi-level framework for scalable graph embedding
references.venue: arXiv preprint:1802.09612,
references.authors: Wenqing Lin Feng He Faqiang Zhang Xu Cheng Hongyun Cai
references.title: Effective and efficient network embedding initialization via graph partitioning
references.authors: Oren E Livne Achi Brandt
references.title: Lean Algebraic Multigrid (LAMG): Fast graph laplacian linear solver
references.venue: SIAM Journal on Scientific Computing (SISC),
references.authors: Andreas Loukas
references.title: Graph reduction with spectral and cut guarantees
references.venue: Journal of Machine Learning Research (JMLR),
references.authors: Takanori Maehara
references.title: Revisiting graph neural networks: All we have is low-pass filters
references.venue: arXiv preprint:1905.09550,
references.authors: Richard Peng He Sun Luca Zanetti
references.title: Partitioning well-clustered graphs: Spectral clustering works
references.venue: The Conference on Learning Theory (COLT),
references.authors: Bryan Perozzi Rami Al-Rfou Steven Skiena
references.title: DeepWalk: Online learning of social representations
references.venue: International Conference on Knowledge Discovery and Data mining (KDD),
references.authors: David I Shuman Sunil K Narang Pascal Frossard Antonio Ortega Pierre Vandergheynst
references.title: The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains
references.venue: Signal Processing Magazine (SPM),
references.authors: Lei Tang Huan Liu
references.title: Leveraging social media networks for classification
references.venue: Data Mining and Knowledge Discovery (DMKD),
references.authors: Petar Veličković William Fedus William L. Hamilton Pietro Liò Yoshua Bengio R Devon Hjelm
references.title: Deep Graph Infomax
references.venue: International Conference on Learning Representations (ICLR),
references.authors: Felix Wu Tianyi Zhang Amauri Holanda de Souza Jr. Christopher Fifty Tao Yu Kilian Q Weinberger
references.title: Simplifying graph convolutional networks
references.venue: International Conference on Machine Learning (ICML),
references.authors: Jaewon Yang Jure Leskovec
references.title: Defining and evaluating network communities based on groundtruth
references.venue: Knowledge and Information Systems (KAIS),
references.authors: Zhilin Yang William W Cohen Ruslan Salakhutdinov
references.title: Revisiting semi-supervised learning with graph embeddings
references.venue: arXiv preprint:1603.08861,
references.authors: Daokun Zhang Jie Yin Xingquan Zhu Chengqi Zhang
references.title: Network representation learning: A survey
references.venue: Transactions on Big Data (TBD),
references.authors: Zhengyan Zhang Cheng Yang Zhiyuan Liu Maosong Sun Zhichong Fang Bo Zhang Leyu Lin
references.title: COSINE: Compressive network embedding on large-scale information networks
references.venue: arXiv preprint:1812.08972,
references.authors: Zhiqiang Zhao Zhuo Feng
references.title: Effective-resistance preserving spectral reduction of graphs
references.venue: Design Automation Conference (DAC),
references.authors: Jie Zhou Ganqu Cui Zhengyan Zhang Cheng Yang Zhiyuan Liu Maosong Sun
references.title: Graph neural networks: A review of methods and applications
references.venue: arXiv preprint:1812.08434,
references.authors: Liang
references.title: 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 
sections.heading: 1 INTRODUCTION
sections.text: 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
  ∗Equal contributions 1Source code of GraphZoom is freely available at: github.com/cornell-zhang/GraphZoom.
  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.
sections.heading: 2 RELATED WORK
sections.text: 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
  2In 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.
  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.
  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, 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 FRAMEWORKGraphZoom Framework
  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.
sections.heading: 3.1 PHASE 1: GRAPH FUSION
sections.text: 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 ∈ RN×N and its node attribute (feature) matrix X ∈ RN×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 Gfusion = (V, Efusion) represented by its adjacency matrix Afusion ∈ RN×N , namely, Afusion = f(Atopo, X). We first convert the initial attribute matrixX into a weighted node attribute graph Gfeat = (V, Efeat) by generating a k-nearest-neighbor (kNN) graph based on the l2-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(N2), 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(M2) 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(MN). 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 wi,j = (Xi,: ·Xj,:)/(‖Xi,:‖‖Xj,:‖), where Xi,: and Xj,: 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 +βAfeat, 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.
sections.heading: 3.2 PHASE 2: SPECTRAL COARSENING
sections.text: 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 3), 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,
  3Laplacian matrix L is defined as L = D −A, where D is degree matrix and A is adjacency matrix.
  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:
  x = ΣNi=1αiui smoothing =====⇒ x̃ = Σni=1α̃iui , n N (1)
  More specifically, we apply a few (typically five to ten) Gauss-Seidel iterations for solving the linear system of equations LGx(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 LG is the Laplacian matrix of graph G or Gfusion. 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 xp ∈ Rt and xq ∈ Rt are highly correlated. Here the node distance is measured by the spectral node affinity ap,q for neighboring nodes p and q (Livne & Brandt, 2012; Chen & Safro, 2011):
  ap,q = |(Tp,:,Tq,:)|2
  ‖Tp,:‖2‖Tq,:‖2 , (Tp,:,Tq,:) = Σ
  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 Hi+1i between two coarsening levels i and i+ 1. More precisely, H i+1 i is a matrix of size |VGi+1 | × |VGi |. (Hi+1i )p,q = 1 if node q in graph Gi is aggregated to (clustered) node p in graph Gi+1; otherwise, it is set to 0. Additional discussions on the properties of Hi+1i are available in Appendix F, which shows this operator a surjective mapping and locality preserving.
  We leverage H10 , H 2 1 , · · · , H ll−1 for constructing a series of spectrally-reduced graphs G1,G2, · · · ,Gl. Specifically, The coarser graph Laplacian LGi+1 can be computed by Eq. (3). It is worth noting that G0 (i.e., Gfusion) is the original fused graph and |V0| = N > |V1| > · · · > |Vl|.
  LGi+1 = H i+1 i LGiH 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(|Efusion|) 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.
sections.heading: 3.3 PHASE 3: GRAPH EMBEDDING
sections.text: Embedding the Coarsest Graph. Once the coarsest graph Gl is constructed, node embeddings El on Gl can be obtained by El = g(Gl), where g(·) can be any unsupervised embedding methods.
sections.heading: 3.4 PHASE 4: EMBEDDING REFINEMENT
sections.text: Given Ei+1, the node embeddings of graph Gi+1 at level i + 1, we can use the corresponding projection operator Hii+1 to project Ei+1 to Gi, which is the finer graph at level i:
  Êi = H i i+1Ei+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 { ∥∥∥Ei − Êi∥∥∥2 2 + tr(EiTLiEi)} (5)
  where Li and Ei 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̃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 Ẽi over the graph. By taking the derivative of the objective function in Eq. (5) and setting it to zero, we have:
  Ei = (I + Li) −1 Êi (6)
  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 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 h̃k(λ) = (1 − λ)k, where k controls the power of graph filter. After transforming h̃k(λ) into the spatial domain, we have: h̃k(L) = (I − L)k = (D− 1 2AD− 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 h̃k(L) to more effectively filter out high-frequency noise components (Maehara, 2019) (see Appendix H). Thus, we modify the adjacency matrix as Ã = 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):
  Ei = (D̃i − 12 ÃiD̃i − 12 )kÊi = (D̃i − 12 ÃiD̃i − 12 )kHii+1Ei+1 (7)
  We iteratively apply Eq. (7) to obtain the embeddings of the original graph (i.e., E0). Note that our refinement stage does not involve training and can be simply considered as several (sparse) matrix multiplications, which can be efficiently computed.
sections.heading: 4 EXPERIMENTS
sections.text: 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.
sections.heading: 4.1 EXPERIMENTAL SETUP
sections.text: Datasets. Table 1 reports 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).
  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) (Veličković 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.
sections.heading: 4.2 PERFORMANCE AND SCALABILITY OF GRAPHZOOM
sections.text: Since HARP and MILE only support transductive learning, we compare them with GraphZoom using DeepWalk, node2vec, and DGI (Veličković 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 GraphZoom. 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
  4DGI 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.
  5GZoom(N2V, l=1) improves over node2vec on Citeseer by 19.4% = (54.7− 45.8)/45.8.
  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.
sections.heading: 4.3 ABLATION ANALYSIS ON GRAPHZOOM KERNELS
sections.text: 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.
sections.heading: 5 CONCLUSIONS
sections.text: 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.
sections.heading: ACKNOWLEDGMENTS
sections.text: This work is supported in part by Semiconductor Research Corporation and DARPA, Intel Corporation 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.
sections.heading: APPENDIX A DETAILS OF DATASETS
sections.text: Transductive task. We follow the experiments setup in Yang et al. (2016) for three standard citation network benchmark datasets: Cora, Citeseer, and Pubmed. In all these three citation networks, nodes represent documents and edges correspond to citations. Each node has a sparse bag-of-word feature vector and a class label. We allow only 20 labels per class for training and 1, 000 labeled nodes for testing. In addition, we further evaluate on Friendster dataset (Yang & Leskovec, 2015), which contains 8 million nodes and 400 million edges, with 2.5% of the nodes used for training and 0.3% nodes for testing. In Friendster, nodes represent users and a 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. (2017) for setting up experiments on both proteinprotein 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 if the same users comment on both posts. We use 60% nodes for training, 40% for testing on PPI and 65% for training and 35% for testing on Reddit.
sections.heading: APPENDIX B DETAILS OF BASELINES
sections.text: DeepWalk first generates random walks based on graph structure. Then, walks are treated as sentences in 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 q, which can combine DFS-like and BFS-like neighborhood exploration.
  Deep Graph Infomax (DGI) is an unsupervised approach that generates node embeddings by maximizing 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. GraphSAGE supports four different aggregation functions: GraphSAGE-GCN, GraphSAGE-mean, GraphSAGE-LSTM and GraphSAGE-pool.
  HARP coarsens the original graph into several levels and apply underlying embedding model to train the coarsened graph at each level sequentially to 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-art multi-level unsupervised graph embedding framework and similar to our GraphZoom framework since it also contains graph coarsening and embedding refinement kernels. 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 on the original graph. We compare GraphZoom with MILE on various datasets, including Friendster that contains 8 million nodes and 400 million edges (shown in Table 2 and Figure 2). Moreover, we further compare each kernel in GraphZoom and MILE in Figure 3.
sections.heading: APPENDIX C INTEGRATE GRAPHZOOM WITH GRAPHSAGE AND DGI
sections.text: As both GraphSAGE and DGI require node features for embedding on coarsest graph, we map the initial node feature matrix X0 to the coarsened graph by iteratively performing Xi+1 = Ĥi+1i Xi, where Ĥi+1i is the mapping operatorH i+1 i with l
  1-normalization per row. When applying DGI to the coarsest graph (i.e., the l-th coarsening level), the node embeddings El may lose local information due to the property of DGI. Inspired by skip connection (He et al., 2016) and Graph U-nets (Gao & Ji, 2019), we use Êl = El||Xl as the node embeddings on the coarsest graph, where || denotes featurewise concatenation.
sections.heading: APPENDIX D GRAPH SIZE AT DIFFERENT COARSENING LEVEL
sections.heading: APPENDIX E GRAPHZOOM ALGORITHM
sections.text: Algorithm 1: GraphZoom algorithm Input: Adjacency matrix Atopo ∈ RN×N ; node feature matrix X ∈ RN×K ;
  base embedding function g(·); coarsening level l Output: Node embedding matrix E ∈ RN×D
  1 A0 = graph fusion(Atopo,X); 2 for i = 1...l do 3 Ai,H i i−1 = spectral coarsening(Ai−1); 4 end 5 EL = g(Al); 6 for i = l...1 do 7 Êi−1 = (H i i−1) T Ei;
  8 Ei−1 = refinement(Êi−1); 9 end
  10 E = E0;
sections.heading: APPENDIX F SPECTRAL COARSENING
sections.text: 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 Vi and the reduced node set Vi+1, where each node v ∈ Vi+1 corresponds to a small set of adjacent vertices in the original node set Vi. Mapping operator Hi+1i can be defined based on the mapping relationship between Vi and Vi+1, Note that the operator Hi+1i ∈ {0, 1}|
  Vi+1|×|Vi| is a matrix containing only 0s and 1s. It has following properties:
  • The row (column) index of Hi+1i corresponds to the node index in graph Gi+1 (Gi). • It is a surjective mapping of the node set, where (Hi+1i )p,q = 1 if node q in graph Gi is aggregated
  to super-node p in graph Gi+1, and (Hi+1i )p′,q = 0 for all nodes p′ ∈ {v ∈ Vi+1 : v 6= p}. • It is a locality-preserving operator, where the coarsened version of Gi induced by the non-zero
  entries of (Hi+1i )p,: is connected for each p ∈ Vi+1.
  Algorithm 2: spectral coarsening algorithm
  Input: Adjacency matrix Ai ∈ R|Vi|×|Vi| Output: Adjacency matrix Ai+1 ∈ R|Vi+1|×|Vi+1| of the reduced graph Gi+1, mapping operator H i+1i ∈ R|
  Vi+1|×|Vi| 1 n = |Vi|, nc = n; 2 [graph reduction ratio] γmax = 1.8 , δ = 0.9; 3 for each edge (p, q) ∈ Ei do 4 [spectral node affinity set] C← ap,q defined in Eq. 2 ; 5 end 6 for each node p ∈ Vi do 7 d(p) =
  ∣∣∣(Ai)p,:∣∣∣, dm(p) = median(∣∣∣(Ai)q,:∣∣∣ for all q ∈ {q|(p, q) ∈ Ei}); 8 if d(p) ≥ 8 · dm(p) then 9 [node aggregation flag] z(p) = 0;
  10 else 11 [node aggregation flag] z(p) = −1; 12 end 13 end 14 γ = 1; 15 while γ < γmax do 16 S = ∅ , U = ∅ ; 17 [unaggregated node set] U← p ∈ {p|z(p) == −1 ∀p ∈ Vi};
  18 S← p ∈ {p|ap,q ≥ δ ·max s 6=p,q
  ( max
  (p,s)∈ Ei
  ( ap,s ) , max (q,s)∈ Ei ( aq,s )) ∀p ∈ Vi};
  19 for each node p in S ∩ U do 20 if z(p) == −1 then
  21 q = argmax (p,q)∈ Ei
  ( ap,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;
sections.heading: 27 else
sections.text: 28 z(p) = z(q), q̂ = z(q);
sections.heading: 29 end
sections.text: 30 update smoothed vectors in T with x(k)p = x (k) q̂ for k = 1, · · · , t nc = nc − 1; 31 end 32 end 33 γ = n/nc, δ = 0.7 · δ ; 34 z(p) = p for node p ∈ {p|z(p) == 0} 35 end 36 form H i+1i and Ai+1 based on z
sections.heading: APPENDIX G CPU TIME OF EACH GRAPHZOOM KERNEL
sections.text: 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.
sections.heading: APPENDIX H GRAPH FILTERS AND LAPLACIAN EIGENVALUES
sections.text: Figure 5a shows the original distribution of graph Laplacian eigenvalues which also can be interpreted as frequencies in graph spectral domain (smaller eigenvalue means lower frequency). The proposed graph filter for embedding refinement (as shown in Figure 5e) can be considered as a bandstop 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 highfrequency noises from the graph signals. Fortunately, it has been shown that by adding self-loops to each node in the graph as follows Ã = A+σI (shown in Figure 5b, 5c, 5d, where σ = 0.5, 1.0, 2.0), the distribution of Laplacian eigenvalues can be squeezed to the left (towards zero) (Maehara, 2019). By properly choosing σ such that large eigenvalues will mostly lie in the stop band (e.g., σ = 1.0, 2.0 shown in Figure 5c and 5d), the graph filter will be able to effectively filtered out high-frequency components (corresponding to high eigenvalues) while retaining low-frequency components, which is similar to a low-pass graph filter as shown in Figure 5f. It is worth noting that if σ is too large, then most eigenvalues will be very close to zero, which makes the graph filter less effective for removing noises. In this work, we choose σ = 2.0 for all our experiments.
  APPENDIX I SPEEDUP OF GRAPHZOOM KERNELS COMPARED TO MILE
  As shown in Figure 6, the combination of GraphZoom coarsening and refinement kernels can always achieve the greatest speedups (green curves); adding GraphZoom fusion kernel (blue curves) will lower the speedups by a small margin but further boost the embedding quality, showing a clear trade-
  off between embedding quality and runtime efficiency: to achieve the highest graph embedding quality, the graph fusion kernel should be included.
sections.heading: APPENDIX J MORE RESULTS ON PPI DATASETS
sections.text: As shown in Figure 7, 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-
  Zoom embedding results can still beat the GraphSAGE baseline obtained with the original graph containing 14, 755 nodes.
sections.heading: APPENDIX K MORE RESULTS ON NON-ATTRIBUTED DATASETS
sections.text: 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 & Leskovec (2016); Liang et al. (2018). As shown in Table 5, GraphZoom (without fusion kernel) improves the performance of basic embedding model (i.e., DeepWalk) at the first coarsening level. When further increasing coarsening level, GraphZoom achieves much larger speedup while its performance may drop a little bit. For link prediction task, we 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.0×, showing GraphZoom can generate high-quality embeddings for various tasks.
sections.heading: APPENDIX L SENSITIVITY ANALYSIS OF GRAPH FUSION KERNEL
sections.text: As graph fusion kernel fuses node attribute with graph topology via Afusion = Atopo +βAfeat, the value of β plays a critical role in balancing attribute and topological information. On the one hand, if β is too small, we may lose too much node attribute information. On the other hand, if β is too
  large, the node attribute information will dominate the fused graph and therefore graph topological information is undermined. As shown in Figure 8, we vary β from 0.1 to 3 in graph fusion kernel and evaluate it on Cora, Citeseer, and Pubmed datasets. The results indicate that β = 1 achieves the best performance on Cora and Pubmed, while β = 0.5 is the best configuration on Citeseer. We choose β = 1 in all our experiments.