Efficiently matching random inhomogeneous graphs via degree profiles

2023/10/16 by Jian Ding, Ding, Jian, Yumou Fei +3 · 3 citations
Computer Science · #Advanced Graph Neural Networks #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (stat.ML) #Privacy-Preserving Technologies in Data #Probability (math.PR) #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.2310.10441

openalex publication_date 2023/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Ω(log² n) and the minimal correlation is at least 1 - O(log^-2 n).

Cited by

• Testing Correlation in Graphs by Counting Bounded Degree Motifs
• Multiplexons: Limits of Multiplex Networks
• Sample Complexity of Correlation Detection in the Gaussian Wigner Model

Related

• Efficient random graph matching via degree profiles
• A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
• Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery
• (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs
• Matching Correlated Inhomogeneous Random Graphs using the k-core Estimator