research-article

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Authors:

Osman Emre Dai,

Daniel Cullina,

Negar Kiyavash,

Matthias GrossglauserAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 47, Issue 1

Pages 96 - 97

https://doi.org/10.1145/3376930.3376992

Published: 17 December 2019 Publication History

Get Access

Abstract

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact informationtheoretic threshold for graph alignment in correlated Erdős-Rényi graphs. However, very little is known about the existence of efficient algorithms to achieve graph alignment without seeds.

In this work we identify a region in which a straightforward O(n11/5 logn)-time canonical labeling algorithm, initially introduced in the context of graph isomorphism, succeeds in aligning correlated Erdős-Rényi graphs. The algorithm has two steps. In the first step, all vertices are labeled by their degrees and a trivial minimum distance alignment (i.e., sorting vertices according to their degrees) matches a fixed number of highest degree vertices in the two graphs. Having identified this subset of vertices, the remaining vertices are matched using a alignment algorithm for bipartite graphs.

Reference

[1]

D. Cullina and N. Kiyavash, "Improved achievability and converse bounds for erdosrenyi graph matching," in Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science - SIGMETRICS 2016, ACM Press, 2016.

Google Scholar

Cited By

View all

Wang ZZhang NWang WWang L(2024)On the Feasible Region of Efficient Algorithms for Attributed Graph AlignmentIEEE Transactions on Information Theory10.1109/TIT.2024.335110770:5(3622-3639)Online publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3351107
Wang ZZhang NWang WWang L(2022)On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834398(1163-1168)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834398
Dai OCullina DKiyavash N(2020)Achievability of nearly-exact alignment for correlated Gaussian databases2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9174507(1230-1235)Online publication date: 21-Jun-2020
https://dl.acm.org/doi/10.1109/ISIT44484.2020.9174507

Index Terms

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis
      1. Network flows

Index terms have been assigned to the content through auto-classification.

Recommendations

Partial Recovery of Erdðs-Rényi Graph Alignment via k-Core Alignment
SIGMETRICS

We determine information theoretic conditions under which it is possible to partially recover the alignment used to generate a pair of sparse, correlated Erdos-Renyi graphs. To prove our achievability result, we introduce the k-core alignment estimator. ...
Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs
SIGMETRICS '19: Abstracts of the 2019 SIGMETRICS/Performance Joint International Conference on Measurement and Modeling of Computer Systems

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdős-...
Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdos-Rényi Graphs

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 47, Issue 1

June 2019

100 pages

ISSN:0163-5999

DOI:10.1145/3376930

Editor:
Zhenhua Liu
Stony Brook University

Issue’s Table of Contents

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 December 2019

Published in SIGMETRICS Volume 47, Issue 1

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
47
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wang ZZhang NWang WWang L(2024)On the Feasible Region of Efficient Algorithms for Attributed Graph AlignmentIEEE Transactions on Information Theory10.1109/TIT.2024.335110770:5(3622-3639)Online publication date: 8-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3351107
Wang ZZhang NWang WWang L(2022)On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834398(1163-1168)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834398
Dai OCullina DKiyavash N(2020)Achievability of nearly-exact alignment for correlated Gaussian databases2020 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT44484.2020.9174507(1230-1235)Online publication date: 21-Jun-2020
https://dl.acm.org/doi/10.1109/ISIT44484.2020.9174507

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Partial Recovery of Erdðs-Rényi Graph Alignment via k-Core Alignment

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdos-Rényi Graphs