The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913982613291008 |
|---|---|
| author | Lu, Qiheng Sidiropoulos, Nicholas D. Konar, Aritra |
| author_facet | Lu, Qiheng Sidiropoulos, Nicholas D. Konar, Aritra |
| contents | Dense subgraph mining is a fundamental technique in graph mining, commonly applied in fraud detection, community detection, product recommendation, and document summarization. In such applications, we are often interested in identifying communities, recommendations, or summaries that reflect different constituencies, styles or genres, and points of view. For this task, we introduce a new variant of the Densest $k$-Subgraph (D$k$S) problem that incorporates the attribute values of vertices. The proposed Vertex-Attribute-Constrained Densest $k$-Subgraph (VAC-D$k$S) problem retains the NP-hardness and inapproximability properties of the classical D$k$S. Nevertheless, we prove that a suitable continuous relaxation of VAC-D$k$S is tight and can be efficiently tackled using a projection-free Frank--Wolfe algorithm. We also present an insightful analysis of the optimization landscape of the relaxed problem. Extensive experimental results demonstrate the effectiveness of our proposed formulation and algorithm, and its ability to scale up to large graphs. We further elucidate the properties of VAC-D$k$S versus classical D$k$S in a political network mining application, where VAC-D$k$S identifies a balanced and more meaningful set of politicians representing different ideological camps, in contrast to the classical D$k$S solution which is unbalanced and rather mundane. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_06655 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem Lu, Qiheng Sidiropoulos, Nicholas D. Konar, Aritra Social and Information Networks Data Structures and Algorithms Dense subgraph mining is a fundamental technique in graph mining, commonly applied in fraud detection, community detection, product recommendation, and document summarization. In such applications, we are often interested in identifying communities, recommendations, or summaries that reflect different constituencies, styles or genres, and points of view. For this task, we introduce a new variant of the Densest $k$-Subgraph (D$k$S) problem that incorporates the attribute values of vertices. The proposed Vertex-Attribute-Constrained Densest $k$-Subgraph (VAC-D$k$S) problem retains the NP-hardness and inapproximability properties of the classical D$k$S. Nevertheless, we prove that a suitable continuous relaxation of VAC-D$k$S is tight and can be efficiently tackled using a projection-free Frank--Wolfe algorithm. We also present an insightful analysis of the optimization landscape of the relaxed problem. Extensive experimental results demonstrate the effectiveness of our proposed formulation and algorithm, and its ability to scale up to large graphs. We further elucidate the properties of VAC-D$k$S versus classical D$k$S in a political network mining application, where VAC-D$k$S identifies a balanced and more meaningful set of politicians representing different ideological camps, in contrast to the classical D$k$S solution which is unbalanced and rather mundane. |
| title | The Vertex-Attribute-Constrained Densest $k$-Subgraph Problem |
| topic | Social and Information Networks Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.06655 |