TREE-G: Entscheidungsbäume, die Graph Neural Networks herausfordern

Bei der Behandlung tabellarischer Daten sind Entscheidungsbäume aufgrund ihrer hohen Genauigkeit, der einfachen Anwendbarkeit und ihrer erklärbaren Eigenschaften eine gängige Wahl. Bei graphenstrukturierten Daten ist jedoch unklar, wie sie effektiv eingesetzt werden können, insbesondere in einer Weise, die die topologische Struktur der Graphen mit den tabellarischen Merkmalen der Knoten verbindet. Um diese Herausforderung anzugehen, stellen wir TREE-G vor. TREE-G modifiziert herkömmliche Entscheidungsbäume durch Einführung einer neuartigen Spaltfunktion, die speziell für graphenbasierte Daten entwickelt wurde. Diese Spaltfunktion berücksichtigt nicht nur die Knotenmerkmale und die topologische Information, sondern nutzt auch einen innovativen Zeigermechanismus, der es ermöglicht, dass Spaltknoten Informationen aus vorherigen Spaltvorgängen nutzen können. Dadurch passt sich die Spaltfunktion der jeweiligen Vorhersageaufgabe und dem vorliegenden Graphen an. Wir analysieren die theoretischen Eigenschaften von TREE-G und belegen dessen Vorteile empirisch an mehreren Benchmarks für Graph- und Knotenvorhersage. In diesen Experimenten übertrifft TREE-G konsistent andere baumbasierte Modelle und erreicht oft auch Leistungen, die jene anderer Graph-Lern-Algorithmen wie Graph Neural Networks (GNNs) oder Graph-Kerne deutlich übersteigen, manchmal sogar mit großem Abstand. Darüber hinaus sind die TREE-G-Modelle und ihre Vorhersagen erklären und visualisieren.