Methods of finding the maximum common transitive subgraph: experimental comparison

Abstract

The problem of finding a maximum common subgraph (MCS) in a graph has broad applications in practical domains. However, certain scenarios require subgraphs with special properties, such as transitivity, that must be kept during building the subgraph. We formally define the concept of a transitive subgraph, investigate its properties. We study four different algorithms for finding the max imum common transitive subgraph (MCTS), compiled a list of tests aim at com paring graphs after making various changes and evaluated their accuracy and efficiency on a set of test cases. Benchmarking on 64 tests ranks the algorithms by scalability and accuracy: branch matching is the most scalable (> 1000 ver tices) and accurate (F1: 0.9907). MCS tree search is viable for graphs of up to ∼ 250 vertices (F1: 0.9752). Backtracking is limited to < 30 vertices (ac curacy: 0.5625), and brute-force is only feasible for graphs with ≤ 10 vertices, despite its high accuracy (0.9375). We discuss the advantages and disadvantages of each method, the test cases where each method demonstrates a non-optimal MCTS,identify the classes on which the methods work correctly and found that the branch matching method based on the longest common subsequence (LCS) algorithm performed the best.