On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory

The subgraph-subgraph matching problem is, given a pair of graphs and a positive integer <i>K</i>, to find <i>K</i> vertices in the first graph, <i>K</i> 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 <i>K</i> matched pairs of vertices, we provide and prove mild conditions for the subgraph-subgraph matching problem solution to almost always be the correct <i>K</i> matched pairs of vertices.

子图-子图匹配（subgraph-subgraph matching）问题的定义为：给定一对图与一个正整数<i>K</i>，需在第一张图中选取<i>K</i>个顶点、第二张图中选取<i>K</i>个顶点，并构建二者之间的双射（bijection），以最小化该双射下的邻接不一致性数量；若该双射的部分映射关系已预先固定，则称该问题为“带种子的”子图-子图匹配问题。该问题属于难解问题，本文提出ssSGM算法，该算法借助弗兰克-沃尔夫方法（Frank-Wolfe methodology）高效求解近似解。随后，在广义相关随机伯努利图模型（generalized correlated random Bernoulli graph model）的框架下——此类模型中两张图天然存在<i>K</i>个匹配顶点对构成的核心结构——我们给出并证明了若干温和条件，使得在此条件下，子图-子图匹配问题的解几乎必然为正确的<i>K</i>个匹配顶点对。