Quasi-Clique Discovery via Energy Diffusion
This addresses the problem of quasi-clique discovery for applications like web spam detection and fraud screening, but it is incremental as it builds on existing graph mining techniques.
The paper tackles the problem of discovering quasi-cliques in large-scale web graphs, which is challenging due to sensitivity to random seeds and lack of edge-density guarantees. The result is EDQC, an energy diffusion-based method that finds larger quasi-cliques on most of 75 real-world datasets with lower variance and competitive runtime.
Discovering quasi-cliques -- subgraphs whose edge density exceeds a given threshold -- is a fundamental task in graph mining with applications to web spam detection, fraud screening, and e-commerce recommendation. However, existing methods for quasi-clique discovery on large-scale web graphs are often sensitive to random seeds or lack of explicit edge-density guarantees, making the task challenging in practice. This paper presents EDQC, an energy diffusion-based method for quasi-clique discovery. EDQC first employs an adaptive energy diffusion process to generate an energy ranking that highlights structurally cohesive regions. Guided by this energy ranking, the algorithm identifies a high-quality subgraph by minimizing conductance, a standard measure from community detection. This subgraph is then refined to meet the specified density threshold. Extensive experiments on 75 real-world graphs show that EDQC finds larger quasi-cliques on most datasets, with consistently lower variance across runs and competitive runtime. To the best of our knowledge, EDQC is the first method to incorporate energy diffusion into quasi-clique discovery.