## CDFGNN: a Systematic Design of Cache-based Distributed Full-Batch Graph Neural Network Training with Communication Reduction

Shuai Zhang Meituan Beijing, China zhangshuai122@meituan.com

## Zite Jiang

SKL Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing, China jiangzite19s@ict.ac.cn

Haihang You* SKL Computer Architecture, Institute of Computing Technology, Chinese Academy of Sciences Beijing, China youhaihang@ict.ac.cn

## Abstract

Graph neural network training is mainly categorized into mini-batch and full-batch training methods. The mini-batch training method samples subgraphs from the original graph in each iteration. This sampling operation introduces extra computation overhead and reduces the training accuracy. Meanwhile, the full-batch training method calculates the features and corresponding gradients of all vertices in each iteration, and therefore has higher convergence accuracy. However, in the distributed cluster, frequent remote accesses of vertex features and gradients lead to huge communication overhead, thus restricting the overall training efficiency.

send the features and gradients of vertices across devices in each iteration, which brings huge communication overhead. Therefore, designing an efficient heterogeneous distributed graph neural network training framework is a challenging and engaging research area.

In this paper, we introduce the cached-based distributed full-batch graph neural network training framework (CDFGNN). We propose the adaptive cache mechanism to reduce the remote vertex access by caching the historical features and gradients of neighbor vertices. Besides, we further optimize the communication overhead by quantifying the messages and designing the graph partition algorithm for the hierarchical communication architecture. Experiments show that the adaptive cache mechanism reduces remote vertex accesses by 63 14% on average. Combined with communica-. tion quantization and hierarchical GP algorithm, CDFGNN outperforms the state-of-the-art distributed full-batch training frameworks by 30 39% in our experiments. Our results . indicate that CDFGNN has great potential in accelerating distributed full-batch GNN training tasks.

Keywords: Graph Neural Network, Distributed Training, Machine Learning System

## 1 Introduction

With the rise of large-scale pre-training models, the demand for distributed training based on heterogeneous architecture is also increasing. As an important deep learning structure, graph neural network (GNN) [1] has been applied in natural language processing, computer vision, knowledge graphs, etc. Compared with traditional graph algorithms, the graph neural network often requires computation on heterogeneous devices. Besides, the graph neural network needs to

The training of distributed graph neural network can be categorized into full-batch training [1, 2] and mini-batch training [3-7]. The main difference between them is whether the entire graph data is involved in each iteration. For the full-batch training method, an iteration contains the model computation phase (including forward propagation and back propagation) and the parameter update phase. For mini-batch training, an additional sampling phase needs to be added. The sampling phase needs to be performed before the model computation phase and the parameter update phase. In the sampling phase, subgraphs are sampled from the entire graph for the current training iteration. Therefore, for the full-batch training, one training epoch is equivalent to one iteration. For the mini-batch training, one training epoch often consists of multiple iterations.

Manymini-batch (sample-based) distributed GNN training methods have been proposed recently. However, these minibatch training methods lead to problems such as information loss [8-10], additional sampling overhead [9], and unable to guarantee convergence [11]. Therefore, in this paper, we focus on another distributed training strategy: full-batch training.

Compared with traditional graph algorithms or deep learning algorithms, distributed full-batch graph neural network training brings new system-level problems. The GNN training process has irregular neighbor vertex access and iterative computation at the same time. Therefore, graph neural network training is also characterized by both memory access intensive and computing intensive tasks [12, 13]. In the distributed environment, there is also a problem of intensive communication for the full-batch training methods. During the full-batch GNN training, both the model parameters and neighbor vertex data (features and gradients) need to

be transmitted across the device. Due to the huge communication volume of vertex features and gradients, efficient full-batch GNN training is extremely difficult.

In this paper, we focus on reducing the communication overhead during distributed full-batch graph neural network training. Considering that the changes of model parameters during GNN training are usually very slight, we cache historical features and gradients of vertices to reduce the cross-device neighbor vertex access. In addition, we adopt the quantization method to compress communication messages. We further design the hierarchical graph partition algorithm to reduce the number of communication messages across physical nodes (at the expense of the extra messages across different GPUs within the same physical node).

Specifically, our main contributions are as follows:

- · We propose the c ache-based d istributed f ull-batch g raph n eural n etwork training method CDFGNN. By adaptively caching vertex-level historical features and gradients, we can greatly reduce the communication overhead without affecting the convergence accuracy and the number of iterations required for convergence.
- · We quantify the vertex features and gradients during communication in CDFGNN to further reduce communication overhead.
- · We design the graph partition algorithm to adapt to the communication characteristics of the hierarchical hardware architecture.
- · Experiments show that CDFGNN can greatly reduce the communication overhead during distributed fullbatch graph neural network training and thus improve the overall training efficiency.

This paper is organized as follows: Section 2 discusses the challenges of distributed GNN training and explains our motivation. Section 3 introduces the computation and communication architecture of CDFGNN. Section 4 proposes the adaptive cache mechanism for vertex features and gradients and theoretically proves the convergence of this mechanism. Section 5 and section 6 describes the quantization method and the hierarchical graph partition algorithm. Section 7 presents and analyzes several experiments, which demonstrate the characteristics and capabilities of CDFGNN. Finally, we review the related work, conclude our approach, and preview the future project in Section 8 and Section 9.

## 2 Background and Motivation

## 2.1 Background

The distributed full-batch GNN training methods require the original graph to be partitioned into several subgraphs, and each computing device (CPU or GPU) only keeps its own subgraph. The corresponding vertex features are also split

Figure 1. Distributed full-batch GNN Training.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-aa3d1445-88b9-4d37-b00d-be85426dc22d.jpg)

and assigned to each device. Thus, the computation of the entire graph can be completed in just one iteration.

During the training process, each computing device saves a copy of the current model parameters to enable local computation. Therefore, for the full-batch GNN training, the model parameter synchronization is also needed after each iteration.

For both GCN [1] and GAT [14] models, the vertex features and gradients of all neighbor vertices are required to calculate the features and gradients of the certain vertex during the forward and backward propagation in each layer. In distributed clusters, such large-scale cross-device data access brings serious communication overhead and becomes a bottleneck of the overall computation. Besides, load balancing among the various devices is also important. This is because load imbalance not only results in computational load imbalance, but also communication imbalance.

Figure 1 shows the training process of a distributed graph neural network with 6 vertices. Vertices on the same device (GPU) are represented by the same color, and red edges identify edges across GPUs.

The right side is the computational graph of the twolayer graph neural network for vertex 'B' and vertex 'D'. In order to obtain the final vertex features, 7 and 6 crossdevice communication messages are required for 'B' and 'D' respectively. Each message contains high-dimensional vertex features. When performing backward propagation, the same number of vertex gradients is also required. Therefore, cross-device communication becomes an important bottleneck for efficient training. The overall communication overhead may even account for about 80% of the total training time [8, 10, 15].

For the distributed mini-batch GNN training, we need to sample graphs before model computation. Thus, an iteration of distributed mini-batch training consists of three stages: sampling, model computation, and model parameter synchronization.

These mini-batches can be sampled by the computing device itself, or sampled by a dedicated sampling device. Each

computing device independently executes forward propagation and backward propagation on its corresponding subgraph. After the computation stage is completed, these computing devices synchronize and accumulate the gradients to update the model parameters.

Figure 2. The sample process of mini-batch training.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-cd33aa40-7bb8-427c-b0ac-09cbb6997235.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-d79ccb0f-8413-4594-b948-c2bde9db4975.jpg)

Figure 2 shows a 2-hop sampling process on the original graph. For the 𝐿 -layers graph neural network, in order to calculate the vertex features, (at least part of) L-hop neighbor vertices need to be included in the sampled subgraph. In figure 2, for calculating vertex 1, we additionally add parts of its 2-hop neighbor vertices to the subgraph. For graphs with high connectivity and small diameter (such as powerlaw graphs), even few vertices sampled will generate a large subgraph. This phenomenon results in significant extra computational overhead. Although we can restrict the maximum number of sampled neighbor vertices as in figure 2, it will directly reduce the model accuracy.

Compared with the full-batch distributed GNN training, the computation stage of mini-batch training is executed independently on sampled subgraphs, thus avoiding the remote vertex access. However, the sampling process also incurs additional computational overhead, including the sampling itself and extra vertex calculations. In addition, the mini-batch GNN training often reduces the model accuracy.

## 2.2 Motivation

The frequent and expensive remote neighbor vertex access restricts the scalability of distributed full-batch GNN training. To overcome this challenge, we can optimize it from the following perspectives:

- · Frequency : Cache neighbor vertex data instead of executing remote access in each iteration,
- · Expensive : Compress the message size,
- · Remote : Make full use of the hierarchical communication architecture.

For GNN training tasks, the model parameters tend to stabilize after several training epochs. Besides, the training process does not require high-precision vertex features and gradients before the model converges. Therefore, we cache

Figure 3. The workflow of CDFGNN.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-ed773583-dad2-413c-a7d9-b53ad452aff7.jpg)

and reuse historical vertex features and gradients during training to reduce communication overhead, especially in the middle stage of the training process.

In order to compress the message size, we quantify the communication messages. These messages include the model parameter gradients and remote neighbor vertex features and gradients. The scale of vertex features and gradients in the GNN training is much larger than the model parameters. Meanwhile, when there are small errors in the vertex features and gradients, the final convergence performance will not be significantly reduced, and sometimes it can even prevent the training process from falling into a local optimal solution. Therefore, we compress the vertex features and gradients during communication by quantifying.

Finally, we analyze the communication characteristics of heterogeneous clusters and find that using the PCIe to communicate between different GPUs in the same physical node is more efficient (higher bandwidth and lower latency) than network communication (InfiniBand) across physical nodes. Therefore, we propose a graph partition algorithm to reduce the number of messages across physical nodes at the cost of increasing communication within physical nodes.

## 3 CDFGNN Architecture

In this section, we take the graph convolutional network (GCN) as an example to describe the computation and communication stage of CDFGNN.

Figure 3 shows the overall computing and communication workflow of CDFGNN. CDFGNN first needs to perform the graph partitioning (GP) algorithm to partition the graph (and corresponding input features) into subgraphs equal to the number of computing devices (GPUs). Different from the traditional full-batch graph neural network training framework, we adopt the vertex-cut GP algorithm. The vertex-cut GP is considered a better approach to handle power-law graphs common in the real world [16, 17]. Figure 4 demonstrates

## Algorithm 1: CDFGNN Workflow

ˆ

Input: Graph 𝐺 𝑉,𝐸 ( ) , Sparse Matrix 𝐴 𝑖 , Input feature 𝐻 ( 0 ) 𝑖 , Current Model Parameter 𝑊 .

Output: Output Feature 𝐻 ( 𝐿 ) 𝑖 .

- 1 for all process 𝑃 𝑖 ( ) parallel do

$$\text{Output: Output Feature } H _ { i } ^ { ( L ) }. \quad \text{$1$} \\ \text{for all process } P ( i ) \text{ parallel} \, \text{do} \\ \left | \, \text{ // Layer-by-layer forward propagation:} \, \text{$i$} \\ \, \text{ for } l = 1, \cdots, L \, \text{do} \\ \, \left | \, \tilde { Z } _ { i } ^ { ( l ) } \leftarrow \tilde { A } _ { i } H _ { i } ^ { ( l - 1 ) } W ^ { ( l - 1 ) } \\ \, \left | \, \text{ Synchronize by communication to get } Z _ { i } ^ { ( l ) } \\ \, \right | \, \text{ } H _ { i } ^ { ( l ) } \leftarrow \sigma \left ( Z _ { i } ^ { ( l ) } \right ) \\ \, \text{ // Layer-by-layer backward propagation:} \\ \, \text{ Compute Loss Function } \mathcal { L } _ { i } \, \text{ and } \tilde { \delta } _ { i } ^ { ( L ) } \\ \, \text{ for } l = L, \cdots, 1 \, \text{do} \\ \, \left | \, \text{ Synchronize by communication to get } \tilde { \delta } _ { i } ^ { ( l ) }. \, \text{$1$} \\ \, \tilde { \delta } _ { i } ^ { ( l - 1 ) } \leftarrow \tilde { \delta } _ { i } ^ { ( l ) } \tilde { A } _ { i } \left ( W ^ { ( l - 1 ) } \right ) ^ { T } \cdot \sigma ^ { \prime } \left ( Z _ { i } ^ { ( l - 1 ) } \right ) ^ { l } \\ \, \text{ } \nabla _ { W ^ { ( l - 1 ) } \mathcal { L } _ { i } } \leftarrow \delta _ { i } ^ { ( l ) } \tilde { A } _ { i } \left ( H _ { i } ^ { ( l - 1 ) } \right ) ^ { T } \\ \, \text{ Parameter Server aggregate } \nabla _ { W ^ { ( l - 1 ) } \mathcal { L } _ { i } }, \, \text{ update} \\ \, \text{ and broadcast parameters:} \\ \, \text{ } W ^ { ( l - 1 ) } = W ^ { ( l - 1 ) } - \eta \sum _ { \nabla _ { W ^ { ( l - 1 ) } \mathcal { L } _ { i } } } ^ { p } \nabla _ { W ^ { ( l - 1 ) } \mathcal { L } _ { i } }$$

Parameter Server aggregate ∇ 𝑊 ( 𝑙 - ) 1 L 𝑖 , and broadcast parameters:

$$\Big \rfloor \ W ^ { ( l - 1 ) } = W ^ { ( l - 1 ) } - \eta \sum _ { i = 1 } ^ { p } \nabla _ { W ^ { ( l - 1 ) } } \mathcal { L } _ { i }$$

$$\Big | \quad \Big \rangle \ W ^ { ( l - 1 ) } = W ^ { ( l - 1 ) } - \eta \sum _ { i = 1 } ^ { \cdot } \nabla _ { W ^ { ( l - 1 ) } }$$

partition results of the vertex-cut GP algorithm. In this example, vertex 'B' exists in all 3 subgraphs and we choose one of these replicas as the master vertex while others as mirror vertices.

We describe the single iteration distributed training in the algorithm 1. 𝐿 refers to the number of layers of the GCN network, and the model parameters of each layer are represented as 𝑊 ( 0 ) , · · · , 𝑊 ( 𝐿 - ) 1 . Next, we describe the computation and communication stage in detail.

## 3.1 Computation Stage of CDFGNN

In the computation stage, each GPU independently performs graph neural network computation tasks on its corresponding subgraph. We use the BSP model [18] to achieve synchronization of vertex features through communication.

Let 𝐴 𝑖 be the adjacency matrix of subgraph 𝑖 and 𝐷 𝑖 be the corresponding submatrix in the original degree matrix. ˆ 𝐴 𝑖 = 𝐷 - / 1 2 𝑖 𝐴 𝐷 𝑖 - / 1 2 𝑖 is the normalized adjacency matrix of the subgraph in the computing device 𝑖 . We use superscript ¥ to represent the intermediate matrix values ( ¥ ( 𝑍 𝑙 ) 𝑖 and ¥ ( 𝛿 𝑙 - ) 1 𝑖 ) calculated only from local subgraphs, and the corresponding expressions without this superscript indicate the value ( 𝑍 ( 𝑙 ) 𝑖 and 𝛿 ( 𝑙 - ) 1 𝑖 ) after communication synchronization.

During the forward propagation of GCN, we calculate the vertex feature 𝐻 ( 𝑙 ) 𝑖 of the 𝑙 -th layer in the subgraph 𝑖 as

$$\ddot { Z } _ { i } ^ { ( l ) } = \hat { A } _ { i } H _ { i } ^ { ( l - 1 ) } W ^ { ( l - 1 ) }, \quad \quad ( 1 ) \quad \ \ u \colon$$

$$H _ { i } ^ { ( l ) } = \sigma \left ( Z _ { i } ^ { ( l ) } \right ). \text{ \quad \ \ } \text{(2)}$$

We calculate ¥ ( 𝑍 𝑙 ) 𝑖 with the local vertex feature 𝐻 ( 𝑙 - ) 1 𝑖 , local normalized adjacency matrix ˆ 𝐴 𝑖 and the global model parameter 𝑊 ( 𝑙 - ) 1 . For restoring the 'real' 𝑍 ( 𝑙 ) 𝑖 (the same as the value during the sequential training), we need to synchronize and aggregate ¥ ( 𝑍 𝑙 ) 𝑖 from each device through communication. The communication stage will be introduced in section 3.2.

According to 𝑍 ( 𝑙 ) 𝑖 , we can calculate the input 𝐻 ( 𝑙 ) 𝑖 of the next layer. 𝐻 ( 𝑙 ) 𝑖 ∈ R | 𝑉 𝑖 | × 𝐹 𝑖 , where 𝐹 𝑖 refers to the vertex feature dimension of the 𝑖 -th layer. By iteratively executing equations 1 and 2, we can complete the calculation of forward propagation layer by layer.

During the backward propagation, we only calculate the loss value of the master vertices when calculating the loss function L . Thus, we can avoid repeated calculations of gradients on multiple replicas.

We use L to represent the loss function in the global and

L 𝑖 to represent its component on subgraph 𝑖 , while 𝑝 ˝ 𝑖 = 1 L 𝑖 = ( )

$$\text{PCC} \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \sin \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \cos \, \tan \, \cos \, \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \, \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \osigma \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \, \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \cos \sin \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \sin \cos \osigma \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos \cos. \quad \text{(3)}$$

L . When calculating the gradient, we define 𝛿 𝑙 𝑖 = ∇ 𝑍 ( 𝑙 ) 𝑖 L to represent the gradient of the global loss function L with respect to the global variable 𝑍 ( 𝑙 ) 𝑖 , and ¥ ( 𝛿 𝑙 ) 𝑖 = ∇ ¥ ( ) 𝑍 𝑙 𝑖 L 𝑖 to represent the gradient of the local loss function L 𝑖 with respect to the local variable ¥ ( 𝑍 𝑙 ) 𝑖 . For calculating ¥ ( 𝛿 𝑙 - ) 1 𝑖 , we have

Note that 𝑍 ( 𝑙 ) 𝑖 is calculated with the sum aggregation of ¥ ( 𝑍 𝑙 ) 𝑗 , 𝑗 ∈ [ 1 , 𝑝 ] , thus we have 𝜕𝑍 ( 𝑙 ) 𝑖 𝜕𝑍 ¥ ( 𝑙 ) 𝑖 = 1 exists for all subgraph 𝑖 . Similar with ¥ ( 𝑍 𝑙 ) 𝑖 , we can also get 𝛿 ( 𝑙 - ) 1 𝑖 by aggregating ¥ ( 𝛿 𝑙 - ) 1 𝑖 from each device through communication.

With 𝛿 ( 𝑙 ) 𝑖 , the gradient of the model parameter 𝑊 ( 𝑙 - ) 1 can be calculated as

$$\lambda _ { i } \text{ be } \begin{array} { c } \infty \text{ causes } \infty \\ \text{trix.} \quad & \nabla _ { W ^ { ( l - 1 ) } } \mathcal { L } _ { i } = \frac { \partial \mathcal { L } _ { i } } { \partial W ^ { ( l - 1 ) } } = \frac { \partial \mathcal { L } _ { i } } { \partial Z _ { i } ^ { ( l ) } } \frac { \partial \ddot { Z } _ { i } ^ { ( l ) } } { \partial W ^ { ( l - 1 ) } } = \delta _ { i } ^ { ( l ) } \hat { A } _ { i } \left ( H _ { i } ^ { ( l - 1 ) } \right ) ^ { T }. \\ \text{trix.} \quad & \text{with non-normal or normal or under one } \text{and take } \text{via a bad to comm}. \end{array}$$

When performing parameter updates, we need to summarize the gradients calculated on all subgraphs as

$$W ^ { ( l ) } = W ^ { ( l ) } - \eta \sum _ { i = 1 } ^ { p } \nabla _ { W ^ { ( l ) } } \mathcal { L } _ { i }.$$

This process also needs to be implemented through communication. However, the data size of model parameters is usually much smaller than the data size of neighbor vertex

After Computation

Figure 4. The communication pattern of CDFGNN.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-2cba4e4b-462c-4f78-b7f7-acba2e255d63.jpg)

features and gradients. Thus, the communication overhead of aggregating model parameters is not the performance bottleneck.

In summary, during one iteration (forward + backward) of one GCN layer, there are two communication synchronizations for vertex values (features and gradients). This communication is to obtain the global intermediate value 𝑍 ( 𝑙 ) in the forward propagation and to obtain the 𝛿 ( 𝑙 ) in the backward propagation. Through these communication synchronizations, the calculated model parameter gradients are theoretically consistent with the single-device full-batch training method.

## 3.2 Communication Stage of CDFGNN

In the real world, most of the data graphs processed by graph neural network algorithms are power-law graphs [19], such as social networks, citation graphs, etc. We adopt the vertexcut GP algorithm, which is more efficient for power-law graphs. In figure 4, we demonstrate the communication pattern for vertex 'B'. We use the gray vertex in subgraph 1 to mark this vertex 'B' as a master vertex, while others are mirror vertices. In the computation stage, these replicas compute their intermediate values ¥ ( 𝑍 𝑙 ) 𝑖 and ¥ ( 𝛿 𝑙 ) 𝑖 independently. We need to aggregate these values through communication to achieve the same value as when executing on a single device.

CDFGNN takes each vertex as the minimum communication unit. The communication stage can be divided into two phases: gather and scatter . In the gather phase, the mirror vertex sends its values to the corresponding master vertex (with the same vertex ID). When the master vertex receives these messages, it should collect them and sum them with its own values. In the scatter phase, the master vertex sends its aggregated values back to all corresponding mirror vertices. The mirror vertex uses the received values to replace the original values. In figure 4, we list the values of vertex 'B' at different communication phases in all subgraphs.

This communication pattern requires the mirror vertex to store the location of its master vertex, and the master vertex to store the locations of all its mirrors. By executing the communication stage, we can ensure that the states of the vertex replicas are consistent with the sequential GNN training.

## 4 Adaptive Vertex Feature Cache

In this section, we introduce the adaptive cache mechanism of CDFGNN and prove its convergence.

## 4.1 Adaptive Cache Mechanism

In order to reduce the expensive vertex feature and gradient communication during the CDFGNN training process, we propose an adaptive vertex-level caching mechanism. Specifically, we cache the intermediate variables 𝑍 ( 𝑙 ) 𝑖 and 𝛿 ( 𝑙 ) 𝑖 during the training process.

For 𝑍 ( 𝑙 ) 𝑖 and 𝛿 ( 𝑙 ) 𝑖 , we adopt the same cache mechanism. For convenience, we take 𝑍 ( 𝑙 ) 𝑖 as the example to introduce the caching mechanism in detail. Firstly, we denote ¥ ( 𝑍 𝑙 ) 𝑖 = { 𝑧 𝑖, 1 , · · · , 𝑧 𝑖, 𝑉 | 𝑖 | } , where 𝑧 𝑖,𝑗 represents the feature vector corresponding to the 𝑗 -th vertex of subgraph 𝑖 in ¥ ( 𝑍 𝑙 ) 𝑖 . For each subgraph, we renumber the vertices with a local ID for continuous memory access. The 𝑗 -th vertex here refers to the vertex with local ID 𝑗 of subgraph 𝑖 .

Let ˜ 𝑧 𝑖,𝑗 be the cached value of 𝑧 𝑖,𝑗 , and ˜ 𝑧 · , 𝑗 be the corresponding cached value in 𝑍 ( 𝑙 ) 𝑖 . For each computing device, it should keep the cached value ˜ 𝑧 𝑖,𝑗 and ˜ 𝑧 · , 𝑗 for all vertices in their own subgraphs.

Thealgorithm 2 describes the update strategy of the cached values ˜ 𝑧 𝑖,𝑗 and ˜ 𝑧 · , 𝑗 . In each forward propagation of the GNN layer, we need to perform this algorithm once. After the update process is completed, we generate the matrix 𝑍 ( 𝑙 ) 𝑖 by directly combining the cached value ˜ 𝑧 · , 𝑗 .

For the cache mechanism, ˜ 𝑧 𝑖,𝑗 keeps the values used by computing device 𝑖 when building the cached value ˜ 𝑧 · , 𝑗 . When the difference between ˜ 𝑧 𝑖,𝑗 and the real value 𝑧 𝑖,𝑗 calculated in current iteration is too large, we need to update ˜ 𝑧 𝑖,𝑗 and ˜ 𝑧 · , 𝑗 for avoiding the large error. We use ∥ 𝑧 𝑖,𝑢 -˜ 𝑧 𝑖,𝑢 ∥∞ ∥ ˜ 𝑧 𝑖,𝑢 ∥∞ to measure the error. ∥ · ∥ ∞ is the 𝐿 ∞ norm, which can be used to represent the maximum absolute value of all elements in it.

We expect ˜ 𝑧 · , 𝑗 to be consistent across all relevant computing devices. Thus, when the ˜ 𝑧 𝑖,𝑗 of any computing device changed, we need to synchronize it to all other replicas.

In order to increase the proportion of cached values as much as possible without reducing the convergence accuracy or increasing the number of iterations for convergence, we design an adaptive caching mechanism by dynamically

## Algorithm 2: Adaptive Vertex Cache Mechanism

Input: current value 𝑧 𝑖,𝑢 , cached value ˜ 𝑧 𝑖,𝑢 and ˜ 𝑧 · ,𝑢 , threshold 𝜖 .

Output: cached value ˜ 𝑧 𝑖,𝑢 and ˜ 𝑧 · ,𝑢 .

- 1 for all process 𝑃 𝑖 ( ) parallel do

2

//

Traverse mirror vertices:

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

𝑢

∈

𝑔𝑒𝑡𝑀𝑖𝑟𝑟𝑜𝑟𝑉𝑒𝑟𝑡𝑖𝑐𝑒𝑠

()

if

∥

do

𝑧

𝑖,𝑢

-

˜

𝑧

𝑖,𝑢

∥∞

&gt;

𝜖

∥

˜

𝑧

𝑖,𝑢

∥∞

then

Send the difference value

Δ

𝑧

𝑧

𝑖,𝑢

=

𝑖,𝑢

-

to the corresponding master vertex

𝑧

˜

𝑖,𝑢

←

𝑧

𝑖,𝑢

Bulk Synchronize! Wait for messages from all processes to be sent!

//

Traverse messages and master vertices:

for for

for

𝑢,

𝑚𝑒𝑠𝑠𝑎𝑔𝑒𝑠

𝑖,𝑢

(

Δ

𝑧

)

∈

do

𝑧

𝑧

𝑖,𝑢

˜

·

,𝑢

← ·

˜

,𝑢

+

Δ

𝑧

active vertex

𝑢

𝑢

∈

.

𝑔𝑒𝑡𝑀𝑎𝑠𝑡𝑒𝑟

if

∥

()

𝑧

𝑖,𝑢

-

˜

𝑧

𝑖,𝑢

∥∞

𝑧

˜

·

,𝑢

← ·

˜

𝑧

,𝑢

do

&gt;

+

𝜖

∥

𝑧

𝑖,𝑢

𝑧

˜

𝑖,𝑢

←

𝑧

𝑖,𝑢

active vertex

𝑢

˜

𝑧

𝑖,𝑢

-

.

𝑢

∈

active vertices do

𝑧

Send the cached value ˜

·

,𝑢

to the corresponding mirror vertices.

adjusting the threshold 𝜖 . We update 𝜖 by

$$\begin{cases} \cdot & \succeq & \cdot & \cdot \\ \epsilon = \begin{cases} \min ( \lambda _ { 1 } \epsilon, \epsilon + \xi ), & a c c < \text{mean} _ { a c c } - \mu _ { 1 }, \epsilon < \nu _ { 1 } \\ \max ( \lambda _ { 2 } \epsilon, \epsilon - \xi ), & a c c > \text{mean} _ { a c c } + \mu _ { 2 }, \epsilon > \nu _ { 2 } \quad ( 6 ) \\ \epsilon, & \text{otherwise} \end{cases} \\ \cdot \wedge & \cdot \cdot \cdot & \cdot & \cdot & \cdot \cdot \end{cases}$$



After each iteration, the value of 𝜖 is updated. Where 𝑎𝑐𝑐 is the model accuracy on the train set in the current epoch, and 𝑚𝑒𝑎𝑛 𝑎𝑐𝑐 is the exponential moving average of 𝑎𝑐𝑐 :

$$\ m e a n _ { a c c } = 0. 8 \times \ m e a n _ { a c c } + 0. 2 \times a c c. \quad \quad ( 7 )$$

For the remaining hyperparameters, they are set by default to 𝜇 1 = 0 001, . 𝜇 2 = 0 02, . 𝜈 1 = 0 3, . 𝜈 2 = 0 001, . 𝜉 = 0 01, . 𝜆 1 = 1 05 and . 𝜆 2 = 0 9 in our experiments. .

Among these hyperparameters, we set 𝜇 1 to be much larger than 𝜇 2. This is because in the early stage of training, the accuracy on the training set increases rapidly. Only when there is a large enough accuracy increment (larger than 𝜇 2) can we consider that the current cache threshold should be relaxed. After the model parameters are stabilized, the accuracy of the model on the training set changes slightly. Therefore, even for small accuracy decreases, the threshold should be set smaller to reduce the cache error. In addition, we also use 𝜉 = 0 02 to define the maximum step . size when 𝜖 changes to avoid the error threshold changing

∥∞

𝑧

𝑖,𝑢

˜

for then

𝑧

𝑖,𝑢

˜

too quickly. We also use 𝜈 1 and 𝜈 2 to limit the value range of 𝜖 to [ 𝜈 , 𝜈 2 1 ] . The settings of these hyperparameters ensure that the training accuracy of the model will not be greatly reduced.

## 4.2 Proof of Convergence

Next, we prove the convergence of the training process when employing the adaptive cache mechanism. Specifically, we will prove that after a finite number of iterations, the model parameters 𝑊 will converge to the local optimal solution 𝑊 ∗ . We use the superscript˜to represent the value obtained in this layer after communication synchronization when the cache mechanism is used. The values without superscripts represent the values obtained by current model parameters and input features without cache mechanism in all layers.

Wefirst lay out the necessary and basic inequality required for the theoretical analysis.

Lemma 1. Denote ∥ 𝐴 ∥∞ = max 𝑖,𝑗 | 𝐴 𝑖,𝑗 | , 𝑐𝑜𝑙 ( 𝐴 ) is the column number of matrix 𝐴 . We have ∥ 𝐴 + 𝐵 ∥∞ ≤ ∥ 𝐴 ∥∞ + ∥ 𝐵 ∥∞ , ∥ 𝐴 · 𝐵 ∥∞ ≤ ∥ 𝐴 ∥∞∥ 𝐵 ∥∞ and ∥ 𝐴𝐵 ∥∞ ≤ 𝑐𝑜𝑙 ( 𝐴 )∥ 𝐴 ∥∞∥ 𝐵 ∥∞ .

Proof. These three inequalities can be proved as follows:

$$\ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \\ \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array} \ell \quad \begin{array} { c } \ell \\ \end{array}\ell \quad \begin{array} { c } \ell \\ \ell \\ \ell \\ \ell \quad \begin{array} { c } \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \leqslant } \quad \begin{array} { c } \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell \\ \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \ell | \leqslant } \end{array}$$

$$\| A \cdot B \| _ { \infty } & = \max _ { i, j } | A _ { i, j } \times B _ { i, j } | \\ & \leq \max _ { i, j } | A _ { i, j } | \times \max _ { i, j } | B _ { i, j } | \quad \quad ( 9 ) \\ & = \| A \| _ { \infty } \| B \| _ { \infty },$$

$$& - \| \varrho \| _ { \infty } \nu \| _ { \infty }, \\ \| A B \| _ { \infty } & = \max _ { i, j } | \sum _ { k = 1 } ^ { c o l ( A ) } A _ { i, k } \times B _ { k, j } | \\ & \leq c o l ( A ) \max _ { i, j, k } | A _ { i, k } \times B _ { k, j } | \quad \text{(10)} \\ & \leq c o l ( A ) \max _ { i, j } | A _ { i, j } | \max _ { i, j } | B _ { i, j } | \\ & = c o l ( A ) \| A \| _ { \infty } \| B \| _ { \infty }. \\ & \quad \quad \quad \ \Box$$

□

Next, we state that with bounded staleness on the embeddings, the approximations of the intermediate matrix results are close to the exact ones in the forward propagation.

Lemma 2. For the forward propagation of CDFGNN with the cache mechanism, if (a) we have ∥ ˜ 𝑍 ( 𝑙 - ) 1 -𝑍 ( 𝑙 - ) 1 ∥∞ ≤ 𝜖 𝑍 ( 𝑙 - ) 1 , while ˜ 𝑍 ( 𝑙 - ) 1 and 𝑍 ( 𝑙 - ) 1 represent the intermediate values with or without cache mechanism, (b) the function 𝜎 (·) is 𝜌 -Lipschitz continuous, (c) the elements in 𝑍 ( 𝑙 ) , ˆ 𝐴 and 𝑊 ( 𝑙 - ) 1 are bounded, while the absolute values are less than 𝐵 and the number of columns is less than 𝐶 . Then we have ∥ ˜ 𝐻 ( 𝑙 - ) 1 -𝐻 ( 𝑙 - ) 1 ∥∞ ≤ 𝜌𝜖 𝑍 ( 𝑙 - ) 1 and ∥ ˜ 𝑍 ( 𝑙 ) -𝑍 ( 𝑙 ) ∥∞ ≤ 𝑝𝜈 𝐵 1 + 𝐶 𝐵 𝜌𝜖 2 2 𝑍 ( 𝑙 - ) 1 .

Proof. We denote ˆ 𝑍 ( 𝑙 ) as the intermediate value when the caching mechanism is used in the previous 𝑙 -1 layers, but not used in the 𝑙 -th layer. Considering that each element in ˆ 𝑍 ( 𝑙 ) is the sum from at most 𝑝 device, the upper bound error of ˜ 𝑍 ( 𝑙 ) for using the cache mechanism in layer 𝑙 , is

$$\| \tilde { Z } ^ { ( l ) } - \hat { Z } ^ { ( l ) } \| _ { \infty } \leq p \nu _ { 1 } B. \text{ \quad \ \ } ( 1 1 )$$

Where 𝜈 1 is the upper bound of 𝜖 defined in the equation (6). Therefore, we have

$$\| \tilde { H } ^ { ( l - 1 ) } - H ^ { ( l - 1 ) } \| _ { \infty } = & \| \sigma ( \tilde { Z } ^ { ( l - 1 ) } ) - \sigma ( Z ^ { ( l - 1 ) } ) \| _ { \infty } \quad ( 1 2 ) \\ \leq & \rho \epsilon _ { Z ^ { ( l - 1 ) } }$$

$$& \| \tilde { Z } ^ { ( l ) } - Z ^ { ( l ) } \| _ { \infty } = \| ( \tilde { Z } ^ { ( l ) } - \tilde { Z } ^ { ( l ) } ) + ( \hat { Z } ^ { ( l ) } - Z ^ { ( l ) } ) \| _ { \infty } \\ \leq & p v _ { 1 } B + \| \hat { A } \sigma ( \tilde { Z } ^ { ( l - 1 ) } ) W ^ { ( l - 1 ) } - \hat { A } \sigma ( Z ^ { ( l - 1 ) } ) W ^ { ( l - 1 ) } \| _ { \infty } \ \ ( 1 3 ) & & \text{Fi} \\ \leq & p v _ { 1 } B + C ^ { 2 } B ^ { 2 } \rho \epsilon _ { Z ^ { ( l - 1 ) } } & & \text{bour} \\ \pi & \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot \quad \, \cdot$$

The equation ( 12) is obtained from the definition of Lipschitz condition. □

Next, we will prove that the intermediate gradient ˜ 𝛿 ( 𝑙 ) = ∇ ˜ 𝑍 ( 𝑙 ) ˜ L with cache mechanism is also close to the exact gradient 𝛿 ( 𝑙 ) = ∇ 𝑍 ( 𝑙 ) L .

Lemma 3. For the backward propagation of CDFGNN, if (a) we have ∥ ˜ 𝑍 ( 𝑙 - ) 1 -𝑍 ( 𝑙 - ) 1 ∥∞ ≤ 𝜖 𝑍 ( 𝑙 - ) 1 , while ˜ 𝑍 ( 𝑙 - ) 1 and 𝑍 ( 𝑙 - ) 1 represent the intermediate values with or without cache mechanism, (b) the function 𝜎 (·) and the derivative of loss function ∇L are 𝜌 -Lipschitz continuous, (c) the elements in 𝛿 ( 𝑙 ) , ˆ 𝐴 , 𝜎 ′ ( 𝑍 ( 𝑙 ) ) and 𝑊 ( 𝑙 - ) 1 are bounded, and their absolute values are less than 𝐵 and the number of columns is less than 𝐶 . Then we have ∥∇ ˜ 𝑍 ( 𝑙 ) ˜ L-∇ ( ) L∥∞ 𝑍 𝑙 and ∥∇ 𝑊 ( 𝑙 ) ˜ L-∇ 𝑊 ( 𝑙 - ) 1 L∥∞ are also bounded.

Proof. First, we prove that ∥ ˜ 𝛿 ( 𝑙 ) -𝛿 ( 𝑙 ) ∥∞ is bounded based on the previous lemma.

For the last layer 𝐿 , we have

$$\| \nabla _ { \tilde { Z } ^ { ( L ) } } \tilde { \mathcal { L } } - \nabla _ { Z ^ { ( L ) } } \mathcal { L } \| _ { \infty } \leq \rho \epsilon _ { Z ^ { ( L ) } } \,. \quad \quad ( 1 4 ) \quad \text{da}$$

Next, we use mathematical induction to complete the proof. For 𝑙 ′ &gt; 𝑙 , if it satisfies ∥∇ ˜ 𝑍 ( 𝑙 ′ ) ˜ L - ∇ 𝑍 ( 𝑙 ′ ) L∥∞ ≤ 𝐾 ( 𝑙 ′ ) , then for the 𝑙 -th layer, we have

$$\det & \left ( \begin{array} { c } l { - } t h \, \text{for the $l$-th layer, we have} \end{array} \right ) ^ { \dots } \, \ e n \, \quad \, \begin{array} { c } \tau \, \cdot \, \end{array} \right ) ^ { \dots } \, \mathcal { L } ( \mathfrak { U } \\ \quad \| \nabla _ { \tilde { Z } ( l ) } \, \tilde { L } - \nabla _ { Z ( l ) } \, \mathcal { L } \| _ { \infty } \, & \leq \mathcal { L } \\ = & \| \tilde { \delta } ^ { ( l + 1 ) } \, \tilde { A } \left ( W ^ { ( l ) } \right ) ^ { T } \cdot \sigma ^ { \prime } \left ( \tilde { Z } ^ { ( l ) } \right ) - \delta ^ { ( l + 1 ) } \, \tilde { A } \left ( W ^ { ( l ) } \right ) ^ { T } \cdot \sigma ^ { \prime } \left ( \tilde { Z } ^ { ( l ) } \right ) \, \| _ { \infty } \, & = \mathcal { L } \\ \leq & C ^ { 2 } \{ \| \tilde { \delta } ^ { ( l + 1 ) } \| _ { \infty } \| \tilde { A } \| _ { \infty } \| \left ( W ^ { ( l ) } \right ) ^ { T } \| _ { \infty } \| \sigma ^ { \prime } \left ( \tilde { Z } ^ { ( l ) } \right ) - \sigma ^ { \prime } \left ( \tilde { Z } ^ { ( l ) } \right ) \, \| _ { \infty } \, & + \frac { \rho } { 2 } \\ + & \| \tilde { \delta } ^ { ( l + 1 ) } - \delta ^ { ( l + 1 ) } \| _ { \infty } \| \tilde { A } \| _ { \infty } \| \left ( W ^ { ( l ) } \right ) ^ { T } \| _ { \infty } \| \sigma ^ { \prime } \left ( \tilde { Z } ^ { ( l ) } \right ) \, \| _ { \infty } \, & \leq \mathcal { L } \\ \leq & C ^ { 2 } ( B ^ { 3 } \rho \epsilon _ { Z ^ { ( l ) } } + K ^ { ( l + 1 ) } B ^ { 3 } ) = C ^ { 2 } B ^ { 3 } ( \rho \epsilon _ { Z ^ { ( l ) } } + K ^ { ( l + 1 ) } ) \, & \quad \, \text{The} \\ \text{Denote $K^{l} = C^{2} B^{3}(\rho \epsilon _ { Z ^ { ( l ) } } + K ^ { ( l + 1 ) } ), \, \text{then we can find that} \quad \, \| \nabla _ { W ( i ) }. \\ \text{the assumption holds for the $l$-th layer Therefore, we can} \end{array}$$

Denote 𝐾 𝑙 = 𝐶 𝐵 2 3 ( 𝜌𝜖 𝑍 ( 𝑙 ) + 𝐾 ( 𝑙 + ) 1 ) , then we can find that the assumption holds for the 𝑙 -th layer. Therefore, we can complete the proof according to mathematical induction.

For ∥∇ 𝑊 ( 𝑙 ) ˜ L - ∇ 𝑊 ( 𝑙 ) L∥∞ , we can get it according to the equation (4):

$$\text{out} \quad \text{equation} \, ( 4 ) \colon & \quad \cdot \quad \cdot \quad \cdot \\ \text{in} \quad \| \nabla _ { W ^ { ( l ) } } \tilde { \mathcal { L } } - \nabla _ { W ^ { ( l ) } } \mathcal { L } \| _ { \infty } \\ = & \| \tilde { \delta } ^ { ( l + 1 ) } _ { i } \hat { A } _ { i } \left ( \tilde { H } ^ { ( l ) } _ { i } \right ) ^ { T } - \delta ^ { ( l + 1 ) } _ { i } \hat { A } _ { i } \left ( H ^ { ( l ) } _ { i } \right ) ^ { T } \| _ { \infty } \\ \leq & C ^ { 2 } \{ \| \tilde { \delta } ^ { ( l + 1 ) } _ { i } \| _ { \infty } \| \hat { A } \| _ { \infty } \| \left ( \tilde { H } ^ { ( l ) } _ { i } \right ) ^ { T } - \left ( H ^ { ( l ) } _ { i } \right ) ^ { T } \| _ { \infty } \\ + & \| \tilde { \delta } ^ { ( l + 1 ) } _ { i } - \delta ^ { ( l + 1 ) } _ { i } \| _ { \infty } \| \hat { A } \| _ { \infty } \| \left ( H ^ { ( l ) } _ { i } \right ) ^ { T } \| _ { \infty } \} \\ \leq & C ^ { 2 } ( B ^ { 2 } \rho \epsilon _ { Z ^ { ( l ) } } + K ^ { l + 1 } B ^ { 2 } ) = C ^ { 2 } B ^ { 2 } ( \rho \epsilon _ { Z ^ { ( l ) } } + K ^ { ( l + 1 ) } ) \\ & \quad \Box \\ & \text{Finally we will nrove that CDFGNN can converge to the}$$

Finally, we will prove that CDFGNN can converge to the local optimal solution under the premise that the error is bounded. For the parameter matrix 𝑊 , we use the subscript 𝑖 to identify that the value is obtained of the 𝑖 -th iteration.

Theorem 1. For the 𝐿 layer graph neural network training based on the CDFGNN cache mechanism, given the local optimal parameters 𝑊 (∗) and the initial parameters 𝑊 ( 1 ) . Assuming that (a) the activation function 𝜎 (·) and the derivative of loss function ∇L are 𝜌 -Lipschitz continuous, (b) the matrix ˆ 𝐴 𝐻 , and 𝑊 , and the corresponding gradients on them are bounded, where the maximum absolute value of the element is 𝐵 , (c) the function L( 𝑊 ) is 𝜌 -smooth. We can prove that there is a constant 𝐾 &gt; 0 such that for ∀ 𝑁 &gt; 𝐿 𝜖 , if the GNN is trained based on the cache mechanism 𝑅 iterations ( 𝑅 ∈ [ 1 , 𝑁 ] and is sampled from [ 1 , . . . , 𝑁 ] uniformly) and the learning rate 𝜂 = min GLYPH&lt;16&gt; 1 𝜌 , 1 √ 𝑁 GLYPH&lt;17&gt; , we have

$$E _ { R } \| \nabla _ { W _ { ( R ) } } \mathcal { L } \| _ { F } ^ { 2 } \leq 2 \frac { \mathcal { L } ( W _ { ( 1 ) } ) - \mathcal { L } ( W _ { ( * ) } ) + \frac { \rho K } { 2 } } { \sqrt { N } }. \quad ( 1 7 )$$

Proof. For the convenience, we denote Δ ( 𝑖 ) = ∇ 𝑊 ( 𝑖 ) ˜ L -∇ 𝑊 ( 𝑖 ) L . Considering that the model parameter 𝑊 is updated under the cache mechanism, we have 𝑊 ( 𝑖 + ) 1 = 𝑊 ( 𝑖 ) + 𝜂 ∇ 𝑊 ( 𝑖 ) ˜ . L According to lemma 3 and the 𝜌 -smooth property of the function L( 𝑊 ) , we have

$$\mathcal { I }, \quad & \text{ of the function $\mathcal{ L}(W),$ we have} \\ \mathcal { I } ( W _ { ( i + 1 ) } ) = \mathcal { L } ( W _ { ( i ) } + \eta \nabla _ { W _ { ( i ) } } \tilde { \mathcal$$

The scaling in the last step is based on the value of the learning rate 𝜂 . According to lemma 3, we have ∥ Δ ( 𝑖 ) ∥ 2 𝐹 ≤ ∥∇ 𝑊 𝑖 ( ) ˜ L | 2 ∞ + ∥∇L( 𝑊 ( 𝑖 ) )∥ 2 ∞ ≤ 2 𝐵 2 ≤ 𝐾 . Therefore, we have

$$\tan _ { \iota _ { 0 } } \mathcal { L } ( W _ { ( i + 1 ) } ) \leq \mathcal { L } ( W _ { ( i ) } ) - ( \eta - \frac { \rho } { 2 } \eta ^ { 2 } ) \| \nabla _ { W _ { ( i ) } } \$$

Sum up the equation (19) for 𝑖 from 1 to 𝑁 , we can get

$$( \eta - \frac { \rho } { 2 } \eta ^ { 2 } ) \sum _ { i = 1 } ^ { N } \| \nabla _ { W _ { ( i ) } } \mathcal { L } \| _ { F } ^ { 2 } & \leq \mathcal { L } ( W _ { ( 1 ) } ) - \$$

Considering 𝜂 = min GLYPH&lt;16&gt; 1 𝜌 , 1 √ 𝑁 GLYPH&lt;17&gt; , we divide both side of equation (20) by 𝑁 𝜂 ( -𝜌 2 𝜂 2 ) , then we have

$$\i o w { \left ( \varkappa \right ) \nu \right ) \nu \right ) } ^ { \nu } \left ( \nu \right ) - \frac { 2 } { 2 } \eta ^ { 2 } \right ), \, \min \, \mathfrak { w } \, \max \, & \quad \quad \quad$$

When 𝑁 →∞ , we can find that the expectation of parameter gradient E 𝑅 → 0. Therefore, we show that convergence of parameters can be achieved in finite iterations.

□

## 5 Communication Quantization

In this section, we propose the communication quantization mechanism of CDFGNN. There are many quantization methods, including linear quantization and logarithmic quantification [20], exponential quantification [21], differentiable quantization [22, 23], etc. Considering that when we adopt the adaptive cache mechanism, the message sent is the difference value instead of the original value. Thus, the message data usually follows an uniform distribution. For this reason, we adopt the simplest linear quantization method to quantify the difference of vertex features and gradients. We do not quantify the model parameters when communicating with the parameter server.

Specifically, for the calculated difference m of features or gradients for the vertex 𝑣 𝑖 , it is represented in the form of a 32-bit floating point format in the GPU memory. In order to quantify it into the 𝐵 -bit unsigned integer format, we need to calculate the maximum element value max ( m ) and the minimum element value min ( m ) at first. Therefore, we can get the quantified value as

$$q _ { i } = \left \lfloor \frac { 2 ^ { B } ( m _ { i } - \min ( \mathbf m ) ) } { \max ( \mathbf m ) - \min ( \mathbf m ) } + 0. 5 \right \rfloor. \quad \quad ( 2 2 ) \quad \ \ \ \ \ \ \ \ \ \$$

When sending the message, the original message size is 𝑇 ∗ 𝐿 , and the quantified message size is 𝐵 ∗ 𝐿 + 2 𝑇 (including the maximum and minimum value). Where 𝐿 refers to the number of elements in m , and 𝑇 refers to the number of bits of the original data format.

During the recovery, for the quantization value 𝑞 𝑖 , we can restore it to

$$\tilde { m } _ { i } = \frac { \max ( \mathbf m ) - \min ( \mathbf m ) } { 2 ^ { B } } q _ { i } + \min ( \mathbf m ). \quad \quad ( 2 3 )$$

$$( 2 0 ) \quad \text{By the definition, we have } \left \lfloor \frac { 2 ^ { B } ( m _ { i } - \min ( m ) ) } { \max ( m ) - \min ( m ) } - 0. 5 \right \rfloor \, < \, q _ { i } \, \leq$$

j 2 𝐵 ( 𝑚 𝑖 -min ( m ) ) max ( m ) -min ( m ) + 0 5 . k . Therefore, the upper bound of the max ( m ) -min ( m ) .

quantization error is 2 𝐵 + 1

## 6 Hierarchical Graph Partition Algorithm

Considering that in the heterogeneous multi-node multiGPU environment, the communication overhead within a single node and across physical nodes is different. We demonstrate the communication architecture in figure 3. The GPU is viewed as the basic computing device.

Weproposeourvertex-cut graph partition algorithm based on the EBV [24] algorithm. To adapt to the hierarchical communication architecture, we rewrite its evaluation function

$$\text{mutation an occurrence, we two are as covariance in question} \\ \text{Eva} _ { ( u, v ) } ( i ) = & ( 1 - \gamma ) ( \mathbb { I } ( i \not \in d _ { \ } r e p _ { u } ) + \mathbb { I } ( i \not \in d _ { \ } r e p _ { v } ) ) \\ \text{for} \\ \Box \text{ of} \\ \Box \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{  \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{} \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{
\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }
\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{\ }\text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{ } \text{                                                                                                                                                                                                         \text{                                                                                                                                                                                                    
\text{                                                                                                                                                                                                     
\text{\                                                                                                                                                                                                       
\end{$$

𝑑 \_ 𝑟𝑒𝑝 𝑢 and ℎ 𝑟𝑒𝑝 \_ 𝑢 represent the GPU IDs and host (CPU) IDs that vertex 𝑢 has been assigned. As long as the vertex 𝑢 has been assigned to any GPU corresponding to the host, the host ID will be added to ℎ 𝑟𝑒𝑝 \_ 𝑢 . We use ℎ𝑜𝑠𝑡 𝑖 to represent the host ID to which the 𝑖 -th GPU belongs. Besides, 𝑒 𝑐𝑜𝑢𝑛𝑡 [ 𝑖 ] and 𝑣 𝑐𝑜𝑢𝑛𝑡 [ 𝑖 ] mean the number of edges and vertices that have been assigned to subgraph 𝑖 .

When partitioning the graph, we assign it edge by edge. For each edge, we select the GPU ID that minimizes the evaluation function as the subgraph ID this edge assigned.

From equation (24), we can found that the term I ( ℎ𝑜𝑠𝑡 𝑖 ∉ ℎ𝑜𝑠𝑡 \_ 𝑟𝑒𝑝 𝑢 ) + I ( ℎ𝑜𝑠𝑡 𝑖 ∉ ℎ𝑜𝑠𝑡 \_ 𝑟𝑒𝑝 𝑣 ) we design can reduce the number of cut vertices between hosts. Usually, we set 𝛾 ≪ 1. Therefore, this term is mainly worked to select a more reasonable host when the other terms are close. In our experiment, we set 𝛾 to 0 1 by default. .

For the other terms, I ( 𝑖 ∉ 𝑑 \_ 𝑟𝑒𝑝 𝑢 ) + I ( 𝑖 ∉ 𝑑 \_ 𝑟𝑒𝑝 𝑣 ) is related to the replication factor among GPUs, while 𝛼 𝑒 𝑐𝑜𝑢𝑛𝑡 [ 𝑖 ] | 𝐸 | / 𝑝 and 𝛽 𝑣 𝑐𝑜𝑢𝑛𝑡 [ 𝑖 ] | 𝑉 | / 𝑝 restrict the edge and vertex imbalance factor respectively. The replication factor is defined as ˝ 𝑝 𝑖 = 1 | 𝑉 𝑖 | | 𝑉 | , that represents the average number of replicas for a vertex. The edge imbalance factor is defined as max 𝑖 = 1 ,...,𝑝 | 𝐸 𝑖 | | 𝐸 | / 𝑝 , while the vertex imbalance factor is defined as max 𝑖 = 1 ,...,𝑝 | 𝑉 𝑖 | ˝ 𝑝 𝑖 = 1 | 𝑉 𝑖 | / 𝑝 . Both of them are used to measure the balance of partition results.

## 7 Experiments and Analysis

In this section, we test CDFGNN in a heterogeneous environment with multiple physical nodes and multiple GPUs

Table 1. Statistics of GNN dataset graphs

| Dataset         | | 𝑉 |           | | 𝐸 |               |   Input Dim |   Output Dim |
|-----------------|-----------------|---------------------|-------------|--------------|
| Reddit          | 232 , 965       | 11 , 606 , 919      |         602 |           41 |
| ogbn-products   | 2 , 449 , 029   | 61 , 859 , 140      |         100 |           47 |
| ogbn-papers100M | 111 , 059 , 956 | 1 , 615 , 685 , 872 |         200 |          172 |
| Friendster      | 65 , 608 , 366  | 1 , 806 , 067 , 135 |          64 |           32 |

Table 2. Communication Performance between GPUs

| Environment   | Pattern   | Bandwidth   |
|---------------|-----------|-------------|
| PCIe          | Peer2Peer | 22.70 GB/s  |
| InfiniBand    | Peer2Peer | 8.27 GB/s   |
| PCIe          | Broadcast | 19.47 GB/s  |
| InfiniBand    | Broadcast | 11.98 GB/s  |

same GNN model. Meanwhile, we implement CDFGNN with 2 famous vertex-cut GP algorithms: HEP [30] and DNE [31]. Thus, we can analysis the influence of different graph partition algorithms on the training efficiency. We also set the 𝛾 to 0 1 and 0 0 respectively for testing the performance of our . . hierarchical GP algorithm, and represent them as EBV 𝛾 = 0 1 . and EBV 𝛾 = 0 0 . . The EBV 𝛾 = 0 0 . is equivalent to the original EBV algorithm.

per node. We compare CDFGNN with the state-of-the-art distributed full-batch graph neural network training frameworks on several datasets. In addition, we select some representative graph partition algorithms to analyze the influence of different graph partition algorithms on the distributed full-batch GNN training. Finally, we conduct the ablation study to demonstrate the effectiveness of each component.

## 7.1 Experiment Setup and Datasets

In the experiment, we compare CDFGNN with the state-ofthe-art distributed full-batch graph neural network training frameworks SANCUS [25] and CAGNET [10]. We select four datasets: Reddit [3], ogbn-products [26], ogbn-papers100M [27] and Friendster [28] for comparing their performance. The statistics of these graphs are listed in table 1. The Friendster does not provide input features and output categories. We randomly generate these data to test the training efficiency of different frameworks on the large graph.

Our experiment platform is a 2-node cluster, with each node has 8 Nvidia A800 80G GPU. The communication within the physical nodes is based on the 16-channel PCIe 4.0, and the communication across the physical nodes is based on the InfiniBand. We use the NCCL for communication, and list the communication performance in Table 2.

We adopt the simple 2-layer graph convolutional network as our test model. The dimensions of the input and output features are determined by the datasets, while the dimension of the hidden layer is set to 64 by default. We adopt the cross-entropy function as the loss function, and the Adam optimizer [29] to update the model parameters. The initial learning rate is set to 0 01 by default. .

## 7.2 Distributed Training Efficiency Comparison

First, we compare CDFGNN with the current state-of-the-art distributed full-batch GNN training frameworks SANCUS and CAGNET. During the training process, we adopted the

Figure 5 presents the average training time per epoch for different GNN training frameworks on four datasets. The GPUs we use are evenly distributed on two physical nodes. We use EBV 𝛾 = 0 1 . , EBV 𝛾 = 0 0 . , HEP and DNE to represent the training efficiency when combined with CDFGNN.

From figure 5, we can find that EBV 𝛾 = 0 1 . achieves the best performance in almost all cases and reduces the training time by 30 39% compared to Sancus on average. Sancus performs . better than CAGNET and even outperforms EBV 𝛾 = 0 1 . in the smallest case (2 GPUS, Reddit). However, the performance of Sancus is limited for larger cases. Comparing EBV 𝛾 = 0 1 . and EBV 𝛾 = 0 0 . , setting 𝛾 to 0 1 can achieve better training effi-. ciency on our cluster. It is worth noting that when there are only 2 GPUs, the partition results of EBV 𝛾 = 0 1 . and EBV 𝛾 = 0 0 . are equivalent. The HEP algorithm also performs well in the smallest dataset (Reddit). But EBV 𝛾 = 0 1 . leads HEP by a larger margin on other datasets. Therefore, we believe that the CDFGNN framework combined with the EBV 𝛾 = 0 1 . can achieve the best training efficiency on graph neural network datasets of different sizes.

## 7.3 Ablation Study

Next, we study the reasons for different performances when different graph partition algorithms are combined with CDFGNN. We compare graph partition results generated by different GP algorithms in Table 3. The 'Inner' and 'Outer' columns mean the maximum number of inner and outer connections on a single subgraph. The number of inner connections refers to the number of messages within the physical node that need to be sent from this device, and outer connections refer to the messages across the physical nodes. We also present the replication factor (RF) and edge imbalance factor (Edge IF) defined in Section 6 for analyzing. Since all GP algorithms compared here are vertex-cut algorithms, we do not give the vertex imbalance factor.

Table 3 shows the characteristics of all GP algorithms on 4 datasets. Setting 𝛾 to 0 1 can greatly reduce the number .

Table 3. The Statistics of differnet graph partition algorithms

| Dataset       | GP algorithm   |   Nodes |   GPU per Node |    Inner |    Outer |     RF |   Edge IF |
|---------------|----------------|---------|----------------|----------|----------|--------|-----------|
| reddit        | EBV 𝛾 = 0 . 0  |       2 |              2 |   104217 |   138583 | 2.9027 |    1.0054 |
| reddit        | EBV 𝛾 = 0 . 1  |       2 |              2 |   105412 |   117879 | 3.086  |    1.0022 |
| reddit        | HEP            |       2 |              2 |    36662 |    52886 | 1.6084 |    1.2693 |
| reddit        | DNE            |       2 |              2 |    65578 |   118788 | 2.1025 |    1.2558 |
| ogbn-products | EBV 𝛾 = 0 . 0  |       2 |              4 |   695905 |   639459 | 3.1788 |    1.0002 |
| ogbn-products | EBV 𝛾 = 0 . 1  |       2 |              4 |   952727 |   481147 | 3.3379 |    1.0008 |
| ogbn-products | HEP            |       2 |              4 |   143711 |   127261 | 1.3304 |    1.2323 |
| ogbn-products | DNE            |       2 |              4 |   367460 |   406408 | 1.9363 |    1.1527 |
| friend        | EBV 𝛾 = 0 . 0  |       2 |              8 | 12395102 |  9988776 | 3.7237 |    1.0002 |
| friend        | EBV 𝛾 = 0 . 1  |       2 |              8 | 19586785 |  5465465 | 4.0322 |    1.0011 |
| friend        | HEP            |       2 |              8 |  5794009 |  4675810 | 1.7048 |    1.776  |
| friend        | DNE            |       2 |              8 |  8737134 | 11670478 | 2.3546 |    1.7455 |
| papers100M    | EBV 𝛾 = 0 . 0  |       2 |              8 | 20438528 | 16362561 | 3.6503 |    1      |
| papers100M    | EBV 𝛾 = 0 . 1  |       2 |              8 | 32241760 |  9924817 | 4.0347 |    1.0001 |
| papers100M    | HEP            |       2 |              8 |  5826661 |  3085959 | 1.3144 |    2.0204 |
| papers100M    | DNE            |       2 |              8 | 10021186 | 13819120 | 2.1475 |    1.3866 |

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-d6fe7a00-a219-440b-8196-fa6b262d5ff6.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-e7095878-f745-4b5c-a76a-32ec1cde63ad.jpg)

(a) Reddit

(b) ogbn-products

Figure 5. Comparison of average training time per epoch.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-170a8164-af5c-49e2-b327-2749803dfc8e.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-b3b24431-a612-4583-890e-62c0f1e9c82b.jpg)

of outer connections (31 08% on average) at the expense . of more inner connections. Considering the inter and outer communication bandwidth comparison in Table 2, the overall communication overhead can be greatly reduced, thereby improving training efficiency. The HEP algorithm achieves the smallest inner and outer connections. However, the graph partition results are significantly imbalanced. Thus, it leads

to imbalanced computing and communication overhead and reduces the overall training efficiency.

We decompose the computation and communication time of different GP algorithms and communication optimization methods based on CDFGNN for further analysis. We list the computation and communication time per epoch of each GPUs in Figure 6. We also provide the corresponding average training time with the dashed lines. When comparing these GP algorithms EBV 𝛾 = 0 1 . , EBV 𝛾 = 0 0 . , HEP and DNE, all communication optimization methods are used by default. When comparing the communication optimization methods, the GP algorithm used is EBV 𝛾 = 0 1 . . The 'Cache' means only the adaptive cache mechanism is used, while 'Quantify' means only the communication quantization is used. 'Baseline' means that no communication optimization methods are used.

As shown in Figure 6, comparing with EBV 𝛾 = 0 1 . , the computation time of EBV 𝛾 = 0 0 . is roughly the same. However, the communication time of EBV 𝛾 = 0 0 . is longer. HEP and DNE have significant workload imbalances, thus restricting their training performance.

Meanwhile, both the adaptive cache mechanism and communication quantization can greatly reduce the communication overhead without affecting the computation overhead. We include the extra calculation time (quantization and dequantization for communication quantization, caching comparison for adaptive cache mechanism) into the communication time for a fair comparison. Therefore, the communication time is not directly proportional to the number of communication messages. On ogbn-products, the adaptive cache mechanism achieves better communication optimization, while on Reddit the communication quantification is more efficient. When combining both methods (EBV 𝛾 = 0 1 . ), we achieve the best performance.

We also analysis the message sending percentage of each layer with the adaptive cache mechanism in Figure 7. To better understand the cache mechanism during different training epochs, we further provide the cache threshold 𝜖 . Figure 7 shows the sending percentage and cache threshold on ogbn-products and Reddit with 4 and 8 GPUs respectively. It can be found that in the middle stage of training, only few messages are sent, thus greatly reducing communication overhead. This phenomenon is consistent with our hypothesis. Furthermore, at about 50 -100 training epochs on ogbn-products, almost no vertex features are sent during the forward propagation. Meanwhile, the cache threshold is dynamically adjusted to a larger value in the middle of training and smaller at other times.

Finally, we verify the convergence of evaluate accuracy of CDFGNN in Figure 8. In addition to the distributed training approaches of CDFGNN, we also implement the full-batch and mini-batch training methods on the single GPU for comparison.

The results in figure 8 show that using the adaptive cache mechanism and communication quantification method has almost no impact on the convergence of accuracy. Due to the small random errors when distributed training, the accuracy in some epochs is even higher than that of single GPU full-batch training. Besides, the mini-batch training method significantly reduce the accuracy, especially on Reddit. That is because we limit the maximum number of neighbors when sampling, and the average degree of Reddit is very large.

## 8 Related Work

The research on distributed graph neural network training is still in the early stages [32], and only a few these works are based on GPU. Compared with traditional distributed large-scale graph computing frameworks [17, 33, 34], the communication overhead of distributed GNN training tasks is more serious. This is because the distributed training of each GCN layer or GAT layer requires sending/receiving features and gradients of neighbor vertices, where the dimension of vertex features and gradients is usually very large.

Many existing distributed graph neural network training frameworks adopt the centralized architecture. For example, NeuGraph [35] proposed a GNN training framework in a single-node multi-GPU environment. They use METIS [36] as the graph partitioning algorithm, and introduce graph computation optimizations into the management of data partitioning, scheduling, and parallelism. However, their work is not open source. RoC [9] dynamically partitions the graph through an online regression model and proposes a interprocess memory management method, but it also leads to a complex execution workflow. PaGraph [37] implements static caching of vertices with high degree in GPU memory, and use a special graph partitioning algorithm to balance workload and reduce cross-device data access. G 3 [38] utilizes parallel graph optimization to improve graph operations in GPU systems, Grain [39] selects GNN data by focusing on maximizing social influence, and RDD [40] uses unlabeled data. AliGraph [41] also uses static caching technology, but only supports CPU clusters. AGL [42] uses MapReduce operations to simultaneously optimize the training and inference phases. In order to reduce and balance communication, DistDGL [43] uses a load-balanced graph partitioning algorithm. Most of these systems suffer from heavy communication overhead and therefore cannot scale to large-scale applications. Besides, we should notice that except for NeuGraph and Roc, which support full-batch graph neural network training, other frameworks are mini-batch training methods that require sampling.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-ff4588d7-6db1-4109-a736-6c188f322223.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-cce2114b-5966-4d50-9b6c-53946bcd309f.jpg)

Figure 6. Time breakdown of different GP algorithms and communication optimization methods.

Figure 7. Percentage of cache threshold and sending messages.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-ca92f719-ef02-4ddf-8c96-5c2fcfda95d8.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-d8fc256b-7ac0-4933-8f42-144d8be7c74a.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-9cfb3b31-33b5-4f1a-a8ec-c19cc89d507f.jpg)

Figure 8. The convergence curve of evaluate accuracy.

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-f28e8dfd-e9da-41b2-8544-95d077579833.jpg)

![Image](https://ac.marcodsn.me/arxiv-markdown-images/2408.00232v1-figure-aa90f560-a6c5-4c87-848e-38de6c62c02e.jpg)

## 9 Conclusion and Future Work

In this paper, we propose a cache-based distributed full-batch graph neural network training framework CDFGNN. To address the problem of excessive communication in existing full-batch training frameworks, we design three optimizations: adaptive cache mechanism, communication quantization, and hierarchical graph partition. With these improvements, CDFGNN outperforms the state-of-the-art distributed full-batch training frameworks. Besides, we theoretically and experimentally prove that the convergence accuracy of CDFGNN is not degraded. Therefore, we believe that CDFGNN can greatly improve the distributed training efficiency for large-scale graphs.

In the future, we want to make full use of the high-speed communication equipment such as NVLink to further reduce the communication overhead.

## References

- [1] T. N. Kipf and M. Welling, 'Semi-supervised classification with graph convolutional networks,' arXiv preprint arXiv:1609.02907 , 2016.
- [2] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, and P. Liò, 'Yoshua 391 bengio. graph attention networks,' in International Conference on Learning Representations , vol. 392, 2018, p. 393.
- [3] W. Hamilton, Z. Ying, and J. Leskovec, 'Inductive representation learning on large graphs,' Advances in neural information processing systems , vol. 30, 2017.
- [4] J. Chen, T. Ma, and C. Xiao, 'Fastgcn: fast learning with graph convolutional networks via importance sampling,' arXiv preprint arXiv:1801.10247 , 2018.
- [5] W. Huang, T. Zhang, Y. Rong, and J. Huang, 'Adaptive sampling towards fast graph representation learning,' Advances in neural information processing systems , vol. 31, 2018.
- [6] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. Prasanna, 'Graphsaint: Graph sampling based inductive learning method,' arXiv preprint arXiv:1907.04931 , 2019.
- [7] J. Dong, D. Zheng, L. F. Yang, and G. Karypis, 'Global neighbor sampling for mixed cpu-gpu training on giant graphs,' in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery &amp; Data Mining , 2021, pp. 289-299.
- [8] Z. Cai, X. Yan, Y. Wu, K. Ma, J. Cheng, and F. Yu, 'Dgcl: an efficient communication library for distributed gnn training,' in Proceedings of the Sixteenth European Conference on Computer Systems , 2021, pp. 130-144.
- [9] Z. Jia, S. Lin, M. Gao, M. Zaharia, and A. Aiken, 'Improving the accuracy, scalability, and performance of graph neural networks with roc,' Proceedings of Machine Learning and Systems , vol. 2, pp. 187-198, 2020.
- [10] A. Tripathy, K. Yelick, and A. Buluç, 'Reducing communication in graph neural network training,' in SC20: International Conference for High Performance Computing, Networking, Storage and Analysis . IEEE, 2020, pp. 1-14.
- [11] J. Chen, J. Zhu, and L. Song, 'Stochastic training of graph convolutional networks with variance reduction,' arXiv preprint arXiv:1710.10568 , 2017.
- [12] J. Thorpe, Y. Qiao, J. Eyolfson, S. Teng, G. Hu, Z. Jia, J. Wei, K. Vora, R. Netravali, M. Kim et al. , 'Dorylus: Affordable, scalable, and accurate { GNN } training with distributed { CPU } servers and serverless threads,' in 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI 21) , 2021, pp. 495-514.
- [13] Z. Wang, Y. Guan, G. Sun, D. Niu, Y. Wang, H. Zheng, and Y. Han, 'Gnn-pim: A processing-in-memory architecture for graph neural networks,' in Advanced Computer Architecture: 13th Conference, ACA 2020, Kunming, China, August 13-15, 2020, Proceedings 13 . Springer, 2020, pp. 73-86.
- [14] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y. Bengio, 'Graph attention networks,' arXiv preprint arXiv:1710.10903 , 2017.
- [15] S. Gandhi and A. P. Iyer, 'P3: Distributed deep graph learning at scale,' in 15th { USENIX } Symposium on Operating Systems Design and Implementation ( { OSDI } 21) , 2021, pp. 551-568.
- [16] J. E. Gonzalez, Y. Low, H. Gu, D. Bickson, and C. Guestrin, 'Powergraph: distributed graph-parallel computation on natural graphs.' in OSDI , vol. 12, no. 1, 2012, p. 2.
- [17] R. Chen, J. Shi, Y. Chen, B. Zang, H. Guan, and H. Chen, 'Powerlyra: Differentiated graph computation and partitioning on skewed graphs,' ACM Transactions on Parallel Computing (TOPC) , vol. 5, no. 3, pp. 1-39, 2019.
- [18] L. G. Valiant, 'A bridging model for parallel computation,' Communications of the ACM , vol. 33, no. 8, pp. 103-111, 1990.
- [19] R. Albert and A.-L. Barabási, 'Statistical mechanics of complex networks,' Reviews of modern physics , vol. 74, no. 1, p. 47, 2002.
- [20] M. Daisuke, H. L. Edward, and B. Murmann, 'Convolutional neural networks using logarithmic data representation,' in Deep Learning and
- Unsupervised Feature Learning Workshop, NIPS 2011 , 2016.
- [21] Y. Li, X. Dong, and W. Wang, 'Additive powers-of-two quantization: An efficient non-uniform discretization for neural networks,' arXiv preprint arXiv:1909.13144 , 2019.
- [22] R. Gong, X. Liu, S. Jiang, T. Li, P. Hu, J. Lin, F. Yu, and J. Yan, 'Differentiable soft quantization: Bridging full-precision and low-bit neural networks,' in Proceedings of the IEEE/CVF international conference on computer vision , 2019, pp. 4852-4861.
- [23] J. Yang, X. Shen, J. Xing, X. Tian, H. Li, B. Deng, J. Huang, and X.-s. Hua, 'Quantization networks,' in Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition , 2019, pp. 7308-7316.
- [24] S. Zhang, Z. Jiang, X. Hou, Z. Guan, M. Yuan, and H. You, 'An efficient and balanced graph partition algorithm for the subgraph-centric programming model on large-scale power-law graphs,' in 2021 IEEE 41st International Conference on Distributed Computing Systems (ICDCS) . IEEE, 2021, pp. 68-78.
- [25] J. Peng, Z. Chen, Y. Shao, Y. Shen, L. Chen, and J. Cao, 'Sancus: sta le n ess-aware c omm u nication-avoiding full-graph decentralized training in large-scale graph neural networks,' Proceedings of the VLDB Endowment , vol. 15, no. 9, pp. 1937-1950, 2022.
- [26] W.-L. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh, '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 &amp; data mining , 2019, pp. 257-266.
- [27] K. Wang, Z. Shen, C. Huang, C.-H. Wu, Y. Dong, and A. Kanakia, 'Microsoft academic graph: When experts are not enough,' Quantitative Science Studies , vol. 1, no. 1, pp. 396-413, 2020.
- [28] 'Friendster,' https://snap.stanford.edu/data/com-Friendster.html.
- [29] D. P. Kingma and J. Ba, 'Adam: A method for stochastic optimization,' arXiv preprint arXiv:1412.6980 , 2014.
- [30] R. Mayer and H.-A. Jacobsen, 'Hybrid edge partitioner: Partitioning large power-law graphs under memory constraints,' in Proceedings of the 2021 International Conference on Management of Data , 2021, pp. 1289-1302.
- [31] M. Hanai, T. Suzumura, W. J. Tan, E. Liu, G. Theodoropoulos, and W. Cai, 'Distributed edge partitioning for trillion-edge graphs,' arXiv preprint arXiv:1908.05855 , 2019.
- [32] S. Abadal, A. Jain, R. Guirado, J. López-Alonso, and E. Alarcón, 'Computing graph neural networks: A survey from algorithms to accelerators, ' ACM Computing Surveys (CSUR) , vol. 54, no. 9, pp. 1-38, 2021.
- [33] W.Fan, J. Xu, Y. Wu, W. Yu, and J. Jiang, 'Grape: Parallelizing sequential graph computations,' Proceedings of the VLDB Endowment , vol. 10, no. 12, pp. 1889-1892, 2017.
- [34] G. Malewicz, M. H. Austern, A. J. Bik, J. C. Dehnert, I. Horn, N. Leiser, and G. Czajkowski, 'Pregel: a system for large-scale graph processing,' in Proceedings of the 2010 ACM SIGMOD International Conference on Management of data , 2010, pp. 135-146.
- [35] L. Ma, Z. Yang, Y. Miao, J. Xue, M. Wu, L. Zhou, and Y. Dai, ' { NeuGraph : Parallel deep neural network computation on large } graphs,' in 2019 USENIX Annual Technical Conference (USENIX ATC 19) , 2019, pp. 443-458.
- [36] G. Karypis and V. Kumar, 'A fast and high quality multilevel scheme for partitioning irregular graphs,' SIAM Journal on scientific Computing , vol. 20, no. 1, pp. 359-392, 1998.
- [37] Z. Lin, C. Li, Y. Miao, Y. Liu, and Y. Xu, 'Pagraph: Scaling gnn training on large graphs via computation-aware caching,' in Proceedings of the 11th ACM Symposium on Cloud Computing , 2020, pp. 401-415.
- [38] H. Liu, S. Lu, X. Chen, and B. He, 'G3: when graph neural networks meet parallel graph processing systems on gpus,' Proceedings of the VLDB Endowment , vol. 13, no. 12, pp. 2813-2816, 2020.
- [39] W. Zhang, Z. Yang, Y. Wang, Y. Shen, Y. Li, L. Wang, and B. Cui, 'Grain: Improving data efficiency of graph neural networks via diversified influence maximization,' arXiv preprint arXiv:2108.00219 , 2021.

- [40] W. Zhang, X. Miao, Y. Shao, J. Jiang, L. Chen, O. Ruas, and B. Cui, 'Reliable data distillation on graph convolutional network,' in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data , 2020, pp. 1399-1414.
- [41] R. Zhu, K. Zhao, H. Yang, W. Lin, C. Zhou, B. Ai, Y. Li, and J. Zhou, 'Aligraph: A comprehensive graph neural network platform,' arXiv preprint arXiv:1902.08730 , 2019.
- [42] D. Zhang, X. Huang, Z. Liu, Z. Hu, X. Song, Z. Ge, Z. Zhang, L. Wang, J. Zhou, Y. Shuang et al. , 'Agl: a scalable system for industrial-purpose graph machine learning,' arXiv preprint arXiv:2003.02454 , 2020.
- [43] D. Zheng, C. Ma, M. Wang, J. Zhou, Q. Su, X. Song, Q. Gan, Z. Zhang, and G. Karypis, 'Distdgl: distributed graph neural network training for billion-scale graphs,' in 2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3) . IEEE, 2020, pp. 36-44.
Shuai Zhang Zite Jiang Haihang You
CDFGNN: a Systematic Design of Cache-based Distributed Full-Batch Graph Neural Network Training with Communication Reduction
Graph neural network training is mainly categorized into mini-batch and
full-batch training methods. The mini-batch training method samples subgraphs
from the original graph in each iteration. This sampling operation introduces
extra computation overhead and reduces the training accuracy. Meanwhile, the
full-batch training method calculates the features and corresponding gradients
of all vertices in each iteration, and therefore has higher convergence
accuracy. However, in the distributed cluster, frequent remote accesses of
vertex features and gradients lead to huge communication overhead, thus
restricting the overall training efficiency.
  In this paper, we introduce the cached-based distributed full-batch graph
neural network training framework (CDFGNN). We propose the adaptive cache
mechanism to reduce the remote vertex access by caching the historical features
and gradients of neighbor vertices. Besides, we further optimize the
communication overhead by quantifying the messages and designing the graph
partition algorithm for the hierarchical communication architecture.
Experiments show that the adaptive cache mechanism reduces remote vertex
accesses by 63.14% on average. Combined with communication quantization and
hierarchical GP algorithm, CDFGNN outperforms the state-of-the-art distributed
full-batch training frameworks by 30.39% in our experiments. Our results
indicate that CDFGNN has great potential in accelerating distributed full-batch
GNN training tasks.