Exact Graph Matching in Correlated Gaussian-Attributed Erdős-Rényi Model
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917725053386752 |
|---|---|
| author | Yang, Joonhyuk Chung, Hye Won |
| author_facet | Yang, Joonhyuk Chung, Hye Won |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_12604 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact Graph Matching in Correlated Gaussian-Attributed Erdős-Rényi Model Yang, Joonhyuk Chung, Hye Won Information Theory Data Structures and Algorithms Social and Information Networks 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. |
| title | Exact Graph Matching in Correlated Gaussian-Attributed Erdős-Rényi Model |
| topic | Information Theory Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2407.12604 |