On Seeded Subgraph-to-Subgraph Matching: The ssSGM Algorithm and Matchability Information Theory
研究子图到子图匹配问题，提出ssSGM算法高效求解，并在广义相关随机伯努利图模型下给出匹配几乎总是正确的温和条件。
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.