DS-Span: Einfache, leistungsstarke Subgraph‑Mining‑Methode für Graph‑Embeddings

Graph‑Representation‑Learning versucht, komplexe, hochdimensionale Graphstrukturen in kompakte Vektorräume zu überführen, die sowohl die Topologie als auch die Semantik bewahren. Unter den verschiedenen Ansätzen bieten subgraphbasierte Methoden einen interpretierbaren Brückenschlag zwischen symbolischer Mustererkennung und kontinuierlichem Embedding‑Training. Allerdings leiden bestehende frequenz- oder diskriminative Subgraph‑Mining‑Methoden häufig unter redundanten Mehrphasen‑Pipelines, hohem Rechenaufwand und einer schwachen Verknüpfung zwischen den gefundenen Strukturen und ihrer diskriminativen Relevanz.

DS‑Span stellt ein einphasiges, diskriminatives Subgraph‑Mining‑Framework vor, das Musterwachstum, Pruning und supervisionsgesteuerte Bewertung in einem einzigen Durchlauf des Suchraums vereint. Durch einen coverage‑capped‑Eligibility‑Mechanismus wird die Exploration dynamisch begrenzt, sobald ein Graph ausreichend repräsentiert ist. Gleichzeitig lenkt ein information‑gain‑gesteuertes Auswahlkriterium die Suche auf Subgraphen, die eine starke Klassen­trennung ermöglichen, während Redundanz minimiert wird. Das daraus resultierende Subgraph‑Set bildet eine effiziente, interpretierbare Basis für nachgelagerte Graph‑Embeddings und Klassifikationen.

Umfangreiche Experimente an Standard‑Benchmarks zeigen, dass DS‑Span kompaktere und diskriminativere Subgraph‑Features erzeugt als vorherige Mehrphasen‑Methoden. Gleichzeitig erreicht es höhere oder gleichwertige Genauigkeiten bei deutlich reduziertem Laufzeitaufwand. Diese Ergebnisse unterstreichen das Potenzial eines einheitlichen, einphasigen diskriminativen Mining‑Ansatzes als Grundlage für skalierbares und interpretierbares Graph‑Representation‑Learning.