Random Graph Matching with Improved Noise Robustness

• URL: http://arxiv.org/abs/2101.11783v1
• Date: Thu, 28 Jan 2021 02:39:27 GMT
• Title: Random Graph Matching with Improved Noise Robustness
• Authors: Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov
• Abstract summary: We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
• Score: 2.294014185517203
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental computational problem arises frequently in multiple fields such as computer vision and biology. Recently, there has been a plethora of work studying efficient algorithms for graph matching under probabilistic models. In this work, we propose a new algorithm for graph matching and show that, for two Erd\H{o}s-R\'enyi graphs with edge correlation $1-\alpha$, our algorithm recovers the underlying matching with high probability when $\alpha \le 1 / (\log \log n)^C$, where $n$ is the number of vertices in each graph and $C$ denotes a positive universal constant. This improves the condition $\alpha \le 1 / (\log n)^C$ achieved in previous work.

Related papers

• 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)
• A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation [12.869436542291144]
  We propose an efficient algorithm for matching two correlated ErdHos--R'enyi graphs with $n$ whose edges are correlated through a latent correspondence. Our algorithm has running time and succeeds to recover the latent matching as long as the edge correlation is non-vanishing.
  arXiv  Detail & Related papers  (2023-06-01T00:58:50Z)
• Correlation Clustering Algorithm for Dynamic Complete Signed Graphs: An Index-based Approach [9.13755431537592]
  In this paper, we reduce the complexity of approximating the correlation clustering problem from $O(mtimesleft( 2+ alpha (G) right)+n)$ to $O(m+n)$ for any given value of $varepsilon$ for a complete signed graph. Our approach gives the same output as the original algorithm and makes it possible to implement the algorithm in a full dynamic setting.
  arXiv  Detail & Related papers  (2023-01-01T10:57:36Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
  arXiv  Detail & Related papers  (2022-10-04T04:36:15Z)
• Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
  We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each. This is the first graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs.
  arXiv  Detail & Related papers  (2022-09-25T20:00:28Z)
• Verification and search algorithms for causal DAGs [11.038866111306728]
  We give a characterization of a minimal sized set of atomic interventions to check the correctness of a claimed causal graph. We generalize our results to the settings of bounded size interventions and node-dependent interventional costs. Our result is the first known algorithm that gives a non-trivial approximation guarantee to the verifying size on general unweighted graphs.
  arXiv  Detail & Related papers  (2022-06-30T15:52:30Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  We study the problem of efficiently summarizing a short video into several paragraphs, leveraging recent progress in fast graph sampling. Experimental results show that our algorithm achieves comparable video summarization as state-of-the-art methods, at a substantially reduced complexity.
  arXiv  Detail & Related papers  (2021-10-21T18:43:00Z)
• Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
  This paper deals with the problem of graph matching or network alignment for ErdHos--R'enyi graphs. It can be viewed as a noisy average-case version of the graph isomorphism problem.
  arXiv  Detail & Related papers  (2021-10-11T05:07: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)
• Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
  Existing deep neural methods require $Omega(n2)$ complexity by building up the adjacency matrix. We develop a novel autoregressive model, named BiGG, that utilizes this sparsity to avoid generating the full adjacency matrix. During training this autoregressive model can be parallelized with $O(log n)$ synchronization stages.
  arXiv  Detail & Related papers  (2020-06-28T04:37:57Z)

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.