Crypto'Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph Learning

• URL: http://arxiv.org/abs/2309.10890v1
• Date: Tue, 19 Sep 2023 19:30:28 GMT
• Title: Crypto'Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph Learning
• Authors: Sofiane Azogagh, Zelma Aubin Birba, S\'ebastien Gambs and Marc-Olivier Killijian
• Abstract summary: Crypto'Graph is an efficient protocol for privacy-preserving link prediction on distributed graphs. It is illustrated for defense against graph poisoning attacks, in which it is possible to identify potential adversarial links without compromising the privacy of the graphs of individual parties.
• Score: 2.048226951354646
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graphs are a widely used data structure for collecting and analyzing relational data. However, when the graph structure is distributed across several parties, its analysis is particularly challenging. In particular, due to the sensitivity of the data each party might want to keep their partial knowledge of the graph private, while still willing to collaborate with the other parties for tasks of mutual benefit, such as data curation or the removal of poisoned data. To address this challenge, we propose Crypto'Graph, an efficient protocol for privacy-preserving link prediction on distributed graphs. More precisely, it allows parties partially sharing a graph with distributed links to infer the likelihood of formation of new links in the future. Through the use of cryptographic primitives, Crypto'Graph is able to compute the likelihood of these new links on the joint network without revealing the structure of the private individual graph of each party, even though they know the number of nodes they have, since they share the same graph but not the same links. Crypto'Graph improves on previous works by enabling the computation of a certain number of similarity metrics without any additional cost. The use of Crypto'Graph is illustrated for defense against graph poisoning attacks, in which it is possible to identify potential adversarial links without compromising the privacy of the graphs of individual parties. The effectiveness of Crypto'Graph in mitigating graph poisoning attacks and achieving high prediction accuracy on a graph neural network node classification task is demonstrated through extensive experimentation on a real-world dataset.

Related papers

• GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data [4.893653298798788]
  cryptographic approaches, such as secure multiparty computation, can be used to compute in a secure manner the function of a distributed graph without centralizing the data of each participant. We propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors can reconstruct the adjacency matrix of the graph. We consider two models of adversary, one who observes the common neighbors matrix only, and a knowledgeable one, that has a partial knowledge of the original graph.
  arXiv  Detail & Related papers  (2024-12-03T09:42:28Z)
• GraphPub: Generation of Differential Privacy Graph with High Availability [21.829551460549936]
  Differential privacy (DP) is a common method to protect privacy on graph data. Due to the complex topological structure of graph data, applying DP on graphs often affects the message passing and aggregation of GNN models. We propose graph publisher (GraphPub), which can protect graph topology while ensuring the availability of data is basically unchanged.
  arXiv  Detail & Related papers  (2024-02-28T20:02:55Z)
• Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data [91.27527985415007]
  Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph. We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
  arXiv  Detail & Related papers  (2023-06-05T07:53:52Z)
• Finding MNEMON: Reviving Memories of Node Embeddings [39.206574462957136]
  We show that an adversary can recover edges with decent accuracy by only gaining access to the node embedding matrix of the original graph. We demonstrate the effectiveness and applicability of our graph recovery attack through extensive experiments.
  arXiv  Detail & Related papers  (2022-04-14T13:44:26Z)
• Graph-in-Graph (GiG): Learning interpretable latent graphs in non-Euclidean domain for biological and healthcare applications [52.65389473899139]
  Graphs are a powerful tool for representing and analyzing unstructured, non-Euclidean data ubiquitous in the healthcare domain. Recent works have shown that considering relationships between input data samples have a positive regularizing effect for the downstream task. We propose Graph-in-Graph (GiG), a neural network architecture for protein classification and brain imaging applications.
  arXiv  Detail & Related papers  (2022-04-01T10:01:37Z)
• Distributed Graph Learning with Smooth Data Priors [61.405131495287755]
  We propose a novel distributed graph learning algorithm, which permits to infer a graph from signal observations on the nodes. Our results show that the distributed approach has a lower communication cost than a centralised algorithm without compromising the accuracy in the inferred graph.
  arXiv  Detail & Related papers  (2021-12-11T00:52:02Z)
• Inference Attacks Against Graph Neural Networks [33.19531086886817]
  Graph embedding is a powerful tool to solve the graph analytics problem. While sharing graph embedding is intriguing, the associated privacy risks are unexplored. We systematically investigate the information leakage of the graph embedding by mounting three inference attacks.
  arXiv  Detail & Related papers  (2021-10-06T10:08:11Z)
• Edge but not Least: Cross-View Graph Pooling [76.71497833616024]
  This paper presents a cross-view graph pooling (Co-Pooling) method to better exploit crucial graph structure information. Through cross-view interaction, edge-view pooling and node-view pooling seamlessly reinforce each other to learn more informative graph-level representations.
  arXiv  Detail & Related papers  (2021-09-24T08:01:23Z)
• GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
  We present textbfGraph textbfModel textbfInversion attack (GraphMI), which aims to extract private graph data of the training graph by inverting GNN. Specifically, we propose a projected gradient module to tackle the discreteness of graph edges while preserving the sparsity and smoothness of graph features. We design a graph auto-encoder module to efficiently exploit graph topology, node attributes, and target model parameters for edge inference.
  arXiv  Detail & Related papers  (2021-06-05T07:07:52Z)
• Signed Graph Diffusion Network [17.20546861491478]
  Given a signed social graph, how can we learn appropriate node representations to infer the signs of missing edges? We propose Signed Graph Diffusion Network (SGDNet), a novel graph neural network that achieves end-to-end node representation learning for link sign prediction in signed social graphs.
  arXiv  Detail & Related papers  (2020-12-28T11:08:30Z)
• Adversarial Privacy Preserving Graph Embedding against Inference Attack [9.90348608491218]
  Graph embedding has been proved extremely useful to learn low-dimensional feature representations from graph structured data. Existing graph embedding methods do not consider users' privacy to prevent inference attacks. We propose Adrial Privacy Graph Embedding (APGE), a graph adversarial training framework that integrates the disentangling and purging mechanisms to remove users' private information from learned node representations.
  arXiv  Detail & Related papers  (2020-08-30T00:06:49Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.