TY - GEN

T1 - On Graph Matching Using Generalized Seed Side-Information

AU - Shariatnasab, Mahshad

AU - Shirani, Farhad

AU - Garg, Siddharth

AU - Erkip, Elza

N1 - Funding Information:
This work is supported by ND EPSCoR grant FAR0033968, NYU WIRELESS Industrial Affiliates and National Science Foundation grant CCF-1815821.
Publisher Copyright:
© 2021 IEEE.

PY - 2021/7/12

Y1 - 2021/7/12

N2 - In this paper, matching pairs of stocahstically generated graphs in the presence of generalized seed side-information is considered. The graph matching problem emerges naturally in various applications such as social network de-anonymization, image processing, DNA sequencing, and natural language processing. A pair of randomly generated labeled Erdös-Rényi graphs with pairwise correlated edges are considered. It is assumed that the matching strategy has access to the labeling of the vertices in the first graph, as well as a collection of shortlists - called ambiguity sets - of possible labels for the vertices of the second graph. The objective is to leverage the correlation among the edges of the graphs along with the side-information provided in the form of ambiguity sets to recover the labels of the vertices in the second graph. This scenario can be viewed as a generalization of the seeded graph matching problem, where the ambiguity sets take a specific form such that the exact labels for a subset of vertices in the second graph are known prior to matching. A matching strategy is proposed which operates by evaluating the joint typicality of the adjacency matrices of the graphs. Sufficient conditions on the edge statistics as well as ambiguity set statistics are derived under which the proposed matching strategy successfully recovers the labels of the vertices in the second graph. Additionally, Fano-type arguments are used to derive necessary conditions for successful seeded graph matching.

AB - In this paper, matching pairs of stocahstically generated graphs in the presence of generalized seed side-information is considered. The graph matching problem emerges naturally in various applications such as social network de-anonymization, image processing, DNA sequencing, and natural language processing. A pair of randomly generated labeled Erdös-Rényi graphs with pairwise correlated edges are considered. It is assumed that the matching strategy has access to the labeling of the vertices in the first graph, as well as a collection of shortlists - called ambiguity sets - of possible labels for the vertices of the second graph. The objective is to leverage the correlation among the edges of the graphs along with the side-information provided in the form of ambiguity sets to recover the labels of the vertices in the second graph. This scenario can be viewed as a generalization of the seeded graph matching problem, where the ambiguity sets take a specific form such that the exact labels for a subset of vertices in the second graph are known prior to matching. A matching strategy is proposed which operates by evaluating the joint typicality of the adjacency matrices of the graphs. Sufficient conditions on the edge statistics as well as ambiguity set statistics are derived under which the proposed matching strategy successfully recovers the labels of the vertices in the second graph. Additionally, Fano-type arguments are used to derive necessary conditions for successful seeded graph matching.

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

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

U2 - 10.1109/ISIT45174.2021.9518130

DO - 10.1109/ISIT45174.2021.9518130

M3 - Conference contribution

AN - SCOPUS:85115097506

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2726

EP - 2731

BT - 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2021 IEEE International Symposium on Information Theory, ISIT 2021

Y2 - 12 July 2021 through 20 July 2021

ER -