Neuer Ansatz mit Graph-Transformern löst Subgraph-Matching effizienter

Das Approximate Subgraph Matching (ASM) ist ein entscheidendes Problem in der Graphanalyse, das die ungefähre Präsenz eines Suchgraphen in einem großen Zielgraphen bestimmt. Da ASM NP-schwer ist, finden sich Anwendungen in Datenbanksystemen, Netzwerkanalyse, Biochemie und Datenschutz.

Traditionelle Verfahren greifen auf heuristische Suchstrategien zurück, die die vollständige Graphinformation nicht optimal nutzen und damit oft suboptimale Lösungen liefern.

In dem neuen Ansatz RL‑ASM wird ein Reinforcement‑Learning‑Modell eingesetzt, das Graph‑Transformer nutzt, um reichhaltige Graphrepräsentationen zu extrahieren. Das Verfahren basiert auf einem Branch‑and‑Bound‑Algorithmus, der Schritt für Schritt Knotenpaare auswählt. Statt heuristischer Entscheidungen werden die Transformer‑Features als Grundlage für die Policy‑Entwicklung verwendet. Die Lernphase beginnt mit einer Imitationsphase, in der überwachte Signale die Agentenführung unterstützen, und wird anschließend mit Proximal Policy Optimization (PPO) verfeinert, um langfristige Belohnungen zu maximieren.

Umfangreiche Experimente an synthetischen und realen Datensätzen zeigen, dass RL‑ASM sowohl in der Genauigkeit als auch in der Laufzeit die bisherigen Methoden übertrifft.

Der Quellcode ist öffentlich verfügbar unter https://github.com/KaiyangLi1992/RL-ASM.