Contextual Graph Matching with Correlated Gaussian Features
We investigate contextual graph matching in the Gaussian setting, where both edge weights and node features are correlated across two networks. We derive precise information-theoretic thresholds for exact recovery, and identify conditions under which almost exact recovery is possible or impossible, in terms of graph and feature correlation strengths, the number of nodes, and feature dimension. Interestingly, whereas an all-or-nothing phase transition is observed in the standard graph-matching scenario, the additional contextual information introduces a richer structure: thresholds for exact and almost exact recovery no longer coincide. Our results provide the first rigorous characterization of how structural and contextual information interact in graph matching, and establish a benchmark for designing efficient algorithms.
Code (0)
등록된 구현이 없습니다.
Tasks
Graph MatchingSimilar Papers 제목 키워드 기반
Exact Matching in Correlated Networks with Node Attributes for Improved Community Recovery
We study community detection in multiple networks whose nodes and edges are jointly correlated. This setting arises naturally in applications such as social platforms, where a shared set of users may exhibit both correla…
AttributeCommunity DetectionGraph MatchingStochastic Block ModelA polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
Motivated by the problem of matching vertices in two correlated Erd\H{o}s-R\'enyi graphs, we study the problem of matching two correlated Gaussian Wigner matrices. We propose an iterative matching algorithm, which succee…
Graph MatchingSeeded graph matching for the correlated Gaussian Wigner model via the projected power method
In the \emph{graph matching} problem we observe two graphs $G,H$ and the goal is to find an assignment (or matching) between their vertices such that some measure of edge agreement is maximized. We assume in this work th…
Graph MatchingThe Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation. Specifically, given an unknown per…
Gaussian Database Alignment and Gaussian Planted Matching
Database alignment is a variant of the graph alignment problem: Given a pair of anonymized databases containing separate yet correlated features for a set of users, the problem is to identify the correspondence between t…