Neural Motif Counting in Uncertain Graphs
No Thumbnail Available
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Date
2024-05-20
Department
Major/Subject
Machine Learning, Data Science and Artificial Intelligence
Mcode
SCI3070
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
50 + 3
Series
Abstract
Motif counting is fundamental in graph analytic tasks (e.g., clustering and recommendation) but #P-hard. Recent research has focused on exploring and applying deep learning-based solutions to tackle this problem. However, these solutions assume a deterministic graph where edge existence is certain, which may not hold due to the measurement and statistical prediction errors. Meanwhile, existing methods for uncertain graphs still face considerable time costs. To address the above issues, we propose UnG-MoCha, a novel deep-learning approach to efficiently count motifs in uncertain graphs. UnG-MoCha extracts representative subgraphs via graph structure learning and learns graph and motif representations using hierarchical and classic graph neural networks, respectively. Canonical correlation analysis is used to exploit correlations between graph and motif representations, boosting accuracy. Experiments on real-world graphs demonstrate UnG-MoCha’s superior performance for scalable motif counting on uncertain graphs.Description
Supervisor
Jung, AlexThesis advisor
MA, ChenhaoKeywords
uncertain graphs, motif counting, graph neural network, deep learning