Sintesi Tecnica: F-Clustering Gerarchico: Approssimazione e Hardness

1. Definizione del Problema

Il documento introduce il Hierarchical F-Clustering (HC-F), una generalizzazione del classico problema di Clustering Gerarchico. Nel clustering gerarchico standard, un dataset (rappresentato come un grafo pesato $G$) viene partizionato ricorsivamente finché ogni cluster non è un singleton. La qualità di una soluzione è misurata dall'obiettivo di Dasgupta, che penalizza il taglio di archi con alta similarità nelle fasi precoci della gerarchia (ovvero, quando la dimensione del cluster è grande).

Nella variante HC-F, il processo ricorsivo è autorizzato a terminare ogni volta che un cluster appartiene a una specifica classe di grafi $\mathcal{F}$. L'obiettivo rimane quello di minimizzare l'obiettivo di Dasgupta, ma i nodi foglia della gerarchia risultante devono essere grafi appartenenti a $\mathcal{F}$ anziché singleton. Gli autori si concentrano su due scelte naturali per $\mathcal{F}$:

1. Alberi ($\mathcal{T}$): Cluster che sono aciclici.
2. Grafi a Diametro Limitato ($\mathcal{D}_d$): Cluster in cui il diametro (la distanza massima tra due nodi qualsiasi) è al massimo $d$.

Il documento assume che $\mathcal{F}$ sia una classe non vuota, chiusa rispetto ai sottografi e riconoscibile in tempo polinomiale.

2. Metodologia e Framework

Gli autori propongono un framework generale per approssimare l'HC-F per classi di grafi che definiscono come $\alpha(n)$-ben comportate. La metodologia centrale si basa su una tecnica di "appiattimento" (flattening), che decompone il problema gerarchico in una sequenza di problemi di partizionamento "piatti", guidati dalla Programmazione Lineare (LP).

2.1 La Condizione $\alpha(n)$-Ben Comportata

Una classe di grafi $\mathcal{F}$ è $\alpha(n)$-ben comportata se il problema associato di $p\mathcal{F}$-Partitioning ($p\mathcal{F}$-P) ammette:

1. Una naturale formulazione di Programmazione Lineare Intera (ILP) utilizzando variabili di taglio degli archi.
2. Vincoli codificati come vincoli di "tipo cover" (ad esempio, $\sum_{e \in R} y_e \geq 1$) che garantiscono che un predicato strutturale $p_\mathcal{F}$ sia soddisfatto per un insieme di terminali.
3. Una rilassazione LP risolvibile in tempo polinomiale.
4. Un algoritmo di arrotondamento che, dato una soluzione LP, produce un taglio valido con un costo al massimo $\alpha(n)$ volte il costo della LP.

Esempi di $p\mathcal{F}$-P includono:

• Feedback Edge Set (FES): Rimozione di archi per rompere i cicli attraverso i terminali (rilevante per gli Alberi).
• Min-Multicut (MMC): Disconnessione di coppie specifiche di terminali (rilevante per il Diametro Limitato).
• $\rho$-Separator: Partizionamento del grafo in modo che i componenti contenenti i terminali abbiano un peso limitato.

2.1 Il Framework Algoritmico

L'algoritmo procede in due fasi principali:

Fase 1: Preprocessing e Rilassazione LP
Gli autori costruiscono un ILP (ILP-HC-F) che codifica la struttura gerarchica utilizzando variabili basate sui livelli.

• Le variabili $y^t_e$ indicano se l'arco $e$ viene tagliato al livello $t$ (dove i livelli corrispondono ai pesi dei cluster).
• Le variabili $x^t_v$ indicano se il vertice $v$ soddisfa il predicato $\mathcal{F}$ al livello $t$.
• La formulazione include vincoli di metriche di diffusione (adattati da Charikar e Chatziafratis) per garantire che i cluster siano sufficientemente separati e vincoli di raffinamento per mantenere la struttura gerarchica.
• L'ILP viene rilassato in una LP (LP-HC-F) e risolto. Una procedura di arrotondamento imposta $x^t_v = 1$ se $x^t_v \geq 1/2$ e scala le variabili degli archi $y^t_e$ per 2, producendo una soluzione parzialmente integrale.

Fase 2: Costruzione Ricorsiva
L'algoritmo costruisce l'albero di clustering top-down:

1. Per un attuale cluster $H$, identifica i vertici che soddisfano il predicato $\mathcal{F}$ ($X_1$) e quelli che non lo soddisfano ($X_0$) a un livello specifico $t = w(H)/2$.
2. Taglio 1 ($E_F$): Utilizza la soluzione LP ristretta a $X_1$ come guida per il problema $p\mathcal{F}$-P. Viene eseguito un algoritmo di approssimazione $\alpha(n)$ per $p\mathcal{F}$-P per tagliare gli archi, garantendo che i vertici in $X_1$ soddisfino il predicato.
3. Taglio 2 ($E_\rho$): Utilizza la soluzione LP ristretta a $X_0$ come guida per il problema del $\rho$-Separator (con $\rho=1/2$). Un algoritmo di approssimazione bicriterio (con rapporto $\beta(n) = O(\log n)$) taglia gli archi per garantire che i componenti rimanenti siano abbastanza piccoli (peso $\leq 2/3$ del genitore).
4. L'unione dei tagli partiziona $H$ in componenti più piccoli, che vengono elaborati ricorsivamente.

3. Risultati Chiave

3.1 Algoritmi di Approssimazione

Il teorema principale afferma che se $\mathcal{F}$ è $\alpha(n)$-ben comportata, esiste un algoritmo di $O(\alpha(n) + \beta(n))$-approssimazione per HC-F, dove $\beta(n) = O(\log n)$ è il rapporto di approssimazione per il problema del $\rho$-Separator.

Applicando questo alle classi specifiche:

• Hierarchical Tree Clustering (HC-$\mathcal{T}$): Poiché il problema del Feedback Edge Set ammette un'approssimazione $O(\log n \cdot \log \log n)$ tramite l'arrotondamento LP, gli autori ottengono un'approssimazione $O(\log n \cdot \log \log n)$ per HC-$\mathcal{T}$.
• Hierarchical Bounded Diameter Clustering (HC-$\mathcal{D}_d$): Poiché il problema del Min-Multicut ammette un'approssimazione $O(\log n)$, gli autori ottengono un'approssimazione $O(\log n)$ per HC-$\mathcal{D}_d$.

Questi sono presentati come i primi algoritmi di approssimazione in tempo polinomiale per queste specifiche varianti di HC-F.

3.2 Hardness di Approssimazione

Il documento stabilisce forti risultati di inapprossimabilità sotto la Small Set Expansion Hypothesis (SSEH):

• Sia HC-$\mathcal{T}$ che HC-$\mathcal{D}_d$ non possono essere approssimati entro alcun fattore costante.
• La prova prevede una riduzione black-box dall'inapprossimabilità del classico Hierarchical Clustering.
  • Per HC-$\mathcal{D}_d$, la riduzione attacca gadget di diametro $d$ a ogni vertice, costringendo l'algoritmo a trattare il gadget come un rappresentante del vertice originale.
  • Per HC-$\mathcal{T}$, la riduzione attacca triangoli ai vertici. Gli autori sfruttano la proprietà per cui il costo dell'ottimo Hierarchical Clustering è inferiore o uguale al costo del Minimum Linear Arrangement (MLA), dimostrando che questo limite inferiore vale anche per gli istanze costruite.

4. Significato e Rivendicazioni

Il documento rivendica di fornire i primi risultati algoritmici per il problema del Hierarchical F-Clustering. Il suo contributo primario è un framework generale che unifica l'approssimazione del clustering gerarchico in varie classi strutturali, a condizione che tali classi soddisfino la condizione di $\alpha(n)$-ben comportata.

Gli autori sottolineano che il loro approccio non è limitato agli alberi o ai grafi a diametro limitato, ma si applica a qualsiasi classe in cui il corrispondente problema di partizionamento piatto (come il Multiway Cut) ammetta una naturale formulazione ILP con garanzie di arrotondamento dimostrabili. Notano che migliorare questi rapporti di approssimazione oltre il fattore $O(\log n)$ richiederebbe probabilmente scoperte fondamentali nell'approssimazione di problemi di taglio e separatore (come lo Sparsest Cut o il Multicut), che sono attualmente ritenuti difficili da migliorare.

Il lavoro evidenzia anche motivazioni pratiche, come la necessità di strutture di clustering che si fermino a componenti "semplici" (come le directory nei file system o le categorie di prodotti nell'e-commerce) piuttosto che forzare tutti i cluster a essere singleton, fornendo così una codifica di livelli di granularità significativi.