Graph embeddings have become a key paradigm to learn node representations and facilitate downstream graph analysis tasks. Many real-world scenarios such as online social networks and communication networks involve streaming graphs, where edges connecting nodes are continuously received in a streaming manner, making the underlying graph structures evolve over time. Such a streaming graph raises great challenges for graph embedding techniques not only in capturing the structural dynamics of the graph, but also in efficiently accommodating high-speed edge streams. Against this background, we propose SGSketch, a highly-efficient streaming graph embedding technique via incremental neighborhood sketching. SGSketch cannot only generate high-quality node embeddings from a streaming graph by gradually forgetting outdated streaming edges, but also efficiently update the generated node embeddings via an incremental embedding updating mechanism. Our extensive evaluation compares SGSketch against a sizable collection of state-of-the-art techniques using both synthetic and real-world streaming graphs. The results show that SGSketch achieves superior performance on different graph analysis tasks, showing 31.9% and 21.9% improvement on average over the best-performing static and dynamic graph embedding baselines, respectively. Moreover, SGSketch is significantly more efficient in both embedding learning and incremental embedding updating processes, showing 54x-1813x and 118x-1955x speedup over the baseline techniques, respectively.@en

With the massive amount of data generated from mobile devices and the increase of computing power of edge devices, the paradigm of Federated Learning has attracted great momentum. In federated learning, distributed and heterogeneous nodes collaborate to learn model parameters. However, while providing benefits such as privacy by design and reduced latency, the heterogeneous network present challenges to the synchronisation methods, or barrier control methods, used in training, regarding system progress and model convergence etc. The design of these barrier mechanisms is critical for the performance and scalability of federated learning systems. We propose a new barrier control technique called Probabilistic Synchronous Parallel (PSP). In contrast to existing mechanisms, it introduces a sampling primitive that composes with existing barrier control mechanisms to produce a family of mechanisms with improved convergence speed and scalability. Our proposal is supported with a convergence analysis of PSP-based SGD algorithm. In practice, we also propose heuristic techniques that further improve the efficiency of PSP. We evaluate the performance of proposed methods using the federated learning specific FEMNSIT dataset. The evaluation results show that PSP can effectively achieve good balance between system efficiency and model accuracy, mitigating the challenge of heterogeneity in federated learning.@en