Search

Federated learning (FL) has emerged as a promising privacy-preserving machine learning paradigm, enabling data owners to collaboratively train a joint model by sharing model parameters instead of private training data. However, recent studies reveal the privacy risks in FL by inferring private training data from model parameters. Therefore, differential privacy (DP) is incorporated into FL to safeguard training data. Nevertheless, DP does not provide a strong theoretical guarantee for protecting data distribution, which is also highly sensitive in the cross-silo FL scenarios as it may reflect the business secrets of data owners. In this article, we develop two attack methods to investigate the potential risks of data distribution leakage in differentially private cross-silo FL. We highlight that an honest-but-curious server can successfully infer both the feature and label distributions of each party’s training data without any background knowledge. Specifically, the first attack applies when models are differentiable, while the second attack caters to non-differentiable classification models. Extensive experiments on six benchmark datasets validate the effectiveness of the proposed attacks. The results demonstrate that the state-of-the-art DP-SGD algorithm is still vulnerable to the inference attack on data distribution, emphasizing the necessity of designing more advanced privacy-preserving FL frameworks.

Random perturbation is a popular method of computing anonymized data for privacy preserving data mining. It is simple to apply, ensures strong privacy protection, and permits effective mining of a large variety of data patterns. However, all the existing studies with good privacy guarantees focus on perturbation at a single privacy level. Namely, a fixeddegree of privacy protection is imposed on allanonymized data released by the data holder. This drawback seriously limits the applicability of random perturbation in scenarios where the holder has numerous recipients to which different privacy levels apply.Motivated by this, we study the problem of multi-level perturbation, whose objective is to release multiple versions of a dataset anonymized at different privacy levels. The challenge is that various recipients may collude by sharing their data to infer privacy beyond their permitted levels. Our solution overcomes this obstacle, and achieves two crucial properties. First, collusion is useless, meaning that the colluding recipients cannot learn anything more than what the most trustable recipient (among the colluding recipients) already knows alone. Second, the data each recipient receives can be regarded (and hence, analyzed in the same way) as the output of conventional uniform perturbation. Besides its solid theoretical foundation, the proposed technique is both space economical and computationally efficient. It requires O (n+m)expected space, and produces a new anonymized version in O(n+ log m) expected time, where nis the cardinality of the original dataset, and mthe number of versions released previously. Both bounds are optimal under the realistic assumption that n» m.

Given a dataset containing sensitive personal information, a statistical database answers aggregate queries in a manner that preserves individual privacy. We consider the problem of constructing a statistical database using output perturbation, which protects privacy by injecting a small noise into each query result. We show that the state-of-the-art approach, e-differential privacy, suffers from two severe deficiencies: it (i) incurs prohibitive computation overhead, and (ii) can answer only a limited number of queries, after which the statistical database has to be shut down. To remedy the problem, we develop a new technique that enforces e-different privacy with economical cost. Our technique also incorporates a query relaxationmechanism, which removes the restriction on the number of permissible queries. The effectiveness and efficiency of our solution are verified through experiments with real data.

Given a graph G, a source node s∈ Gand a positive integer k, a top-k Personalized PageRank (PPR)query returns the knodes with the highest PPR values with respect to s, where the PPR of a node vmeasures its relevance from the perspective of source s.Top-kPPR processing is a fundamental task in many important applications such as web search, social networks, and graph analytics. This paper aims to answer such a query in realtime, i.e., within less than 100ms, on an Internet-scale graph with billions of edges. This is far beyond the current state of the art, due to the immense computational cost of processing a PPR query. We achieve this goal with a novel algorithm kPAR, which utilizes the massive parallel processing power of GPUs.The main challenge in designing a GPU-based PPR algorithm lies in that a GPU is mainly a parallel computationdevice, whereas PPR processing involves graph traversals and value propagation operations, which are inherently sequentialand memory-bound.Existing scalable PPR algorithms are mostly described as single-thread CPU solutions that are resistant to parallelization. Further, they usually involve complex data structures which do not have efficient adaptations on GPUs. kPAR overcomes these problems via both novel algorithmic designs (namely, adaptive forward pushand inverted random walks) and system engineering (e.g., load balancing) to realize the potential of GPUs. Meanwhile, kPAR provides rigorous guarantees on both result quality and worst-case efficiency. Extensive experiments show that kPAR is usually 10x faster than parallel adaptations of existing methods. Notably, on a billion-edge Twitter graph, kPAR answers a top-1000 PPR query in 42.4 milliseconds.

We consider the edge uncertainty in an undirected graph and study the k-median (resp. k-center) problems, where the goal is to partition the graph nodes into kclusters such that the average (resp. minimum) connection probability between each node and its cluster's center is maximized. We analyze the hardness of these problems, and propose algorithms that provide considerably improved approximation guarantees than the existing studies do. Specifically, our algorithms offer (1 -- 1/e)-approximations for the k-median problem and (OPTck)-approximations for the k-center problem, where OPTck is the optimal objective function value for k-center. In addition, our algorithms incorporate several non-trivial optimizations that significantly enhance their practical efficiency. Extensive experimental results demonstrate that our algorithms considerably outperform the existing methods on both computation efficiency and the quality of clustering results.

The data management group at the Nanyang Technological University (dante) was founded in 2009 by the first author when the School of Computer Science and Engineering hired two young faculty members in this area. The group currently consists of three faculty members and more than twenty graduate students, research assistants, and postdocs. Our alumni include faculty members at the Chinese University of Hong Kong, National University of Singapore, University of New South Wales, and several researchers and engineers at Facebook, Google, eBay, Huawei, and other technology companies. The group's major funding is from the Ministry of Education in Singapore, National Research Foundation, and companies such as Huawei.

Ridesharing is popular among travellers because it can reduce their travel costs, and it also holds the potential to reduce travel time, congestion, air pollution, and overall fuel consumption. Existing ridesharing systems (e.g., lyft, uberPOOL) often offer each traveler only one choice that aims to minimize system-wide vehicle travel distance or time. In this demonstration, we present a price-and-time-aware ridesharing system, termed as PTRider, which provides more options. It considers both pick-up time and price, so that travellers are able to choose the vehicle matching their preferences best. To answer the ridesharing request in real time, PTRider builds indexes on the road network and vehicles separately, and utilizes corresponding efficient matching methods. A real-life dataset that contains 432,327 trips extracted from 17,000 Shanghai taxis for one day (May 29, 2009) is used to demonstrate that PTRider can return various options for every ridesharing request in real time.

Single-source and top-kSimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads.This paper presents ProbeSim, an index-freealgorithm for single-source and top-kSimRank queries that provides a non-trivial theoretical guarantee in the absolute error of query results. ProbeSimestimates SimRank similarities without precomputing any indexing structures, and thus can naturally support real-timeSimRank queries on dynamicgraphs. Besides the theoretical guarantee, ProbeSimalso offers satisfying practical efficiency and effectiveness due to non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of pooling.

Personalized PageRank (PPR)computation is a fundamental operation in web search, social networks, and graph analysis. Given a graph G, a source s,and a target t,the PPR query Π(s, t) returns the probability that a random walk on Gstarting from sterminates at t.Unlike global PageRank which can be effectively pre-computed and materialized, the PPR result depends on both the source and the target, rendering results materialization infeasible for large graphs. Existing indexing techniques have rather limited effectiveness; in fact, the current state-of-the-art solution, BiPPR,answers individual PPR queries without pre-computation or indexing, and yet it outperforms all previous index-based solutions.Motivated by this, we propose HubPPR,an effective indexing scheme for PPR computation with controllable tradeoffs for accuracy, query time, and memory consumption. The main idea is to pre-compute and index auxiliary information for selected hub nodes that are often involved in PPR processing. Going one step further, we extend HubPPR to answer top-kPPR queries, which returns the knodes with the highest PPR values with respect to a source s, among a given set Tof target nodes. Extensive experiments demonstrate that compared to the current best solution BiPPR, HubPPRachieves up to 10x and 220x speedup for PPR and top-kPPR processing, respectively, with moderate memory consumption. Notably, with a single commodity server, HubPPRanswers a top-kPPR query in seconds on graphs with billions of edges, with high accuracy and strong result quality guarantees.

In a constrained shortest path (CSP)query, each edge in the road network is associated with both a length and a cost. Given an origin s, a destination t, and a cost constraint θ, the goal is to find the shortest path from sto twhose total cost does not exceed θ. Because exact CSP is NP-hard, previous work mostly focuses on approximate solutions. Even so, existing methods are still prohibitively expensive for large road networks. Two main reasons are (i) that they fail to utilize the special properties of road networks and (ii) that most of them process queries without indices; the few existing indices consume large amounts of memory and yet have limited effectiveness in reducing query costs.Motivated by this, we propose COLA, the first practical solution for approximate CSP processing on large road networks. COLAexploits the facts that a road network can be effectively partitioned, and that there exists a relatively small set of landmark vertices that commonly appear in CSP results. Accordingly, COLAindexes the vertices lying on partition boundaries, and applies an on-the-fly algorthm called α-Dijkfor path computation within a partition, which effectively prunes paths based on landmarks. Extensive experiments demonstrate that on continent-sized road networks, COLAanswers an approximate CSP query in sub-second time, whereas existing methods take hours. Interestingly, even without an index, the α-Dijkalgorithm in COLAstill outperforms previous solutions by more than an order of magnitude.