Labeling Trick: Eine Theorie zur Verwendung von Graph Neural Networks für die Mehrknoten-Darstellungslernung

In dieser Arbeit stellen wir eine Theorie zur Verwendung von Graph-Neuralen Netzen (GNNs) für die Lernrepräsentation von mehreren Knoten vor (wobei es darum geht, eine Repräsentation für eine Menge von mehr als einem Knoten zu lernen, wie z.B. einen Link). Wir wissen, dass GNNs entwickelt wurden, um Repräsentationen einzelner Knoten zu erlernen. Wenn wir eine Repräsentation für eine Menge von mehreren Knoten lernen möchten, ist es in früheren Arbeiten üblich, die durch ein GNN erlernten Einzelknotenrepräsentationen direkt zu aggregieren, um eine gemeinsame Knotenmengenrepräsentation zu erhalten. In dieser Arbeit zeigen wir eine grundlegende Einschränkung dieses Ansatzes, nämlich die Unfähigkeit, die Abhängigkeiten zwischen den Knoten in der Menge zu erfassen. Wir argumentieren, dass das direkte Aggregieren individueller Knotenrepräsentationen nicht zu einer effektiven gemeinsamen Repräsentation für mehrere Knoten führt.Daraufhin bemerken wir, dass einige erfolgreiche frühere Arbeiten im Bereich des Lernens von Mehrknotenrepräsentationen, einschließlich SEAL, Distance Encoding und ID-GNN, alle Node-Labeling verwendet haben. Diese Methoden beschriften zunächst die Knoten im Graph gemäß ihren Beziehungen zur Zielknotenmenge, bevor sie ein GNN anwenden. Anschließend werden die in dem beschrifteten Graph erlernten Knotenrepräsentationen zu einer Knotenmengenrepräsentation aggregiert. Durch die Untersuchung ihrer internen Mechanismen vereinigen wir diese Node-Labeling-Techniken in eine einzige und allgemeinste Form – das Labeling-Trick. Wir beweisen, dass mit dem Labeling-Trick ein hinreichend ausdrucksstarkes GNN die ausdrucksstärksten Knotenmengenrepräsentationen lernt und damit prinzipiell jede gemeinsame Lernaufgabe über Knotensätze lösen kann.Experimente an einem wichtigen Zweiknotenaufgaben-Lernproblem, der Link-Vorhersage (Link Prediction), bestätigten unsere Theorie. Unsere Arbeit erklärt die überlegene Leistung der früher auf Node-Labeling basierenden Methoden und legt eine theoretische Grundlage für die Verwendung von GNNs bei der Lernrepräsentation von Mehrknotensätzen.