Back to search

University of British Columbia

Statistical inference on structured data : sequences and graphs

Abstract

dc:description

In the era of big data, structured data, such as sequences and graphs, have become central to various scientific and engineering disciplines. This dissertation explores statistical inference techniques tailored to these complex data structures, focusing on the development of novel methodologies that address the challenges posed by sequences and graphs. The first part of the dissertation addresses the inference of sequences, with a particular focus on the noisy computing problem. We investigate several fundamental computing tasks under an active learning setting, including finding the total ordering or the largest element of a real sequence through noisy pairwise comparisons and determining whether the weight of a binary sequence exceeds a certain threshold based on noisy bit readings. To characterize optimal query complexity, we propose novel query strategies and develop statistical lower bounds, which tighten the existing bounds for all these problems. The second part of the dissertation studies the inference on graphs, specifically focusing on the graph alignment problem. Graph alignment refers to the task of finding the vertex correspondence between two correlated graphs. We explore a variant of this problem known as attributed graph alignment, where additional attribute information is leveraged to aid the alignment process. We propose new polynomial-time algorithms for this problem and provide a theoretical analysis of their performance. Our results demonstrate that these algorithms can successfully identify the correct vertex correspondence under a weak correlation between the two graphs.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Wang, Ziao
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/89883

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

Wang, Ziao. Statistical inference on structured data : sequences and graphs. doctoral thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/89883