
\section{Introduction}







\IEEEPARstart{G}{raph} is a well-known data structure widely used in many critical application fields due to its powerful representation capability of data, especially in expressing the associations between objects \cite{introduction_to_graph_theory, graph_applications}.
Many real-world data can be naturally represented as graphs which consist of a set of vertices and edges.
Take social networks as an example~\cite{social_network_analysis,What_is_Twitter}, the vertices in the graph represent people and the edges represent interactions between people on Facebook \cite{DBLP:conf/nips/learning_to_discover/facebook_dataset_ego/}.
An illustration of graphs for social networks is illustrated in Fig. \ref{fig:01ley_gnndt} (a), where the circles represent the vertices, and the arrows represent the edges.
Another well-known example is knowledge graphs \cite{Freebase_knowledge_graph, ashburner2000gene}, in which the vertices represent entities while the edges represent relations between the entities \cite{WordNet_knowledge_graph}.


\begin{comment}

\Dang{
Graphs are widely applied in many critical applications due to their powerful capability to express associations between objects \cite{introduction_to_graph_theory, graph_applications}.
Many real-world data can be naturally represented as a set of vertices connected by edges.
For instance, people in a social network \cite{social_network_analysis,What_is_Twitter} can be represented as vertices in a graph, and their interactions on Facebook can be symbolized by edges \cite{DBLP:conf/nips/learning_to_discover/facebook_dataset_ego/}, as illustrated in Fig. \ref{fig:01ley_gnndt} (a).
Another example is knowledge graph \cite{Freebase_knowledge_graph, ashburner2000gene}, in which the vertices represent entities while the edges represent relations between the entities \cite{WordNet_knowledge_graph}.
}
\end{comment}


Graph neural networks (GNNs) demonstrate superior performance compared to other algorithmic models in learning over graphs \cite{tkde_deep_learning_on_graphs_gnngood, tnnls_a_comprehensive_survey_gnngood, aiopen_graph_neural_networks_a_review_gnngood}.
Deep neural networks (DNNs) have been widely used to analyze Euclidean data such as images~\cite{Nature_Deep_Learning}. However, they have been challenged by graph data from the non-Euclidean domain due to the arbitrary size and complex topological structure of graphs~\cite{nips_inductive_representation_ley_graphsage_minibatch}. Besides, a major weakness of deep learning paradigms identified by industry is that they cannot effectively carry out causal reasoning, which greatly reduces the cognitive ability of intelligent systems~\cite{geometric_learning}. To this end, GNNs have emerged as the premier paradigm for graph learning and endowed intelligent systems with cognitive ability. 
An illustration for GNNs is shown in Fig. \ref{fig:01ley_gnndt} (b). 
After getting graph data as input, GNNs use forward propagation and backward propagation to update the model parameters.
Then the trained model can be applied to graph tasks, including vertex prediction \cite{iclr_semi_supervised_classification_with_nodeprediction} (predicting the properties of specific vertices), link prediction \cite{nips_link_prediction_based_on_linkprediction} (predicting the existence of an edge between two vertices), and graph prediction \cite{aaai_an_end_to_end_deep_learing_graphprediction} (predicting the properties of the whole graph), as shown in Fig. \ref{fig:01ley_gnndt} (c). 



\begin{comment}

\Dang{
The methodology of GNNs originates from the demand to apply deep learning techniques to graph data.
Although traditional deep neural networks (DNNs) can successfully analyze Euclidean data like images, they have been challenged by graph data from the non-Euclidean domain, as they cannot process the arbitrary size and complex topological structure of graphs~\cite{nips_inductive_representation_ley_graphsage_minibatch}.
Besides, industry finds that DNNs cannot effectively carry out causal reasoning, which dramatically reduces the cognitive ability of intelligent systems~\cite{geometric_learning}.
To this end, GNNs have emerged as the premier paradigm for graph learning and endowed intelligent systems with cognitive ability.
An illustration for GNNs is shown in Fig. \ref{fig:01ley_gnndt} (b).
After getting graph data as input, GNNs use forward propagation and backward propagation to update the model's parameters.
Then the trained model can be applied to graph tasks, including vertex prediction \cite{iclr_semi_supervised_classification_with_nodeprediction} (predicting the properties of specific vertices), link prediction \cite{nips_link_prediction_based_on_linkprediction} (predicting the existence of an edge between two vertices), and graph prediction \cite{aaai_an_end_to_end_deep_learing_graphprediction} (predicting the properties of the whole graph). 
}
\end{comment}

Thanks to the superiority of GNNs, they have been widely used in various real-world applications in many critical fields. 
These real-world applications include 
knowledge inference~\cite{gcn_knowledge_graph}, natural language processing \cite{DBLP:journals/cim/YoungHPC18/gnn_nlp/, DBLP:conf/icdm/WuPZZP19/pan_gnn03}, machine translation \cite{gcn_machine_translation}, recommendation systems \cite{kdd_graph_convolutional_ley_pinsage,DBLP:conf/www/Fan0LHZTY19/gnn_recommend01/,DBLP:conf/aaai/MaMZSLC20/gnn_recommend02}, visual reasoning \cite{gcn_visual_reasoning}, chip design \cite{google_ai_chip_design, GCN-RL_circuit_designer,GCN_EDA}, traffic prediction \cite{google_map_gnn, DBLP:conf/aaai/ChenLTZWWZ19/gnn_traffic_prediction01/, DBLP:conf/aaai/LiZ21/gnn_traffic_prediction02/}, ride-hailing demand forecasting~\cite{gcn_ride-hailing_demand_forecasting}, spam review detection~\cite{xianyu_spam_review_detection}, molecule property prediction \cite{DBLP:conf/nips/FoutBSB17/gnn_protein/}, and so forth. 
GNNs enhance the machine intelligence when processing a broad range of real-world applications, such as giving $>$50\% accuracy improvement for real-time ETAs in Google Maps~\cite{google_map_gnn}, generating $>$40\% higher-quality recommendations in Pinterest~\cite{kdd_graph_convolutional_ley_pinsage}, achieving $>$10\% improvement of ride-hailing demand forecasting in Didi~\cite{gcn_ride-hailing_demand_forecasting}, improving $>$66.90\% of \textit{recall at 90\% precision} for spam review detection in Alibaba~\cite{xianyu_spam_review_detection}.

\begin{comment}

\Dang{
GNNs show superior performance in learning over graphs compared to other methods \cite{tkde_deep_learning_on_graphs_gnngood, tnnls_a_comprehensive_survey_gnngood, aiopen_graph_neural_networks_a_review_gnngood}.
As a result, it is widely applied in many critical fields, including
    knowledge inference~\cite{gcn_knowledge_graph},
    natural language processing \cite{DBLP:journals/cim/YoungHPC18/gnn_nlp/},
    machine translation \cite{gcn_machine_translation},
    recommendation system \cite{kdd_graph_convolutional_ley_pinsage,DBLP:conf/www/Fan0LHZTY19/gnn_recommend01/,DBLP:conf/aaai/MaMZSLC20/gnn_recommend02},
    visual reasoning \cite{gcn_visual_reasoning},
    chip design \cite{google_ai_chip_design, GCN-RL_circuit_designer,GCN_EDA},
    traffic prediction \cite{google_map_gnn, DBLP:conf/aaai/ChenLTZWWZ19/gnn_traffic_prediction01/, DBLP:conf/aaai/LiZ21/gnn_traffic_prediction02/},
    ride-hailing demand forecasting~\cite{gcn_ride-hailing_demand_forecasting},
    spam review detection~\cite{xianyu_spam_review_detection},
    and molecule property prediction \cite{DBLP:conf/nips/FoutBSB17/gnn_protein/}.
GNNs enhances machine intelligence in a broad field of real-world applications, such as
    improving accuracy by $>$50\% of real-time ETAs in Google Maps~\cite{google_map_gnn},
    generating $>$40\% higher-quality recommendations in Pinterest~\cite{kdd_graph_convolutional_ley_pinsage},
    achieving a $>$10\% improvement of ride-hailing demand forecasting in Didi~\cite{gcn_ride-hailing_demand_forecasting},
    and improving $>$66.90\% of \textit{recall at 90\% precision} for spam review detection in Alibaba~\cite{xianyu_spam_review_detection}.
}
\end{comment}





\begin{figure*}[!t]
   
    \centering
    \includegraphics[page=1, width=0.99\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
   
    \caption{Distributed GNN training: (a) Illustration of graphs; (b) Illustration of training; (c) Illustration of graph tasks; (d) Illustration of distributed training.}
    \label{fig:01ley_gnndt}
   
\end{figure*}







However, both industry and academia are still eagerly expecting the acceleration of GNN training for the following reasons \cite{pvldb_aligraph, pvldb_agl, eurosys_flexgraph, ia3_distdgl}:
\begin{itemize}
    \item \textit{The scale of graph data is rapidly expanding, consuming a great deal of time for GNN training.}
    With the explosion of information on the Internet, new graph data are constantly being generated and changed, such as the establishment and demise of interpersonal relationships in social communication and the changes in people's preferences for goods in online shopping.
    The scales of vertices and edges in graphs are approaching or even outnumbering the order of billions and trillions, respectively \cite{nips_open_graph_benchmark_ogbdataset, sc_reducint_communication_in_graph_cagnet, DBLP:journals/tjs/HuangQWC20/chen_largegraph02/, DBLP:journals/tpds/HuangWFWC22/chen_largegraph03/}.
    The growth rate of graph scales is also astonishing.
    For example, the number of vertices (i.e., users) in Facebook's social network is growing at a rate of 17\% per year \cite{/facebook/17percent/}.
    Consequently, GNN training time dramatically increases due to the ever-growing scale of graph data.
    
   
   
   
   
   
    \item \textit{Swift development and deployment of novel GNN models involves repeated training, in which a large amount of training time is inevitable.}
    Much experimental work is required to develop a highly-accurate GNN model since repeated training is needed \cite{tnnls_a_comprehensive_survey_gnngood, aiopen_graph_neural_networks_a_review_gnngood, tkde_deep_learning_on_graphs_gnngood}.
    Moreover, expanding the usage of GNN models to new application fields also requires much time to train the model with real-life data.
    Such a sizeable computational burden calls for faster methods of training.
   
   
   
   
   
   
   
   
   
\end{itemize}










Distributed training is a popular solution to speed up GNN training \cite{atc_neugraph, mlsys_roc, sc_reducint_communication_in_graph_cagnet, eurosys_dgcl, sc_distgnn, eurosys_flexgraph, arxiv_mg_gcn, osdi_dorylus, arxiv_sar, pvldb_aligraph, ia3_distdgl, pvldb_agl, socc_pagraph, cluster_2pgraph, arxiv_llcg, arxiv_distdglv2, arxiv_graphtheta, arxiv_salient, /osdi/Gandhi/p3/distributed_deep_graph/, DBLP:conf/infocom/LuoBW22/new02/DGTP}.
It tries to accelerate the entire computing process by adding more computing resources, or ``nodes", to the computing system with parallel execution strategies, as shown in Fig. \ref{fig:01ley_gnndt} (d). 
NeuGraph \cite{atc_neugraph}, proposed in 2019, is the first published work of distributed GNN training.
Since then, there has been a steady stream of attempts to improve the efficiency of distributed GNN training in recent years with significantly varied optimization techniques, including workload partitioning \cite{atc_neugraph, mlsys_roc, eurosys_dgcl, sc_distgnn}, transmission planning \cite{mlsys_roc, atc_neugraph, eurosys_dgcl, eurosys_flexgraph}, caching strategy \cite{pvldb_aligraph, socc_pagraph, cluster_2pgraph}, etc.

Despite the aforementioned efforts, there is still a dearth of review of distributed GNN training.
The need for management and cooperation among multiple computing nodes leads to a different workflow, resulting in complex computational and communication patterns, and making it a challenge to optimize distributed GNN training. 
However, regardless of plenty of efforts on this aspect have been or are being made, there are hardly any surveys on these challenges and solutions.
Current surveys mainly focus on GNN models and hardware accelerators \cite{tkde_deep_learning_on_graphs_gnngood, aiopen_graph_neural_networks_a_review_gnngood, tnnls_a_comprehensive_survey_gnngood, computing_survey_computing_graph_neural_networks_gnnsurvey1, arxiv_relational_inductive_gnnsurvey2, arxiv_machine_learning_gnnsurvey3, ijcai_graph_neural_networks_gnnsurvey4}, but they are not intended to provide a careful taxonomy and a general overview of distributed training of GNNs, especially from the perspective of the workflows, computational patterns, communication patterns, and optimization techniques.




This paper presents a comprehensive review of distributed training of GNNs by investigating its various optimization techniques.
First, we summarize distributed GNN training into several categories according to their workflows. In addition, we introduce their computational patterns, communication patterns, and various optimization techniques proposed in recent works to facilitate scholars to quickly understand the principle of recent optimization techniques and the current research status.
Second, we introduce the prevalent software frameworks and hardware platforms for distributed GNN training and their respective characteristics.
Third, we emphasize the uniqueness of distributed GNN training by comparing it with distributed DNN training.
Finally, we discuss interesting issues and opportunities in this field.


Our main goals are as follows:
\begin{itemize}
    \item Introducing the basic concepts of distributed GNN training.
   
    \item Analyzing the workflows, computational patterns, and communication patterns of distributed GNN training and summarizing the optimization techniques.
   
    \item Highlighting the differences between distributed GNN training and distributed DNN training
    \item Discussing interesting issues and opportunities in the field of distributed GNN training.
\end{itemize}




The rest of this paper is described in accordance with these goals. Its organization is shown in Table \ref{table:organization} and summarized as follows:

\begin{table*}[!htbp]
\centering
\caption{Content guidance of this paper.} \label{table:organization}
\renewcommand\arraystretch{1.5} 
\setlength{\tabcolsep} {1.5mm}{
\begin{tabular}{|c|cc|}
\hline 
\textbf{Section} &  \textbf{Subsection} & \textbf{Index} \\ \hline \hline
\multirow{3}{*}{Background} 
&  Graphs  &  Section \ref{sec:background:graphs}\\ 
&  Graph Neural Networks  &  Section \ref{sec:background:graph_neural_network} \\ 
&  Training Methods for Graph Neural Networks  &   Section \ref{sec:background:training_method}\\ \hline
\multirow{5}{*}{\makecell[c]{Taxonomy of \\Distributed GNN Training}} 
&  Distributed Full-batch Training  & Section \ref{sec:taxonomy:dft_intro} \\ 
&  Distributed Mini-batch Training  & Section \ref{sec:taxonomy:dmt_intro} \\ 
& \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Comparison Between Distributed Full-batch Training \\and Distributed Mini-batch Training \end{tabular}}  
& \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Section \ref{sec:taxonomy:dft_dmt_comparison} \end{tabular}}   \\ 
&   &  \\
&  Other Information of Taxonomy  & Section \ref{sec:taxonomy:others_information} \\ \hline
\multirow{2}{*}{Distributed Full-batch Training} 
&  Dispatch-workload-based Execution  & Section \ref{sec:dft:chunk_execution}  \\ 
&  Preset-workload-based Execution  & Section \ref{sec:dft:partition_execution} \\ \hline
\multirow{2}{*}{Distributed Mini-batch Training} 
&  Individual-sample-based Execution  & Section \ref{sec:dmt:sample_individual_execution} \\
&  Joint-sample-based Execution  & Section \ref{sec:dmt:sample_joint_execution} \\ 
\hline
\makecell[c]{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Software Frameworks for \\Distributed GNN Training\end{tabular}}} & \multirow{2}{*}{(Introduction of the Software Frameworks)}  & \multirow{2}{*}{Section \ref{sec:software_framework}} \\ 
\makecell[c]{} &  &  \\ \hline
\multirow{3}{*}{\makecell[c]{Hardware Platforms for \\Distributed GNN Training}} 
&  Multi-CPU Hardware Platform  &  Section \ref{sec:hp:multi_cpu_hardware_platform} \\ 
&  Multi-GPU Hardware Platform  &  Section \ref{sec:hp:multi_gpu_hardware_platform} \\ 
&  Multi-CPU Hardware Platform V.S. Multi-GPU Hardware Platform  &  Section \ref{sec:hp:comparison_cpu_or_cpu} \\ \hline
\multirow{3}{*}{\makecell[c]{Comparison to \\Distributed DNN Training}} 
&  Brief Introduction to Distributed DNN Training  &  Section \ref{sec:comparison_to_dnn:brief_intro_dnn} \\ 
&  Distributed Full-batch Training V.S. DNN Model Parallelism  & Section \ref{sec:comparison_to_dnn:full_vs_model}  \\ 
&  Distributed Mini-batch Training V.S. DNN Data Parallelism  &  Section \ref{sec:comparison_to_dnn:mini_vs_data} \\ \hline
\multirow{5}{*}{\makecell[c]{Summary and Discussion}} 
&Quantitative Analysis of Performance Bottleneck   &Section \ref{sec:summary:quantitative}   \\
&Performance Benchmark   & Section \ref{sec:summary:performance_benchmark} \\
&Distributed Training on Extreme-scale Hardware Platform   & Section \ref{sec:summary:distributed_training_on_extreme_scale} \\
&Domain-specific Distributed Hardware Platform   & Section \ref{sec:summary:domain_specific} \\
&General Communication Library for Distributed GNN Training   & Section \ref{sec:summary:general_communication} \\ \hline
Conclusion &  (Conclusion of the Survey) & Section \ref{sec:conclusion} \\ \hline

\end{tabular}
}
\end{table*}

\begin{itemize}
    \item Section \ref{sec:background} introduces the basic concepts of graphs and GNNs as well as two training methods of GNNs: full-batch training and mini-batch training. 
    
    \item Section \ref{sec:taxonomy} introduces the taxonomy of distributed GNN training and makes a comparison between them.
    
    \item Section \ref{sec:dft} introduces distributed full-batch training of GNNs and further categorizes it into two types, of which the workflows, computational patterns, communication patterns, and optimization techniques are introduced in detail.
    
    \item Section \ref{sec:dmt} introduces distributed mini-batch training and classifies it into two types. We also present the workflow, computational pattern, communication pattern, and optimization techniques for each type.
 
    \item Section \ref{sec:software_framework} introduces software frameworks currently supporting distributed GNN training and describes their characteristics.
    
    \item Section \ref{sec:hardware_platform} introduces hardware platforms for distributed GNN training.
    
    \item Section \ref{sec:comparison_to_dnn} highlights the uniqueness of distributed GNN training by comparing it with distributed DNN training.
    
    \item Section \ref{sec:summary} summarizes the distributed full-batch training and distributed mini-batch training, and discusses several interesting issues and opportunities in this field. 
    
    \item Section \ref{sec:conclusion} is the conclusion of this paper.
  

\end{itemize}

\begin{figure}[hbtp]
    \vspace{-10pt}
    \centering
   
    \includegraphics[page=9, width=0.42\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
    \vspace{-5pt}
    \caption{Illustrations of Euclidean and non-Euclidean data: (a) Image from Euclidean space; (b) Graph data from non-Euclidean space.}
    \label{fig:background:graphs}
   
\end{figure}


\section{Background} \label{sec:background} 

This section provides some background concepts of graphs as well as GNNs, and introduces the two training methods applied in GNN training: full-batch and mini-batch.





\subsection{Graphs} \label{sec:background:graphs}



A graph is a type of data structure consisting of vertices and edges.
Its flexible structure can effectively express the relationship among a set of objects with arbitrary size and undetermined structure, which is called non-Euclidean data.
As shown in Fig. \ref{fig:background:graphs} (a) and (b), the form of non-Euclidean data is not as highly structured as Euclidean data.
However, by using vertices to represent the objects and edges to represent relationships among the objects, graphs can effectively represent non-Euclidean data, such as social networks and knowledge graphs.

There are mainly three taxonomies of graphs:

\begin{itemize}
    \item \textbf{Directed/Undirected Graphs:}
    Every edge in a directed graph has a fixed direction, indicating that the connection is only from a source vertex to a destination vertex.
    However, in an undirected graph, the connection represented by an edge is bi-directional between the two vertices.
    An undirected graph can be transformed into a directed one, in which two edges in the opposite direction represent an undirected edge in the original graph.
    
    \item \textbf{Homogeneous/Heterogeneous Graphs:}
    Homogeneous graphs contain a single type of vertex and edge, while heterogeneous graphs contain multiple types of vertices and multiple types of edges. 
    Thus, heterogeneous graphs are more powerful in expressing the relationships between different objects.
    
    \item \textbf{Static/Dynamic Graphs:}
    The structure and the feature of static graphs are always unchanged, while those of dynamic graphs can change over time.
    A dynamic graph can be represented by a series of static graphs with different timestamps.
    
\end{itemize}


\subsection{Graph Neural Networks}\label{sec:background:graph_neural_network}

\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=8, width=0.60\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Model architecture of GNNs. $h$ represents $h_v^l$, the representation feature of vertex $v$ at the $l$-th layer. $a$ represents $a_v^l$, the aggregation result of vertex $v$ at the $l$-th layer.}
    \label{fig:01_gnn}
   
\end{figure*}



GNNs have been dominated to be a promising algorithmic model for learning knowledge from graph data~\cite{RGCN,GIN,spatial_temporal_GCN, DBLP:conf/kdd/WuPL0CZ20/pan_gnn01, DBLP:journals/tkdd/WuPDZ21/pan_gnn02, DBLP:conf/icdm/ZhuZPZW19/pan_gnn04}.
It takes the graph data as input and learns a representation vector for each vertex in the graph. The learned representation can be used for down-stream tasks such as vertex prediction \cite{iclr_semi_supervised_classification_with_nodeprediction}, 
link prediction \cite{nips_link_prediction_based_on_linkprediction}, and
graph prediction \cite{aaai_an_end_to_end_deep_learing_graphprediction}.




As illustrated in Fig. \ref{fig:01_gnn}, a GNN model consists of one or multiple layers consisting of neighbor aggregation and neural network operations, referred to as the Aggregation step and Combination step, respectively.
In the Aggregation step, the Aggregate function $Aggregate(~)$ is used to aggregate the feature vectors of in-coming neighboring vertices from the previous GNN layer for each target vertex.
For example, in Fig. \ref{fig:01_gnn}, vertex 4 would gather the feature vectors of itself and its incoming neighboring vertices (i.e., vertex 2, 5, 8) using the Aggregate function.
In the Combination step, the Combine function $Combine(~)$ transforms the aggregated feature vector of each vertex using neural network operations.
To sum up, the aforementioned computation on a graph $\mathcal{G(V,E)}$ can be formally expressed by
\begin{align}  
    a_v^l & = Aggregate(\{h_u^{l-1}|u \in N(v) \cup \{v\}\}) \label{eq1} \\
    h_v^l & = Combine(a_v^l) \label{eq2}
\end{align}
where $h_v^l$ denotes the feature vector of vertex $v$ at the $l$-th layer, and $N(v)$ represents the neighbors of vertex $v$.
Specifically, the input feature of vertex $v \in \mathcal{V}$ is denoted as $h_v^0$.


\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=2, width=0.99\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Training methods for GNNs and their distributed implementations.}
    \label{fig:overall_training_method}
   
\end{figure*}



\Dang
}

\subsection{Training Methods for Graph Neural Networks} \label{sec:background:training_method}

In this subsection, we introduce the training methods for GNNs, which are approached in two ways including full-batch training \cite{iclr_semi_supervised_classification_ley_gcn_fullbatch, iclr_graph_attention_ley_gat} and mini-batch training \cite{iclr_fastgcn_ley_minibatch, nips/adaptive_sampling/layerwise2, nips_inductive_representation_ley_graphsage_minibatch, iclr_graphsaint, kdd_gns}.



A typical training procedure of neural networks, including GNNs, includes forward propagation and backward propagation.
In forward propagation, the input data is passed through the layers of neural networks towards the output.
Neural networks generate differences of the output of forward propagation by comparing it to the predefined labels.
Then in backward propagation, these differences are propagated through the layers of neural networks in the opposite direction, generating gradients to update the model parameters.

As illustrated in Fig. \ref{fig:overall_training_method}, training methods of GNNs can be classified into full-batch training \cite{iclr_semi_supervised_classification_ley_gcn_fullbatch, iclr_graph_attention_ley_gat} and mini-batch training \cite{iclr_fastgcn_ley_minibatch, nips/adaptive_sampling/layerwise2, nips_inductive_representation_ley_graphsage_minibatch, iclr_graphsaint, kdd_gns}, depending on whether the whole graph is involved in each \textbf{round}.
Here, we define a \textbf{round} of full-batch training consisting of a model computation phase, including forward and backward propagation, and a parameter update phase.
On the other hand, a \textbf{round} in mini-batch training additionally contains a sampling phase, which samples a small-sized workload required for the subsequent model computation and thus locates prior to the other two phases.
Thus, an \textbf{epoch}, which is defined as an entire pass of the data, is equivalent to a round of full-batch training, while that in mini-batch training usually contains several rounds.
Details of these two methods are introduced below.








\subsubsection{Full-batch Training} \label{sec:background:full_batch_training}
Full-batch training utilizes the whole graph to update model parameters in each round.









Given a training set $\mathcal{V}_t \subset \mathcal{V}$,
the loss function of full-batch training is
\begin{equation}\label{eq3_full_loss}
    \mathcal{L} = \frac{1}{|\mathcal{V}_t|}\sum_{v_i \in \mathcal{V}_t} \nabla l(y_i, z_i)
\end{equation}
where $\nabla l(~)$ is a loss function, $y_i$ is the known label of vertex $v_i$, and $z_i$ is the output of GNN model when inputting feature $x_i$ of $v_i$.
In each epoch, GNN model needs to aggregate representations of all neighboring vertices for each vertex in $\mathcal{V}_t$ all at once.
As a result, the model parameters are updated only once at each epoch.


\subsubsection{Mini-batch Training}\label{sec:background:mini_batch_training}


Mini-batch training utilizes part of the vertices and edges in the graph to update model parameters in every forward propagation and backward propagation. 
It aims to reduce the number of vertices involved in the computation of one round to reduce the computing and memory  resource requirements.

Before each round of training, a mini-batch $\mathcal{V}_s$ is sampled from the training dataset $\mathcal{V}_t$.
By replacing the full training dataset $\mathcal{V}_t$ in equation (\ref{eq3_full_loss}) with the sampled mini-batch $\mathcal{V}_s$, we obtain the loss function of mini-batch training:
\begin{equation}\label{eq3_mini_loss}
    \mathcal{L} = \frac{1}{|\mathcal{V}_s|}\sum_{v_i \in \mathcal{V}_s} \nabla l(y_i, z_i)
\end{equation}
It indicates that for mini-batch training, the model parameters are updated multiple times at each epoch, since numerous mini-batches are needed to have an entire pass of the training dataset, resulting in many rounds in an epoch.
Stochastic Gradient Descent (SGD) \cite{compstat_sgd}, a variant of gradient descent which applies to mini-batch, is used to update the model parameters according to the loss $\mathcal{L}$.



\textbf{Sampling:}
Mini-batch training requires a sampling phase to generate the mini-batches.
The sampling phase first samples a set of vertices, called target vertices, from the training set according to a specific sampling strategy, and then it samples the neighboring vertices of these target vertices to generate a complete mini-batch.
The sampling method can be generally categorized into three groups: Node-wise sampling, Layer-wise sampling, and Subgraph-based sampling \cite{liuxin_sampling_survey, arxiv_salient}.
\begin{itemize}
    \item \textbf{Node-wise sampling} \cite{nips_inductive_representation_ley_graphsage_minibatch, kdd_graph_convolutional_ley_pinsage, icml_learing_steady_states_ley_nodewise1, icml_stochastic_training_ley_nodewise2} is directly applied to the neighbors of a vertex: the algorithm selects a subset of each vertex's neighbors. 
    It is typical to specify a different sampling size for each layer. 
    For example, in GraphSAGE \cite{nips_inductive_representation_ley_graphsage_minibatch}, it samples at most 25 neighbors for each vertex in the first layer and at most 10 neighbors in the second layer.
    \item \textbf{Layer-wise sampling} \cite{iclr_fastgcn_ley_minibatch, nips_layer_dependent_ley_layerwise1, nips/adaptive_sampling/layerwise2} enhances Node-wise sampling. 
   
    It selects multiple vertices in each layer and then proceeds recursively layer by layer.
    \item \textbf{Subgraph-based sampling} \cite{iclr_graphsaint, kdd/cluster_gcn/subgraph_based1, ijcnn/ripple_walk_training/subgraph_based2, ipdps/accurate_efficient/subgraph_based3} first partition the original graph into multiple subgraphs, and then samples the mini-batches from one or a certain number of them.
\end{itemize}







\section{Taxonomy of Distributed GNN Training}\label{sec:taxonomy}



\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=10, width=0.75\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Taxonomy of distributed GNN training.}
    \label{fig:taxonomy:tax_of_cate}
   
\end{figure*}





This section introduces the taxonomy of distributed GNN training.
As shown in Fig. \ref{fig:taxonomy:tax_of_cate}, we firstly categorize it into distributed full-batch training and distributed mini-batch training, according to the training method introduced in Sec. \ref{sec:background:training_method}, i.e., whether the whole graph is involved in each round, and show the key differences between the two types.
Each of the two types is classified further into two detailed types respectively by analyzing their workflows. This section introduces the first-level category, that is, distributed full-batch training and distributed mini-batch training, and makes a comparison between them.
The second-level category of the two types will later be introduced in Sec. \ref{sec:dft} and Sec. \ref{sec:dmt}, respectively.



\subsection{Distributed Full-batch Training} \label{sec:taxonomy:dft_intro}














Distributed full-batch training is the distributed implementation of GNN full-batch training, as illustrated in Fig. \ref{fig:overall_training_method}.
Except for graph partition, a major difference is that multiple computing nodes need to synchronize gradients before updating model parameters, so that the models across the computing nodes remain unified.
Thus, a round of distributed full-batch training includes two phases: model computation (forward propagation + backward propagation) and gradient synchronization. The model parameter update is included in the gradient synchronization phase.

Since each round involves the entire raw graph data, a considerable amount of computation and a large memory footprint are required in each round \cite{arxiv_sar,eurosys_flexgraph,sc_distgnn}.
To deal with it, distributed full-batch training mainly adopts the workload partitioning method \cite{atc_neugraph,mlsys_roc}: split the graph to generate small workloads, and hand them over to different computing nodes.




Such a workflow leads to a lot of irregular inter-node communications in each round, mainly for transferring the features of vertices along the graph structure.
This is because the graph data is partitioned and consequently stored in a distributed manner, and the irregular connection pattern in a graph, such as the arbitrary number and location of a vertices' neighbors.
Therefore, many uncertainties exist in the communication of distributed full-batch training, including the uncertainty of the communication content, target, time, and latency, leading to challenges in the optimization of distributed full-batch training.



As shown in Fig. \ref{fig:taxonomy:tax_of_cate}, we further classify distributed full-batch training more specifically into two categories according to whether the workload is preset in the preprocessing phase, namely dispatch-workload-based execution and preset-workload-based execution, as shown in the second column of Table \ref{table:category}.
Their detailed introduction and analysis are presented in Sec. \ref{sec:dft:chunk_execution} and Sec. \ref{sec:dft:partition_execution}.


\subsection{Distributed Mini-batch Training} \label{sec:taxonomy:dmt_intro}

Similar to distributed full-batch training, distributed mini-batch training is the distributed implementation of GNN mini-batch training as in Fig. \ref{fig:overall_training_method}.
It also needs to synchronize gradients prior to model parameter update, so a round of distributed mini-batch training includes three phases: sampling, model computation, and gradient synchronization. The model parameter update is included in the gradient synchronization phase.

Distributed mini-batch training parallelizes the training process by processing several mini-batches simultaneously, one for each computing node.
The mini-batches can be sampled either by the computing node itself or by other devices, such as another node specifically for sampling.
Each computing node performs forward propagation and backward propagation on its own mini-batch.
Then, the nodes synchronize and accumulate the gradients, and update the model parameters accordingly.
Such a process can be formulated by 
\begin{equation}\label{eq01_ley_minibatch_gradient} 
    \mathcal{W}_{i+1} = \mathcal{W}_i + \sum^n_{j = 1} \nabla g_{i,j}
\end{equation}
where $\mathcal{W}_i$ is the weight parameters of model in the $i^{\text{th}}$ round of computation, $\nabla g_{i,j}$ is the gradients generated in the backward propagation of the computing node $j$ in the $i^{\text{th}}$ round of computation, and the $n$ is the number of the computing nodes. 


As shown in Fig. \ref{fig:taxonomy:tax_of_cate}, we further classify it more specifically into two categories according to whether the sampling and model computation are decoupled, namely individual-sample-based execution and joint-sample-based execution, as shown in the second column of Table \ref{table:category}.
Their detailed introduction and analysis are presented in Sec. \ref{sec:dmt:sample_individual_execution} and Sec. \ref{sec:dmt:sample_joint_execution}.



\begin{table*}[!t]
   
 \caption{Comparison between distributed full-batch training and distributed mini-batch training.} \label{table:overall_comparison_distrbuted_training}

 \centering
\renewcommand\arraystretch{1.8} 
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|cc|}
\hline
 & \textbf{Distributed Full-batch Training}   & \textbf{Distributed Mini-batch Training}  \\ \hline \hline
 \textbf{Workflow Characteristic} & Collaborative Computation with Workload Partition & Independent Computation with Periodic Synchronization \\ \hline
 \textbf{Independence of Computation}   & Low   & High  \\ \hline
 \textbf{Involvement of Entire Graph?}  & Yes   & No  \\ \hline
 \textbf{Memory Capacity Requirement}   & High & Low \\ \hline
  \textbf{Communication Volume}          & Large & Small \\ \hline
 \textbf{Prime Communication Content}   & Features of Neighboring Vertices & Mini-batches \\ \hline
  \textbf{Communication Irregularity}   & High & Low \\ \hline
 \textbf{Communication Uncertainty}     & High & Low \\ \hline
 \textbf{Communication Bandwidth Requirement} & High & Low \\ \hline
 \textbf{Additional Overhead}           & -    & An Extra Phase (Sampling Phase) \\ \hline
 \textbf{Primary Challenges}            & Workload Imbalance and Massive Transmissions & Insufficient Sampling Performance \\ \hline

\end{tabular}
    }
\end{table*}



\subsection{Comparison Between Distributed Full-batch Training and Distributed Mini-batch Training} \label{sec:taxonomy:dft_dmt_comparison}




This subsection compares distributed full-batch training with distributed mini-batch training of GNNs. The major differences are also summarized in Table \ref{table:overall_comparison_distrbuted_training}.



The workflow of distributed full-batch training is summarized as collaborative computation with workload partition.
Since the computation in each round involves the entire graph, the computing nodes need to cache it locally, leading to a high memory capacity requirement \cite{atc_neugraph}.
Also, the communication volume of distributed full-batch training is large \cite{sc_distgnn, sc_reducint_communication_in_graph_cagnet}.
In every round, the Aggregate function needs to collect the features of neighbors for each vertex, causing a large quantity of inter-node communication requests since the graph is partitioned and stored on different nodes.
Considering that the communication is based on the irregular graph structure, the communication irregularity of distributed full-batch training is high \cite{eurosys_dgcl}.
Another characteristic of communication is high uncertainty.
The time of generating the communication request is indeterminate, since each computing node sends communication requests according to the currently involved vertices in its own computing process.
As a result, the main challenges of distributed full batch training are workload imbalance and massive transmissions \cite{eurosys_dgcl, sc_distgnn, mlsys_roc}.



In contrast, the workflow of distributed mini-batch training is summarized as independent computation with periodic synchronization.
The major transmission content is the mini-batches, sent from the sampling node (or component) to the computing node (or component) responsible for the current mini-batch \cite{socc_pagraph, cluster_2pgraph, /cal22/linhaiyang/characterizing_and_gnn/}.
As a result, these transmissions have low irregularity and low uncertainty, as the direction and content of transmission are deterministic.
Since the computation of each round only involves the mini-batches, it triggers less communication volume and requires less memory capacity \cite{socc_pagraph}.
However, the extra sampling phase may cause some new challenges.
Since the computation of the sampling phase is irregular and requires access to the whole graph for neighbor information of a given vertex, it is likely to encounter the problem of insufficient sampling performance, causing the subsequent computing nodes (or components) to stall due to lack of input, resulting in a performance penalty \cite{/cal22/linhaiyang/characterizing_and_gnn/, arxiv_salient}.




\Dang{
}


\begin{table*}[hbtp]
   
 \caption{Summary of recent studies on distributed GNN training.} \label{table:category}

 \centering
 \renewcommand\arraystretch{1.5} 
    \resizebox{0.99\textwidth}{!}{
\begin{tabular}{|c|rrrrrr|}
\hline
\textbf{Name}     & \textbf{Taxonomy}   & \textbf{Software Framework} & \textbf{Hardware Platform} &\textbf{GPU Types}  &\textbf{Year} &\textbf{Code Available}\\ \hline \hline
\multicolumn{7}{|c|}{\begin{tabular}[c]{@{}c@{}} \textbf{Distributed Full-batch Training} \end{tabular}} \\ \hline
             NeuGraph \cite{atc_neugraph}          &Dispatch-workload-based Execution        &NeuGraph   &multi-GPU  &Tesla P100 &2019 &-\\
             Roc \cite{mlsys_roc}                  &Dispatch-workload-based Execution        &Roc        &multi-GPU  &Tesla P100 &2020 &Yes\\
             CAGNET \cite{sc_reducint_communication_in_graph_cagnet}              &Preset-workload-based Execution        &PyTorch    &multi-GPU  &Tesla V100  &2020 &Yes\\
             DGCL \cite{eurosys_dgcl}              &Preset-workload-based Execution    &PyTorch       &multi-GPU  &Tesla V100  &2021 &-\\
             DistGNN \cite{sc_distgnn}             &Preset-workload-based Execution    &DGL        &multi-CPU  &-   &2021   &Yes\\
             FlexGraph \cite{eurosys_flexgraph}    &Preset-workload-based Execution    &FlexGraph  &multi-CPU  &-   &2021   &-\\
             MG-GCN \cite{arxiv_mg_gcn}            &Preset-workload-based Execution        &MG-GCN     &multi-GPU  &Tesla V100/A100 &2021 &Yes\\
             Dorylus \cite{osdi_dorylus}           &Preset-workload-based Execution        &Dorylus    &multi-CPU  &- &2021 &Yes\\
             SAR\cite{arxiv_sar}                   &Preset-workload-based Execution    &DGL        &multi-CPU  &- &2021 &-\\ 
\hline 
\multicolumn{7}{|c|}{\begin{tabular}[c]{@{}c@{}} \textbf{Distributed Mini-batch Training} \end{tabular}} \\ \hline
            AliGraph \cite{pvldb_aligraph}     &Joint-sample-based Execution     &AliGraph   &multi-CPU  &- &2019 &-\\
            DistDGL \cite{ia3_distdgl}         &Joint-sample-based Execution     &DGL    &multi-CPU  &-       &2020       &-\\
            AGL \cite{pvldb_agl}               &Individual-sample-based Execution          &AGL    &multi-CPU  &- &2020 &- \\
            PaGraph \cite{socc_pagraph}        &Joint-sample-based Execution     &DGL    &multi-GPU  &GTX 1080Ti  &2020   &-\\
            2PGraph \cite{cluster_2pgraph}     &Joint-sample-based Execution     &PyTorch    &multi-GPU  &RTX 3090 &2021  &-\\
            LLCG \cite{arxiv_llcg}             &Joint-sample-based Execution     &PyG    &multi-GPU  &RTX 8000    &2021   &Yes\\
           
            GraphTheta \cite{arxiv_graphtheta}     &Joint-sample-based Execution       &GraphTheta &multi-CPU  &- &2021 &-\\
            SALIENT \cite{arxiv_salient}       &Individual-sample-based Execution           &PyG    &multi-GPU  &Tesla V100    &2021   &-\\
            P3 \cite{/osdi/Gandhi/p3/distributed_deep_graph/}  &Joint-sample-based Execution &DGL &multi-GPU &Tesla P100 &2021 &-\\
            DistDGLv2 \cite{arxiv_distdglv2}       &Joint-sample-based Execution &DistDGLv2  &multi-GPU  &Tesla T4  &2022 &-\\
            DGTP \cite{DBLP:conf/infocom/LuoBW22/new02/DGTP} &Individual-sample-based Execution & DGL &multi-GPU &GTX 1080Ti &2022 &-\\
\hline 
\end{tabular}
    }
\end{table*}







\subsection{Other Information of Taxonomy}\label{sec:taxonomy:others_information}



Table \ref{table:category} provides a summary of the current studies on distributed GNN training using our proposed taxonomy.
Except for the aforementioned classifications, we also add some supplemental information in the table to provide a comprehensive review of them.


\textbf{Software frameworks.}
The software frameworks used by the various studies are shown in the third column of Table \ref{table:category}.
PyTorch Geometric (PyG) \cite{arxiv_pyg} and Deep Graph Library (DGL) are the most popular among them.
In addition, there are many newly proposed software frameworks aiming at distributed training of GNNs, and many of them are the optimization version of PyG \cite{arxiv_pyg} or DGL \cite{arxiv_dgl}.
A detailed introduction to the software frameworks of distributed GNN training is presented in Sec. \ref{sec:software_framework}.


\textbf{Hardware platforms.}
Multi-CPU platform and multi-GPU platform are the most common hardware platforms of distributed GNN training, as shown in the fourth column of Table \ref{table:category}.
Multi-CPU platform usually refers to a network with multiple servers, which uses CPUs as the only computing component.
On the contrary, in multi-GPU platforms, GPUs are responsible for the major computing work, while CPU(s) handle some computationally complex tasks, such as workload partition and sampling.
A detailed introduction to the hardware platforms is presented in Sec. \ref{sec:hardware_platform}.


\textbf{Year.} 
The contribution of distributed GNN training began to emerge in 2019 and is now showing a rapid growth trend.
This is because more attention is paid to it due to the high demand from industry and academia to shorten the training time of GNN model.

\textbf{Code available.}
The last column of Table \ref{table:category} simply records the open source status of the corresponding study on distributed GNN training for the convenience of readers.





\section{Distributed Full-batch Training}\label{sec:dft}

\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=3, width=0.99\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{GNN distributed full-batch training: (a) Categories of GNN distributed full-batch training; (b) Illustration of dispatch-workload-based execution; (c) Illustration of preset-workload-based execution.}
    \label{fig:02_dft}
   
\end{figure*}



This section describes GNN distributed full-batch training in detail.
Our taxonomy classifies it into two categories according to whether the workload is preset in the preprocessing phase, namely dispatch-workload-based execution and preset-workload-based execution, as shown in Fig. \ref{fig:02_dft} (a).


\subsection{Dispatch-workload-based Execution}\label{sec:dft:chunk_execution}

The dispatch-workload-based execution of distributed full-batch training is illustrated in Fig. \ref{fig:02_dft} (b). Its workflow, computational pattern, communication pattern, and optimization techniques are introduced in detail as follows.


\subsubsection{Workflow}




In the dispatch-workload-based execution, a leader and multiple workers are used to perform training.
The leader stores the model parameters and the graph data, and is also responsible for scheduling:
it splits the computing workloads into chunks, distributes them to the workers, and collects the intermediate results sent from the workers.
It also processes these results and advances the computation.
Note that, the \textit{chunk} we use here is as a unit of workload.



\subsubsection{Computational Pattern} 
The computational patterns of forward propagation and backward propagation are similar in dispatch-workload-based execution: the latter can be seen as the reversed version of the former.
As a result, we only introduce forward propagation's computational pattern here for simplicity.
The patterns of the two functions in forward propagation (Aggregate and Combine) differ a lot and will be introduced below respectively.




\textbf{Aggregate function.} The computational pattern of the Aggregate function is dynamic and irregular, making workload partition for this step a challenge.
In the Aggregation step, each vertex needs to aggregate the features of its own neighbors.
As a result, the computation of the Aggregation step relies heavily on the graph structure, which is irregular or even changeable.
Thus, the number and memory location of neighbors vary significantly among vertices, resulting in the dynamic and irregular computational pattern \cite{hpca/hygcn/gnn_asic_acc}, causing the poor workload predictability and aggravating the difficulty of workload partition.



\textbf{Combine function.} The computational pattern of the Combine function is static and regular, thus the workload partition for it is simple.
The computation of the Combination step is to perform neural network operations on each vertex.
Since the structure of neural networks is regular and these operations share the same weight parameters, the Combination step enjoys a regular computational pattern.
Consequently, a simple partitioning method is sufficient to maintain workload balance, so it is relatively not a major consideration in dispatch-workload-based execution of GNN distributed full-batch training.


\subsubsection{Communication Pattern}




The majority of communication is the transmission of input data and output results between the leader and the workers \cite{atc_neugraph}. 
Since the leader is responsible for workload distribution and intermediate result collection, it needs to communicate with multiple workers.
Such a communication structure results in a one-to-many communication pattern, resulting in a possible bottleneck in the leader's communication path \cite{atc_neugraph}.
However, these communications are relatively regular since the distribution of tasks is controlled by the leader.
Therefore, the communication path congestion can be avoided to some extent by optimized scheduling techniques.




\subsubsection{Optimization Techniques}
Next, we introduce the optimization techniques used to partition workload, balance workload, reduce transmission, and exploit parallelism for dispatch-workload-based execution. We classify them into four categories, including 
\blackcircled{1} Vertex-centric Workload Partition, 
\blackcircled{2} Balanced Workload Generation, 
\blackcircled{3} Transmission Planning, and 
\blackcircled{4} Feature-dimension Workload Partition. A summary for these categories is shown in Table \ref{table:summary_of_chunk_execution}.
Note that the transmission reduction in this paper refers to a reduction in the amount of transmitted data or in transmission time.

\begin{table*}[hbtp]
   
 \caption{Summary of various categories of optimization techniques used in dispatch-workload-based execution of distributed full-batch training.} \label{table:summary_of_chunk_execution}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{1\textwidth}{!}{
\begin{tabular}{|l|cccc|}
\hline
\textbf{Optimization Technique}     
& \textbf{Function}  &  \textbf{Operation Object} & \textbf{Focus}  & \textbf{Related Work}\\ \hline \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \blackcircled{1} Vertex-centric Workload Partition   \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Workload Partition  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Graph or Matrix \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Graph or Matrix \\Partition Strategy \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   NeuGraph \cite{atc_neugraph}, Roc \cite{mlsys_roc} \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}    \blackcircled{2} Balanced Workload Generation \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Workload Balance \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Partition Operation \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Partition Strategy \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}    Roc \cite{mlsys_roc} \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{3} Transmission Planning  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Reduction  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Transmission Operation  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Roc \cite{mlsys_roc}, NeuGraph \cite{atc_neugraph} \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  \blackcircled{4} Feature-dimension Workload Partition   \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Parallelism Exploitation   \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Vertices' Feature  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Feature Partition Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  NeuGraph \cite{atc_neugraph}  \end{tabular}}  \\
    &   &   &   &   \\ \hline


\end{tabular}
    }
\end{table*}







\textbf{\blackcircled{1} Vertex-centric Workload Partition.}
Vertex-centric workload partition refers to the technique of generating workload chunks by partitioning the graph or matrix from the perspective of vertices. 
Specifically, the graph is partitioned into a list of subgraphs according to the source vertex $u$ and the destination vertex $v$ of edge $(u, v)$.
Then the subgraphs are taken as the workload chunk, and the leader distributes them to each computing node for computation.
This is a very common partitioning method for processing large-scale graphs in the traditional graph analytics \cite{micro/graphicionado/graph_processing_asic_acc, micro/alleviating_irregularity_in/yan/graphdyns/graph_processing_asic_acc, pvldb/a_distributed_multi_gpu/roc_graph_partition}.



\begin{figure}[hbtp]
   
    \centering
    \includegraphics[page=6, width=0.45\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Illustration of 2D graph partition.}
   
    \label{fig:05_chunk_vertex_partition}
    \vspace{-10pt}
\end{figure}






Fig. \ref{fig:05_chunk_vertex_partition} illustrates 2D graph partition, an typical example of graph partition.
The vertices are firstly partitioned into $P$ disjoint blocks.
Then, we tile the edges into $P \times P$ chunks according to their source and destination vertices: in the $y^{\text{th}}$ chunk of the $x^{\text{th}}$ row, the source vertices of the edges all belong to $x^{\text{th}}$ source vertex block, and the destination vertices all belong to $y^{\text{th}}$ destination vertex block.
This partitioning method works well for the Aggregation step, which needs to transfer the information of the source vertex to the destination vertex along the edge.



NeuGraph \cite{atc_neugraph} adopts the 2D graph partitioning method. 
It chooses $P$ as the minimum integer satisfying the requirement to fit each chunk in the device memory of GPUs.
Roc \cite{mlsys_roc}, on the other hand, uses the graph partition strategy proposed in \cite{pvldb/a_distributed_multi_gpu/roc_graph_partition}, which can also be mentioned as 1D graph partition.
Suppose there are now $n$ computing nodes, and the number of vertices in the graph is $T$.
Then select $n$-1 numbers, ranging from 1 to $T$, to split the vertices into $n$ parts, that is, $n$ subgraphs.
In this way, each subgraph holds consecutively numbered vertices, which are stored in adjacent locations, and their in-edges, thereby improving the data access efficiency of computing nodes.












\textbf{\blackcircled{2} Balanced Workload Generation.}
Workload balance is an extremely important optimization goal for dispatch-workload-based execution.
Since the workloads are split and distributed to multiple computing nodes, the prerequisite of the continuation of computing is that all the computing nodes have already returned their intermediate results.
If the workload is not evenly partitioned, the consequent lag of waiting will stall the training process.
Therefore, it is necessary to carefully adjust the workload partition, so as to make the workload of each computing node as balanced as possible.



In response to that, Roc \cite{mlsys_roc} proposes a linear regression cost model to produce balanced workloads in each round.
The cost model is used to predict the computation time of a GNN layer on an arbitrary input, which could be the whole or any subset of an input graph.


\textbf{\blackcircled{3} Transmission Planning.}
Planning data transmission is helpful to make full use of reusable data across computing components and nodes, thereby reducing data transmission.
In dispatch-workload-based execution, the major transmission overhead is caused by the requirement to transmit the input data and intermediate results.
Recent work focuses on harvesting two following optimization opportunities to reduce this overhead.


\textit{Avoid repeated transmission of overlapped data.}
The input data required by different computing tasks may overlap.
As a result, caching these overlapped parts on computing nodes or components is a reasonable way to reduce transmission.
Roc \cite{mlsys_roc} formulates GPU memory management as a cost minimization problem. 
It uses a recursive dynamic programming algorithm to find the global optimal solution to decide which part of the data should be cached in GPU memory for reuse, according to the input graph, the GNN model, and device information.
This minimizes data transmission between the CPU and GPUs.




\textit{Rationally select the source of the transmission.}
The overhead of data transmission can be reduced by allowing computing components or nodes to send data, so every component or node can rationally select the source of the transmission.
As a result, the design can reduce the overhead by decreasing the transmission distance.
For instance, NeuGraph \cite{atc_neugraph} employs a chain-based streaming scheduling scheme.
The idea is to have one GPU (which already holds the data chunk) forward the data chunk to its neighbor GPU under the same PCIe switch, which can eliminate the bandwidth contention on the upper-level shared inter-connection link.



\textbf{\blackcircled{4} Feature-dimension Workload Partition.}
Feature-dimension partition refers to the finer partition of the workload from the dimension of the vertex feature, to make full use of the parallel computing hardware in the computing node.
In traditional graph analytics, the majority of the input is the structure data of graphs, such as edges.
However, in GNNs, vertex features make up the majority of the dataset, while graph structure takes up only a tiny fraction of it.
This is because the feature of each vertex in traditional graph analytics is usually just a scalar, while it is a long-length vector or even a large tensor in GNNs.
For example, the feature dimension of a vertex can be 512, 1024, or even more \cite{/cal22/linhaiyang/characterizing_and_gnn/, atc_neugraph}.
It is thus feasible to split the workload more finely in the feature dimension, thereby further improving the degree of computational parallelism.




To harvest the opportunity, NeuGraph \cite{atc_neugraph} explores feature-level parallelism by splitting the feature of each vertex evenly into multiple parts, which partitions the workload in a more fine-grained way.
It then assigns it to different GPU threads for corresponding computation.
This method takes full advantage of the massive parallel computing resources of GPUs.





\subsection{Preset-workload-based Execution}\label{sec:dft:partition_execution}

The preset-workload-based execution of distributed full-batch training is illustrated in Fig. \ref{fig:02_dft} (c).
Its workflow, computational pattern, communication pattern, and optimization techniques are introduced in detail as follows.

\subsubsection{Workflow}


Preset-workload-based execution involves multiple collaborative workers to perform training.
The graph is firstly split into subgraphs through the partition operation in the preprocessing phase.
Then, each worker holds one subgraph and a replica of the model parameters.
During training, each worker is responsible to complete the computing tasks of all the vertices in its subgraph.
As a result, a worker needs to query the information from other workers to gather the information of neighboring vertices.
However, the Combine function can be performed directly locally, as the model parameters are replicated, but this also means that gradient synchronization is required for each round to ensure the consistency of model parameters across the nodes.





\subsubsection{Computational Pattern}




The computational pattern of preset-workload-based execution differs significantly in different steps.
In the Aggregation step, a node needs to query the neighbor information of vertices from other nodes, so only when each computing node cooperates efficiently can the data be supplied to the target computing node in a timely manner.
However, in the Combination step, each computing node conducts the operation on the vertices in its own subgraph independently due to the local replica of model parameters.
As a result, the Aggregation step is more prone to inefficiencies such as computational stagnation, and it is the key optimization point for preset-workload-based execution.





In addition, the preset workload has the benefit that the whole graph can be loaded at a time, as it is partitioned into small subgraphs which fit in the memory of computing nodes in the preprocessing phase.
This means that it is more scalable than dispatch-workload-based execution when either adding more computing resources or increasing the size of the dataset.
This avoids frequent accesses to graph data from low-speed storage such as hard disks, thereby ensuring the timely provision of data for high-speed computing.



\subsubsection{Communication Pattern}
Communication happens mostly in the Aggregation step and gradient synchronization.
Due to the distributed storage of graph data, it encounters a lot of irregular transmissions during the Aggregation step when collecting the features of its neighboring vertices that are stored in other nodes due to graph partition \cite{eurosys_dgcl}.
Since the features of vertices are vectors or even tensors, the amount of data transmitted in the Aggregation step is large.
Also, the communication is irregular due to the irregularity graph structure \cite{hpca/hygcn/gnn_asic_acc,micro/alleviating_irregularity_in/yan/graphdyns/graph_processing_asic_acc,Tigr}, which brings difficulty in optimizing connection.
In contrast, the communication overhead of gradient synchronization is minuscule due to the small size of model parameters and the regular communication pattern.
As a result, the communication between nodes in the Aggregation step is the main concern of preset-workload-based execution in distributed full-batch training.




\subsubsection{Optimization Techniques}

Here we introduce the optimization techniques used to balance workload, reduce transmission, and reduce memory pressure for preset-workload-based execution in detail.
We classify them into four categories: \blackcircled{1} Graph Pre-partition, \blackcircled{2} Transmission Optimization, \blackcircled{3} Delayed Aggregation, and \blackcircled{4} Activation Rematerialization.
A summary for these categories is shown in Table \ref{table:summary_of_partition_execution}.


\begin{table*}[hbtp]
   
 \caption{Summary of various categories of optimization techniques used in preset-workload-based execution of distributed full-batch training.} \label{table:summary_of_partition_execution}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{1\textwidth}{!}{
\begin{tabular}{|l|cccc|}
\hline
\textbf{Optimization Technique}     & \textbf{Function}  & \textbf{Operation Object} & \textbf{Focus} & \textbf{Related Work}\\ \hline \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}\blackcircled{1} Graph Pre-partition\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Workload Balance and \\Transmission Reduction\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Entire Graph\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Graph Partition Strategy\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}DGCL \cite{eurosys_dgcl}, Dorylus \cite{osdi_dorylus}, \\FlexGraph \cite{eurosys_flexgraph}, DistGNN \cite{sc_distgnn}\end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}\blackcircled{2} Transmission Optimization\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Transmission Reduction\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Transmission Data\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Transmission Strategy\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}} DGCL \cite{eurosys_dgcl},  FlexGraph \cite{eurosys_flexgraph}\end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}\blackcircled{3} Delayed Aggregation\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Transmission Reduction\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Aggregation Operation\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Aggregation Strategy\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Dorylus \cite{osdi_dorylus}, DistGNN \cite{sc_distgnn}\end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}\blackcircled{4} Activation Rematerialization\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Memory Pressure Reduction\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Intermediate Results\end{tabular}} &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Intermediate Results \\Retrieve Strategy\end{tabular}}  &\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}SAR \cite{arxiv_sar}\end{tabular}}  \\
    &   &   &   &   \\ \hline

\end{tabular}
    }
\end{table*}




\textbf{\blackcircled{1} Graph Pre-partition.}
Graph pre-partition refers to partitioning the whole graph into several subgraphs according to the number of computing nodes, mainly to balance workload and reduce transmission \cite{eurosys_dgcl}. This operation is conducted in the preprocessing phase.
The two key principles in designing the partitioning algorithm are listed as follows.


First, in order to pursue workload balance, the subgraphs need to be similar in size.
In preset-workload-based execution, each worker performs the computation of vertices within its own subgraph.
Therefore, the size of the subgraph determines the workload of the worker.
The main reference parameters are the number of vertices and edges in the subgraph.
Since preset-workload-based execution has a gradient synchronization barrier, workload balance is very important for computing nodes to complete a round of computation at a similar time.
Otherwise, some computing nodes will be idle, causing performance loss.

Second, minimizing the number of edge-cuts in the graph pre-partition can reduce communication overhead.
It is inevitable to cut edges in the graph pre-partition, meaning that the source and destination vertices of an edge might be stored in different computing nodes.
When the information of neighboring vertex is required during the computation of the Aggregation step, communication between workers is introduced.
Therefore, reducing the number of edges cut can reduce communication overhead in the Aggregation step.


DGCL \cite{eurosys_dgcl} uses METIS library \cite{metis/dgcl_partition_algorithm} to partition the graph for both the above two targets.
Dorylus \cite{osdi_dorylus} also uses an edge-cut algorithm \cite{osdi/gemini/dorylus_graph_partition} for workload balance.
DistGNN \cite{sc_distgnn} aims at the two targets too. 
However, it uses a vertex-cut based graph partition technique instead.
This means distributing the edges among the partitions. 
Thus, each edge exists in only one partition, while a vertex can reside in multiple partitions. 
Any updates to such vertex must be synchronized to its replicas in other partitions.
FlexGraph \cite{eurosys_flexgraph} partitions the graph in the manner of edge-cut too.
Besides, it learns a cost function to estimate the training cost for the given GNN model.
Using the estimated training cost, FlexGraph migrates the workload from overloaded partitions to underloaded ones to pursue workload balance.

\textbf{\blackcircled{2} Transmission Optimization.}
Transmission optimization refers to adjusting the transmission strategy between computing nodes to reduce communication overhead. Due to the irregular nature of communication in preset-workload-based execution, the demand for transmission optimization is even stronger than above.

DGCL \cite{eurosys_dgcl} provides a general and efficient communication library for distributed GNN training.
It tailors the shortest path spanning tree algorithm to transmission planning, which jointly considers fully utilizing fast links, avoiding contention, and balancing workloads on different links.





Compared to traditional transmission planning, FlexGraph \cite{eurosys_flexgraph} takes a different approach to take advantage of the aggregation nature of the Aggregate function.
FlexGraph \cite{eurosys_flexgraph} partially aggregates the features of neighboring vertices that co-locate at the same partition when possible, aiming to reduce the amount of data transmission and overlap partial aggregations and communications.
When each computing node receives a neighbor information request from other nodes, it will first partially aggregate the neighbor information locally, and then send the partial result to the requesting computing node, instead of directly sending the initial neighbor information.
The requesting computing node only needs to aggregate the received partial result with its local nodes to continue the computation.
As a result, due to the reduction in data transmission and the overlap of computation and communication, the communication overhead is significantly reduced.



\textbf{\blackcircled{3} Delayed Aggregation.}
By allowing the computing nodes to utilize old transmitted data in the Aggregation step, delayed aggregation can reduce the overhead of data transmission.
Normally, there is no scope for intra-epoch overlap due to the dependence between consecutive phases in an epoch.
Delayed aggregation solves the problem to overlap the computation and communication, allowing the model to use the previously transmitted data.
However, we need to point out that in order to ensure convergence and final accuracy, the delayed aggregation is mainly based on bounded asynchronous training \cite{osdi_dorylus}. 




Dorylus \cite{osdi_dorylus} uses bounded asynchronous training on two synchronization points: the update of weight parameters in the backward propagation, and the neighbor aggregation in the Aggregation step.
Bounded asynchronous training of GNNs is based on bounded staleness \cite{atc/exploiting_bounded_staleness/bounded_staleness/1, /nips/hogwild/bounded_staleness/2, icdcs/dynamic_stale_synchronous/bounded_staleness/3, /nips/more_effective_distributed/bounded_staleness/4}, an effective technique for mitigating the convergence problem by employing lightweight synchronization.
The key policy is to restrict the number of iterations between the fastest worker and the slowest worker to not exceed more than a user-specified staleness threshold $s$, where $s$ is a natural number.
As long as the policy is not violated, there is no waiting time among workers.



DistGNN \cite{sc_distgnn} proposes the delayed remote partial aggregates (DRPA) algorithm to overlap the communication with local computation, which is inter-epoch computation-communication overlap.
In the algorithm, the set of vertices that may be queried by other computing nodes is partitioned into $r$ subsets.
For each epoch computation, only the data of one subset is transmitted.
The transmitted data is not required to be received at this epoch, but after $r$ epochs.
This means that the computing nodes do not use the latest global data of vertices, but locally existing data of them.
This algorithm allows communication to overlap with more computational processes, thereby reducing communication overhead.





\textbf{\blackcircled{4} Activation Rematerialization.}
Activation rematerialization uses data retransmission and recomputation during the computation process to reduce the memory pressure of computing nodes caused by intermediate results or data.




In preset-workload-based execution, the graph data is stored in each worker in a distributed manner: if there are $n$ workers, then each worker only needs to store $1/n$ of raw data initially.
However, during the computation, each worker needs to store the information received from other workers.
In forward propagation, each worker needs to query other workers to obtain the neighbor information of its local vertices, and the information needs to be stored for later use in backward propagation.
As a result, the actual data stored by each worker during the computation is much larger than its initial size.
In addition, its size is difficult to estimate and may lead to memory overflow problems.



Activation rematerialization, a widely-applied and mature technology in DNN, solves the problem by storing all activations during forward propagation. Activation is the output of each layer of neural networks, which means the representation of each vertex of each layer in GNNs.
Its idea is to recompute or load the activations directly from disks during the backward propagation to reduce the pressure of memory \cite{/arxiv/training_deep_nets/rematerialization/1, /mlsys/checkmate_breaking_the_memory/rematerialization/2}.


SAR \cite{arxiv_sar} draws on the idea of activation rematerialization and proposes sequential aggregation and rematerialization for distributed GNN training.
The specific execution flow is as follows.
In forward propagation, each computing node only receives activation from one other computing node at a time.
After the aggregation operation is completed, the activation is removed immediately.
Then the computing node receives the activation from the next computing node and continues the aggregation operation.
This makes the activation of each vertex only exist in the computing node where it is located, and there will be no replicas.
In backward propagation, the computation is also performed sequentially as above.
Each computing node transmits activation sequentially to complete the computation.
Through this method, memory will not overflow as long as the memory capacity of the computing node is larger than the size of two subgraphs.
This allows SAR to scale to arbitrarily large graphs by simply adding more workers.





\section{Distributed Mini-batch Training}\label{sec:dmt}

\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=4, width=0.99\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{GNN distributed mini-batch training: (a) Categories of GNN distributed mini-batch training; (b) Illustration of individual-sample-based execution; (c) Illustration of joint-sample-based execution.}
    \label{fig:03_dmt}
   
\end{figure*}




This section describes GNN distributed mini-batch training in detail.
Our taxonomy classifies it into two categories according to whether the sampling and
model computation are decoupled, namely individual-sample-based execution and joint-sample-based execution, as illustrated in Fig. \ref{fig:03_dmt} (a).



\subsection{Individual-sample-based Execution} \label{sec:dmt:sample_individual_execution}

The individual-sample-based execution of distributed mini-batch training is illustrated in Fig. \ref{fig:03_dmt} (b).
Its workflow, computational pattern, communication pattern, and optimization techniques are introduced in detail as follows.

\subsubsection{Workflow}


The individual-sample-based execution involves multiple samplers and workers so that it decouples sampling from the model computation.
The sampler first samples the graph data to generate a mini-batch, and then sends the generated mini-batch to the workers.
The worker performs the computation of the mini-batch and conducts gradient synchronization with other workers to update the model parameters.
By providing enough computing resources for the samplers to prepare mini-batches for the workers, the computation can be performed without stalls.




A more detailed description of the workflow follows.
First, the samplers generate mini-batches by querying the graph structure.
Since each worker requires one mini-batch per round of training, the samplers need to generate enough mini-batches in time.
These mini-batches are transferred to the workers for subsequent computations.
The workers perform forward propagation and backward propagation on their own received mini-batch and generate gradients.
After that, gradient synchronization is conducted between workers to update model parameters.



\subsubsection{Computational Pattern}



The computational pattern in the individual-sample-based execution is dominated by the computation of the sampler and the workers, which are responsible for the sampling phase and other computational phases respectively.
The sampling phase relies on the graph structure, which leads to irregularities in the computation.
These irregularities are reflected in the uncertainty of the data, including its amount and storage address, making it difficult to estimate the computational efficiency of the samplers, as well as the efficiency of mini-batch generation.
After that, the sampler sends the mini-batches to the workers, which perform model computation on the batches.
In contrast to sampling, the computational efficiency of workers is easy to estimate, since the amount of data and computation between mini-batches are similar.
In addition, since the size of the GNN model is small, the gradient synchronization overhead is also small, which makes it generally not a bottleneck \cite{ia3_distdgl, socc_pagraph}.
As a result, the difference in the computational pattern between the samplers and workers makes the generation of mini-batch and the balance of consumption the focus of attention.
The key optimization point is to accelerate the sampling process, so that it provides enough mini-batches in time to avoid stalls.







\subsubsection{Communication Pattern}

The main communication of individual-sample-based execution is the mini-batch transmission between samplers and workers, which is characterized by regular but frequent.
Since the mini-batch consists of a fixed number of target vertices and their limited neighbors, the amount of data is consistent and small.
In addition, its transmission target is determined.
This makes the transmission regular.
Due to the small amount of data in the mini-batch, the amount of computation is also small and it is easy to estimate the time cost required for computation.
Due to the continuous consumption of mini-batches by workers, frequent mini-batch transfers are required for maintaining a timely supply of mini-batches.


\subsubsection{Optimization Techniques}


Here we introduce the optimization techniques used to generate mini-batch, balance workload, reduce transmission, and exploit parallelism for individual-sample-based execution in detail.
We classify them into four categories: \blackcircled{1} Parallel Mini-batch Generation, \blackcircled{2} Dynamic Mini-batch Allocation, \blackcircled{3} Mini-batch Transmission Pipelining, and \blackcircled{4} Parallel Aggregation with Edge Partitioning.
A summary for these categories is shown in Table \ref{table:summary_of_sample_individual_execution}.



\begin{table*}[hbtp]
   
 \caption{Summary of various categories of optimization techniques used in individual-sample-based execution of distributed mini-batch training.} \label{table:summary_of_sample_individual_execution}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{1\textwidth}{!}{
\begin{tabular}{|l|cccc|}
\hline
\textbf{Optimization Technique}     
& \textbf{Function} & \textbf{Operation Object}  & \textbf{Focus}  & \textbf{Related Work}\\ \hline \hline

\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}\blackcircled{1} Parallel Mini-batch Generation\end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Mini-batch Generation   \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Generation Operation  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Generation Parallel Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  SALIENT \cite{arxiv_salient}, \\AGL \cite{pvldb_agl}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{2} Dynamic Mini-batch Allocation  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Workload Balance  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Mini-batch  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Mini-batch Allocation Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   SALIENT \cite{arxiv_salient}, \\AGL \cite{pvldb_agl}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{3} Mini-batch Transmission Pipelining  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Reduction  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Operation  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  SALIENT \cite{arxiv_salient}, \\AGL \cite{pvldb_agl}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{4} Parallel Aggregation with Edge Partitioning  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Parallelism Exploitation  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Aggregation Operation  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Computation Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  AGL \cite{pvldb_agl}  \end{tabular}}  \\
    &   &   &   &   \\ \hline

\end{tabular}
    }
\end{table*}




\textbf{\blackcircled{1} Parallel Mini-batch Generation.}
Parallel mini-batch Generation refers to parallelizing the generation of mini-batches to reduce the waiting time of the workers for mini-batches. It aims to speed up the sampling to provide the workers with sufficient mini-batches in time.
As mentioned before, the computational pattern of the sampling is irregular, which is hard to be efficiently performed by GPUs.
Therefore, CPUs are generally used to perform sampling \cite{cluster_2pgraph, socc_pagraph}.
A widely-used solution is to parallelize the generation of mini-batches by using CPUs' multi-thread design.


SALIENT \cite{arxiv_salient} parallelizes mini-batch generation by using the multi-thread technology of CPUs.
It uses C++ threads to end-to-end implement mini-batch generation rather than Python threads to avoid Python's global interpreter lock, and thus improves the performance of mini-batch generation.


AGL \cite{pvldb_agl}, on the other hand, generates $k$-hop neighborhoods of vertices through preprocessing to simplify and speed up the generation of mini-batches.
Here, the $k$-hop neighborhoods are the vertices that can be visited within the maximum $k$ edges by the given vertex.
AGL proposes a distributed pipeline to generate $k$-hop neighborhoods of each vertex based on message passing, and implements it with MapReduce infrastructure \cite{/mapreduce/}.
The generated $k$-hop neighborhoods information is stored in the distributed file system.
Since it is only necessary to collect the $k$-hop neighborhoods information of the target vertices when a mini-batch is required, such a design greatly accelerates the sampling process.
In order to limit the size of $k$-hop neighborhoods, AGL implements a set of sampling strategies to selectively collect neighbors.


\textbf{\blackcircled{2} Dynamic Mini-batch Allocation.}
In dynamic mini-batch allocation, mini-batches are dynamically allocated to the workers to ensure that each computing node has mini-batch supply in time and alleviate workload imbalance.
Usually, a well-designed allocator is used to collect the mini-batch generated by the samplers, and then supply the mini-batch in time according to the needs of the workers.
In this way, the performance of sampling is determined by the efficiency of all samplers, instead of the slowest sampler.
This can effectively avoid the situation that the computation is stalled due to the long sampling time of some slow samplers.



Meanwhile, dynamic mini-batch allocation helps to alleviate workload imbalance.
Traditionally, the mini-batch static allocation is that each worker has one or several corresponding samplers, and its sampler is responsible for sampling and transferring mini-batches to it.
Due to the irregular computational pattern of sampling, the computing time of a sampler is difficult to estimate, and it may lead to serious workload imbalance in static allocation, as the workers corresponding to some slow samplers have to wait for their mini-batches.
In contrast, dynamic mini-batch allocation uniformly manages the workload and dispatches mini-batches to workers in time, thereby avoiding workload imbalance and achieving better performance.



SALIENT \cite{arxiv_salient} implements dynamic mini-batch allocation by using a lock-free input queue.
CPU responsible for sampling and GPU responsible for model computation are not in a static correspondence.
The number of each worker is sequentially stored in the queue.
The mini-batch generated by each CPU will be assigned a destination worker number according to the number stored in the queue during the generation.
After the generation, the mini-batch will be sent to the corresponding worker according to the destination number immediately.
The lock-free input queue is a simple design that effectively avoids the problem faced by static allocation.





\textbf{\blackcircled{3} Mini-batch Transmission Pipelining.}
Mini-batch transmission pipelining refers to pipelining the transmission of mini-batches and the model computation to reduce the overhead of data transmission.

Due to the decoupled nature of sampling and model computation in individual-sample-based execution, mini-batches need to be transferred from samplers to workers.
The overhead of the transmission is high and even occupies up to 35\% of the per-epoch time \cite{arxiv_salient}.
Fortunately, the mini-batch transmission and model computation do not require strict sequential execution.
Thus, the mini-batch transmission and model computation pipelining can be implemented to reduce the mini-batch transmission overhead.
This reduces the occurrence of worker stagnation due to the failure of the mini-batch to be supplied in time.

In SALIENT \cite{arxiv_salient}, the samplers are CPUs and the workers are GPUs, so mini-batches need to be transferred from CPUs to GPUs.
To pipeline mini-batch transmission and model computation, it uses different GPU threads to deal with each of them respectively.
AGL \cite{pvldb_agl} uses the idea of pipelining to reduce the data transmission too.



\begin{comment}
\textbf{\blackcircled{4} Asynchronous Mini-batch Training.}
\todo{huge problem -- ley 1009}
Asynchronous mini-batch training refers to training multiple versions of model parameters asynchronously, so as to remove the synchronous barrier for the update of model parameters.
It helps reduce the time that workers wait for each other.

Synchronous training is the common training strategy in individual-sample-based execution as it guarantees convergence and final accuracy, but it is easy to face performance degradation.
It requires all workers to perform gradient synchronization after completing one round of training.
The barrier effect of synchronization results in all workers waiting for the slowest worker in the system before processing the next mini-batch, causing performance degradation.
As mentioned earlier, the workload imbalance is severe in distributed GNN training, making this problem even worse.

Compared with synchronous training, asynchronous training can avoid the stagnation of computing nodes caused by waiting for each other. The current asynchronous training on individual-sample-based execution mainly follows the way of stale asynchronous training using a parameter server. 
For example, AGL \cite{pvldb_agl} uses a multi-version parameter management to enable asynchronous mini-batches training. A parameter server is set up to hold multiple versions of model parameters. This server sends the latest version of model parameters to the workers and receives the gradients from them to update the model parameters.
In this way, each worker does not need to wait for other workers to update the only one version of model parameters, thereby improving the computational efficiency.
\end{comment}




\textbf{\blackcircled{4} Parallel Aggregation with Edge Partitioning.}
Parallel aggregation with edge partitioning refers to partitioning the edges in mini-batches according to their destination vertices and assigning each partition to an individual thread to accomplish aggregation in parallel. 

For the Aggregation operation of GNNs, the neighboring vertex's feature needs to be aggregated for each vertex.
It means the computation is actually determined by the edges.
AGL \cite{pvldb_agl} proposes edge partitioning techniques to accomplish parallel aggregation according to this property.
In each mini-batch, AGL partitions the edges into several partitions according to their destination vertices ensuring that the edges with the same destination vertex are in the same partition.
Then these partitions are handled by multiple threads independently.
As there are no data conflicts between these threads, the Aggregation operation can be accomplished effectively in parallel.
In addition, the workload balance between these threads is guaranteed.
It is because the mini-batch generated by sampling ensures that each vertex has a similar number of neighboring vertex, resulting in a similar number of edges per edge partition. 


\subsection{Joint-sample-based Execution} \label{sec:dmt:sample_joint_execution}

The joint-sample-based execution of distributed mini-batch training is illustrated in Fig. \ref{fig:03_dmt} (c). Its workflow, computational pattern, communication pattern, and optimization techniques are introduced in detail as follows.

\subsubsection{Workflow}
In the joint-sample-based execution, multiple collaborative workers are used to perform training.
The graph is split into subgraphs through the partition in the preprocessing. 
Each worker holds one subgraph and a replica of the model parameters.
The workers sample their own subgraphs to generate mini-batches and perform forward propagation as well as backward propagation on the mini-batches to obtain gradients.
Then they update the model synchronously through communication with other workers.




A more detailed description of the workflow follows.
First, in order to make the computation of each worker more independent, a well-design graph partition algorithm is used to split the original graph into multiple subgraphs in the preprocessing.
Each subgraph is assigned to a worker, and the worker samples its local subgraph, which means the target vertex chosen for sampling is chosen only from its own subgraph.
However, the worker may need to query other workers for the neighborhoods of target vertices in the sampling. 
Second, the worker performs model computation on the mini-batch generated by itself.
Through forward and backward propagation, each worker produces gradients and conducts gradient synchronization together to update model parameters.
Note that the sampling and model computation is conducted on a single worker.
This feature makes the computation of each computing node more independent, which greatly reduces the demand for data transmission.


\subsubsection{Computational Pattern}

In the joint-sample-based execution, the computation of each computing node is relatively independent.
The computation of each computing node includes two parts: sampling and model computation.
In addition, gradient synchronization between computing nodes is required for updating model parameters.
In the sampling phase, each computing node mainly uses its own local data, and there may be a need to access remote data for neighbor information of vertices.
The mini-batch generated by sampling is directly consumed by itself for model computation.
For such a computing pattern, the main concern is how to make the computation of computing nodes more independent, so as to obtain better performance.

\subsubsection{Communication Pattern}

There are three communication requirements in joint-sample-based execution, each with a different communication pattern.
The first exists in the sampling phase, and its communication pattern is irregular.
In the joint-sample-based execution, each computing node selects the target vertices of the mini-batch from its own subgraph.
Then the computing node needs to sample the neighbors of these target vertices.
Since the graph is partitioned, it may be necessary to query other computing nodes to obtain the neighbor information of these target vertices \cite{ia3_distdgl}.
As the communication is determined by the graph structure and the graph itself has an irregular connection pattern, its communication pattern is irregular.



The second communication requirement is in the gradient synchronization phase.
After sampling and model computation, the computing nodes need to synchronize to update the model parameters.
Unlike DNNs, the size of model parameters of GNNs is much smaller, since GNNs have few layers and share weights across all vertices.
As a result, it is expected that the gradient synchronization phase occupies a small part of the execution time \cite{socc_pagraph, ia3_distdgl}.
However, synchronization with the nature of a fence requires all computing nodes to complete the computation before it can start, so it is highly sensitive to workload imbalance.
The low performance of a single computing node will cause other computing nodes to wait, which will result in a large time overhead for this part of the communication \cite{/cal22/linhaiyang/characterizing_and_gnn/}.




The third communication requirement only arises when the sampling and model computation of a single worker are performed on different computing components, such as CPUs and GPUs on a single server \cite{socc_pagraph, cluster_2pgraph}.
Its communication pattern is regular but with high redundancy.
The existence of the same vertex in different mini-batches is called inter-mini-batch redundancy, which leads to wasted transmission.
This redundancy is exacerbated by the fact that each computing node in the joint-sample-based execution mainly samples on its own subgraph: compared to the sampling on the entire graph, the sampling on the same subgraph exhibits a higher probability of sampling the same vertices for different mini-batches \cite{socc_pagraph}. 
As a result, reducing transmission overhead by eliminating this redundancy is an effective optimization point.




\subsubsection{Optimization Techniques}




Here we introduce the optimization techniques used to reduce transmission overhead and waiting overhead for joint-sample-based execution in detail.
We categorize them into four categories, including 
\blackcircled{1} Locality-aware Partition, \blackcircled{2} Partition with Overlap, \blackcircled{3} Independent Execution with Refinement, and \blackcircled{4} Frequently-used Data Caching.
A summary for these categories is shown in Table \ref{table:summary_of_sample_joint_execution}.


\begin{table*}[hbtp]
   
 \caption{Summary of various categories of optimization techniques used in joint-sample-based execution of distributed mini-batch training.} \label{table:summary_of_sample_joint_execution}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{1\textwidth}{!}{
\begin{tabular}{|l|cccc|}
\hline
\textbf{Optimization Technique}     
& \textbf{Function}  & \textbf{Operation Object} & \textbf{Focus} & \textbf{Related Work}\\ \hline \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{1} Locality-aware Partition  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Transmission Reduction \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Entire Graph \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   Graph Partition Strategy \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   PaGraph \cite{socc_pagraph}, 2PGraph \cite{cluster_2pgraph}, \\DistDGL \cite{ia3_distdgl}, AliGraph \cite{pvldb_aligraph}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{2} Partition with Overlap  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Reduction  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Neighboring Vertices  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Duplicate Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  PaGraph \cite{socc_pagraph}, 2PGraph \cite{cluster_2pgraph}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{3} Independent Execution with Refinement  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Waiting Time Reduction  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Computing Fashion  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Computing Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  LLCG \cite{arxiv_llcg}  \end{tabular}}  \\
    &   &   &   &   \\ \hline
\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}   \blackcircled{4} Frequently-used Data Caching  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Transmission Reduction  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Frequently-used Data  \end{tabular}} 
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  Caching Strategy  \end{tabular}}  
&\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}  AliGraph \cite{pvldb_aligraph}, PaGraph \cite{socc_pagraph}, \\2PGraph \cite{cluster_2pgraph}  \end{tabular}}  \\
    &   &   &   &   \\ \hline


\end{tabular}
    }
\end{table*}





\textbf{ \blackcircled{1} Locality-aware Partition.}
Locality-aware partition refers to partitioning the graph into subgraphs with good locality, that is, vertices and their neighbors have a high probability to be in the same subgraph, so most of the data required for sampling is local to the computing node.
This partition is conducted in the preprocessing phase.



Locality-aware partition aims to make the computation of the nodes more independent by reducing the communication between them.
According to the workflow of mini-batch training, the model computation is restricted in using the mini-batch data and does not involve access to the entire raw graph data.
That means the access to the raw graph data is almost completely in the sampling phase.
By focusing on the locality of the graph, each vertex and its neighbors are clustered into a subgraph as much as possible.
This makes the workers mainly access their own subgraph during the sampling phase, reducing the remote queries of neighboring vertices, and thus improving the independence of each worker's computation.



The graph partition here is very different from the one of distributed full-batch training mentioned earlier in the paper, which is mainly reflected in its purpose.
The graph partition in the preset-workload-based execution of distributed full-batch training focuses more on workload balance due to its significant impact on performance.
Because a large amount of information of the subgraph is related to the execution time, it is necessary to take various factors into account to guide the graph partition, such as the numbers of vertices and edges.
In contrast, workload balance is not the critical issue for graph partition in distributed mini-batch training.
Because the computation amount of the subgraph is mainly determined by the number of target vertices contained in it, it is only necessary to ensure that the number of target vertices in each subgraph tends to be consistent, which is simple but effective.
Such characteristics cause the two graph partitions to be quite different, which in turn leads to different techniques used.



To implement locality-aware partition, PaGraph \cite{socc_pagraph} proposes a formula to guide the graph partition.
Its partition algorithm scans the whole target vertex set, and iteratively assigns the scanned vertex to one of $K$ partitions according to the score computed from the formula:
\begin{equation}\label{eq4_pagraph_score} 
    score_{v_t}^{(i)} = |TV_i \cap IN(V_t)|\cdot\frac{(TV_{avg}-|TV_i|)}{|PV_i|}
\end{equation}
where $TV_i$ denotes the train vertex set already assigned to the $i$-th partition, $IN(V_t)$ denotes the $L$-hop ($L$ is the layer number of GNN model) incoming neighbor set of the target vertex $v_t$, and $PV_i$ denotes the total number of vertices in the $i$-th partition.
$TV_{avg}$ denotes the expected number of target vertices in the final $i$-th partition, which is typically set as the total number of vertices $|TV_i|$ divided by the partition number $K$ for workload balance. 
This formula fully considers the distribution of the vertices' neighbors when splitting them into each subgraph, thus making great use of the locality of the graph.


Other researches mainly use existing graph partition algorithms to harvest the locality of the graph.
2PGraph \cite{cluster_2pgraph} uses cluster-based graph partition algorithm \cite{/siamsc/a_fast_and_high_quality/distdgl_metis/2pgraph_partition_algorithm1/, /pami/weighted_graph_cuts/2pgraph_partition_algorithm2/} in its graph partition.
DistDGL \cite{ia3_distdgl} takes advantage of the multi-constraint mechanism in METIS \cite{/siamsc/a_fast_and_high_quality/distdgl_metis/2pgraph_partition_algorithm1/} for graph partition.
AliGraph \cite{pvldb_aligraph} implements four graph partition algorithms in its system and suggests that the four algorithms are suitable for different circumstances.
They are METIS \cite{metis/dgcl_partition_algorithm} for processing sparse graphs, vertex and edge cut partitions \cite{/osdi/powergraph/aligraph_graph_partition_2/} for processing dense graphs, 2-D partition \cite{/sc/scalable_matrix_computations/aligraph_graph_partition_3/} for systems with a fixed number of workers, and streaming-style partition strategy \cite{/kdd/streaming_graph_partitioning/aligraph_graph_partition_4/} for graphs with frequently edge updates.


\begin{figure*}[hbtp]
    \vspace{5pt}
    \centering
    \includegraphics[page=7, width=0.6\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Illustration of graph partition with overlap: (a) Graph partition with non-overlap where no duplicate method is used; (b) Graph partition with overlap. The duplicate range is 1-hop neighbors. 
    The vertices in white are original target vertices, while the vertices in grey are duplicated, referred to as mirror vertices.
    }
    \label{fig:06_overlap}
    \vspace{5pt}
\end{figure*}


\textbf{\blackcircled{2} Partition with Overlap.}
Partition with overlap refers to duplicating the neighboring vertices of the target vertex when partitioning the graph, thereby reducing or even completely eliminating the data transmission between computing nodes in the sampling phase.


For comparison, we first review the general graph partitioning method used in traditional graph analytics, i.e., partition with non-overlap which means no duplicate method is used.
An example of partition with non-overlap is demonstrated in Fig. \ref{fig:06_overlap} (a).
The original graph is split into two subgraphs, denoted as A and B.
The vertices held by each subgraph are disjoint.
This has the benefit of linearly reducing the requirement of memory capacity when training large graphs.
In the case of $n$ workers, each worker only needs to hold $1/n$ of the original graph data.
However, partition with non-overlap causes some vertices' neighbors to be stored in remote workers, resulting in the need for remote queries during the sampling phase.
Intensive transmissions would lead to inefficiencies in the parallel execution of distributed training.

To reduce the amount of transmission in the sampling phase, partition with overlap is proposed.
An example of partition with overlap is illustrated in Fig. \ref{fig:06_overlap} (b), whose duplicate range is 1-hop neighbors.
The original graph is split into two subgraphs with duplicate vertices.
Vertex 2 and 7 are duplicated as they are the 1-hop neighboring vertex of target vertices in subgraph A.
This method takes advantage of the characteristics of GNN mini-batch training.
When the mini-batch is sampled, only the $L$-hop neighboring vertices of the target vertices are needed, where $L$ is the number of GNN layers.
Therefore, by duplicating the features of its neighboring vertices, the transmission overhead in the sampling phase can be reduced.
These duplicate vertices are regarded as mirror vertices, which do not participate in training as target vertices \cite{/osdi/powergraph/aligraph_graph_partition_2/}. 
If the $L$-hop neighbors are fully duplicated, the transmission requirements during the sampling phase can be completely eliminated.
Note that duplicating more vertices causes an increase in the memory capacity requirements of the computing nodes, so there is a trade-off in how many neighboring vertices are duplicated.


Both PaGraph \cite{socc_pagraph} and 2PGraph \cite{cluster_2pgraph} use this method to make the computation of each worker more independent. 
DGCL \cite{eurosys_dgcl} defines a replication factor, which is computed from the total number of vertices (including the original and mirror vertices) kept by all workers divided by the number of vertices in the original graph.
In its experiments, for the dense Reddit dataset \cite{nips_inductive_representation_ley_graphsage_minibatch} with 16 GPU workers and 2-hop duplicate range, the replication factor reach 15.
In contrast, for the sparser Web-Google dataset \cite{/im/community_structure_in_large/web_google/dgcl_dataset} with the same setting, the replication factor is much smaller which is 2.5. 
It suggests that sparse graphs are more suitable for the duplicate method as they have less memory capacity overhead.




\textbf{\blackcircled{3} Independent Execution with Refinement.}
Independent execution with refinement refers to letting each worker compute and update the model parameters independently, and then periodically averages the model parameters using additional refine operation to release the potential of parallel computation while ensuring high accuracy.

Although the workers of joint-sample-based execution mainly perform computations on their own local subgraph, there are still interactions between them to advance the training process, including the sampling phase and the gradient synchronization phase.
The limitations of these two phases cause each worker's execution to be affected by the state of other workers, resulting in idle wait time.

In order to achieve more independent computation of each computing node, LLCG \cite{arxiv_llcg} proposes a method of independent execution with refinement.
In its implementation, each worker first performs sampling and corresponding model computation independently on their own subgraphs.
That is to say, the data of remote workers is not accessed at all, and each worker only updates its own model parameters locally.
A parameter server then periodically collects the model parameters from each worker, and performs the average operation of the parameters.
Finally, the parameter server refines the average result, that is, it samples the mini-batch on the whole graph and conducts model computation to update the model parameters of every worker. 
This is due to the fact that each worker lacks the structural information of the whole graph, which may lead to low accuracy. 
Through this method, the computation of each worker is more independent while the refinement on model parameters ensures the high accuracy of GNN model.



\textbf{\blackcircled{4} Frequently-used Data Caching.}
Frequently-used data caching refers to caching the information of frequently used vertices from other computing nodes, including neighbors or features, to reduce the overhead of data transmission.

To reduce the transmission overhead of obtaining the neighboring vertices in the sampling phase, AliGraph \cite{pvldb_aligraph} proposes to cache the outgoing neighbors of important vertices wherever important vertices are located.
Important vertices are identified by the following formula.
\begin{equation}\label{eq_important_vertice}
    Imp^k(v) = \frac{Nin^k(v)}{Nout^k(v)} > U^k
   
\end{equation}
where $Imp^k(v)$ denotes the importance score of the vertex v, $Nin^k(v)$ and $Nout^k(v)$ represents the number of $k$-hop incoming and outgoing neighbors of the vertex $v$, and $U^k$ is a user-specified threshold.
When the $Imp^k(v)$ exceeds $U^k$, the vertex $v$ is considered to be an important vertex.
By caching the outgoing neighbors of important vertex $v$, the transmission overhead derived from the queries of other vertices via $v$ can be reduced.


Similarly, the frequently-used data caching technique can also reduce the transmission of mini-batches between CPUs and GPUs.
It is the third communication requirement of joint-sample-based execution which occurs when CPUs and GPUs are responsible for sampling and model computation respectively.
Due to the benefit of mini-batch training, each GPU only needs to load one mini-batch of data per round of computation, and it is possible to load cached data into the free memory during model computation.
Thus, by caching node features and combining them into mini-batches on GPUs, the amount of mini-batch transmission can be reduced.


PaGraph \cite{socc_pagraph} uses a very simple caching strategy.
It sorts vertices according to their degree from largest to smallest and then caches them in order, where the degree is the number of incoming edges of a vertex.
The higher the degree, the higher the cache priority.
This is a simple but effective method: when a vertex has a larger degree, this vertex is more likely to be a neighbor of other target vertices.
As for the proportion of cached vertices, it is determined by measuring the free memory capacity of GPUs during the pre-run.
2PGraph \cite{cluster_2pgraph} proposes GNN Layer-aware Caching.
It adopts a sampling method that uses a fixed order of target vertices, which allows it to schedule the vertices to train next.
By pre-caching all of the target vertices' $L$-hop neighbors into GPU memory before the computation, the time overhead of data transmission can be almost completely eliminated.
However, fixing the order of target vertices may compromise the model accuracy, so it proposes to periodically permute the order to reduce this effect.








\section{Software Frameworks for \\ Distributed GNN Training}\label{sec:software_framework}


\begin{table*}[hbtp]
 \caption{Software frameworks for distributed GNN training.} \label{table:framework}
 
 \centering
 \renewcommand\arraystretch{1.8} 
    \resizebox{1\textwidth}{!}{
\begin{tabular}{|c|cccccccc|}
\hline
\multicolumn{1}{|c|}{\multirow{2}{*}{\textbf{Name}}}    &\multirow{2}{*}{\textbf{Multi-CPU}}  &\multirow{2}{*}{\textbf{Multi-GPU}}   &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Distributed\\Mini-batch Training\end{tabular}}} &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Distributed\\Full-batch Training\end{tabular}}}  &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Homogeneous\\Graph\end{tabular}}} &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Heterogeneous\\Graph\end{tabular}}} &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Static\\Graph\end{tabular}}} &\textbf{\multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Dynamic\\Graph\end{tabular}}}\\
\multicolumn{1}{|c|}{} & & & & & & & & \\ \hline \hline
             PyG \cite{arxiv_pyg}       &\checkmark   &\checkmark   &\checkmark   &\checkmark  &\checkmark &\checkmark  &\checkmark  &\checkmark   \\\hline
             DGL \cite{arxiv_dgl}      &\checkmark   &\checkmark   &\checkmark   &\checkmark  &\checkmark &\checkmark   &\checkmark &\checkmark   \\\hline
             NeuGraph \cite{atc_neugraph}      &   &\checkmark   &   &\checkmark &\checkmark  &   &\checkmark &   \\\hline
             Roc \cite{mlsys_roc}      &   &\checkmark   &   &\checkmark  &\checkmark &   &\checkmark &   \\\hline
            
             FlexGraph \cite{eurosys_flexgraph}      &\checkmark   &   &   &\checkmark  &\checkmark &\checkmark   &\checkmark &   \\\hline
             MG-GCN \cite{arxiv_mg_gcn}      &   &\checkmark   &   &\checkmark &\checkmark  &   &\checkmark &   \\\hline
             Dorylus \cite{osdi_dorylus}       &\checkmark   &   &   &\checkmark  &\checkmark &   &\checkmark &   \\\hline
             AliGraph \cite{pvldb_aligraph}     &\checkmark   &   &\checkmark   & &\checkmark  &\checkmark   &\checkmark &\checkmark   \\\hline
             AGL \cite{pvldb_agl}      &\checkmark   &   &\checkmark   & &\checkmark  &   &\checkmark &   \\\hline
            
             GraphTheta \cite{arxiv_graphtheta}      &\checkmark   &   &\checkmark   &\checkmark &\checkmark  &   &\checkmark &   \\
\hline 
\end{tabular}
    }
\end{table*}



In this section, we introduce the software frameworks of distributed GNN training. 
Table \ref{table:framework} provides a summary of these frameworks and their supported attributes.

\textbf{Basic Software Frameworks.} PyG \cite{arxiv_pyg} and DGL \cite{arxiv_dgl} are the two most popular software frameworks in the GNN community.
PyG \cite{arxiv_pyg} is a geometric deep learning extension library for PyTorch to enable deep learning on irregular structure data such as graphs.
It supports both CPU and GPU computing, providing convenience for using GPU to accelerate the computing process.
Through the message-passing application programming interface (API), it is easy to express various GNN models, as neighbor aggregation is a kind of message propagation.
DGL \cite{arxiv_dgl} is a framework specialized for deep learning models on graphs.
It abstracts the computation of GNNs into a few user-configurable message passing primitives, thus helping users express GNNs more conveniently.
It achieves good performance by exploring a wide range of parallelization strategies.
It also supports both CPU and GPU computing.


Due to their open source and easy-to-use nature, more and more software frameworks are building on top of them and propose optimizations for distributed GNN training, such as DistGNN \cite{sc_distgnn}, SAR \cite{arxiv_sar}, DistDGL \cite{ia3_distdgl}, PaGraph \cite{socc_pagraph}, LLCG \cite{arxiv_llcg}, DistDGLv2 \cite{arxiv_distdglv2}, SALIENT \cite{arxiv_salient}, P3 \cite{pvldb_g3}, and so on.
Next, we introduce the software frameworks dedicated to distributed full-batch training and distributed mini-batch training.

\textbf{Software Frameworks Dedicated to Distributed Full-batch Training.}
The software frameworks dedicated to distributed full-batch training includes NeuGraph \cite{atc_neugraph}, Roc \cite{mlsys_roc}, FlexGraph \cite{eurosys_flexgraph}, MG-GCN \cite{arxiv_mg_gcn}, and Dorylus \cite{osdi_dorylus}.


NeuGraph \cite{atc_neugraph} is a distributed GNN training software framework proposed in 2019, using multi-GPU hardware platform.
It is categorized as the dispatch-workload-based execution of distributed full-batch training.
It proposes SAGA-NN, an abstract model for the programming of GNN operations which splits each layer of model computation into four stages: Scatter, ApplyEdge, Gather, and ApplyVertex.
SAGA-NN is named after these stages.
The Scatter stage means the vertices scatter their features to their output edges, while the Gather stage means the vertices gather the value from their input edges.
There are two user-defined functions used in the ApplyEdge stage and ApplyVertex stage, for users to declare neural network computations on edges and vertices respectively.
Through the abstraction of SAGA-NN, users can easily express various GNN models and execute them in a parallelized way.
NeuGraph optimizes the training process based on this abstract model, using techniques including vertex-centric workload partition, transmission planning, and feature-dimension workload partition.



Roc \cite{mlsys_roc} is a distributed multi-GPU software framework for fast GNN training and inference, proposed in 2020.
It is categorized as the dispatch-workload-based execution of distributed full-batch training.
Its optimization of distributed training mainly focuses on balanced workload generation and transmission planning.
In terms of balanced workload generation, an online linear regression cost model is proposed to achieve efficient graph partition. The cost model is being tuned by collecting runtime data.
According to this cost model, the training resources and time required for the subgraph can be estimated to guide the workload partition for workload balance.
In terms of transmission planning, a recursive dynamic programming algorithm is introduced to find the global optimal solution to decide which part of the data should be cached in GPU memory for reuse.





FlexGraph \cite{eurosys_flexgraph} is a distributed multi-CPU training software framework proposed in 2021.
It is categorized as the preset-workload-based execution of distributed full-batch training.
In order to express more kinds of GNNs including GNNs for heterogeneous graphs, it proposes a novel programming abstraction, namely NAU.
NAU splits the computation of one GNN layer into three stages including NeighborSelection, Aggregation, and Update stages, each with a user-defined function.
Based on NAU, FlexGraph optimizes the training process using techniques including graph pre-partition and partial aggregation.
In terms of graph pre-partition, it introduces a cost model to estimate the runtime overhead of the workload, so as to guide the workload partition for workload balance.
In terms of partial aggregation, FlexGraph partially aggregates the features of vertices collocated at the same partition when possible.
In addition, it overlaps partial aggregations and communication to reduce the transmission overhead.




MG-GCN \cite{arxiv_mg_gcn} is a distributed multi-GPU training software framework proposed in 2021.
It is categorized as the preset-workload-based execution of distributed full-batch training.
It focuses on the efficient parallelization of the sparse matrix-matrix multiplication (SpMM) kernel on multi-GPU hardware platform.
It uses matrix partitioning method to distribute raw data to multiple GPUs, and each GPU is responsible for completing the workload of its own local matrix.
It involves the efficient reuse of memory buffers to reduce the memory footprint of training GNN models, and overlaps communication and computation to reduce communication overhead.
Specifically, the memory buffer in the computing node is used to cache the data reused by the forward propagation and backward propagation, thereby reducing data transmission.
As for the communication and computation overlap, it uses two GPU streams for computation and communication, respectively.


Dorylus \cite{osdi_dorylus} is a distributed multi-CPU training software framework proposed in 2021.
It is categorized as the preset-workload-based execution of distributed full-batch training.
Its main focus is on how to train GNNs at a low cost, so it adopts serverless computing.
Serverless computing refers to ``cloud function" threads, such as AWS Lambda and Google Cloud Functions, that can be used massively in parallel at an extremely low price.
The hardware platform of Dorylus consists of CPUs and serverless threads.
CPUs mainly perform the Aggregation operation, while the serverless threads are used for the Combination operation due to more regular computation and simpler workload partition in the Combination operations.
It adopts a fine-grained workload partition to adapt to the situation that the available hardware resources of serverless threads are quite limited.
In addition, asynchronous training is used to make full use of computing resources and reduce stagnation.


\textbf{Software Frameworks Dedicated to Distributed Mini-batch Training.}
The software frameworks dedicated to distributed mini-batch training includes AliGraph \cite{pvldb_aligraph} and AGL \cite{pvldb_agl}.

AliGraph \cite{pvldb_aligraph} is a distributed multi-CPU training framework proposed in 2019.
It is categorized as the joint-sample-based execution of distributed mini-batch training.
It supports not only GNNs for homogeneous graphs and static graphs, but also GNNs for heterogeneous graphs and dynamic graphs.
In terms of storage, it adopts a graph partitioning method to store graph data in a distributed manner.
The structure and features of the subgraph in each computing node are stored separately. In addition, two caches are added for the features of vertices and edges.
Furthermore, it proposes a caching strategy to reduce the communication overhead between computing nodes, that is, each computing node caches the outgoing neighbors of frequently-used vertices.

AGL \cite{pvldb_agl} is a distributed multi-CPU training software framework proposed in 2020.
It is categorized as the individual-sample-based execution of distributed mini-batch training.
To speed up the sampling process, it introduces a distributed pipeline to generate $k$-hop neighborhood in the spirit of message passing, which is implemented with MapReduce infrastructure \cite{/mapreduce/}.
In this way, in the sampling phase, mini-batch data can be rapidly generated by collecting the $k$-hop neighbors of the target vertices.
In the training phase, the computing nodes are partitioned into workers and parameter servers.
The workers perform the model computation on the mini-batches, while the parameter servers maintain the current version of the model parameters.
It also uses the commonly used optimization techniques for better efficiency, such as the transmission pipeline.


\textbf{Software Frameworks Dedicated to Both Distributed Full-batch Training and Mini-batch Training.}
There exists a software framework dedicated to both distributed full-batch training and distributed mini-batch training.

GraphTheta \cite{arxiv_graphtheta} is a distributed multi-CPU training software framework proposed in 2021.
It supports three training methods: mini-batch, full-batch, and cluster-batch training.
The cluster-batch training methods is proposed by Chiang \cite{kdd/cluster_gcn/subgraph_based1} in 2019.
It first partitions a large graph into a set of smaller clusters.
Then, it generates a batch of data either based on one cluster or a combination of multiple clusters.
Apparently, cluster-batch restricts the neighbors of a target vertex into only one cluster, which is equivalent to conducting a globalized convolution on a cluster of vertices.
There is a parameter server in GraphTheta, which is responsible for managing multi-version model parameters.
The worker obtains the model parameters from the parameter server and transfers the generated gradient back to the parameter server for the update of model parameters.
Multi-version parameter management makes it possible to train GNNs asynchronously as well as synchronously.









\section{Hardware Platforms for \\ Distributed GNN Training}\label{sec:hardware_platform}

In this section, we introduce the hardware platforms for distributed GNN training.
At present, it is mainly categorized into two types: multi-CPU hardware platform and multi-GPU hardware platform.
A summary of the hardware platform for distributed GNN training is shown in Table \ref{table:summary_of_hardware_platform}.
Next, we introduce them separately.







\begin{figure*}[hbtp]
   
    \centering
    \includegraphics[page=5, width=0.8\textwidth]{2022_6_8_graph_for_gnn_dt.pdf}
   
    \caption{Hardware platforms for distributed GNN training: (a) Multi-CPU hardware platform; (b) Multi-GPU hardware platform.}
    \label{fig:04_hardware_platform}
   
\end{figure*}

\begin{table*}[hbtp]
   
 \caption{Summary of hardware platforms for distributed GNN training.} \label{table:summary_of_hardware_platform}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{0.98\textwidth}{!}{
\begin{tabular}{|c|ccc|}
\hline
\multicolumn{1}{|c|}{\textbf{Hardware Platform}} & \textbf{Main Advantages}                                                              & \textbf{Main Disadvantages}                                                                             & \multicolumn{1}{c|}{\textbf{Suitable Training Method}} \\ \hline
\multicolumn{1}{|c|}{\multirow{2}{*}{Multi-CPU}}                  & \multirow{2}{*}{\begin{tabular}[c]{@{}c@{}}Rich Memory Resource \\ and Good Scalability\end{tabular}} & \multirow{2}{*}{Limited Computing Resource}                                                                             & \multicolumn{1}{c|}{\multirow{2}{*}{Distributed Full-batch Training}}   \\
\multicolumn{1}{|c|}{}                                            &                                                                                                       &                                                                                                                         & \multicolumn{1}{c|}{}                                                   \\ \hline
\multicolumn{1}{|c|}{Multi-GPU}                                   & Rich Computing Resource                                                                               & \begin{tabular}[c]{@{}c@{}}Limited Memory Resource, Resource Contention, \\ and High Transmission Overhead\end{tabular} & \multicolumn{1}{c|}{Distributed Mini-batch Training}                    \\ \hline
\multicolumn{1}{l}{}                                              & \multicolumn{1}{l}{}                                                                                  & \multicolumn{1}{l}{}                                                                                                    & \multicolumn{1}{l}{}                                                   
\end{tabular}
    }
\end{table*}

\subsection{Multi-CPU Hardware Platform}\label{sec:hp:multi_cpu_hardware_platform}

The structure diagram of multi-CPU hardware platform is illustrated in Fig. \ref{fig:04_hardware_platform} (a). It is mainly composed of multiple computing nodes. Each computing node has one or multiple CPUs. CPUs in each computing node communicate with each other through the network.
The graph data is generally stored in each computing node in a distributed storage manner.
Each computing node performs computations mainly on its own local data. 
When remote data is required, it queries other computing nodes through the network to obtain the required data.

The main advantage of multi-CPU hardware platform is the good scalability due to the large memory \cite{sc_distgnn, ia3_distdgl}.
By increasing the number of computing nodes, large graphs can be maintained completely in memory.
This makes it possible to avoid data access to high-latency storage components, such as hard disks, thereby ensuring the timely supply of data.
This characteristic makes it ideal for preset-workload-based execution of distributed full-batch training \cite{sc_distgnn, eurosys_flexgraph} and joint-sample-based execution of distributed mini-batch training \cite{pvldb_aligraph, ia3_distdgl, arxiv_graphtheta}.
The graph is partitioned and distributed to different computing nodes for storage.
Each computing node is responsible for the workload of its own subgraph.
This results in computing nodes using mostly local data for computation, although additional communication is also involved.
By further optimizing the communication overhead, multi-CPU platforms can achieve good scalability.


The main disadvantage of multi-CPU hardware platform is the limited computing resource in each computing node.
CPU is a latency-oriented architecture with limited computing resources \cite{throughput_oriented_architectures}.
This makes it less friendly to neural network operations that incur a lot of computation \cite{NVIDIA_Tesla, GPU_Computing}.
This problem is even more pronounced when using distributed mini-batch training.
In this case, CPUs perform both the sampling and model computation, leading to a shortage of computing resources.




\subsection{Multi-GPU Hardware Platform}\label{sec:hp:multi_gpu_hardware_platform}
The structure diagram of multi-GPU hardware platform is illustrated in Fig. \ref{fig:04_hardware_platform} (b).
Graph data is generally stored in a distributed manner on multiple computing nodes.
Each computing node consists of CPUs and GPUs.
Computing nodes are connected through high-speed network interfaces.
For example, GPUs communicate with each other over PCIe under the same computing node and over InfiniBand across different computing nodes. GPUs can also be interconnected through NVLink and NVSwitch for higher-speed inter-GPU communication.


The main advantage of multi-GPU hardware platform is the rich computing resources.
Compared with CPUs, GPUs have more computing resources that can be used for large-scale parallel computing. 
This is because GPU is a throughput-oriented architecture which focuses on improving the throughput by using massive computing resources \cite{throughput_oriented_architectures, NVIDIA_Tesla, GPU_Computing}. 
In view of the development of DNN, both sparse matrix multiplication and dense matrix multiplication in GPU have been fully developed, which facilitates the model computation of GNN.
Due to its limited memory capacity, it is not suitable for distributed full-batch training.
Otherwise, it will result in a large amount of data transmission.
Currently, distributed mini-batch training is usually performed on multi-GPU hardware platform.
The most popular way to perform distributed mini-batch training on multi-GPU hardware platform is that CPUs are responsible for the sampling phase and GPUs are responsible for the model computation.
This is because the computational pattern of the sampling phase is irregular and CPUs are more suitable for the irregular computational pattern than GPUs \cite{Tigr, micro/alleviating_irregularity_in/yan/graphdyns/graph_processing_asic_acc}.


The main disadvantages of multi-GPU hardware platform are resource contention issues and expensive data transmission overhead.
Since there are generally multiple GPUs on a computing node, these GPUs share the computing node's resources, including CPU sampling threads and network interface \cite{/cal22/linhaiyang/characterizing_and_gnn/, atc_neugraph}.
The competition for these resources makes multiple GPUs hard to obtain sufficient input data in time.
This causes the occurrence of computational stagnation, resulting in poor scalability, manifested by a large gap between the actual speedup and the ideal \cite{/cal22/linhaiyang/characterizing_and_gnn/}.
The expensive data transmission overhead is due to the tight memory resources of GPUs.
When using a multi-GPU hardware platform for distributed full-batch training, it needs to continuously transmit input data and output data \cite{atc_neugraph}.
When performing distributed mini-batch training, it is also necessary to continuously transmit the mini-batch data sampled by CPUs \cite{socc_pagraph}.
This problem is further exacerbated when the graph is large.






\subsection{Multi-CPU Hardware Platform V.S. Multi-GPU Hardware Platform}\label{sec:hp:comparison_cpu_or_cpu}

The summary of the comparison between multi-CPU hardware platform and multi-GPU hardware platform is shown in Table \ref{table:summary_of_hardware_platform}.
Multi-CPU and multi-GPU hardware platforms have their own advantages and are suitable for different scenarios.
The different characteristics of the two also lead to different optimization directions.
Multi-CPU hardware platform is more suitable for distributed full-batch training.
The entire graph can be cached in the memory, which leads to good scalability.
Multi-GPU hardware platform is more suitable for distributed mini-batch training given its limited memory resources.
However, when the graph size is small and there are high-speed interconnections between GPUs, such as NVLink, distributed full-batch training using multi-GPU hardware platform can achieve good performance \cite{mlsys_roc}.


\section{Comparison to Distributed DNN Training}\label{sec:comparison_to_dnn}

In this section, we highlight the characteristics of distributed computing of GNNs by comparing the distributed training of GNNs with that of DNNs.
We first introduce the two categories of distributed DNN training: data parallelism and model parallelism.
Among them, for GNN distributed full-batch training, its operation mode is similar to the model parallelism of DNNs.
GNN distributed mini-batch training is similar to the data parallelism of DNNs.
The two pairs are compared separately below.
A summary of the comparison between distributed GNN training and distributed DNN training is shown in Table \ref{table:summary_of_DNN_GNN_comparison}.
Next, we introduce them separately.


\begin{table*}[hbtp]
   
 \caption{Summary of the comparison between distributed GNN training and distributed DNN training.}\label{table:summary_of_DNN_GNN_comparison}

 \centering
\renewcommand\arraystretch{1.5} 
\resizebox{0.95\textwidth}{!}{
\begin{tabular}{|c|c|cc|}
\hline
& \textbf{Comparison Object}  & \textbf{Distributed Full-batch Training}  & \textbf{DNN Model Parallelism} \\ \hline \hline
\multirow{2}{*}{\textbf{Similarity}}  
                    
                      & Perspective of Parallelism Exploitation   &  \multicolumn{2}{c|}{Model} \\ \cline{2-4}
                      & Fashion of Parallelism Exploitation   &  \multicolumn{2}{c|}{Partitioning Workload of Model Computation} \\ \hline
\multirow{4}{*}{\textbf{Difference}}    
                      & Communication Uncertainty                 & High  & Low \\  \cline{2-4}
                      & Transmission Planing Complexity          & High  & Low \\  \cline{2-4}
                      & Probability of Communication Congestion  & High  & Low \\  \cline{2-4}
                      & Probability of Computation Stagnation    & High  & Low \\  \hline
\hline
\hline
& \textbf{Comparison Object}  & \textbf{Distributed Mini-batch Training}  & \textbf{DNN Data Parallelism} \\ \hline \hline
\multirow{2}{*}{\textbf{Similarity}}  
                    
                   
                     & Perspective of Parallelism Exploitation & \multicolumn{2}{c|}{Input Data} \\ \cline{2-4}
                     & Fashion of Parallelism Exploitation    & \multicolumn{2}{c|}{Partitioning Raw Data} \\ \hline
\multirow{6}{*}{\textbf{Difference}}   
                     & Source of Input Data & Generated by Sampling Phase & Directly Loaded From Raw Data  \\ \cline{2-4}
                    
                     & Main Phase of Inter-node Communication & Sampling & Gradient Synchronization \\ \cline{2-4}
                     & Communication Uncertainty                 & High  & Low \\  \cline{2-4}
                     & Transmission Planing Complexity          & High  & Low \\  \cline{2-4}
                     & Probability of Communication Congestion  & High  & Low \\  \cline{2-4}
                     & Probability of Computation Stagnation    & High  & Low \\  \hline
\end{tabular}
    }
\end{table*}



\subsection{Brief Introduction to Distributed DNN Training}\label{sec:comparison_to_dnn:brief_intro_dnn} 

Distributed DNN training is categorized into model parallelism and data parallelism \cite{jpdc/a_hitchhiker/dnn_review}.
\textit{In model parallelism, the model is split into several parts and different computing nodes compute each part.}
AlexNet \cite{nips/imagnenet_classification/alexnet} is the first one to use model parallelism, because its model size could not fit in one GPU at that time. 
Therefore, the model is split into two parts, which are then computed by two GPUs together.


\textit{In data parallelism, each computing node holds a copy of the model parameters, and the input dataset is distributed to each computing node.
Each computing node conducts the training process completely using its own local data and uses the generated gradients to update the model parameters with other computing nodes together.}
Data parallelism is classified into synchronous training and asynchronous training. 
However, compared with synchronous distributed training, asynchronous distributed training has lower final accuracy, and sometimes non-convergence may occur \cite{jpdc/a_hitchhiker/dnn_review}. 
In synchronous distributed training, after each computing node completes one round of training on a small piece of data, the system starts to collect gradients, which are used to update the model parameters uniformly. 
In this way, each round of training in each computing node is carried out with the same model parameters, which is equivalent to the case of one computing node. 


\subsection{Distributed Full-batch Training V.S. DNN Model Parallelism}\label{sec:comparison_to_dnn:full_vs_model}


\textbf{Similarities.} Both of them distribute the workload of model computation to different computing nodes from the perspective of the model.
Each computing node needs to transfer the intermediate results of model computation to each other and cooperate to complete a round of training.
In DNN model parallelism, DNN model computation is partitioned into different parts and distributed to different computing nodes \cite{nips/imagnenet_classification/alexnet}.
Each computing node may be responsible for executing several layers of DNN, or a set of operations within each layer.
Similarly, GNN distributed full-batch training also distributes the workload of model computation to different computing nodes from the perspective of the model \cite{atc_neugraph, mlsys_roc, arxiv_mg_gcn, sc_reducint_communication_in_graph_cagnet}. 
Since the operation of GNN model computation is to operate on vertices, including the Aggregation and Combination operations, the workload is generally distributed to different computing nodes by partitioning the graph.
Each computing node is responsible for completing the Aggregation and Combination operation of its assigned vertices and communicating with other computing nodes to jointly advance the computation \cite{eurosys_dgcl, sc_distgnn, eurosys_flexgraph}.


\textbf{Differences.} DNN model parallelism has low data communication uncertainty, while GNN distributed full-batch training exhibits high data communication uncertainty.
In DNN model parallelism, most of the transmitted data is intermediate data generated in the computation.
Since the transmission of intermediate data directly affects the execution of other computing nodes, there is a strong execution dependence among computing nodes.
Due to the high certainty of data transmission in DNN model parallelism, which is reflected in the fixed data volume and transmission target, the computation and data transmission can be overlapped by reasonable planning to reduce the communication overhead.
However, in GNN distributed full-batch training, the data communication uncertainty is high.
This is because the data transmitted between each computing node is mainly the feature of the neighboring vertex needed in the Aggregation step.
Due to the irregular connection pattern of the graph itself and the fluctuation of the computational efficiency of each computing node, there are great uncertainties in data transmission \cite{eurosys_dgcl}.
Therefore, the congestion of the communication network can easily occur, which in turn leads to stagnation of computation \cite{MultiGCN}.





\subsection{Distributed Mini-batch Training V.S. DNN Data Parallelism} \label{sec:comparison_to_dnn:mini_vs_data}



\textbf{Similarities.} Both of them use small pieces of input data per round of training to update the model parameters.
The computing nodes use different small pieces of input data for computation, and then jointly update the model parameters.
In DNN data parallelism, each computing node holds a portion of the original data, typically stored in its memory.
In each round of computation, a small piece of data is taken from its own local data and computed.
Then, using the generated gradients, the model parameters are updated asynchronously or synchronously.
In GNN distributed mini-batch training, the training of each computing node also uses independent input data, that is, the mini-batch generated by sampling \cite{socc_pagraph, cluster_2pgraph}.

\textbf{Differences.} The input data required for each round of GNN distributed mini-batch training need to be generated by the sampling, while DNN data parallelism is loaded directly from memory.
In DNN data parallelism, each computing node performs computations on its own local data \cite{jpdc/a_hitchhiker/dnn_review}.
It does not need to communicate with other computing nodes except for the stage of updating model parameters.
In GNN distributed mini-batch training, a large number of communication requirements are required in the sampling phase, including querying graph data and transmitting mini-batch data.
As graphs generally exhibit an irregular connection pattern, the communication in the sampling phase is highly irregular, resulting in high communication uncertainty and planning complexity.
This leads to the fact that distributed GNN training may not be able to provide input data in time due to the inefficiency of the sampling, resulting in computational stagnation.
This makes it necessary to optimize the sampling stage to reduce the communication overhead when conducting GNN distributed mini-batch training \cite{socc_pagraph, cluster_2pgraph}.






\section{Summary and Discussion}\label{sec:summary} 





This section summarizes the aforementioned details of distributed GNN training, and discusses several interesting issues and opportunities in this field.

The main focus of optimizing distributed full-batch training is to reduce its communication overhead\cite{atc_neugraph, mlsys_roc, sc_reducint_communication_in_graph_cagnet, eurosys_dgcl, sc_distgnn, eurosys_flexgraph, osdi_dorylus}.
In this training method, each computing node inevitably needs to communicate with other nodes for information about the entire graph structure, so that it can finish operations which require graph data that are not stored in the local split, such as aggregating information of neighboring nodes which are distributed in other computing components.
As a result, reducing communication overhead, mainly by reasonably splitting the graph and planning the data transmission, can greatly improve computational efficiency.

By contrast, the main focuses of optimizing distributed mini-batch training are to speed up the sampling phase and to reduce the mini-batch transmission overhead \cite{arxiv_salient, pvldb_agl, ia3_distdgl, pvldb_aligraph, socc_pagraph, cluster_2pgraph}.
Currently, it is popular to perform distributed mini-batch training in which CPUs are responsible for sampling and GPUs are responsible for GNN model computation.
The sampling capability of CPUs is insufficient, producing a lot of idleness and limiting the utilization of GPUs due to insufficient data supply.
By accelerating sampling and optimizing data transmission, the utilization of computing components can be improved, thereby improving efficiency.

The two methods show their advantages in different aspects respectively. 
In current designs of distributed training of GNNs, the adoption of the mini-batch method is gradually increasing due to its advantages of a simpler implementation and less memory pressure.
Distributed full-batch training, on the other hand, requires programmers to put more effort into programming and design, so it is more difficult to optimize.
However, some research shows that the final precision of distributed full-batch training can be higher \cite{mlsys_roc}.

Next, we discuss several interesting issues and opportunities in this field. 

\subsection{Quantitative Analysis of Performance Bottleneck}\label{sec:summary:quantitative}

As mentioned before, the performance of distributed GNN training is primarily hindered by the workload imbalance across different computing nodes, irregular transmission between computing nodes, etc.
Although these performance bottlenecks are well-known in the GNN community, the quantitative analysis of these bottlenecks, which is important to guide the optimizations for distributed GNN training, is still obscure.

Recently, a lot of characterization efforts for GNN training or inference have been conducted on a single computing node or a single GPU~\cite{GCN_Characterization_CAL,GNN_Architectural_Implication,Characterizing_HGNNs,character_Distributed_GNN,Understanding_GNN,/mlsys/understanding_gnn_computational/gat_intermediate_data}. 
For example, Yan et al. \cite{GCN_Characterization_CAL} quantitatively disclose the computational pattern of the inference on a single GPU.
Zhang et al. \cite{GNN_Architectural_Implication} quantitatively characterize the training of a large portion of GNN variants concerning general-purpose and application-specific hardware architectures.
However, there are few characterization efforts on distributed GNN training \cite{character_Distributed_GNN}. 

Diagnosing performance issues without a quantitative understanding of the bottlenecks can cause misdiagnosis: A potentially expensive effort that involves optimizing something that is not the real problem. 
Although Lin et al. \cite{character_Distributed_GNN} quantitatively characterize the end-to-end execution of distributed GNN training, it is not enough for the long-term development of distributed GNN training. We believe that the quantitative analysis of performance bottleneck will be one of the main directions in the field of distributed GNN training. 



\subsection{Performance Benchmark} \label{sec:summary:performance_benchmark}


Despite the large quantity of performance benchmarks presented to fairly evaluate and compare the performance of software frameworks and hardware platforms for DNNs, there are few performance benchmarks for distributed GNN training. 
Most of the recent benchmarks for GNNs mainly focus on evaluating the prediction accuracy of trained GNN models.
For example, Open Graph Benchmark (OGB)~\cite{nips_open_graph_benchmark_ogbdataset} provides a set of large-scale real-world benchmark datasets to facilitate the graph machine learning research.
However, current benchmarks focus mainly on the accuracy, instead of performance.
As a result, standardized performance benchmark suites with typical, representative, and widely-acknowledged workloads are needed for the industry and academia to comprehensively compare the performance of distributed GNN training systems.

In the field of DNNs, MLperf~\cite{MLPerf_IEEE_Micro}, an industry standard benchmark suite for machine learning performance, has made a great contribution to the development of software frameworks and systems.
Therefore, we believe that performance benchmark suites for GNNs similar to MLperf are vital to drive the rapid development of GNNs.



\subsection{Distributed Training on Extreme-scale Hardware Platform}\label{sec:summary:distributed_training_on_extreme_scale}


For distributed GNN training on large-scale graphs or even extreme-scale graphs, the performance can be greatly improved by using the extreme-scale hardware platform.
The scale of the graph data has reached a staggering magnitude and is growing at an exaggerated rate.
For example, Sogou \cite{DBLP:conf/sc/LinZYTXCZHMLZX18/shentu} graph dataset has 12 trillion edges and Kronecker2 \cite{DBLP:conf/pkdd/LeskovecCKF05/kronecker} graph dataset has 70 trillion edges.
The training on graphs in this order of magnitude puts a very high requirement on the computing resources and memory resources of the computing system.
Only by using the extreme-scale hardware platform can the training task be completed in a reasonable time.
In this respect, the research of graph processing and distributed DNN training on the extreme-scale hardware platform can be used for reference.
ShenTu \cite{DBLP:conf/sc/LinZYTXCZHMLZX18/shentu} realizes processing graph with trillion edges in seconds by using petascale computing system.
It suggests that the extreme-scale hardware platform can be used to accelerate distributed GNN training, which needs to explore and establish more hardware platform support for distributed GNN training.







\subsection{Domain-specific Distributed Hardware Platform}\label{sec:summary:domain_specific}

There are many single-node domain-specific hardware platforms designed for GNNs. 
However, very few efforts are conducted on distributed hardware platforms.
Recently, many single-node domain-specific hardware accelerators designed for GNNs have achieved significant improvement in performance and efficiency compared with the single-GPU platform. 
For example, HyGCN~\cite{hpca/hygcn/gnn_asic_acc} proposes a hybrid architecture consisting of the Aggregation engine and Combination engine for the acceleration of the Aggregation operation and Combination operation respectively. Compared with NVIDIA V100 GPU, HyGCN achieves an average 6.5$\times$ speedup with 10$\times$ energy reduction, respectively.
However, the single-node platform is not sufficient to handle the rapid development of GNNs since the ever-growing scale of graphs dramatically increases the training time, generating the demand for distributed GNN hardware platform. In response to that, MultiGCN~\cite{MultiGCN} proposes a distributed hardware platform for the acceleration of GNN inference, which consists of multiple computing nodes to perform the inference in parallel. 
MultiGCN achieves 2.5$\sim$8$\times$ speedup over the state-of-the-art multi-GPU software framework. 
But only a single work is not enough.   
We have witnessed that TPU-Pod~\cite{TPU-Pod}, a domain-specific supercomputer for training DNNs, greatly accelerates the deployment of large-scale DNN models.
Therefore, we believe that a domain-specific distributed hardware platform for GNNs similar to TPU-Pod is time to present, which is vital to drive the rapid development and deployment of GNNs.


\subsection{General Communication Library for Distributed GNN Training}\label{sec:summary:general_communication}

The variety of hardware platforms and irregular communication patterns of distributed GNN training lead to strong demand for a general communication library to ease the programming effort on transmission planning while achieving high efficiency.
The communication characteristics of hardware platforms are various due to the differences in the number of computing nodes, network topology, and communication bandwidth as well as communication latency of interconnection interface.  
In order to better adapt to the various transmission requirements of distributed GNN training on various hardware platforms, it is urgent to develop a general communication library which adapts to different network topologies, as well as various interconnection interfaces of different communication bandwidths and latency, so as to ease the implementation of novel communication patterns while ensuring efficiency. 









\section{Conclusion}\label{sec:conclusion}
In this paper, we comprehensively review distributed training of GNNs.
After investigating recent efforts on distributed GNN training, we classify them in more detail according to their workflow, including the dispatch-workload-based execution as well as preset-workload-based execution of distributed full-batch training, and the individual-sample-based execution as well as joint-sample-based execution of distributed mini-batch training.
Each taxonomy's workflow, computational pattern, and communication pattern are summarized, and various optimization techniques are further introduced to facilitate the understanding of recent research status, and to enable readers to quickly build up a big picture of distributed training of GNNs.
In addition, this paper introduces the training software and hardware platforms, and then contrasts distributed GNN training with distributed DNN training.
In the end, we provide several discussions about interesting issues and opportunities of distributed GNN training.

The emergence of distributed GNN training has successfully expanded the usage of GNNs on large-scale graphs, making it a powerful tool when learning from real-world associative relations.
We optimistically look forward to new research which can further optimize this powerful tool on large-scale graph data and bring its application into the next level.




\begin{comment}




\todo{
}
\end{comment}





\section*{Acknowledgments}
This work was supported by the National Natural Science Foundation of China (Grant No. 61732018, 61872335, and 62202451), Austrian-Chinese Cooperative R\&D Project (FFG and CAS) (Grant No. 171111KYSB20200002), CAS Project for Young Scientists in Basic Research (Grant No. YSBR-029), and CAS Project for Youth Innovation Promotion Association.





\bibliographystyle{IEEEtran}
