FedWalk: Communication Efficient Federated Unsupervised Node Embedding with Differential Privacy
Node embedding aims to map nodes in the complex graph into low-dimensional representations. The real-world large-scale graphs and difficulties of labeling motivate wide studies of unsupervised node embedding problems. Nevertheless, previous effort mostly operates in a centralized setting where a complete graph is given. With the growing awareness of data privacy, data holders who are only aware of one vertex and its neighbours demand greater privacy protection. In this paper, we introduce FedWalk, a random-walk-based unsupervised node embedding algorithm that operates in such a node-level visibility graph with raw graph information remaining locally. FedWalk is designed to offer centralized competitive graph representation capability with data privacy protection and great communication efficiency. FedWalk instantiates the prevalent federated paradigm and contains three modules. We first design a hierarchical clustering tree (HCT) constructor to extract the structural feature of each node. A dynamic time warping algorithm seamlessly handles the structural heterogeneity across different nodes. Based on the constructed HCT, we then design a random walk generator, wherein a sequence encoder is designed to preserve privacy and a two-hop neighbor predictor is designed to save communication cost. The generated random walks are then used to update node embedding based on a SkipGram model. Extensive experiments on two large graphs demonstrate that Fed-Walk achieves competitive representativeness as a centralized node embedding algorithm does with only up to 1.8% Micro-F1 score and 4.4% Marco-F1 score loss while reducing about 6.7 times of inter-device communication per walk.
Code (0)
등록된 구현이 없습니다.
Tasks
Dynamic Time WarpingMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Federated Graph Learning with Adaptive Importance-based Sampling
For privacy-preserving graph learning tasks involving distributed graph datasets, federated learning (FL)-based GCN (FedGCN) training is required. A key challenge for FedGCN is scaling to large-scale graphs, which typica…
Federated LearningGraph LearningGraph SamplingPrivacy PreservingFedC4: Graph Condensation Meets Client-Client Collaboration for Efficient and Private Federated Graph Learning
Federated Graph Learning (FGL) is an emerging distributed learning paradigm that enables collaborative model training over decentralized graph-structured data while preserving local privacy. Existing FGL methods can be c…
Graph LearningProvably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networks
Graph neural networks (GNNs) achieve strong performance on relational data, but real-world graphs are often distributed across organizations that cannot share raw data due to privacy and policy constraints. Existing fede…
Data Poisoning Attacks on Federated Machine Learning
Federated machine learning which enables resource constrained node devices (e.g., mobile phones and IoT devices) to learn a shared model while keeping the training data local, can provide privacy, security and economic b…
BIG-bench Machine LearningData PoisoningFederated LearningMulti-Task LearningGraphScale: A Framework to Enable Machine Learning over Billion-node Graphs
Graph Neural Networks (GNNs) have emerged as powerful tools for supervised machine learning over graph-structured data, while sampling-based node representation learning is widely utilized in unsupervised learning. Howev…
Representation Learning