Impossibility of Partial Recovery in the Graph Alignment Problem

• URL: http://arxiv.org/abs/2102.02685v1
• Date: Thu, 4 Feb 2021 15:26:48 GMT
• Title: Impossibility of Partial Recovery in the Graph Alignment Problem
• Authors: Luca Ganassali, Laurent Massouli\'e, Marc Lelarge
• Abstract summary: 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.
• Score: 3.5880535198436156
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as 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, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erd\"os-R\'enyi graph.

Related papers

• Information-Theoretic Thresholds for the Alignments of Partially Correlated Graphs [7.001453437549302]
  ErdHos-R'enyi graphs model, wherein a pair of induced subgraphs with a certain number are correlated. We prove that there exists an optimal rate for partial recovery for the number of correlated nodes. In the proof of possibility results, we propose correlated functional digraphs, which partition the edges of the intersection graph into two types of components.
  arXiv  Detail & Related papers  (2024-06-08T10:17:42Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• 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)
• Contrastive Graph Clustering in Curvature Spaces [74.03252813800334]
  We present a novel end-to-end contrastive graph clustering model named CONGREGATE. To support geometric clustering, we construct a theoretically grounded Heterogeneous Curvature Space. We then train the graph clusters by an augmentation-free reweighted contrastive approach.
  arXiv  Detail & Related papers  (2023-05-05T14:04:52Z)
• Casting graph isomorphism as a point set registration problem using a simplex embedding and sampling [0.0]
  A graph can be represented as a point set in enough dimensions using a simplex embedding and sampling. The isomorphism of them corresponds to the existence of a perfect registration between the point set forms of the graphs. The related idea of equivalence classes suggests that graph canonization may be an important tool in tackling graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-11-15T12:16:21Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• 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)
• 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)
• 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)
• Testing correlation of unlabeled random graphs [18.08210501570919]
  We study the problem of detecting the edge correlation between two random graphs with $n$ unlabeled nodes. This is formalized as a hypothesis testing problem, where under the null hypothesis, the two graphs are independently generated. Under the alternative, the two graphs are edge-correlated under some latent node correspondence, but have the same marginal distributions as the null.
  arXiv  Detail & Related papers  (2020-08-23T19:19:45Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)

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.