Federated Cross-Client Subgraph Pattern Detection
For practitioners needing to detect subgraph patterns across distributed graph data without centralizing raw data, this work provides a method to bridge the performance gap between federated and centralized GNNs.
The paper addresses the representation-equivalence gap in federated subgraph pattern detection caused by partition boundaries. It proposes a per-step, layer-wise embedding exchange framework that, under an extended-subgraph assumption, recovers the same node representations as a centralized GNN, with experiments showing that combining embedding exchange and federated parameter aggregation recovers most of the representation gap.
Subgraph pattern detection aims to uncover complex interaction structures in graphs. However, state-of-the-art graph neural network (GNN)-based solutions assume centralized access to the entire graph. When graphs are instead distributed across multiple parties, client-local GNN computations diverge from those of a centralized model, resulting in a representation-equivalence gap. We formalize this as a structural observability problem, where subgraph patterns crossing partition boundaries become locally unidentifiable. To bridge this gap, we propose a per-step, layer-wise embedding exchange framework in which clients synchronize intermediate node representations at each layer of the forward pass, without exposing raw features or labels. Under an extended-subgraph assumption and shared model parameters across clients, this framework recovers the same node representations as a centralized GNN over the full graph. Experiments on synthetic directed multigraphs with cycles, bicliques, and scatter-gather patterns show that embedding exchange and federated parameter aggregation are complementary rather than interchangeable: their combination recovers most of the representation gap, provided exchanged embeddings are fresh per-step rather than stale per-epoch.