arXiv:2604.01000v1 [cs.LG] 1 Apr 2026
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training Nikolai Merkel∗
Ruben Mayer
[email protected] Technical University of Munich (TUM) Munich, Germany
[email protected] University of Bayreuth Bayreuth, Germany
Volker Markl
Hans-Arno Jacobsen
[email protected] TU Berlin, BIFOLD, DFKI Berlin, Germany
[email protected] University of Toronto Toronto, Canada
Abstract Graph Neural Networks (GNNs) are widely used for learning on graph-structured data, but scaling GNN training to massive graphs remains challenging. To enable scalable distributed training, graphs are divided into smaller partitions that are distributed across multiple machines such that inter-machine communication is minimized and computational load is balanced. In practice, existing partitioning approaches face a fundamental trade-off between partitioning overhead and partitioning quality. We propose EmbedPart, an embedding-driven partitioning approach that achieves both speed and quality. Instead of operating directly on irregular graph structures, EmbedPart leverages node embeddings produced during the actual GNN training workload and clusters these dense embeddings to derive a partitioning. EmbedPart achieves more than 100× speedup over Metis while maintaining competitive partitioning quality and accelerating distributed GNN training. Moreover, EmbedPart naturally supports graph updates and fast repartitioning, and can be applied to graph reordering to improve data locality and accelerate single-machine GNN training. By shifting partitioning from irregular graph structures to dense embeddings, EmbedPart enables scalable and highquality graph data optimization.
1
Introduction
Graph Neural Networks (GNNs) have emerged as a state-of-theart method for extracting insights and predictions from graphstructured data. Their application spans diverse domains, including learning on relational databases [11], recommendation systems [59], drug discovery [24], fraud detection [30], and knowledge graphs [43]. However, training GNNs efficiently at scale remains computationally and memory intensive because for each vertex large feature vectors and intermediate representations need to be stored and computationally expensive neural network operations are performed. Consequently, distributed GNN training has become an essential strategy to scale to large graphs. In order to enable distributed GNN training, the input graph must be partitioned into smaller subgraphs that are distributed across multiple machines. Each worker processes the vertices of ∗ Work partially conducted at Technical University of Munich and TU Berlin / BIFOLD.
Optimize data layout based on graph structure Input Graph
Graph Partitioning
optimized graph
GNN training
Graph Reordering
(a) Traditional approach. Optimize data layout in embedding space Input Graph
GNN training
embeddings
Graph Partitioning Graph Reordering
optimized graph
(b) Proposed approach: EmbedPart
Figure 1: (a) Traditional approaches perform graph partitioning or reordering as a preprocessing step based solely on the graph structure. (b) Our approach (EmbedPart) derives partitions from node embeddings produced during GNN training. These embeddings capture both structural and feature information and enable partitioning or reordering directly in the dense embedding space using scalable clustering.
its local partition; however, for processing, information from vertices on remote partitions may be required. Consequently, data such as feature vectors and intermediate representations must be exchanged between machines during distributed training, which introduces substantial communication and synchronization overhead and can dominate end-to-end GNN training time [37]. To reduce the communication burden in distributed graph processing, graph partitioning methods have been proposed [17, 21, 32, 48], aiming to minimize cross-partition edges that lead to network communication while balancing the number of vertices across machines to achieve workload balance. Challenges. Despite extensive research, existing graph partitioning methods face key limitations: (1) they often require expensive upfront computation and partitioning time may not be amortized over the GNN training process, (2) repartitioning overhead is prohibitive in scenarios where the number of partitions must change dynamically (e.g., when scaling in or out), (3) they struggle with
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
efficiently handling updates in dynamic graphs, and (4) operate on irregular graph data structures which makes it challenging to parallelize, e.g., on a GPU. Solution. We propose a novel embedding-driven graph partitioning approach, EmbedPart, that fundamentally differs from classical methods: instead of constructing a partitioning before training begins (see Figure 1a), the GNN training is directly started. Then, the node embeddings that naturally emerge during the GNN workload itself are used to perform graph partitioning in the dense embedding space of the nodes (see Figure 1b). EmbedPart consists of two lightweight phases: (1) extracting node embeddings produced as a by-product of the GNN training, and (2) clustering these embeddings in the dense embedding space to derive graph partitions, followed by a lightweight rebalancing step to satisfy balancing constraints. This design decouples graph partitioning from expensive operations on highly irregular graph structures. Partitioning in the embedding space is efficient and trivially parallelizable: for instance, K-Means can cluster embeddings efficiently in parallel on a GPU. As a result, partitioning overhead becomes negligible relative to GNN training time and enables fast repartitioning. Further, EmbedPart naturally extends to dynamic settings where the graph changes over time, due to the inductive capabilities of GNNs, which can compute embeddings for new vertices. Additionally, embeddings produced by one specific GNN architecture can be reused to partition graphs for other architectures. Finally, thanks to its modular separation of embedding computation, clustering, and balancing, EmbedPart can be directly applied to graph reordering by reusing the clustering phase while omitting balancing. This reorders vertices such that nodes within the same partition are placed consecutively in memory, improving cache locality for single-machine GNN training. Contributions. Our contributions are summarized as follows:
• We introduce EmbedPart, a novel embedding-driven partitioning approach that derives graph partitions from node embeddings produced during the actual GNN training workload. By shifting partitioning from irregular graph structures to dense embedding spaces, EmbedPart transforms graph partitioning into a scalable clustering problem and enables efficient parallelization. • EmbedPart has a modular architecture consisting of embedding extraction, clustering, and lightweight balancing. All components can be replaced; for example, more advanced clustering algorithms could further improve performance. • EmbedPart operates on embeddings that can be reused and computed incrementally, enabling efficient repartitioning for evolving graphs and changing system configurations. This makes EmbedPart well suited for dynamic graphs and iterative machine learning workflows where data and resource requirements change over time. • We demonstrate that EmbedPart reduces partitioning overhead by more than two orders of magnitude compared to state-of-the-art in-memory partitioners while maintaining competitive partitioning quality and strong distributed GNN training performance.
• While primarily designed for graph partitioning, EmbedPart can also be applied to graph reordering, improving training performance in single-machine settings by increasing cache locality. The paper is organized as follows. In Section 2, we introduce the graph partitioning problem and provide background on graph neural network (GNN) training. Section 3 presents EmbedPart, our novel architecture for graph partitioning. In Section 4, we evaluate EmbedPart with respect to partitioning time, partitioning quality, and distributed training performance. We further demonstrate its applicability to graph reordering. Section 6 discusses related work, and Section 7 concludes the paper.
2 Background 2.1 Graph Partitioning Let 𝐺 = (𝑉 , 𝐸) be a graph with a set of vertices 𝑉 and edges 𝐸 ⊆ 𝑉 × 𝑉 . Let 𝑁 (𝑣) be the set of vertices to which vertex 𝑣 is connected by an edge, also called neighbors of 𝑣. In vertex partitioning (see Figure 2), the set of vertices 𝑉 is divided in 𝑘 disjoint partitions 𝑃1, . . . , 𝑃𝑘 . By partitioning the vertices, edges may be cut. For example, in Figure 2, the edge between vertices 3 and 4 (colored red) is cut. Each vertex 𝑣 ∈ 𝑉 will be assigned to exactly Ð one partition. Therefore, 𝑉 = 𝑖 ∈ [𝑘 ] 𝑃𝑖 and 𝑃𝑖 ∩ 𝑃 𝑗 = ∅ for 𝑖 ≠ 𝑗. Let pid(v) be the partition number 𝑝 ∈ [𝑘] to which 𝑣 is assigned. An edge 𝑒 = (𝑢, 𝑣) is cut if pid(u) ≠ pid(v) meaning 𝑢 and 𝑣 are assigned to different partitions.
0
1
2
3
4
5
0
1
4
5
6
7
2
3
6
7
Graph
Partition 1
Partition 2
Figure 2: Vertices are assigned to partitions. Edges connecting vertices of different partitions are cut.
2.1.1 Partitioning quality metrics. Two commonly used partitioning quality metrics are the edge-cut-ratio and the vertex balance. Let 𝐶 = {(𝑢, 𝑣) ∈ 𝐸 | pid(u) ≠ pid(v)} be the set of edges which are cut. The edge-cut-ratio is defined as: ECR =
|𝐶 | . |𝐸|
(1)
The smaller the edge-cut ratio, the fewer edges are cut. An edgecut ratio of 0 indicates that no edges are cut (good), and an edge-cut ratio of 1 indicates that all edges are cut (bad). The vertex balance of a partitioning 𝑃 is defined as: 𝐵 𝑣 (𝑃) =
max (|𝑃1 |, . . . , |𝑃𝑘 |) . mean(|𝑃1 |, . . . , |𝑃𝑘 |)
(2)
The vertex balance is between 1 and 𝑘. The closer the balance to 1, the better. A balance of 1 indicates that all partitions have the same number of vertices (good), and a balance of 𝑘 indicates that one partition contains all vertices while the other partitions are empty (bad).
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
1
3
Graph partitioning as pre-processing step
0 2
1
4
3
6
5
Distributed GNN training (GraphSage, etc.)
2 Select GNN hyper-parameter
7
Graph
0
1
4
5
4
5 Model evaluation
2
3
Partition 1
6
Down-stream Tasks
7
Partition 2
Hyper-parameter search
Figure 3: Distributed GNN training pipeline: 1 the input graph is partitioned into 𝑘 partitions; 2 hyperparameters for the GNN are selected; 3 the model is trained in a distributed fashion; 4 the model is evaluated; repeat 3 - 4 with the next hyperparameter set; 5 once the final model is trained, it is applied to downstream tasks. 2.1.2 Partitioning goal. The goal of graph partitioning for distributed GNN training is two-fold: (i) minimizing the number of cut edges (edge-cut-ratio) and (ii) balancing the number of vertices across machines (vertex balance). In distributed GNN training, these partitioning objectives directly impact system performance. Cut edges induce inter-machine communication during message passing, as feature vectors and intermediate representations must be exchanged across partitions. At the same time, the computational cost and GPU memory footprint of GNN training scale with the number of local vertices, since features and intermediate representations must be stored and processed per vertex. Therefore, well-balanced partitions are essential to avoid stragglers and memory bottlenecks, while minimizing cut edges reduces communication overhead.
2.1.3 Partitioner types. Graph partitioners can broadly be categorized into two classes: in-memory graph partitioners and streaming graph partitioners. In-memory graph partitioning algorithms load the entire graph into memory before performing the partitioning. This approach allows to operate with a global view of the graph structure, which typically leads to high-quality partitions (less cut edges) but comes at the cost of significant memory requirements and limited scalability for very large graphs. In contrast, streaming graph partitioners process the graph in a sequential manner, assigning vertices or edges to partitions as they arrive in the stream. Since they do not have access to the full graph at once, these methods rely only on local or partial information when making assignment decisions. While this constraint can lead to lower-quality partitions (more cut edges) compared to in-memory methods, streaming partitioners are considerably more scalable and can handle graphs that are too large to fit into memory, making them attractive for large-scale graph processing scenarios. The traditional distinction between in-memory and streaming partitioners lies in whether they have access to the full graph structure. EmbedPart is largely orthogonal to this distinction. Since partitioning is performed on dense node embeddings rather than directly on the graph topology, EmbedPart does not require a global or incremental view of the graph structure during the partitioning step. Instead, structural information is implicitly encoded in the node embeddings through the message-passing operations performed during GNN training.
2.2
Graph Neural Network Training
Graph Neural Networks (GNNs) are a special type of neural network capable of performing deep learning on graph-structured data. They are widely used for different prediction tasks, such as node classification or link prediction. Let 𝐺 = (𝑉 , 𝐸) be a graph and 𝑥 𝑣 be the feature vector of vertex 𝑣. Let ℎ 𝑣(𝑙 ) be the representation of 𝑣 in layer 𝑙 and ℎ 𝑣(0) be the feature vector 𝑥 𝑣 . A GNN consists of 𝐿 layers, which are iteratively computed. In each GNN layer 𝑙, for a vertex 𝑣, the hidden representations of its neighboring vertices of the previous layer 𝑙 − 1 are aggregated to 𝑎 𝑣(𝑙 ) by applying an aggregation function (see Equation 3). Then, the representation of 𝑣 is updated based on 𝑎 𝑣(𝑙 ) and ℎ 𝑣(𝑙 −1) (see Equation 4). 𝑎 𝑣(𝑙 ) = AGGREGATE (𝑙 ) ({ℎ𝑢(𝑙 −1) | 𝑢 ∈ 𝑁 (𝑣)})
(3)
ℎ 𝑣(𝑙 ) = UPDATE (𝑙 ) (𝑎 𝑣(𝑙 ) , ℎ 𝑣(𝑙 −1) )
(4)
The main approaches to train GNNs are mini-batch and fullgraph training [3]. In mini-batch training, multiple mini-batches are sampled from the graph in each epoch, and each mini-batch leads to a model update. In contrast, in full-graph training, in each epoch, the model is updated only once based on the whole graph. A standard distributed GNN training pipeline is illustrated in Figure 3. It begins with partitioning the input graph across machines ( 1 ), followed by selecting a GNN architecture and corresponding hyperparameters, such as the number of layers or hidden dimensions ( 2 ). The selected model is then trained in a distributed manner ( 3 ) and evaluated by measuring the prediction performance with accuracy metrics ( 4 ). Based on the prediction performance, different hyperparameters or GNN variants may be explored in iterative retraining cycles. Once a satisfactory model is obtained, it is deployed for downstream tasks such as recommendation ( 5 ).
3
EmbedPart: Embedding-driven Partitioning
We propose an architecture for Embedding-driven Partitioning (EmbedPart). The key idea is to leverage node embeddings produced during the actual GNN training workload for graph partitioning. Rather than computing a partitioning as a separate preprocessing step, EmbedPart derives partitions from node embeddings produced during the actual GNN training workload. These
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
Phase 1: Embedding Computation
Phase 2: Clustering and Balancing
Node embeddings 0
Embedding Clustering
1
0 2
1 3
4 6
5 7
2
GNN Training (GraphSage, GAT, GCN, ...)
3
Migrate 4 to Cluster 2 for balancing 0
4
5
1
5
0 1
4
4
2
6
2
6
5
3
7
3
7
6
Cluster 1
Cluster 2
Cluster 1
Cluster 2
0
1
4
5
2
3
6
7
Partitioning
Partition 1
Partition 2
7
Input graph with attached feature vectors After graph partitioning the actual workload (GNN training) is continued with an improved data layout
Figure 4: EmbedPart overview: The input to EmbedPart is like in GNN training, a graph with features that are attached to nodes. In Phase 1, we train a GNN model (the actual workload) and get node embeddings. At any point, the process can transition to Phase 2, where clustering on the embeddings assigns nodes to clusters. To maintain balanced distributed training, nodes are migrated from overloaded to underloaded clusters such as node 4. The resulting clusters are then used for graph partitioning. Finally, the process returns to Phase 1 to continue GNN training with the improved data layout. embeddings are then clustered into 𝑘 partitions, followed by a lightweight balancing step to ensure that partitions satisfy vertex balancing constraints. Later on we show how this architecture can also be used for graph reordering. Algorithm 1 summarizes the overall procedure. Algorithm 1 EmbedPart Input: Graph 𝐺 = (𝑉 , 𝐸), number of partitions 𝑘, GNN architecture A, imbalance factors 𝛽𝑡𝑟𝑎𝑖𝑛 , 𝛽 𝑣𝑎𝑙 ,𝛽𝑟𝑒𝑠𝑡 migration policy M Output: Partition assignment 𝑃 : 𝑉 → {1, . . . , 𝑘} 1: E ← Phase1_TrainAndEmbed(𝐺, A) ⊲ Alg. 2 2: 𝑃 ← Phase2_ClusterAndBalance(E, 𝑘, 𝛽𝑡𝑟𝑎𝑖𝑛 , 𝛽 𝑣𝑎𝑙 , 𝛽𝑟𝑒𝑠𝑡 , M) ⊲ Alg. 3 3: return 𝑃
Algorithm 3 Phase 2: ClusterAndBalance Input: Embeddings E, number of partitions 𝑘, imbalance factors 𝛽𝑡𝑟𝑎𝑖𝑛 , 𝛽 𝑣𝑎𝑙 , 𝛽𝑟𝑒𝑠𝑡 , migration policy M Output: Partition assignment 𝑃 : 𝑉 → {1, . . . , 𝑘} 1: 𝑃 ← KMeans(E, 𝑘) (𝑖 ) 2: 𝑉𝑡𝑟𝑎𝑖𝑛 ← training vertices in partition 𝑖 (𝑖 ) 3: 𝑉𝑣𝑎𝑙 ← validation vertices in partition 𝑖 (𝑖 )
4: 𝑉𝑟𝑒𝑠𝑡 ← remaining vertices in partition 𝑖 (𝑖 )
5: while any |𝑉𝑡𝑟𝑎𝑖𝑛 | > 𝛽𝑡𝑟𝑎𝑖𝑛 · 6:
Migrate training vertices from overloaded to underloaded | partitions using M (𝑃, 𝑉𝑡𝑟𝑎𝑖𝑛 , 𝛽𝑡𝑟𝑎𝑖𝑛 · |𝑉train 𝑘 ) (𝑖 )
7: while any |𝑉𝑣𝑎𝑙 | > 𝛽 𝑣𝑎𝑙 · 8:
Algorithm 2 Phase 1: TrainAndEmbed Input: Graph 𝐺 = (𝑉 , 𝐸), GNN architecture A Output: Node embeddings E = {𝑒 𝑣 | 𝑣 ∈ 𝑉 } 1: Run the actual GNN workload on 𝐺 2: return E extracted from the GNN
Phase 2: Clustering and Balancing. In Phase 2 (Algorithm 3: ClusterAndBalance), the node embeddings (one embedding per node) are clustered into 𝑘 groups using clustering. We use K-Means clustering; however, also other clustering approaches can be used. The resulting clusters are interpreted as graph partitions. While
|𝑉val | 𝑘 do
Migrate validation vertices from overloaded to underloaded |𝑉 | partitions using M (𝑃, 𝑉𝑣𝑎𝑙 , 𝛽 𝑣𝑎𝑙 · 𝑘val ) (𝑖 )
Phase 1: Embedding Computation. In Phase 1 (Algorithm 2: TrainAndEmbed), we execute the actual GNN training workload and extract a node embedding 𝑒 𝑣 for each vertex 𝑣. These embeddings encode both node features and structural information from the local neighborhood and serve as input to the subsequent clustering phase to partition the graph.
9: while any |𝑉𝑟𝑒𝑠𝑡 | > 𝛽𝑟𝑒𝑠𝑡 · 10:
|𝑉train | do 𝑘
|𝑉rest | do 𝑘
Migrate remaining vertices from overloaded to underloaded | partitions using M (𝑃, 𝑉𝑟𝑒𝑠𝑡 , 𝛽𝑟𝑒𝑠𝑡 · |𝑉rest 𝑘 )
11: return 𝑃
K-Means always produces exactly 𝑘 partitions, it does not guarantee balance, and some partitions may contain significantly more vertices than others. Such imbalance can slow down distributed GNN training, as workers assigned to overloaded partitions become stragglers, forcing other workers to wait and overloaded partitions may exceed memory capacity on the assigned machine, leading to out-of-memory errors [37]. To address this, we apply a rebalancing procedure that migrates vertices from overloaded to underloaded partitions according to a migration policy M (Algorithm 4). We propose a highly scalable migration policy, though it can easily be replaced by more sophisticated alternatives. Our policy ensures that the vertex balance (see Equation 2) does not exceed a given threshold 𝛽.
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
Algorithm 4 Migration policy M: Random migration proportional to free capacity Input: Partition assignment 𝑃, candidate node set S, capacities 𝐶𝑖 for each partition 𝑖 Output: Updated assignment 𝑃 1: Compute current loads 𝐿𝑖 = |{𝑣 ∈ S | 𝑃 (𝑣) = 𝑖}| 2: Identify overloaded partitions 𝑂 = {𝑖 | 𝐿𝑖 > 𝐶𝑖 } and underloaded partitions 𝑈 = {𝑖 | 𝐿𝑖 < 𝐶𝑖 } 3: Compute free capacity 𝑓𝑖 = 𝐶𝑖 − 𝐿𝑖 for 𝑖 ∈ 𝑈 and probabilities Í 𝑝𝑖 = 𝑓𝑖 / 𝑢 ∈𝑈 𝑓𝑢 4: for each 𝑖 ∈ 𝑂 do 5: Select 𝑚𝑖 = 𝐿𝑖 − 𝐶𝑖 nodes 𝑖 with smallest degree in 𝑂 6: for each selected node 𝑣 do 7: Sample destination 𝑖 ∈ 𝑈 with probability 𝑝𝑖 8: Reassign: 𝑃 (𝑣) ← 𝑖 9: return 𝑃
First, we compute the maximum number of vertices allowed per partition such that the vertex-balance constraint is satisfied. Based on this limit, we identify the set of overloaded partitions 𝑂 and underloaded partitions 𝑈 , and compute (i) the number of vertices that must be migrated from each partition in 𝑂 and (ii) the remaining capacity of each partition in 𝑈 . For each partition in 𝑂, we then select the required number of vertices to migrate. Each selected vertex is assigned to a target partition in 𝑈 by sampling from 𝑈 with probability proportional to the available capacity. One question is which vertices to migrate from overloaded partitions. In EmbedPart, the vertices with the smallest degree from each overloaded partition are selected. The intuition is that migrating low-degree vertices reduces the likelihood of increasing the edge cut, as these vertices are connected to fewer neighbors. For example, migrating a vertex with degree three can only lead to three more cut edges, a high-degree vertex, however, can lead to many more cut edges.
3.1
Design Considerations and Extensions
The architecture of EmbedPart offers several practical advantages that make it broadly applicable. We discuss these design considerations and extensions below. Modularity. Each component of EmbedPart, embedding computation, clustering, and migration for balancing, can be independently replaced or enhanced. This modularity enables EmbedPart to be adaptable to various workloads and easily extended with new techniques. Dynamic graphs. EmbedPart naturally supports dynamic graphs. Thanks to the inductive nature of GNN models, embeddings for newly added or modified nodes can be computed without requiring the retraining of the entire model. This property enables efficient partition updates in settings where the underlying graph evolves over time. Re-partitioning. EmbedPart also supports re-partitioning when system resources or training requirements change. Since partitioning is fast, the number of partitions can be adjusted dynamically, for example, to scale in or out. This flexibility is particularly important because memory consumption in GNN training depends strongly
on the model architecture and hyperparameters (e.g., number of layers, feature size, and hidden dimension), and hyperparameter search may require different memory budgets across configurations, which in turn can change the number of machines needed. Model reuse and multi-model support. Node embeddings generated with a specific GNN model can be used for partitioning and training other models. For example, embeddings obtained with GraphSAGE can be used to partition the graph for later training a graph attention network (GAT). Similarly, embeddings from a model trained for link prediction can be repurposed to partition graphs for node classification. Beyond partitioning: graph reordering. Finally, EmbedPart can also be applied to graph reordering for single-machine GNN training. Graph reordering improves cache locality and reduces training runtime, showing that EmbedPart has utility beyond distributed GNN training.
4
Evaluation
In the following, we evaluate EmbedPart with respect to partitioning quality metrics, partitioning run-time, and distributed GNN training performance. Then, we evaluate EmbedPart with regard to graph reordering quality metrics and single-machine GNN training performance. Implementation. We implemented EmbedPart with the stateof-the-art GNN system Deep Graph Library (DGL) [52] to train GNN models (Phase 1) and use K-Means clustering with Facebook AI Similarity Search (FAISS) [10] to cluster node embeddings (Phase 2). K-Means uses sampling-based clustering, meaning that the KMeans centroids are computed based on a sample of all embeddings. We found that 29 embeddings per cluster lead to good quality. Baselines. We compare EmbedPart with state-of-the-art gaph partitioning approaches: We perform in-memory partitioning with Metis [21] and Spinner [32], streaming partitioning with Ldg [48], buffered streaming partitioning with Cuttana [17], and random partitioning as a baseline. GNN architectures. We train two state-of-the-art models, GraphSage [18] and Graph attention networks (GAT) [49], as they are commonly used for distributed GNN training [15, 37, 60]. We perform both node and link prediction tasks. Evaluation platform. We use 4 servers equipped with an NVIDIA L40S GPU (Ada Lovelace Architecture, 48 GB GDDR6 with ECC), an AMD EPYC GENOA 9454P 48-core processor, and 768 GB of main memory each. Datasets. We selected different real-world graphs for our evaluations: arxiv, papers100M, and products from the Open Graph Benchmark (OGB) [20] and reddit from the Deep Graph Library (DGL) [52]. The graphs are shown in Table 1 along with different graph properties. Naming. We emphasize that EmbedPart is an architecture for building embedding-driven graph partitioners, rather than a single partitioning algorithm. The actual partitioner instance depends on the underlying GNN architecture it was trained on. In the following, we use the naming convention: partitioners trained on link prediction with two and three GNN layers are denoted as EmbedPart-l-2 and EmbedPart-l-3, respectively, while partitioners trained on node
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
Table 1: Evaluation graphs along with the number of vertices, number of edges, and mean degree. Graph
Vertices
Edges
Mean Deg.
#Epochs
arxiv
papers100M
products
arxiv reddit products papers100M
169,343 232,965 2,449,029 111,059,956
1,166,243 114,615,892 123,718,280 1,615,685,872
13.77 983.98 101.03 29.10
0 1 2 3 4 5 10 30 50 70 90
0.72 0.70 0.67 0.61 0.59 0.56 0.50 0.45 0.45 0.44 0.44
0.56 0.49 0.48 0.49 0.48 0.49 0.49 0.49 0.49 0.49 0.49
0.56 0.51 0.44 0.39 0.36 0.34 0.27 0.22 0.21 0.20 0.20
0.70 0.52 0.42 0.37 0.33 0.31 0.28 0.27 0.26 0.27 0.27
(vertex) prediction with two and three GNN layers are denoted as EmbedPart-v-2 and EmbedPart-v-3, respectively.
4.1
When Are Embeddings Good Enough?
A core advantage of EmbedPart is that it leverages the embeddings generated during the actual GNN training process, thus avoiding the cost of training a separate model solely for partitioning. However, this raises an important question: After how many GNN training epochs is the model useful for producing high-quality partitions? To answer this, we investigate the partitioning quality (measured by edge-cut ratio and enforcing a vertex balance smaller 1.05) when using node embeddings generated after varying numbers of GNN training epochs, both for node and link prediction tasks. The results are shown in Table 2a and 2b for node and link prediction, respectively. We summarize our key findings as follows:
Loss Accuracy
2
0.8
Accuracy
4 Loss
Table 2: Average edge-cut ratio (lower is better) after different numbers of GNN training epochs.
(a) Node prediction.
#Epochs
arxiv
papers100M
products
0 1 2 3 4 5 10 30 50 70 90
0.61 0.41 0.38 0.37 0.36 0.36 0.35 0.33 0.32 0.32 0.32
0.51 0.40 0.39 0.38 0.37 0.37 0.35 0.34 0.34 0.34 0.35
0.55 0.39 0.27 0.22 0.19 0.17 0.15 0.14 0.14 0.14 0.15
0.70 0.40 0.33 0.33 0.31 0.32 0.29 0.28 0.28 0.28 0.29
0.6 0
(b) Link prediction. 0
20
40
60
80
100
Epoch
Figure 5: Loss and accuracy for reddit over epochs. (1) Partitioning quality improves with more training. The edge-cut ratio decreases as the number of training epochs increases. After just 5 epochs, the quality is already quite good and after 30-50 epochs, it stabilizes and is close to the best achievable with our method. For example, the edge-cut ratio is heavily reduced for products from 0.56 to 0.21 for node prediction and from 0.55 to 0.14 for link prediction, respectively, when increasing the number of training epochs from 0 to 50. It is plausible that the edge-cut ratio is lower in the face of more training epochs. The more training epochs, the better the GNN in terms of prediction performance (accuracy), and also the more useful the embeddings produced by the model. This is shown in Figure 5 and was also observed for the remaining graphs: Even after a few training epochs, the validation loss decreases sharply and the accuracy of the GNN model is already quite high. However, at the beginning of our training workload, we do not have a trained GNN, meaning the parameters of the neural networks in the GNN are randomly initialized. In the following, we investigate how EmbedPart works with an untrained GNN.
(2) Even an untrained GNN (0 epochs) is beneficial. Remarkably, using an untrained GNN to generate initial embeddings produces significantly better partitions than random partitioning. This suggests that GNN architectures encode inductive biases that help preserve graph structure, even before training. Table 3a and Table 3b show the reduction of the edge-cut ratio achieved by an untrained GNN in percent compared to random partitioning, for node prediction and link prediction, respectively. Across all datasets and partition counts, we observe significant improvements: compared to random partitioning, the edge-cut ratio decreases by between 7.03% and 53.40%. These results point out a key strength of our method: even without additional training overhead, it can already provide substantial improvements over naive partitioning schemes. After just a few training epochs, the partitioning quality improves significantly, reaching competitive levels quickly. Since the embeddings are obtained as a natural byproduct of the actual GNN workload, our method incurs virtually no extra cost, making it both efficient and practical for real-world use.
Partitioning Performance
We evaluate the partitioning performance of EmbedPart by partitioning the graphs listed in Table 1 into 𝑘 ∈ {2, 4, 8, 16, 32} partitions and measure partitioning time and different partitioning quality metrics. The main observations are as follows: (1) Significant reduction in partitioning time. EmbedPart achieves drastic speedups over traditional in-memory partitioners and even outperforms streaming graph partitioning. Figure 6a gives an overview of the speedup of the partitioners over Metis over all graphs and the number of partitions. Figures 7a–7d show all numbers per graph and the number of partitions. On average, EmbedPart-l-2, EmbedPart-l-3, EmbedPartv-2, and EmbedPart-v-3 achieve speedups between 127.12× and 155.27× over Metis. Spinner is significantly slower, achieving only a speedup of 0.71× (i.e., a slowdown) relative to Metis. Among the streaming approaches, Ldg and Cuttana achieve speedups of 61.10× and 1.78× over Metis, respectively. Overall, EmbedPart exhibits the lowest partitioning time and is therefore well suited for dynamic or evolving graphs, where fast and repeated repartitioning is required. (2) Competitive partitioning quality. Despite its speed, EmbedPart delivers strong partitioning quality. It consistently achieves significantly lower edge cut ratios than random partitioning. Figure 6b shows how much the partitioners decrease the edge-cut ratio of random partitioning in percentages: On average Metis, Spinner, EmbedPart-l-3, EmbedPart-l-2, EmbedPart-v-3, EmbedPart-v-2, Cuttana, and Ldg, reduce the edge-cut ratio by 74.65%, 69.81%, 67.71%, 67.14%, 58.99%, 57.49%, 56.46%, and 42.14% EmbedPart-l-3 leads in 100%, 80%, 50%, and 25%, of all cases to a lower edge-cut ratio than Ldg, Cuttana, Spinner, and Metis, respectively. Therefore, EmbedPart is much faster in terms of partitioning time and competitive in terms of graph partitioning quality. For
Em
ER
is et M
SP IN N
TT AN A
G
G LD
TT AN A CU
be
be
SP
(b) Link prediction.
dP ar t-V -2
0
dP ar t-V -3
14.84
Em
33.89
be
39.50
20
L2
25.17
40
dP ar t-
Mean
60
Em
29.59 15.60 11.08 9.48 8.44
L3
48.74 37.20 32.10 27.75 23.67
be
52.76 53.40 40.04 28.45 22.83
Em
32.89 31.05 26.37 20.25 15.29
ER
2 4 8 16 32
80
dP ar t-
IN N
products
is
papers100M
et
arxiv
M
#Partitions
Edge-cut reduction
(a) Partitioning time speedup relative to Metis. Larger values indicate faster partitioning.
(a) Node prediction.
4.2
CU
14.17
LD
31.23
Pa rt -V -2
32.36
be d
11.13
Pa rt -V -3
Mean
100
Em
19.19 22.55 10.69 8.71 9.69
L3
37.90 37.49 32.63 25.82 22.30
t-
49.91 39.07 30.42 23.14 19.25
be d
10.55 14.81 13.53 9.73 7.03
Em
2 4 8 16 32
101
L2
t-
products
be dP ar
papers100M
Em
arxiv
be dP ar
#Partitions
102
Em
Table 3: Edge-cut ratio reduction by an untrained GNN compared to random partitioning in percentage. Larger is better.
Speedup over Metis
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
(b) Edge-cut reduction in % relative to random partitioning. Larger values indicate better partitioning quality.
Figure 6: Comparison of partitioning time speedups and edgecut reductions.
example, on the reddit dataset, EmbedPart outperforms both Metis and Spinner in certain configurations (see Figure 8b). Importantly, EmbedPart also provides an excellent balance of training vertices. It reliably respects the specified maximum imbalance ratio of 1.05, while Cuttana, Ldg and Spinner often violate this constraint. For instance, on arxiv, Cuttana, Ldg and Spinner yield training vertex imbalances of 1.4, 1.9 and 2.0 for 32 partitions, respectively and on products, they lead to imbalances of 1.9, 3.5 and 1.4 for 32 partitions, respectively. Similar trends are observed across the remaining datasets. We conclude that EmbedPart offers a good trade-off between partitioning speed and quality, making it a practical and scalable solution for partitioning large-scale graphs in modern distributed GNN training pipelines.
4.3
Distributed GNN Training Performance
To evaluate the impact of graph partitioning on distributed GNN training performance, we run experiments on a cluster of four GPU servers. We use Distributed Deep Graph Library (DistDGL) [52, 61] to train 2- and 3-layer GAT and GraphSAGE models on all graphs listed in Table 1, using 2 and 4 GPU servers. For graph partitioning, we use the same methods evaluated in the previous section: Metis, Spinner, Ldg, Cuttana, and our approach EmbedPart. We find that Metis, EmbedPart-v-3, EmbedPart-v-2, Spinner, EmbedPart-l-3, EmbedPart-l-2, Cuttana, and Ldg lead to average training speedups of 2.55×, 2.01×, 1.92×, 1.84×, 1.78×, 1.59×, 1.51×,
EmbedPart-L-3
EmbedPart-V-2
EmbedPart-V-3
LDG
Metis
SPINNER
random
2
4
8 #Partitions
16
0.697
0.085
0.019
0.084
0.081
0.824
0.085
0.896 0.001
0.485
0.054
0.014
0.055
0.052
0.587
0.054
0.575
0.001
0.385
0.039
0.011
0.037
0.033
0.495
0.039
0.518
0.001
0.385
0.025
0.009
0.028
0.024
0.465
0.026
0.001
0.357
0.328
0.029
0.007
0.028
0
0.026
1
0.438
2
1.381
EmbedPart-L-2
0.001
CUTTANA
0.029
Partitioning Time (s)
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
32
2
8 #Partitions
16
0.001
0.258
0.097
0.097
0.093
20.37
random 18.545
27.528
SPINNER
0.099
0.001
0.255
0.066
0.067
0.066
17.46
Metis 18.012
LDG
26.317 0.055
17.246 0.001
0.254
0.048
0.046
0.041
0.039
0.001
4
16.854
EmbedPart-V-3
26.164
EmbedPart-V-2 17.373
16.037
0.257
0.031
0.037
0.034
0.033
25.906
EmbedPart-L-3
0.001
15.759
15.053
0.258
0.067
0
0.067
20
0.061
40
EmbedPart-L-2
25.956
CUTTANA
0.061
Partitioning Time (s)
(a) arxiv.
32
2
16
0.007
43.155
random
23.729
0.541
0.336
0.358
0.308
54.662
SPINNER
0.313
37.104 0.008
0.456
0.245
0.24
0.205
8 #Partitions
Metis
22.617
LDG
54.685 0.216
0.007
31.665
0.408
0.19
0.199
0.171
0.171
0.008
4
23.041
EmbedPart-V-3
55.066
EmbedPart-V-2
26.597
21.634
0.374
0.207
0.202
0.136
0.146
54.421
EmbedPart-L-3
0.009
21.8
0.353
0.314
0
0.336
25
0.308
50
20.03
75
EmbedPart-L-2
54.425
CUTTANA
0.327
Partitioning Time (s)
(b) reddit.
32
2
4
8 #Partitions
16
random
0.356
4608.42
1892.57
24.383
19.606
19.938
15.577
616.813
SPINNER
15.121
0.356
4325.42
Metis
1548.97
19.826
15.791
16.663
LDG
10.304
240.525
10.61
0.356
3779.31
1494.13
EmbedPart-V-3
16.435
13.514
12.912
7.029
228.632
1262.09
14.474
11.053
10.575
5.787
232.149
6.311
0.357
2217.68
1111.12
12.875
10.361
10.225
0
8.333
2500
231.612
5000
EmbedPart-V-2
7.145
EmbedPart-L-3
0.356
EmbedPart-L-2
3048.54
CUTTANA 7500
7.581
Partitioning Time (s)
(c) products.
32
(d) papers100M.
Figure 7: Partitioning run-time on different graphs and number of partitions. Lower is better
and 1.41×, respectively (see Figure 9). More detailed numbers are shown in Figures 10a-10h for each graph. We observe that EmbedPart leads to competitive distributed GNN training performance and outperforms Spinner and Ldg in many cases. There are even cases where Metis is outperformed. These results underscore that EmbedPart provides an excellent trade-off between partitioning cost and training performance: it delivers good training performance at a fraction of the partitioning time, and substantially outperforms Ldg and Spinner in both speed and quality.
4.4
Robustness to Graph Updates
We now evaluate how well EmbedPart generalizes to updated graphs. In many real-world scenarios, graphs evolve over time. Let 𝐺𝑡 denote the state of the graph at time 𝑡. We have five subgraphs
𝐺 1, . . . , 𝐺 5 containing 10%, 30%, 50%, 70%, and 90% of the vertices of the full graph 𝐺, respectively. We train a GNN model for each graph 𝐺 1, . . . , 𝐺 5 and then apply each model directly to the full graph 𝐺 without any retraining to compute node embeddings for 𝐺, which are then used for graph partitioning. Then, we compare the achieved partitioning quality against a model that was trained directly on the full graph 𝐺. Table 4 shows the resulting edge-cut ratios. Our key observation is that the partitioning quality remains stable even as the graph changed significantly. For example, on products, training on 𝐺 2 (only 30% of 𝐺) yields an edge-cut of 0.23, which is very close to the 0.21 achieved when training directly on 𝐺. Similar trends hold across all datasets. While performance drops when training on 𝐺 1 (only 10% of 𝐺), results become robust when training on 30% or
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
4
0.969
0.457
0.654
random
0.431
0.694
16
0.68
0.471
0.493
SPINNER
0.47
0.938 0.4
0.631
Metis
0.336
0.596
8 #Partitions
0.586
0.318
0.573
0.28
0.475
0.459
0.32
0.378
0.322
0.75
0.219
0.431
0.199
0.328
2
0.314
0.269
0.335
0.268
0.501
0.141
0.245
0.166
0.174
0.0
0.168
0.169
0.136
0.5
LDG
0.384
EmbedPart-V-3
0.425
EmbedPart-V-2
0.415
EmbedPart-L-3
0.875
EmbedPart-L-2
1.0 0.144
Edge-cut ratio
CUTTANA 1.5
32
(a) arxiv.
2
4
8 #Partitions
16
0.969
0.517
0.679
random
0.571
0.401
0.477
0.439
SPINNER
0.459
0.342
0.937
0.392
0.612
Metis
0.385
0.335
0.343
0.301
0.596
0.265
0.276
0.238
0.235
0.251
0.245
0.75 0.159
0.437
0.187
0.144
0.222
0.177
0.207
0.198
0.5
0.11
0.358
0.115
0.136
0.0
0.126
0.138
0.144
0.5
LDG
0.305
EmbedPart-V-3
0.343
EmbedPart-V-2
0.29
EmbedPart-L-3
0.875
EmbedPart-L-2
1.0 0.118
Edge-cut ratio
CUTTANA 1.5
32
(b) reddit.
8 #Partitions
16
random
0.262
0.31
0.175
0.357
0.233
0.233
0.206
0.227
0.254
0.133
0.247
0.283
0.158
0.206
0.19
0.097
0.191
SPINNER
0.969
Metis
0.875
4
0.213
0.119
0.168
0.148
0.161
0.066
0.125
0.75
2
0.137
0.156
0.107
0.134
0.128
0.5
0.095
0.075
0.027
0.066
0.056
0.0
0.05
0.103
0.5
LDG
0.362
EmbedPart-V-3
0.937
EmbedPart-V-2
0.184
EmbedPart-L-3
0.161
EmbedPart-L-2
1.0 0.09
Edge-cut ratio
CUTTANA 1.5
32
(c) products.
2
4
8 #Partitions
16
0.969 0.33
0.802
random
0.271
0.716
0.713
0.564
0.828
SPINNER
0.504
0.938 0.277
0.771
Metis
0.227
0.633
0.875 0.228
0.711
0.176
0.507
0.487
0.307
0.73
0.295
0.75
0.164
0.6 0.12
0.373
0.377
0.259
0.615
0.257
0.5
0.104
0.393
0.055
0.228
0.0
0.215
0.5
LDG
0.652
EmbedPart-V-3
0.441
EmbedPart-V-2
0.795
EmbedPart-L-3
0.434
EmbedPart-L-2
0.196
0.401
1.0
0.145
Edge-cut ratio
CUTTANA 1.5
32
(d) papers100M.
Figure 8: Partitioning quality metrics: Edge-cut ratio on different graphs and number of partitions. Lower is better.
Speedup
3 2 1
G LD
A TT AN
CU
dP ar
t-
L2
ER N Em be
SP IN
L3 t-
dP ar
t-V -2
Em be
dP ar
t-V -3 Em be
dP ar
Em be
M
et is
0
more, demonstrating the effectiveness of EmbedPart even under substantial graph updates. This observation is plausible. GNNs are inductive models, meaning they are capable of generalizing to unseen vertices as long as the structural patterns and feature distributions are similar. As a result, when a model was trained on an older version of the graph it is often sufficient to achieve high-quality embeddings for partitioning the latest graph.
Figure 9: Speedup of partitioners over random partitioning. Larger is better.
4.5
Extension to Graph Reordering
While EmbedPart is primarily designed for distributed GNN training, we also demonstrate how to use it as an effective optimization to accelerate single-machine GNN training through graph reordering. Graph reordering is a data layout optimization with the goal of improving data locality by placing vertices accessed together close by in memory. The IDs of vertices are used as the position in
Speedup
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
2
0
2
4 #GPUs
Speedup
(a) 2-Layer GNN on arxiv. CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
2
0
2
4
Table 4: Average edge-cut ratio (lower is better) when training on different graph snapshots of 𝐺. The trained model is applied to the latest graph 𝐺 without retraining. Graph / size (%)
arxiv
papers100M
products
𝐺 1 / 10 𝐺 2 / 30 𝐺 3 / 50 𝐺 4 / 70 𝐺 5 / 90 𝐺 / 100
0.56 0.48 0.46 0.46 0.45 0.45
0.50 0.50 0.49 0.49 0.49 0.49
0.30 0.23 0.21 0.20 0.20 0.21
0.32 0.28 0.27 0.27 0.26 0.26
#GPUs
Speedup
(b) 3-Layer GNN on arxiv. CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
2
0
2
4 #GPUs
(c) 2-Layer GNN on reddit.
Speedup
2
CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
1 0
2
4
Speedup
#GPUs CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-3 (d) 3-Layer GNN on reddit. EmbedPart-V-2 LDG
Metis SPINNER
2
𝜉 𝜋 (𝑢, 𝑣) = |𝜋 (𝑢) − 𝜋 (𝑣)|
(5)
The larger the gap between two vertices, the more distant they are from each other in memory. The vertex bandwidth for a vertex 𝑣 ∈ 𝑉 is defined as the distance to the most distant neighbor of 𝑣:
5
0
memory. In graph reordering the IDs are relabeled (reordered) in a way that vertices accessed together get similar IDs and therefore are stored close by in memory. For GNN training, graph reordering is an effective because vertices iteratively aggregate information of neighboring vertices in the message passing phase (see Equation 3), meaning vertices access both features and intermediate embeddings of their neighbors [38]. According to [38], the reordering quality metric that correlates the most with training speedup is the average graph bandwidth, which we use for evaluation. It is defined in the following. Let 𝜋 : 𝑉 → 𝑉 be a bijection mapping vertices to their IDs. The gap between two vertices 𝑢, 𝑣 ∈ 𝑉 is defined as:
4 #GPUs
Speedup
(e) 2-Layer GNN on products. CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
𝛽 𝑣 (𝐺, 𝜋) = max{𝜉 𝜋 (𝑣, 𝑢) | ∀𝑢 ∈ 𝑛(𝑣)} Metis SPINNER
4
1 ∑︁ 𝛽b(𝐺, 𝜋) = 𝛽 𝑣 (𝐺, 𝜋). |𝑉 | 𝑣 ∈𝑉
2 0
2
4 #GPUs
Speedup
5.0
CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
2.5 0.0
2
4 #GPUs
(g) 2-Layer GNN on papers100M.
4
CUTTANA EmbedPart-L-2
EmbedPart-L-3 EmbedPart-V-2
EmbedPart-V-3 LDG
Metis SPINNER
2 0
2
(7)
The lower the average graph bandwidth the better the data locality in GNN training.
(f) 3-Layer GNN on products.
Speedup
(6)
Finally, the average graph bandwidth of graph 𝐺 is defined as:
4 #GPUs
(h) 3-Layer GNN on papers100M.
Figure 10: Achieved speedups for distributed GNN training on different graphs, number of GPUs, and number of GNN layers.
4.5.1 Adapting EmbedPart for Reordering. We adapt EmbedPart as follows to work for graph reordering: We reorder the graph such that vertices in the same partition get consecutive IDs. The intuition is that vertices are densely connected within partitions, while connections between partitions are less likely. This means that while a low edge-cut in distributed training reduces communication between machines, in single-machine training it reduces random memory accesses. However, there is one crucial difference between single-machine and distributed GNN training scenarios. In distributed GNN training, vertex balancing ensures that every worker gets a similar share of the graph in terms of memory and workload, e.g., because features and intermediate representations must be stored in memory for each vertex. In contrast, this is not the case for single-machine GNN training. Therefore, we also evaluate EmbedPart without enforcing the vertex balance constraint, which was otherwise maintained at ≤ 1.05 by our migration policy after the clustering phase. This has two advantages: First, we can skip the balancing step where
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
Table 5: Speedups through reordering for single-machine GNN training. Larger is better. OOM indicates out-of-memory errors.
Strategy
arxiv
products
Cuttana Ldg Metis Spinner EmbedPart-l-3 EmbedPart-l-3-u EmbedPart-v-3 EmbedPart-v-3-u EmbedPart-l-2 EmbedPart-l-2-u EmbedPart-v-2 EmbedPart-v-2-u
1.029 1.037 0.989 1.003 1.025 1.044 1.002 0.993 1.026 1.011 1.024 1.019
1.149 1.127 1.161 1.127 1.147 1.165 1.109 1.148 1.149 1.162 1.134 1.142
CPU reddit 1.110 1.145 1.175 1.136 1.147 1.186 1.147 1.212 1.136 1.171 1.146 1.160
papers100M
arxiv
products
0.951 1.022 0.935 0.955 0.954 1.017 1.016 0.998 1.010 0.995 0.990 0.957
1.001 1.002 1.002 1.000 1.001 1.000 0.999 0.999 1.001 1.001 1.001 1.000
2.052 2.021 2.077 2.018 1.995 2.074 1.948 2.047 2.011 2.073 1.994 2.045
GPU reddit 1.026 1.007 1.011 1.011 1.013 1.022 1.024 1.018 1.009 1.021 1.009 1.020
papers100M OOM OOM OOM OOM OOM OOM OOM OOM OOM OOM OOM OOM
Table 6: Both the average graph bandwidth and edge-cut ratio are better (lower) for the unbalanced EmbedPart.
Strategy
arxiv
Average graph bandwidth products reddit papers100M
arxiv
Edge-cut ratio products reddit papers100M
EmbedPart-l-3 EmbedPart-l-3-unbalanced EmbedPart-v-3 EmbedPart-v-3-unbalanced EmbedPart-l-2 EmbedPart-l-2-unbalanced EmbedPart-v-2 EmbedPart-v-2-unbalanced
74K 56K 79K 72K 71K 58K 79K 72K
1022K 659K 1196K 875K 1025K 765K 1124K 925K
0.471 0.360 0.680 0.619 0.470 0.356 0.694 0.647
0.233 0.162 0.357 0.269 0.233 0.168 0.362 0.313
154K 124K 151K 123K 154K 129K 155K 131K
vertices are migrated from overloaded to underloaded partitions. Second, the migration step reduces graph partitioning and graph reordering quality (edge-cut ratio and average graph bandwidth) because migrated vertices lead to higher edge-cut ratio and higher average graph bandwidth which will be shown in the following.
4.5.2 Experimental Results. In the following we analyse training speedups and graph reordering quality. Training Speedup. Table 5 reports the observed GNN training speedups achieved through graph reordering for CPU- and GPU-based training. We find that EmbedPart is effective for graph reordering in both CPU-based and GPU-based training. For CPU-based training, EmbedPart achieves speedups up to 1.212×, outperforming all baselines on arxiv, products, and reddit. For GPU-based training, we observe substantial improvements by graph reordering primarily on the products dataset. Here, Metis achieves the highest speedup of 2.077×, which is nearly identical to the 2.074× speedup achieved by EmbedPart (EmbedPartl-2-unbalanced). On the remaining datasets, GPU speedups are more modest, with most graph reordering strategies yielding only marginal improvements. Reordering Quality. To understand the performance improvements, Table 6 shows both the average graph bandwidth and edgecut ratio for balanced and unbalanced variants of EmbedPart. We
57594K 38407K 61468K 44247K 55970K 39413K 61169K 44830K
0.477 0.372 0.401 0.293 0.459 0.376 0.439 0.331
0.564 0.286 0.716 0.271 0.504 0.307 0.713 0.311
find that removing the balance constraint drastically improves reordering quality (lower is better for both metrics). For average graph bandwidth on products, the unbalanced versions reduce from 1022K, 1196K, 1025K, and 1124K to 659K, 875K, 765K, and 925K for EmbedPart-l-3, EmbedPart-v-3, EmbedPart-l2, and EmbedPart-v-2, respectively, representing improvements of 35%, 27%, 25%, and 18%. A similar trend is observed across all graphs. Similarly, we observe substantial decreases in edge-cut ratio on products from 0.233, 0.357, 0.233, and 0.362 to 0.162, 0.269, 0.168, and 0.313 for EmbedPart-l-3, EmbedPart-v-3, EmbedPart-l-2, and EmbedPart-v-2, respectively. Furthermore, the unbalanced variants can significantly reduce partitioning time. For instance, the partitioning time of EmbedPartl-3 and EmbedPart-l-3-unbalanced is 15.6s and 7.8s on papers100M, respectively, corresponding to a 50% reduction in preprocessing overhead while simultaneously improving reordering quality since the migration phase is skipped and only clustering is performed. Takeaway. Although EmbedPart is not optimized specifically for graph reordering, it achieves the best performance in most cases for CPU-based GNN training, while being substantially faster than competing methods. This demonstrates the broader applicability and versatility of our embedding-based partitioning approach beyond distributed GNN training alone. It also highlights the advantages of our modular architecture, where we can replace or
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
skip different phases depending on the use case. For example, completely skipping the migration phase for balancing is effective for single-machine GNN training where balance is not as critical as in distributed GNN training, resulting in both better quality partitions and reduced preprocessing time.
5
Discussion
Embedding Reuse in Iterative ML Workflows. Model development in machine learning typically involves systematic hyperparameter optimization and model selection, which require evaluating multiple configurations of architectures [5, 45]. In the context of GNNs, exploring different layer depths, hidden dimensions, or training parameters can substantially affect memory consumption and computational demand, potentially changing the number of machines required for distributed training [37]. In addition, models are often retrained due to data drift [14]. Consequently, GNN training is rarely a one-shot process. EmbedPart is designed for such iterative settings. Once available, node embeddings can be reused to derive updated partitionings, enabling fast repartitioning when scaling resources up or down or retraining on updated data. Flexible Balancing Policies. The migration-based balancing step is lightweight and modular. Balancing objectives can be adapted by assigning weights to vertices, and different imbalance thresholds can be incorporated without modifying the overall architecture. In our evaluation, we follow common practice in graph partitioning literature and enforce balance with respect to the number of vertices [6].
6
Related Work
Graph Partitioning for Distributed Processing. Graph partitioning is a long-standing and vibrant area of research for optimizing distributed graph processing. A wide range of partitioning algorithms has been proposed [17, 19, 21, 32–34, 48, 63]. Many works have shown that graph partitioning can speed up distributed graph processing workloads such as PageRank, Shortest Paths, Connected Components [1, 16, 22, 36, 39, 50]. More recently, it has also been demonstrated that graph partitioning can substantially accelerate distributed GNN training [37]. Our work fundamentally differs from prior partitioning work. Existing methods rely on graph structure, which is highly irregular and difficult to process efficiently and treat partitioning as a separate pre-processing step. We instead partition based on dense node embeddings that are naturally generated as part of the actual GNN training workload which can be performed highly efficiently. We view this embedding-driven perspective as a new research direction that enables further opportunities for optimization. Graph Reordering for Single-machine Processing. Graph reordering is a data management optimization that improves data locality by placing frequently accessed vertices close together in memory, thus improving cache utilization. Prior work has shown its effectiveness for single-machine graph processing of classical analytics workloads [4, 56], and more recently for single-machine GNN training [38, 58]. In our work, we demonstrate that EmbedPart can also be applied to graph reordering, further broadening its applicability.
System for Graph Neural Network Training. Many specialized systems [2, 13, 15, 27, 35, 41, 42, 44, 51–55, 57, 61, 62] have been proposed to support GNN training at scale. For our evaluation, we build upon one of the most widely used open-source systems, which also serves as the foundation for several subsequent GNN systems [15, 35]. Data Management Techniques for GNN Training. A complementary line of work investigates data management optimizations for GNN workloads [25, 29, 60], including sampling to reduce computation and communication overheads by training on subgraphs [7, 9, 18, 28, 46, 47], caching of frequently accessed data to mitigate I/O bottlenecks [26, 40, 41, 62], and compression and sparsification to reduce memory overhead and accelerate message passing [8, 12, 23, 31]. In contrast, we propose EmbedPart, an embedding-driven architecture for graph partitioning and reordering, providing a fresh perspective on these core data management optimizations.
7
Conclusions
We presented EmbedPart, an embedding-driven architecture for graph partitioning that shifts partitioning from graph topology to the dense embedding space produced during GNN training. By leveraging node embeddings that are already generated as part of the training workload, EmbedPart transforms graph partitioning into a scalable clustering problem over dense representations. Our evaluation shows that this design reduces partitioning time by more than two orders of magnitude compared to state-of-the-art in-memory partitioners while maintaining competitive partitioning quality and distributed GNN training performance. At the same time, the approach naturally supports dynamic graphs, fast repartitioning, and can also be applied to graph reordering to accelerate single-machine GNN training. More broadly, our work highlights the potential of embeddingdriven data management techniques that leverage learned representations to guide system-level optimizations. As machine learning workloads increasingly operate on learned embeddings, these representations provide new opportunities for designing scalable and adaptive data layout strategies.
Acknowledgments This work is funded in part by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 438107855.
References [1] Zainab Abbas, Vasiliki Kalavri, Paris Carbone, and Vladimir Vlassov. 2018. Streaming Graph Partitioning: An Experimental Study. Proc. VLDB Endow. 11, 11 (July 2018), 1590–1603. doi:10.14778/3236187.3236208 [2] Xin Ai, Hao Yuan, Zeyu Ling, Qiange Wang, Yanfeng Zhang, Zhenbo Fu, Chaoyi Chen, Yu Gu, and Ge Yu. 2024. NeutronTP: Load-Balanced Distributed Full-Graph GNN Training with Tensor Parallelism. Proc. VLDB Endow. 18, 2 (Oct. 2024), 173–186. doi:10.14778/3705829.3705837 [3] Saurabh Bajaj, Hojae Son, Juelin Liu, Hui Guan, and Marco Serafini. 2024. Graph Neural Network Training Systems: A Performance Comparison of Full-Graph and Mini-Batch. Proc. VLDB Endow. 18, 4 (Dec. 2024), 1196–1209. doi:10.14778/ 3717755.3717776 [4] Vignesh Balaji and Brandon Lucia. 2018. When is Graph Reordering an Optimization? Studying the Effect of Lightweight Graph Reordering Across Applications and Input Graphs. In 2018 IEEE International Symposium on Workload Characterization (IISWC). 203–214. doi:10.1109/IISWC.2018.8573478 [5] James Bergstra and Yoshua Bengio. 2012. Random search for hyper-parameter optimization. J. Mach. Learn. Res. 13, null (Feb. 2012), 281–305.
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
[6] Ümit Çatalyürek, Karen Devine, Marcelo Faraj, Lars Gottesbüren, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Sebastian Schlag, Christian Schulz, Daniel Seemaier, and Dorothea Wagner. 2023. More Recent Advances in (Hyper)Graph Partitioning. ACM Comput. Surv. 55, 12, Article 253 (March 2023), 38 pages. doi:10.1145/3571808 [7] Qixuan Chen, Yuhang Song, Melissa Martinez, and Vasiliki Kalavri. 2025. RingSampler: GNN sampling on large-scale graphs with io_uring. In Proceedings of the 17th ACM Workshop on Hot Topics in Storage and File Systems (Boston, MA, USA) (HotStorage ’25). Association for Computing Machinery, New York, NY, USA, 52–60. doi:10.1145/3736548.3737829 [8] Yuhan Chen, Haojie Ye, Sanketh Vedula, Alex Bronstein, Ronald Dreslinski, Trevor Mudge, and Nishil Talati. 2023. Demystifying Graph Sparsification Algorithms in Graph Properties Preservation. Proc. VLDB Endow. 17, 3 (Nov. 2023), 427–440. doi:10.14778/3632093.3632106 [9] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 2019. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (Anchorage, AK, USA) (KDD ’19). Association for Computing Machinery, New York, NY, USA, 257–266. doi:10. 1145/3292500.3330925 [10] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre-Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. 2024. The Faiss library. (2024). arXiv:2401.08281 [cs.LG] [11] Vijay Prakash Dwivedi, Charilaos Kanatsoulis, Shenyang Huang, and Jure Leskovec. 2025. Relational Deep Learning: Challenges, Foundations and NextGeneration Architectures. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.2 (Toronto ON, Canada) (KDD ’25). Association for Computing Machinery, New York, NY, USA, 5999–6009. doi:10.1145/3711896.3736558 [12] Yangxin Fan, Haolai Che, and Yinghui Wu. 2025. Inference-Friendly Graph Compression for Graph Neural Networks. Proc. VLDB Endow. 18, 9 (May 2025), 3203–3215. doi:10.14778/3746405.3746438 [13] Zhenbo Fu, Xin Ai, Qiange Wang, Yanfeng Zhang, Shizhan Lu, Chaoyi Chen, Chunyu Cao, Hao Yuan, Zhewei Wei, Yu Gu, Yingyou Wen, and Ge Yu. 2025. NeutronTask: Scalable and Efficient Multi-GPU GNN Training with Task Parallelism. Proc. VLDB Endow. 18, 6 (Feb. 2025), 1705–1719. doi:10.14778/3725688.3725700 [14] João Gama, Indrundefined Žliobaitundefined, Albert Bifet, Mykola Pechenizkiy, and Abdelhamid Bouchachia. 2014. A survey on concept drift adaptation. ACM Comput. Surv. 46, 4, Article 44 (March 2014), 37 pages. doi:10.1145/2523813 [15] Swapnil Gandhi and Anand Padmanabha Iyer. 2021. P3: Distributed Deep Graph Learning at Scale. In 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21). USENIX Association, 551–568. https://www.usenix. org/conference/osdi21/presentation/gandhi [16] Gurbinder Gill, Roshan Dathathri, Loc Hoang, and Keshav Pingali. 2018. A Study of Partitioning Policies for Graph Analytics on Large-Scale Distributed Platforms. Proc. VLDB Endow. 12, 4 (Dec. 2018), 321–334. doi:10.14778/3297753.3297754 [17] Milad Rezaei Hajidehi, Sraavan Sridhar, and Margo Seltzer. 2024. CUTTANA: Scalable Graph Partitioning for Faster Distributed Graph Databases and Analytics. Proc. VLDB Endow. 18, 1 (Sept. 2024), 14–27. doi:10.14778/3696435.3696437 [18] William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Long Beach, California, USA) (NIPS’17). Curran Associates Inc., Red Hook, NY, USA, 1025–1035. [19] Loc Hoang, Roshan Dathathri, Gurbinder Gill, and Keshav Pingali. 2021. CuSP: A Customizable Streaming Edge Partitioner for Distributed Graph Analytics. SIGOPS Oper. Syst. Rev. 55, 1 (June 2021), 47–60. doi:10.1145/3469379.3469385 [20] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 (2020), 22118–22133. [21] George Karypis and Vipin Kumar. 1996. Parallel multilevel k-way partitioning scheme for irregular graphs. In Proceedings of the 1996 ACM/IEEE Conference on Supercomputing (Pittsburgh, Pennsylvania, USA) (Supercomputing ’96). IEEE Computer Society, USA, 35–es. doi:10.1145/369028.369103 [22] Iacovos G. Kolokasis and Polyvios Pratikakis. 2019. Cut to Fit: Tailoring the Partitioning to the Computation. In Proceedings of the 2nd Joint International Workshop on Graph Data Management Experiences Systems (GRADES) and Network Data Analytics (NDA) (Amsterdam, Netherlands) (GRADES-NDA’19). Association for Computing Machinery, New York, NY, USA, Article 9, 10 pages. doi:10.1145/3327964.3328498 [23] Dongyue Li, Tao Yang, Lun Du, Zhezhi He, and Li Jiang. 2021. AdaptiveGCN: Efficient GCN Through Adaptively Sparsifying Graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (Virtual Event, Queensland, Australia) (CIKM ’21). Association for Computing Machinery, New York, NY, USA, 3206–3210. doi:10.1145/3459637.3482049 [24] Shuangli Li, Jingbo Zhou, Tong Xu, Liang Huang, Fan Wang, Haoyi Xiong, Weili Huang, Dejing Dou, and Hui Xiong. 2021. Structure-aware Interactive
Graph Neural Networks for the Prediction of Protein-Ligand Binding Affinity. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining (Virtual Event, Singapore) (KDD ’21). Association for Computing Machinery, New York, NY, USA, 975–985. doi:10.1145/3447548.3467311 [25] Ningyi Liao, Siqiang Luo, Xiaokui Xiao, and Reynold Cheng. 2025. Advances in Designing Scalable Graph Neural Networks: The Perspective of Graph Data Management. In Companion of the 2025 International Conference on Management of Data (Berlin, Germany) (SIGMOD/PODS ’25). Association for Computing Machinery, New York, NY, USA, 844–850. doi:10.1145/3722212.3725634 [26] Zhiqi Lin, Cheng Li, Youshan Miao, Yunxin Liu, and Yinlong Xu. 2020. PaGraph: Scaling GNN training on large graphs via computation-aware caching. In Proceedings of the 11th ACM Symposium on Cloud Computing (Virtual Event, USA) (SoCC ’20). Association for Computing Machinery, New York, NY, USA, 401–415. doi:10.1145/3419111.3421281 [27] Renjie Liu, Yichuan Wang, Xiao Yan, Haitian Jiang, Zhenkun Cai, Minjie Wang, Bo Tang, and Jinyang Li. 2025. DiskGNN: Bridging I/O Efficiency and Model Accuracy for Out-of-Core GNN Training. Proc. ACM Manag. Data 3, 1, Article 34 (Feb. 2025), 27 pages. doi:10.1145/3709738 [28] Xin Liu, Mingyu Yan, Lei Deng, Guoqi Li, Xiaochun Ye, and Dongrui Fan. 2022. Sampling Methods for Efficient Training of Graph Convolutional Networks: A Survey. IEEE/CAA Journal of Automatica Sinica 9, 2 (February 2022), 205–234. doi:10.1109/JAS.2021.1004311 [29] Xin Liu, Mingyu Yan, Lei Deng, Guoqi Li, Xiaochun Ye, Dongrui Fan, Shirui Pan, and Yuan Xie. 2022. Survey on Graph Neural Network Acceleration: An Algorithmic Perspective. In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, Lud De Raedt (Ed.). International Joint Conferences on Artificial Intelligence Organization, 5521–5529. doi:10. 24963/ijcai.2022/772 Survey Track. [30] Mingxuan Lu, Zhichao Han, Susie Xi Rao, Zitao Zhang, Yang Zhao, Yinan Shan, Ramesh Raghunathan, Ce Zhang, and Jiawei Jiang. 2022. BRIGHT - Graph Neural Networks in Real-time Fraud Detection. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management (Atlanta, GA, USA) (CIKM ’22). Association for Computing Machinery, New York, NY, USA, 3342–3351. doi:10.1145/3511808.3557136 [31] Yuxin Ma, Ping Gong, Tianming Wu, Jiawei Yi, Chengru Yang, Cheng Li, Qirong Peng, Guiming Xie, Yongcheng Bao, Haifeng Liu, and Yinlong Xu. 2024. Eliminating Data Processing Bottlenecks in GNN Training over Large Graphs via Two-level Feature Compression. Proc. VLDB Endow. 17, 11 (July 2024), 2854–2866. doi:10.14778/3681954.3681968 [32] Claudio Martella, Dionysios Logothetis, Andreas Loukas, and Georgos Siganos. 2017. Spinner: Scalable Graph Partitioning in the Cloud. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 1083–1094. doi:10.1109/ ICDE.2017.153 [33] Ruben Mayer and Hans-Arno Jacobsen. 2021. Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory Constraints. In Proceedings of the 2021 International Conference on Management of Data (Virtual Event, China) (SIGMOD ’21). Association for Computing Machinery, New York, NY, USA, 1289–1302. doi:10.1145/3448016.3457300 [34] Ruben Mayer, Kamil Orujzade, and Hans-Arno Jacobsen. 2022. Out-of-Core Edge Partitioning at Linear Run-Time . In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE Computer Society, Los Alamitos, CA, USA, 2629–2642. doi:10.1109/ICDE53745.2022.00242 [35] Vasimuddin Md, Sanchit Misra, Guixiang Ma, Ramanarayan Mohanty, Evangelos Georganas, Alexander Heinecke, Dhiraj Kalamkar, Nesreen K. Ahmed, and Sasikanth Avancha. 2021. DistGNN: Scalable Distributed Training for Large-Scale Graph Neural Networks. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (St. Louis, Missouri) (SC ’21). Association for Computing Machinery, New York, NY, USA, Article 76, 14 pages. doi:10.1145/3458817.3480856 [36] Nikolai Merkel, Ruben Mayer, Tawkir Ahmed Fakir, and Hans-Arno Jacobsen. 2023. Partitioner Selection with EASE to Optimize Distributed Graph Processing. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). 2400–2414. doi:10.1109/ICDE55515.2023.00185 [37] Nikolai Merkel, Daniel Stoll, Ruben Mayer, and Hans-Arno Jacobsen. 2025. An Experimental Comparison of Partitioning Strategies for Distributed Graph Neural Network Training. In Proceedings 28th International Conference on Extending Database Technology, EDBT 2025, Barcelona, Spain, March 25-28, 2025. OpenProceedings.org, 171–184. doi:10.48786/EDBT.2025.14 [38] Nikolai Merkel, Pierre Toussing, Ruben Mayer, and Hans-Arno Jacobsen. 2024. Can Graph Reordering Speed Up Graph Neural Network Training? An Experimental Study. Proc. VLDB Endow. 18, 2 (Oct. 2024), 293–307. doi:10.14778/3705829. 3705846 [39] Anil Pacaci and M. Tamer Özsu. 2019. Experimental Analysis of Streaming Algorithms for Graph Partitioning. In Proceedings of the 2019 International Conference on Management of Data (Amsterdam, Netherlands) (SIGMOD ’19). Association for Computing Machinery, New York, NY, USA, 1375–1392. doi:10.1145/3299869.3300076
Nikolai Merkel, Ruben Mayer, Volker Markl, and Hans-Arno Jacobsen
[40] Jeongmin Brian Park, Vikram Sharma Mailthody, Zaid Qureshi, and Wen-mei Hwu. 2024. Accelerating Sampling and Aggregation Operations in GNN Frameworks with GPU Initiated Direct Storage Accesses. Proc. VLDB Endow. 17, 6 (Feb. 2024), 1227–1240. doi:10.14778/3648160.3648166 [41] Yeonhong Park, Sunhong Min, and Jae W. Lee. 2022. Ginex: SSD-enabled billionscale graph neural network training on a single machine via provably optimal in-memory caching. Proc. VLDB Endow. 15, 11 (July 2022), 2626–2639. doi:10. 14778/3551793.3551819 [42] Jingshu Peng, Zhao Chen, Yingxia Shao, Yanyan Shen, Lei Chen, and Jiannong Cao. 2022. Sancus: staleness-aware communication-avoiding full-graph decentralized training in large-scale graph neural networks. Proc. VLDB Endow. 15, 9 (may 2022), 1937–1950. doi:10.14778/3538598.3538614 [43] Michael Sejr Schlichtkrull, Thomas N. Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. 2018. Modeling Relational Data with Graph Convolutional Networks. In The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings (Lecture Notes in Computer Science, Vol. 10843), Aldo Gangemi, Roberto Navigli, Maria-Esther Vidal, Pascal Hitzler, Raphaël Troncy, Laura Hollink, Anna Tordai, and Mehwish Alam (Eds.). Springer, 593–607. doi:10.1007/978-3-319-93417-4_38 [44] Zeang Sheng, Wentao Zhang, Yangyu Tao, and Bin Cui. 2024. outre: An out-ofcore de-redundancy gnn training framework for massive graphs within a single machine. Proceedings of the VLDB Endowment 17, 11 (2024), 2960–2973. [45] Jasper Snoek, Hugo Larochelle, and Ryan P. Adams. 2012. Practical Bayesian optimization of machine learning algorithms. In Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2 (Lake Tahoe, Nevada) (NIPS’12). Curran Associates Inc., Red Hook, NY, USA, 2951–2959. [46] Yuhang Song, Po Hao Chen, Yuchen Lu, Naima Abrar, and Vasiliki Kalavri. 2024. In situ neighborhood sampling for large-scale GNN training. In Proceedings of the 20th International Workshop on Data Management on New Hardware (Santiago, AA, Chile) (DaMoN ’24). Association for Computing Machinery, New York, NY, USA, Article 11, 5 pages. doi:10.1145/3662010.3663443 [47] Zhen Song, Yu Gu, Tianyi Li, Qing Sun, Yanfeng Zhang, Christian S. Jensen, and Ge Yu. 2023. ADGNN: Towards Scalable GNN Training with AggregationDifference Aware Sampling. Proc. ACM Manag. Data 1, 4, Article 229 (Dec. 2023), 26 pages. doi:10.1145/3626716 [48] Isabelle Stanton and Gabriel Kliot. 2012. Streaming graph partitioning for large distributed graphs. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Beijing, China) (KDD ’12). Association for Computing Machinery, New York, NY, USA, 1222–1230. doi:10.1145/2339530.2339722 [49] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. 2017. Graph attention networks. stat 1050, 20 (2017), 10–48550. [50] Shiv Verma, Luke M. Leslie, Yosub Shin, and Indranil Gupta. 2017. An Experimental Comparison of Partitioning Strategies in Distributed Graph Processing. Proc. VLDB Endow. 10, 5 (Jan. 2017), 493–504. doi:10.14778/3055540.3055543 [51] Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman. 2023. MariusGNN: Resource-Efficient Out-of-Core Training of Graph Neural Networks. In Proceedings of the Eighteenth European Conference on Computer Systems (Rome, Italy) (EuroSys ’23). Association for Computing Machinery, New York, NY, USA, 144–161. doi:10.1145/3552326.3567501 [52] Minjie Yu Wang. [n. d.]. Deep Graph Library: towards efficient and scalable deep learning on graphs. ICLR Workshop on Representation Learning on Graphs and Manifolds ([n. d.]). https://par.nsf.gov/biblio/10311680 [53] Qiange Wang, Yao Chen, Weng-Fai Wong, and Bingsheng He. 2023. HongTu: Scalable Full-Graph GNN Training on Multiple GPUs. Proc. ACM Manag. Data 1, 4, Article 246 (Dec. 2023), 27 pages. doi:10.1145/3626733 [54] Qiange Wang, Yao Chen, Weng-Fai Wong, and Bingsheng He. 2023. HongTu: Scalable Full-Graph GNN Training on Multiple GPUs. Proc. ACM Manag. Data 1, 4, Article 246 (Dec. 2023), 27 pages. doi:10.1145/3626733 [55] Qiange Wang, Yanfeng Zhang, Hao Wang, Chaoyi Chen, Xiaodong Zhang, and Ge Yu. 2022. NeutronStar: Distributed GNN Training with Hybrid Dependency Management. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 1301–1315. doi:10.1145/3514221.3526134 [56] Hao Wei, Jeffrey Xu Yu, Can Lu, and Xuemin Lin. 2016. Speedup Graph Processing by Graph Ordering. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA) (SIGMOD ’16). Association for Computing Machinery, New York, NY, USA, 1813–1828. doi:10.1145/2882903.2915220 [57] Yidi Wu, Kaihao Ma, Zhenkun Cai, Tatiana Jin, Boyang Li, Chenguang Zheng, James Cheng, and Fan Yu. 2021. Seastar: vertex-centric programming for graph neural networks. In Proceedings of the Sixteenth European Conference on Computer Systems (Online Event, United Kingdom) (EuroSys ’21). Association for Computing Machinery, New York, NY, USA, 359–375. doi:10.1145/3447786.3456247 [58] Peiqi Yin, Xiao Yan, Jinjing Zhou, Qiang Fu, Zhenkun Cai, James Cheng, Bo Tang, and Minjie Wang. 2023. DGI: An Easy and Efficient Framework for GNN Model Evaluation. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (Long Beach, CA, USA) (KDD ’23). Association for
Computing Machinery, New York, NY, USA, 5439–5450. doi:10.1145/3580305. 3599805 [59] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. 2018. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (London, United Kingdom) (KDD ’18). Association for Computing Machinery, New York, NY, USA, 974–983. doi:10.1145/3219819.3219890 [60] Hao Yuan, Yajiong Liu, Yanfeng Zhang, Xin Ai, Qiange Wang, Chaoyi Chen, Yu Gu, and Ge Yu. 2024. Comprehensive Evaluation of GNN Training Systems: A Data Management Perspective. Proc. VLDB Endow. 17, 6 (Feb. 2024), 1241–1254. doi:10.14778/3648160.3648167 [61] Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis. 2020. Distdgl: distributed graph neural network training for billion-scale graphs. In 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3). IEEE, 36–44. [62] Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. 2019. AliGraph: a comprehensive graph neural network platform. Proc. VLDB Endow. 12, 12 (Aug. 2019), 2094–2105. doi:10.14778/3352063.3352127 [63] Michał Zwolak, Zainab Abbas, Sonia Horchidan, Paris Carbone, and Vasiliki Kalavri. 2022. GCNSplit: bounding the state of streaming graph partitioning. In Proceedings of the Fifth International Workshop on Exploiting Artificial Intelligence Techniques for Data Management (Philadelphia, Pennsylvania) (aiDM ’22). Association for Computing Machinery, New York, NY, USA, Article 3, 12 pages. doi:10.1145/3533702.3534920