Computer Science > Information Theory
[Submitted on 1 Feb 2021 (v1), last revised 11 Mar 2024 (this version, v4)]
Title:Attributed Graph Alignment
Download PDF HTML (experimental)Abstract:Motivated by various data science applications including de-anonymizing user identities in social networks, we consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this paper, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish both the achievability and converse results on recovering vertex correspondence exactly, where the conditions match for certain parameter regimes. Our results span the full spectrum between models that only consider user-user connections and models where only attribute information is available.
Submission history
From: Ziao Wang [view email][v1] Mon, 1 Feb 2021 06:57:20 UTC (30 KB)
[v2] Mon, 15 Mar 2021 08:36:14 UTC (65 KB)
[v3] Thu, 2 Mar 2023 23:30:48 UTC (790 KB)
[v4] Mon, 11 Mar 2024 18:22:48 UTC (218 KB)
Current browse context:
cs.IT
References & Citations
Bibliographic and Citation Tools
Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)