Graph Clustering using Node Embeddings and k-NN Graphs
Creators: name: Αθανασιάδης, Γεώργιος Χαριλάου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Συσταδοποίηση
Ενσωματώσεις
Γράφος k-Πλησιέστερων Γειτόνων
Clustering
Embeddings
k-NN Graph

description: Clustering is a crucial data mining technique that groups similar data points together, enabling pattern recognition, data compression, and insightful data analysis in various fields. More often used in tabular data, clustering in graphs faces certain challenges and a variety of different approaches. A baseline method for hierarchical graph clustering utilizes the distance matrix of the graph as the dataset. In this thesis, we propose three alternative methods: The first alternative, instead of the computationally heavy distance matrix, utilizes node embeddings, low-dimensional vector representations of graph nodes that capture their structural and relational properties within the graph, enabling efficient graph analysis. Several different methods and algorithms for creating quality embeddings are experimented with, in terms of speed, scalability and quality of produced embeddings. In the second alternative, while maintaining the distance matrix as the dataset on which clustering is performed, we introduce the use of the initial graph’s K-Nearest Neighbors graph (k-NNG), where each node is only connected to its k nearest nodes. More importantly, the third alternative, combines node embeddings with the use of the initial graph’s K-Nearest Neighbors graph (k-NNG). Within this method, there is an additional two distinct experimental routes: in the first, various experiments with fixed values of k are conducted, whereas in the second, k is determined as a varying percentage of each node’s degree. In our study, we compare and contrast the methods as well as the several different cases within each method, in an experimental context using various metrics, some extrinsic, based on ground truth partitioning data, but primarily based on intrinsic, more objective cluster quality metrics. We aim to assess which method is superior in terms of clustering quality as well as scalability and computational cost.
description: Η συσταδοποίηση (clustering) είναι μια σημαντική τεχνική εξόρυξης δεδομένων που ομαδοποιεί παρόμοιες καταχωρήσεις δεδομένων, επιτρέποντας την αναγνώριση προτύπων, τη συμπίεση δεδομένων και την ανάλυση δεδομένων σε διάφορους τομείς. Η συσταδοποίηση, που χρησιμοποιείται συχνότερα σε δεδομένα πίνακα (tabular data), αντιμετωπίζει στα δεδομένα γράφων ορισμένες προκλήσεις και μια ποικιλία διαφορετικών προσεγγίσεων. Μια βασική μέθοδος για την ιεραρχική συσταδοποίηση γραφημάτων χρησιμοποιεί τον πίνακα αποστάσεων του γράφου ως σύνολο δεδομένων. Σε αυτή τη διατριβή προτείνουμε τρεις εναλλακτικές μεθόδους: Η πρώτη εναλλακτική, αντί για τον υπολογιστικά κοστοβόρο πίνακα αποστάσεων, χρησιμοποιεί ενσωματώσεις κόμβων (node embeddings), ήτοι διανυσματικές αναπαραστάσεις χαμηλών διαστάσεων κόμβων γραφημάτων που καταγράφουν τις δομικές και σχεσιακές ιδιότητές τους μέσα στο γράφημα, επιτρέποντας αποτελεσματική ανάλυση γραφήματος. Γίνονται διάφορα πειράματα με διάφορες μεθόδους και αλγορίθμους συσταδοποίησης και δημιουργίας ποιοτικών ενσωματώσεων (embeddings), όσον αφορά την ταχύτητα, την επεκτασιμότητα και την ποιότητα των παραγόμενων συστάδων. Στη δεύτερη εναλλακτική, ενώ διατηρούμε τον πίνακα απόστασης ως το σύνολο δεδομένων στο οποίο εκτελείται η συσταδοποίηση, εισάγουμε τη χρήση του γραφήματος Κ-Πλησιέστερων Γειτόνων (K-Nearest Neighbors) του αρχικού γραφήματος (k-NNG), όπου κάθε κόμβος συνδέεται μόνο με τους k πλησιέστερους κόμβους του. Η τρίτη εναλλακτική, συνδυάζει τις ενσωματώσεις κόμβων με τη χρήση του γραφήματος Κ Πλησιέστερων-Γειτόνων του αρχικού γραφήματος. Μέσα σε αυτή τη μέθοδο, υπάρχουν δύο επιπλέον διακριτές πειραματικές οδοί: στην πρώτη, διεξάγονται διάφορα πειράματα με σταθερές τιμές k, ενώ στη δεύτερη, το k προσδιορίζεται ως μεταβαλλόμενο ποσοστό του βαθμού (degree) κάθε κόμβου. Στη μελέτη μας, συγκρίνουμε και αντιπαραβάλλουμε τις μεθόδους καθώς και τις πολλές διαφορετικές υποπεριπτώσεις κάθε μεθόδου, σε ένα πειραματικό πλαίσιο όπου χρησιμοποιούνται διάφορες μετρικές, κάποιες εξωγενείς (extrinsic), βασισμένες σε παραδοχές (ground truth), αλλά κυρίως βασισμένες σε εγγενείς (intrinsic), πιο αντικειμενικές μετρικές ποιότητας συσταδοποίησης. Στόχος μας είναι να αξιολογήσουμε ποιά μέθοδος είναι καλύτερη όσον αφορά την ποιότητα συσταδοποίησης, καθώς και την επεκτασιμότητα και το υπολογιστικό κόστος.