Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/E8A3E3FF-49EB-40C9-B34B-7F8BAFD5138A | - |
| Identifier | https://doi.org/10.26233/heallink.tuc.95673 | - |
| Language | en | - |
| Extent | 63 pages | en |
| Extent | 1.2 megabytes | en |
| Title | Graph alignment algorithms | en |
| Title | Aλγόριθμoι αντιστοίχισης γράφων | el |
| Creator | Papamanolis Anastasios | en |
| Creator | Παπαμανωλης Αναστασιος | el |
| Contributor [Thesis Supervisor] | Liavas Athanasios | en |
| Contributor [Thesis Supervisor] | Λιαβας Αθανασιος | el |
| Contributor [Committee Member] | Karystinos Georgios | en |
| Contributor [Committee Member] | Καρυστινος Γεωργιος | el |
| Contributor [Committee Member] | Zervakis Michail | en |
| Contributor [Committee Member] | Ζερβακης Μιχαηλ | el |
| Publisher | Πολυτεχνείο Κρήτης | el |
| Publisher | Technical University of Crete | en |
| Academic Unit | Technical University of Crete::School of Electrical and Computer Engineering | en |
| Academic Unit | Πολυτεχνείο Κρήτης::Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών | el |
| Content Summary | Graph 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 Item | Diploma Work | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2023-04-25 | - |
| Date of Publication | 2023 | - |
| Subject | Graph alignment | en |
| Subject | Graph matching | en |
| Subject | Graph embedding | en |
| Subject | Spectral embedding | en |
| Subject | Data mining | en |
| Bibliographic Citation | Anastasios Papamanolis, "Graph alignment algorithms", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2023 | en |
| Bibliographic Citation | Αναστάσιος Παπαμανώλης, "Aλγόριθμoι αντιστοίχισης γράφων", Διπλωματική Εργασία, Σχολή Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Πολυτεχνείο Κρήτης, Χανιά, Ελλάς, 2023 | el |
Copyright © DIAS 2013
