Edge-Centric Federated Subgraph Isomorphism Counting via Residual Graph Neural Networks

Subgraph isomorphism counting is a fundamental yet computationally challenging task in graph analysis, with broad applications in bioinformatics and social network mining. With the tightening of data privacy regulations and the emergence of data silos, traditional centralized Graph Neural Network (GNN) approaches face significant deployment hurdles. Existing federated subgraph counting methods are primarily designed for database federation scenarios, focusing on exact queries and the privacy and security concerns of databases. However, this rigid focus on exactness and heavy cryptographic security severely limits their scalability and generalizability to complex, arbitrary query patterns. To bridge this gap, we propose a general Federated Edge-Centric Framework for Subgraph Isomorphism Counting (FedCount), shifting the paradigm from exact querying on federated databases to neural approximate counting under federated architectures. Rather than relying on heavy cryptographic techniques, we exclusively leverage the inherent structural isolation of federated learning as a lightweight empirical privacy measure. While this framework does not theoretically defend against advanced gradient-based inference attacks, it successfully prevents the direct leakage of raw graph topology and node features, achieving high-precision approximate counting without the prohibitive cryptographic overheads. Specifically, we introduce two key technical innovations to enhance local counting capability: (1) we integrate a provable edge encoding scheme into the interaction-based GNN architecture, explicitly modeling edge-to-edge interactions to break the expressiveness bottleneck of standard message passing; (2) we design a Residual Edge-Centric Readout mechanism that mitigates the gradient vanishing problem, enabling the effective training of deeper networks to capture high-order topological dependencies. Extensive experiments on multiple benchmark datasets demonstrate that our framework significantly outperforms existing distributed enumeration baselines in terms of generalization and efficiency, approaching the performance of centralized state-of-the-art models.