Technische Samenvatting: Connected by Construction (C2TSP)

Probleemdefinitie

Het artikel behandelt het Traveling Salesman Problem (TSP), een canoniek combinatorisch optimalisatieprobleem dat een oplossing vereist die voldoet aan twee structurele beperkingen: lokale graadbeperkingen (elke knoop moet graad twee hebben) en globale connectiviteit (de geselecteerde randen moeten één enkele Hamiltoniaanse cyclus vormen).

Huidige op leren gebaseerde methoden voor TSP falen vaak in het direct representeren van deze globale verbonden structuur binnen het geleerde object. In plaats daarvan vertrouwen zij op:

• Autoregressieve constructie: Het sequentieel genereren van tours met procedurele masking.
• Heatmap-gebaseerde benaderingen: Het voorspellen van randscores en vertrouwen op downstream reparatie, sampling of zoekprocessen om een geldige tour te verkrijgen.
• Toewijzingsruimte-relaxaties: Het modelleren van gladde permutatie-achtige objecten die de rand-nabijheidstructuur die de tourkosten bepaalt, niet direct vastleggen.

Deze benaderingen lijden onder twee primaire beperkingen: ze bieden geen tractabele globale distributie over verbonden combinatorische objecten, en hun prestaties zijn nauw gekoppeld aan downstream decoding of zoekprocessen, wat het moeilijk maakt om de kwaliteit van de geleerde representatie te scheiden van de effecten van de nabewerking.

Methodologie: C2TSP

De auteurs stellen C2TSP (Connected by Construction) voor, een end-to-end unsupervised learning pipeline die TSP leert via een structureel betekenisvol latent object: de gewortelde 1-boom (rooted 1-tree).

1. De Gewortelde 1-Boom Surrogaat

In plaats van te proberen direct een Hamiltoniaanse cyclus te leren (die een onhandelbare partitiefunctie heeft), werkt het model op de familie van gewortelde 1-bomen.

• Definitie: Een gewortelde 1-boom bestaat uit een opspante boom op alle niet-wortel knopen ($\bar{V}$) plus precies twee randen incident aan een vaste wortelknoop ($r$).
• Structurele Garantie: Door constructie is elke configuratie in deze familie globaal verbonden en voldoet deze aan de wortelgraadbeperking ($d_r = 2$).
• Tractabiliteit: In tegenstelling tot de Hamiltoniaanse Gibbs-distributie laat de familie van gewortelde 1-bomen een exacte factorisatie toe. Dit maakt de exacte berekening van de partitiefunctie $Z_r(\eta)$, randmarginals $\mu(\eta)$ en graadmomenten mogelijk, wat training met verwachte kosten mogelijk maakt zonder sampling.

2. Gesmoothde Held–Karp Equilibratie

Het primaire structurele defect van een gewortelde 1-boom is dat niet-wortel knopen mogelijk niet graad twee hebben. Om dit te corrigeren, introduceren de auteurs een gesmoothde Held–Karp (HK) equilibratie-laag.

• Deze laag lost voor node-additieve duale variabelen ($\lambda$) op die de randkosten zo bijsturen dat de verwachte graad van elke niet-wortel knoop gelijk is aan twee onder de gewijzigde Gibbs-distributie.
• De laag wordt end-to-end getraind met behulp van impliciete differentiatie door de evenwichtsmap, volgens het paradigma van impliciete optimalisatie-lagen.
• Dit proces zorgt ervoor dat de geleerde distributie in verwachting graad-gebalanceerd is, waardoor het "graaddefect" wordt verwijderd terwijl de connectiviteit behouden blijft.

3. Certificaat-gestuurde Verscherping

Zelfs na HK-equilibratie kan de distributie nog steeds waarschijnlijkheidsmassa bevatten op niet-tour structuren (gewortelde 1-bomen die geen Hamiltoniaanse cycli zijn).

• Certificaat: De auteurs leiden een certificaat af dat deze "niet-tour massa" ($\gamma(q)$) begrenst met behulp van de totale variantie van de niet-wortel graden: $\gamma(q) \leq \frac{1}{2} \sum \text{Var}(d_i)$.
• Verfijning: Een certificaat-gestuurde verscherpingsstap gebruikt de afgeleide van een Bernoulli upper-bound certificaat om de marginale distributie naar meer tour-achtige structuren te duwen. Dit fungeert als een deterministische verfijning die randen met een lage waarschijnlijkheid straft en randen met een hoge waarschijnlijkheid beloont, waardoor de gecertificeerde bovengrens op de niet-tour massa wordt verminderd.

4. Learning Pipeline

De pipeline leert residuele randperturbaties ($\Gamma_\theta$) van de onbevooroordeelde TSP-kosten.

• Forward Pass: Ruwe kosten worden geperturbeerd, geprojecteerd om node-additieve componenten te verwijderen, door de HK-equilibratie-laag geleid en verfijnd via certificaat-gestuurde verscherping.
• Loss Functie: Het model wordt getraind met een unsupervised loss gebaseerd op de verwachte TSP-kosten van de geleerde randmarginals, zonder expliciete straftermen voor structurele beperkingen (aangezien deze door de architectuur worden afgedwongen).

Belangrijkste Bijdragen

1. Tractabele Gewortelde 1-Boom Representatie: Het artikel introduceert een representatie die globale connectiviteit garandeert door constructie en tegelijkertijd exacte marginale berekening voor training toelaat.
2. C2TSP Pipeline: Een end-to-end unsupervised framework die een Graph Neural Network (GNN) voor residuele randperturbatie combineert met een gesmoothde Held–Karp laag voor graad-equilibratie.
3. Non-Tour Mass Certificate: De afleiding van een certificaat dat de resterende structurele kloof begrenst, welke vervolgens wordt gebruikt om een verscherpingsmechanisme te sturen dat de distributie richting Hamiltoniaanse cycli duwt.
4. Empirische Validatie: Demonstratie dat de gewortelde 1-boom representatie sterke pure-decoding prestaties oplevert en robuust blijft wanneer het wordt geïntegreerd in klassieke solvers zoals LKH-3, in tegen tegenstelling tot verschillende heatmap-gebaseerde baselines die bij grotere schalen degraderen.

Experimentele Resultaten

De auteurs evalueerden C2TSP op 2-D symmetrische Euclidische TSP instanties (TSP-50 tot TSP-1000) tegenover baselines inclusief DIFUSCO, DIMES, Fast-T2T, UTSP, en NeuroLKH.

• Pure Decoding: C2TSP behaalde de laagste optimaliteitsgap in 20 van de 25 geteste configuraties (variërend in probleemgrootte en decoder niveau). Opvallend genoeg presteerde het het best in regimes met zware lokale zoekbudgetten (bijv. 100 iteraties van 2-opt), wat suggere het dat de geleerde distributie reeds een sterke tour-achtige structuur codeert.
• LKH Integratie: Wanneer gebruikt als kandidaat-bron voor de LKH-3 solver, bleef C2TSP robuust over alle probleemgroottes en bleef het binnen $\sim 1$ deel per tienduizend (‱) van de vanilla LKH-3. In tegenstelling hiermee degradeerden heatmap-gebaseerde methoden (DIFUSCO, Fast-T2T, UTSP) significant bij grotere formaten ($n \geq 500$) wanneer ze met LKH werden geïntegreerd.
• Ablatie Studies:
  • Het verwijderen van de randperturbatie veroorzaakte een substantiële daling in prestaties (gemiddelde gap steeg van 1,55% naar 12,74%), wat de noodzaak aangeeft om de residuele randgeometrie te leren.
  • Certificaat-gestuurde verscherping verbeterde de prestaties verder door de marginale distributie te verfijnen, wat bevestigt dat een lage gerelaxeerde kost alleen onvoldoende is voor hoogwaardige decoding.

Betekenis en Claims

Het artikel claimt dat een differentieerbaar latent object een centrale modelleringskeuze is voor leren-gebaseerde TSP. Door verbondenheid te coderen vóór decoding, legt C2TSP een "nabij-tour marginal" bloot waarvan de structurele evolutie getraind, gecertificeerd en geanalyseerd kan worden.

De auteurs positioneren hun werk als een verschuiving van het leren van onbeperkte randscores naar het leren van een tractabele nabij-tour marginal met expliciete structurele betekenis. Zij argumenteren dat deze benadering de geleerde representatie scheidt van de nabewerking, waardoor het model een globaal consistente startpositie kan bieden voor lokale zoekprocedures.

Het artikel erkent een beperking die inherent is aan de ontwerpkeuze: de gewortelde 1-boom relaxeert de exacte Hamiltoniaanse cyclus-support. Hoewel connectiviteit wordt afgedwongen en graad-balans in verwachting wordt hersteld, worden de resterende graadfluctuaties gecontroleerd via equilibratie en verscherping in plaats van exact geëlimineerd. De auteurs suggereren dat dit nieuwe richtingen opent voor striktere certificaat-gestuurde updates en rijkere tractabele verbonden families.