Detailansicht
From bit Flips to lottery tickets
expressivity in graph neural networks
Lorenz Kummer
Art der Arbeit
Dissertation
Universität
Universität Wien
Fakultät
Fakultät für Informatik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Doktoratsstudium der technischen Wissenschaften Informatik
Betreuer*innen
Nils Morten Kriege ,
Wilfried Gansterer
DOI
10.25365/thesis.80880
URN
urn:nbn:at:at-ubw:1-27681.54682.413678-7
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
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.
Abstract
(Englisch)
Complex objects such as molecules, proteins, or social networks can be naturally represented as graphs, and Graph Neural Networks (GNNs) have emerged as powerful tools for learning on such graph-structured data. GNNs thereby extend the applicability of established deep learning techniques to new domains such as financial and medical data analysis, or chem- and bioinformatics, leading to scenarios where efficient deployment is crucial. This increasing adoption leads to new security challenges, particularly around the interplay between efficiency-enhancing techniques such as quantization and expressivity, a key property of GNNs denoting their ability to distinguish graph structures, as well as the robustness of GNNs to malicious activity. In this thesis, we focus on the robustness of GNNs to malicious perturbations of their parameters, specifically examining their vulnerability under assumptions on their numerical representation and precision. Moreover, we discuss the importance of expressivity in the context of sparse GNN parameterizations and show that careless sparsification can lead to irrecoverable loss of predictive performance. We introduce the first Bit-Flip Attack (BFA) dedicated to maliciously perturbing the binary representation of the parameters of a quantized GNN. BFAs have so far been almost exclusively studied for Convolutional Neural Networks (CNNs). Our BFA is specifically designed to degrade a GNN’s ability to impair expressivity, highlighting that this fundamental property can be leveraged as a pivotal point by an attacker. Consequentially recognizing the importance of defending GNNs from BFAs, we offer the first study on how well existing defenses transferred from CNNs can protect quantized GNNs. We build upon the insights from these results and propose Crossfire. Crossfire is not only the first BFA defense dedicated to GNNs, but also the first BFA defense in general seeking to not only maintain the predictive performance of a target model or detect an attack, but to also verifiably restore the network to its pre-attack state. To further deepen our understanding of the robustness-expressivity relationship, we examine the vulnerability of a certain class of GNNs and establish formal criteria to characterize a GNN’s susceptibility to losing expressivity due to BFAs in a first theoretical analysis. This enables an analysis of the impact of homophily, graph structural variety, feature encoding, and activation functions on GNN robustness, leading to the discovery of particularly vulnerable configurations. Moreover, we derive theoretical bounds for the number of bit flips required to degrade GNN expressivity on a given dataset. Going beyond quantization to enhance efficiency and extending the established Lottery Ticket Hypothesis with new insights for GNNs, we identify expressivity as crucial for finding sparse initializations (winning tickets) that preserve the predictive performance. We establish conditions under which the expressivity of a sparsely initialized GNN matches that of the full network. Moreover, we subsequently show that an increased expressivity in the initialization potentially accelerates model convergence and improves generalization.
Schlagwörter
Schlagwörter
(Deutsch)
Graphen Graph Neuronale Netzwerke Maschinelles Nernen
Schlagwörter
(Englisch)
Graphs Graph Neural Networks Machine Learning
Autor*innen
Lorenz Kummer 
Haupttitel (Englisch)
From bit Flips to lottery tickets
Hauptuntertitel (Englisch)
expressivity in graph neural networks
Publikationsjahr
2025
Umfangsangabe
x, 109 Seiten : Illustrationen
Sprache
Englisch
Beurteiler*innen
Stephan Günnemann ,
Xiaolu Hou
Klassifikation
54 Informatik > 54.72 Künstliche Intelligenz
AC Nummer
AC17832381
Utheses ID
79214
Studienkennzahl
UA | 786 | 880 | |