On Densest $k$-Subgraph Mining and Diagonal Loading
<|reference_start|>On Densest $k$-Subgraph Mining and Diagonal Loading: The Densest $k$-Subgraph (D$k$S) problem aims to find a subgraph comprising $k$ vertices with the maximum number of edges between them. A continuous reformulation of the binary quadratic D$k$S problem is considered, which incorporates a diagonal loading term. It is shown that this non-convex, continuous relaxation is tight for a range of diagonal loading parameters, and the impact of the diagonal loading parameter on the optimization landscape is studied. On the algorithmic side, two projection-free algorithms are proposed to tackle the relaxed problem, based on Frank-Wolfe and explicit constraint parametrization, respectively. Experiments suggest that both algorithms have merits relative to the state-of-art, while the Frank-Wolfe-based algorithm stands out in terms of subgraph density, computational complexity, and ability to scale up to very large datasets.<|reference_end|>
@article{lu2024on,
    title={On Densest $k$-Subgraph Mining and Diagonal Loading},
    author={Qiheng Lu, Nicholas D. Sidiropoulos, Aritra Konar},
    journal={arXiv preprint arXiv:2410.07388},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.07388},
    primaryClass={cs.SI cs.DS}
}