研究相关高斯特征下的图匹配，揭示结构与上下文信息的协同机制。
Contextual Graph Matching with Correlated Gaussian Features
- 基于相关高斯特征建模双图匹配问题
- 发现精确恢复与近似恢复的阈值不重合
- 为高效算法设计提供理论基准
我们研究高斯设定下的上下文图匹配问题，其中两个网络的边权重和节点特征均存在相关性。推导出精确恢复的信息论阈值，并根据图相关性强度、特征相关性强度、节点数量和特征维度，识别出几乎精确恢复可能或不可能的条件。有趣的是，尽管标准图匹配中存在全有或全无的相变现象，但引入额外上下文信息后，精确恢复与近似恢复的阈值不再一致。结果首次严格刻画了结构信息与上下文信息在图匹配中的交互作用，并为设计高效算法建立了基准。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。