Graph neural networks (GNNs) play a key role in learning representations from graph-structured data and are demonstrated to be useful in many applications. However, the GNN training pipeline has been shown to be vulnerable to node feature leakage and edge extraction attacks. This paper investigates a scenario where an attacker aims to recover private edge information from a trained GNN model. Previous studies have employed differential privacy (DP) to add noise directly to the adjacency matrix or a compact graph representation. The added perturbations cause the graph structure to be substantially morphed, reducing the model utility. We propose a new privacy-preserving GNN training algorithm, Eclipse, that maintains good model utility while providing strong privacy protection on edges. Eclipse is based on two key observations. First, adjacency matrices in graph structures exhibit low-rank behavior. Thus, Eclipse trains GNNs with a low-rank format of the graph via singular values decomposition (SVD), rather than the original graph. Using the low-rank format, Eclipse preserves the primary graph topology and removes the remaining residual edges. Eclipse adds noise to the low-rank singular values instead of the entire graph, thereby preserving the graph privacy while still maintaining enough of the graph structure to maintain model utility. We theoretically show Eclipse provide formal DP guarantee on edges. Experiments on benchmark graph datasets show that Eclipse achieves significantly better privacy-utility tradeoff compared to existing privacy-preserving GNN training methods. In particular, under strong privacy constraints (𝜖 < 4), Eclipse shows significant gains in the model utility by up to 46%. We further demonstrate that Eclipse also has better resilience against common edge attacks (e.g., LPA), lowering the attack AUC by up to 5% compared to other state-of-the-art baselines.

Stragglers, Byzantine workers, and data privacy are the main bottlenecks in distributed cloud computing. Some prior works proposed coded computing strategies to jointly address all three challenges. They require either a large number of workers, a significant communication cost or a significant computational complexity to tolerate Byzantine workers. Much of the overhead in prior schemes comes from the fact that they tightly couple coding for all three problems into a single framework. In this paper, we propose Adaptive Verifiable Coded Computing (AVCC) framework that decouples the Byzantine node detection challenge from the straggler tolerance. AVCC leverages coded computing just for handling stragglers and privacy, and then uses an orthogonal approach that leverages verifiable computing to mitigate Byzantine workers. Furthermore, AVCC dynamically adapts its coding scheme to trade-off straggler tolerance with Byzantine protection. We evaluate AVCC on a compute-intensive distributed logistic regression application. Our experiments show that AVCC achieves up to 4.2× speedup and up to 5.1% accuracy improvement over the state-of-the-art Lagrange coded computing approach (LCC). AVCC also speeds up the conventional uncoded implementation of distributed logistic regression by up to 7.6×, and improves the test accuracy by up to 12.1%.

By using the viewpoint of modern computational algebraic geometry, we explore properties of the optimization landscapes of deep linear neural network models. After providing clarification on the various definitions of “flat” minima, we show that the geometrically flat minima, which are merely artifacts of residual continuous symmetries of the deep linear networks, can be straightforwardly removed by a generalized$L_2$-regularization. Then, we establish upper bounds on the number of isolated stationary points of these networks with the help of algebraic geometry. Combining these upper bounds with a method in numerical algebraic geometry, we findallstationary points for modest depth and matrix size. We demonstrate that, in the presence of the non-zero regularization, deep linear networks can indeed possess local minima which are not global minima. Finally, we show that even though the number of stationary points increases as the number of neurons (regularization parameters) increases (decreases), higher index saddles are surprisingly rare.

Recent advances in localization techniques have fundamentally enhanced social networking services, allowing users to share their locations and location-related contents. This has further increased the popularity of location-based social networks (LBSNs) and produces a huge amount of trajectories composed of continuous and complex spatio-temporal points from people’s daily lives. How to accurately aggregate large-scale trajectories is an important and challenging task. Conventional clustering algorithms (e.g., k -means or k -mediods) cannot be directly employed to process trajectory data due to their serialization, triviality and redundancy. Aiming to overcome the drawbacks of traditional k -means algorithm and k -mediods, including their sensitivity to the selection of the initial k value, the cluster centers and easy convergence to a locally optimal solution, we first propose an optimized k -means algorithm (namely OKM ) to obtain k optimal initial clustering centers based on the density of trajectory points. Second, because k -means is sensitive to noisy points, we propose an improved k -mediods algorithm called IKMD based on an acceptable radius r by considering users’ geographic location in LBSNs. The value of k can be calculated based on r , and the optimal k points are selected as the initial clustering centers with high densities to reduce the cost of distance calculation. Thirdly, we thoroughly analyze the advantages of IKMD by comparing it with the commonly used clustering approaches through illustrative examples. Last, we conduct extensive experiments to evaluate the performance of IKMD against seven clustering approaches including the proposed optimized k -means algorithm, k -mediods algorithm, traditional density-based k -mediods algorithm and the state-of-the-arts trajectory clustering methods. The results demonstrate that IKMD significantly outperforms existing algorithms in the cost of distance calculation and the convergence speed. The methods proposed is proved to contribute to a larger effort targeted at advancing the study of intelligent trajectory data analytics.