Outlier detection in graphs using random walks
Creators: name: Μερκουρόπουλος, Βασίλειος Μάρκου
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Γράφοι
Ανίχνευση Ανωμαλιών
Τυχαίοι Περίπατοι
Graphs
Outlier Detection
Random Walks

description: This thesis focuses on anomaly detection in graphs, with an emphasis on applying and improving advanced random walk techniques, such as Node2Vec. The primary aim of the research is to develop and enhance anomaly detection algorithms that can identify anomalies with greater accuracy and effectiveness. To achieve this goal, the study utilizes two major datasets, FraudYelp and FraudAmazon, each characterized by unique graph features and distinct anomaly distributions. The work begins with the Independent Subgraphs Approach, which examines each subgraph individually, providing an initial understanding of their characteristics. Next, the Unified Graph Approach is proposed, where all subgraphs are combined into a single graph to enhance connectivity and provide richer information for anomaly analysis. The final approach, the Weighted Graph Approach, introduces edge weights computed based on Pearson correlation and edge frequency, offering a more sophisticated and precise method for anomaly detection. In the final phase, the thesis focuses on optimizing the Node2Vec algorithm by tuning hyperparameters such as the number of walks and walk length. Experimental results demonstrate significant improvements in detection accuracy for various top-N node selections. The study concludes with a comprehensive assessment of algorithm scalability and effectiveness, highlighting their practical implications for analyzing large graph datasets.
description: Αυτή η διπλωματική εργασία εστιάζει στην ανίχνευση ανωμαλιών σε γραφήματα, με στόχο την εφαρμογή και τη βελτίωση προηγμένων τεχνικών τυχαίων περιπάτων, όπως το Node2Vec. Η κύρια επιδίωξη της έρευνας είναι η ανάπτυξη και η βελτίωση αλγορίθμων ανίχνευσης ανωμαλιών που μπορούν να εντοπίσουν ανωμαλίες με μεγαλύτερη ακρίβεια και αποτελεσματικότητα. Για την επίτευξη αυτού του στόχου, η μελέτη αξιοποιεί δύο σημαντικά σύνολα δεδομένων, το FraudYelp και το FraudAmazon, τα οποία διακρίνονται για τις μοναδικές χαρακτηριστικές τους παραμέτρους και τις ιδιαίτερες κατανομές ανωμαλιών. Η εργασία ξεκινά με την ανάλυση της προσέγγισης Ανεξάρτητων Υπογραφών, η οποία εξετάζει κάθε υπογράφο μεμονωμένα, παρέχοντας μια αρχική κατανόηση των χαρακτηριστικών τους. Στη συνέχεια, η προσέγγιση Ενοποιημένου Γράφου προτείνεται, όπου όλοι οι υπογράφοι συνδυάζονται σε έναν ενιαίο γράφο, ενισχύοντας τη συνδεσιμότητα και παρέχοντας πλουσιότερες πληροφορίες για την ανάλυση ανωμαλιών. Η τελευταία προσέγγιση, η Προσέγγιση Ζυγισμένου Γράφου, εισάγει βάρη στις ακμές, τα οποία υπολογίζονται με βάση τη συσχέτιση Pearson και τη συχνότητα εμφάνισης των ακμών, προσφέροντας μια πιο εξελιγμένη και ακριβή μέθοδο εντοπισμού ανωμαλιών. Στην τελική φάση, η εργασία εστιάζει στη βελτιστοποίηση του αλγορίθμου Node2Vec, ρυθμίζοντας υπερπαραμέτρους όπως τον αριθμό των περιπάτων και το μήκος των περιπάτων. Τα αποτελέσματα των πειραμάτων δείχνουν σημαντικές βελτιώσεις στην ακρίβεια της ανίχνευσης για διάφορες επιλογές κορυφαίων κόμβων. Η μελέτη καταλήγει σε μια συνολική αξιολόγηση της κλιμάκωσης και της αποτελεσματικότητας των αλγορίθμων, αναδεικνύοντας τις πρακτικές τους επιπτώσεις στην ανάλυση μεγάλων γραφικών συνόλων.