Institutional Repository [SANDBOX]
Technical University of Crete
EN  |  EL

Search

Browse

My Space

Graph alignment algorithms

Papamanolis Anastasios

Simple record


URIhttp://purl.tuc.gr/dl/dias/E8A3E3FF-49EB-40C9-B34B-7F8BAFD5138A-
Identifierhttps://doi.org/10.26233/heallink.tuc.95673-
Languageen-
Extent63 pagesen
Extent1.2 megabytesen
TitleGraph alignment algorithmsen
TitleAλγόριθμoι αντιστοίχισης γράφωνel
CreatorPapamanolis Anastasiosen
CreatorΠαπαμανωλης Αναστασιοςel
Contributor [Thesis Supervisor]Liavas Athanasiosen
Contributor [Thesis Supervisor]Λιαβας Αθανασιοςel
Contributor [Committee Member]Karystinos Georgiosen
Contributor [Committee Member]Καρυστινος Γεωργιοςel
Contributor [Committee Member]Zervakis Michailen
Contributor [Committee Member]Ζερβακης Μιχαηλel
PublisherΠολυτεχνείο Κρήτηςel
PublisherTechnical University of Creteen
Academic UnitTechnical University of Crete::School of Electrical and Computer Engineeringen
Academic UnitΠολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστώνel
Content SummaryGraph alignment is a computational problem which aims to find a correspondence between vertices of graphs that minimizes their node and edge disagreements. This problem arises in many fields, such as computational biology, where finding conserved functional components between species can lead to gene-disease associations or drug discoveries, social sciences, where unveiling unique users on different platforms can remove bots, and computer vision for recognising objects. Compared with the exact graph (sub)isomorphism problem often considered in a theoretical setting, the inexact graph alignment problem is often cast as a Quadratic Assignment Problem (QAP), which has attracted significant research interest. This thesis presents a comprehensive review of the recent research activity concerning the global pairwise one-to-one alignment, detailing the methodologies and formulations of four state-of-the-art graph alignment algorithms. Specifically, Umeyama’s method solves the orthogonal relaxation of the QAP by using spectral embeddings, IsoRank applies random walks with restarts on the normalized Kronecker product graph, LowRank-Align solves a rank-k approximation of the orthogonal relaxation of the QAP using an alternating optimization framework, and CONE-Align uses embeddings obtained with the NetMF method and aligns their subspaces using a Wasserstein-Procrustes framework. To evaluate these algorithms, a standard experimental setup is adopted. A graph, G1, is aligned with a “noisy” and permuted version of itself, G2, in order to create an instance of the graph alignment problem. The noise level is the percentage of extra edges in G2 with respect to the total edges in G1. Only simple (unweighted, undirected, with no loops or multiple edges) graphs are considered. Several widely-used quality measures are used, such as the Node Correctness (NC), the Edge Correctness (EC), the Induced Conserved Structure (ICS), the Symmetric Substructure Score (S3), the Matched Neighborhood Consistency (MNC), and the wall time. The experiments suggest that CONE-Align performs well for both synthetic and real- world networks, LowRank-Align performs well in some occasions, Umeyama’s method has moderate performance, but steady over datasets, and IsoRank is the overall worst. As for the quality measures, MNC and S3 seem to be the most fair.en
Type of ItemΔιπλωματική Εργασίαel
Type of ItemDiploma Worken
Licensehttp://creativecommons.org/licenses/by/4.0/en
Date of Item2023-04-25-
Date of Publication2023-
SubjectGraph alignmenten
SubjectGraph matchingen
SubjectGraph embeddingen
SubjectSpectral embeddingen
SubjectData miningen
Bibliographic CitationAnastasios Papamanolis, "Graph alignment algorithms", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023en
Bibliographic CitationΑναστάσιος Παπαμανώλης, "Aλγόριθμoι αντιστοίχισης γράφων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2023el

Available Files

Services

Statistics