An Experimental Comparison of Partitioning Strategies for Distributed
  Graph Neural Network Training
Recently, graph neural networks (GNNs) have gained much attention as a
growing area of deep learning capable of learning on graph-structured data.
However, the computational and memory requirements for training GNNs on
large-scale graphs make it necessary to distribute the training. A prerequisite
for distributed GNN training is to partition the input graph into smaller parts
that are distributed among multiple machines of a compute cluster. Although
graph partitioning has been studied with regard to graph analytics and graph
databases, its effect on GNN training performance is largely unexplored. As a
consequence, it is unclear whether investing computational efforts into
high-quality graph partitioning would pay off in GNN training scenarios.
  In this paper, we study the effectiveness of graph partitioning for
distributed GNN training. Our study aims to understand how different factors
such as GNN parameters, mini-batch size, graph type, features size, and
scale-out factor influence the effectiveness of graph partitioning. We conduct
experiments with two different GNN systems using vertex and edge partitioning.
We found that high-quality graph partitioning is a very effective optimization
to speed up GNN training and to reduce memory consumption. Furthermore, our
results show that invested partitioning time can quickly be amortized by
reduced GNN training time, making it a relevant optimization for most GNN
scenarios. Compared to research on distributed graph processing, our study
reveals that graph partitioning plays an even more significant role in
distributed GNN training, which motivates further research on the graph
partitioning problem.
Nikolai Merkel, Daniel Stoll, Ruben Mayer, Hans-Arno Jacobsen
# An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training

###### Abstract.

Recently, graph neural networks (GNNs) have gained much attention as a growing area of deep learning capable of learning on graph-structured data. However, the computational and memory requirements for training GNNs on large-scale graphs can exceed the capabilities of single machines or GPUs, making distributed GNN training a promising direction for large-scale GNN training. A prerequisite for distributed GNN training is to partition the input graph into smaller parts that are distributed among multiple machines of a compute cluster. Although graph partitioning has been extensively studied with regard to graph analytics and graph databases, its effect on GNN training performance is largely unexplored.

In this paper, we study the effectiveness of graph partitioning for distributed GNN training. Our study aims to understand how different factors such as GNN parameters, mini-batch size, graph type, features size, and scale-out factor influence the effectiveness of graph partitioning. We conduct experiments with two different GNN systems using vertex and edge partitioning. We found that graph partitioning is a crucial pre-processing step that can heavily reduce the training time and memory footprint. Furthermore, our results show that invested partitioning time can be amortized by reduced GNN training, making it a relevant optimization.

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: preprint: AIP/12/15

+
Footnote †: preprint: AIP/12/15
that graph partitioning is effective for GNN training, leading to speedups of up to 10.4 and reducing the memory footprint by up to 85.1%. Compared to results known from distributed graph processing, these numbers are much higher, showing the enormous potential of graph partitioning for GNN workloads.
2. We show that partitioning quality properties such as the replication factor or vertex balance can influence the GNN training a lot. We find a strong correlation between replication factor, network communication and memory footprint. Therefore, minimizing the replication factor is crucial for efficient distributed GNN training. We also show that a vertex imbalance can decrease the speedup and also leads to severe imbalances regarding memory utilization.
3. We find that GNN parameters such as the hidden dimension, the number of layers, the mini-batch size and the feature size influence the effectiveness of graph partitioning, both in terms of training time and memory overheads. Our experiments further show that a higher scale-out factor can decrease the effectiveness of vertex partitioning, while the effectiveness increases for edge partitioning.
4. We find that invested partitioning time can be amortized by faster GNN training in typical scenarios, making graph partitioning relevant for production systems.

Our paper is organized as follows. In Section 2, we introduce graph partitioning and graph neural networks. In Section 3, we describe our methodology. Then, we analyze the results for DistGNN in Section 4 and for DistDGL in Section 5. In Section 6, we summarize our main findings and in Section 7 we discuss related work. Finally, we conclude our paper in Section 8.

## 2. Background

Let \(G=(V,E)\) be a graph consisting of a set of vertices \(V\) and a set of edges \(E\subseteq V\times V\). \(N(v)\) represents the set of vertices that are connected to \(v\). In the following, we discuss graph partitioning in Section 2.1 and distributed GNN training in Section 2.2.

### Graph Partitioning

The main approaches for graph partitioning are _edge partitioning_ and _vertex partitioning_ (see Figure 1). In the following, we present both approaches in more detail, along with commonly used partitioning quality metrics.

Edge PartitioningIn edge partitioning (vertex-cut), the set of edges \(E\) is divided into \(k\) partitions by assigning each edge to exactly one partition \(p\in P=\{p_{1},\ldots,p_{k}\}\) with \(\cup_{i=1}^{k}p_{i}=E\). Through this process, vertices can be cut. A cut vertex is replicated to all partitions that have adjacent edges. Each partition \(p_{i}\) covers a set of vertices \(V(p_{i})=\{v\in V\,|\exists e=\{u,v\}\in p_{i}\}\). The goal of edge partitioning (Zhou et al., 2017) is to minimize the number of cut vertices while keeping the partitions' edges \(\alpha\)-balanced, meaning \(\forall p_{i}\in P:|p_{i}|\leq\alpha\cdot\frac{|E|}{k}\).

Commonly used quality metrics to evaluate edge partitioners are the mean _replication factor_ and _edge balance_. The replication factor \(RF(P)\) is defined as \(\frac{1}{|V|}\sum_{i=1}^{k}|V(p_{i})|\) and represents the average number of partitions to which vertices are replicated. This metric is closely related to communication costs because replicated vertices need to synchronize their state via the network. The edge balance is defined as \(\mathit{EB}(P)=\frac{max(\{|p_{i}|,\ldots,|p_{k}|\})}{mean(|p_{i}|,\ldots,|p_{ k}|)|)}\) and the vertex balance as \(\mathit{VB}(P)=\frac{max(\{|V(p_{i})|,\ldots,|V(p_{i})|\})}{mean(\{|V(p_{i})|, \ldots,|V(p_{i})|\})}\). Most edge partitioners do not explicitly balance vertices because the computational load of many graph algorithms is proportional to the number of edges as messages are aggregated along the edges (e.g., the PageRank algorithm).

Vertex PartitioningIn vertex partitioning (edge-cut), the set of vertices \(V\) is divided into \(k\) partitions by assigning each vertex \(v\) to exactly one partition \(p\in P=\{p_{1},\ldots,p_{k}\}\) with \(\cup_{i=1}^{k}p_{i}=V\). Vertex partitioning aims to minimize the number of cut edges while balancing the partition sizes in terms of number of vertices. We define \(E_{cut}\) as the set of cut edges. An edge \(e=\{u,v\}\) is cut if both \(u\) and \(v\) are assigned to different partitions.

Commonly used vertex partitioning quality metrics to evaluate vertex partitioners are the _edge-cut ratio_ and _vertex balance_. The edge-cut ratio is defined as \(\lambda=\frac{|E_{cut}|}{|E|}\) and indicates communication costs, as messages are sent via edges, and cut edges lead to network communication speed even machines. The vertex balance is defined as \(\mathit{VB}(P)=\frac{max(\{|p_{1}|,\ldots,|p_{k}|\})}{mean(\{|p_{1}|,\ldots,|p _{k}|\})}\) and indicates computation balance.

Partitioner TypesBoth edge and vertex partitioning algorithms can be categorized into (1) _streaming partitioners_, which stream the graph and directly assign vertices or edges to partitions (Zhou et al., 2017; Wang et al., 2017; Wang et al., 2018; Wang et al., 2019; Wang et al., 2019). Streaming partitioners can be further divided into _stateless_ partitioners, which do not keep any state, and _stateful_ streaming partitioners, which use some state, e.g., the current load per partition or to which partition vertices or edges were assigned. The state is considered for the assignments. (2) _In-memory partitioners_ which load the complete graph into the memory (Goh et al., 2017; Wang et al., 2018; Wang et al., 2019; Wang et al., 2019; Wang et al., 2019). (3) _Hybrid partitioners_ that partition one part with an in-memory partitioner and the remaining part with a streaming partitioner (Wang et al., 2019).

### Graph Neural Network Training

Graph Neural Networks are a class of neural networks which operate on graph-structured data. GNNs iteratively learn on graphs by aggregating the local neighborhoods of vertices. At start, each vertex \(v\) is represented by its feature vector \(h_{v}^{(0)}\). In each layer, a vertex \(v\) aggregates learned representations of its neighbors \(N(v)\) of the previous layers, resulting in \(a_{v}^{(k)}\) (Equation 1).

\[a_{v}^{(k)}=\mathit{AGGREGATE}^{(k)}(\{h_{u}^{(k-1)}|u\in N(v)\}) \tag{1}\]

A vertex updates its representation based on \(a_{v}^{(k)}\) and its previous intermediate representation \(h_{v}^{(k-1)}\) in layer \(k-1\) by applying an update function (Equation 2).

\[h_{v}^{(k)}=\mathit{UPDATE}^{(k)}(a_{v}^{(k)},h_{v}^{(k-1)}) \tag{2}\]

Figure 1. Edge partitioning vs. vertex partitioning.
The main approaches to train GNNs are _full-batch_ and _mini-batch_ training (Golovolovolovolov et al., 2012). In full-batch training, the entire graph is used to update the model once per epoch. In mini-batch training, each epoch contains multiple iterations, where a mini-batch is sampled from the graph and used for training and model update.

## 3. Experimental Methodology

Our study aims to investigate the effect of graph partitioning on the performance of distributed GNN training. We want to answer the following five research questions (RQ):

* How effective is graph partitioning for distributed GNN training in reducing training time and memory footprint?
* Do classical partitioning quality metrics accurately describe the effectiveness of partitioning algorithms for distributed GNN workloads? Which partitioning quality metric is most crucial?
* How much is the partitioning effectiveness influenced by GNN parameters such as the _number of layers_, _hidden dimension_, _feature size_, _mini-batch size_, and _type of graph_?
* What is the impact of the scale-out factor on the partitioning effectiveness?
* Can the invested partitioning time be amortized by a reduced GNN training time?

To answer these research questions, we conduct various experiments with two state-of-the-art distributed GNN systems: _DistGNN_(Golovolovolov et al., 2012) and _DistDGL_(D
**Training & partitioning time** We measure the time per epoch. In addition, we measure the time spent in the forward pass, backward pass, synchronization of the model, and the optimizer step. Furthermore, we measure the partitioning time.

### Partitioning Performance

We compare the partitioning algorithms regarding their communication costs and computational balance in the following.

_Communication costs._ We observe significant differences in terms of replication factors for the different partitioners. In all cases, _HEP100_ leads to the lowest (best) replication factor and _Random_ to the largest (worst) one. Figure 1(b) shows, for example, that _HEP100_ at 32 partitions leads to a replication factor of 2.52 on _OR_, which is much smaller compared to _Random_ which leads to a replication factor of 22.2. In general, more partitions lead to larger replication factors. For some partitioners, the replication factors increase more sharply than for others if the number of partitions increases. We observe a strong correlation (\(R^{2}\geq 0.98\)) between the replication factor and network traffic. This correlation is shown in Figure 3 for _OR_ for different numbers of machines and number of layers and is also observed for the remaining graphs. The observation is plausible. The higher the replication factor, the more data is communicated via the network because more vertices are replicated and must synchronize their states.

We conclude that **minimizing the replication factor is crucial for reducing network overhead**.

_Computational balance._ It is crucial to balance the number of edges and vertices per partition. Each edge leads to an aggregation in the GNN, and neural network operations are performed for vertices. We observe a good edge balance of at most \(\alpha\leq 1.11\) for all partitioners. However, we observe significant vertex imbalances (see Figure 4). Especially, the partitioners _2PS-L_, _HEP10_ and _HEP100_ lead to large imbalances between 1.18 and 1.89 on 4 machines (see. Figure 3(a)) and can even increase up to 2.44 on 32 machines (see. Figure 3(b)). The vertex imbalance has a significant influence on the balance of memory utilization. Figure 5 reports the imbalance regarding memory utilization for all partitioners. We observe that vertex imbalance perfectly correlates with memory utilization imbalance.

We conclude that **minimizing vertex imbalance is crucial for balancing memory utilization**.

_Partitioning time._ Figure 6 reports the partitioning time for partitioning all graphs into 4 and 32 partitions. We observe that the partitioning times of some algorithms, e.g., _Random_, _2PS-L_ and _DBH_, are less dependent on the number of partitions, compared to the remaining partitioners, where more partitions lead to higher partitioning times. For example, _HDRF_ takes much more time to partition the graphs into 32 partitions compared to 4 partitions, which is expected because the complexity of the scoring function depends on the number of partitions.

In the following, we further analyze how the GNN training time is influenced by the partitioning metrics for different number of machines, and how GNN parameters influence the effectiveness of the partitioners.

### GNN Training Performance

In Figure 7, we report the speedup distribution for all partitioners compared to random partitioning for all combinations of _feature size_, _hidden dimension_ and _number of layers_ (see Table 3). We observe significant differences in terms of training time between the partitioners. _HEP100_ leads to the largest speedups of up to 3.53, 6.18, 8.15 and 10.41 on the graphs _EU_, _EN_, _OR_ and _HW_, respectively. For example, on _OR_, compared to _Random_, on average _DBH_, _2PS-L_, _HDRF_, _HEP10_ and _HEP100_ lead to speedups of 1.40, 1.46, 1.44, 2.96 and 3.68 on 8 machines, 1.62, 1.61, 1.75, 4.37 and 7.16 on 16 machines and 1.74, 1.95, 2.00, 5.67 and 7.16 on 32 machines. We observe

Figure 4. Vertex balance.

Figure 5. Memory utilization balance (4 machines).

Figure 3. Replication factor vs. network communication for different number of machines and number of layers on _OR_.

Figure 2. Replication factors.
that the effectiveness in terms of speedup increases if the number of machines increases. Only _2PS-L_ on _EU_ has a slowdown of 0.92, 0.92, and 0.91 on 8, 16 and 32 machines, respectively. We attribute this to the observation that the partitioning is highly imbalanced in terms of vertex balance, which we discuss in the following. We observe that a low replication factor is crucial to achieve large speedups. However, if the replication factor of two partitioners is close, it becomes clear that vertex balance is important as well. This can for example be seen in Figure 8. _2PS-L_ leads to a similar replication factor as _HDRF_ and _DBH_ on _EN_. However, _2PS-L_ leads to a large vertex imbalance while _HDRF_ and _DBH_ are perfectly balanced. We observe that _2PS-L_ leads to much smaller speedups which indicates that the vertex imbalance has a negative effect on the speedup.

In Figure 7, we observe only little spread in terms of speedup. In other words, the partitioners' speedups are independent of the GNN parameters. We make a similar observation for network traffic. The savings are stable and not influenced much by the GNN parameters. This observation seems plausible. The replication factor influences for how many replicas the vertex state needs to be synchronized. The GNN parameters hidden dimension and feature size influence the state size and determine how much state needs to be synchronized. However, the ratio between the partitioners stays stable.

Figure 8(a) and Figure 8(b) give an overview of how much memory is needed for training with different partitioners in percent of random partitioning. We make two main observations. (1) The high-quality partitioners (_HEP10_ and _HEP100_) are much more effective than the other partitioners. (2) A large deviation indicates that the partitioners' effectiveness depends on the GNN parameters. In the following, we first discuss why the partitioners differ in their effectiveness in terms of memory footprint and analyze how the GNN parameters influence this effectiveness.

We observe a strong correlation (\(R^{2}\geq 0.99\)) between the replication factor and memory footprint. Further, we observe that the memory footprint can heavily decrease, e.g., _HEP100_ reduces the memory for the graphs _EU_, _OR_, _HW_, _EN_ by 37% 53%, 56% and 60% on 8 machines, by 44%, 60%, 65% and 63% on 16 machines and by 40%, 67%, 66% and 63% on 32 machines, respectively compared to _Random_. There are also cases where random partitioning leads to out-of-memory errors. For example, in all cases, _DI_ can not be processed if random partitioning is applied, but in contrast, the more advanced partitioners enable the processing in many cases. In classical distributed graph processing, the replication factor is often minimized with the primary goal of reducing network communication. The memory load is less critical, especially if the vertex state is small which is the case for many graph processing algorithms such as BFS, DFS, Connected Components, PageRank, and K-cores. In contrast, in GNNs, the vertex state consists of large feature vectors meaning that the vertex state, not the graph structure, dominates the required memory. We conclude that **minimizing the replication factor is crucial for minimizing the memory overhead and can be decisive for GNN training.**

In the following, we analyze how the different GNN parameters influence the effectiveness of the partitioners **in terms of memory**.

_(1) Feature size._ In Figure 9(a), we report the memory footprint for all partitioners in percent of random partitioning dependent on the feature size. We observe that if we keep all other parameters constant, an increase in the feature size increases the effectiveness. This result seems plausible. A fixed amount of memory is needed, e.g., for storing the graph structure. With an increasing feature size, the state to replicate increases, making partitioning more effective. We conclude, **the larger the feature size, the higher the effectiveness of graph partitioners to reduce the memory footprint.**

Figure 8. Replication factor vs. speedup on _EN_ along with the vertex balance in the brackets.

Figure 6. Partitioning time.

Figure 7. Speedup distribution of graph partitioners on 4, 8, 16 and 32 machines for all experiments.
(2) _Hidden dimension._ If the feature size and number of layers are kept constant, there will be some fixed amount of memory for the graph structure, the corresponding features, and the replication of the features. We observe that the higher the hidden dimension, the more effective the partitioners become (see Figure (b)b). This observation seems reasonable. Larger hidden sizes lead to more state (intermediate representations) which needs to be synchronized among the machines as they are needed as the input of the next layer. We conclude that **the larger the hidden dimension, the higher the effectiveness of graph partitioners to reduce the memory footprint**.

_(3) Number of layers._ The number of layers can influence the effectiveness of graph partitioning. The higher the number of layers, the more intermediate representations need to be stored (one per vertex and layer) which are needed in the backward pass. The replication factor influences to how many machines the intermediate representations are replicated, and the hidden dimension determines their size. We observe that, especially if the hidden dimension is large and the feature size is small, the effectiveness increases for more layers. This seems reasonable.

If the feature size is large and the hidden dimension is small, the effectiveness of graph partitioning remains relatively unaffected by the number of layers. This is because the state size is large due to the replication of large features. Increasing the number of layers results in more replications of small hidden representations, which does not significantly impact the memory footprint. However, if the feature size is small and the hidden dimension is large, increasing the number of layers leads to more replications of large hidden representations.

We conclude, **the larger the hidden dimension and the smaller the features size, the higher the effectiveness of graph partitioners with an increasing number of layers increases.**

_(4) Scale-out factor._ In the following, we analyze how the scale-out factor influences the partitioners' effectiveness in terms of speedup and memory footprint. Figure (a)a shows the average speedup for all graph partitioners at different scale-out factors compared to random partitioning. We observe that the effectiveness of all graph partitioners increases if more machines are used for training. However, there are differences in how sharply the effectiveness increases. For the more light-weight partitioners _2PS-L_, _DBH_ and _HDRF_, the speedups increase moderately from 1.57, 1.37, and 1.49 on 4 machines to 1.79, 1.7, and 2.06 on 32 machines, respectively. The partitioners _HEP10_ and _HEP100_ lead to a speedup of 1.95 and 2.47 on 4 machines which increase sharply to 5.41 and 6.77 on 32 machines, respectively. We make similar observations for the memory overheads (see Figure (b)b). All partitioners lead to substantial savings which increase if the number of machines increases. Both observations are plausible: In Figure (c)c, we report the achieved replication factors for all partitioners for all scale-out factors in percentages of _Random_, meaning lower numbers are better. We find that the replication factor of all partitioners increases less sharply than _Random_ if the scale-out factor increases. We observe that the replication factors of _2PS-L_, _DBH_, _HDRF_ is 56.74%, 76.49% and 62.16% of _Random_ on 4 machines and 39.99%, 60.81% and 48.58% of _Random_ on 32 machines. _HEP10_ and _HEP100_ achieve a replication factor of 49.27% and 36.05% of _Random_ on 4 machines and significant lower replication factors of 14.05% and 11.37% of _Random_ on 32 machines, respectively.

We conclude that **the effectiveness of graph partitioning is increasing both in terms of training time and memory overhead if the number of machines is increasing**.

_(5) Partitioning time amortization._ In Table 4, we report the average number of epochs until the partitioning time is amortized by faster training time for each combination of graph and partitioner. We assume that random partitioning does not take any time. _DBH_ is the partitioner that amortizes the fastest: on average, it takes 1.39, 3.79, 3.05, and 3.83 epochs on the graphs _EN_, _EU_, _HW_ and _OR_ to amortize the partitioning time. _HEP100_ which leads to the largest speedups amortizes after 4.29, 12.0, 4.7, and 7.03 epochs on the graphs _EN_, _EU_, _HW_ and _OR_. Full-batch training is often performed for hundreds of epochs (Shen et al., 2017). **Therefore, the partitioning time can be amortized.** In addition, a hyper-parameter search is often performed which requires even more training epochs. Therefore, it is even more beneficial to invest in partitioning.

## 5. DistDgl

### Experiments

**Graph partitioning algorithms** We use six state-of-the-art vertex partitioners from different categories: (1) stateless streaming partitioning with random partitioning, (2) stateful streaming with LDG, and (3) in-memory partitioning with ByteGNN, Spinner, Metis, and KaHIP (see. Table 2).

Figure 10. Memory footprint in % of random partitioning dependant on different GNN hyper-parameters for _OR_ on 8 machines.

Figure 9. Distribution of memory footprint of graph partitioners in % of random partitioning on 4 and 32 machines.
**Workloads** We selected a representative set of graph neural network architectures commonly used in distributed GNN training, namely, GAT, GraphSage, and GCN. We use the same hyperparameters as for _DistGNN_ (see Table 3). If not mentioned otherwise, we perform neighborhood sampling for all GNN models with the following configuration. Let \(S_{i}\) be the number of neighbors to sample for layer \(i\). For two layer GNNs, we use \(l_{1}=25\) and \(l_{2}=20\), for three layer GNNs \(l_{1}=15\), \(l_{2}=10\) and \(l_{3}=5\) and for four layer GNNs, \(l_{1}=10\), \(l_{2}=10\), \(l_{3}=5\) and \(l_{4}=5\). We use a global batch size \(GBS\) of 1024 if not stated otherwise. Therefore, each worker \(w_{i}\in W\) trains with \(\frac{GBS}{|W|}\) samples.

**Partitioning metrics** We compare the partitioners with the commonly used partitioning quality metrics _edge-cut_ and vertex balance introduced in Section 2.1. In addition, we measure the training vertex balance. Further, we measure metrics based on the sampled mini-batches: the number of edges of the computation graphs, the number of local input vertices, and the number of vertices that need to be fetched via the network.

**Training & Partitioning Time** We measure the epoch and step time and all phases (mini-batch sampling, feature loading, forward pass, backward pass, and model update) for each step. In addition, we measure the partitioning time.

### Partitioning Performance

In the following, we compare the graph partitioners regarding communication costs and computational balance.

_Communication Costs._ In Figure 12, we report the achieved edge-cut ratio for each combination of graph, graph partitioning algorithm, and number of partitions. In most cases, _KaHIP_ achieves the lowest edge-cut and random partitioning leads to the largest edge-cut. We observe significant differences between the partitioning algorithms in terms of edge-cut, e.g., _KaHIP_ achieves an edge-cut ratio smaller than 0.001 and 0.12 on the graph _DI_ and _EU_ for 32 partitions, respectively, which is much lower (better) compared to random partitioning which leads to edge-cuts of 0.68 and 0.93 for the same graphs. We also observed for all partitioning algorithms that a higher number of partitions leads to a larger edge-cut.

In the following, we investigate the influence of the edge-cut on network communication. There are cases where a lower edge-cut results in less network communication. However, there are also cases where even if the edge-cut of different partitioners is similar, the network communication can differ a lot. For example, we observed that Spinner has an edge-cut lower than Metis on _OR_, but the network communication is much higher.

This observation seems reasonable. There can be edges that are more frequently involved in the sampling process. If these edges are cut, they lead to more network traffic than edges hardly visited in the sampling process. To ensure that the observed anomaly is related to graph partitioning, we measure for each mini-batch the number of vertices needed for processing the mini-batch that are not local to the respective worker. We define these vertices as _remote vertices_. We observe a strong correlation between the number of remote vertices and network traffic. We conclude that edge-cut is not always a perfect predictor for network traffic and that there are cases where a lower edge-cut still leads to more remote vertices and higher network traffic.

_Computation Balance._ For efficient distributed graph processing, it is crucial that the computation is balanced among machines which is measured via the vertex balance. However, unlike distributed graph processing algorithms such as PageRank, the computational load of mini-batch GNN training depends on the size of the sampled mini-batches. Each worker samples a mini-batch based on the k-hop

\begin{table}
\begin{tabular}{|l||c|c|c|c|c|} \hline Graph & DBH & 2PS-L & HDRF & HEP10 & HEP100 \\ \hline \hline EN & 1.39 & 4.57 & 4.64 & 3.35 & 4.29 \\ \hline EU & 3.79 & no & 8.8 & 10.15 & 12.0 \\ \hline HO & 3.05 & 4.22 & 7.26 & 4.48 & 4.7 \\ \hline OR & 3.83 & 7.39 & 11.69 & 6.64 & 7.03 \\ \hline \end{tabular}
\end{table}
Table 4. Number of epochs until graph partitioning time is amortized by faster GNN training time. “No” means no amortization is possible because of slowdown.

Figure 11. The effectiveness of graph partitioning increases in terms of speedup and memory overhead if the scale-out factor is increased from 4 to 8, 16 and 32 machines.
neighborhood of the training vertices. To ensure load balance, it is essential that the computation graphs of mini-batches are of similar size. We define the number of vertices that are needed to compute a mini-batch as the _input vertices_ and _input vertex balance_ per step as the number of input vertices of the largest mini-batch divided by the average number of input vertices per mini-batch in the respective step. In Figures 13(a)-13(b), we report the imbalance of the mini-batches in terms of input vertices. We observe a large imbalance, which is increasing as the number of partitions is increased.

_Partitioning Time_. In Figure 15, we report the partitioning time for all graphs and partitioning algorithms for 4 and 32 partitions. We observe that the best (in terms of lowest edge-cut) performing partitioner _KaHIP_, leads to the highest partitioning time.

In the following, we investigate the influence of the partitioning metrics on the actual GNN training time and analyze how the GNN hyper-parameters influence the effectiveness of the graph partitioners.

### GNN Training Performance

In Figure 16, we report the average speedups for all combinations of _feature size_, _hidden dimension_ and _number of layers_ (see Table 3) for all graph partitioners with random partitioning as a baseline on 4, 8, 16 and 32 machines for the GraphSage architecture. In our experiments, _KaHIP_ and _Metis_ lead to the largest speedups of up to 1.84, 1.84, 3.09 and 3.47 on a cluster with 4, 8, 16 and 32 machines, respectively. Therefore, graph partitioning is an important preprocessing step for distributed GNN training.

In Figure 16, we see significant variances in terms of speed up that indicate that the effectiveness of the partitioning algorithms depends on the GNN parameters. Therefore, we conduct a detailed analysis of how different GNN parameters influence the different training phases and how the partitioners differ from each other. On each worker in each step, we measure the phase times (1) mini-batch sampling, (2) feature loading, (3) forward pass, (4) backward pass, and (5) model update. In each step, we identify the worker which leads to the longest mini-batch sampling, feature loading and forward pass time as the straggler. We exclude the time for the backward pass because it also contains the time for the all-reduce operation in which the gradients are synchronized between the workers. The model update time is negligible. Then, we get the phase times of the slowest worker per step and sum up the phase times of all steps of the respective slowest worker. In other words, we are interested in how much time the straggler spends on average in each phase. In the following, we investigate how the different GNN model parameters influence the effectiveness of graph partitioning in terms of speedup of the distributed training compared to random partitioning. In Figure 17, we observe large imbalances for all partitioners, showing that even if the number of training vertices

Figure 16. Speedup distribution of graph partitioners on 4, 8, 16 and 32 machines for all GraphSage experiments.

Figure 14. Balance in terms of input vertices of the mini-batches for the GraphSage model.

Figure 13. Training vertex balance (8 partitions).

Figure 15. Partitioning time on a logarithmic scale.
is balanced, the computation time can be imbalanced. Interestingly, all partitioners lead to large imbalances.

_(1) Feature size._ We observe that **the effectiveness of partitioning increases with larger feature sizes**. Figures (a)a-(b)b shows the speedup for the partitioners compared to random partitioning dependent on the feature size. For example, in Figure (a)a, the training for GraphSage with _KaHIP_ leads to a speedup of 1.23 and 1.52 for a feature size of 16 and 512, respectively. This observation is plausible. As feature sizes increase, network communication increases because larger feature vectors are sent over the network, making graph partitioning even more valuable in reducing communication costs.

**Detailed:** For each combination of number layers and hidden dimension, we vary the feature size. We make the following key observations: (1) The larger the feature size, the longer the feature fetching phase (see Figure (a)a) while the sampling time stays constant. We also observe that for small feature sizes (up to 64), the sampling takes more time than fetching features, but for large feature sizes of 512, the time for feature fetching dominates the sampling time by a lot (see Figure (a)a). In contrast, for the road network _DI_, we observe that sampling always takes more time than fetching features (see Figure (b)b) which seems plausible because the mean degree in the road network is small and the skew of the degree distribution is low. Therefore, the sampled mini-batches are small, and only a few input vertices must be fetched. We also observe that the edge-cut for the road network is much lower than for the remaining graphs (see Figure 12). (2) The forward and backward pass time increases with larger feature sizes, which is plausible because more computations will be performed in the first layer.

We observe that the partitioners differ a lot from each other when varying the feature size and that the feature size influences the different phases. The feature fetching phase is influenced most, which can for example be seen in Figure (a)a for training a three layer GraphSage with a hidden dimension of 64 on the graph _EU_. In most cases, the better the partitioner in terms of edge-cut, the lower the communication costs, which can speed up both the mini-batch sampling and the feature fetching phase.

_(2) Number of hidden dimensions._ We found that **partitioning becomes less crucial as the hidden dimension increases**. For example, compared with random partitioning, _KaHIP_ leads to a speedup of 1.38 and 1.19 and _Metis_ 1.31 and 1.15 for a hidden dimension of 16 and 512, respectively. This result is reasonable since an increased hidden size leads to greater computational costs, potentially dominating the communication costs.

**Detailed:** We vary the hidden dimension for each combination of feature size and number of layers. Our main observations are: (1) sampling and feature loading time stay constant, which is expected as only the neural network operations are influenced by the hidden dimension. The larger the hidden dimension, the more time is used for computation. (2) We also observe that the effectiveness of partitioners decreases for the larger hidden sizes because most of the differences are in feature loading and sampling. However, if the hidden size increases, the computation takes a larger share of the overall training time. Therefore, the difference between the partitioners is lower.

_(3) Number of Layers._ We observe that **the effectiveness of the partitioners remains relatively unaffected by an increasing number of layers.** In some cases, the effectiveness slightly increases or decreases, but the influence is much smaller than the influence of the feature size and hidden dimension, and there is also no clear trend. This is an unexpected observation. One could think that the effectiveness of the partitioning algorithms would

Figure 19. Phase times for a 3 layer GraphSAGE model with a hidden dimension of 64 on 4 machines for different feature sizes.

Figure 17. Balance in terms of training time.

Figure 18. Speedup of graph partitioners for the GraphSage model on 4 and 32 machines for different feature sizes.
heavily decrease if the number of layers increases because large parts of the graph will be contained in the mini-batches, but still, the partitioning algorithms lead to different training times, and many partitioners outperform random partitioning.

**Detailed:** We vary the number of layers for each combination of feature size and hidden dimension. We make the following key observations: (1) All phases increase in run-time if the number of layers increases. This is expected because an increase in the number of layers leads to larger computation graphs within the mini-batches, which increase the communication costs (more remote accesses in the sampling phase and more remote vertices to fetch via the network) and the computation costs (more neural network operations). (2) We observe, especially for 3 and 4 layer GraphSage, that most of the speedup gained by different partitioning algorithms comes from faster sampling and feature fetching (see Figure 21).

_(4) Scale-out factor._ In the following, we investigate the effectiveness of scaling out distributed GNN training to more machines for all partitioning algorithms. We scale out from 4 to 8, 16 and 32 machines. We make the following observations: (1) For _DI_, scaling out increases the effectiveness of the partitioners. Especially for the partitioners _KaHIP_, _Metis_, _LDG_ and _ByteGNN_, the effectiveness increases a lot. However, for _Spinner_, the effectiveness stays relatively constant. This seems plausible as the edge-cut for _Random_ and _Spinner_ is far higher on _DI_ than for the remaining partitioners (see Figure 12). (2) For the remaining graphs, we observe that the effectiveness of GraphSage decreases on average (see Figure 1(a)). For example, _KaHIP_ and _Metis_ lead to a speedup of 1.32 and 1.27 on 4 machines and to a smaller speedup of 1.25 and 1.19 on 32 machines, respectively. We found that the number of remote vertices (see Figure 1(b)) and the edge-cut (see Figure 1(c)) of the partitioners in percentages of _Random_ is increasing when scaling out to more machines. We also observe that the network communication of the partitioners in percentages of _Random_ is also increasing. In other words, the effectiveness of the partitioners is also decreasing in terms of partitioning metrics and network communication compared to _Random_, when the number of machines increases. It is worth to note that the feature loading phase scales really well. We found that large feature sizes make partitioning more effective. For large feature vectors and few machines, the feature fetching phase can take a large share of the training time and also leads to large differences between the partitioners (see Figures 1(a) and 1(b)). The feature fetching phase can decrease sharply when scaling out to more machines. Therefore, the difference between the partitioners is decreasing, resulting in lower effectiveness. We make a similar observation with the sampling phase. We conclude that **in most cases, the effectiveness of partitioning slightly decreases if the scale-out factor increases**.

_(5) Partitioning time amortization._ In Table 5, we report the average number of epochs until the partitioning time is amortized by faster training time for each combination of graph and partitioner. We observe that **the partitioning time can be amortized by faster GNN training**. However, _KaHIP_, the partitioner which leads to the largest speedups only amortizes for _DI_ but not for the remaining graphs. However, _Metis_, which also leads to significant speedups, does amortize for all graphs.

Figure 23. Speedup of graph partitioners for the GraphSage model on 4 and 32 machines for different number of layers.

Figure 21. Times of different phases for a GraphSAGE model with a hidden dimension and feature size of 64 on 4 machines for the _OR_ graph.

Figure 20. Speedup of graph partitioners for the GraphSage model on 4 and 32 machines for different hidden dimensions.

Figure 22. Times of different phases for a 3 layer GraphSAGE with a feature size of 64 on 4 machines for the _OR_ graph.
### Influence of mini-batch size on partitioner effectiveness

The following experiments aim to investigate the influence of the _mini-batch size_ on the effectiveness of partitioning. In other words, we want to evaluate if the partitioning is more crucial (in terms of reduced training time) if the mini-batch size increases.

We fix the number of workers to 16 and set the mini-batch size to 512, 1024, 2048, 4096, 8192, 16384, and 32768 for a three layer GAT and a three layer GraphSage. For both GNN architectures, we use two configurations: (1) hidden dimension and feature size of 64 (low communication) and (2) hidden dimension of 64 and feature size of 512 (high communication).

We observe for all partitioners that the network traffic decreases if the batch size increases compared to _Random_ (see Figure 26b). For example, _KaHIP_ and _Spinner_ lead to a network communication of 66% and 77% of _Random_ with a batch size of 512 and of 48% and 67% if the batch size is set to 32768, respectively. We observe a similar trend for the number of remote vertices (see Figure 26c). This seems reasonable. Many vertices can end up in _different_ mini-batches. However, if the mini-batch increases, the overlap in the larger mini-batches increases, leading to fewer remote vertices.

The effectiveness of the partitioners can decrease or increase with larger batch sizes if the feature size is 64: However, there is no clear trend. In contrast, if the features size is 512, in most cases, the effectiveness of the partitioners increases for ByteGNN, KaHIP, Metis and Spinner on the graphs _HW_, _EU_, _EN_ and _OR_. For example, Figure 26a shows that training with _KaHIP_ and _Metis_ lead to a speed up of 1.27 and 1.13 for a small batch size of 512 and to a larger speed up of 1.91 and 1.65 if the batch size is set to 32768. We conclude that **larger batch sizes increase the partitioner effectiveness for large feature sizes**.

\begin{table}
\begin{tabular}{|l||l|l|l|l|l|} \hline Graph & ByteGNN & KaHIP & LDG & SPINNER & METIS \\ \hline \hline DI & 0.93 & 2.61 & 0.1 & 14.37 & 1.13 \\ \hline EN & 2.16 & 2501.93 & 0.39 & 54.07 & 16.79 \\ \hline EU & no & 1197.25 & no & 53.8 & 8.14 \\ \hline HO & 0.68 & 347.51 & 0.47 & 77.78 & 10.7 \\ \hline OR & 3.14 & 223.19 & 0.27 & 70.19 & 14.59 \\ \hline \end{tabular}
\end{table}
Table 5. Number of epochs until graph partitioning time is amortized by faster GNN training time. ”No” means no amortization is possible because of slowdown.

Figure 24. The effectiveness of partitioning decreases when scaling GraphSage from 4 to 32 machines.

Figure 25. Phase times for a 3 layer GAT and GraphSage with a feature size of 512 and a hidden dimension of 64 on the _OR_ graph trained with 4, 8, 16 and 32 machines.
Lessons Learned

In the following, we summarize our main findings and refer them to the research questions introduced in Section 3.

**(1) Graph partitioning is effective to speed up GNN training (RQ-1).** We observed large speedups of up to 10.41 and 3.4 for DistGNN and DistDGL, respectively. The speedups achieved for DistDGL are comparable to those seen in distributed graph processing [29; 30; 32]. However, the speedups for DistGNN are higher. Full-batch training leads to large communication and memory overheads, both heavily influenced by graph partitioning, which makes graph partitioning crucial for efficient distributed full-batch GNN training.

**(2) Graph partitioning is effective in reducing the memory footprint (RQ-1).** We found that the replication factor perfectly correlates with the amount of necessary memory. Different from classical distributed graph processing, where the state of vertices is small, in GNNs, the state of vertices is large. The vertices can have large feature vectors and intermediate representations that must be stored for all vertices. Minimizing the replication factor leads to significant memory savings because fewer vertex states are replicated. We observe many cases where advanced partitioning algorithms leading to small replication factors can reduce the necessary amount of memory by up to 85.1%. Therefore, the replication factor determines whether training a GNN with the given memory budget is possible at all.

**(3) Classical partitioning metrics are relevant for GNN performance (RQ-2)**. For both DistDGL and DistGNN, we observed that both communication and balancing metrics are important. Especially for DistGNN, we observed that the replication factor has a large correlation with the network communication, the memory overhead, and ultimately the training time. Minimizing the replication factor to reduce the GNN training time is crucial. We also found that in cases where two different partitioners lead to a similar replication factor, balancing the vertices becomes important. Furthermore, vertex balance perfectly correlates with memory utilization balance which is crucial for memory-intensive full-batch training. This is an important insight, as most edge partitioners balance the number of edges per partition and do not focus on balancing vertices.

**(4) GNN parameters influence the effectiveness of graph partitioners (RQ-3).** Unlike distributed graph processing, in GNN training, the GNN models have parameters, such as the number of layers, the hidden dimension, or the batch size, and the graphs have attached features. For DistDGL, we observed that GNN parameters influence the partitioners' effectiveness. Graph partitioning is effective, especially if the feature vectors are large and the hidden dimensions are low. We also found that if the feature size is large and the mini-batch size increases, the effectiveness increases a lot. For DistGNN, we observe that effectiveness in terms of training run-time is less dependent on the GNN parameters. However, regarding memory overhead, the effectiveness increases if the feature size, the hidden dimension or the number of layers increases.

**(5) The scale-out factor influences the effectiveness of graph partitioners (RQ-4)**. For DistDGL, we observe that in most cases, the effectiveness of graph partitioning slightly decreases when scaling out to more machines. However, for DistGNN, graph partitioning becomes very important because the network costs increase significantly.

**(6) Partitioning can be amortized by faster GNN training (RQ-5).** For both DistDGL and DistGNN, we found that the invested graph partitioning time can in many cases be amortized already after a few epochs, making graph partitioning an important optimization for distributed GNN training.

## 7. Related Work

Different studies [2; 45; 12; 34] have been conducted to investigate how graph partitioning influences the performance of distributed graphs processing systems. Verma et al. [45] study the graph partitioning algorithms available in GraphX [14], PowerGraph [13], and PowerLyra [9] for graph analytics. Abbas et al. [2] study streaming graph partitioners and compare them in a graph processing framework based on Apache Flink [7] for graph analytics. Gill et al. [12] investigate the influence of different partitioning strategies in D-Galois for graph analytics workloads. Pacaci and Ozsu [34] study streaming graph partitioning algorithms for graph analytics with PowerLyra and online graph query workloads with JanusGraph [1]. The studies focus on classical graph workloads. However, distributed GNN training is different. First, GNN training leads to large memory and communication overheads. Huge feature vectors and large intermediate states are computed, stored, and sent over the network. Second, the computations consist of computationally expensive neural network operations. Third, the GNN workloads are not only characterized by the model architecture, but also by GNN parameters such as the number of layers and hidden dimension. Forth, mini-batch-based training has a complex data loading phase which consists of distributed multi-hop sampling followed by a communication intensive feature loading phase.

Graph partitioning is a vibrant research area and many different approaches exist [16; 18; 19; 26; 27; 28; 29; 30; 32; 33; 35; 36; 37; 38; 39; 40; 41; 46; 48; 51]. See [8] for a recent survey about graph partitioning. We selected a representative set of different categories.

Many distributed graph neural network systems exist [11; 17; 42; 43; 49; 50]. A recent survey [44] gives an overview of different systems and compares those along different axis, also graph partitioning. We extend this research by experimentally investigating the effectiveness of graph partitioning for GNN training.

## 8. Conclusions

In our work, we performed an experimental evaluation to investigate the effectiveness of graph partitioning for distributed GNN training. We showed that graph partitioning is an essential optimization for distributed GNN training and that different factors such as GNN parameters (e.g., hidden dimension, number of layers, mini-batch size, etc.), the scale-out factor, and the feature size can influence the effectiveness of graph partitioning for GNN training, both in terms of memory footprint and training time. Further, we found that invested partitioning time can be amortized by reduced GNN training time. Based on our findings, we conclude that graph partitioning has great potential to make GNN training more effective. We hope our research can spawn the development of even more effective graph partitioning algorithms in the future.