Scalable Neural Network Training over Distributed Graphs
Graph neural networks (GNNs) fuel diverse machine learning tasks involving
graph-structured data, ranging from predicting protein structures to serving
personalized recommendations. Real-world graph data must often be stored
distributed across many machines not just because of capacity constraints, but
because of compliance with data residency or privacy laws. In such setups,
network communication is costly and becomes the main bottleneck to train GNNs.
Optimizations for distributed GNN training have targeted data-level
improvements so far -- via caching, network-aware partitioning, and
sub-sampling -- that work for data center-like setups where graph data is
accessible to a single entity and data transfer costs are ignored.
  We present RETEXO, the first framework which eliminates the severe
communication bottleneck in distributed GNN training while respecting any given
data partitioning configuration. The key is a new training procedure, lazy
message passing, that reorders the sequence of training GNN elements. RETEXO
achieves 1-2 orders of magnitude reduction in network data costs compared to
standard GNN training, while retaining accuracy. RETEXO scales gracefully with
increasing decentralization and decreasing bandwidth. It is the first framework
that can be used to train GNNs at all network decentralization levels --
including centralized data-center networks, wide area networks, proximity
networks, and edge networks.
Aashish Kolluri, Sarthak Choudhary, Bryan Hooi, Prateek Saxena
# Retexo: Scalable Neural Network Training over Distributed Graphs

###### Abstract

Graph neural networks offer a promising approach to supervised learning over graph data. Graph data, especially when it is privacy-sensitive or too large to train on centrally, is often stored partitioned across disparate processing units (clients) which want to minimize the communication costs during collaborative training. The fully-distributed setup takes such partitioning to its extreme, wherein features of only a single node and its adjacent edges are kept locally with one client processor. Existing GNNs are _not_ architected for training in such setups and incur prohibitive costs therein. We propose Retexo, a novel transformation of existing GNNs that improves the communication efficiency during training in the fully-distributed setup. We experimentally confirm that Retexo offers up to \(6\)_orders of magnitude better communication efficiency_ even when training shallow GNNs, with a minimal trade-off in accuracy for supervised node classification tasks.

Machine Learning, ICML

## 1 Introduction

Graph neural networks (GNN) are designed for learning representations over graph data which are useful for classification, regression, and other applications. GNNs have been deployed for serving recommendations, financial fraud detection, and language modeling and are reported to offer state-of-the-art performance (Wu et al., 2020; Zhou et al., 2020). However, their design thus far has centered mainly for the centralized setup where the graph data is stored and processed in centralized servers. The centralized setup is not ideal due to its threat to security and privacy of user's data (Cadwalldar & Graham-Harrison, 2018; Illmer, 2021). Services that build on distributed graphs are becoming popular as alternatives to the centralized ones. For instance, social networks such as Signal and Mastodon do not store the social graph at centralized servers (Marlinspike, 2017; Mastodon, 2022). Graphs capturing location traces, health data, and financial transactions can also be distributed across mutually untrusting parties (Suzumura et al., 2019; Hulsen, 2020). Thus, designing machine learning protocols for distributed graphs enable the aforementioned GNN-based applications with better privacy and data sovereignty.

In this paper, we introduce the problem of learning neural networks for supervised node classification on fully-distributed graphs. In such graphs, each node stores its features and edges locally on its trusted device (client) such as a mobile or an IoT device. The clients along with a server (of a service provider) aim to learn a machine learning model, in a supervised fashion, that can be used to classify the nodes based on their features and the graph structure. This setup applies to health monitoring over bluetooth-proximity networks, serving recommendations in distributed social networks, and social fitness tracking applications (Dong et al., 2021; Gui et al., 2017; Madan et al., 2010).

Existing GNNs have not been designed for training in a fully-distributed setup and retrofitting them directly to this setup leads to high communication costs. For example, a standard graph convolutional network (GCN) with \(K\) trainable layers would require message-passing, i.e., propagating the layers and other intermediate node representations between clients during each round of training. The clients with ground-truth labels (_train-clients_) would engage their \(K\)-hop neighborhood in multiple client-to-client interactions in every round of training. Typically, there are hundreds of training rounds. This overhead is prohibitively high, especially for bandwidth-constrained clients. Further, clients may not be available for such communication to ensure successful completion of every training round. Therefore, it is important to devise GNNs for which training has much lower client-to-client communication costs.

We propose Retexo, the first framework for training neural networks, that are transformations of existing message-passing GNN architectures, in the fully-distributed setup. For instance, a graph convolutional network GCN can be transformed to its corresponding RetexoGCN. Unlike
GNNs, training RetexoGNNs needs only \(K\) rounds of message-passing between clients. The key idea in RetexoGNNs is to disentangle the aggregation of intermediate representations over graph edges from the end-to-end training of the model. Instead, RetexoGNNs are trained layer-by-layer and only after fully training every layer, the embeddings (logits) output by the trained layer are propagated over the graph edges. The propagated embeddings are aggregated in the way existing GNNs do and the aggregated embeddings are used as features to train the next layer.

We emphasize that Retexo offers generic flexibility at retrofitting to several base GNN architectures that exist today. Retexo does not assume anything about the structural properties of the graph, correlations between features and attributes, and the aggregation mechanisms of the base GNN. Therefore, GNNs designed for all kinds of graph datasets, such as homophilous, heterophilous and inductive settings, can be transformed in to their distributed counterparts.

To show its wide applicability, we evaluate RetexoGNNs on common real-world graph datasets for the transductive, heterophilous, and inductive setups. We find that classification accuracy of RetexoGNNs is within \(1.2\%\) of their respective GNNs on average in our evaluated configurations. If GNNs and RetexoGNNs were to be implemented for the fully-federated setup, we measure how much data is transferred per client to train the models. The total data transferred on client-to-client communication channels per client in RetexoGNNs is **up to 6 orders of magnitude (\(\mathbf{10^{6}\times}\)) lower** in comparison to base GNNs. The total data transferred per client across both client-to-client and client-to-server channels is up to \(20\times\) lower for training RetexoGNN than for the base GNN.

Broader ImpactWe only highlight Retexo's applicability for the fully-distributed setup, however, Retexo can be used in any distributed setup. For instance, efficiently training GNNs in the federated setup, where the graph is split into few large subgraphs with one subgraph stored per client, is being studied extensively (Zhang et al., 2021; Wang et al., 2022; Md et al., 2021; He et al., 2021; Gandhi and Iyer, 2021). RetexoGNNs can be cheaper to train than their corresponding GNNs in the federated setup as well due to much fewer rounds of client-to-client communication.

## 2 Background & Problem

Consider an graph \(\mathcal{G}:(\mathcal{V},\mathcal{E})\) which has nodes \(\mathcal{V}\) and edges \(\mathcal{E}\). Each node has attribute or feature vector of \(I\) dimensions, given by the node-feature map \(\mathbf{F}:\mathcal{V}\rightarrow\mathbb{R}^{I}\), and its neighbors are denoted as the set \(\mathcal{N}(v)\).

Message-passing Graph Neural Networks.A GNN model (\(\mathbf{M}:(v,\mathcal{G},\mathbf{F}))\rightarrow\mathbb{R}^{O}\) takes a node, all features of all nodes, and the graph as an input. It outputs the node embeddings for the given node \(v\). We focus on _message-passing_ GNNs which are widely-used in practice, wherein every node aggregates representations from its \(m\)-hop neighbors and concatenates with its own representation in each round \(m\in[1,\dots,K]\). \(K\) is a parameter between \(2-5\) specified by the architecture. Therefore, the representation of the node \(v\) after \(m\) rounds of message passing will be:

\[\mathbf{Q}_{v}^{m}=\mathbf{f}_{\theta}^{m-1}(\mathsf{COMBINE}(\mathbf{Q}_{v}^{ m-1},\mathsf{AGGR}_{u\in\mathcal{N}(v)}^{m-1}(\mathbf{Q}_{u}^{m-1})))\]

Here, \(\mathbf{f}_{\theta}^{m-1}\) is a non-linear function with learnable parameters, \(\mathsf{COMBINE}\) is usually the concatenate operation, and \(\mathsf{AGGR}\) represents aggregation functions that may have learnable parameters. \(\mathsf{AGGR}\) functions vary with different GNNs. For example, \(\mathsf{AGGR}\) is the mean operator in GCNs (Kipf and Welling, 2016) or a max-pooling layer in GraphSage (Hamilton et al., 2017). In essence, to get the \(m^{th}\) representation of a node, a non-linear transformation over an aggregate of the \(m\)-\(1^{th}\) representations of it neighbors are used.

The goal of training a GNN is to find the values of \(\mathbf{f}_{\theta}^{m-1}\) and \(\mathsf{AGGR}^{m-1}\) functions \(\forall m\in\{1\cdots K\}\). These parameters are optimized for accuracy on upstream tasks such as supervised node classification, which is our focus as well.

Prior Setups.Prior work has considered two different setups for supervised node classification (see Figure 1, (a)). In the centralized setup, which is most widely used, the entire graph including node attributes and the structure is stored

Figure 1: Training GNNs for supervised node classification across three different setups—centralized, federated and fully-distributed.
and processed at one central server. The server is trusted and it bears the costs of learning the model. In contrast, the more recently proposed federated setup (Figure 1, (b)) for graph learning has a central server that does _not_ have the full graph. The graph is partitioned into sub-graphs and stored on a few clients, typically \(5\)-\(20\), and each such client is trusted with storing a large sub-graph. The central server and the clients collaborate with each other to learn a GNN, and the clients do not reveal the raw sub-graphs to the server in this process. This setup is useful when the clients may belong to different organizations (e.g. banks, drug discovery companies, or hospitals) or when the clients are servers of an organization that are available across geopolitical boundaries (Wang et al., 2022). Raw data sharing across clients is disallowed by privacy laws and regulations in such setups.

Training in the federated setup has higher costs than in the centralized setup. In every training round, the clients communicate with each other to pass intermediate representations and gradients across the cross-client edges and with the server to share intermediate models. However, the clients are still trusted "centralized" servers with large sub-graphs and the communication costs, especially client-to-client, can be optimized using their sub-graphs (see Section 6). Further, the federated graph learning libraries may ignore the cross-client edges too (Wang et al., 2022; He et al., 2021).

### Node Classification on Fully-Distributed Graphs

Unlike prior setups, we propose the _fully-distributed_ setup where the clients can hold only one node's data, taking the federated setup to an extreme. Specifically, a client contains a node with attributes and the node's edges. There is a server which knows the identities of the clients in the graph. We study the supervised node classification problem where the server knows the labels for a small fraction of the nodes and the goal is to learn a model that can classify the remaining nodes into prior-known \(O\) label categories. Classification can be for other nodes in the same graph (_transductive setting_) or on an unseen graph (_inductive setting_). The latter is important for evolving graphs.

We do not consider the labels as private in this work, however, our proposed solution can be adapted to the setup where the clients do not reveal their labels to the server with minor changes. Clients share only the intermediate gradients and embeddings, not raw features, as is also the case in federated learning protocols. All involved parties are assumed to be honest, i.e., the server and the clients would follow the protocol. Figure 1(c) illustrates this setup.

Concrete Application.Mobile sensing based proximity networks and distributed social networks are the most popular examples of this setup. Consider the proximity networks formed by user's mobile devices using sensors such as blue-tooth. Proximity networks model users' short-term and recurring physical interactions which implies that they can be used to model social influence propagation, location traces, and infectious diseases (Pan et al., 2011; Madan et al., 2010; Hernandez-Orallo et al., 2020). Consequently, supervised node classification on proximity networks can enable important applications such as health monitoring, serving recommendations, and sentiment analysis. For instance, GNNs achieve state-of-the-art performance in predicting symptoms caused by Influenza using supervised node classification on proximity networks (Dong et al., 2021). However, users might not want to reveal their sensitive attributes and edges in the physical proximity network to any external centralized services. Therefore, enabling GNNs on the fully-distributed proximity networks helps such applications.

Evidently, the clients in a fully-distributed network may be bandwidth-constrained and the client-to-client communication networks may be asynchronous and unreliable (due to mobility). How do we train a GNN in the fully-distributed setup for supervised node classification efficiently?

## 3 GNNs for Fully-Distributed Setup

Existing GNNs do not naturally extend to the proposed setup since message-passing is built into the end-to-end training process. We illustrate this using a \(2\)-layer GCN.

Graph convolutional network (GCN).GCN is a canonical example of message-passing GNNs with the AGGR being a mean function, i.e., a node's representation is an average of its neighbors' representations. For a GCN:

\[\mathbf{Q}_{v}^{m}=\theta^{m-1}\cdot\mathsf{Concat}(\mathbf{Q}_{v}^{m-1}, \mathsf{Mean}_{u\in\mathcal{N}(v)}(\mathbf{Q}_{u}^{m-1}))\]

\(\mathbf{Q}^{0}\) is the input node features with dimension \(I\), and \(\theta^{m-1}\) are the weight parameters with hidden size \(H\). 1

Footnote 1: In practice, there is a non-linear activation (ReLU) on every \(\theta\).

Therefore, a GCN can be parameterized by its set of weight layers \(\{\theta^{0},\cdots,\theta^{m-1}\}\). A two layer GCN can be simply represented as \(\{\theta^{0}_{IH},\theta^{1}_{HO}\}\). \(\theta^{0}_{IH}\) represents the first layer which transforms the input node features with dimension \(I\) to the hidden dimension of size \(H\). \(\theta^{1}_{HO}\) represents the second layer which transforms the hidden features with dimension \(H\) to output embedding with dimension \(O\).

### Baseline: Fully Distributed GCNs

When a GCN is trained as-is in a fully distributed setup, the communication costs will be high. The GCN is trained across \(R\) training rounds. Each training round begins with the server sending an aggregated model to the train-clients. The train-clients then perform two message-passing rounds, one each for the forward and the backward pass, wherein
they mobilize the clients in their \(2\)-hop neighborhood. Figure 2 shows the message-passing for the forward pass.

In the forward pass, a train-client will send the first layer of the GCN to its neighbors and ask them for their initial representations, i.e., raw features (see (1) in Figure 2). 2 The \(1\)-hop neighbors will then ask their neighbors for their initial representations. The \(2\)-hop and \(1\)-hop neighbors will send their initial representations to their neighbors (2). The \(1\)-hop neighbors will use their neighbors' initial representations and the first layer to compute the hidden representations, which they send to the train-clients (3). The train-clients use the initial and hidden representations of their neighbors to compute the output embedding.

Footnote 2: Sending raw features can be avoided by using an additional non-invertible weight layer on the features before aggregation.

The backward pass would also require another round of message-passing since certain weights are shared by multiple nodes. Concretely, the train-client would have to ask its neighbors for certain factors to compute the gradient and the neighbors might need some factors from theirs too.

Appendix A gives more details of the training process. One noteworthy point here is that clients have to send layer parameters to their neighbors in the above process. This is because the server does not know neighbors of any client.

### Problems with Distributed GCN

Challenge 1.In each training round, GCN requires many rounds of communication between the clients in \(K\)-hop neighborhoods. This leads to _high latency and data transfer volumes_. For instance, the clients in proximity networks could be mobile phones with low-bandwidth networks.

Challenge 2.Implementing the backward pass is akin to re-designing the automatic gradient computation used in the popular machine learning libraries for the fully-distributed setup. This is a challenge in itself and further demands _high availability_ from the clients. For instance, in proximity networks, it can be difficult to ensure the availability of the neighbors of a node at the same time for both forward and backward passes. The problem is exacerbated when \(2\)-hop (and higher order) neighbors are necessary. Even if everyone was available for one round, doing this for all training rounds is not practical.

We explain next why the client-to-client communication overheads for training even a 2-layer neural network in practice can be in the order of gigabytes for a client.

_Forward pass, sharing model:_ In a \(2\)-layer GCN, when the degree of a train-client is \(d\), the train-client will have to first send the parameters of the first layer to its \(d\) neighbors. The size of the first layer will be \(2IH\) and the number of parameters sent by the train-clients is \(2IH\cdot d\). The clients from the \(1\)-hop neighborhood would receive the layer. The total number of parameters received by such clients would be \(2IH\). Across \(R\) rounds of training, the data transferred by the train-clients just for sharing the models with neighbors is \(2IHdR\times 32\) bytes. 3 Further, the data transferred by each neighbor of the train-clients is \(2IHR\times 32\) bytes. The hidden representations and factors required for gradients would be \(O((I+H)\cdot d)\) and \(O(I\cdot d)\) bytes respectively.

Footnote 3: Assuming the parameters are represented using \(32\)-bit floating point precision.

Cost Illustration.Consider a \(2\)-layer GCN where \(I=1000\) and \(H=256\). Let there be a train-client with \(d=10\) neighbors. The total data transferred by it during forward pass, for one training round, would be \(2\times 1000\times 256\times 10\times 32=160\) Mb. If the model is trained for \(R=400\) rounds, the total data transferred just for message-passing during forward pass for that train-client is \(64\) Gb. Further, the neighbors of this train-client would transfer at least \(6.4\) Gb. For each train-client and their neighbors, these costs would increase linearly with degree, input size, size additional pooling layers, and the number of layers \(K\).

## 4 The Retexo GNN Architecture

We present a novel graph learning architecture called Retexo that requires much fewer message-passing rounds for training. Retexo can be seen as a generic transformation of a traditional GNN into its Retexo counterpart. Retexo architectures retain the AGGR and COMBINE functions in the original GNNs. This is important for preserving accuracy in homophilous, heterophilous (Zheng et al., 2022), and inductive settings (Hamilton et al., 2017).

The graph edge structure is directly encoded as a sandwiched layer in a traditional GNN architecture. Therefore, all layers parameters are optimized simultaneously in each

Figure 2: A single train-client \(v_{i}\) performing forward pass with its \(1\)-hop neighbor \(v_{j}\) and \(2\)-hop neighbor \(v_{k}\) in one training round.
training round. In a fully-distributed setup, this is expensive as it requires syncing parameter state between neighbors in a training round. Our framework Retexo remedies the architecture by _decoupling_ the edge structure from training of layers and delaying the message-passing to only _after_ the training of one layer completes. For instance, if a GCN has \(2\) layers then the Retexo framework will deconstruct the layers and train them sequentially one after another. After training each layer, its output logits are sent between neighbors in one message-passing round. Once the nodes receive their neighbors' logits, they will compute the AGGR and COMBINE functions and use the aggregated logits as features to train the next layer. We illustrate this in Figure 3.

The number of message-passing rounds in a RetexoGNN equal the number of layers (\(K\)) in the original GNN, but crucially, are independent of the number of training rounds (\(R\)). This drastically reduces the total number of message-passing rounds from \(O(R)\) to \(K\). Computing gradients while training the layers does not require any message-passing between clients. Furthermore, Retexo naturally extends to the federated setup wherein a large sub-graph is stored at every client instead of a single node. Therefore, Retexo remains compatible with training improvements developed for the federated learning setup as well. Examples of such improvements include federated optimization (Reddi et al., 2020), handling for asynchronous real-world deployments (Bonawitz et al., 2019; Nguyen et al., 2022), defenses against data poisoning, and training for better robustness (Liu and Yu, 2022).

### Architecture of RetexoGNNs

For a \(K\)-layer base GNN, a RetexoGNN counterpart is a collection of \(K+1\) independent trainable models.

In RetexoGNN (Figure 3, right side), the first model is an MLP which is used to learn embeddings from the node features. 4 There is no AGGR before the first MLP since that requires propagating raw features. There are \(K\) more MLPs after the first one, each having the AGGR and COMBINE layers of the base GNN. RetexoGNN's intermediate embeddings (logits after every model) are given by:

Footnote 4: In fact, this model could be any classifier, such as a CNN.

\[\mathbf{Q}_{v}^{1} =\mathbf{f}_{\theta}^{0}(Q_{v}^{0})\] \[\mathbf{Q}_{u}^{m} =\mathbf{f}_{\theta}^{m-1}(\mathsf{COMBINE}(\mathbf{Q}_{v}^{m-1}, \mathsf{AGG}_{u\in\mathcal{N}(v)}(\mathbf{Q}_{u}^{m-1})))\] \[\mathbf{f}_{\theta}^{0} =\text{ MLP}_{0}=(\theta_{H}^{0},\theta_{HO}^{0})\] \[\mathbf{f}_{\theta}^{m-1} =\text{ MLP}_{m-1}=(\theta_{OH}^{m-1},\theta_{HO}^{m-1}),\;m\in\{2, \ldots,K+1\}\]

In \((\theta_{OH}^{m-1},\theta_{HO}^{m-1})\), the \(\theta_{OH}^{m-1}\) converts the aggregated embeddings to a representation of size \(H\) and the \(\theta_{HO}^{m-1}\) converts that into the output. In our running example, the \(2\)-layer RetexoGCN can be represented by \(\{\text{MLP}_{0}:(\theta_{IH}^{0},\theta_{HO}^{0}),\text{ MLP}_{1}:(\theta_{OH}^{1},\theta_{HO}^{1}),\text{ MLP}_{2}:(\theta_{OH}^{2},\theta_{HO}^{2})\}\).

### Training a RetexoGNN

For training every MLP we use the traditional federated learning approaches. Before training each MLP, except the first one, we do a message-passing round to get the embeddings from a node's neighbors. We describe an outline of the training protocol here (see Algorithm 1) and provide full details, for the federated learning and message passing protocols, in the Appendix B.

Federated Learning.The server and the clients together train \(K+1\) models sequentially. For each model, the training proceeds in rounds. The server samples a subset of the train-clients for each round and delegates training / validation tasks to them. In each training task, the server shares the model parameters with the selected clients. The clients then perform a forward and backward pass on the model using their local data. The clients then return the updated model to the server. In each validation task, the server just asks the clients to report their accuracy. Notice that for the AGGR layer, the client uses the embeddings collected from its neighbors in the previous message-passing round. Each client has a single input (feature vector and a label). Hence, it carries out only a single forward and backward pass per training round. Therefore, this is equivalent to the standard FedSGD training protocol. For the federated setup with multiple nodes per client, one can instead use the FedAVG protocol wherein multiple forward and backward passes are carried out locally on the client (McMahan et al., 2017).

Message-Passing.Before training the \(m^{th}\) MLP, the server initializes a message-passing round by sending all the clients the \((m-1)\) trained MLP parameters, i.e., it syncs the latest model with the clients. The clients then compute embeddings from it and share them with their neighbors. For example, consider a RetexoGNN with three MLP and say the server is training its third MLP. At this point, the server sends the second model to all clients. So, now all clients will have the first MLP (\(\text{MLP}_{0}\)), their own first embeddings output by their first MLP (\(\mathbf{Q}_{v}^{1}\)), the first embeddings obtained from their neighbors (\(\mathbf{Q}_{u}^{1}\), \(u\in\mathcal{N}(v)\)) from the previous message passing round, and the second MLP (\(\text{MLP}_{1}\)). The clients locally compute \(\mathbf{Q}_{v}^{2}\) using this

Figure 3: Base GNN to its RetexoGNN.
information. The clients then share \(\mathbf{Q}_{v}^{2}\) with their neighbors to complete the current message-passing round.

Retexo allows the communication network to be asynchronous. The server starts a message-passing round and lets the computation take as long as needed. In proximity networks, clients can communicate information with neighbors when in close proximity using Nearby Share or Airdrop protocols (Google; Apple). In distributed social networks, the clients do not need to be in proximity or have public IP addresses. Instead, WebRTC can be used (WebRTC).

In highly asynchronous networks, one successful message-passing round including the sync, can take a few seconds to few hours before we can start the training procedure. This underscores the importance of having only few of message-passing rounds. We emphasize that, unlike in a GNN, training RetexoGNN would require clients to share only the embeddings and only once per message-passing round which is practical even in weak mobile network environments. Further, having only \(K\) rounds of message-passing makes it feasible for the server to sync the model with all the clients after training it.

All neighbors of a train client do not need to be available for a message-passing round; the client can aggregate embeddings received from the available nodes. Retexo is robust to such unavailability. More experiments reported in Appendix D elaborate on this feature of RetexoGNNs.

## 5 Evaluation

We evaluate RetexoGNNs on \(2\) aspects:

**Performance.** What accuracy do RetexoGNNs achieve in the transductive, inductive, and heterophilous settings?

**Communication Efficiency.** How do RetexoGNNs communication costs compare to those of the baseline GNNs in the fully distributed setup?

### Experimental Setup

We consider three widely-used traditional GNNs that are known to perform well across most settings: GCN (Kipf and Welling, 2016), GraphSAGE (Hamilton et al., 2017), and GAT (Velickovic et al., 2017). 5 For GraphSAGE, we use the max-pooling layer for aggregation.

Footnote 5: We use simple mean aggregation instead of localized spectral convolution for GCN as described here (Hamilton et al., 2017).

Datasets.For the transductive setting, we evaluate on \(7\) datasets--Cora, Citeseer, PubMed, Facebook, LastFMAsia, Wiki-cooc, and Roman-empire. The first \(5\) datasets are commonly used for the homophilous setting (Wu et al., 2020) and the latter \(2\) have been introduced recently for the heterophilous setting (Anonymous, 2023). We use \(5\) to \(10\%\) of the nodes for training and validation each. For smaller datasets we use 10% so that there are enough nodes for training and for the larger ones we use 5%. For the inductive setting, we construct evolving graphs similar to prior work, from the homophilous-transductive datasets (Zeng et al., 2019). For the homophilous-transductive and the inductive settings, we use \(2\)-layer GNNs and for the heterophilous-transductive setting, we use \(5\)-layer GNNs as recommended here (Anonymous, 2023). We then construct the RetexoGNNs that correspond to these GNNs. We provide full details on the datasets, splits, and architectures in Appendix C.1.

Implementation & Training.We first implemented the baseline GNNs and their respective RetexoGNNs on the centralized server. We further implemented RetexoGNNs in the FederatedScope library (Wang et al., 2022) to confirm that our implementations in the centralized setup transfer to the fully-distributed setup. Our designs are carefully implemented such that all operations performed in the centralized setup can be extended to the fully-distributed setup as is. We only use the SGD optimizer with momentum and weight decay since other optimizers lead to unpredictable results when there is only one node per client. For similar reasons, we do not use dropout and batch normalization.

For measuring communication costs, we do not run baseline GNNs and RetexoGNNs on a real distributed network and instead report on the communication-efficiency (data transferred between clients) in our simulations on the centralized setup. To emulate practical implementations of federated learning protocols, we diverge from the traditional epoch-based training in the centralized setup to
round-based (Bonawitz et al., 2019). In each round, we randomly sample a batch of train nodes and validation nodes, up to \(1024\) total, independent of the previous rounds. We fix the total number of rounds to \(400\) in the transductive and inductive settings whereas \(1000\) in the heterophilous setting. We sample the neighbors considered for aggregation up to a maximum of \(25\) across every hop, as in (Anonymous, 2023).

We report accuracy of all models under their best hyperparameter settings found using grid search (see Appendix C). We also separately report validation accuracies with early-stopping to show how it can further reduce communication costs for a small drop in accuracy.
criteria to early-stop across all evaluated configurations. So, we manually choose the patience as \(30\) since that is much smaller than \(400\) and gave us the best results for GNNs in most configurations. In Figure 4 (right side) we report the results for these experiments. Consider the example of GraphSAGE vs RetexoSage. On client-to-client channels, the total data transferred for GraphSAGE is about \(3.3\times 10^{6}\) MB and RetexoSage is \(1.13\) MB which is \(10^{6}\times\) lower. On both channels together, the total data transferred for GraphSAGE and RetexoSage is about \(4.3\times 10^{6}\) MB and about \(2.4\times 10^{5}\) MB respectively, which is \(20\times\) lower. We report the remaining evaluated configurations in Appendix D.

To summarize, RetexoGNNs by design have minute communication costs, up to \(10^{6}\times\) lower, on client-to-client channels compared to GNNs even with early-stopping. Further, as GNNs become deeper, with higher \(K\) for instance in the heterophilous setting, the difference in communication costs between GNNs and RetexoGNNs will only increase.

## 6 Related Work

Training GNNs in the federated setup for node classification tasks on a single connected graph is popular, see surveys (He et al., 2021; Liu and Yu, 2022). The protocols (Zheng et al., 2021; Wang et al., 2020; Chen et al., 2021) ignore cross-client edges, i.e., the clients do not propagate messages across such edges. The remaining protocols (Zhang et al., 2021; Wan et al., 2022; Yao and Joe-Wong, 2022; Chen et al., 2021; Md et al., 2021) consider aggregating information from cross-client edges either directly by propagating messages or by generating synthetic graphs to mimic cross-client graph information. However, none of these works have considered the fully-distributed setup and are also motivated differently. For instance, one motivation is to increase the efficiency of training on large graphs using distributed computation with shared memory. Further, these protocols do not extend to the fully-distributed setup since they either assume or only work if there are a large number of nodes stored in one client. (Zhang et al., 2021) relies on each client generating synthetic graphs based on the subgraph it stores. (Wan et al., 2022) require an initialization step of partitioning the graph across clients to minimize the inter-client communication. In contrast, it is straight-forward to extend Retexo to the federated setup considered by these protocols since, outside of message-passing, Retexo mimics the typical federated learning setup irrespective of the number of nodes per client. RetexoGNNs would still require only \(K\) rounds of message-passing across the clients.

Alternative federated setups have also been studied for node and graph classification tasks where clients store disjoint graphs. None of the protocols designed for these setups apply to ours. In the federated setup for graph classification, the clients store multiple full graphs, such as molecules, where each graph has a label associated with it. The task is to collaboratively learn a GNN that can be used by the clients to label their local graphs (Jiang et al., 2020; He et al., 2021; Xie et al., 2021). Vertically federated setup considers federated graph learning where the same nodes are present across different clients but their features are split among clients (Chen et al., 2020). Protocols have also been designed for user-item bipartite graphs to do item recommendations (Wu et al., 2021). (Scardapane et al., 2020) propose a serverless distributed protocol, to train a GNN, where clients have their own communication channels between them which may be different from the actual graph edges. This protocol also relies on the clients storing large subgraphs and incurs significant communication costs to do distributed consensus in the absence of a server. Extending

\begin{table}
\begin{tabular}{l|l|l|l|l|l|l|l} Method & Cora & Citeseer & PubMed & Facebook & LastFMAsia & Wiki-cooc & Roman-empire \\ \hline MLP & \(0.644\pm 0.011\) & \(0.652\pm 0.007\) & \(0.779\pm 0.006\) & \(0.710\pm 0.007\) & \(0.645\pm 0.007\) & \(0.895\pm 0.005\) & \(0.653\pm 0.004\) \\ GCN & \(0.814\pm 0.014\) & \(0.710\pm 0.007\) & \(0.825\pm 0.003\) & \(0.871\pm 0.002\) & \(0.804\pm 0.007\) & \(0.918\pm 0.005\) & \(0.752\pm 0.004\) \\ RetexoGCN & \(0.763\pm 0.011\) & \(0.702\pm 0.011\) & \(0.801\pm 0.008\) & \(0.816\pm 0.010\) & \(0.756\pm 0.010\) & \(0.940\pm 0.004\) & \(0.804\pm 0.005\) \\ GraphSAGE & \(0.805\pm 0.010\) & \(0.699\pm 0.006\) & \(0.815\pm 0.004\) & \(0.894\pm 0.005\) & \(0.815\pm 0.005\) & \(0.936\pm 0.007\) & \(0.815\pm 0.005\) \\ RetexoSage & \(0.785\pm 0.010\) & \(0.705\pm 0.010\) & \(0.806\pm 0.010\) & \(0.843\pm 0.009\) & \(0.788\pm 0.010\) & \(0.9616\pm 0.010\) & \(0.835\pm 0.004\) \\ GAT & \(0.813\pm 0.014\) & \(0.707\pm 0.008\) & \(0.815\pm 0.003\) & \(0.877\pm 0.006\) & \(0.808\pm 0.009\) & \(0.976\pm 0.009\) & \(0.800\pm 0.009\) \\ RetexoGAT & \(0.802\pm 0.013\) & \(0.711\pm 0.006\) & \(0.804\pm 0.011\) & \(0.851\pm 0.006\) & \(0.807\pm 0.006\) & \(0.972\pm 0.004\) & \(0.816\pm 0.005\) \\ \end{tabular}
\end{table}
Table 1: Micro-F1 scores for node classification in the transductive setting.

\begin{table}
\begin{tabular}{l|l|l|l|l|l} Method & Cora & Citeseer & PubMed & Facebook & LastFMAsia \\ \hline MLP & \(0.593\pm 0.012\) & \(0.623\pm 0.020\) & \(0.769\pm 0.031\) & \(0.708\pm 0.005\) & \(0.603\pm 0.010\) \\ GCN & \(0.747\pm 0.016\) & \(0.689\pm 0.018\) & \(0.828\pm 0.009\) & \(0.850\pm 0.007\) & \(0.757\pm 0.005\) \\ RetexoGCN & \(0.670\pm 0.021\) & \(0.673\pm 0.015\) & \(0.807\pm 0.012\) & \(0.810\pm 0.008\) & \(0.712\pm 0.013\) \\ GraphSAGE & \(0.709\pm 0.024\) & \(0.684\pm 0.020\) & \(0.816\pm 0.007\) & \(0.876\pm 0.006\) & \(0.760\pm 0.011\) \\ RetexoSage & \(0.722\pm 0.025\) & \(0.664\pm 0.027\) & \(0.808\pm 0.010\) & \(0.836\pm 0.007\) & \(0.741\pm 0.010\) \\ GAT & \(0.769\pm 0.015\) & \(0.685\pm 0.017\) & \(0.810\pm 0.008\) & \(0.827\pm 0.019\) & \(0.743\pm 0.014\) \\ RetexoGAT & \(0.743\pm 0.030\) & \(0.683\pm 0.018\) & \(0.808\pm 0.011\) & \(0.860\pm 0.006\) & \(0.774\pm 0.012\) \\ \end{tabular}
\end{table}
Table 2: Micro-F1 scores for node classification in the inductive setting.
Retexo to these setups is an interesting future work.

## 7 Conclusion

We have presented new neural network architectures, RetexoGNNs, that are practical to train on fully-distributed graphs, as they offer significantly lower communication costs for training compared to existing GNN architectures.

To reproduce our experiments, we release our code here. 6

Footnote 6: [https://github.com/aashishkolluri/retexognn-prototype](https://github.com/aashishkolluri/retexognn-prototype)
