Überwachte Gemeinschaftserkennung mit Liniengraph-Neuralnetzen

Traditionell kann die Erkennung von Gemeinschaften in Graphen mit Hilfe spektraler Methoden oder durch posteriore Inferenz unter probabilistischen grafischen Modellen gelöst werden. Indem man sich auf zufällige Graphenfamilien wie das stochastische Blockmodell konzentriert, hat die jüngste Forschung beide Ansätze vereint und sowohl statistische als auch berechnungsbezogene Erkennungsschwellen im Hinblick auf das Signal-Rausch-Verhältnis identifiziert. Durch die Umformulierung der Gemeinschaftserkennung als klassifizierungsproblem für Knoten in Graphen können wir sie auch aus einer Lernperspektive untersuchen. Wir stellen eine neue Familie von Graph Neural Networks (GNNs) vor, die Gemeinschaftserkennungsprobleme in einem überwachten Lernsetting lösen. Wir zeigen, dass diese GNNs auf datengetriebene Weise und ohne Zugang zu den zugrundeliegenden Generativmodellen die Leistung des Belief-Propagation-Algorithmus bei binären und multiklassigen stochastischen Blockmodellen erreichen oder sogar übertreffen können, was als Berechnungsschwelle gilt. Insbesondere schlagen wir vor, GNNs mit dem nicht-rückkehrenden Operator (non-backtracking operator), der auf dem Liniengraph der Kantenadjazenz definiert ist, zu erweitern. Unsere Modelle erzielen auch gute Ergebnisse bei realen Datensätzen. Darüber hinaus führen wir die erste Analyse des Optimierungslandschafts beim Training linearer GNNs für Gemeinschaftserkennungsprobleme durch und zeigen, dass unter bestimmten Vereinfachungen und Annahmen die Verlustwerte an lokalen und globalen Minima nicht weit auseinander liegen.