Επιβλέπων:                   Χ. Ζαρολιάγκης
Συνεπιβλέπων:            Σ. Κοντογιάννης

Η Νευρωνική Αλγοριθμική Συλλογιστική (Neural Algorithmic Reasoning – NAR) αποτελεί ένα σύγχρονο ερευνητικό πεδίο στη διασταύρωση της Μηχανικής Μάθησης και των κλασικών Αλγορίθμων. Βασικός στόχος της είναι η ανάπτυξη νευρωνικών μοντέλων τα οποία δεν περιορίζονται στην πρόβλεψη της εξόδου ενός προβλήματος, αλλά επιχειρούν να μάθουν και να αναπαράγουν την υπολογιστική διαδικασία ενός αλγορίθμου. Ιδιαίτερο ενδιαφέρον παρουσιάζουν προβλήματα γραφημάτων/δικτύων, όπως η εύρεση συντομότερων διαδρομών, η αναζήτηση κατά πλάτος, ο υπολογισμός ελάχιστου γεννητικού δέντρου και άλλα προβλήματα δυναμικού προγραμματισμού και συνδυαστικής βελτιστοποίησης.

Για την εκτέλεση τέτοιων αλγοριθμικών διαδικασιών χρησιμοποιούνται συχνά Νευρωνικά Δίκτυα Γραφημάτων (Graph Neural Networks – GNNs) και ειδικότερα μοντέλα ανταλλαγής μηνυμάτων σε Νευρωνικά Δίκτυα (Message-Passing Neural Networks – MPNNs). Η δομή των συγκεκριμένων μοντέλων παρουσιάζει φυσική αντιστοιχία με πολλούς αλγορίθμους γραφημάτων, καθώς η πληροφορία μεταδίδεται επαναληπτικά μεταξύ γειτονικών κόμβων με τρόπο ανάλογο προς τις διαδοχικές καταστάσεις ενός κλασικού αλγορίθμου. Το πρότυπο αξιολόγησης CLRS Algorithmic Reasoning Benchmark [1] έχει δημιουργήσει ένα ενιαίο πλαίσιο για τη μελέτη του προβλήματος, περιλαμβάνοντας διαφορετικές κατηγορίες κλασικών αλγορίθμων και παρέχοντας πληροφορία τόσο για την τελική έξοδο όσο και για τις ενδιάμεσες καταστάσεις εκτέλεσής τους.

Παρά την υψηλή ακρίβεια που μπορούν να επιτύχουν τα νευρωνικά μοντέλα σε δεδομένα παρόμοια με εκείνα της εκπαίδευσής τους, σημαντική ερευνητική πρόκληση αποτελεί η γενίκευσή τους σε δεδομένα εκτός της κατανομής εκπαίδευσης (Out-of-Distribution – OOD generalization). Για παράδειγμα, ένα μοντέλο που εκπαιδεύεται στην εκτέλεση ενός αλγορίθμου σε μικρά τυχαία γραφήματα ενδέχεται να παρουσιάζει σημαντική πτώση της απόδοσής του όταν εφαρμοστεί σε σημαντικά μεγαλύτερα γραφήματα ή σε γραφήματα διαφορετικής τοπολογίας, πυκνότητας ή κατανομής βαρών/κοστών. Το ζήτημα αυτό είναι ιδιαίτερα σημαντικό, καθώς ένας κλασικός αλγόριθμος ορίζεται ανεξάρτητα από τη συγκεκριμένη κατανομή των στιγμιοτύπων στα οποία εφαρμόζεται. Συνεπώς, η ικανότητα ενός νευρωνικού μοντέλου να γενικεύει σε τέτοιες μεταβολές αποτελεί βασικό κριτήριο του κατά πόσο έχει μάθει ουσιαστικά την υποκείμενη αλγοριθμική διαδικασία και όχι μόνο στατιστικά χαρακτηριστικά των δεδομένων εκπαίδευσης.

Για την αντιμετώπιση του προβλήματος έχουν προταθεί διαφορετικές προσεγγίσεις. Μεταξύ αυτών περιλαμβάνονται τεχνικές αιτιακής κανονικοποίησης και παραγωγής κατάλληλων παραλλαγών των δεδομένων, οι οποίες ενισχύουν το αναλλοίωτο των ενδιάμεσων υπολογισμών [2], καθώς και αρχιτεκτονικές που περιορίζουν τις εσωτερικές καταστάσεις των νευρωνικών μοντέλων σε διακριτές αλγοριθμικές καταστάσεις [3]. Οι προσεγγίσεις αυτές έχουν παρουσιάσει σημαντικές βελτιώσεις στη γενίκευση εκτός κατανομής, χωρίς ωστόσο να εξαλείφουν το γενικότερο ερώτημα του πότε, γιατί, και υπό ποιες συνθήκες ένα νευρωνικό δίκτυο μπορεί να μάθει έναν αλγόριθμο και να γενικεύει αξιόπιστα σε νέα στιγμιότυπα.

Στο πλαίσιο της διπλωματικής εργασίας θα μελετηθεί η ικανότητα νευρωνικών μοντέλων γραφημάτων να μαθαίνουν και να εκτελούν κλασικούς αλγορίθμους, με ιδιαίτερη έμφαση στη γενίκευση επί στιγμιοτύπων διαφορετικών από εκείνα που χρησιμοποιήθηκαν κατά την εκπαίδευση. Η μελέτη μπορεί να περιλαμβάνει μεταβολές στο μέγεθος και στην τοπολογία των γραφημάτων, στην πυκνότητα των ακμών και στις κατανομές των αριθμητικών χαρακτηριστικών τους. Παράλληλα, θα διερευνηθούν μέθοδοι βελτίωσης της γενίκευσης, όπως κατάλληλες στρατηγικές εκπαίδευσης, αξιοποίηση των ενδιάμεσων καταστάσεων του εκτελούμενου αλγορίθμου, ή αυτόματη αναζήτηση στιγμιοτύπων στα οποία το νευρωνικό μοντέλο αποτυγχάνει.

Στο πλαίσιο της διπλωματικής αυτής ζητούνται:

• Η μελέτη και επισκόπηση της τρέχουσας τεχνολογικής και ερευνητικής στάθμης στη Νευρωνική Αλγοριθμική Συλλογιστική, με έμφαση στα Νευρωνικά Δίκτυα Γραφημάτων και στο πρόβλημα της γενίκευσης στην εκμάθηση εκτός κατανομής εκπαίδευσης.
• Η μελέτη και υλοποίηση αντιπροσωπευτικών νευρωνικών μοντέλων για την εκμάθηση κλασικών αλγορίθμων γραφημάτων, αξιοποιώντας πρότυπα αξιολόγησης όπως το CLRS Algorithmic Reasoning Benchmark [1].
• Η ανάπτυξη και υλοποίηση μιας μεθόδου με στόχο τη βελτίωση της γενίκευσης των νευρωνικών μοντέλων σε μεγαλύτερα ή δομικά διαφορετικά στιγμιότυπα. Ενδεικτικές κατευθύνσεις αποτελούν η προσαρμοστική διαδικασία εκπαίδευσης, η αξιοποίηση αλγοριθμικών ιδιοτήτων και ενδιάμεσων καταστάσεων, ή η αναζήτηση και αξιοποίηση δύσκολων παραδειγμάτων και αντιπαραδειγμάτων.
• Η εκτενής πειραματική και συγκριτική αξιολόγηση της προτεινόμενης προσέγγισης σε διαφορετικούς αλγορίθμους και οικογένειες γραφημάτων, εξετάζοντας τη συμπεριφορά των μοντέλων ως προς το μέγεθος, την τοπολογία και άλλα χαρακτηριστικά των στιγμιοτύπων.

Ενδεικτική Βιβλιογραφία

[1] Petar Veličković, Adrià Puigdomènech Badia, David Budden, Razvan Pascanu, Andrea Banino, Misha Dashevskiy, Raia Hadsell, and Charles Blundell: The CLRS Algorithmic Reasoning Benchmark. Proceedings of the 39th International Conference on Machine Learning (ICML), PMLR 162, 2022., https://proceedings.mlr.press/v162/velickovic22a.html

[2] Beatrice Bevilacqua, Kyriacos Nikiforou, Borja Ibarz, Ioana Bica, Michela Paganini, Charles Blundell, Jovana Mitrovic, and Petar Veličković: Neural Algorithmic Reasoning with Causal Regularisation. Proceedings of the 40th International Conference on Machine Learning (ICML), PMLR 202, 2023. https://arxiv.org/abs/2302.10258 .

[3] Gleb Rodionov and Liudmila Prokhorenkova: Discrete Neural Algorithmic Reasoning. Proceedings of the 42nd International Conference on Machine Learning (ICML), PMLR 267, 2025. https://proceedings.mlr.press/v267/rodionov25a.html

[4] Solveig Wittig, Antonis Vasileiou, Robert R. Nerem, Timo Stoll, Floris Geerts, Yusu Wang, and Christopher Morris: Which Algorithms Can Graph Neural Networks Learn? 2026. https://doi.org/10.48550/arXiv.2602.13106