Original title: Aplikace metody učení bez učitele na hledání podobných grafů
Translated title: Application of Unsupervised Learning Methods in Graph Similarity Search
Authors: Sabo, Jozef ; Burgetová, Ivana (referee) ; Křivka, Zbyněk (advisor)
Document type: Master’s theses
Year: 2021
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Cieľom tejto diplomovej práce bolo v spolupráci s firmou Avast navrhnúť systém, ktorý dokáže dolovať znalosti z databázy grafov pomocou metód učenia bez učiteľa. Grafy, určené pre dolovanie, popisujú chovanie počítačových systémov a do databázy prichádzajú anonymne od používateľov softvérových produktov firmy. Grafom v databáze je možné priradiť jednu z dvoch tried: čistý graf alebo malware (škodlivý) graf. Úlohou navrhnutého samoučiacieho systému je nad grafovou databázou nájsť zhluky grafov, v ktorých sa triedy grafov nemiešajú. Zhluky grafov, v ktorých sa nachádza iba jedna trieda grafov, sa dajú interpretovať ako rôzne typy čistých alebo malware grafov a sú užitočným zdrojom ďalších analýz nad grafmi. Pre ohodnotenie kvality zhlukov bola navrhnutá vlastná metrika pomenovaná ako jednofarebnosť. Metrika hodnotí kvalitu zhlukov na základe toho ako veľmi sa v zhlukoch miešajú čisté a malware grafy. Najlepšie výsledky metrika dosiahla, keď boli vektorové reprezentácie grafov vytvorené modelom hlbokého učenia (variačným grafovým autoenkodérom s dvomi relačnými grafovými konvolučnými operátormi)  a pre zhlukovanie nad vektormi bola použitá bezparametrická metóda MeanShift. Goal of this master's thesis was in cooperation with the company Avast to design a system, which can extract knowledge from a database of graphs. Graphs, used for data mining, describe behaviour of computer systems and they are anonymously inserted into the company's database from systems of the company's products users. Each graph in the database can be assigned with one of two labels: clean or malware (malicious) graph. The task of the proposed self-learning system is to find clusters of graphs in the graph database, in which the classes of graphs do not mix. Graph clusters with only one class of graphs can be interpreted as different types of clean or malware graphs and they are a useful source of further analysis on the graphs. To evaluate the quality of the clusters, a custom metric, named as monochromaticity, was designed. The metric evaluates the quality of the clusters based on how much clean and malware graphs are mixed in the clusters. The best results of the metric were obtained when vector representations of graphs were created by a deep learning model (variational  graph autoencoder with two relation graph convolution operators) and the parameterless method MeanShift was used for clustering over vectors.
Keywords: Avast; clustering; communities detection; graph; graph embeddings; graph neural networks; node embeddings; unsupervised learning; Avast; detekcia komunít; graf; grafové neurónové siete; učenie bez učiteľa; vektorové reprezentácie grafov; vektorové reprezentácie uzlov; zhlukovanie

Institution: Brno University of Technology (web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library.
Original record: http://hdl.handle.net/11012/200141

Permalink: http://www.nusl.cz/ntk/nusl-445517


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses