Efficient approaches to deal with oversmoothing in deep graph neural networks

Abstract

Graph Neural Networks (GNNs) have achieved remarkable success in a wide range of tasks involving relational data, yet their performance deteriorates as depth increases due to the phenomenon known as oversmoothing, where node representations become indistinguishable across layers. This thesis presents a systematic investigation into the oversmoothing problem and proposes novel theoretical and empirical approaches for mitigating it, thus enabling deeper and more expressive GNN architectures. We first introduce a novel layer-wise metric to quantify oversmoothing, providing theoretical bounds and practical detection tools. We show that oversmoothing is exacerbated when the number of weight matrices is coupled with the depth of message passing, and propose G-Reg, a regularization strategy that preserves representational diversity. Next, we study residual connections and analyze their limitations in enabling long-range node interactions. Our analysis shows that while residual-based models (e.g., APPNP, GCNII) resist oversmoothing on standard benchmarks, they fail in settings requiring deep and expressive propagation. To highlight this, we introduce a synthetic dataset tailored to evaluate the capability of a GNN to capture long-range dependencies. We then explore partial training in GNNs, where only a single layer is trained while others remain fixed. Our results reveal that increasing model width counteracts the lack of full training and significantly reduces oversmoothing, even in deep architectures. This approach matches or outperforms fully trained models in both standard and “cold start” scenarios. Building on this, we propose G-Init, a graph informed weight initialization strategy inspired by classical deep learning initialization techniques. G-Init accounts for graph topology and improves gradient flow in deep GNNs, reducing oversmoothing and enhancing classification performance across tasks.Finally, we investigate the impact of the activation function on oversmoothing. Our theoretical and empirical findings demonstrate that modifying the slope of ReLU leads to better representational diversity and improved performance in deep GNNs, without employing architectural changes or residual connections. Together, these contributions advance our understanding of depth-related challenges in GNNs and offer multiple scalable, theoretically grounded solutions to overcome oversmoothing. The findings support a rethinking of GNN design principles and pave the way for more robust architectures suited to real-world problems.

Τα Νευρωνικά Δίκτυα Γράφων (Graph Neural Networks - GNNs) έχουν επιδείξει εντυπωσιακή επιτυχία σε ένα ευρύ φάσμα εργασιών που αφορούν σχεσιακά δεδομένα. Ωστόσο, η απόδοσή τους επιδεινώνεται όσο αυξάνεται το βάθος τους, λόγω του φαινομένου της υπερ-εξομάλυνσης (oversmoothing), κατά το οποίο οι αναπαραστάσεις των κόμβων καθίστανται σχεδόν πανομοιότυπες μεταξύ των επιπέδων. Η παρούσα διατριβή παρουσιάζει μια συστηματική μελέτη του προβλήματος της υπερ-εξομάλυνσης και προτείνει νέες θεωρητικές και εμπειρικές προσεγγίσεις για την αντιμετώπισή του, καθιστώντας δυνατή τη σχεδίαση βαθύτερων και εκφραστικότερων αρχιτεκτονικών GNN. Πρώτον, εισάγουμε μία νέα μετρική σε κάθε επίπεδο (layer-wise) για τη μέτρηση της υπερ-εξομάλυνσης, συνοδευόμενη από θεωρητικά όρια και εργαλεία πρακτικής ανίχνευσης. Δείχνουμε ότι η υπερ-εξομάλυνση επιδεινώνεται όταν ο αριθμός των πινάκων βαρών συσχετίζεται με το βάθος της διάδοσης μηνυμάτων, και προτείνουμε το G-Reg, μια στρατηγική κανονικοποίησης που διατηρεί την ποικιλομορφία των αναπαραστάσεων. Στη συνέχεια, μελετούμε τις residual συνδέσεις και αναλύουμε τους περιορισμούς τους στην υποστήριξη αλληλεπιδράσεων μακρινής εμβέλειας μεταξύ κόμβων. Η ανάλυσή μας δείχνει ότι, παρόλο που τα μοντέλα με residuals (π.χ. APPNP, GCNII) αντιστέκονται στην υπερ-εξομάλυνση σε τυπικά benchmarks, αποτυγχάνουν σε σενάρια που απαιτούν βαθιά και εκφραστική διάδοση πληροφορίας. Για την ανάδειξη αυτού, εισάγουμε ένα συνθετικό σύνολο δεδομένων σχεδιασμένο να αξιολογεί την ικανότητα ενός GNN να αποτυπώνει μακρινές εξαρτήσεις. Έπειτα, εξετάζουμε τη μερική εκπαίδευση (partial training) σε GNNs, όπου εκπαιδεύεται μόνο ένα επίπεδο ενώ τα υπόλοιπα παραμένουν σταθερά. Τα αποτελέσματά μας αποκαλύπτουν ότι η αύξηση του πλάτους του μοντέλου αντισταθμίζει την απουσία πλήρους εκπαίδευσης και μειώνει σημαντικά την υπερ-εξομάλυνση, ακόμη και σε βαθιές αρχιτεκτονικές. Η προσέγγιση αυτή ισοφαρίζει ή ξεπερνά πλήρως εκπαιδευμένα μοντέλα τόσο σε τυπικά όσο και σε "cold start" σενάρια. Επιπρόσθετα, προτείνουμε τη μέθοδο G-Init, μια στρατηγική αρχικοποίησης βαρών ενημερωμένη από τη δομή του γράφου, εμπνευσμένη από κλασικές τεχνικές αρχικοποίησης για βαθιά νευρωνικά δίκτυα. Η G-Init λαμβάνει υπόψη την τοπολογία του γράφου και βελτιώνει τη ροή των gradients σε βαθιά GNNs, μειώνοντας την υπερ-εξομάλυνση και ενισχύοντας την επίδοση τους σε προβλήματα ταξινόμησης. Τέλος, διερευνούμε την επίδραση της συνάρτησης ενεργοποίησης στην υπερ-εξομάλυνση. Τα θεωρητικά και εμπειρικά ευρήματά μας δείχνουν ότι η τροποποίηση της κλίσης της ReLU οδηγεί σε καλύτερη ποικιλομορφία αναπαραστάσεων και βελτιωμένη απόδοση σε βαθιά GNNs, χωρίς να απαιτούνται αλλαγές στην αρχιτεκτονική ή residual συνδέσεις. Συνολικά, οι συνεισφορές αυτές προωθούν την κατανόησή μας σχετικά με τις προκλήσεις που σχετίζονται με το βάθος στα GNNs και προσφέρουν πολλαπλές, επεκτάσιμες και θεωρητικά τεκμηριωμένες λύσεις για την αντιμετώπιση της υπερ-εξομάλυνσης. Τα ευρήματα υποδεικνύουν την ανάγκη επαναπροσδιορισμού των αρχών σχεδίασης των βαθιών GNNs και ανοίγουν τον δρόμο για πιο αξιόπιστες αρχιτεκτονικές κατάλληλες για πραγματικές εφαρμογές.