Correcting the Output of Approximate Graph Matching Algorithms

Joseph Lubars, R. Srikant

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Approximate graph matching refers to the problem of finding the best correspondence between the node labels of two correlated graphs. The problem has been applied to a number of domains, including social network de-anonymization. Recently, a number of algorithms have been proposed for seeded graph matching, which uses a few seed matches between two graphs to determine the remaining correspondence. We adapt the ideas from seeded algorithms to develop a graph matching correction algorithm, which takes a partially correct correspondence as input and returns an improved correspondence. We show that this algorithm can correct all errors in graph matching for stochastic block model graphs with high probability. Finally, we apply our algorithm as a post-processing step for other approximate graph matching algorithms to significantly improve the performance of state-of-the-art algorithms for seedless graph matching.

Original languageEnglish (US)
Title of host publicationINFOCOM 2018 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1745-1753
Number of pages9
ISBN (Electronic)9781538641286
DOIs
StatePublished - Oct 8 2018
Event2018 IEEE Conference on Computer Communications, INFOCOM 2018 - Honolulu, United States
Duration: Apr 15 2018Apr 19 2018

Publication series

NameProceedings - IEEE INFOCOM
Volume2018-April
ISSN (Print)0743-166X

Other

Other2018 IEEE Conference on Computer Communications, INFOCOM 2018
CountryUnited States
CityHonolulu
Period4/15/184/19/18

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Correcting the Output of Approximate Graph Matching Algorithms'. Together they form a unique fingerprint.

  • Cite this

    Lubars, J., & Srikant, R. (2018). Correcting the Output of Approximate Graph Matching Algorithms. In INFOCOM 2018 - IEEE Conference on Computer Communications (pp. 1745-1753). [8486238] (Proceedings - IEEE INFOCOM; Vol. 2018-April). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/INFOCOM.2018.8486238