🤖 AI

Graph Neural Networks are Heuristics

Dit artikel toont aan dat Graph Neural Networks kunnen fungeren als snelle, geleerde heuristieken voor het Euclidische Handelsreizigersprobleem door ongesuperviseerd trainen te gebruiken om volledige tours te genereren in een enkele forward pass, waarbij ze traditionele greed-baselines overtreffen zonder afhankelijk te zijn van labels, beloningen of sequentiële decodering.

Oorspronkelijke auteurs: Yimeng Min, Carla P. Gomes

Gepubliceerd 2026-07-07

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Yimeng Min, Carla P. Gomes

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Idee: Leren een puzzel op te lossen zonder regelboek

Stel je voor dat je probeert een enorme puzzel op te lossen: het Reizende Handelsman-probleem (TSP). Je hebt een kaart met 100, 200 of zelfs 500 steden, en je moet de kortst mogelijke route vinden die elke stad precies één keer bezoekt en terugkeert naar huis.

Traditioneel lossen mensen dit op twee manieren op:

De "Perfecte" Manier: Gebruik een supercomputer om elke mogelijke route te controleren. Dit garandeert het beste antwoord, maar duurt eeuwig (zoals proberen elk boek in een bibliotheek te lezen om één specifieke zin te vinden).
De "Goed Genoeg" Manier (Heuristieken): Gebruik een set handgemaakte regels, zoals "ga altijd naar de dichtstbijzijnde stad als volgende." Dit is snel, maar leidt vaak tot een matige route omdat het vast komt te zitten in lokale valstrikken.

De bewering van het papier:
De auteurs, Yimeng Min en Carla Gomes van Cornell University, stellen dat Graph Neural Networks (GNN's) niet alleen "helpers" hoeven te zijn die deze oude regels sturen. In plaats daarvan kan de GNN zelf de slimste regelmaker zijn.

Ze bouwden een systeem dat leert de TSP op te lossen zonder dat het de juiste antwoorden geleerd krijgt (geen labels), zonder een gokspel te spelen om beloningen te krijgen (geen reinforcement learning), en zonder achteraf zijn werk te controleren om fouten te herstellen (geen zoekopdracht of lokale verbetering). Het leert puur door naar de vorm van het probleem te kijken.

Hoe het werkt: De "One-Shot" Kunstenaar

De meeste AI-modellen die puzzels oplossen, werken als een langzame schilder die telkens één penseelstreek toevoegt (de volgende stad beslissen, dan de volgende, enzovoort). Dit papier gebruikt een Niet-Autoregressief model.

De Analogie: De Instant Mozaïek
Stel je voor dat je een doos met tegels hebt die steden vertegenwoordigen.

Oude AI: Pakt één tegel op, plaatst hem, pakt een andere op, plaatst deze ernaast, enzovoort. Het bouwt het pad stap voor stap op.
De AI van dit papier: Kijkt in één oogslag naar de hele doos met tegels en klikt ze direct in elkaar tot een compleet, afgewerkt mozaïek in één enkele flits. Het bouwt het pad niet; het ziet direct het hele plaatje.

Het Geheime Recept: Drie Trucs voor Eén Enkel Model

Omdat de AI niet mag "zoeken" of zijn fouten mag "herstellen" nadat hij een gok heeft gedaan, hoe wordt hij dan zo goed? De auteurs gebruikten drie slimme trucs om het model robuust en divers te maken:

Symmetrie-bewuste Visie (De "Roterende Kaart" Truc):
Als je een kaart van steden roteert, verandert de kortste route niet; hij ziet er alleen anders uit. De auteurs leerden de AI dat de vorm van de route ertoe doet, niet de specifieke coördinaten. Ze gaven de AI een speciale "intrinsieke" manier om de kaart te zien (zoals het gebruiken van een kompas en een liniaal ten opzichte van het middelpunt), zodat de AI niet in de war raakt door waar de kaart op de tafel ligt.
Gecontroleerde Chaos (De "Dropout" Truc):
Normaal gesproken, wanneer je een AI traint, zet je sommige van zijn neuronen willekeurig uit (genaamd "dropout") om te voorkomen dat de AI de trainingsdata uit het hoofd leert. De auteurs hielden deze "uit"-knop actief, zelfs wanneer de AI de puzzel oploste.
- De Analogie: Stel je voor dat je een chef vraft om hetzelfde gerecht 10 keer te koken. Meestal zou de chef het precies hetzelfde bereiden. Maar hier is de chef licht afgeleid of gebruikt hij telkens een iets andere hoeveelheid zout. Dit creëert 10 licht verschillende versies van het gerecht. De AI voert de puzzel 10 keer uit met deze "afleiding" en genereert zo 10 verschillende routes. Je kiest vervolgens gewoon de beste. Dit creëert variatie zonder dat je 10 verschillende chefs hoeft te trainen.
Snapshot Ensembling (De "Tijdreis" Truc):
Tijdens het trainen verandert een model in de loop van de tijd. De auteurs sloegen het model op verschillende momenten tijdens de training op (zoals het maken van foto's van een student aan het einde van elke maand).
- De Analogie: In plaats van alleen het eindcijfer van de student te gebruiken, gebruiken ze de prestaties van de student in september, oktober, november en december. Soms is de "september"-versie van het model beter in een specifiek type puzzel dan de "december"-versie. Door deze "snapshots" te combineren, krijgen ze een team van experts uit dezelfde trainingssessie, die allemaal gratis samenwerken.

De Resultaten: Snel en Verrassend Goed

Het papier testte dit op kaarten met 100, 200 en 500 steden.

Snelheid: Het is ongelooflijk snel. Op een moderne computerchip (GPU) lost het de puzzel op in milliseconden. Het is sneller dan een mens kan knipperen.
Kwaliteit:
- Het verslaat de standaard "Ga naar de dichtstbijzijnde buur" (greedy) methode met een ruime marge.
- Het is competitief met veel tragere, complexe methoden die gebruikmaken van zoekopdrachten en verfijning.
- Het komt binnen ongeveer 4% tot 12% van het "perfecte" wiskundige antwoord (gevonden door de supertrage Concorde-solver), wat een enorme prestatie is voor iets dat niet zoekt of fouten herstelt.

De Kernboodschap

Het papier concludeert dat Graph Neural Networks niet slechts assistenten zijn; zij zijn zelf heuristieken.

In plaats van dat een menselijke ingenieur een complexe set regels schrijft om een probleem op te lossen, kunnen we een neuraal netwerk trainen om de structuur van het probleem te "voelen" en in één enkele, razendsnelle blik een hoogwaardige oplossing te produceren. De AI leert de "grammatica" van de oplossing direct van de data, wat bewijst dat je niet de regels van het spel hoeft te programmeren als je de computer kunt leren de structuur van het spel te begrijpen.

Technische Samenvatting: Graph Neural Networks zijn Heuristieken

Probleemdefinitie
Het artikel behandelt het Euclidische Handelsreizigersprobleem (TSP), een canoniek combinatorisch optimalisatieprobleem waarbij het doel is om de kortste Hamiltoniaanse cyclus te vinden door een verzameling van $n$ steden. De auteurs dagen het heersende paradigma uit waarbij Graph Neural Networks (GNN's) slechts als hulpmiddelen dienen—het verstrekken van scores, het sturen van zoekprocessen of het imiteren van algoritmen voor klassieke solvers. In plaats daarvan stelt het artikel dat een GNN kan fungeren als een zelfstandige, geleerde heuristiek. De specifieke uitdaging is het construeren van een volledige tour in één enkele forward pass, zonder te vertrouwen op autoregressieve decodering, reinforcement learning-beloningen, expliciete zoekprocedures (zoals beam search) of post-hoc lokale verbetering (zoals 2-opt).

Methodologie
De voorgestelde methode is een niet-autoregressief, ongesuperviseerd GNN-framework dat leert de TSP-instanties direct vanuit de geometrische structuur van het probleem op te lossen.

Doel en Formulering:
De TSP wordt geformuleerd als het minimaliseren van de trace van het product tussen de afstandmatrix $D$ en een permutatiematrix $P$ , getransformeerd door een cyclische verschuivingsmatrix $V$ . Om end-to-end gradiëntgebaseerde optimalisatie mogelijk te maken, wordt de discrete permutatie $P$ tijdens de training gerelaxeerd naar een zachte permutatiematrix $T$ met behulp van de Gumbel-Sinkhorn-relaxatie. De verliesfunctie is simpelweg de verwachte tourlengte: $L_{TSP} = \langle D, TVT^\top \rangle$ . Tijdens de inferentie wordt de zachte permutatie omgezet in een harde permutatie met behulp van het Hongarije-algoritme.
Symmetrie-bewuste Kenmerkextractie:
Om ervoor te zorgen dat het model de symmetrieën van de Euclidische groep respecteert (permutatie- en translatie-invariantie/equivariantie), introduceren de auteurs een deterministische kenmerkextractor.

Translatie-invariantie: Stadscoördinaten worden gecentreerd door het gemiddelde af te trekken.
Canonieke Frame: Een orthonormaal frame wordt geconstrueerd met behulp van de eigenvectoren van de empirische covariantiematrix van de gecentreerde punten. Dit verwijdert rotatie- en reflectie-ambiguïteiten.
Harmonische Codering: Punten worden geprojecteerd op dit canonieke frame om intrinsieke polaire coördinaten ( $r, \theta$ ) af te leiden. Angulaire informatie wordt gecodeerd met $M$ Fourier-harmonischen ( $\sin(m\theta), \cos(m\theta)$ ), wat de GNN voorziet van rotatie-invariante structurele aanwijzingen.

Netwerkarchitectuur:
De kern van het model is een Scattering-Attention Graph Neural Network (SCT-GNN). Het combineert diffusie-gebaseerde representaties (met behulp van graafoperators afgeleid van machten van een gesmoothde random-walk matrix) met leerbare aandachtmechanismen die kenmerken adaptief mengen over verschillende diffusieschalen. Het netwerk is per constructie permutatie-equivariant.
Ensemble-strategieën voor Diversiteit:
Om de diversiteit van oplossingen te genereren zonder meerdere modellen te trainen of iteratieve zoekprocessen uit te voeren, hanteert het artikel twee mechanismen binnen een enkele trainings-traject:

Monte Carlo (MC) Dropout: Dropout wordt toegepast tijdens de inferentie. Door meerdere stochastische forward passes uit te voeren met verschillende dropout-masks, genereert het model diverse tours vanuit een enkele getrainde instantie.
Snapshot Ensembling: Meerdere checkpoints worden op verschillende tijdstippen (epochs) tijdens een enkele trainingsronde opgeslagen. Deze snapshots, die verschillende punten in het optimalisatielandschap vertegenwoordigen, worden gezamenlijk gebruikt tijdens de inferentie. De beste tour onder de snapshots wordt geselecteerd.

Belangrijkste Bijdragen

GNN's als Zelfstandige Heuristieken: Het artikel demonstreert dat een GNN een volledige heuristiek kan zijn, die in één forward pass een geldige tour produceert zonder hulp van zoekprocessen of verfijning.
Ongesuperviseerd Leren: Het model vereist geen grondwaarheid (ground-truth) optimale oplossingen of reinforcement-beloningen; het leert uitsluitend door de tourlengte-doelstelling te minimaliseren.
Leren van Globale Structuur: Door lokale hebzuchtige (greedy) mechanismen te verwijderen en te vertrouwen op een globale Hamiltonian-cyclus doelstelling, leert het model niet-lokale combinatorische restricties die puur lokale beslisregels (zoals nearest-neighbor) missen.
Efficiëntie: De methode bereikt milliseconde-snelheid bij inferentie op GPU's, wat een gunstige kwaliteit-efficiëntie-afweging biedt vergeleken met klassieke heuristieken en andere leer-gebaseerde benaderingen die afhankelijk zijn van autoregressieve decodering of zoekprocessen.

Resultaten
Experimenten werden uitgevoerd op TSP-instanties met $n=100, 200,$ en $500$ knopen getrokken uit een uniforme Euclidische distributie.

Prestaties vs. Greedy: Het model presteert consistent beter dan de Greedy Nearest-Neighbor (NN) baseline. Voor TSP100 verbeterde de gemiddelde tourlengte van 9,67 (Greedy) naar 8,18 (Deterministische GNN).
Prestaties vs. Klassieke Heuristieken: De methode presteert significant beter dan de Christofides-heuristiek op kleinere instanties (TSP100, TSP200) en komt overeen met deze op TSP500, maar met ordes van grootte lagere inferentietijd op GPU's.
Prestaties vs. Leer-gebaseerde Baselines: Vergeleken met Reinforcement Learning (RL) en Supervised Learning (SL) baselines (bijv. GAT, GCN), bereikt de voorgestelde methode competitieve of superieure optimaliteitsgaps (bijv. een gap van 4,39% op TSP100 versus 2,48% voor een sterke RL-baseline met beam search), terwijl deze aanzienlijk sneller is omdat het autoregressieve decodering en beam search vermijdt.
Ensemble-effecten: Zowel MC dropout als snapshot ensembling verminderen de optimaliteitsgap verder. De combinatie van beide strategieën leverde de beste resultaten op (4,39% gap op TSP100, 8,25% op TSP200, 12,11% op TSP500) met inferentietijden die in het milliseconde-regime blijven (tot ongeveer ~82ms voor het gecombineerde ensemble op TSP500).

Betekenis en Claims
Het artikel claimt dat heuristieken geen handmatig ontworpen regels of zoekprocedures hoeven te zijn, maar direct kunnen voortkomen uit het leren van de structuur van het probleem. Door TSP te formuleren als directe permutatie-lering met een differentieerbare Hamiltonian-cyclus doelstelling, laten de auteurs zien dat GNN's globale combinatorische restricties kunnen internaliseren. De betekenis ligt in de verschuiving van het paradigma van combinatorische optimalisatie: structurele restricties en generatieve modellen kunnen expliciet zoeken vervangen als de basis voor het oplossen van onhandelbare problemen. De resultaten suggereren dat "geleerde heuristieken" zowel de kwaliteit van de oplossing als de computationele efficiëntie kunnen evenaren of overtreffen van klassieke ontwerpmethoden, vooral wanneer de kosten van zoekprocessen prohibitief zijn. Het werk positioneert ongesuperviseerde GNN's als een nieuwe klasse van snelle, geleerde heuristieken voor combinatorische optimalisatie.