Towards Scalable Persistence-Based Topological Optimization

Technische Samenvatting: Naar Schaalbare Persistentie-gebaseerde Topologische Optimalisatie

Probleemstelling
Persistentie-gebaseerde topologische optimalisatie tracht een puntenwolk $X \subset \mathbb{R}^d$ te vervormen om doelfuncties van de vorm $L(X) = \ell(\text{Dgm}(X))$ te minimaliseren, waarbij $\text{Dgm}(X)$ een persistentiediagram is. Hoewel dit theoretisch onderbouwd is door de stabiliteit van persistente homologie, staat de praktische implementatie voor twee gekoppelde knelpunten:

1. Noodzaak tot Subsampling: Het berekenen van persistente homologie op grote puntenwolken is computerafkeurend, wat subsampling noodzakelijk maakt. Echter, introduceert standaard uniforme subsampling een dichtheidsbias, waarbij vaak dichte gebieden overbemonsterd worden terwijl schaarse randgebieden die cruciaal zijn voor topologische kenmerken gemist worden.
2. Gradienten-Sparsiteit: De topologische gradient is zeer spaarzaam; slechts een kleine set "anker"-punten (die betrokken zijn bij kritieke geboorte-/sterfte-simplicialen) ontvangt niet-nul updates. De meeste punten hebben nul-gradienten, wat de optimalisatie vertraagt.
3. Schaalbaarheid van Gladdening: Een recente oplossing, diffeomorf interpolatie (Carrière et al., 2024), breidt spaarzame gradienten uit tot een glad omgevingsvectorveld met behulp van interpolatie in een Reproducing Kernel Hilbert Space (RKHS). Dit vereist echter het oplossen van een kernel-lineair systeem bij elke iteratie, wat in grootschalige settingen computarisch dominant wordt ($O(|I|^3)$).

Methodologie
De auteurs stellen een schaalbaar proces voor dat zowel subsampling- als gradient-uitbreidingsproblemen aanpakt via twee hoofdcomponenten:

1. Subsampling via Random Slicing:
   In plaats van uniforme sampling introduceren de auteurs een gestructureerde bemonsteraar geïnspireerd op gesneden optimale transport.

   • Mechanisme: In elke iteratie wordt een willekeurige richting $u$ getrokken. Punten worden geprojecteerd op deze 1D-lijn ($t_i = \langle x_i, u \rangle$) en gesorteerd. De subsample wordt gevormd door punten te selecteren op gelijkmatig verdeelde rangen in deze gesorteerde lijst.
   • Voordeel: Dit zorgt voor globale geometrische dekking en vermindert dichtheidsbias. Door rangstratificatie af te dwingen, voorkomt de methode dat dichte clusters het bemonsteringsbudget monopoliseren, waardoor schaarse gebieden (bijv. grenzen tussen clusters) consistent worden vertegenwoordigd.

2. Nadaraya-Watson (NW) Gaussische Convolutie:
   Om de kostbare RKHS-kerneloplossing te vervangen, stellen de auteurs het gebruik van een snelle NW-schatter voor om de spaarzame anker-gradienten te gladstrijken tot een globaal vectorveld.

   • Mechanisme: Gegeven ankerpunten $x_i$ met gradienten $g_i$, wordt het veld op elk punt $x$ gedefinieerd als een gewogen gemiddelde: $\bar{v}(x) = \sum_{i \in I} w_i(x) g_i$, waarbij de gewichten $w_i(x)$ genormaliseerde Gaussische affiniteiten zijn $\exp(-\|x-x_i\|^2 / 2\sigma^2)$.
   • Voordelen:
     • Berekenings-efficiëntie: Het vermijdt het oplossen van een lineair systeem, wat de kosten aanzienlijk verlaagt.
     • Geometrisch Gedrag: In tegenstelling tot RKHS-interpolatie, die genormaliseerde kernels gebruikt en kan leiden tot het verdwijnen van de veldgrootte ver van de ankers, dwingt NW-gladstrijking een convexe combinatie af ($\sum w_i = 1$). Dit zorgt ervoor dat het veld niet-nul blijft en zich gedraagt als een lokaal barycentrisch gemiddelde, wat een robuustere propagatie van spaarzame signalen over het domein biedt.
   • Theoretische Garanties: Het artikel levert grenzen voor anker-benaderingsfouten en vestigt globale Lipschitz-continuïteit voor het NW-veld, waarbij wordt aangetoond dat de Lipschitz-constante schaalt met $1/\sigma^2$.

3. Adaptieve Bandbreedte-Learning:
   Door te erkennen dat de bandbreedteparameter $\sigma$ de prestaties kritiek beïnvloedt, stellen de auteurs voor om $\sigma$ online te leren via backpropagation. Ze parametriseren $\sigma(\theta) = \sigma_0 \exp(\theta)$ en updaten $\theta$ om een vooruitziende verliesfunctie te minimaliseren, waardoor de gladstrijkingschaal zich kan aanpassen aan het lokale optimalisatieregime.

Belangrijkste Bijdragen

• Random Slicing: Een lichtgewicht subsampling-schema dat de geometrische dekking verbetert en dichtheidsbias vermindert zonder clustering of ver-van-punt sampling te vereisen.
• NW Gladstrijking: Een vervanging voor exacte kernel-interpolatie die een snelle, genormaliseerde Gaussische convolutie biedt voor het uitbreiden van spaarzame topologische gradienten, waarmee lineaire oplossingen met kubische tijd worden vermeden.
• Theoretische Analyse: Bewijzen van anker-benaderingsgrenzen en globale Lipschitz-schattingen voor de NW-gladstrijkingsoperator.
• Empirische Validatie: Demonstratie van snelheidswinsten en verbeterde doelfunctiewaarden op 2D- en 3D-taken.

Experimentele Resultaten
De auteurs evalueerden hun methode op een 3D topologische augmentatietaken met behulp van de Stanford Bunny puntenwolk ($n \approx 36.000$), met als doel 2D topologische kenmerken (holtes) te versterken.

• Basislijnen: Vergelijking tegen (i) Vanilla spaarzame gradientafstijging (geen gladstrijking), (ii) Exacte Kernel Diffeomorf Interpolatie, en (iii) de voorgestelde NW-Convolutiemethode.
• Prestaties:
  • Doelfunctiewaarde: De NW-Convolutiemethode bereikte een significant lagere loss ($-0,01869$) vergeleken met zowel Vanilla ($-0,00026$) als Kernel ($-0,00151$) methoden.
  • Uitvoeringstijd: De NW-methode behield een uitvoeringstijd per epoch ($2,573$s) die vergelijkbaar was met de Vanilla-basislijn ($2,044$s) en was een orde van grootte sneller dan de Kernel-methode ($19,979$s).
• Sensitiviteit: Experimenten op een ruizige 2D-cirkel toonden een hoge sensitiviteit voor de bandbreedte $\sigma$, wat de noodzaak onderstreept van de voorgestelde adaptieve leerverstrategie.

Betekenis en Claims
Het artikel claimt een centraal praktisch knelpunt in persistentie-gebaseerde optimalisatie aan te pakken: de afweging tussen de spaarzaamheid van topologische gradienten en de berekeningskosten om deze glad te strijken. Door random slicing te combineren met NW-gladstrijking, bieden de auteurs een proces dat zowel schaalbaar als effectief is.

De auteurs handhaven een bescheiden toon regarding hun bijdrage. Zij stellen dat hun werk voornamelijk een stap is om persistentie-gedreven optimalisatie schaalbaarder en praktischer te maken voor settingen met grote puntsets en herhaalde PH-berekeningen. Zij merken expliciet op dat hun huidige evaluatie beperkt is tot gecontroleerde synthetische en standaard geometrie-benchmarks (Stanford Bunny, 2D-vormen) en dat zij nog geen end-to-end impact op downstream real-world taken demonstreren. Het werk wordt gepositioneerd als een methodologische verbetering van de optimalisatielus zelf, eerder dan een nieuw toepassingsdomein.