Skip to main content
Cornell University
We gratefully acknowledge support from the Simons Foundation, member institutions, and all contributors. Donate
arxiv logo > cs > arXiv:2102.00665

Help | Advanced Search

Computer Science > Information Theory

(cs)
[Submitted on 1 Feb 2021 (v1), last revised 11 Mar 2024 (this version, v4)]

Title:Attributed Graph Alignment

Authors:Ning Zhang, Ziao Wang, Weina Wang, Lele Wang
Download a PDF of the paper titled Attributed Graph Alignment, by Ning Zhang and 2 other authors
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.
Subjects: Information Theory (cs.IT)
Cite as: arXiv:2102.00665 [cs.IT]
  (or arXiv:2102.00665v4 [cs.IT] for this version)
  https://doi.org/10.48550/arXiv.2102.00665
arXiv-issued DOI via DataCite

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)
Full-text links:

Access Paper:

    Download a PDF of the paper titled Attributed Graph Alignment, by Ning Zhang and 2 other authors
  • Download PDF
  • HTML (experimental)
  • TeX Source
  • Other Formats
license icon view license
Current browse context:
cs.IT
< prev   |   next >
new | recent | 2102
Change to browse by:
cs
math
math.IT

References & Citations

  • NASA ADS
  • Google Scholar
  • Semantic Scholar

DBLP - CS Bibliography

listing | bibtex
Ning Zhang
Weina Wang
Lele Wang
a export BibTeX citation Loading...

Bookmark

BibSonomy logo Reddit logo

Bibliographic and Citation Tools

Bibliographic Explorer (What is the Explorer?)
Litmaps (What is Litmaps?)
scite Smart Citations (What are Smart Citations?)
Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)
  • About
  • Help
  • contact arXivClick here to contact arXiv Contact
  • subscribe to arXiv mailingsClick here to subscribe Subscribe
  • Copyright
  • Privacy Policy
  • Web Accessibility Assistance
  • arXiv Operational Status
    Get status notifications via email or slack