MILE: A Multi-Level Framework for Scalable Graph Embedding
Jiongqian Liang Saket Gurukar Srinivasan Parthasarathy

Viscous electron flow in mesoscopic two-dimensional electron gas.
    A. K. Bakarov
    December 30, 2023
=================================================================





	 Recently there has been a surge of interest in designing graph embedding methods. Few, if any, can scale to a large-sized 
graph with millions of nodes due to both computational complexity and memory requirements.
In this paper, we relax this limitation by introducing the MultI-Level Embedding (MILE) framework – a generic methodology allowing contemporary graph embedding methods to scale to large graphs.
MILE repeatedly coarsens the graph into smaller ones using a hybrid matching technique 
to maintain the backbone structure of the graph.
It then applies existing embedding methods on the coarsest graph and 
refines the embeddings to the original graph through a graph convolution neural network that it learns.




The proposed MILE framework is agnostic to the underlying graph embedding techniques and can be applied
to many existing graph embedding methods without modifying them.
We employ our framework on several popular graph embedding techniques and conduct embedding for real-world graphs.
Experimental results on five large-scale datasets demonstrate that MILE significantly boosts the speed (order of magnitude)
of graph embedding while generating embeddings of better quality, for



the task of node classification.
MILE can comfortably scale to a graph with 9 million nodes and 40 million edges, 
on which existing methods run out of memory or take too long to compute on a modern workstation.
Our code and data are publicly available with detailed instructions for adding new base embedding methods: <https://github.com/jiongqian/MILE>. 






§ INTRODUCTION




In recent years, network embedding has attracted much interest due to its broad applicability for a range of tasks such as social influence prediction <cit.>, network role discovery<cit.>, political perspective detection <cit.>, and social recommender systems <cit.>.

COMMENTED OUT

role discovery <cit.>, query pattern matching <cit.>, 
 visualization <cit.>,

including database cleaning <cit.>,

exploratory data analysis <cit.>,
distance oracles <cit.>, 
classification <cit.>
and link prediction <cit.>



While these new embedding methods often offer a competitive qualitative advantage over traditional approaches,
many of them do not scale to large datasets (e.g., graphs with over 1 million nodes) since they are computationally expensive and often memory intensive. 
For example, random-walk-based embedding techniques such as DeepWalk <cit.> and Node2Vec <cit.>, 
require a large amount of CPU time to generate a sufficient number of walks and train the embedding model. 
It takes over 10 hours for a single machine to achieve quality embeddings on a graph with a million nodes using such methods. 

COMMENTED OUT

As another example, embedding methods based on matrix factorization, including GraRep <cit.> and NetMF <cit.>, requires constructing an enormous objective matrix (usually much denser than adjacency matrix), on which matrix factorization is performed. Even a medium-size graph with 100K nodes can easily require hundreds of GB of memory using those methods.
On the other hand, many graph datasets in the real world tend to be large-scale with millions or even billions of nodes.


To the best of our knowledge, none of the existing efforts examines how to scale up graph embedding in a generic way. We make the first attempt to close this gap. We are also interested in the related question of whether the quality of such embeddings can be improved along the way. Specifically, we ask:




  * Can we scale up the existing embedding techniques in an agnostic manner so that they can be directly applied to larger datasets?


  * Can the quality of such embedding methods be strengthened by incorporating the holistic view of the graph? 



To tackle these problems, we propose a MultI-Level Embedding (MILE) framework for graph embedding. Our approach relies on a three-step process: first, we repeatedly coarsen the original graph into smaller ones
by employing a hybrid matching strategy; second, we compute the embeddings on the coarsest graph using an existing  
embedding technique - 
note that graph embedding on the coarsest graph is inexpensive to compute and utilizes far less memory,
and moreover intuitively can capture the global structure of the original graph <cit.>; 
and third,
we propose a novel refinement model based on learning a graph convolution network to refine the embeddings from 
the coarsest graph to the original graph – learning a graph convolution network allows us to attain a refinement procedure that levers the dependencies inherent to the graph structure and the embedding method of choice. 


To summarize, we find:





  * MILE is generalizable: Our MILE framework is agnostic to the underlying graph embedding techniques and treats them as black boxes.




  * MILE is scalable: MILE can significantly improve the scalability of the embedding methods (up to 30-fold), by reducing the running time and memory consumption. 




  * MILE generates high-quality embeddings: In many cases, we find that the quality of embeddings improves by levering MILE (in some cases is in excess of  10%). 






















In recent years, graph embedding has attracted much interest due to its broad applicability for various tasks  <cit.>.


However, such methods rarely scale to large datasets (e.g., graphs with over 1 million nodes) since they are computationally expensive and often memory intensive. 
For example, random-walk-based embedding techniques

require a large amount of CPU time to generate a sufficient number of walks and train the embedding model. 

As another example, embedding methods based on matrix factorization, including GraRep <cit.> and NetMF <cit.>, requires constructing an enormous objective matrix (usually much denser than adjacency matrix), on which matrix factorization is performed. Even a medium-size graph with 100K nodes can easily require hundreds of GB of memory using those methods.
On the other hand, many graph datasets in the real world tend to be large-scale with millions or even billions of nodes.
For instance, Google's knowledge graph covers over 570M entities while
Facebook friendship graph contains at least 1.39B user dataset with over 1 trillion connections <cit.>.
To the best of our knowledge, none of the existing efforts examines how to scale up graph embedding in a generic way. We make the first attempt to close this gap. We are also interested in the related question of whether the quality of such embeddings can be improved along the way. Specifically, we ask:




  * Can we scale up the existing embedding techniques in an agnostic manner so that they can be directly applied to larger datasets?


  * Can the quality of such embedding methods be strengthened by incorporating the holistic view of the graph? 



To tackle these problems, we propose a MultI-Level Embedding (MILE) framework for graph embedding. Our approach relies on a three-step process: first, we repeatedly coarsen the original graph into smaller ones
by employing a hybrid matching strategy; second, we compute the embeddings on the coarsest graph using an existing  
embedding techniques - 


and third,
we propose a novel refinement model based on learning a graph convolution network to refine the embeddings from 
the coarsest graph to the original graph – learning a graph convolution network allows us to compute a refinement procedure that levers the dependencies inherent to the graph structure and the embedding method of choice. 


To train this model for embeddings refinement, we design a particular learning task on the coarsest graph, which is efficient to perform. 
To summarize, we find that:





  * MILE is generalizable : Our MILE framework is agnostic to the underlying graph embedding techniques and treats them as black boxes.




  * MILE is scalable : MILE can significantly improve the scalability of the embedding methods (up to 30-fold), by reducing the running time and memory consumption. 




  * MILE generates high-quality embeddings :  In many cases, we find that the quality of embeddings improves by levering MILE (in some cases is in excess of  10%). 






























§ RELATED WORK






Network Embedding:
Many techniques for graph or network
embedding have been proposed in recent years.
DeepWalk and Node2Vec generate truncated random walks on graphs and 
apply the Skip Gram by treating the walks as sentences <cit.>.

LINE learns the node embeddings by preserving the first-order and second-order proximities <cit.>.
Following LINE, SDNE leverages deep neural networks to capture the highly non-linear structure <cit.>.
Other methods construct a particular objective matrix and use matrix factorization techniques to generate embeddings,
e.g., GraRep <cit.> and NetMF <cit.>.
This also led to the proliferation of network embedding methods for information-rich graphs, 
including heterogeneous information networks <cit.> and
attributed graphs <cit.>. 

There are very few efforts, focusing on the scalability of network embedding <cit.>.
First, such efforts are specific to a particular embedding strategy and do not generalize. Second, the scalability of such efforts is  limited to moderately sized datasets. Finally, and notably, these efforts at scalability are actually orthogonal to our strategy and can potentially be employed along with our efforts to afford even greater speedup. 


The closest work to this paper is HARP <cit.>, which proposes a hierarchical paradigm for graph embedding based on
iterative learning methods (e.g., DeepWalk and Node2Vec).
However, HARP focuses on improving the quality of embeddings by using 
the learned embeddings from the previous level
as the initialized embeddings for the next level, which introduces a huge computational overhead.
Moreover, it is not immediately obvious how a HARP like a methodology would be extended to other graph embedding techniques (e.g., GraRep and NetMF) in an agnostic manner since such an approach would necessarily require one to modify the embedding methods to preset their initialized embeddings. 
In this paper, we focus on designing a general-purpose framework to scale up embedding methods treating them as black boxes. 















Multi-level Community Detection:

The multi-level approach has been widely studied for efficient community detection <cit.>.



The key idea of these multi-level algorithms is to coarsen the original graph into a much smaller one, which is
then partitioned into clusters. The partitions are then recovered from the coarse-grained graph to the original graph in a recursive manner.
While our framework shares some ideas at a conceptual level with such efforts, the objectives are distinct in that we focus on graph embeddings while these methods work on graph partitioning and community discovery. 




























§ PROBLEM FORMULATION


Let 𝒢 = (V, E) be the input graph 
where V and E are respectively the node set and edge set.
Let A be the adjacency matrix of the graph  


and we assume 𝒢 is undirected, though our problem can be easily extended <cit.> to a directed graph. Table <ref> shows the table of notations. We first define graph embedding:


Graph Embedding
Given a graph 𝒢 = (V, E) and a 
pre-defined 
dimensionality d (d ≪ |V|),
the problem of graph embedding is to learn a d-dimension vector representation for 
each node in 
graph
𝒢 so that graph properties are best preserved.


Following this, a graph embedding method is essentially a mapping 
function f: ℝ^|V|× |V|↦ℝ^|V|× d, whose input is the adjacency matrix A (or 𝒢)
and output is a lower dimension matrix.  Motivated by the fact that the majority of graph embedding methods cannot scale to large datasets, we seek to speed up 
existing graph embedding methods without sacrificing quality.
We formulate the problem as: 

 Given a graph 𝒢 = (V, E) and a graph embedding method f(·), we aim to 
realize a strengthened graph embedding method f̂(·) so that it is more scalable 
than f(·) while generating embeddings of comparable or even better quality.






§ METHODOLOGY





















To address the aforementioned problem, we propose a scalable 
MultI-Level Embedding (MILE) framework. 


Figure <ref> shows the overview of our MILE framework,
which contains three key phases: graph coarsening, base embedding, and embeddings refining. 

On the whole, we reduce the size of the graph through repeated coarsening and 
run graph embedding on the coarsest graph, after which we perform embeddings refinement to recover
the embeddings on the original graph.

We summarize some important notations in Table <ref>
and describe our framework in detail below.




The MILE framework comprises three phases: graph coarsening, base embedding, and refinement (see Figure <ref>), described next. 

COMMENTED OUT
 Table <ref> includes common notations used in this paper. 





 §.§ Graph Coarsening



In this phase, the input graph 𝒢 (or 𝒢_0) is repeatedly coarsened into a series of smaller graphs 
𝒢_1, 𝒢_2, ..., 𝒢_m such that |V_0| > |V_1| > ... > |V_m|.
In order to coarsen a graph from 𝒢_i to 𝒢_i+1, 
multiple nodes in 𝒢_i are collapsed to form super-nodes in 𝒢_i+1,
and the edges incident on a super-node are the union of the edges on the original nodes in 𝒢_i.
Here the set of nodes forming a super-node is called a matching.
We propose a hybrid matching technique containing two
matching strategies that can efficiently coarsen the graph while retaining the global structure. A toy example is shared in Figure <ref>. =-1




We follow the strategy in existing work <cit.> for weighting self-loops (the weight of the self-loop on node BC is 2 instead of 1).






Structural Equivalence Matching (SEM) : Given two vertices u and v in an unweighted graph 𝒢, we call they are structurally equivalent if they are incident on the same set of neighborhoods. In figure <ref>, node D and E are structurally equivalent. The intuition of matching structually equivalent nodes is that if two vertices are structurally equivalent, then their node embeddings will be similar. The novel SEM method – though dependent on graph structure –  is highly effective on the real world datasets.
 Empirically, we found 5-20% of nodes to be structurally equivalent in many real world datasets. For example, during the first level of coarsening, YouTube has 172,906 nodes (or 86,453 pairs) out of 1,134,890 nodes that are found to be SEM (around 15%); Yelp has 875,236 nodes (or 437,618 pairs) out of 8,938,630 nodes are SEM (around 10%). Note that even more nodes are involved in SEM 
across iterations, as SEM is run iteratively at each coarsening level.





If two vertices u and v in an unweighted graph 𝒢 are structurally equivalent,
then their node embeddings derived from 𝒢 will be identical.




This can be proved by reasoning on the fact that the two nodes are non-distinguishable and interchangeable on 𝒢 if they share the same set of the neighborhoods (details of proof omitted due to the limit of space). 
Base on Theorem <ref>, we define a structural equivalence matching as a set of nodes that are structurally equivalent to each other.
For the example in Figure <ref>, nodes D and E are considered a structural equivalent matching.



Normalized Heavy Edge Matching (NHEM) : Heavy edge matching is a popular matching method for graph coarsening <cit.>. 
We select an unmatched node, say u, in the graph and find a large weighted edge  (u, v) incident on node u such that node v is also unmatched. We then collapse nodes u and v into one super-node and mark them as matched. We repeat the matching process until there are no unmatched nodes or an unmatched node does not have an unmatched neighbor node. 
In this paper, we propose to normalize the edge weights when applying heavy edge matching using the formula as follows

    W_i(u, v) = A_i(u, v)/√(D_i(u, u) · D_i(v, v)).

In Eq. <ref>,
Here,
the weight of an edge is normalized by the degree of the two vertices on which the edge is incident.
Intuitively, it penalizes the weights of edges connected with high-degree nodes.
For the example in Figure <ref>, 
node B is equally likely to be matched with node A and node C without edge weight normalization.
With normalization, node B will be matched with C, which is a better matching since B is more 
structurally similar to C. 




We will show later that this normalization is tightly connected with the graph convolution kernel.

Hybrid Matching Method  : We use a hybrid of two matching methods above for graph coarsening. 
To construct 𝒢_i+1 from 𝒢_i, 
we first find out all the structural equivalence matching (SEM) ℳ_1, 
where 𝒢_i is treated as an unweighted graph.
This is followed by the searching of the normalized heavy edge matching (NHEM) ℳ_2 on 𝒢_i.
Nodes in each matching are then collapsed into a super-node in 𝒢_i+1.
Note that some nodes might not be matched at all and they will be directly copied to 𝒢_i+1.
Figure <ref> provides a toy example for illustrating the process.




Formally, we build the adjacency matrix A_i+1 of 𝒢_i+1 through matrix operations.
To this end, we define the matching matrix storing the matching information from graph 𝒢_i to 𝒢_i+1 as a binary matrix M_i, i+1∈{0, 1}^|V_i|×|V_i+1|. The r-th row and c-th column
of M_i, i+1 is set to 1 if node r in 𝒢_i will be collapsed to super-node c in 𝒢_i+1, and 
is set to 0 if otherwise. 
Each column of M_i, i+1 represents a matching with the 1s representing the nodes in it.

Each unmatched vertex appears as an individual column in M_i, i+1 with merely one entry set to 1.
For the toy example in Figure <ref>, matching matrix M_0,1 of dimension 5× 3 indicates the mapping information from the original graph to the coarsened graph. In particular, 2nd row and 3rd row means node B and node C form a matching and are mapped to super-node BC in the coarsened graph (similar for 4th and 5th row).
Following this formulation, we construct the adjacency matrix of 𝒢_i+1 by using

    A_i+1 = M_i, i+1^TA_iM_i, i+1.



Algorithm <ref> summarizes the steps of graph coarsening. 
For each iteration of coarsening,
SEM is generated followed by NHEM (line 2-9). 
A key part of NHEM is to visit the vertices in ascending
order of the number of neighbors (line 5).
This is important to ensure that a large fraction of vertices can be matched in each step, and the graph can be coarsened significantly.
Intuitively, vertices with a small number of neighbors have a limited choice of finding a match and should be given a
higher priority for matching (otherwise, once their neighbors are matched by others, these vertices cannot be matched).






Key Intuitions:
The graph coarsening phase significantly reduces the size of graph while maintaining the clustering structure and backbone of the original graph.

The coarsening phase also potentially exposes the global structure of the graph to the base embedding method that it otherwise might not take into account thereby offering a potential efficacy gain (up to a point). This efficacy gain has also been observed elsewhere, in the context of stochastic flow algorithms <cit.>. Note that stochastic flow algorithms share some common mathematical abstraction to several graph embedding methods  <cit.>. The embeddings learned by base embedding method on the coarsened graph can act as an effective initialization for the graph-topology aware refinement model. 







Choice for Coarsening Level:
Similar to other multi-level frameworks, such as graph partitioning <cit.> and visualization <cit.>, the choice of coarsening level depends on the application domain and the graph properties. However, we found a small number of coarsening levels (from 2 to 4) usually yields the best-quality embeddings with decent speedup when the graph is of medium size (# nodes < 1,000,000). For larger graph (# nodes > 1,000,000), the embeddings tend to remain constantly high-quality even with coarsening levels from 6 to 8 while speedup increases even more. We defer our detailed discussion on this to the experiments section. 























pseudocode














 §.§ Base Embedding on Coarsened Graph



The size of the graph reduces drastically after each iteration of coarsening, 
halving the size of the graph in the best case. 
We coarsen the graph for m iterations and apply the graph embedding method f(·)
on the coarsest graph 𝒢_m. 

Denoting the embeddings on 𝒢_m as ℰ_m, we have ℰ_m = f ( 𝒢_m ). Since our framework is agnostic to the adopted graph embedding method,
we can use any graph embedding algorithm for base embedding.  












 §.§ Refinement of Embeddings



The final phase of MILE is the embedding refinement.
Given a series of coarsened graph 𝒢_0, 𝒢_1, 𝒢_2, ..., 𝒢_m, their corresponding matching matrix M_0,1, M_1,2, ..., M_m-1, m, and the node embeddings ℰ_m 
on 𝒢_m, we seek to develop an approach to derive the node embeddings of 𝒢_0 from 𝒢_m.
To this end, we first study an easier subtask:
given a graph 𝒢_i, its coarsened graph 𝒢_i+1, the matching matrix M_i, i+1
and the node embeddings ℰ_i+1 on 𝒢_i+1, how to infer the embeddings ℰ_i
on graph 𝒢_i.
Once we solved this subtask,
we can then iteratively apply the technique on each pair of consecutive graphs
from 𝒢_m to 𝒢_0 and eventually derive the node embeddings on 𝒢_0.
In this work, we propose to use a graph-based neural network model to perform embedding refinement.


Graph Convolution Network for  Refinement Learning : 
Since we know the matching information between the two consecutive graphs 𝒢_i and 𝒢_i+1,
we can easily project the node embeddings from the coarse-grained graph 𝒢_i+1 to
the fine-grained graph 𝒢_i using

    ℰ^p_i = M_i, i+1ℰ_i+1

In this case, embedding of a super-node is directly copied to its original node(s).
We call ℰ^p_i the projected embeddings from 𝒢_i+1 to 𝒢_i, or simply projected embeddings without ambiguity. 
While this way of simple projection maintains some information of node embeddings,
it has an obvious limitation that 
nodes will share the same embeddings 
if they are matched and collapsed into a super-node during the coarsening phase.
This problem will be more serious when the embedding refinement is performed iteratively from 
𝒢_m, ..., 𝒢_0. 
To address this issue, we propose to learn a graph convolution network (GCN) for embedding refinement <cit.>.
Specifically, we design a graph-based neural network model ℰ_i = 
ℛ(ℰ^p_i, A_i),  which derives the embeddings ℰ_i on graph 𝒢_i based on the projected embeddings  ℰ^p_i (from the base method) and the graph adjacency matrix A_i (from the input graph).


 





we consider the graph convolution <cit.> of d-channel input signals X with filters g on G as

    X ∗_G g = U θ_g U^T X.

Here, θ_g = diag(θ) is parameterized by spectral multipliers θ∈ℝ^|V| in the Fourier domain, U is the matrix of eigenvectors of the normalized graph Laplacian L = I - D^-1/2 A D^-1/2, where D is a diagonal matrix with entries
D(i, i) = ∑_j A(i, j).


Since Eq. <ref> can be computationally expensive, 
we use its fast approximate version from <cit.>:

    X ∗_G g ≈D̃^-1/2ÃD̃^-1/2 X  Θ





where Ã = A + λ D, D̃(i, i) = ∑_j Ã(i, j), Θ∈ℝ^d× d, and λ∈ [0, 1] is a hyper-parameter for controlling the weight of self-loop. 
As this approximate convolution model can be regarded as a layer-wise linear model,
we can stack multiple such layers to achieve a model of higher capacity. 



Given graph G with adjacency matrix A, we consider the fast approximation of graph convolution from <cit.>. The k-th layer of this neural network model is

    H^(k)(X, A) = σ( D̃^-1/2ÃD̃^-1/2 H^(k-1)(X, A) Θ^(k))

where σ(·) is an activation function, Θ^(k) is a layer-specific trainable weight matrix, and H^(0)(X, A) = X. In this paper, we define our embedding refinement model as a l-layer graph convolution model

    ℰ_i = ℛ(ℰ^p_i, A_i) ≡ H^(l)(ℰ^p_i, A_i ).



The architecture of the refinement model is shown in Figure <ref>. The intuition behind this refinement model is to integrate the structural information of the current graph 𝒢_i
into the projected embedding ℰ^p_i by repeatedly performing the spectral graph convolution. 

Each layer of graph convolution network in Eq. <ref> can be regarded as one iteration of embedding propagation
in the graph following the re-normalized adjacency matrix D̃^-1/2ÃD̃^-1/2.
Note that this re-normalized matrix is well aligned with the way we conduct normalized heavy edge matching in Eq. <ref>. 


 Choice for Number of GCN Layers:
The graph convolution model is often treated as a message passing operator <cit.> with the number of layers corresponding to the number of hops in the graph. In other words, l GCN layers correspond to aggregating structural information from all the l-hop neighbours for each node. 
On the one hand, we want l to be larger than 1 so that node embeddings can reflect connectivity structure beyond immediate neighbors. On the other hand, we also do not want too large an l as it will make the node embeddings homogeneous and less distinguishable across the graph due to the small-world property of real-world graphs. Similar to existing literature <cit.> we find that setting l to 2 worked best in practice.














Intricacies of Refinement Learning : 

The learning of the refinement model is essentially learning
Θ^(k) for each k ∈ [1, l] according to Eq. <ref>.
Here we study how to design the learning task and construct the loss function. Since the graph convolution model H^(l)(·) aims to predict the embeddings ℰ_i on graph 𝒢_i, we
can directly run a base embedding on 𝒢_i to generate the “ground-truth” embeddings
and use the difference between
these embeddings and the predicted ones as the loss function for training. 
We propose to learn Θ^(k) on the coarsest graph and reuse them across all the levels for refinement.







Specifically, we can define the loss function as the mean square error as follows

    L = 1/|V_m|‖ℰ_m - H^(l)(M_m, m+1ℰ_m+1, A_m) ‖^2.


We refer to the learning task associated with the above loss function as double-base embedding learning.

We point out, however, there are two key drawbacks to this method.
First of all, the above loss function requires one more level of coarsening to construct 𝒢_m+1 and an extra base embedding on 𝒢_m+1.
These two steps, especially the latter, introduce non-negligible overheads to the MILE framework.
More importantly, ℰ_m might not be a desirable “ground truth” for the refined embeddings. 
This is because most of the embedding methods are invariant to an orthogonal transformation of the embeddings, i.e., the embeddings can be rotated by an arbitrary 
orthogonal matrix <cit.>. In other words, the embedding spaces of graph 𝒢_m and 𝒢_m+1 can be totally different since the two base embeddings are learned independently. 
Even if we follow the paradigm in <cit.> and conduct base embedding on 𝒢_m using the simple projected embeddings
from 𝒢_m+1 (ℰ^p_m) as initialization, the embedding space does not naturally generalize and can drift during re-training. 
One possible solution is to use an alignment procedure to force the embeddings to be aligned between the two graphs  <cit.>. But it could be very expensive.

In this paper, we propose a very simple method to address the above issues. Instead of conducting an additional level of coarsening,
we construct a dummy coarsened graph by simply copying 𝒢_m, i.e., M_m,m+1 = I and 𝒢_m+1 = 𝒢_m. 
By doing this, we not only reduce one iteration of graph coarsening, but also avoid performing base embedding on 𝒢_m+1 simply because
ℰ_m+1=ℰ_m. Moreover, the embeddings of 𝒢_m and 𝒢_m+1 are guaranteed to be in the same space in this case without any drift. With this strategy, we change the loss function for model learning as follows

    L = 1/|V_m|‖ℰ_m - H^(l)(ℰ_m, A_m) ‖^2.



We minimize the difference between the generated embeddings and the embeddings generated from the refinement model (GCN based) so that the learnt refinement model could then be levered to generate embeddings in other coarsening levels. With the above loss function, we adopt gradient descent with back-propagation to learn the 
parameters Θ^(k), k ∈ [1, l]. In the subsequent refinement steps, 
we apply the same set of parameters Θ^(k) to infer the refined embeddings. 
We point out that the training of the refinement model is rather efficient as it is done on the coarsest graph.

The embedding refinement process involves merely sparse matrix
multiplications using Eq. <ref> and is relatively affordable compared to conducting embedding on 
the original graph. With these different components, we summarize the whole algorithm of our MILE framework in Algorithm <ref>. 






pseudocode







Discussion on Reusing Θ^(k) Across All Levels:
 Similar to GCN, Θ^(k)  is a matrix of filter parameters and is of size d*d (where d is the embedding dimensionality). Eq. <ref> 


 defines how the embeddings are propagated during embedding refinements, parameterized by Θ^(k) . Intuitively,  Θ^(k)  defines how different embedding dimensions interact with each other during the embedding propagation. This interaction is dependent on graph structure and base embedding method, which can be learned from the coarsest level.  Ideally, we would like to learn this parameter Θ^(k)  on  consecutive levels. But this is not practical since this could be expensive as the graph gets more fine-grained (and defeat our purpose of scaling up graph embedding). This trick of “sharing” parameters across different levels is the trade-off between efficiency and effectiveness. To some extent, it is similar to  GCN <cit.>, where the authors share the same filter parameters Θ^(k)  over the whole graph (as opposed to using different Θ^(k)  for different nodes; see Eq (6) and (7) in<cit.>). Moreover, we empirically found this works well and is much more efficient. As we will reveal in the Experiments section, the shared Θ^(k) values do much better than alternative Θ^(k) choices during refinement (see Table <ref>). 
 
 
 
 
 


Intuition and Rationale of Embedding Refinements:
Refining the embeddings from a coarsened graph to its fine-grained graph boils down to two steps: a) projecting the node embeddings back to fine-grained graph based on  correspondence matching; and b) propagating the projected embeddings locally, adjusting them based on the fine-grained graph structure. The first step is relatively straightforward through matrix multiplication (Eq. <ref>). For the second step, we re-purpose the GCN model to propagate the node embeddings. There are mainly two reasons that GCN performs well in this part. First, the propagation rule in GCN is shown to be a first-order approximation of the localized spectral filters on graphs <cit.> and as a result, the propagated embeddings can  capture the local graph structure. Second, GCN contains learnable Θ^(k) and is capable of modeling the interaction between different embedding dimensions in the propagation process, as discussed above.






 §.§ Time Complexity Analysis



COMMENTED OUT

 It is non-trivial to derive the exact time complexity of MILE as it is dependent on the graph structure, the chosen base embedding method, and the convergence rate of the GCN model training. Here, we provide a rough estimation of the time complexity.  For simplicity, we assume the number of vertices and the number of edges are reduced by factor α and β respectively at each step of coarsening
 (α>1.0 and β>1.0),
 i.e., V_i = 1/αV_i-1 and E_i = 1/βE_i-1 (we found α and β in range [1.5, 2.0], empirically).  With m levels of coarsening, the coarsening complexity is approximately O((1- 1/βm)/(1- 1/β) × E)) and since 1/βm is very small, the complexity can be reduced to O(β/β-1× E).
 For the base embedding phase, suppose the embedding algorithm has time complexity of T(V, E), the complexity of the base embedding phase is
 T(V/α^m, E/β^m).
 For the refinement phase, the time complexity can be divided into two parts, i.e. the GCN model training and the embedding inference applying the GCN model. 
 The former has similar complexity as the original GCN and can be denoted as O(k_1*E/β ^m) <cit.>, where k_1 is a small constant related to embedding dimensionality and the number of training epochs.
 
 The embedding inference part is simply sparse matrix multiplication using Eq. <ref> with time complexity O(k_2*E/β ^m)
 when refining the embeddings on graph 𝒢_i, where k_2 is an even smaller
 constant (k_2 < k_1). As a result, the time complexity of the whole refinement phase is
 O(k_1*E/β ^m +  k_2*(E + E/β ^1 ... + E/β ^m-1)) ≈ O(k_3 * E) where k_3 is a small constant. 
 
 
 
 
 
 
 
 
 
 

 Overall, for an embedding algorithm of time complexity T(V, E), the MILE framework can reduce it to be
 T(V/α^m, E/β^m) + O(k*E). This is a significant improvement considering T(V, E) is usually very large.
 The reduction in time complexity is attributed to the fact that we run the embedding learning and refinement model training at the coarsest graph.
 In addition, the overhead introduced by
 the coarsening phase and recursive embedding refinement is relatively small (linear to the number of edges E).
 Note that the constant factor k in the complexity term is usually small and we empirically found it to be in the scale of tens.
 Because of this, even when the complexity of the original embedding algorithm T(V, E) is linear to E, our MILE framework
 could still potentially speed up the embedding process because the complexity of MILE contains a smaller constant factor k (see Sec. <ref>
 for the experiment of applying MILE on LINE). 


Furthermore,
it is worth noting that many of the existing embedding strategies
involve hyperparameters tunning for the best performance,
especially for those methods based on neural networks (e.g., DeepWalk, Node2Vec, etc.).


This, in turn, requires the algorithm to be run repeatedly – hence any savings in runtime by applying MILE are magnified across multiple runs of the algorithm with different hyper-parameter settings.








§ TIME COMPLEXITY



  
 It is non-trivial to derive the exact time complexity of MILE as it is dependent on the graph structure, the chosen base embedding method, and the convergence rate of the GCN model training. Here, we provide a rough estimation of the time complexity.  For simplicity, we assume the number of vertices and the number of edges are reduced by factor α and β respectively at each step of coarsening 
(α>1.0 and β>1.0),
i.e., V_i = 1/αV_i-1 and E_i = 1/βE_i-1. (we found α and β in range [1.5, 2.0], empirically).  With m levels of coarsening, the coarsening complexity is approximately O((1- 1/βm)/(1- 1/β) × E)) and since 1/βm is small, the complexity reduces to O(β/β-1× E).
For the base embedding phase, if the embedding algorithm has time complexity of T(V, E), the complexity of the base embedding phase is
T(V/α^m, E/β^m).
For the refinement phase, the time complexity can be divided into two parts, i.e. the GCN model training and the embedding inference applying the GCN model.
The former has similar complexity as the original GCN and can be denoted as O(k_1*E/β ^m) <cit.>, where k_1 is a small constant related to embedding dimensionality and the number of training epochs. 

The embedding inference part is simply sparse matrix multiplication using Eq. 
H^(k)(X, A) = σ( D̃^-1/2ÃD̃^-1/2 H^(k-1)(X, A) Θ^(k))
with time complexity O(k_2*E_i)
when refining the embeddings on graph 𝒢_i, where k_2 is an even smaller
constant (k_2 < k_1). As a result, the time complexity of the whole refinement phase is 
O(k_1*E/β ^m +  k_2*(E + E/β ^1 ... + E/β ^m-1)) ≈ O(k_3 * E) where k_3 is a small constant.




Overall, for an embedding algorithm of time complexity T(V, E), the MILE framework can reduce it to be 
T(V/α^m, E/β^m) + O(k*E). This is a significant improvement considering T(V, E) is usually very large. 
The reduction in time complexity is attributed to the fact that we run the embedding learning and refinement model training at the coarsest graph. 
In addition, the overhead introduced by
the coarsening phase and recursive embedding refinement is relatively small (linear to the number of edges E). 
Note that the constant factor k in the complexity term is usually small and we empirically found it to be in the scale of tens. 
Because of this, even when the complexity of the original embedding algorithm is linear to E, our MILE framework
could still potentially speed up the embedding process because the complexity of MILE contains a smaller constant factor k. 

Furthermore,
it is worth noting that many of the existing embedding strategies 
involve hyper-parameter tuning for the best performance,
especially for those methods based on neural networks (e.g., DeepWalk, Node2Vec, etc.). 


This, in turn, requires the algorithm to be run repeatedly – hence any savings in runtime by applying MILE are magnified across multiple runs of the algorithm with different hyper-parameter settings.



 





§ EXPERIMENTS AND ANALYSIS


































Datasets: The datasets used in our study (See Table <ref>) have seen prior use for evaluating representation learning methods <cit.> and are primarily drawn from popular social media platforms while one is drawn from a well curated bioinformatics dataset.  We preprocess the Yelp dataset following a procedure described in  <cit.>[Raw data: <https://www.yelp.com/dataset_challenge/dataset>]. 




The details of these datasets are shown below:

  
  *  PPI is a Protein-Protein Interaction graph constructed based on the interplay 
  activity between proteins of Homo Sapiens, where the labels represent biological states. 
  
  *  Blog is a network of social relationship of bloggers on BlogCatalog and the labels indicate interests of the bloggers. 
  
  *  Flickr is a social network of the contacts between users on flickr.com with labels denoting the interest groups. 
  
  *  YouTube is a social network between users on YouTube, where labels represent genres of groups subscribed by users.
  
  *  Yelp is a social network of friends on Yelp and 
  labels indicate the business categories on which the users review.


The first four datasets have been previously used to evaluate graph embedding strategies <cit.>, while Yelp dataset is preprocessed by us following a procedure previously described elsewhere <cit.>[Raw data: <https://www.yelp.com/dataset_challenge/dataset>].





  

 
 


Base Embedding Methods: 
To demonstrate that MILE can work with
different graph embedding methods, we explore several popular methods for graph embedding.
 



  * Random-walk based methods: We select DeepWalk <cit.> and Node2Vec <cit.> as baseline methods for this group. We set the length of random walks as 80, number of walks per node as 10, and context windows size as 10. In Node2Vec, we set p=4.0 and q=1.0 which we found empirically to generate better results across all the datasets.


  * Edge reconstruction based method: We select Line <cit.> as it is a representative work in this group. The number of edge samples is set to 100 million.


  * Matrix-factorization based methods : 
GraRep <cit.> and NETMF  <cit.> are two popular methods in this group. For GraRep, we set k=4. We varied this parameter but found this value to work well (also suggested by the original authors <cit.>). For NetMF, we set the window size to 10 and the rank h to 1024.


  * Deep neural network based methods: We lever SDNE <cit.> as an exemplar for this group. We set alpha to 0.2 and beta to 10.0. We varied these parameters and found these values to work well – these parameter values also work well in original paper. 




  * Distributed embedding methods:  We compare MILE against Pytorch-biggraph <cit.>. We set the parameter negative batch sizes to 500 and set learning rate to 0.01. We varied these parameters and found these values to work well – these parameters fall in the suggested values by the authors <cit.>.







  
  * DeepWalk (DW) <cit.>: 
  This method generates truncated random walks on graphs and 
  applies the Skip Gram by treating the walks as sentences. 
  Following the original work <cit.>, we set the length of random walks as 80, number of walks per node as 10, and context windows size as 10. 
  
  * Node2Vec (NV) <cit.>: 
  This is an improved version of DeepWalk, where it generates random walks with more flexibility controlled through parameters p and q. 
  We use the same setting as DeepWalk for those common hyper-parameters while setting p=4.0 and q=1.0, which we found empirically to generate better results across all the datasets. 
  
  * Line (LN) <cit.>: This method aims at preserving first-order and second-order proximities and has been applied on large-scale graph. We learn the first-order and second-order embeddings respectively and concatenate them to a unified embedding.    
  
  * GraRep (GR) <cit.>: This method considers different powers (up to k) of the adjacency matrix to preserve higher-order graph proximity for graph embedding. It uses SVD decomposition to generate the low-dimensional representation of nodes. 
  We set k = 4 as suggested in the original work.
  
  * NetMF (NM) <cit.>: 
  It is a recent effort that supports  
  graph embedding via matrix factorization. 
  
  We set the window size to 10 and the rank h to 1024, and lever the approximate version, as suggested and reported by the authors. 
  







By showing the performance gain of using MILE on top of these methods, we want to ensure the contribution of this work is of broad interest to the community.  We also want to reiterate that these methods are quite different in nature. 








COMMENTED OUT

Though NetMF <cit.> with an appropriately constructed objective matrix has been shown to approximate DW, N2V and Line through implicit matrix factorization,there are limitations to such approximations <cit.>. The most important one is the requirement of a sufficiently large embedding dimensionality.Additionally, we note that while unification is possible under such a scenario, the methods based on matrix factorization are quite different from the original methods and do place a much larger premium on space (memory consumption) - in fact this is observed in our experiments where we are unable to run NetMF and GraRep in many cases without incorporating them within MILE (see experimental results below).







MILE-specific Settings: 
For all the above base embedding methods, we set the embedding dimensionality d as 128.
When applying our MILE framework,
we vary the coarsening levels m from 1 to 8 whenever possible.

For the graph convolution network model,
the self-loop weight λ is set to 0.05, the number of hidden layers l is 2,
and tanh(·) is used as the activation function,
the learning rate is set to 0.001 and the number of training epochs is 200.
The Adam Optimizer is used for model training.





Evaluation Metrics: 
We evaluate the quality of the embeddings through multi-label node classification <cit.> and link prediction <cit.>. 
Specifically, for node classification, we run a 10-fold cross validation using the embeddings as features and report the average Micro-F1 and average Macro-F1.
For link prediction, we follow the setup described in <cit.>. Specifically, we evaluate the link prediction performance in terms of AUROC on 5-fold cross validation and report the average AUROC scores. 

Running time: We  present end-to-end wallclock time  for scalability analysis. For MILE, the reported running time include the execution time of all the phases, including the training time of refinement model. 




System Specifications: 
The experiments were conducted on a machine running Linux with an
Intel Xeon E5-2680 CPU (28 cores, 2.40GHz) and 128 GB of RAM.
We implement our MILE framework in .



For all the five base embedding methods, we adapt the original code from the
authors
[DeepWalk: <https://github.com/phanein/deepwalk>; 
 Node2Vec: <http://snap.stanford.edu/node2vec/>; 

        Line:  <https://github.com/thunlp/OpenNE>
        
        
 
          GraRep: <https://github.com/thunlp/OpenNE>; 
 NetMF: <https://github.com/xptree/NetMF>]. For SDNE, we lever the publicly available source code from here  <cit.>.
    We additionally use the TensorFlow package for the embedding refinement learning component.
    We lever the available parallelism (on 28 cores)
    for each method
    (e.g., the generation of random walks in DeepWalk and Node2Vec, the training of the refinement model in MILE, etc.).





 §.§ MILE Framework Performance



We first evaluate the performance of our MILE framework when applied to different graph embedding methods. 
The performance of MILE  with various base embedding methods – on different datasets and different coarsening levels  – for node classification and link prediction is shown in Figure <ref> and Figure <ref>, respectively.[We discuss the results of Yelp later.] 
We also investigate various design choices related to MILE in a subsequent section. The evaluation of various design choices are conducted through the lens of node classification, but similar results hold for link prediction.
 Note that a coarsening level of m=0, corresponds to the original embedding method.  




We make the following observations:














MILE is scalable.
MILE greatly boosts the speed of the explored embedding methods. In the case of node classification, as shown in Figure <ref>, with a single level of coarsening (m=1), we are able to achieve speedup ranging from 1.5× to 3.4× (on PPI, Blog, and Flickr) while improving qualitative performance. Larger speedups are typically observed on GraRep, NetMF, and SDNE. 
Increasing the coarsening level m to 2, the speedup increases further (up to 14.4×), while the quality of the embeddings is comparable
with the original methods reflected by Micro-F1. 
On YouTube, for the coarsening levels 6 and 8, we observe more than 10× speedup for DeepWalk, Node2Vec, Line, and SDNE. 
The execution of SDNE method on flickr dataset does not finish in 2 days, however,  the execution of MILE(SDNE) with coarsen level 8 finishes in less than 1 hour.
For NetMF on YouTube, the speedup is even larger – original NetMF runs out of memory within 9.5 hours while MILE (NetMF) only takes around  20 minutes (m=8).  
In the case of link prediction, as shown in Figure <ref>, we observe that an increase in coarsening level results in a consistent decrease in the running time of embedding methods. The higher coarsening levels (m= 7,8) leads to 1.2× to 113× speedup for all the methods on BlogCatalog and PPI datasets. On Flickr and YouTube, the running time reduction for all the methods ranges from 10×  to 29× while the quality of the embeddings is comparable (or even better) with respect to the original methods in terms of AUROC score.







Impact of MILE on embedding quality. 
In the case of node classification, as shown in Figure <ref>, 
for coarsening levels m=1 or 2, we observe that MILE learnt embeddings are almost always better in quality across all the datasets and methods. Examples include MILE (DeepWalk, m=1) on Blog/PPI, MILE (Line, m=1) on PPI and MILE (NetMF, m=1) on PPI/Blog/Flickr. 

Even with higher number of coarsening level (m=2 for PPI/Blog/Flickr; m=6,8 for YouTube),
MILE in addition to being much faster can still improve, qualitatively, 
over the original 
methods on most of the datasets, e.g., MILE (NetMF, m=2) ≫ NetMF on PPI, Blog, and Flickr. 
In the case of link prediction, as shown in Figure <ref>, we observe that the increase in coarsening level results in a corresponding increase in AUROC scores in most of the cases. For Node2vec, LINE and NetMF, with a single level of coarsening (m=1), we see improvement in AUROC from 3% to 10% on PPI and BlogCatalog datasets. With higher coarsening levels (m=7, 8), we see a consistent improvement in AUROC from 1.4% to 10.7% for Node2vec, LINE, NetMF and GraRep methods on Flickr and YouTube datasets. For SDNE, on Blog and YouTube dataset, the link prediction performance across coarsening levels 2-5 remains competitive with original SDNE method. We observe a 2x-15x speed in this range, consistent with other methods that use MILE. 
As discussed when describing the key intuitions underpinning the coarsening-refinement strategy that MILE employs (in Section <ref>),
the observed improvement on quality – for both node classification and link prediction – is likely due to the fact that the base embedding methods are exposed to a  holistic view of the entire graph. This observation is consistent with those observed for stochastic flow clustering <cit.>. 







MILE supports multiple embedding methods. 
We empirically show that MILE can work with different category of embedding methods on multiple real world datasets.
We observe that MILE 

often
improves both the quality and the 
efficiency of NetMF on all four datasets (for YouTube, NetMF 
runs out of memory). For the largest dataset, the speedups afforded exceed 30-fold.
We observe that for GraRep, while speedups with MILE are consistently observed, the qualitative improvements  if any, are smaller (for both YouTube and Flickr, the base method runs out of memory).
For Line, even though its time complexity is linear to the number of edges <cit.>, 
applying MILE framework on top of it still generates significant speed-up (likely due to the fact that the complexity of Line contains a larger constant factor k than MILE). 
On the other hand, MILE on top of Line generates better quality of embeddings on PPI and YouTube while falling a bit short on Blog and Flickr.   
For DeepWalk and Node2Vec, we again observe consistent improvements in scalability (up to 11-fold on the larger datasets) on the node classification task using MILE with a few levels of coarsening. However, when the coarsening level is increased, the additional
speedup afforded (up to 17-fold) comes at a mixed cost to quality (micro-F1 drops slightly). We observe similar trends – improvements in embedding quality and reduction in the running time – in the case of link prediction experiments.



























Impact of varying coarsening levels on MILE. 

In the case of node classification, as shown in Figure <ref>, when coarsening level m is small (m=1 or 2), MILE tends to significantly improve the quality of embeddings while taking much less time.  From m=0 to m=1, we see a clear jump of the Micro-F1 score on all the datasets across the  base embedding methods. This observation is more evident on larger datasets (Flickr and YouTube). On YouTube,  MILE (DeepWalk) with m=1 increases the Micro-F1 score by 5.3% while only consuming half of the time compared to the original DeepWalk. MILE (DeepWalk) continues to generate embeddings of better quality than DeepWalk until m=7, where the speedup is 13×.  As the coarsening level m in MILE increases, the running time drops dramatically while the quality of embeddings only decreases slightly. 
In the case of link prediction, as shown in Figure <ref>, the methods with higher coarsening levels (m=7,8) on all the evaluated datasets, except GraRep on PPI, show an improvement of AUROC with respect to the embedding performance on the original graph. For SDNE, we observe that as we vary the coarsening levels till coarsen level 5, the link prediction performance on Blog, Flickr, YouTube remains close to original method while we see improvement in the speedup. However on  YouTube we see a drop in AUROC score with coarsening levels 6 and 8 for SDNE.  For  both node classification and link prediction, the execution time decreases at an almost exponential rate (logarithm scale on the y-axis in the second row of Figure <ref> and Figure <ref>). On the other hand, the Micro-F1 score descends much more slowly (the first row of Figure <ref>), most of which are still better than the original methods. 


Overall, the above experiments shows that MILE can not only accommodate existing embedding methods - treating them as a blackbox - but also provides nice trade-off between effectiveness and efficency, a useful lever for downstream tasks and use-cases.






To summarize, our MILE framework not only significantly speeds up the embedding methods, 
but also improves the quality of the node embeddings.
We do notice that it negatively affects the embeddings in some case when the number of coarsening 
levels is large, e.g., MILE (GR, m=2) on PPI and Blog. But the decrease is mostly minor compared to 
large speedup achieved. Moreover, we can reduce the coarsening levels in order to generate better embeddings (e.g., m=1)
if the quality of the embeddings is valued over efficiency.
We discuss the trade-off between quality and efficiency of graph embedding in Sec. <ref>













 §.§ MILE: Large Graph Embedding
 

We now explore the scalability of MILE on the large Yelp dataset. 
None of the five graph embedding methods studied in this paper can successfully conduct graph embedding on 
Yelp within 60 hours on a modern machine with 28 cores and 128 GB RAM.
Even extending the run-time deadline to 100 hours, we see DeepWalk and Line barely finish. 

Leveraging the proposed MILE framework now makes it much easier to perform graph embedding on this scale of datasets


(see Figure <ref> for the results).

We observe that MILE significantly reduces the running time and improves the Micro-F1 score. 
For example, 
The Micro-f1 scores of original DeepWalk and Line are 0.640 and 0.625 respectively, which all take more than 80 hours. But using MILE with m=4, the micro-F1 score improves to 0.643 (DeepWalk) and 0.642 (Line) while achieving speedups of around 1.6×. 
Moreover, MILE reduces the running time of DeepWalk from 53 hours (coarsening level 4) to 
2 hours (coarsening level 22) while reducing the Micro-F1 score just by 1% (from 0.643 to 0.634).
Meanwhile, there is no change in the Micro-F1 score from the coarsening level 4 to 10,
where the running time is improved by a factor of two. 

These results affirm the power of the proposed MILE framework on scaling up graph embedding algorithms while generating quality embeddings. We also observe similar performance gain and reduction in the running time for the link prediction task, however, due to paucity of space the link prediction results on Yelp dataset are not shared in this paper. 


        

























 §.§ Memory Consumption





We also study the impact of MILE on reducing memory consumption.
For this purpose, we focus on MILE (GraRep) and MILE (NetMF), with GraRep and NetMF as base embedding methods respectively. 
Both of these are embedding methods based on matrix factorization, which possibly involves a dense objective matrix and could be rather memory expensive. We do not explore DeepWalk and Node2Vec here since their embedding learning methods generate truncated random walks (training data) on the fly
with almost negligible memory consumption (compared to the space storing the graph and the embeddings).

Figure <ref> shows the memory consumption of MILE (GraRep) and MILE(NetMF) as the coarsening level increases on Blog (results on other datasets are similar). 
We observe that MILE significantly reduces the memory consumption as the coarsening level increases. 
Even with one level of coarsening, the memory consumption of GraRep and NetMF reduces by 64% and 42% respectively. 
The dramatic reduction continues as the coarsening level increases until it reaches 4, where the
memory consumption is mainly contributed by the storage of the graph and the embeddings.
This memory reduction is consistent with our intuition, since both # rows and # columns in the objective matrix 
for factorization 
reduce almost by half with one level of coarsening.







 §.§ Comparing MILE with HARP



HARP is a  
multi-level method primarily
for improving the quality of graph embeddings.
We compare HARP with our MILE framework using DeepWalk and Node2vec as the base embedding
methods[We use the source code from the authors: <https://github.com/GTmac/HARP>. 
  Results on Node2Vec are similar and hence omitted.].
methods[<https://github.com/GTmac/HARP>].
Table <ref> shows the performance of these two methods on the four datasets (coarsening level is 1 on PPI/Blog/Flickr and 6 on YouTube). 
We also observe similar node classification performance with Macro-f1 metric (not shown).
From the table, we can observe that MILE generates embeddings of comparable quality with HARP.
MILE performs much better than HARP on PPI and Blog, marginally better on Flickr and marginally worse on YouTube.
However, MILE is significantly faster than HARP on all the four datasets (e.g. on YouTube, MILE affords a  31× speedup).
This is because HARP requires running the whole embedding algorithm on each coarsened graph, which introduces a huge computational overhead. 













 §.§ Comparing MILE with Pytorch-biggraph


In this section, we compare the performance of MILE with Pytorch-biggraph. In Pytorch-biggraph, we set the number of workers to 28 (equal to the number of available cores). Figure <ref> and Figure <ref> respectively show the node classification and link prediction performance of both Pytorch-biggraph and MILE (Deepwalk) methods. Note that, in MILE, the speedup is driven by the coarsening level and higher speedup is achieved with higher coarsening level – as evident from the experiments shown in Figure <ref> and Figure <ref>. For PPI and Blog dataset, we set coarsen level to 2 and for Flickr and YouTube dataset, we set  coarsen level to 6. From Figure <ref>, we see that for the node classification task on PPI and YouTube dataset, MILE outperforms Pytorch-biggraph on classification quality metrics (higher-quality embeddings) while the running time of MILE is lower than Pytorch-biggraph. The lower running time of MILE is due to the proposed multi-level framework.   
From Figure <ref>, we observe that MILE outperforms Pytorch-biggraph for the link prediction task on three datasets namely PPI, Blog and Flickr with less running time compared to Pytorch-biggraph. This experiment shows that on a single system with 28-cores, MILE outperforms Pytorch-biggraph in terms of running time and also outperforms Pytorch-biggraph on downstream tasks such as node classification and link prediction. 















§ MILE DRILLDOWN




 §.§ Design Choices





We now study the role of the design choices we make within the MILE framework related to the coarsening and refinement procedures
described. 
To this end, we examine alternative design choices and systematically examine their performance.
The alternatives we consider are:


Random Matching (MILE-): 

For each iteration of coarsening, we repeatedly pick a random pair of connected nodes as a match and merge them into a super-node until no more matching can be found. The rest of the algorithm is the same as our MILE. 

Simple Projection (MILE-): We replace our embedding refinement model with a simple projection method. In other words, we directly copy the embedding of a super-node to its original node(s) without any refinement ( ℰ^p_i = M_i, i+1ℰ_i+1 ).



Averaging Neighborhoods (MILE-): For this baseline method, the refined embedding of each node is a weighted average node embedding of its neighborhoods (weighted by the edge weights). This can be regarded as an embeddings propagation method. We add self-loop to each node[Self-loop weights are tuned to the best performance.] and conduct the embeddings propagation for two rounds.

Untrained Refinement Model (MILE-): Instead of training the refinement model to minimize the loss defined 
as L = 1/|V_m|‖ℰ_m - H^(l)(ℰ_m, A_m) ‖^2, 
this baseline merely uses a fixed set of values for parameters Θ^(k) without training (values are randomly generated; other parts of the refinement model 
are the same, including Ã and D̃). 


Double-base Embedding for Refinement Training (MILE-): This method replaces the loss function 
L = 1/|V_m|‖ℰ_m - H^(l)(ℰ_m, A_m) ‖^2
with 
L = 1/|V_m|‖ℰ_m - H^(l)(M_m, m+1ℰ_m+1, A_m) ‖^2
for model training. 
It conducts one more layer of coarsening and 
base embedding (level m+1), from which the embeddings are projected to level m and used as the input for model training. 

GraphSAGE as Refinement Model (MILE-): It replaces the graph convolution network in our refinement step with GraphSAGE <cit.>[Adapt code from <https://github.com/williamleif/GraphSAGE>]. 
We choose max-pooling for aggregation and set the number of sampled neighbors as 100, as suggested by the authors. Also, concatenation is conducted instead of replacement during the process of propagation. 










































 §.§ Results of MILE-variants


Table <ref> shows the comparison of performance on these methods across the four datasets. 

Here, we focus on using DeepWalk and NetMF for base embedding with coarsening level as m=1 for PPI, Blog, and Flickr, while m=6 for YouTube. Results are similar for the other embedding options we consider. 



We hereby summarize the key information derived from Table <ref> as follows:



The matching methods used within MILE offer a qualitative benefit at a minimal cost to execution time. Comparing 
MILE with MILE- for all the datasets, we can see that MILE generates better embeddings than MILE- using either DeepWalk or NetMF as the base embedding method. 
Though MILE- is slightly faster than MILE due to its random matching, 
its Micro-F1 score are consistently lower than of MILE. 


The graph convolution based refinement learning methodology in MILE is particularly effective. 
Simple projection-based MILE-, performs significantly worse than MILE.
The other two variants (MILE- and MILE-) which do not train the refinement model at all, also perform much worse than the proposed method. Note MILE- is the same as MILE except it uses a default set of parameters instead of learning those parameters. Clearly, the model learning part of our refinement method is a fundamental contributing factor to the effectiveness of MILE.
Through training, the refinement model is tailored to the specific graph under the base embedding method in use.
The overhead cost of this learning (comparing MILE with MILE-),
can vary depending on the base embedding employed (for instance on the YouTube dataset, it is an insignificant 1.2% on DeepWalk - while being up to 20% on NetMF) but is still
worth it due to qualitative benefits (Micro-F1 up from 30.2 to 40.9 with NetMF on YouTube).

Graph convolution refinement learning outperforms GraphSAGE.
Replacing the graph convolution network with GraphSAGE for embedding refinement,
MILE- does not perform as well as MILE. It is also computationally more expensive, partially 
due to its reliance on embeddings concatenation, instead of replacement, during the process the embeddings 
propagation (higher model complexity). 


Double-base embedding learning is not effective.
In the section – Intricacies of Refinement Learning – we discussed the issues with unaligned embeddings

of
the double-base embedding
method for the refinement model learning. 
The performance gap between MILE and MILE- in Table <ref> provides empirical evidence 
supporting our argument.        
This gap is likely caused by the fact that the base embeddings of level m and level m+1 might not lie in the same embedding space (rotated by some orthogonal matrix) <cit.>. 
As a result, using the projected embeddings ℰ^p_m as input for model training (MILE-) is not as good as directly using ℰ_m (MILE). Moreover, Table <ref> shows that the additional round of base embedding in MILE- introduces a non-trivial overhead. On YouTube, the running time of MILE- is 1.6 times as much as MILE.























































 

  §.§.§ Extending MILE to directed graphs


MILE can be extended to directed graphs. As pointed out by <cit.>, one can construct random-walk Laplacians for a directed graph thus incorporating approaches like NetMF to accommodate such solutions.  Another simple solution is to symmetrize the graph while accounting for directionality. Once the graph is symmetrized, any of the embedding strategies we discuss can be employed within the MILE framework (including the coarsening technique). There are many ideas for symmetrization of directed graphs (see for example work described by <cit.> or <cit.>.   








 §.§ Discussion on reusing Θ^(k)  across all levels


 Similar to GCN, Θ^(k)  is a matrix of filter parameters and is of size d*d (where d is the embedding dimensionality). Eq. <ref> in this paper defines how the embeddings are propagated during embedding refinements, parameterized by Θ^(k) . Intuitively,  Θ^(k)  defines how different embedding dimensions interact with each other during the embedding propagation. This interaction is dependent on graph structure and base embedding method, which can be learned from the coarsest level.  Ideally, we would like to learn this parameter Θ^(k)  on every two consecutive levels. But this is not practical since this could be expensive as the graph get more fine-grained (and defeat our purpose of scaling up graph embedding). This trick of “sharing” parameters across different levels is the trade-off between efficiency and effectiveness. To some extent, it is similar to the original GCN <cit.>, where the authors share the same filter parameters Θ^(k)  over the whole graph (as opposed to using different Θ^(k)  for different nodes; see Eq (6) and (7) in<cit.>). Moreover, we empirically found this works good enough and much more efficient. Table <ref> shows that if we do not share Θ^(k)  values and use random values for Θ^(k)  during refinements, the quality of embedding is much worse (see baseline MILE-untr). 
 


 
 
 

 §.§ Discussion on  effectiveness of SEM

The effectiveness of structurally equivalent matching (SEM) is highly dependent on graph structure but in general 5% - 20% of nodes are structurally equivalent (most of which are low-degree nodes). For example, during the first level of coarsening, YouTube has 172,906 nodes (or 86,453 pairs) out of 1,134,890 nodes that are found to be SEM (around 15%); Yelp has 875,236 nodes (or 437,618 pairs) out of 8,938,630 nodes are SEM (around 10%). In fact, more nodes are involved in SEM as SEM is run iteratively at each coarsening level.







 §.§ Reuse of Θ^(k)  across all levels
 As mentioned in section – Intricacies of Refinement Learning – 
in the refinement phase we learn Θ^(k) on the coarsest graph and reuse the learnt Θ^(k) across all coarsening levels. Similar to GCN, Θ^(k)  is a matrix of filter parameters and is of size d*d (where d is the embedding dimensionality). Equation:  
H^(k)(X, A) = σ( D̃^-1/2ÃD̃^-1/2 H^(k-1)(X, A) Θ^(k))
defines how the embeddings are propagated during embedding refinements, parameterized by Θ^(k) . Intuitively,  Θ^(k)  defines how different embedding dimensions interact with each other during the embedding propagation. This interaction is dependent on graph structure and base embedding method, which can be learned from the coarsest level.  One could also learn the parameter Θ^(k)  on every two consecutive levels, however, as the graph get more fine-grained across coarsening levels, the learning of Θ^(k) on every two consecutive levels would become expensive.

The trick of “sharing” parameters across different levels is the trade-off between efficiency and effectiveness. 

In Table <ref>,  we see that “sharing” parameters across different levels works well in practice. Table <ref> also shows that if we do not share Θ^(k)  values and use random values for Θ^(k)  during refinements, the quality of embedding is much worse (see baseline MILE-untr). 




§ EFFECTIVENESS OF SEM

The effectiveness of structurally equivalent matching (SEM) is highly dependent on graph structure but in general 5% - 20% of nodes are structurally equivalent (most of which are low-degree nodes). For example, during the first level of coarsening, YouTube has 172,906 nodes (or 86,453 pairs) out of 1,134,890 nodes that are found to be SEM (around 15%); Yelp has 875,236 nodes (or 437,618 pairs) out of 8,938,630 nodes are SEM (around 10%). In fact, more nodes are involved in SEM as SEM is run iteratively at each coarsening level.








§ DISCUSSIONS



 §.§ Discussion on reusing Θ^(k)  across all levels

COMMENTED OUT

As mentioned in section – Intricacies of Refinement Learning – 
in the refinement phase we learn Θ^(k) on the coarsest graph and reuse the learnt Θ^(k) across all coarsening levels. Similar to GCN, Θ^(k)  is a matrix of filter parameters and is of size d*d (where d is the embedding dimensionality). Equation:  
H^(k)(X, A) = σ( D̃^-1/2ÃD̃^-1/2 H^(k-1)(X, A) Θ^(k))
defines how the embeddings are propagated during embedding refinements, parameterized by Θ^(k) . Intuitively,  Θ^(k)  defines how different embedding dimensions interact with each other during the embedding propagation. This interaction is dependent on the graph structure and the base embedding method, which can be learned from the coarsest level.  One could also learn the parameter Θ^(k)  on every two consecutive levels, however, as the graph get more fine-grained across coarsening levels, the learning of Θ^(k) on every two consecutive levels would become expensive.

The trick of “sharing” parameters across different levels is the trade-off between efficiency and effectiveness. 

In Table <ref>,  we see that “sharing” parameters across different levels work well in practice. Table <ref> also shows that if we do not share Θ^(k)  values and use random values for Θ^(k)  during refinements, the quality of embedding is much worse (see baseline MILE-untr). 
 
 

 §.§ Discussion on the choice of embedding methods

 
 We wish to point out that we chose the base embedding methods as they are 
 are widely used. By showing the performance gain of using MILE on top of these methods, we want to ensure the contribution of this work is of broad interest to the community.  We also want to reiterate that these methods are quite different in nature: 
 
 


  *  DeepWalk (DW) and Node2vec (N2V) rely on the use of random walks for the latent representation of features. 

  *  LINE learns an embedding that directly optimizes a carefully constructed objective function that preserves both first/second-order proximity among nodes in the embedding space.

  *  GraRep constructs multiple objective matrices based on high orders of random walk laplacians, factories each objective matrix to generate embeddings and then concatenates the generated embeddings to form final embedding.

  *  NetMF constructs an objective matrix based on random walk Laplacian and factorizes the objective matrix in order to generate the embeddings.

  
  
 
 Indeed NetMF <cit.> with an appropriately constructed objective matrix has been shown to approximate DW, N2V, and LINE allowing such be conducting implicit matrix factorization of approximated matrices. There are limitations to such approximations (shown in a related context by <cit.>) - the most important one is the requirement of a sufficiently large embedding dimensionality.  Additionally, we note that while unification is possible under such a scenario, the methods based on matrix factorization are quite different from the original methods and do place a much larger premium on space (memory consumption) - in fact this is observed by the fact we are unable to run NetMF and GraRep in many cases without incorporating them within MILE.


 

 §.§ Discussion on  extending MILE to directed graphs

 
 Note that as pointed out by <cit.>, one can construct random-walk Laplacians for a directed graph thus incorporating approaches like NetMF to accommodate such solutions.  Another simple solution is to symmetrize the graph while accounting for directionality. Once the graph is symmetrized, any of the embedding strategies we discuss can be employed within the MILE framework (including the coarsening technique). There are many ideas for symmetrization of directed graphs (see for example work described by <cit.> or <cit.>.   
 
 


 §.§ Discussion on the effectiveness of SEM

 
The effectiveness of structurally equivalent matching (SEM) is highly dependent on graph structure but in general, 5% - 20% of nodes are structurally equivalent (most of which are low-degree nodes). For example, during the first level of coarsening, YouTube has 172,906 nodes (or 86,453 pairs) out of 1,134,890 nodes that are found to be SEM (around 15%); Yelp has 875,236 nodes (or 437,618 pairs) out of 8,938,630 nodes are SEM (around 10%). In fact, more nodes are involved in SEM as SEM is run iteratively at each coarsening level.








§ CONCLUSION


In this work, we propose a novel multi-level embedding (MILE) framework to scale up graph embedding techniques,
without modifying them. Our framework incorporates existing embedding techniques as black boxes, and significantly improves the scalability of extant 
methods by reducing both the running time and memory consumption. 
Additionally, MILE also provides a lift in the quality of node embeddings in 
most of the cases. A fundamental contribution of MILE is its ability to learn a refinement strategy that depends on both the underlying graph properties and the embedding method in use. =-1







COMMENTED OUT

In the future, 
we plan to generalize MILE for other types of graphs to enable its use on a broader class of applications.
One direction is to extend MILE to directed graphs. 
As pointed out elsewhere<cit.>, one can construct random-walk Laplacians for a directed graph thus incorporating approaches like NetMF for directed graphs. Alternatively one may symmetrize the graph<cit.> and subsequently employ any of the embedding strategies we discussed above.
Extending MILE to attributed and heterogeneous graphs is also of interest<cit.> - we hope to see similar gains there.




We also wish to extend MILE on large datasets with hybrid CPU/GPU architectures while retaining the property of agnosticity with respect to the base embedding technique. A few studies <cit.> have scaled embedding methods on large datasets on different parallel architectures. However,  these approaches inevitably require modifying the base embedding method in order to scale them to large datasets and are therefore not agnostic to the embedding method. One approach that seems promising in this regard is the use of graph stratification<cit.> to partition the graph and then apply MILE independently on each partition before fusing the results together.
Examining the performance of such an idea on a hybrid CPU/GPU architectures will be of interest.






In this work, we report experiments on undirected graphs. However, MILE can be extended to directed graphs too. As pointed out by <cit.>, one can construct random-walk Laplacians for a directed graph thus incorporating approaches like NetMF for directed graphs.  Another simple solution is to symmetrize the graph while accounting for directionality. Once the graph is symmetrized, any of the embedding strategies we discuss can be employed within the MILE framework (including the coarsening technique). There are many ideas for symmetrization of directed graphs (see for example work described by <cit.> or <cit.>.   In the future, 
we plan to generalize MILE for information-rich graphs and employing MILE for more applications.








Acknowledgments:
This work is supported by the National Science Foundation
under grants EAR-1520870 and DMS-1418265. Computational support was provided by
the Ohio Supercomputer Center under grant PAS0166.
All content represents the opinion of the authors,
which is not necessarily shared or endorsed by their sponsors.



aaai



