From bit Flips to lottery tickets

Komplexe Objekte wie Moleküle, Proteine oder soziale Netzwerke lassen sich natürlich als Graphen modellieren, für welche sich Graph Neural Networks (GNNs) als leistungsstarkes Lernverfahren etabliert haben. GNNs übertragen bewährte Deep-Learning-Techniken auf Bereiche wie die Analyse von Finanz- und Sozialnetzwerken oder medizinischen Daten sowie Chemie- und Bioinformatik und führen so zu Anwendungen, in denen Effizienz zentral ist. Diese zunehmende Verbreitung macht es notwendig, potenzielle Sicherheitsrisiken zu erforschen, insbesondere das Zusammenspiel von Expressivität, welche die Fähigkeit von GNNs bezeichnet, Graphstrukturen zu unterscheiden, und effizienzsteigernden Verfahren wie Quantisierung. In der vorliegenden Dissertation untersuchen wir die Robustheit von GNNs gegenüber gezielten Parameterstörungen und analysieren ihre Verwundbarkeit unter Annahmen über ihre numerische Darstellung und Präzision. Zudem diskutieren wir Expressivität im Kontext sparsifizierter GNN-Parametrisierungen und zeigen, dass unbedachte Sparsifizierung zu irreversiblen Einbußen der Vorhersageleistung führen kann. Wir stellen den ersten Angriff vor, der die binäre Darstellung quantisierter GNNs mittels Bit-Flip-Angriffen (BFAs) gezielt manipuliert, wobei es sich um ein Verfahren handelt, das bisher überwiegend für Convolutional Neural Networks (CNNs) untersucht wurde. Unser BFA zielt explizit darauf ab, die Expressivität eines GNN und damit seine Fähigkeit zur Unterscheidung von Graphstrukturen zu beeinträchtigen und zeigt damit, dass ein Angreifer diese fundamentale Eigenschaft ausnutzen kann. Angesichts dessen untersuchen wir erstmals, wie gut bestehende, von CNNs übertragene Abwehrmechanismen GNNs schützen. Basierend auf diesen Erkenntnissen entwickeln wir Crossfire, die erste speziell für quantisierte GNNs entwickelte BFA-Abwehr und auch die Erste, die nicht nur die Vorhersageleistung des Zielmodells erhält oder einen Angriff erkennt, sondern das Modell nachweislich in den Ursprungszustand zurückversetzen kann. Um das Bild zu vervollständigen, analysieren wir die Verwundbarkeit einer bestimmten Klasse von GNNs und entwickeln erste formale Kriterien, um die Anfälligkeit für Expressivitätsverluste durch BFAs zu charakterisieren. Dies ermöglicht eine Analyse des Einflusses von Homophilie, struktureller Vielfalt, Merkmalskodierung und Aktivierungsfunktionen auf die Robustheit von GNNs und führt zur Identifikation besonders verwundbarer Konfigurationen. Überdies leiten wir Schranken für die Anzahl an Bit-Flips ab, die nötig sind, um die Expressivität eines GNN auf einem Datensatz zu verringern. Über Quantisierung hinaus identifizieren wir die Expressivität sparsifizierter Subnetzwerke als Schlüssel, um sparsifizierte Initialisierungen („Winning Tickets“) zu finden, die die Vorhersageleistung erhalten. Wir geben Bedingungen an, unter denen die Expressivität eines derart initialisierten GNN jener des vollständigen Netzwerks entspricht. Zudem zeigen wir, dass höhere Expressivität in der Initialisierung potenziell Konvergenzverhalten und Generalisierungfähigkeit verbessert.