The Open Collections website will be undergoing maintenance on Wednesday December 7th from 9pm to 11pm PST. The site may be temporarily unavailable during this time.

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On the information-theoretic limits of attributed graph alignment Zhang, Ning


Graph alignment aims at recovering the vertex correspondence between two correlated graphs, which is a task that frequently occurs in graph mining applications such as social network analysis, computational biology, etc. Existing studies on graph alignment mostly identify the vertex correspondence by exploiting the graph structure similarity. However, in many real-world applications, additional information attached to individual vertices, such as the user profiles in social networks, might be publicly available. In this thesis, we consider the attributed graph alignment problem, where additional information attached to individuals, 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 a wide range of practical regimes. Our results span the full spectrum between models that only consider graph structure similarity and models where only attribute information is available.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International