Résumé Technique : F-Clustering Hiérarchique : Approximation et Dureté

1. Définition du Problème

L'article introduit le F-Clustering Hiérarchique (HC-F), une généralisation du problème classique de clustering hiérarchique. Dans le clustering hiérarchique standard, un ensemble de données (représenté par un graphe pondéré $G$) est partitionné de manière récursive jusqu'à ce que chaque cluster soit un singleton. La qualité d'une solution est mesurée par l'objectif de Dasgupta, qui pénalise la coupure d'arêtes à forte similitude tôt dans la hiérarchie (c'est-à-dire lorsque la taille du cluster est grande).

Dans la variante HC-F, le processus récursif est autorisé à se terminer dès qu'un cluster appartient à une classe de graphes spécifique $\mathcal{F}$. L'objectif reste de minimiser l'objectif de Dasgupta, mais les nœuds feuilles de l'arbre de clustering résultant doivent être des graphes appartenant à $\mathcal{F}$ plutôt que des singletons. Les auteurs se concentrent sur deux choix naturels pour $\mathcal{F}$ :

1. Arbres ($\mathcal{T}$) : Des clusters qui sont acycliques.
2. Graphes à diamètre borné ($\mathcal{D}_d$) : Des clusters où le diamètre (la distance maximale entre deux nœuds quelconques) est au plus $d$.

L'article suppose que $\mathcal{F}$ est une classe non vide, close sous les sous-graphes et reconnaissable en temps polynomial.

2. Méthodologie et Cadre

Les auteurs proposent un cadre général pour approximer le HC-F pour des classes de graphes qu'ils nomment $\alpha(n)$-bien comportementales. La méthodologie centrale repose sur une technique de « lissage » (flattening), décomposant le problème hiérarchique en une séquence de problèmes de partitionnement « plats », guidée par la programmation linéaire (LP).

2.1 La condition $\alpha(n)$-bien comportementale

Une classe de graphes $\mathcal{F}$ est $\alpha(n)$-bien comportementale si le problème associé de $p\mathcal{F}$-Partitioning ($p\mathcal{F}$-P) admet :

1. Une formulation naturelle en programmation linéaire en nombres entiers (ILP) utilisant des variables de coupe d'arêtes.
2. Des contraintes encodées sous forme de contraintes de type « couverture » (par exemple, $\sum_{e \in R} y_e \geq 1$) qui garantissent qu'un prédicat structurel $p_\mathcal{F}$ est satisfait pour un ensemble de terminaux.
3. Une relaxation LP solvable en temps polynomial.
4. Un algorithme d'arrondi qui, étant donné une solution LP, produit une coupe valide avec un coût au plus $\alpha(n)$ fois le coût de la LP.

Les exemples de $p\mathcal{F}$-P incluent :

• Feedback Edge Set (FES) : Supprimer des arêtes pour briser les cycles à travers des terminaux (pertinent pour les Arbres).
• Min-Multicut (MMC) : Déconnecter des paires spécifiques de terminaux (pertinent pour le Diamètre Borné).
• $\rho$-Séparateur : Partitionner le graphe de sorte que les composantes contenant des terminaux aient un poids borné.

2.1 Le Cadre Algorithmique

L'algorithme procède en deux phases principales :

Phase 1 : Prétraitement et Relaxation LP
Les auteurs construisent un ILP (ILP-HC-F) qui encode la structure hiérarchique en utilisant des variables basées sur les niveaux.

• Les variables $y^t_e$ indiquent si l'arête $e$ est coupée au niveau $t$ (où les niveaux correspondent aux poids des clusters).
• Les variables $x^t_v$ indiquent si le sommet $v$ satisfait le prédicat $\mathcal{F}$ au niveau $t$.
• La formulation inclut des contraintes de métriques d'étalement (adaptées de Charikar et Chatziafratis) pour assurer que les clusters sont suffisamment séparés, ainsi que des contraintes de raffinement pour maintenir la structure hiérarchique.
• L'ILP est relaxée en une LP (LP-HC-F) et résolue. Une procédure d'arrondi définit $x^t_v = 1$ si $x^t_v \geq 1/2$ et multiplie les variables d'arêtes $y^t_e$ par 2, produisant une solution partiellement intégrale.

Phase 2 : Construction Récursive
L'algorithme construit l'arbre de clustering de haut en bas :

1. Pour un cluster actuel $H$, il identifie les sommets qui satisfont le prédicat $\mathcal{F}$ ($X_1$) et ceux qui ne le satisfont pas ($X_0$) à un niveau spécifique $t = w(H)/2$.
2. Coupe 1 ($E_F$) : Il utilise la solution LP restreinte à $X_1$ comme guide pour le problème $p\mathcal{F}$-P. Un algorithme d'approximation $\alpha(n)$ pour $p\mathcal{F}$-P est exécuté pour couper les arêtes, garantissant que les sommets dans $X_1$ satisfont le prédicat.
3. Coupe 2 ($E_\rho$) : Il utilise la solution LP restreinte à $X_0$ comme guide pour le problème du $\rho$-Séparateur (avec $\rho=1/2$). Un algorithme d'approximation bicritère (avec un ratio $\beta(n) = O(\log n)$) coupe les arêtes pour garantir que les composantes restantes sont suffisamment petites (poids $\leq 2/3$ du parent).
4. L'union des coupes partitionne $H$ en composantes plus petites, qui sont traitées de manière récursive.

3. Résultats Clés

3.1 Algorithmes d'Approximation

Le théorème principal stipule que si $\mathcal{F}$ est $\alpha(n)$-bien comportementale, il existe un algorithme d'approximation $O(\alpha(n) + \beta(n))$ pour HC-F, où $\beta(n) = O(\log n)$ est le ratio d'approximation pour le problème du $\rho$-Séparateur.

Application à ces classes spécifiques :

• Hierarchical Tree Clustering (HC-$\mathcal{T}$) : Puisque le problème Feedback Edge Set admet une approximation $O(\log n \cdot \log \log n)$ via l'arrondi LP, les auteurs obtiennent une approximation $O(\log n \cdot \log \log n)$ pour HC-$\mathcal{T}$.
• Hierarchical Bounded Diameter Clustering (HC-$\mathcal{D}_d$) : Puisque le problème Min-Multicut admet une approximation $O(\log n)$, les auteurs obtiennent une approximation $O(\log n)$ pour HC-$\mathcal{D}_d$.

Ces résultats sont présentés comme les premiers algorithmes d'approximation en temps polynomial pour ces variantes spécifiques de HC-F.

3.2 Dureté de l'Approximation

L'article établit des résultats de dureté d'approximation forts sous l'hypothèse de l'expansion des petits ensembles (Small Set Expansion Hypothesis - SSEH) :

• HC-$\mathcal{T}$ et HC-$\mathcal{D}_d$ ne peuvent pas être approximés par un facteur constant.
• La preuve implique une réduction boîte noire de l'inapproximabilité du clustering hiérarchique classique.
  • Pour HC-$\mathcal{D}_d$, la réduction attache des gadgets de diamètre $d$ à chaque sommet, forçant l'algorithme à traiter le gadget comme un représentant du sommet original.
  • Pour HC-$\mathcal{T}$, la réduction attache des triangles aux sommets. Les auteurs exploitent la propriété selon laquelle le coût de l'optimal Hierarchical Clustering est minoré par le coût du Minimum Linear Arrangement (MLA), montrant que cette borne inférieure tient également pour les instances construites.

4. Signification et Revendications

L'article affirme fournir les premiers résultats algorithmiques pour le problème de F-Clustering Hiérarchique. Sa contribution principale est un cadre général qui unifie l'approximation du clustering hiérarchique dans diverses classes structurelles, à condition que ces classes satisfassent la condition $\alpha(n)$-bien comportementale.

Les auteurs soulignent que leur approche n'est pas limitée aux arbres ou aux graphes à diamètre borné, mais s'applique à toute classe où le problème de partitionnement plat correspondant (comme le Multiway Cut) admet une formulation ILP naturelle avec des garanties d'arrondi prouvables. Ils notent que l'amélioration de ces ratios d'approximation au-delà du facteur $O(\log n)$ nécessiterait probablement des percées dans l'approximation des problèmes fondamentaux de coupe et de séparateur (comme le Sparsest Cut ou le Multicut), qui sont actuellement considérés comme difficiles à améliorer.

Le travail met également en évidence des motivations pratiques, telles que le besoin de structures de clustering qui s'arrêtent à des composantes « simples » (comme les répertoires dans les systèmes de fichiers ou les catégories de produits dans l'e-commerce) plutôt que de forcer tous les clusters à être des singletons, permettant ainsi d'encoder des niveaux de granularité significatifs.