GAP : Cadre de partitionnement de graphe approximatif et généralisable

La partition de graphe est le problème consistant à diviser les nœuds d'un graphe en partitions équilibrées tout en minimisant les coupures d'arêtes entre ces partitions. En raison de sa nature combinatoire, de nombreuses solutions approchées ont été développées, notamment des variantes de méthodes multiréseaux et de clustering spectral. Nous proposons GAP, un cadre de partitionnement approché généralisable qui adopte une approche d'apprentissage profond pour la partition de graphe. Nous définissons une fonction de perte différentiable qui représente l'objectif de partitionnement et utilisons la rétropropagation pour optimiser les paramètres du réseau. Contrairement aux méthodes de base qui refont l'optimisation pour chaque graphe, GAP est capable de généralisation, ce qui nous permet d'entraîner des modèles capables de produire des partitions performantes au moment de l'inférence, même sur des graphes inconnus. De plus, puisque nous apprenons la représentation du graphe tout en optimisant conjointement la fonction de perte de partitionnement, GAP peut être facilement ajusté à diverses structures de graphes. Nous évaluons les performances de GAP sur des graphes de tailles et structures variées, y compris des graphes issus de modèles largement utilisés en apprentissage automatique (par exemple, ResNet, VGG et Inception-V3), des graphes sans échelle et des graphes aléatoires. Nous montrons que GAP atteint des partitions compétitives tout en étant jusqu'à 100 fois plus rapide que les méthodes de base et qu'il généralise bien aux graphes inconnus.