The graph alignment problem: fundamental limits and efficient algorithms
This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves most of the edges. Focusing on the planted version where the graphs are random, we are interested in understanding the fundamental information-theoretical limits for this problem, as well as designing and analyzing algorithms that are able to recover the underlying alignment in the data. For these algorithms, we give some high probability guarantees on the regime in which they succeed or fail.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Fundamental Limits in Multi-image Alignment
The performance of multi-image alignment, bringing different images into one coordinate system, is critical in many applications with varied signal-to-noise ratio (SNR) conditions. A great amount of effort is being inves…
Image RegistrationThe Edge Density Barrier: Computational-Statistical Tradeoffs in Combinatorial Inference
We study the hypothesis testing problem of inferring the existence of combinatorial structures in undirected graphical models. Although there exist extensive studies on the information-theoretic limits of this probl…
Two-sample testingMinimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, comm…
Community DetectionGraphon EstimationTwo-sample testingFundamental Limits of Prediction, Generalization, and Recursion: An Entropic-Innovations Perspective
In this paper, we examine the fundamental performance limits of prediction, with or without side information. More specifically, we derive generic lower bounds on the $\mathcal{L}_p$ norms of the prediction errors that a…
PredictionvalidOn the Fundamental Limits of Exact Inference in Structured Prediction
Inference is a main task in structured prediction and it is naturally modeled with a graph. In the context of Markov random fields, noisy observations corresponding to nodes and edges are usually involved, and the goal o…
Computational EfficiencyStructured Prediction