Ένας νέος τρόπος εκπαίδευσης AI σε δεδομένα γραφημάτων χωρίς επίβλεψη

Συγγραφείς: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ΠΕΡΙΛΗΨΗ Η πληρότητα του περιεχομένου διαφόρων δικτύων πληροφοριών, όπως τα κοινωνικά δίκτυα και τα δίκτυα επικοινωνίας, παρέχει την άνευ προηγουμένου δυνατότητα για την εκμάθηση υψηλής ποιότητας εκφραστικών αναπαραστάσεων χωρίς εξωτερική επίβλεψη. Αυτή η εργασία διερευνά πώς να διατηρηθεί και να εξαχθεί η άφθονη πληροφορία από δεδομένα με δομή γράφου στον χώρο ενσωμάτωσης με μη επιβλεπόμενο τρόπο. Για το σκοπό αυτό, προτείνουμε μια νέα έννοια, το Γραφικό Αμοιβαίο Πληροφοριακό (Graphical Mutual Information - GMI), για τη μέτρηση της συσχέτισης μεταξύ των γράφων εισόδου και των υψηλού επιπέδου κρυφών αναπαραστάσεων. Το GMI γενικεύει την ιδέα των συμβατικών υπολογισμών αμοιβαίας πληροφορίας από τον διανυσματικό χώρο στον τομέα του γράφου, όπου η μέτρηση αμοιβαίας πληροφορίας από δύο πτυχές των χαρακτηριστικών κόμβων και της τοπολογικής δομής είναι απαραίτητη. Το GMI παρουσιάζει πολλά οφέλη: Πρώτον, είναι αναλλοίωτο στην ισομορφική μετατροπή των γράφων εισόδου — ένας αναπόφευκτος περιορισμός σε πολλούς υπάρχοντες αλγόριθμους εκμάθησης αναπαραστάσεων γράφων · Επιπλέον, μπορεί να εκτιμηθεί και να μεγιστοποιηθεί αποτελεσματικά με τρέχουσες μεθόδους εκτίμησης αμοιβαίας πληροφορίας, όπως το MINE · Τέλος, η θεωρητική μας ανάλυση επιβεβαιώνει την ορθότητα και την ορθολογικότητά του. Με τη βοήθεια του GMI, αναπτύσσουμε ένα μη επιβλεπόμενο μοντέλο μάθησης που εκπαιδεύεται μεγιστοποιώντας το GMI μεταξύ της εισόδου και της εξόδου ενός κωδικοποιητή γράφου νευρωνικών δικτύων. Εκτεταμένα πειράματα σε επαγωγική καθώς και επαγωγική ταξινόμηση κόμβων και πρόβλεψη συνδέσμων αποδεικνύουν ότι η μέθοδός μας υπερτερεί των σύγχρονων μη επιβλεπόμενων αντιστοίχων, και ακόμη και κάποιες φορές υπερβαίνει την απόδοση των επιβλεπόμενων. 1 ΕΙΣΑΓΩΓΗ Για την επίτευξη αξιόπιστης ποσοτικής ανάλυσης για ποικίλα δίκτυα πληροφοριών, η εκμάθηση αναπαραστάσεων υψηλής ποιότητας για δεδομένα με δομή γράφου έχει γίνει ένα από τα τρέχοντα συναρπαστικά θέματα. Πρόσφατες μέθοδοι για την επίτευξη αυτού του στόχου, που γενικά κατηγοριοποιούνται ως Γραφικά Νευρωνικά Δίκτυα (Graph Neural Networks - GNNs), έχουν σημειώσει αξιοσημείωτες προόδους σε ένα μεγάλο αριθμό εργασιών μάθησης, όπως η ταξινόμηση κόμβων [ , , ], η πρόβλεψη συνδέσμων [ , , ], η ευθυγράμμιση γράφων [ , , ], η μοριακή παραγωγή [ , , ], για να αναφέρουμε μερικές. Παρόλο που υπάρχει γόνιμη πρόοδος, η εκπαίδευση GNNs σε υπάρχουσες προσεγγίσεις απαιτεί συνήθως κάποια μορφή επίβλεψης. Αναμφίβολα, οι πληροφορίες επισήμανσης είναι δαπανηρές στην απόκτησή τους — χειροκίνητη επισήμανση ή πληρωμή για άδεια, και είναι ακόμη αδύνατες να επιτευχθούν λόγω της πολιτικής απορρήτου. Για να μην αναφέρουμε ότι η αξιοπιστία των δεδομένων επισημάνσεων είναι μερικές φορές αμφισβητήσιμη. Ως εκ τούτου, το πώς να επιτευχθεί υψηλής ποιότητας αναπαράσταση γράφου χωρίς επίβλεψη καθίσταται απαραίτητο για πολλές πρακτικές περιπτώσεις, κάτι που παρακινεί τη μελέτη αυτής της εργασίας. 35 42 50 26 27 49 12 19 43 4 5 46 Εξετάζοντας προσεκτικά τα συλλεγόμενα δεδομένα με δομή γράφου, διαπιστώνουμε ότι προέρχονται γενικά από διάφορες πηγές, όπως κοινωνικά δίκτυα, δίκτυα παραπομπών και δίκτυα επικοινωνίας, όπου υπάρχουν τεράστιες ποσότητες πληροφοριών περιεχομένου και σύνδεσης. Για παράδειγμα, δεδομένα σε πολλές κοινωνικές πλατφόρμες όπως το Twitter, το Flickr και το Facebook περιλαμβάνουν χαρακτηριστικά χρηστών, π.χ., βασικές προσωπικές λεπτομέρειες, κείμενα, εικόνες, IP, και τις σχέσεις τους, π.χ., αγοράζοντας το ίδιο αντικείμενο, όντας φίλοι. Αυτά τα πλούσια δεδομένα περιεχομένου είναι επαρκή για να υποστηρίξουν επακόλουθες εργασίες εξόρυξης χωρίς πρόσθετη καθοδήγηση: αν δύο οντότητες εμφανίζουν ακραία ομοιότητα στα χαρακτηριστικά, υπάρχει υψηλή πιθανότητα σύνδεσης μεταξύ τους (πρόβλεψη συνδέσμων) και είναι πιθανό να ανήκουν στην ίδια κατηγορία (ταξινόμηση) · αν δύο οντότητες συνδέονται και οι δύο με την ίδια οντότητα, πιθανώς έχουν παρόμοια χαρακτηριστικά (σύσταση). Υπό αυτή την έννοια, η διατήρηση και εξαγωγή όσο το δυνατόν περισσότερων πληροφοριών από δίκτυα πληροφοριών στον χώρο ενσωμάτωσης διευκολύνει την εκμάθηση υψηλής ποιότητας εκφραστικών αναπαραστάσεων που παρουσιάζουν επιθυμητή απόδοση σε εργασίες εξόρυξης χωρίς καμία μορφή επίβλεψης. Η μη επιβλεπόμενη εκμάθηση αναπαραστάσεων γράφων είναι μια πιο ευνοϊκή επιλογή σε πολλές περιπτώσεις λόγω της ελευθερίας από τις επισημάνσεις, ειδικά όταν σκοπεύουμε να επωφεληθούμε από μεγάλης κλίμακας μη επισημασμένα δεδομένα στον κόσμο. Για να κληρονομήσουμε πλήρως τις πλούσιες πληροφορίες στους γράφους, σε αυτήν την εργασία, εκτελούμε ενσωμάτωση γράφου βασισμένη στη μεγιστοποίηση Αμοιβαίας Πληροφορίας (Mutual Information - MI), εμπνευσμένοι από την εμπειρική επιτυχία της μεθόδου Deep Info-Max [ ] που λειτουργεί σε εικόνες. Για να ανακαλύψουμε χρήσιμες αναπαραστάσεις, το Deep InfoMax εκπαιδεύει τον κωδικοποιητή για να μεγιστοποιήσει το MI μεταξύ των εισόδων του (δηλ., οι εικόνες) και των εξόδων του (δηλ., τα κρυφά διανύσματα). Όταν εξετάζουμε το Deep InfoMax στον τομέα του γράφου, ο πρώτος λίθος που πρέπει να πατήσουμε είναι πώς να ορίσουμε το MI μεταξύ γράφων και κρυφών διανυσμάτων, ενώ η τοπολογία των γράφων είναι πιο περίπλοκη από τις εικόνες (βλ. Σχήμα Μια από τις προκλήσεις είναι να διασφαλιστεί ότι η συνάρτηση MI μεταξύ της κρυφής αναπαράστασης κάθε κόμβου και των χαρακτηριστικών εισόδου της γειτονιάς του υπακούει στην ιδιότητα συμμετρίας, ή ισοδύναμα, είναι αναλλοίωτη στις μεταθέσεις των γειτονιών. Ως μια πρόσφατη εργασία που εξετάζει το MI, το Deep Graph Infomax (DGI) [ ] ενσωματώνει πρώτα έναν γράφο εισόδου και έναν αντίστοιχο παραμορφωμένο γράφο, στη συνέχεια συνοψίζει τον γράφο εισόδου ως διάνυσμα μέσω μιας συνάρτησης ανάγνωσης, και τέλος μεγιστοποιεί το MI μεταξύ αυτής της διανυσματικής σύνοψης και των κρυφών αναπαραστάσεων διακρίνοντας τον γράφο εισόδου (θετικό δείγμα) από τον παραμορφωμένο γράφο (αρνητικό δείγμα). Το Σχήμα δίνει μια εύκολα κατανοητή επισκόπηση του DGI. Η μεγιστοποίηση αυτού του είδους MI αποδεικνύεται ισοδύναμη με τη μεγιστοποίηση του MI μεταξύ των χαρακτηριστικών εισόδου των κόμβων και των κρυφών διανυσμάτων, αλλά αυτή η ισοδυναμία ισχύει υπό ορισμένες προκαθορισμένες συνθήκες, π.χ., η συνάρτηση ανάγνωσης πρέπει να είναι ενέσιμη, κάτι που φαίνεται να είναι υπερβολικά περιοριστικό σε πραγματικές περιπτώσεις. Ακόμη και αν εγγυηθούμε την ύπαρξη ενέσιμης συνάρτησης ανάγνωσης με κάποιο σχεδιασμό, π.χ., αυτό που χρησιμοποιείται στο DeepSets [ ], η ενέσιμη ικανότητα της συνάρτησης ανάγνωσης επηρεάζεται επίσης από το πώς εκπαιδεύονται οι παράμετροί της. Αυτό σημαίνει ότι μια αρχικά ενέσιμη συνάρτηση κινδυνεύει ακόμη να γίνει μη ενέσιμη εάν εκπαιδευτεί χωρίς καμία εξωτερική επίβλεψη. Και αν η συνάρτηση ανάγνωσης δεν είναι ενέσιμη, οι πληροφορίες του γράφου εισόδου που περιέχονται σε μια διανυσματική σύνοψη θα μειωθούν καθώς αυξάνεται το μέγεθος του γράφου. Επιπλέον, το DGI παραμένει σε μια μεγιστοποίηση MI αμοιβαίας πληροφορίας σε αδρή κλίμακα γράφου/τμήματος. Επομένως, στο DGI, δεν υπάρχει εγγύηση ότι ο κωδικοποιητής μπορεί να αποστάξει επαρκείς πληροφορίες από τα δεδομένα εισόδου, καθώς ποτέ δεν συσχετίζει λεπτομερώς τις κρυφές αναπαραστάσεις με τις αρχικές εισόδους τους. 20 1). 41 1 47 Σε αυτήν την εργασία, προτείνουμε έναν πιο απλό τρόπο για να εξετάσουμε το MI όσον αφορά τις γραφικές δομές χωρίς τη χρήση καμίας συνάρτησης ανάγνωσης ή παραμόρφωσης. Παράγουμε άμεσα το MI συγκρίνοντας την είσοδο (δηλ., τον υπο-γράφο που αποτελείται από τη γειτονιά εισόδου) και την έξοδο (δηλ., την κρυφή αναπαράσταση κάθε κόμβου) του κωδικοποιητή. Και, ενδιαφέρον, οι θεωρητικές μας παραγωγές δείχνουν ότι το άμεσα διατυπωμένο MI μπορεί να αποσυντεθεί σε ένα σταθμισμένο άθροισμα τοπικών MIs μεταξύ κάθε χαρακτηριστικού γειτονιάς και του κρυφού διανύσματος. Με αυτόν τον τρόπο, έχουμε αποσυνθέσει τα χαρακτηριστικά εισόδου και έχουμε καταστήσει τον υπολογισμό MI διαχειρίσιμο. Επιπλέον, αυτή η μορφή MI μπορεί εύκολα να ικανοποιήσει την ιδιότητα συμμετρίας εάν προσαρμόσουμε τις τιμές των βαρών. Αναβάλλουμε περισσότερες λεπτομέρειες στην § Καθώς το παραπάνω MI μετριέται κυρίως στο επίπεδο των χαρακτηριστικών των κόμβων, το ονομάζουμε Feature Mutual Information (FMI). 3.1. Δύο εναπομείναντα ζητήματα σχετικά με το FMI: **1.** τα συνδυαστικά βάρη είναι ακόμη άγνωστα και **2.** δεν λαμβάνει υπόψη την τοπολογία (δηλ., τα χαρακτηριστικά των ακμών). Για να αντιμετωπίσουμε περαιτέρω αυτά τα δύο ζητήματα, ορίζουμε τη μέτρηση Graphical Mutual Information (GMI) με βάση το FMI. Συγκεκριμένα, το GMI εφαρμόζει μια διαισθητική ανάθεση τιμών θέτοντας τα βάρη στο FMI ίσα με την εγγύτητα μεταξύ κάθε γείτονα και του κόμβου-στόχου στον χώρο αναπαράστασης. Όσον αφορά τη διατήρηση της τοπολογικής πληροφορίας, το GMI συσχετίζει περαιτέρω αυτά τα βάρη με τα χαρακτηριστικά των ακμών εισόδου μέσω ενός επιπρόσθετου όρου αμοιβαίας πληροφορίας. Το προκύπτον GMI είναι τοπολογικά αναλλοίωτο και επίσης υπολογίσιμο με Mutual Information Neural Estimation (MINE) Οι κύριες συνεισφορές της εργασίας μας είναι οι εξής: . • : Γενικεύουμε την συμβατική εκτίμηση MI στον τομέα του γράφου και προτείνουμε μια νέα έννοια Graphical Mutual Information (GMI) αναλόγως. Το GMI είναι απαλλαγμένο από Έννοιες τον πιθανό κίνδυνο που προκαλείται από τη συνάρτηση ανάγνωσης, καθώς εξετάζει το MI μεταξύ γράφων εισόδου και υψηλού επιπέδου ενσωματώσεων με έναν άμεσο τρόπο. • : Μέσω της θεωρητικής μας ανάλυσης, δίνουμε μια διαχειρίσιμη και υπολογίσιμη μορφή GMI που αποσυνθέτει το Αλγόριθμοι συνολικό GMI σε ένα σταθμισμένο άθροισμα τοπικών MIs. Με τη βοήθεια της μεθόδου MINE, η μεγιστοποίηση GMI μπορεί εύκολα να επιτευχθεί σε επίπεδο κόμβου. • : Επιβεβαιώνουμε την αποτελεσματικότητα του GMI σε διάφορες δημοφιλείς εργασίες ταξινόμησης κόμβων και πρόβλεψης συνδέσμων Πειραματικά Ευρήματα συμπεριλαμβανομένων τόσο επαγωγικών όσο και επάγουσων. Τα πειράματα δείχνουν ότι η μέθοδός μας προσφέρει υποσχόμενη απόδοση σε μια ποικιλία σημείων αναφοράς και ακόμη και μερικές φορές υπερβαίνει την απόδοση των επιβλεπόμενων αντιστοίχων. 2 ΣΧΕΤΙΚΗ ΕΡΓΑΣΙΑ Σύμφωνα με την εστίαση της εργασίας μας, ανασκοπούμε συνοπτικά προηγούμενες εργασίες στους δύο ακόλουθους τομείς: **1.** εκτίμηση αμοιβαίας πληροφορίας, και **2.** νευρωνικά δίκτυα για μάθηση αναπαραστάσεων σε γράφους. . Καθώς η αρχή InfoMax [ ] υποστηρίζει τη μεγιστοποίηση του MI μεταξύ των εισόδων και εξόδων νευρωνικών δικτύων, πολλές μέθοδοι όπως οι αλγόριθμοι ICA [ , ] προσπαθούν να χρησιμοποιήσουν την ιδέα του MI στην μη επιβλεπόμενη εκμάθηση χαρακτηριστικών. Ωστόσο, αυτές οι μέθοδοι δεν μπορούν να γενικευτούν εύκολα σε βαθιά νευρωνικά δίκτυα λόγω της δυσκολίας στον υπολογισμό του MI μεταξύ υψηλών διαστάσεων συνεχών μεταβλητών. Ευτυχώς, η Mutual Information Neural Estimation (MINE) [ ] καθιστά εφικτή την εκτίμηση του MI σε βαθιά νευρωνικά δίκτυα εκπαιδεύοντας ένα στατιστικό δίκτυο ως διακριτή για να διακρίνει δείγματα που προέρχονται από την κοινή κατανομή και το γινόμενο των περιθωριακών κατανομών δύο τυχαίων μεταβλητών. Συγκεκριμένα, το MINE χρησιμοποιεί την ακριβή διατύπωση του MI βασισμένη στην KL, ενώ μια μη-KL εναλλακτική, η απόκλιση Jensen-Shannon (JSD) [ ], μπορεί να χρησιμοποιηθεί χωρίς την ανησυχία για την ακριβή τιμή του MI. Εκτίμηση αμοιβαίας πληροφορίας 3 1 21 2 30 . Με την ταχεία ανάπτυξη των γράφων νευρωνικών δικτύων (GNNs), ένας μεγάλος αριθμός αλγορίθμων εκμάθησης αναπαραστάσεων γράφων που βασίζονται σε GNNs έχουν προταθεί τα τελευταία χρόνια, οι οποίοι παρουσιάζουν ισχυρότερη απόδοση από τις παραδοσιακές μεθόδους ενσωμάτωσης βασισμένες σε τυχαίους περιπάτους και παραγοντοποίηση [ , , , , ]. Τυπικά, αυτές οι μέθοδοι μπορούν να χωριστούν σε επιβλεπόμενες και μη επιβλεπόμενες κατηγορίες. Μεταξύ αυτών, υπάρχει πλούσια βιβλιογραφία σχετικά με την επιβλεπόμενη εκμάθηση αναπαραστάσεων σε γράφους [ , , , , ]. Παρά την ποικιλία στην αρχιτεκτονική των δικτύων, επιτυγχάνουν εμπειρική επιτυχία με τη βοήθεια επισημάνσεων που συχνά δεν είναι προσβάσιμες σε ρεαλιστικά σενάρια. Σε αυτή την περίπτωση, οι μη επιβλεπόμενες μέθοδοι εκμάθησης γράφων [ , , ] έχουν ευρύτερη εφαρμογή. Η καλά γνωστή μέθοδος είναι το GraphSAGE [ ], ένα επαγωγικό πλαίσιο για την εκπαίδευση GNNs με ένα αντικειμενικό σκοπό βασισμένο σε τυχαίους περιπάτους στη μη επιβλεπόμενη ρύθμισή του. Και πρόσφατα, το DGI [ ] εφαρμόζει την ιδέα της μεγιστοποίησης MI στον τομέα του γράφου και επιτυγχάνει ισχυρή απόδοση με μη επιβλεπόμενο τρόπο. Ωστόσο, το DGI υλοποιεί μια μεγιστοποίηση χονδρόκοκκης κλίμακας (δηλ., μεγιστοποίηση MI σε επίπεδο γράφου/τμήματος) η οποία καθιστά δύσκολη τη διατήρηση της λεπτής πληροφορίας στον γράφο εισόδου. Επιπλέον, η συνθήκη που επιβάλλεται στη συνάρτηση ανάγνωσης που χρησιμοποιείται στο DGI φαίνεται να είναι υπερβολικά περιοριστική σε πραγματικές περιπτώσεις. Αντίθετα, εστιάζουμε στην αφαίρεση του περιορισμού της συνάρτησης ανάγνωσης και στην επίτευξη μεγιστοποίησης γραφικού αμοιβαίου πληροφοριακού σε επίπεδο κόμβου, μεγιστοποιώντας άμεσα το MI μεταξύ εισόδων και εξόδων του κωδικοποιητή. Οι αναπαραστάσεις που παράγονται από τη μέθοδό μας είναι πιο εξελιγμένες στη διατήρηση των πληροφοριών του γράφου εισόδου, η οποία διασφαλίζει τη δυνατότητά της για επακόλουθες εργασίες εξόρυξης γράφων, π.χ., ταξινόμηση κόμβων, πρόβλεψη συνδέσμων και σύσταση. Νευρωνικά δίκτυα για εκμάθηση αναπαραστάσεων γράφων 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 ΓΡΑΦΙΚΟ ΑΜΟΙΒΑΙΟ ΠΛΗΡΟΦΟΡΙΑΚΟ: ΟΡΙΣΜΟΣ ΚΑΙ ΜΕΓΙΣΤΟΠΟΙΗΣΗ Πριν προχωρήσουμε, παρέχουμε πρώτα τις προκαταρκτικές έννοιες που χρησιμοποιούνται σε αυτήν την εργασία. Έστω G = (V, E) ένας γράφος με N κόμβους vi ∈ V και ακμές eij = (vi , vj ) ∈ E. Τα χαρακτηριστικά των κόμβων, με υποτιθέμενη εμπειρική κατανομή πιθανότητας P, δίνονται από το X ∈ R = {x , · · · , x } όπου x ∈ R συμβολίζει το χαρακτηριστικό για τον κόμβο v . Ο πίνακας γειτνίασης A ∈ R αναπαριστά τις συνδέσεις των ακμών, όπου A που σχετίζεται με την ακμή e μπορεί να είναι ένας πραγματικός αριθμός ή ένα πολυδιάστατο διάνυσμα . N ×D 1 N i D i N ×N ij ij 1 Ο στόχος της εκμάθησης αναπαραστάσεων γράφου είναι να μάθουμε έναν κωδικοποιητή f : R × R → R , έτσι ώστε τα κρυφά διανύσματα H = {h , · · · , h } = f (X , A) να υποδεικνύουν αναπαραστάσεις υψηλού επιπέδου για όλους τους κόμβους. Η διαδικασία κωδικοποίησης μπορεί να ξαναγραφτεί σε μορφή ανά κόμβο. N ×D N ×N N ×D′ 1 N Για να το δείξουμε αυτό, ορίζουμε τα X και A για τον κόμβο i ως αντίστοιχα τα χαρακτηριστικά των γειτόνων του και τον αντίστοιχο πίνακα γειτνίασης i i υπό συνθήκη των γειτόνων. Συγκεκριμένα, X αποτελείται από όλους τους k-hop γείτονες του v με k ≤ l όταν ο κωδικοποιητής f είναι ένας l-στρωματικός GNN, και περιέχει τον ίδιο τον κόμβο i εάν προσθέσουμε περαιτέρω αυτο-βρόχους στον πίνακα γειτνίασης. Εδώ, ονομάζουμε τον υπο-γράφο που επεκτείνεται από τα X και A ως για τον κόμβο i, συμβολιζόμενο ως G . Με τον ορισμό του support graph, η κωδικοποίηση για κάθε κόμβο γίνεται h = f (G ) = f (X , A ). i i i i support graph i i i i i Στο Deep InfoMax [ ], ο στόχος εκπαίδευσης του κωδικοποιητή είναι να μεγιστοποιήσει το MI μεταξύ των εισόδων και των εξόδων του. Το MI εκτιμάται χρησιμοποιώντας ένα στατιστικό δίκτυο ως διακριτή για την ταξινόμηση δειγμάτων που προέρχονται από την κοινή κατανομή και εκείνων που προέρχονται από το γινόμενο των περιθωριακών κατανομών. Φυσικά, όταν προσαρμόζουμε την ιδέα του Deep InfoMax σε γράφους, θα πρέπει να μεγιστοποιήσουμε το MI μεταξύ της αναπαράστασης h και του support graph G για κάθε κόμβο. Συμβολίζουμε αυτό το γραφικό MI ως I (h ; G ). Ωστόσο, δεν είναι άμεσο να ορίσουμε I (h ; G ). Οι δυσκολίες είναι: Δυσκολίες στον ορισμό γραφικού αμοιβαίου πληροφοριακού. 20 i i i i i i • Το γραφικό MI θα πρέπει να είναι αναλλοίωτο ως προς τον δείκτη του κόμβου. Με άλλα λόγια, θα πρέπει να έχουμε I (h ; G ) = I (h′ ; G′ ), εάν τα G και G′ είναι ισόμορφα μεταξύ τους. i i i i i i • Εάν υιοθετήσουμε τη μέθοδο MINE για τον υπολογισμό του MI, ο διακριτής στο MINE δέχεται μόνο εισόδους σταθερού μεγέθους. Αυτό είναι ακόμη αδύνατο για τα G καθώς διαφορετικά G συνήθως περιλαμβάνουν διαφορετικό αριθμό κόμβων και επομένως είναι διαφορετικού μεγέθους. i i Για να ξεπεράσουμε το ζήτημα του ορισμού του γραφικού αμοιβαίου πληροφοριακού, αυτή η ενότητα ξεκινά εισάγοντας την έννοια του Feature Mutual Information (FMI) που βασίζεται μόνο στα χαρακτηριστικά των κόμβων. Με βάση την έμπνευση από την αποσύνθεση του FMI, ορίζουμε στη συνέχεια το Graphical Mutual Information (GMI), το οποίο λαμβάνει υπόψη τόσο τα χαρακτηριστικά των κόμβων όσο και 3.1 Feature Mutual Information Συμβολίζουμε την εμπειρική κατανομή πιθανότητας των χαρακτηριστικών κόμβων X ως p(X ), την πιθανότητα του h ως p(h ), και την κοινή κατανομή ως p(h , X ). Σύμφωνα με τη θεωρία πληροφορίας, το MI μεταξύ h και X ορίζεται ως i i i i i i i i Ενδιαφέρον, έχουμε το ακόλουθο θεώρημα αποσύνθεσης αμοιβαίας πληροφορίας για τον υπολογισμό I (h ; X ). i i Θεώρημα 1 (Αποσύνθεση Αμοιβαίας Πληροφορίας). Εάν η δεσμευμένη πιθανότητα p(h |X ) είναι πολλαπλασιαστική (βλ. ορισμό πολλαπλασιαστικής στο [ ]), η παγκόσμια αμοιβαία πληροφορία I (h ; X ) που ορίζεται στην Εξ. i i 36 i i (1) μπορεί να αποσυντεθεί ως σταθμισμένο άθροισμα τοπικών MIs, δηλαδή, ≤ ≤ 1 όπου, x είναι ο j-οστός γείτονας του κόμβου i, in είναι ο αριθμός όλων των στοιχείων στο X , και το βάρος w ικανοποιεί j i ij 1 w ij για κάθε j. Για να αποδείξουμε το παραπάνω θεώρημα, εισάγουμε πρώτα δύο λήμματα και έναν ορισμό. Λήμμα 1. Για οποιεσδήποτε τυχαίες μεταβλητές X, Y, και Z, έχουμε Με την αποσύνθεση στο Θεώρημα μπορούμε να υπολογίσουμε τη δεξιά πλευρά της Εξ. μέσω MINE, καθώς οι είσοδοι του διακριτή γίνονται πλέον τα ζεύγη (h , x ) των οποίων το μέγεθος παραμένει πάντα το ίδιο (δηλ., D' × D). Επιπλέον, μπορούμε να προσαρμόσουμε τα βάρη για να αντικατοπτρίσουμε την ισομορφική μετατροπή των γράφων εισόδου. Για παράδειγμα, εάν το X περιέχει μόνο γείτονες ενός hop του κόμβου i, η τοποθέτηση όλων των βαρών να είναι ίδια θα οδηγήσει στο ίδιο MI για τους κόμβους εισόδου σε διαφορετικές διατάξεις. 1, (2) i j i Παρά τα ορισμένα οφέλη της αποσύνθεσης, είναι δύσκολο να χαρακτηριστούν οι ακριβείς τιμές των βαρών, καθώς σχετίζονται με τις τιμές I (h ; x ) και τις υποκείμενες κατανομές πιθανότητάς τους. i j Ένας τετριμμένος τρόπος είναι να θέσουμε όλα τα βάρη ίσα με , τότε η μεγιστοποίηση της δεξιάς πλευράς της Εξ. ισοδυναμεί με τη μεγιστοποίηση του κατώτατου ορίου του I (h ; X ), μέσω του οποίου μεγιστοποιείται και το αληθινό FMI σε κάποιο βαθμό. Εκτός από αυτή τη μέθοδο, παρέχουμε επιπλέον μια πιο ενισχυμένη λύση εξετάζοντας τα βάρη ως εκπαιδεύσιμες προσοχές, η οποία είναι το θέμα της επόμενης υποενότητας. 1 (2) i i