: Scalable Neural Network Training over Distributed Graphs

Aashish Kollurisoc
Sarthak Choudharybits
Bryan Hooisoc
Prateek Saxenasoc

socSchool of Computing, National University of Singapore, Singapore
bitsSchool of Computing, BITS Pilani, India, (Work done during internship at NUS)

Aashish<EMAIL_ADDRESS>Sarthak<EMAIL_ADDRESS>Bryan<EMAIL_ADDRESS>Prateek<EMAIL_ADDRESS>
Machine Learning, ICML

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 , a novel transformation of existing GNNs that improves the communication efficiency during training in the fully-distributed setup. We experimentally confirm that 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.

§ 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 [Cadwalladr & 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 $\num$ 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.

Training GNNs for supervised node classification across three different setups—centralized, federated and fully-distributed.

We propose , 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 can be transformed to its corresponding . Unlike GNNs, training needs only $\num$ rounds of message-passing between clients. The key idea in is to disentangle the aggregation of intermediate representations over graph edges from the end-to-end training of the model. Instead,  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 offers generic flexibility at retrofitting to several base GNN architectures that exist today. 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 on common real-world graph datasets for the transductive, heterophilous, and inductive setups. We find that classification accuracy of is within $1.2\%$ of their respective GNNs on average in our evaluated configurations. If GNNs and 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 is up to 6 orders of magnitude ($\bf 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 than for the base GNN.

Broader Impact We only highlight 's applicability for the fully-distributed setup, however, 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 & Iyer, 2021]. 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.

§ BACKGROUND & PROBLEM

Consider an graph $\Gc:(\Vc, \Ec)$ which has nodes $\Vc$ and edges $\Ec$. Each node has attribute or feature vector of $I$ dimensions, given by the node-feature map $\feat:\Vc\xrightarrow{}\mathbb{R}^{I}$, and its neighbors are denoted as the set $\set{N}(v)$.

Message-passing Graph Neural Networks. A GNN model ($\fc{M}:(v, \Gc, \feat))\xrightarrow{}\mathbb{R}^\numlabels$) 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 $\hopiter$-hop neighbors and concatenates with its own representation in each round $\hopiter \in [1,\dots,K]$. $\num$ is a parameter between $2-5$ specified by the architecture.

Therefore, the representation of the node $v$ after $\hopiter$ rounds of message passing will be:

\arr{Q}^{\hopiter}_v = \fc{f}^{\hopiter-1}_\theta(\cf{COMBINE}(\arr{Q}^{\hopiter-1}_v, \cf{AGGR}^{\hopiter-1}_{u\in\set{N}(v)}(\arr{Q}^{\hopiter-1}_u)))

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

The goal of training a GNN is to find the values of $\fc{f}^{\hopiter-1}_\theta$ and $\cf{AGGR}^{\hopiter-1}$ functions  $\forall m \in\{1\cdots \num\}$. 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 <ref>, (a)). In the centralized setup, which is most widely used, the entire graph including node attributes and the structure is stored 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 <ref>, (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 <ref>). 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 $\numlabels$ 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 <ref>(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 bluetooth. 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, Hernández-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?

§ 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 .

Graph convolutional network (GCN).

is a canonical example of message-passing GNNs with the $\cf{AGGR}$ being a mean function, i.e., a node's representation is an average of its neighbors' representations. For a :

\arr{Q}^\hopiter_v = \arr{\theta}^{\hopiter-1}\cdot\cf{Concat}(\arr{Q}^{\hopiter-1}_{v}, \cf{Mean}_{u\in\set{N}(v)}(\arr{Q}_{u}^{\hopiter-1}))
% \tilde{\Ac}\cdot \arr{Q}_{u}^{\hopiter-1})
% \text{, }
% \arr{Q}^{k} &= \sigma(\tilde{\Ac}\cdot \arr{Q}^{k-1}\cdot \arr{\theta}^{k-1})\\
% \tilde{\Ac} = \arr{D}^{-1}\cdot\Ac %\text{, }

$\arr{Q}^0$ is the input node features with dimension $I$, and $\arr{\theta}^{\hopiter-1}$ are the weight parameters with hidden size $H$. [In practice, there is a non-linear activation (ReLU) on every $\theta$.]

Therefore, a can be parameterized by its set of weight layers $\{\arr{\theta}^0,\cdots, \arr{\theta}^{\hopiter-1}\}$.

A two layer can be simply represented as $\{\arr{\theta}^0_{IH}, \arr{\theta}^{1}_{HO}\}$. $\arr{\theta}^0_{IH}$ represents the first layer which transforms the input node features with dimension $I$ to the hidden dimension of size $H$. $\arr{\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 is trained as-is in a fully distributed setup, the communication costs will be high. The is trained across $\numrounds$ 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 <ref> shows the message-passing for the forward pass.

In the forward pass, a train-client will send the first layer of the to its neighbors and ask them for their initial representations, i.e., raw features (see (1) in Figure <ref>). [Sending raw features can be avoided by using an additional non-invertible weight layer on the features before aggregation.] 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.

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 <ref> 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.

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.

§.§ Problems with Distributed

Challenge 1. In each training round, requires  many rounds of communication between the clients in $\num$-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 , 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 $\numrounds$ rounds of training, the data transferred by the train-clients just for sharing the models with neighbors is $2IHd \numrounds\times 32$ bytes. [Assuming the parameters are represented using $32$-bit floating point precision.] Further, the data transferred by each neighbor of the train-clients is $2IH \numrounds\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.

Cost Illustration. Consider a $2$-layer 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\times1000\times256\times10\times32 = 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$.

§ THE GNN ARCHITECTURE

We present a novel graph learning architecture called that requires much fewer message-passing rounds for training. can be seen as a generic transformation of a traditional GNN into its counterpart. architectures retain the  $\cf{AGGR}$ and $\cf{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 training round. In a fully-distributed setup, this is expensive as it requires syncing parameter state between neighbors in a training round. Our framework 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 has $2$ layers then the 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 $\cf{AGGR}$ and $\cf{COMBINE}$ functions and use the aggregated logits as features to train the next layer. We illustrate this in Figure <ref>.

The number of message-passing rounds in a equal the number of layers ($\num$) 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 $\num$. Computing gradients while training the layers does not require any message-passing between clients. Furthermore, naturally extends to the federated setup wherein a large sub-graph is stored at every client instead of a single node. Therefore, 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 & Yu, 2022].

§.§ Architecture of

For a $\num$-layer base GNN, a counterpart is a collection of  $\num+1$ independent trainable models.

In (Figure <ref>, right side), the first model is an which is used to learn embeddings from the node features. [In fact, this model could be any classifier, such as a CNN.] There is no $\cf{AGGR}$ before the first since that requires propagating raw features. There are $\num$ more after the first one, each having the $\cf{AGGR}$ and $\cf{COMBINE}$ layers of the base GNN. 's intermediate embeddings (logits after every model) are given by:

\begin{align*}
\arr{Q}^{1}_v &= \fc{f}^{0}_\theta(Q^0_v)\\
\arr{Q}^{\hopiter}_v &= \fc{f}^{\hopiter-1}_\theta(\cf{COMBINE}(\arr{Q}^{\hopiter-1}_v, \cf{AGGR}^{m-1}_{ u\in\set{N}(v)}(\arr{Q}^{\hopiter-1}_u)))\\
\fc{f}^{0}_\theta &= \text{ \mlp}_{0} = (\arr{\theta}^{0}_{IH}, \arr{\theta}^{0}_{HO})\\
\fc{f}^{\hopiter-1}_\theta &= \text{ \mlp}_{m-1} = (\arr{\theta}^{\hopiter-1}_{OH}, \arr{\theta}^{\hopiter-1}_{HO}),~\hopiter\in\{2,\ldots, \num+1\}
\end{align*}

In $(\arr{\theta}^{\hopiter-1}_{OH}, \arr{\theta}^{\hopiter-1}_{HO})$, the $\arr{\theta}_{OH}^{\hopiter-1}$ converts the aggregated embeddings to a representation of size $H$ and the $\arr{\theta}^{\hopiter-1}_{HO}$ converts that into the output. In our running example, the $2$-layer can be represented by $\{\text{\mlp}_0:(\arr{\theta}^{0}_{IH}, \arr{\theta}^{0}_{HO}),\text{ \mlp}_1:(\arr{\theta}^{1}_{OH}, \arr{\theta}^{1}_{HO}),\text{ \mlp}_2:(\arr{\theta}^{2}_{OH}, \arr{\theta}^{2}_{HO})\}$.

Base GNN to its .

§.§ Training a

For training every we use the traditional federated learning approaches. Before training each , 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 <ref>) and provide full details, for the federated learning and message passing protocols, in the Appendix <ref>.

Federated Learning.
The server and the clients together train $\num+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 $\cf{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].

Before training the $\hopiter^{th}$ , the server initializes a message-passing round by sending all the clients the $(\hopiter -1)$ trained 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 with three and say the server is training its third . At this point, the server sends the second model to all clients. So, now all clients will have the first ($\text{\mlp}_0$), their own first embeddings output by their first ($\arr{Q}_v^1$), the first embeddings obtained from their neighbors ($\arr{Q}_u^1$, $u\in\set{N}(v)$) from the previous message passing round, and the second ($\text{\mlp}_1$). The clients locally compute $\arr{Q}_v^2$ using this information. The clients then share $\arr{Q}_v^2$ with their neighbors to complete the current message-passing round.

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 [10, 2]. In distributed social networks, the clients do not need to be in proximity or have public IP addresses. Instead, WebRTC can be used [35].

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 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 $\num$ 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. is robust to such unavailability. More experiments reported in Appendix <ref> elaborate on this feature of .

§ EVALUATION

We evaluate on $2$ aspects:

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

Communication Efficiency. How do 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:  [Kipf & Welling, 2016],  [Hamilton et al., 2017], and  [Veličković et al., 2017]. [We use simple mean aggregation instead of localized spectral convolution for GCN as described here [Hamilton et al., 2017].] For , we use the max-pooling layer for aggregation.

For the transductive setting, we evaluate on $7$ datasets—, , , , , , and . 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 that correspond to these GNNs.  We provide full details on the datasets, splits, and architectures in Appendix <ref>.

Implementation & Training.
We first implemented the baseline GNNs and their respective on the centralized server. We further implemented 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 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 <ref>). We also separately report validation accuracies with early-stopping to show how it can further reduce communication costs for a small drop in accuracy.

Micro-F1 scores for node classification in the transductive setting.

$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$

$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$

$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$

$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$

$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$

$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$

$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$

Micro-F1 scores for node classification in the inductive setting.

$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$

$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$

$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$

$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$

$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$

$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$

$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$

§.§ Results

Q1: Node-classification performance. We present the micro-F1 scores in Tables <ref> and <ref> for the transductive and inductive settings. Across all evaluated configurations, the performance of is within $1.20\%$ of their respective GNNs on average. performs the best among the models across all but one evaluated configurations. It sometimes outperforms in the inductive setting (up to $3.3\%$). In the heterophilous setting, perform better than their respective GNNs by up to $5\%$. is the weakest performing model with $5\%$ less accuracy than the in $3$ homophilous-transductive datasets. Overall, it is reasonable to expect that will sometimes have worse performance than the GNNs since the aggregation is done over the embeddings of the first in , unlike in GNNs which aggregate over the raw features directly.

Q2: Communication-efficiency.  We perform our experiments on homophilous-transductive datasets and measure the data  transferred across the client-to-client and the client-to-server communication channels in megabytes (MB). In our first experiment, we use the same evaluated configurations on which we have reported the accuracy.

We find that the total data transferred on client-to-client communication channels in is up to $4$ to $7$ orders of magnitude less compared to vanilla GNNs across all evaluated configurations. We take the example of the dataset to illustrate our results.

Consider and which performs $2\%$ worse than , then across all nodes, the total data transferred on the client-to-client channels to train a is about $7.7\times10^6$ MB and is $1.13$ MB which is $10^6\times$ lower. Moreover, training requires transferring only $0.018$ MB per client across $2$ message-passing rounds. In contrast, for instance, requires a client to transfer $43,763$ MB in the worst case, across $400$ rounds—a saving of several orders ($>10^6\times$) of magnitude.  We observe similar reductions for all other evaluated configurations (see Appendix <ref>).

The majority of the data transfer costs for is on the client-to-server channels.  These costs are unavoidable in the federated learning setup. They are common to baseline GNNs too and are similar for both GNNs and . In Figure <ref> (left side), we present the total data transferred per client on both channels. If we consider vs , the total data transferred by all clients on both channels is about $10^7$ MB for and about $1.1\times10^6$ for which is about $10\times$ lower. Further, in , the data transferred is almost the same for all train clients, about $2,000$ MB, and close to $2$ MB for the remaining clients. In , the distribution of data transferred across clients is skewed with the most affected ones transferring up to $80,000$ MB.  We see similar results for remaining datasets (see Appendix <ref>).

To evaluate if the communication-efficiency for GNNs can be further reduced, we implement early-stopping in the transductive setting while keeping the remaining hyperparameters unchanged. It is difficult to identify a common 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 <ref> (right side) we report the results for these experiments. Consider the example of vs . On client-to-client channels, the total data transferred for is about $3.3\times10^6$ MB and is $1.13$ MB which is $10^6\times$ lower. On both channels together, the total data transferred for and is about $4.3\times10^6$ MB and about $2.4\times10^5$ MB respectively, which is $20\times$ lower. We report the remaining evaluated configurations in Appendix <ref>.

To summarize, 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 $\num$ for instance in the heterophilous setting, the difference in communication costs between GNNs and will only increase.

§ 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 & 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 & 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 to the federated setup considered by these protocols since, outside of message-passing, mimics the typical federated learning setup irrespective of the number of nodes per client. 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 to these setups is an interesting future work.

§ CONCLUSION

We have presented new neural network architectures, , 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. [https://github.com/aashishkolluri/retexognn-prototype]

[Anonymous, 2023]
A critical look at evaluation of GNNs under heterophily: Are we
really making progress?
In Submitted to The Eleventh International Conference on
Learning Representations, 2023.
URL <https://openreview.net/forum?id=tJbbQfw-5wv>.
under review.

[2]
Airdrop, apple.

[Bonawitz et al., 2019]
Bonawitz, K., Eichner, H., Grieskamp, W., Huba, D., Ingerman, A., Ivanov, V.,
Kiddon, C., Konečnỳ, J., Mazzocchi, S., McMahan, B., et al.
Towards federated learning at scale: System design.
Proceedings of Machine Learning and Systems, 2019.

[Cadwalladr & Graham-Harrison, 2018]
Cadwalladr, C. and Graham-Harrison, E.
Revealed: 50 million facebook profiles harvested for cambridge
analytica in major data breach.
The Guardian, 2018.

[Chen et al., 2020]
Chen, C., Zhou, J., Zheng, L., Wu, H., Lyu, L., Wu, J., Wu, B., Liu, Z., Wang,
L., and Zheng, X.
Vertically federated graph neural network for privacy-preserving node
arXiv preprint arXiv:2005.11903, 2020.

[Chen et al., 2021]
Chen, C., Hu, W., Xu, Z., and Zheng, Z.
Fedgl: federated graph learning framework with global
arXiv preprint arXiv:2105.03170, 2021a.

[Chen et al., 2021]
Chen, F., Li, P., Miyazaki, T., and Wu, C.
Fedgraph: Federated graph learning with intelligent sampling.
IEEE Transactions on Parallel and Distributed Systems,

[Dong et al., 2021]
Dong, G., Cai, L., Datta, D., Kumar, S., Barnes, L. E., and Boukhechba, M.
Influenza-like symptom recognition using mobile sensing and graph
neural networks.
In Proceedings of the Conference on Health, Inference, and
Learning, 2021.

[Gandhi & Iyer, 2021]
Gandhi, S. and Iyer, A. P.
P3: Distributed deep graph learning at scale.
In 15th $\{$USENIX$\}$ Symposium on Operating Systems Design
and Implementation ($\{$OSDI$\}$ 21), pp.  551–568, 2021.

[10]
Nearby share, android.

[Gui et al., 2017]
Gui, X., Chen, Y., Caldeira, C., Xiao, D., and Chen, Y.
When fitness meets social networks: Investigating fitness tracking
and social practices on werun.
In Proceedings of the 2017 CHI conference on human factors in
computing systems, 2017.

[Hamilton et al., 2017]
Hamilton, W., Ying, Z., and Leskovec, J.
Inductive representation learning on large graphs.
Advances in neural information processing systems, 30, 2017.

[He et al., 2021]
He, C., Balasubramanian, K., Ceyani, E., Rong, Y., Zhao, P., Huang, J.,
Annavaram, M., and Avestimehr, S.
Fedgraphnn: A federated learning system and benchmark for graph
neural networks.
arXiv preprint arXiv:2104.07145, 2021a.

[He et al., 2021]
He, C., Ceyani, E., Balasubramanian, K., Annavaram, M., and Avestimehr, S.
Spreadgnn: Serverless multi-task federated learning for graph neural
arXiv preprint arXiv:2106.02743, 2021b.

[Hernández-Orallo et al., 2020]
Hernández-Orallo, E., Manzoni, P., Calafate, C. T., and Cano, J.-C.
Evaluating how smartphone contact tracing technology can reduce the
spread of infectious diseases: The case of covid-19.
IEEE Access, 2020.

[Hulsen, 2020]
Hulsen, T.
Sharing is caring—data sharing initiatives in healthcare.
International journal of environmental research and public
health, 2020.

[Illmer, 2021]
Illmer, A.
Singapore reveals covid privacy data available to police.
BBC News, 2021.

[Jiang et al., 2020]
Jiang, M., Jung, T., Karl, R., and Zhao, T.
Federated dynamic gnn with secure aggregation.
arXiv preprint arXiv:2009.07351, 2020.

[Kipf & Welling, 2016]
Kipf, T. N. and Welling, M.
Semi-supervised classification with graph convolutional networks.
arXiv preprint arXiv:1609.02907, 2016.

[Liu & Yu, 2022]
Liu, R. and Yu, H.
Federated graph neural networks: Overview, techniques and challenges.
arXiv preprint arXiv:2202.07256, 2022.

[Madan et al., 2010]
Madan, A., Moturu, S. T., Lazer, D., and Pentland, A.
Social sensing: obesity, unhealthy eating and exercise in
face-to-face networks.
In Wireless Health 2010, pp.  104–110. 2010.

[Marlinspike, 2017]
Marlinspike, M.
Technology preview: Private contact discovery for signal.
Signal blog, 2017.

[Mastodon, 2022]
Running your own server on mastodon.
Mastodon Docs, 2022.

[McMahan et al., 2017]
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A.
Communication-efficient learning of deep networks from decentralized
In Artificial intelligence and statistics, 2017.

[Md et al., 2021]
Md, V., Misra, S., Ma, G., Mohanty, R., Georganas, E., Heinecke, A., Kalamkar,
D., Ahmed, N. K., and Avancha, S.
Distgnn: Scalable distributed training for large-scale graph neural
In Proceedings of the International Conference for High
Performance Computing, Networking, Storage and Analysis, 2021.

[Nguyen et al., 2022]
Nguyen, J., Malik, K., Zhan, H., Yousefpour, A., Rabbat, M., Malek, M., and
Huba, D.
Federated learning with buffered asynchronous aggregation.
In International Conference on Artificial Intelligence and
Statistics, 2022.

[Pan et al., 2011]
Pan, W., Aharony, N., and Pentland, A.
Composite social network for predicting mobile apps installation.
In Proceedings of the AAAI Conference on Artificial
Intelligence, 2011.

[Reddi et al., 2020]
Reddi, S., Charles, Z., Zaheer, M., Garrett, Z., Rush, K., Konečnỳ,
J., Kumar, S., and McMahan, H. B.
Adaptive federated optimization.
arXiv preprint arXiv:2003.00295, 2020.

[Scardapane et al., 2020]
Scardapane, S., Spinelli, I., and Di Lorenzo, P.
Distributed training of graph convolutional networks.
IEEE Transactions on Signal and Information Processing over
Networks, 2020.

[Suzumura et al., 2019]
Suzumura, T., Zhou, Y., Baracaldo, N., Ye, G., Houck, K., Kawahara, R., Anwar,
A., Stavarache, L. L., Watanabe, Y., Loyola, P., et al.
Towards federated graph learning for collaborative financial crimes
arXiv preprint arXiv:1909.12946, 2019.

[Veličković et al., 2017]
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., and
Bengio, Y.
Graph attention networks.
arXiv preprint arXiv:1710.10903, 2017.

[Wan et al., 2022]
Wan, C., Li, Y., Li, A., Kim, N. S., and Lin, Y.
Bns-gcn: Efficient full-graph training of graph convolutional
networks with partition-parallelism and random boundary node sampling.
Proceedings of Machine Learning and Systems, 2022.

[Wang et al., 2020]
Wang, B., Li, A., Li, H., and Chen, Y.
Graphfl: A federated learning framework for semi-supervised node
classification on graphs.
arXiv preprint arXiv:2012.04187, 2020.

[Wang et al., 2022]
Wang, Z., Kuang, W., Xie, Y., Yao, L., Li, Y., Ding, B., and Zhou, J.
Federatedscope-gnn: Towards a unified, comprehensive and efficient
package for federated graph learning.
KDD, 2022.

[35]
Webrtc: Real-time communication for the web.

[Wu et al., 2021]
Wu, C., Wu, F., Cao, Y., Huang, Y., and Xie, X.
Fedgnn: Federated graph neural network for privacy-preserving
arXiv preprint arXiv:2102.04925, 2021.

[Wu et al., 2020]
Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., and Philip, S. Y.
A comprehensive survey on graph neural networks.
IEEE transactions on neural networks and learning systems,

[Xie et al., 2021]
Xie, H., Ma, J., Xiong, L., and Yang, C.
Federated graph classification over non-iid graphs.
Advances in Neural Information Processing Systems,
34:0 18839–18852, 2021.

[Yao & Joe-Wong, 2022]
Yao, Y. and Joe-Wong, C.
Fedgcn: Convergence and communication tradeoffs in federated training
of graph convolutional networks.
arXiv preprint arXiv:2201.12433, 2022.

[Zeng et al., 2019]
Zeng, H., Zhou, H., Srivastava, A., Kannan, R., and Prasanna, V.
Graphsaint: Graph sampling based inductive learning method.
arXiv preprint arXiv:1907.04931, 2019.

[Zhang et al., 2021]
Zhang, K., Yang, C., Li, X., Sun, L., and Yiu, S. M.
Subgraph federated learning with missing neighbor generation.
Advances in Neural Information Processing Systems, 2021.

[Zheng et al., 2021]
Zheng, L., Zhou, J., Chen, C., Wu, B., Wang, L., and Zhang, B.
Asfgnn: Automated separated-federated graph neural network.
Peer-to-Peer Networking and Applications, 2021.

[Zheng et al., 2022]
Zheng, X., Liu, Y., Pan, S., Zhang, M., Jin, D., and Yu, P. S.
Graph neural networks for graphs with heterophily: A survey.
arXiv preprint arXiv:2202.07082, 2022.

[Zhou et al., 2020]
Zhou, J., Cui, G., Hu, S., Zhang, Z., Yang, C., Liu, Z., Wang, L., Li, C., and
Sun, M.
Graph neural networks: A review of methods and applications.
AI Open, 2020.