AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

Technische Samenvatting: AGDN – Leren om het Handelsreizigersprobleem op te lossen met een Anisotroop Grafische Diffusienetwerk

Probleemdefinitie
Het Handelsreizigersprobleem (Traveling Salesman Problem, TSP) is een fundamenteel combinatorisch optimalisatieprobleem waarbij het doel is om de kortste route te vinden die een reeks steden precies één keer bezoekt en terugkeert naar de oorsprong. Hoewel Graph Neural Networks (GNN's) effectieve instrumenten zijn geworden voor TSP vanwege hun aansluiting bij de topologische zoekruimte van het probleem, kampen huidige op leren gebaseerde benaderingen met twee kritieke beperkingen:

1. Gebrek aan Informatieve Topologische Prior: In tegenstelling tot standaard grafische leertaken worden TSP-instanties doorgaans gemodelleerd als volledig verbonden grafen. Deze structuur mist een inherente topologische prior met betrekking tot de optimale oplossing, wat het voor modellen moeilijk maakt om relevante informatie van de oplossing te onderscheiden van ruis.
2. Informatieverlies via Sparsificatie: Om de computationele complexiteit te beheersen, gebruiken bestaande methoden vaak grafische sparsificatie (bijv. via $k$-NN). Dit proces brengt echter het risico met zich mee dat randen die deel uitmaken van de optimale oplossing worden verwijderd. Wanneer optimale paren knopen ontkoppeld zijn, hebben ondiepe GNN's moeite om de noodzakelijke multi-hop relaties te vangen, terwijl diepere GNN's lijden onder over-smoothing en over-squashing.

Methodologie: Anisotropic Graph Diffusion Network (AGDN)
De auteurs stellen AGDN voor, een framework dat is ontworpen om het TSP op te lossen zonder afhankelijk te zijn van grafische sparsificatie. De methodologie bestaat uit vier kerncomponenten:

1. MixScore Transitiematrix:
   In plaats van een standaard adjacency matrix of een eenvoudige afstand-gebaseerde transitie te gebruiken, construeert AGDN een MixScore transitiematrix. Deze matrix integreert twee soorten informatie:

   • Paarsgewijze Afstand: Gecodeerd via een Gaussische kernel ($\exp(-e_{ij}/\sigma)$) om geometrische nabijheid te vangen.
   • Knopen-gelijkenis: Afgeleid van knoop-embeddings in twee verschillende latente ruimtes: een Bron-ruimte ($S$) en een Bestemmings-ruimte ($D$).
     De matrix wordt geformuleerd door de inwendige producten van embeddings uit deze ruimtes ($H_S H_D^T$) samen te voegen met de genormaliseerde afstandmatrix ($T_{rw}$), verwerkt door een Multi-Layer Perceptron (MLP). Dit stelt het model in staat om transitiekansen te coderen die zowel geometrische afstand als geleerde structurele gelijkenis reflecteren.

2. Anisotrope Grafische Diffusie:
   AGDN maakt gebruik van een diffusiemechanisme dat informatie in zowel inkomende ($S$) als uitgaande ($D$) richtingen afzonderlijk verspreidt.

   • Multi-hop Aandacht: Het framework maakt gebruik van een leerbaar multi-hop aandachtmechanisme (geparameteriseerd door $\theta_k$) om informatie te aggregeren uit $K$ hops binnen een enkele convolutielaag. Dit voorkomt de noodzaak voor het stapelen van meerdere lagen, waardoor over-smoothing wordt verminderen.
   • Anisotropie: Door aparte $S$- en $D$-ruimtes te behouden, legt het model directionele informatiestroom vast, wat de granulariteit van knoopkarakterisering verbetert.

3. Knoopinformatie Aggregatie:
   Na de diffusie worden de embeddings uit de $S$- en $D$-ruimtes geaggregeerd. De auteurs gebruiken een self-attention mechanisme waarbij de $S$-ruimte embeddings fungeren als queries en de $D$-ruimte embeddings fungeren als keys en values. Deze asymmetrische aggregatie wordt gevolgd door een finale MLP om de verenigde knoop-embeddings te produceren.

4. Oplossing Identificatie:
   De geaggregeerde knoop-embeddings worden gebruikt om edge-embeddings te genereren via buitenproducten. Een edge-niveau aandachtmechanisme herweegt deze embeddings om kritieke randen te benadrukken. Ten slotte voorspelt een MLP een heatmap die de waarschijnlijkheid representeert dat elke rand deel uitmaakt van de optimale tour. Deze heatmap stuurt een Monte Carlo Tree Search (MCTS) aan om de uiteindelijke oplossing te construeren. Het model wordt geoptimaliseerd via ofwel supervised learning (cross-entropy tegen de grondwaarheid-heatmaps) of unsupervised learning (het minimaliseren van de verwachte tour-lengte).

Belangrijkste Bijdragen

• Probleemkarakterisering: Het paper identificeert en formaliseert de beperkingen van huidige GNN-benaderingen, specifiek de disconnect veroorzaakt door grafische sparsificatie en het gebrek aan informatieve priors in volledig verbonden TSP-grafen.
• Algoritmisch Ontwerp: De introductie van de MixScore transitiematrix en het Anisotropic Graph Diffusion mechanisme. Deze innovaties maken efficiënte multi-hop informatiepropagatie mogelijk zonder sparsificatie, waardoor de connectiviteit tussen optimale knopenparen behouden blijft.
• Empirische Validatie: Uitgebreide experimenten tonen aan dat AGDN superieur presteert aan state-of-the-art methoden in zowel supervised als unsupervised settings over diverse probleemgroottes en knoopverdelingen.

Experimentele Resultaten
De auteurs evalueerden AGDN op TSP-instanties variërend van 200 tot 1000 knopen, evenals op real-world datasets uit TSPLIB.

• Effectiviteit: In supervised learning (SL) settings bereikte AGDN de laagste kloof ten opzichte van de optimale oplossing vergeleken met baselines zoals GatedGCN, Att-GCN en DIFUSCO. Bijvoorbeeld, op TSP-1000 bereikte AGDN een kloof van 1,28% vergeleken met 7,26% voor GatedGCN. In unsupervised learning (UL) settings presteerde AGDN ook beter dan UTSP en Position.
• Efficiëntie: AGDN demonstreerde superieure computationele efficiëntie. Het vereiste minder parameters en minder inferentietijd dan GatedGCN, met name naarmate het aantal hops voor informatieaggregatie toenam. Dit wordt toegeschreven aan het vermogen om multi-hop informatie in een enkele laag te vangen.
• Generalisatie: Het model toonde robuuste generalisatie wanneer getraind op TSP-100 en getest op grotere instanties (TSP-200, 500, 1000) en diverse knoopverdelingen (Uniform, Cluster, Explosion, Implosion). Het behield ook een hoge prestatie op real-world TSPLIB instanties (tsp225, pcb442, pr1002) zonder hertraining.

Betekenis
Het paper beweert dat AGDN een fundamentele afweging tussen grafische sparsificatie en informatieverlies bij het oplossen van TSP aanpakt. Door een anisotrope diffusiestrategie en een MixScore prior te introduceren, stelt het framework GNN's in staat om de volledige connectiviteit van TSP-grafen effectief te benutten. De resultaten suggereren dat AGDN een schaalbare en generaliseerbare oplossing biedt die de kloof overbrugt tussen theoretische grafische leercapaciteiten en de praktische eisen van combinatorische optimalisatie, waarbij state-of-the-art prestaties worden behaald met concurrerende inferentietijden.