标题： 信息理论极限上的精确子图对齐问题 显示英文标题

标题： Information-Theoretic Limits on Exact Subgraph Alignment Problem

摘要： 图对齐问题旨在识别两个相关图之间的顶点对应关系。 大多数现有研究集中在两个图共享相同顶点集的场景中。 然而，在许多现实世界的应用中，例如计算机视觉、社交网络分析和生物信息学中，任务通常涉及在较大的图中定位一个小的图模式。 现有的图对齐算法和分析无法直接处理这些场景，因为它们不是为识别小图模式位于较大图中的特定顶点子集而设计的。 受这一限制的启发，我们引入了子图对齐问题，该问题旨在恢复嵌入在较大图中的小图模式的顶点集和/或顶点对应关系。 在特殊情况下，当小图模式是较大图的诱导子图，并且要恢复顶点集和对应关系时，该问题简化为子图同构问题，这在最坏情况下是NP难的。 在本文中，我们通过提出Erdos-Renyi子图对模型以及一些适当的恢复准则，正式制定了子图对齐问题。 然后，我们建立了子图对齐问题的几乎紧密的信息理论结果，并提出了某些新颖的分析方法。 显示英文摘要

摘要： The graph alignment problem aims to identify the vertex correspondence between two correlated graphs. Most existing studies focus on the scenario in which the two graphs share the same vertex set. However, in many real-world applications, such as computer vision, social network analysis, and bioinformatics, the task often involves locating a small graph pattern within a larger graph. Existing graph alignment algorithms and analysis cannot directly address these scenarios because they are not designed to identify the specific subset of vertices where the small graph pattern resides within the larger graph. Motivated by this limitation, we introduce the subgraph alignment problem, which seeks to recover both the vertex set and/or the vertex correspondence of a small graph pattern embedded in a larger graph. In the special case where the small graph pattern is an induced subgraph of the larger graph and both the vertex set and correspondence are to be recovered, the problem reduces to the subgraph isomorphism problem, which is NP-complete in the worst case. In this paper, we formally formulate the subgraph alignment problem by proposing the Erdos-Renyi subgraph pair model together with some appropriate recovery criterion. We then establish almost-tight information-theoretic results for the subgraph alignment problem and present some novel approaches for the analysis.