Partial Recovery in the Graph Alignment Problem

• URL: http://arxiv.org/abs/2007.00533v5
• Date: Thu, 13 Jan 2022 09:07:04 GMT
• Title: Partial Recovery in the Graph Alignment Problem
• Authors: Georgina Hall and Laurent Massouli\'e
• Abstract summary: We consider the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem. We show that it is possible to achieve partial recovery in the $nqs=Theta(1)$ regime under certain additional assumptions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we consider the graph alignment problem, which is the problem of recovering, given two graphs, a one-to-one mapping between nodes that maximizes edge overlap. This problem can be viewed as a noisy version of the well-known graph isomorphism problem and appears in many applications, including social network deanonymization and cellular biology. Our focus here is on partial recovery, i.e., we look for a one-to-one mapping which is correct on a fraction of the nodes of the graph rather than on all of them, and we assume that the two input graphs to the problem are correlated Erd\H{o}s-R\'enyi graphs of parameters $(n,q,s)$. Our main contribution is then to give necessary and sufficient conditions on $(n,q,s)$ under which partial recovery is possible with high probability as the number of nodes $n$ goes to infinity. In particular, we show that it is possible to achieve partial recovery in the $nqs=\Theta(1)$ regime under certain additional assumptions.

Related papers

• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• Graph Mixup with Soft Alignments [49.61520432554505]
  We study graph data augmentation by mixup, which has been used successfully on images. We propose S-Mixup, a simple yet effective mixup method for graph classification by soft alignments.
  arXiv  Detail & Related papers  (2023-06-11T22:04:28Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Matching recovery threshold for correlated random graphs [9.12788494573002]
  For two correlated graphs which are independently sub-sampled from a common ErdHos-R'enyi graph $mathbfG(n, p)$, we wish to recover their emphlatent matching from the observation of these two graphs emphwithout labels. Our result sharpens a constant factor in a recent work by Wu, Xu and Yu.
  arXiv  Detail & Related papers  (2022-05-29T13:04:20Z)
• Correlation detection in trees for partial graph alignment [3.5880535198436156]
  We consider alignment of graphs, which consists in finding a mapping between the nodes of two graphs which preserves most of the edges. Our approach is to compare local structures in the two graphs, matching two nodes if their neighborhoods are 'close enough' for correlated graphs. This problem can be rephrased in terms of testing whether a pair of branching trees is drawn from either a product distribution, or a correlated distribution.
  arXiv  Detail & Related papers  (2021-07-15T22:02:27Z)
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• Impossibility of Partial Recovery in the Graph Alignment Problem [3.5880535198436156]
  We show an average-case and noisy version of the well-known NP-hard graph isomorphism problem. For the correlated Erd"os-R'enyi model, we prove an impossibility result for partial recovery in the sparse regime. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise.
  arXiv  Detail & Related papers  (2021-02-04T15:26:48Z)
• Settling the Sharp Reconstruction Thresholds of Random Graph Matching [19.54246087326288]
  We study the problem of recovering the hidden correspondence between two edge-correlated random graphs. For dense graphs with $p=n-o(1)$, we prove that there exists a sharp threshold. For sparse ErdHos-R'enyi graphs with $p=n-Theta(1)$, we show that the all-or-nothing phenomenon no longer holds.
  arXiv  Detail & Related papers  (2021-01-29T21:49:50Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)

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.