TY - GEN
T1 - Typicality Matching for Pairs of Correlated Graphs
AU - Shirani, Farhad
AU - Garg, Siddharth
AU - Erkip, Elza
N1 - Funding Information:
This research was supported in part by NSF grant CNS-1553419.
Funding Information:
This research was supported in part by NSF grant CNS-1553419
Publisher Copyright:
© 2018 IEEE.
PY - 2018/8/15
Y1 - 2018/8/15
N2 - In this paper, the problem of matching pairs of correlated random graphs with multi-valued edge attributes is considered. Graph matching problems of this nature arise in several settings of practical interest including social network de-anonymization, study of biological data, and web graphs. An achievable region of graph parameters for successful matching is derived by analyzing a new matching algorithm that we refer to as typicality matching. The algorithm operates by investigating the joint typicality of the adjacency matrices of the two correlated graphs. Our main result shows that the achievable region depends on the mutual information between the variables corresponding to the edge probabilities of the two graphs. The result is based on bounds on the typicality of permutations of sequences of random variables that might be of independent interest.
AB - In this paper, the problem of matching pairs of correlated random graphs with multi-valued edge attributes is considered. Graph matching problems of this nature arise in several settings of practical interest including social network de-anonymization, study of biological data, and web graphs. An achievable region of graph parameters for successful matching is derived by analyzing a new matching algorithm that we refer to as typicality matching. The algorithm operates by investigating the joint typicality of the adjacency matrices of the two correlated graphs. Our main result shows that the achievable region depends on the mutual information between the variables corresponding to the edge probabilities of the two graphs. The result is based on bounds on the typicality of permutations of sequences of random variables that might be of independent interest.
UR - http://www.scopus.com/inward/record.url?scp=85052458493&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052458493&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2018.8437567
DO - 10.1109/ISIT.2018.8437567
M3 - Conference contribution
AN - SCOPUS:85052458493
SN - 9781538647806
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 221
EP - 225
BT - 2018 IEEE International Symposium on Information Theory, ISIT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE International Symposium on Information Theory, ISIT 2018
Y2 - 17 June 2018 through 22 June 2018
ER -