On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909134186610688 |
|---|---|
| author | Wang, Ziao Zhang, Ning Wang, Weina Wang, Lele |
| author_facet | Wang, Ziao Zhang, Ning Wang, Weina Wang, Lele |
| contents | Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős--Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_10106 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment Wang, Ziao Zhang, Ning Wang, Weina Wang, Lele Data Structures and Algorithms Information Theory Graph alignment aims at finding the vertex correspondence between two correlated graphs, a task that frequently occurs in graph mining applications such as social network analysis. Attributed graph alignment is a variant of graph alignment, in which publicly available side information or attributes are exploited to assist graph alignment. Existing studies on attributed graph alignment focus on either theoretical performance without computational constraints or empirical performance of efficient algorithms. This motivates us to investigate efficient algorithms with theoretical performance guarantee. In this paper, we propose two polynomial-time algorithms that exactly recover the vertex correspondence with high probability. The feasible region of the proposed algorithms is near optimal compared to the information-theoretic limits. When specialized to the seeded graph alignment problem under the seeded Erdős--Rényi graph pair model, the proposed algorithms extends the best known feasible region for exact alignment by polynomial-time algorithms. |
| title | On the Feasible Region of Efficient Algorithms for Attributed Graph Alignment |
| topic | Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2201.10106 |