University of British Columbia
Statistical inference on structured data : sequences and graphs
Abstract
dc:descriptionIn 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