TY - GEN
T1 - On Graph Matching Using Generalized Seed Side-Information
AU - Shariatnasab, Mahshad
AU - Shirani, Farhad
AU - Garg, Siddharth
AU - Erkip, Elza
N1 - 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 -