AI in EE

AI IN DIVISIONS

AI in Communication Division

AI in EE

AI IN DIVISIONS

AI in Communication Division ​

AI in Communication Division

Exact Graph Matching in Correlated Gaussian-Attributed Erdos-Renyi Model, IEEE International Symposium on Information Theory (ISIT), July 2024. (정혜원 교수 연구실)

Title: Exact Graph Matching in Correlated Gaussian-Attributed Erdos-Renyi Model 

Authors: Joonhyuk Yang and Hye Won Chung

Conference: IEEE International Symposium on Information Theory (ISIT), July 2024. 

Abstract: Graph matching problem aims to identify node correspondence between two or more correlated graphs. Previous studies have primarily focused on models where only edge information is provided. However, in many social networks, not only the relationships between users, represented by edges, but also their personal information, represented by features, are present. In this paper, we address the challenge of identifying node correspondence in correlated graphs, where additional node features exist, as in many real-world settings. We propose a two-step procedure, where we initially match a subset of nodes only using edge information, and then match the remaining nodes using node features. We derive information-theoretic limits for exact graph matching on this model. Our approach provides a comprehensive solution to the real-world graph matching problem by providing systematic ways to utilize both edge and node information for exact matching of the graphs.

Main figure:

1