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.