Title: On seeded subgraph-to-subgraph matching: The ssSGM Algorithm and matchability information theory Show Chinese title

Title: 关于有种子的子图到子图匹配：ssSGM 算法与可匹配性信息理论

Abstract: The subgraph-subgraph matching problem is, given a pair of graphs and a positive integer $K$, to find $K$ vertices in the first graph, $K$ vertices in the second graph, and a bijection between them, so as to minimize the number of adjacency disagreements across the bijection; it is ``seeded" if some of this bijection is fixed. The problem is intractable, and we present the ssSGM algorithm, which uses Frank-Wolfe methodology to efficiently find an approximate solution. Then, in the context of a generalized correlated random Bernoulli graph model, in which the pair of graphs naturally have a core of $K$ matched pairs of vertices, we provide and prove mild conditions for the subgraph-subgraph matching problem solution to almost always be the correct $K$ matched pairs of vertices. Show Chinese abstract

Abstract: 子图-子图匹配问题，给定一对图和一个正整数$K$，找到第一个图中的$K$个顶点，第二个图中的$K$个顶点，并在它们之间建立双射，以最小化双射中的邻接不一致数量；如果该双射的某些部分是固定的，则称为“带种子”的问题。 该问题难以处理，我们提出了 ssSGM 算法，该算法使用 Frank-Wolfe 方法来高效地找到近似解。 然后，在一种广义的相关随机伯努利图模型的背景下，其中这对图自然具有$K$个匹配的顶点对的核心，我们提供了并证明了子图-子图匹配问题解几乎总是正确的$K$个匹配顶点对的温和条件。