Mining Contrasting Quasi-Clique Patterns
This work addresses the need for extracting knowledge from sparsity in multi-graph data, such as social networks or collaboration graphs, though it appears incremental by extending existing quasi-clique mining to include contrasting patterns.
The paper tackles the problem of mining dense quasi-cliques in multi-graph scenarios by introducing contrasting quasi-clique patterns, which identify vertices that are highly dense in one graph but sparse in another, and proposes an algorithm that efficiently computes these patterns, demonstrating its effectiveness on synthetic and real-world datasets.
Mining dense quasi-cliques is a well-known clustering task with applications ranging from social networks over collaboration graphs to document analysis. Recent work has extended this task to multiple graphs; i.e. the goal is to find groups of vertices highly dense among multiple graphs. In this paper, we argue that in a multi-graph scenario the sparsity is valuable for knowledge extraction as well. We introduce the concept of contrasting quasi-clique patterns: a collection of vertices highly dense in one graph but highly sparse (i.e. less connected) in a second graph. Thus, these patterns specifically highlight the difference/contrast between the considered graphs. Based on our novel model, we propose an algorithm that enables fast computation of contrasting patterns by exploiting intelligent traversal and pruning techniques. We showcase the potential of contrasting patterns on a variety of synthetic and real-world datasets.