Efficiently matching random inhomogeneous graphs via degree profiles

• URL: http://arxiv.org/abs/2310.10441v1
• Date: Mon, 16 Oct 2023 14:25:43 GMT
• Title: Efficiently matching random inhomogeneous graphs via degree profiles
• Authors: Jian Ding, Yumou Fei, Yuanzheng Wang
• Abstract summary: We find an efficient matching algorithm as long as the minimal average degree is at least $Omega(log2 n)$. Inspired by and extending the matching algorithm via degree profiles, we obtain an efficient matching algorithm as long as the minimal average degree is at least $Omega(log-2 n)$.
• Score: 11.485620556026571
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the problem of recovering the latent vertex correspondence between two correlated random graphs with vastly inhomogeneous and unknown edge probabilities between different pairs of vertices. Inspired by and extending the matching algorithm via degree profiles by Ding, Ma, Wu and Xu (2021), we obtain an efficient matching algorithm as long as the minimal average degree is at least $\Omega(\log^{2} n)$ and the minimal correlation is at least $1 - O(\log^{-2} n)$.

Related papers

• Efficient Graph Matching for Correlated Stochastic Block Models [7.320365821066744]
  We study learning problems on correlated block models with two balanced communities. Our main result gives the first efficient algorithm for graph matching in this setting. We extend this to an efficient algorithm for exact graph matching whenever this is information-theoretically possible.
  arXiv  Detail & Related papers  (2024-12-03T18:36:45Z)
• 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)
• Efficient Algorithms for Exact Graph Matching on Correlated Stochastic Block Models with Constant Correlation [7.914348940034351]
  We propose an efficient algorithm for matching graphs with community structure. Our algorithm is the first low-order-time algorithm achieving exact matching between two correlated block models.
  arXiv  Detail & Related papers  (2023-05-31T09:06:50Z)
• Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
  We present two new classes of algorithms for efficient field integration on graphs encoding point clouds. The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
  arXiv  Detail & Related papers  (2023-02-02T08:33:36Z)
• 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)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  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.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
  We show that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model. For loss factors, we prove that HSDMPG can attain an $mathcalObig (1/sttnbig)$ which is at the order of excess error on a learning model.
  arXiv  Detail & Related papers  (2020-09-18T02:18:44Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  We consider the problem of ranking $N$ objects starting from a set of noisy pairwise comparisons provided by a crowd of equal workers. We propose a class of non-adaptive ranking algorithms that rely on a least-squares intrinsic optimization criterion for the estimation of qualities.
  arXiv  Detail & Related papers  (2020-02-26T16:19:09Z)

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.