Mining structure overlaps for efficient graph compression

Several graph compression approaches rely on finding dense structures such as cliques or quasi-cliques which are simple to encode, i.e., they are defined by the set of their vertices. The graph is then encoded by its structures. However, existing methods consider these structures at a high level ignoring overlaps. This leads to encoding multiple times the overlapping parts of the considered structures, which is redundant. To deal with this issue, we propose to dig deep into the structures, to identify these overlappings so as to avoid redundant encoding. Hence, we develop algorithms to construct highly compressed graph representations. We tested our algorithms on several graph datasets, and our results outperform state of the art methods.