Résumé Technique : Équité Individuelle dans le Partitionnement Hiérarchique

1. Formulation du Problème

Le papier traite d'une limitation fondamentale du partitionnement hiérarchique classique : bien que ces méthodes produisent des représentations multi-résolutions (dendrogrammes) définies par des ultramétriques, elles manquent souvent de garanties concernant le traitement des points de données individuels. Les approches standards optimisent des objectifs globaux ou suivent des règles de liaison glouttes, ce qui peut déformer les similitudes locales de manière à affecter de façon disproportionnée certains individus spécifiques. Puisque les structures hiérarchiques se propagent vers le haut, les distorsions précoces dans les voisinages locaux affectent toutes les résolutions plus grossières.

Les auteurs formalisent le problème de l'Équité Individuelle dans le Partitionnement Hiérarchique. L'exigence fondamentale est que des individus similaires (définis par une métrique $d$) soient traités de manière similaire. Plus précisément, le papier examine s'il existe une représentation ultramétrique $u$ qui satisfait deux conditions :

1. Domination : $u(i, j) \ge d(i, j)$ pour toutes les paires (aucune distance n'est contractée).
2. Équité Locale : Au sein d'un voisinage de $k$ plus proches voisins ($k$-NN) d'un point $i$, la distance ultramétrique est bornée par un relâchement multiplicatif $\alpha$ (et un relâchement additif $\beta$) par rapport à la métrique d'origine : $u(i, j) \le \alpha d(i, j) + \beta$ pour tout $j \in N_k(i)$.

L'objectif principal est de caractériser le relâchement multiplicatif minimal $\alpha^\star(d, k)$ requis pour qu'une telle ultramétrique réalisable existe.

2. Méthodologie et Cadre Théorique

Paysage de Faisabilité

Les auteurs analysent la faisabilité de trouver une ultramétrique dominante qui respecte des contraintes de Lipschitz locales. Ils distinguent les voisinages mutuels (où $j \in N_k(i)$ et $i \in N_k(j)$) des voisinages unidirectionnels.

Résultats Théoriques Clés

• Relâchement Local Nécessaire (Théorème 1) : Les auteurs définissent un ratio d'hétérogénéité locale, $\alpha^{\text{mut}}_k(d)$, qui mesure la séparation d'échelle maximale au sein des étoiles de $k$ plus proches voisins mutuels. Ils prouvent que tout relâchement multiplicatif $\alpha$ réalisable doit satisfaire $\alpha \ge \alpha^{\text{mut}}_k(d)$. Cela établit un seuil local net ; si le relâchement est inférieur à cette valeur, l'équité est mathématiquement impossible.
• Stabilité (Théorème 2) : Le seuil de relâchement minimal est montré comme étant Lipschitz-stable sous des perturbations $\ell_\infty$ bornées de la métrique, à condition que les identités des $k$ plus proches voisins restent inchangées (voisinages $\epsilon$-stables).
• Suffisance Constructive (Théorème 3) : En s'appuyant sur la théorie classique de l'incorporation d'arbres (spécifiquement les résultats de [11]), les auteurs prouvent que pour toute métrique à $n$ points, une ultramétrique dominante avec un relâchement $\alpha = O(\log n)$ existe toujours. Cela fournit une borne supérieure globale sur la distorsion requise.
• Écart Intrinsèque Local-Global (Proposition 1) : Une découverte critique est la séparation entre la structure locale et la réalisabilité globale. Les auteurs construisent des familles de métriques (basées sur des graphes expanseurs) où le ratio d'hétérogénéité locale est trivial ($\alpha^{\text{mut}}_k(d) = 1$), pourtant toute ultramétrique dominante nécessite une distorsion de $\Theta(\log n)$. Cela démontre que la cohérence locale ne garantit pas la faisabilité globale.
• Monotonie (Théorème 4) : Le relâchement minimal réalisable $\alpha^\star(d, k)$ est non-décroissant par rapport à la taille du voisinage $k$. Le renforcement des contraintes d'équité locale (augmentation de $k$) ne réduit jamais le relâchement global requis.

Approche Algorithmique : FCAC

Pour construire des ultramétriques réalisables, le papier propose le Fairness Constrained Agglomerative Clustering (FCAC).

• Mécanisme : Le FCAC modifie le partitionnement agglomératif standard en imposant des contraintes d'équité lors du processus de sélection de la fusion. Il sépare le score de liaison (qui détermine l'ordre de fusion) de l'assignation de la hauteur de fusion.
• Assignation de la Hauteur : La hauteur de fusion est fixée à $h(A, B) = \max(\ell(A, B), \max_{i \in A, j \in B} d(i, j))$, garantissant que la condition de dominance ($u \ge d$) est respectée.
• Vérification de Faisabilité : Avant de fusionner deux clusters, l'algorithme vérifie si la hauteur proposée viole la contrainte d'équité ($h \le \alpha d(i, j) + \beta$) pour toute paire de voisins à travers les clusters.
• Complexité : L'algorithme s'exécute en $O(n^3 k)$ temps dans le pire des cas. Le papier note que déterminer la complexité computationnelle exacte du problème de décision de faisabilité sous-jacent reste une direction ouverte.

3. Résultats Expérimentaux

Les auteurs valident leurs affirmations théoriques sur des jeux de données synthétiques et réels (mélanges gaussiens, graphes aléatoires 3-réguliers, UCI Census Income, German Credit Data et Iris).

• Seuils de Faisabilité : Les expériences sur les mélanges gaussiens montrent une transition nette dans la faisabilité. Le relâchement minimal réalisable $\alpha^\star$ était significativement plus élevé (17,46) que le seuil mutuel local (5,08), confirmant que la cohérence locale sous-estime les exigences de distorsion globale.
• Écart Local-Global : Sur les graphes aléatoires 3-réguliers, le ratio local $\alpha^{\text{mut}}_k(d)$ restait de 1, tandis que le relâchement minimal réalisable $\alpha^\star$ augmentait avec $n$, démontrant empiriquement l'écart $\Theta(\log n)$ prédit par la Proposition 1.
• Comportement de Mise à l'Échelle :
  • Dans les jeux de données hétérogènes (ex: Adult), $\alpha^\star$ augmentait significativement avec la taille de l'échantillon $n$, suggérant que les violations géométriques locales rares s'accumulent pour amplifier la distorsion globale.
  • Dans les jeux de données plus stables (ex: German Credit), $\alpha^\star$ restait relativement constant malgré l'augmentation de $n$.
• Saturation de l'Obstruction : Le relâchement minimal $\alpha^\star$ a été observé comme saturant pour de petites tailles de voisinage ($k \approx 3$), indiquant que l'obstruction ultramétrique globale est déterminée par des configurations géométriques à petite échelle.
• Comparaison Algorithmique : Sur le jeu de données Adult ($n=800$), la variante FCAC (basée sur l'Arbre Couvrant Minimum - MST) a atteint un relâchement de 1,00, alors que l'incorporation FRT (une méthode standard d'incorporation d'arbres) a produit un relâchement moyen de 67,26, malgré la garantie théorique $O(\log n)$ de FRT. Cela suggère qu'une construction tenant compte de la géométrie peut nettement surpasser les bornes d'incorporation génériques en pratique.

4. Signification et Revendications

Le papier affirme fournir la première analyse de faisabilité structurelle de l'équité individuelle dans le partitionnement hiérarchique. Sa signification réside dans :

1. Recadrage de l'Équité : Déplacer l'attention de l'optimisation des objectifs globaux vers la caractérisation de la faisabilité des contraintes d'équité locale au sein de la géométrie rigide des ultramétriques.
2. Quantification du Coût Intrinsèque : Établir que le coût de l'équité dans les représentations hiérarchiques est intrinsèquement lié à la distorsion métrique, en identifiant spécifiquement une séparation inévitable de $\Theta(\log n)$ entre la similitude locale et la réalisabilité ultramétrique globale pour certaines familles de métriques.
3. Contribution Algorithmique : Fournir un algorithme constructif (FCAC) qui impose ces contraintes et démontrer empiriquement que les méthodes dépendantes des données (spécifiquement la variante basée sur l'MST) peuvent atteindre un relâchement proche de l'optimal par rapport aux techniques d'incorporation génériques.

Les auteurs concluent que bien que les conditions locales soient nécessaires, elles sont insuffisantes pour déterminer la réalisabilité globale, et que le relâchement minimal requis est une propriété fondamentale de la structure géométrique des données. Un travail futur est suggéré pour caractériser la complexité computationnelle du problème de faisabilité et étendre le cadre à d'autres représentations multi-échelles.