Seeded graph matching: Efficient algorithms and theoretical guarantees

Farhad Shirani; Siddharth Garg; Elza Erkip

doi:10.1109/ACSSC.2017.8335178

Seeded graph matching: Efficient algorithms and theoretical guarantees

Farhad Shirani, Siddharth Garg, Elza Erkip

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

In this paper, a new information theoretic framework for graph matching is introduced. Using this framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is introduced. The algorithm uses 'typicality matching' and techniques from point-to-point communications for reliable matching. Assuming an Erdös-Renyi model on the correlated graph pair, it is shown that successful matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between the edge variables in the two graphs.

Original language	English (US)
Title of host publication	Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
Editors	Michael B. Matthews
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	253-257
Number of pages	5
ISBN (Electronic)	9781538618233
DOIs	https://doi.org/10.1109/ACSSC.2017.8335178
State	Published - Jul 2 2017
Event	51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 - Pacific Grove, United States Duration: Oct 29 2017 → Nov 1 2017

Publication series

Name	Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
Volume	2017-October

Other

Other	51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017
Country/Territory	United States
City	Pacific Grove
Period	10/29/17 → 11/1/17

ASJC Scopus subject areas

Control and Optimization
Computer Networks and Communications
Hardware and Architecture
Signal Processing
Biomedical Engineering
Instrumentation

Access to Document

10.1109/ACSSC.2017.8335178

Cite this

Shirani, F., Garg, S., & Erkip, E. (2017). Seeded graph matching: Efficient algorithms and theoretical guarantees. In M. B. Matthews (Ed.), Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 (pp. 253-257). Article 8335178 (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017; Vol. 2017-October). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ACSSC.2017.8335178

Seeded graph matching: Efficient algorithms and theoretical guarantees. / Shirani, Farhad; Garg, Siddharth ; Erkip, Elza.
Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. ed. / Michael B. Matthews. Institute of Electrical and Electronics Engineers Inc., 2017. p. 253-257 8335178 (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017; Vol. 2017-October).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Shirani, F, Garg, S & Erkip, E 2017, Seeded graph matching: Efficient algorithms and theoretical guarantees. in MB Matthews (ed.), Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017., 8335178, Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017, vol. 2017-October, Institute of Electrical and Electronics Engineers Inc., pp. 253-257, 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017, Pacific Grove, United States, 10/29/17. https://doi.org/10.1109/ACSSC.2017.8335178

Shirani F, Garg S , Erkip E. Seeded graph matching: Efficient algorithms and theoretical guarantees. In Matthews MB, editor, Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. Institute of Electrical and Electronics Engineers Inc. 2017. p. 253-257. 8335178. (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017). doi: 10.1109/ACSSC.2017.8335178

Shirani, Farhad ; Garg, Siddharth ; Erkip, Elza. / Seeded graph matching : Efficient algorithms and theoretical guarantees. Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017. editor / Michael B. Matthews. Institute of Electrical and Electronics Engineers Inc., 2017. pp. 253-257 (Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017).

@inproceedings{dd050b35d3504ca3842aa05baef0cf78,

title = "Seeded graph matching: Efficient algorithms and theoretical guarantees",

abstract = "In this paper, a new information theoretic framework for graph matching is introduced. Using this framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is introduced. The algorithm uses 'typicality matching' and techniques from point-to-point communications for reliable matching. Assuming an Erd{\"o}s-Renyi model on the correlated graph pair, it is shown that successful matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between the edge variables in the two graphs.",

author = "Farhad Shirani and Siddharth Garg and Elza Erkip",

year = "2017",

month = jul,

day = "2",

doi = "10.1109/ACSSC.2017.8335178",

language = "English (US)",

series = "Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "253--257",

editor = "Matthews, {Michael B.}",

booktitle = "Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017",

note = "51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017 ; Conference date: 29-10-2017 Through 01-11-2017",

}

TY - GEN

T1 - Seeded graph matching

T2 - 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017

AU - Shirani, Farhad

AU - Garg, Siddharth

AU - Erkip, Elza

PY - 2017/7/2

Y1 - 2017/7/2

N2 - In this paper, a new information theoretic framework for graph matching is introduced. Using this framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is introduced. The algorithm uses 'typicality matching' and techniques from point-to-point communications for reliable matching. Assuming an Erdös-Renyi model on the correlated graph pair, it is shown that successful matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between the edge variables in the two graphs.

AB - In this paper, a new information theoretic framework for graph matching is introduced. Using this framework, the graph isomorphism and seeded graph matching problems are studied. The maximum degree algorithm for graph isomorphism is analyzed and sufficient conditions for successful matching are rederived using type analysis. Furthermore, a new seeded matching algorithm with polynomial time complexity is introduced. The algorithm uses 'typicality matching' and techniques from point-to-point communications for reliable matching. Assuming an Erdös-Renyi model on the correlated graph pair, it is shown that successful matching is guaranteed when the number of seeds grows logarithmically with the number of vertices in the graphs. The logarithmic coefficient is shown to be inversely proportional to the mutual information between the edge variables in the two graphs.

UR - http://www.scopus.com/inward/record.url?scp=85050963697&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85050963697&partnerID=8YFLogxK

U2 - 10.1109/ACSSC.2017.8335178

DO - 10.1109/ACSSC.2017.8335178

M3 - Conference contribution

AN - SCOPUS:85050963697

T3 - Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017

SP - 253

EP - 257

BT - Conference Record of 51st Asilomar Conference on Signals, Systems and Computers, ACSSC 2017

A2 - Matthews, Michael B.

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 29 October 2017 through 1 November 2017

ER -

Seeded graph matching: Efficient algorithms and theoretical guarantees

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this