Large Scale Constrained Clustering With Reinforcement Learning

2024-02-15 · Benedikt Schesch, Marco Caserta

Given a network, allocating resources at clusters level, rather than at each node, enhances efficiency in resource allocation and usage. In this paper, we study the problem of finding fully connected disjoint clusters to minimize the intra-cluster distances and maximize the number of nodes assigned to the clusters, while also ensuring that no two nodes within a cluster exceed a threshold distance. While the problem can easily be formulated using a binary linear model, traditional combinatorial optimization solvers struggle when dealing with large-scale instances. We propose an approach to solve this constrained clustering problem via reinforcement learning. Our method involves training an agent to generate both feasible and (near) optimal solutions. The agent learns problem-specific heuristics, tailored to the instances encountered in this task. In the results section, we show that our algorithm finds near optimal solutions, even for large scale instances.

📄 PDF Abstract BibTeX arXiv:2402.10177

Code (0)

등록된 구현이 없습니다.

Tasks

ClusteringCombinatorial OptimizationConstrained Clusteringreinforcement-learning Reinforcement Learning

Constrained 1-Spectral Clustering

2015-05-24 · Syama Sundar Rangapuram, Matthias Hein

An important form of prior information in clustering comes in form of cannot-link and must-link constraints. We present a generalization of the popular spectral clustering technique which integrates such constraints. Mot…

All Clustering Form

Sub-Task Discovery with Limited Supervision: A Constrained Clustering Approach

2019-03-24 · ICLR Workshop LLD 2019 · Phillip Odom, Aaron Keech, Zsolt Kira

Hierarchical reinforcement learning captures sub-task information to learn modular policies that can be quickly adapted to new tasks. While hierarchies can be learned jointly with policies, this requires a lot of interac…

Clustering Constrained Clustering Hierarchical Reinforcement Learning reinforcement-learning+2

arXiv4TGC: Large-Scale Datasets for Temporal Graph Clustering

2023-06-08 · Meng Liu, Ke Liang, Yue Liu, Siwei Wang 외

Temporal graph clustering (TGC) is a crucial task in temporal graph learning. Its focus is on node clustering on temporal graphs, and it offers greater flexibility for large-scale graph structures due to the mechanism of…

Clustering Graph Clustering Graph Learning Node Clustering

A Scalable Global Optimization Algorithm For Constrained Clustering

2025-10-26 · Pedro Chumpitaz-Flores, My Duong, Cristobal Heredia, Kaixun Hua arxiv

Constrained clustering leverages limited domain knowledge to improve clustering performance and interpretability, but incorporating pairwise must-link and cannot-link constraints is an NP-hard challenge, making global op…

Kempe Swap K-Means: A Scalable Near-Optimal Solution for Semi-Supervised Clustering

2026-03-28 · Yuxuan Ren, Shijie Deng arxiv

This paper presents a novel centroid-based heuristic algorithm, termed Kempe Swap K-Means, for constrained clustering under rigid must-link (ML) and cannot-link (CL) constraints. The algorithm employs a dual-phase iterat…

Computational Efficiency