Technische Samenvatting: Contrastieve Neurale Algoritmische Redenering voor Grafiekkleuring

Probleemstelling

Grafiekkleuring is een fundamenteel probleem in discrete optimalisatie waarbij het doel is om kleuren toe te wijzen aan knooppunten zodanig dat aangrenzende knooppunten verschillende kleuren ontvangen, waarbij het totaal aantal gebruikte kleuren wordt geminimaliseerd (het kromingsgetal). Het probleem is NP-hard, en het benaderen van het kromingsgetal binnen een factor van $O(n^{1-\epsilon})$ is eveneens NP-hard. Hoewel heuristische methoden (greedy algoritmen, SAT-solvers) en recente ongesuperviseerde leerbenaderingen (fysica-geïnspireerde losses) bestaan, lijden deze aan beperkingen:

1. Gebrek aan Generalisatie: Ongesuperviseerde methoden optimaliseren doorgaans elke grafiekinstantie onafhankelijk, waardoor ze niet generaliseren over verschillende grafiekgroottes en distributies.
2. Interpreteerbaarheid: Bestaande solvers missen vaak mechanismen om voorkennis te integreren of geometrische interpretaties van de oplossingsruimte te bieden.
3. Schaalbaarheid: SAT-gebaseerde solvers en instantie-specifieke optimalisatie kunnen computationeel duur zijn voor grote grafieken.

Het artikel richt zich op benaderende $k$-kleuring, waarbij het doel is om maximaal $k$ kleuren te gebruiken terwijl het aantal monochromatische randen (conflicten) wordt geminimaliseerd.

Methodologie

De auteurs stellen een gesuperviseerd contrastief leerkader voor dat een overdraagbare kleuringsgeometrie leert. In plaats van direct kleur-logits te voorspellen of een instantie vanaf nul op te lossen, leert de methode knoop-embeddings waarbij de geometrische relaties de kleuringsbeperkingen coderen.

Kernkader

1. Contrastief Doel: De aanpak beschouwt knooppunten met dezelfde kleur als positieve paren en aangrenzende knooppunten als negatieve paren.
2. Absolute-Waarde InfoNCE: Een belangrijke innovatie is het gebruik van een absolute-waarde variant van de InfoNCE loss. In tegenstelling tot standaard InfoNCE, die vectoren uitlijnt, richt dit doel zich op het uitlijnen van ongeoriënteerde lijnen.
   • Knooppunten met dezelfde kleur: Hun embeddings worden aangemoedigd om te imploderen op een gedeelde één-dimensionale subspace (een lijn), waardoor ze in beide richtingen ($\pm$) langs die lijn kunnen wijzen.
   • Aangrenzende knooppunten: Hun embeddings worden naar orthogonale richtingen geduwd.
3. Architectuur: Een Graph Neural Network (GNN) encoder brengt de grafiekknooppunten in kaart naar unit-norm embeddings. Tijdens de inferentie wordt een lijn-canonicalisatie stap toegepast (bijv. het afdwingen dat de eerste niet-nul waarde positief is), gevolgd door clustering (bijv. $k$-medoids) om de uiteindelijke kleurtoewijzingen te bepalen.
4. Gesuperviseerde Setting: De methode gaat ervan uit dat er tijdens de training toegang is tot een "correcte" of benaderende kleuringsregel (bijv. greedy kleuring labels) om de positieve/negatieve paren te definiëren.

Kernbijdragen

1. Theoretische Karakterisering van Optima

Het artikel biedt een scherpe theoretische analyse van de absolute-waarde InfoNCE loss:

• Lijn-Prototype Structuur: De auteurs bewijzen dat de globale minima van de loss een specifieke geometrie vertonen: de representaties van knooppunten met dezelfde kleur imploderen naar een gedeelde één-dimensionale subspace (lijn), terwijl randen orthogonale subspaces verbinden.
• Ondergrens: Ze stellen een scherpe ondergrens vast voor de loss-functie, waarbij zij aantonen dat gelijkheid exact optreedt wanneer deze "lijn-implosie" en "rand-orthogonaliteit" plaatsvinden.
• Stationariteit: In de gesuperviseerde setting worden de stationaire punten van de loss beheerst door de gewogen quotient-grafiek van de kleuring, wat de loss-geometrie verbindt met de onderliggende grafiekstructuur.

2. Optimalisatiedynamiek en Bias

• Manifold Invariantie: Onder een "equitable" kleuringsaanname (waarbij knooppunten in dezelfde kleurklasse een identiek aantal buren hebben in andere klassen), is de geimplodeerde prototype-manifold invariant onder geprojecteerde subgradient-dynamiek.
• Max-Margin Bias: In een ongenormaliseerde variant vertoont gradiëntafdaling een impliciete bias naar het maximaliseren van de minimale absolute contrastieve marge op de actieve quotient-grafiek, wat convergeert naar een max-margin oplossing.

3. Certificeerbaarheid

De geleerde geometrie biedt een certificaat voor de kleurbaarheid van de grafiek. Als de geleerde representaties een benaderde orthogonaliteit bereiken, demonstreert het artikel hoe dit kan worden opgetild naar een exacte orthogonale representatie, wat een bovengrens oplevert voor de Lovász $\vartheta(G)$ functie. Dit verbindt de geleerde embeddings met klassieke grafentheoretische certificaten.

4. Empirische Prestaties

De auteurs valideren de aanpak op synthetische en real-world datasets:

• Generalisatie: De modellen vertonen sterke grootte-generalisatie (trainen op kleine grafieken, testen op grotere grafieken) en OOD-transfer (out-of-distribution) over verschillende grafiekfamilies (bijv. Book, Myciel, Queen grafieken).
• Efficiëntie: De geleerde encoders produceren laag-conflict kleuringen die de greedy baselines evenaren of soms zelfs verbeteren.
• Snelheid: In tegen tegenstelling tot ongesuperviseerde baselines (bijv. PI-GNN, full-GCN) die tijd-outs ervaren op grote instanties (bijv. cycli met 7.000 knooppunten) door per-instantie optimalisatiekosten, decoderen de getrainde contrastieve encoders grote grafieken in milliseconden na een korte eenmalige trainingsfase.
• Feature Adaptatie: Het artikel onderzoekt strategieën voor feature adaptatie (bijv. het hashen van Bag-of-Words features) om modellen over verschillende citatienetwerken (Cora, CiteSeer, PubMed) te transfereren, waarbij wordt aangetoond dat het behouden van lexicale signalen via hashing de OOD-prestaties verbetert ten opzichte van louter structurele features.

Betekenis en Claims

Het artikel claimt de eerste neurale gesuperviseerde leerbenadering voor grafiekkleuring te zijn die gepaard gaat met een kleurbaarheids-certificaat. De betekenis ligt in:

• Geometrische Interpreteerbaarheid: Het biedt een precies geometrisch mechanisme waarbij kleurpartities lijn-prototypes worden en grafiekranden orthogonaliteitsbeperkingen vormen.
• Schaalbaarheid en Overdraagbaarheid: Het overwint de beperking van instantie-specifieke optimalisatie door een overdraagbare representatie te leren die generaliseert over verschillende grafiekgroottes en distributies.
• Theoretische Fundering: Het gaat verder dan heuristisch black-box leren door de exacte geometrie van de loss-optima en de dynamiek van het optimalisatieproces te karakteriseren.

De auteurs merken bescheiden op dat hoewel de karakterisering van de globale optima scherp is, de resultaten over dynamische invariantie steunen op aannames van "equitable coloring". Ze erkennen ook dat geen enkele architectuur of feature-set universeel optimaal is voor alle grafiekfamilies, wat suggereert dat toekomstig werk zich kan richten op sterkere generalisatietheorie en hybride ontwerpen tussen gesuperviseerd en ongesuperviseerd leren.