Federated Learning with Graph Data

In Federated Learning with Graph Data, clients hold subgraphs that differ not just in node features and labels, but in their fundamental topology—the number of nodes, edge density, and community structure. This structural Non-IID violates the assumption that all local models learn from similarly structured relational data. Aggregating models trained on a dense social subgraph with those from a sparse transaction subgraph can lead to severe model bias and poor generalization, as the learned representations are optimized for incompatible graph geometries.

A defining challenge is the presence of inter-client edges—relationships that connect nodes residing on different clients' subgraphs. In a federated healthcare graph, a patient (node on Hospital A's subgraph) might be treated by a doctor (node on Clinic B's subgraph). These edges are critical for tasks like link prediction or community detection but cannot be directly observed by any single client. Federated algorithms must infer or collaboratively learn these missing connections without exchanging raw node data, a problem known as link-level Non-IID. Failure to account for this leads to models with a fragmented and incomplete understanding of the global graph.

The graph structure provides a powerful attack vector for adversarial clients. A malicious participant can poison the graph structure by adding or removing edges within their local subgraph to create misleading relational patterns. For example, in a federated financial graph for fraud detection, an attacker could create spurious transaction edges between legitimate accounts to disguise money laundering patterns. Because graph neural networks (GNNs) propagate information along edges, such structural poisoning can disproportionately influence the global model's understanding of relationships, making detection more difficult than feature-only poisoning in traditional FL.

The graph topology itself is highly sensitive. In a federated social network, even sharing aggregated model updates (e.g., GNN gradients) can leak information about a client's local community structure or the degree distribution of nodes. Adversaries can perform model inversion or membership inference attacks by analyzing these updates to infer whether specific relationships exist. Standard privacy techniques like Differential Privacy (DP) must be carefully adapted, as adding noise to graph-structured gradients can severely degrade model utility due to the complex, non-Euclidean nature of the data.

Standard federated averaging (FedAvg) aggregates neural network weights, assuming a consistent, aligned model architecture. Graph Neural Networks (GNNs) have components with specific geometric meanings:

• Graph Convolutional Layers: Weights are tied to node feature transformations.
• Attention Mechanisms: Parameters define how nodes attend to neighbors. Aggregating these layers from clients with wildly different subgraph sizes and degrees requires sophisticated methods. Naive averaging can produce a GNN whose message-passing behavior is not calibrated for any realistic graph, leading to unstable training and convergence failure.

Federated learning must handle partial client participation each round. In graph FL, this means the global model only ever trains on a random, disconnected set of subgraphs. This subgraph-level client dropout creates a volatile and incomplete view of the global graph topology for training. Algorithms must be robust to this structural missingness. Furthermore, performing efficient mini-batch sampling for GNNs locally is challenging, as sampling a batch of nodes requires also sampling their multi-hop neighbors, which can lead to explosive computational graphs and inconsistent local training costs across heterogeneous clients.

Graph Neural Networks are a class of deep learning models designed to operate directly on graph-structured data. They learn node, edge, and graph-level representations by iteratively aggregating information from a node's local neighborhood.

• Core Mechanism: Uses message-passing where nodes exchange feature vectors with their neighbors.
• Key Architectures: Includes Graph Convolutional Networks (GCNs), Graph Attention Networks (GATs), and GraphSAGE.
• Federated Relevance: In a federated setting, each client typically holds a local subgraph. Training a GNN across clients requires aggregating model updates while respecting the relational structure and privacy of each client's subgraph topology.

Subgraph Heterogeneity refers to the statistical and structural differences between the local graph data held by different clients in a federated system. This is a primary source of Non-IID data in graph FL.

• Manifestations: Includes variations in node degree distributions, community structures, node/edge feature distributions, and label distributions.
• Impact: Causes client drift in GNN training, where local models overfit to their unique subgraph structure, degrading the performance of the aggregated global model on the overall graph.
• Example: In a federated social network analysis, one client's subgraph may represent a dense professional network, while another's represents a sparse acquaintance network.

Cross-Node Federated Learning is the standard formulation for FL with graph data, where each client owns a disjoint set of nodes (and their associated edges) from a larger global graph. The learning objective is to train a single GNN model for the entire graph.

• Data Partitioning: The global graph is partitioned horizontally by nodes. Clients do not share raw node/edge data.
• Privacy Challenge: Even sharing GNN gradients or embeddings can leak information about a node's neighbors and features due to the message-passing mechanism.
• Solution Direction: Often requires secure aggregation and differential privacy techniques specifically adapted for graph data to prevent inference of sensitive relationships.

Cross-Graph Federated Learning is a formulation where each client possesses a separate, self-contained graph (or set of graphs). The goal is to learn a GNN model that generalizes across these different graph instances.

• Data Partitioning: Each client's data is a separate graph dataset (e.g., different molecular graphs, different traffic networks).
• Learning Objective: Aims to capture shared underlying patterns across diverse graph structures, such as common functional groups in molecules or traffic flow dynamics.
• Applications: Common in drug discovery (multiple research institutes hold proprietary molecular graphs) and smart city networks (each city manages its own sensor network graph).

Federated Graph Partitioning refers to the initial (often offline) process of dividing a large global graph into subgraphs distributed across clients, with the aim of preserving learning efficiency and privacy.

• Objectives: Minimize cross-client edges (cuts) to reduce communication and privacy leakage, while maintaining representative local data distributions.
• Methods: Can use metis-style partitioning for balance, community detection to keep densely connected nodes together, or learning-based partitioning.
• Trade-off: Excessively isolated subgraphs increase subgraph heterogeneity, while partitions with many cross-client edges complicate secure training.

Graph Topology Inference Attacks are privacy attacks unique to federated GNNs, where an adversary (e.g., a curious server or client) attempts to reconstruct the connective structure of a client's local subgraph.

• Attack Vectors: Can exploit shared model gradients, intermediate embeddings, or aggregated neighbor information from the GNN's message-passing layers.
• Risk: Revealing if two nodes (e.g., users in a social network) are connected can be a severe privacy breach, even if their features are protected.
• Defenses: Employ differential privacy on gradients, secure multi-party computation (MPC) for aggregation, or topology masking techniques.