Back to search

University of British Columbia

On the information-theoretic limits of attributed graph alignment

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Ning
Contributors dc:contributor
  • Wang, Lele

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/82555

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Zhang, Ning. On the information-theoretic limits of attributed graph alignment. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/82555