GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data

• URL: http://arxiv.org/abs/2412.02329v2
• Date: Fri, 06 Dec 2024 14:20:15 GMT
• Title: GRAND : Graph Reconstruction from potential partial Adjacency and Neighborhood Data
• Authors: Sofiane Azogagh, Zelma Aubin Birba, Josée Desharnais, Sébastien Gambs, Marc-Olivier Killijian, Nadia Tawbi,
• Abstract summary: 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.<n>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.<n>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.
• Score: 4.893653298798788
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. However, the output of the protocol itself can leak sensitive information about the structure of the original graph. In particular, in this work we propose an approach by which an adversary observing the result of a private protocol for the computation of the number of common neighbors between all pairs of vertices, can reconstruct the adjacency matrix of the graph. In fact, this can only be done up to co-squareness, a notion we introduce, as two different graphs can have the same matrix of common neighbors. 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. Our results demonstrate that secure multiparty protocols are not enough for privacy protection, especially in the context of highly structured data such as graphs. The reconstruction that we propose is interesting in itself from the point of view of graph theory.

Related papers

• PieClam: A Universal Graph Autoencoder Based on Overlapping Inclusive and Exclusive Communities [7.130067003076749]
  PieClam is a graph autoencoder for representing any graph as overlapping generalized communities. We show that PieClam is a universal autoencoder, able to uniformly approximately reconstruct any graph.
  arXiv  Detail & Related papers  (2024-09-18T00:49:42Z)
• Crypto'Graph: Leveraging Privacy-Preserving Distributed Link Prediction for Robust Graph Learning [2.048226951354646]
  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.
  arXiv  Detail & Related papers  (2023-09-19T19:30:28Z)
• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  We investigate a previously overlooked phenomenon: in many cases, a densely connected, complementary graph can be found for the original graph. The denser graph may share nodes with the original graph, which offers a natural bridge for transferring selective, meaningful knowledge. We identify this setting as Graph Intersection-induced Transfer Learning (GITL), which is motivated by practical applications in e-commerce or academic co-authorship predictions.
  arXiv  Detail & Related papers  (2023-02-27T22:56:06Z)
• Variational Graph Generator for Multi-View Graph Clustering [51.89092260088973]
  We propose Variational Graph Generator for Multi-View Graph Clustering (VGMGC) This generator infers a reliable variational consensus graph based on a priori assumption over multiple graphs. It embeds the inferred view-common graph and view-specific graphs together with features.
  arXiv  Detail & Related papers  (2022-10-13T13:19:51Z)
• Collaborative likelihood-ratio estimation over graphs [55.98760097296213]
  Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We develop this idea in a concrete non-parametric method that we call Graph-based Relative Unconstrained Least-squares Importance Fitting (GRULSIF) We derive convergence rates for our collaborative approach that highlights the role played by variables such as the number of available observations per node, the size of the graph, and how accurately the graph structure encodes the similarity between tasks.
  arXiv  Detail & Related papers  (2022-05-28T15:37:03Z)
• A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
  We propose a robust framework for adversarial graph embedding, named AGE. AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution. Based on this framework, we propose three models to handle three types of graph data.
  arXiv  Detail & Related papers  (2021-05-22T07:05:48Z)
• COLOGNE: Coordinated Local Graph Neighborhood Sampling [1.6498361958317633]
  replacing discrete unordered objects such as graph nodes by real-valued vectors is at the heart of many approaches to learning from graph data. We address the problem of learning discrete node embeddings such that the coordinates of the node vector representations are graph nodes. This opens the door to designing interpretable machine learning algorithms for graphs as all attributes originally present in the nodes are preserved.
  arXiv  Detail & Related papers  (2021-02-09T11:39:06Z)
• Generating a Doppelganger Graph: Resembling but Distinct [5.618335078130568]
  We propose an approach to generating a doppelganger graph that resembles a given one in many graph properties. The approach is an orchestration of graph representation learning, generative adversarial networks, and graph realization algorithms.
  arXiv  Detail & Related papers  (2021-01-23T22:08:27Z)
• Factorizable Graph Convolutional Networks [90.59836684458905]
  We introduce a novel graph convolutional network (GCN) that explicitly disentangles intertwined relations encoded in a graph. FactorGCN takes a simple graph as input, and disentangles it into several factorized graphs. We evaluate the proposed FactorGCN both qualitatively and quantitatively on the synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2020-10-12T03:01:40Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question [13.625395368083641]
  We address the common setting in which one of the graphs to match is a bipartite network and one is unipartite. We formulate the graph matching problem between a bipartite and a unipartite graph using an undirected graphical model. We show how our methods can result in a more accurate matching than the naive approach of transforming the bipartite networks into unipartite.
  arXiv  Detail & Related papers  (2020-02-05T05:24:54Z)

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.