Query: gnn privacy

title: A resource aware approach for authenticating privacy preserving GNN queries
abstract: Nowadays many location service providers (LSPs) employ spatial databases outsourced from a third party data owner (DO) to answer various users' queries, e.g. group nearest neighbor (GNN) queries that enable a group of users to find a meeting place minimizing their aggregate travel distance. Along with the benefits from LSPs and DO, protection of location privacy and authentication of query results become two major concerns for users while assessing GNN queries. This paper proposes a resource aware approach that supports effective location privacy preservation and efficient query result authentication with a less storage, communication and computation overhead. Specifically, two centroid based techniques are investigated to generate a centroid point, which initiates GNN query on behalf of the group members. Then, an authentication algorithm based on Voronoi diagram is proposed for spatial queries. Finally, we demonstrate how our approach is resistant to various attacks, and evaluate its performance by comparing with three competitive approaches. The results show the proposed approach is better and more economical in terms of resource overhead, while considering both privacy preservation and query authentication.

title: Federated Dynamic GNN with Secure Aggregation
abstract: Given video data from multiple personal devices or street cameras, can we exploit the structural and dynamic information to learn dynamic representation of objects for applications such as distributed surveillance, without storing data at a central server that leads to a violation of user privacy? In this work, we introduce Federated Dynamic Graph Neural Network (Feddy) a distributed and secured framework to learn the object representations from multi user graph sequences: i) It aggregates structural information from nearby objects in the current graph as well as dynamic information from those in the previous graph. It uses a self supervised loss of predicting the trajectories of objects. ii) It is trained in a federated learning manner. The centrally located server sends the model to user devices. Local models on the respective user devices learn and periodically send their learning to the central server without ever exposing the user's data to server. iii) Studies showed that the aggregated parameters could be inspected though decrypted when broadcast to clients for model synchronizing, after the server performed a weighted average. We design an appropriate aggregation mechanism of secure aggregation primitives that can protect the security and privacy in federated learning with scalability. Experiments on four video camera datasets (in four different scenes) as well as simulation demonstrate that Feddy achieves great effectiveness and security.

title: Privacy Preserving Graph Neural Network for Node Classification
abstract: Recently, Graph Neural Network (GNN) has achieved remarkable progresses in various real world tasks on graph data, consisting of node features and the adjacent information between different nodes. High performance GNN models always depend on both rich features and complete edge information in graph. However, such information could possibly be isolated by different data holders in practice, which is the so called data isolation problem. To solve this problem, in this paper, we propose a Privacy Preserving GNN (PPGNN) learning paradigm for node classification task, which can be generalized to existing GNN models. Specifically, we split the computation graph into two parts. We leave the private data (i.e. features, edges, and labels) related computations on data holders, and delegate the rest of computations to a semi honest server. We conduct experiments on three benchmarks and the results demonstrate that PPGNN significantly outperforms the GNN models trained on the isolated data and has comparable performance with the traditional GNN trained on the mixed plaintext data.

title: Adversary for Social Good: Protecting Familial Privacy through Joint Adversarial Attacks
abstract: Social media has been widely used among billions of people with dramatical participation of new users every day. Among them, social networks maintain the basic social characters and host huge amount of personal data. While protecting user sensitive data is obvious and demanding, information leakage due to adversarial attacks is somehow unavoidable, yet hard to detect. For example, implicit social relation such as family information may be simply exposed by network structure and hosted face images through off the shelf graph neural networks (GNN) which will be empirically proved in this paper. To address this issue, in this paper, we propose a novel adversarial attack algorithm for social good. First, we start from conventional visual family understanding problem, and demonstrate that familial information can easily be exposed to attackers by connecting sneak shots to social networks. Second, to protect family privacy on social networks, we propose a novel adversarial attack algorithm that produces both adversarial features and graph under a given budget. Specifically, both features on the node and edges between nodes will be perturbed gradually such that the probe images and its family information can not be identified correctly through conventional GNN. Extensive experiments on a popular visual social dataset have demonstrated that our defense strategy can significantly mitigate the impacts of family information leakage.

title: Efficient privacy preserving group nearest neighbor queries with the presence of active adversaries
abstract: Location based services (LBSs) allow users to ask location dependent queries and receive information based on their location. A group of users can send a group nearest neighbor (GNN) query in order to receive a Point Of Interest (POI) This POI in turn shows a point which is the minimum distance from all members of the group. To benefit from these services, it is important to preserve the location privacy of each group user from others in the group (Intragroup location privacy) as well as from anyone outside of the group, including the LBS, (Intergroup location privacy) It may also be necessary to protect the location privacy of the resulting POI from the LBS and other possible attackers. In this paper, we propose two different privacy preserving protocols for finding the exact answer to a GNN query among a set of returned POIs. The first protocol assumes a semi honest model while the second one works in a malicious model. The proposed protocols are based on the Anonymous Veto network and Burmester Desmedt key establishment protocols. The security analysis shows that the proposed protocols provide both Intragroup and Intergroup location privacy; they also protect the location privacy of the resulting POI and are resistant to collusion and multi point aggregate distance attacks. The performed analyses indicate that they incur a constant computation cost per user and are efficient in terms of computation and communication costs.

title: Enhanced Privacy Preserving Group Nearest Neighbor Search
abstract: Group <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq1 2930696.gif"/alternatives>/inline formula> nearest neighbor <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq2 2930696.gif"/alternatives>/inline formula>GNN) search allows a group of <inline formula><tex math notation="LaTeX"$n$/tex math><alternatives><mml:math><mml:mi>n</mml:mi>/mml:math><inline graphic xlink:href="wu ieq3 2930696.gif"/alternatives>/inline formula> mobile users to jointly retrieve <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq4 2930696.gif"/alternatives>/inline formula> points from a location based service provider (LSP) that minimizes the aggregate distance to them. We identify four protection objectives in the privacy preserving <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq5 2930696.gif"/alternatives>/inline formula>GNN search: (i) every user's location should be protected from LSP; (ii) the group's query and the query answer should be protected from LSP; (iii) LSP's private database information should be protected from users; (iv) every user's location should be protected from other users in the group. We design two privacy preserving solutions under two types of threat model to the privacy preserving <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq6 2930696.gif"/alternatives>/inline formula>GNN search in the full user collusion environment, where any <inline formula><tex math notation="LaTeX"$n 1$/tex math><alternatives><mml:math><mml:mrow><mml:mi>n</mml:mi><mml:mo> /mml:mo><mml:mn>1</mml:mn>/mml:mrow>/mml:math><inline graphic xlink:href="wu ieq7 2930696.gif"/alternatives>/inline formula> users in the group may collude to infer the location of the remaining user. Our solutions do not rely on heavy pre computation on LSP like previous works. Though we consider <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq8 2930696.gif"/alternatives>/inline formula>GNN, the proposed privacy preserving solutions can be easily adopted to any group query as it treats the query answering (i.e. <inline formula><tex math notation="LaTeX"$k$/tex math><alternatives><mml:math><mml:mi>k</mml:mi>/mml:math><inline graphic xlink:href="wu ieq9 2930696.gif"/alternatives>/inline formula>GNN) as a black box. Theoretical and experimental analysis suggest that our solutions are highly efficient in both communication cost and user computational cost while incurring some reasonable overhead on LSP.

title: FedGNN: Federated Graph Neural Network for Privacy Preserving Recommendation
abstract: Graph neural network (GNN) is widely used for recommendation to model high order interactions between users and items. Existing GNN based recommendation methods rely on centralized storage of user item graphs and centralized model learning. However, user data is privacy sensitive, and the centralized storage of user item graphs may arouse privacy concerns and risk. In this paper, we propose a federated framework for privacy preserving GNN based recommendation, which can collectively train GNN models from decentralized user data and meanwhile exploit high order useritem interaction information with privacy well protected. In our method, we locally train GNN model in each user client based on the user item graph inferred from the local user item interaction data. Each client uploads the local gradients of GNN to a server for aggregation, which are further sent to user clients for updating local GNN models. Since local gradients may contain private information, we apply local differential privacy techniques to the local gradients to protect user privacy. In addition, in order to protect the items that users have interactions with, we propose to incorporate randomly sampled items as pseudo interacted items for anonymity. To incorporate high order user item interactions, we propose a user item graph expansion method that can find neighboring users with co interacted items and exchange their embeddings for expanding the local user item graphs in a privacy preserving way. Extensive experiments on six benchmark datasets validate that our approach can achieve competitive results with existing centralized GNN based recommendation methods and meanwhile effectively protect user privacy.

title: Protecting privacy for distance and rank based group nearest neighbor queries
abstract: This paper proposes a novel approach to safeguarding location privacy for GNN (group nearest neighbor) queries. Given the locations of a group of dispersed users, the GNN query returns the location that minimizes the total or the maximal distance for all group users. The returned location is typically a meeting place such as a cinema or coffee shop where the group would like to meet. In our work, we highlight the challenges for private GNN queries and propose a general framework that have two key features: (i) it ensures privacy in a decentralized manner and (ii) can compute an optimal location for GNN query that maximizes the group's overall preference for the meeting place. To mask their precise locations, we assume that user locations are given as regions to a location based service provider (LSP) The LSP computes then a set of candidate answers (i.e. meeting places) for the GNN query. We identify two privacy attacks on the user locations, the distance intersection attack and the rank disclosure attack. These attacks are possible when the answer of a GNN query is determined from the candidate answers in a straightforward manner. We develop private filters that prevent these attacks and compute the GNN from the retrieved candidate answers. Our decentralized approach ensures that neither the users nor the LSP can learn the location of any group member. Our algorithms compute from the candidate set an optimal meeting place given the group members' imprecise locations. Our key insight to an efficient computation is to prune the meeting places that cannot be GNNs given the locations of the group members within the search region. A comprehensive experimental evaluation shows the effectiveness of our approach to answering private GNN queries.

title: Protecting privacy for group nearest neighbor queries with crowdsourced data and computing
abstract: User privacy in location based services (LBSs) has become an important research area. We introduce a new direction to protect user privacy that evaluates LBSs with crowdsourced data and computation and eliminates the role of a location based service provider. We focus on the group nearest neighbor (GNN) query that allows a group to meet at their nearest point of interest such as a restaurant that minimizes the total or maximum distance of the group. We develop a crowdsource based approach, called PrivateMeetUp, to evaluate GNN queries in a privacy preserving manner and implement a working prototype of PrivateMeetUp.

title: Location privacy for group meetups
abstract: A Group Nearest Neighbor (GNN) query finds a point of interest (POI) that minimizes the aggregate distance for a group of users. In current systems, users have to reveal their exact, often sensitive locations to issue a GNN query. This calls for private GNN queries. However, existing methods for private GNN queries either are computationally too expensive for mobile phones or cannot resist sophisticated attacks. Our approach can efficiently and effectively process an important variant of private GNN queries: queries that minimize the maximum distance for any user in the group. To achieve high efficiency we develop a distributed multi party private protocol to compute the maximum function. Our method exploits geometric constraints to prune POIs and avoids unnecessary data disclosure. In contrast to current state of the art multi party private protocols, our proposed protocol does not rely on cryptography and has a fast runtime. Importantly, a user does not have to provide a location directly, even in imprecise form.