A Fast Exact Algorithm to Enumerate Maximal Pseudo-cliques in Large Sparse Graphs

Pseudo-cliques (subgraphs with almost all possible edges) have many applications. But they do not satisfy the convertible antimonotone constraint (as we prove here). So, it is hard to reduce the search space of pseudo-cliques and list them efficiently. To our knowledge, only two exact algorithms, namely, ODES and PCE, were proposed for this purpose, but both have high execution times. Here, we present an exact algorithm named Fast Pseudo-Clique Enumerator (FPCE). It employs some pruning techniques we derived to reduce the search space. Our experiment on 15 real and 16 synthetic graphs shows that (i) on real graphs, FPCE is, on average, 38.6 and 6.5 times faster than ODES and PCE, respectively, whereas (ii) on synthetic graphs, FPCE is, on average, 39.7 and 3.1 times faster than ODES and PCE, respectively. We apply FPCE and a popular heuristic method on a PPI network to identify pseudo-cliques. FPCE outputs match with more known protein complexes, are more accurate, and are biologically more significant - suggesting that the exact computation of pseudo-cliques may give better insights. For its speed, FPCE is a suitable choice in such cases.