Experimental Analysis of Graph Alignment Algorithms.

Introduction

The graph alignment problem calls for finding a matching between the nodes of one graph and those of another graph, in a way that they correspond to each other by some fitness measure. Over the last years, several graph alignment algorithms have been proposed and evaluated on diverse datasets and quality measures. Typically, a newly proposed algorithm is compared to previously proposed ones on some specific datasets, types of noise, and quality measures where the new proposal achieves superiority over the previous ones. However, no systematic comparison of the proposed algorithms has been attempted on the same benchmarks. This paper fills this gap by conducting an extensive, thorough, and commensurable evaluation of state-of-the-art graph alignment algorithms. Our results indicate that certain overlooked solutions perform competitively, while there is no one-size-fits-all winner.

Algorithms

We evaluate nine representative graph-alignment algorithms, and their papers and the original codes are given in the following table.

Algorithm	Paper	Original Code
GWL	arXiv'2019	Python
CΟΝΕ-ALign	CIKM '20	Python
Grasp	APWeb-WAIM'2021	Python
Regal	CIKM '2018	Python
LREA	WWW '2018	Julia
NSD	IEEE'2012	Julia
Isorank	PNAS'2008	-
Net-Align	ACM'2013	Matlab
Klau's	APBC '2009	Matlab
S-GWL	NeurIPS'2019	Python
Graal	JRSICU'2010	C
Grampa	ICML'2020	-
B-Grasp	-	-

Datasets

Our experiment involves seventeen real-world datasets

Dataset	Type
ca-netscience	COLLABORATION NETWORKS
bio-celegans	BIOLOGICAL
in-arenas	EMAIL
inf-euroroad	INFRASTRUCTURE
inf-power	INFRASTRUCTURE
ca-GrQc	COLLABORATION
bio-dmela	BIOLOGICAL
ca-AstroPh	COLLABORATION
soc-hamsterster	Social Networks
socfb-Bowdoin47	Facebook
socfb-Hamilton46	Facebook
socfb-Haverford76	Facebook
socfb-Swarthmore42	Facebook
soc-facebook	Social Networks
high-school-2013	Social Networks
mammalia-voles	BIOLOGICAL
MultiMagna	BIOLOGICAL

Also it involves synthetic graphs generated using the networkx library synthetic graphs.

Parameters

For the optimal parameters in terms of accuraccy and running time of each algorithm on all experimental datasets, see the parameters page. If running time is not an issue higher embeding dimensionality and more iterations yield better accuracy results.

Required Libraries

scipy,numpy,networkx,pickle,psutil,matplotlib,sklearn,theano,pymanopt,pandas,pot,pytest,autograd,openpyxl,lapjv(Linux)

Usage

How to run experiments :

The following commands generate the relevant figures in our evaluation paper:

1)  python workexp with scaling #: This will run the scalability experiment as in the paper
2)  python workexp with tuning #: This will run the tunning experiment as in the paper
3)  python workexp with real_noise #: This will run the real graphs experiments as in the paper :MultiMagna,HighSchool,Voles datasets
4)  python workexp with real #: This will run the high noise experiments as in the paper 
5)  python workexp with arenasish #:This will run the random graph experiment+ arenas dataset as in the paper
6)  python workexp with playground #: This will run the low noise experiment as in the paper

Keywords can be used to make the experiments more specific or add more functionalities :

seed=[***] # will run the experiment with specific randomness, it can be used again to run exactly the same experiment

mall #- will run all the possible extraction methods for all the selected aglorithms - JonkerVolgenant,Neirest Neigboor,SortGreedy on cost and/or similarity

run=[...] #to choose only specific algorithms to run 0=GWL,1=Cone etc based on the Algorithms table order

iters=[..] #to speficy the number of iterations

mon=[True] #to return results also for memory and Cpu usage

Load= [..] #to load the graphs of a specific run id, from the previusly runned . Every experiment creates a unique id.

accs=[...] #to specify the evaluation methods         0-acc,1-EC,2-ICS,3-S3,4-Jacc,5-MNC

plot=[..] #create a plot

no_disc=True #nodes to be conected or not

until_connected=False #network to be conected or not

noise_type=[..] #1 for One-Way, 2 MultiModal ,3 Two-Way

save=true #Store alignment information

Reference

Please cite our work in your publications if it helps your research:

@inproceedings{DBLP:conf/edbt/SkitsasOHMK23,
  author    = {Konstantinos Skitsas and
               Karol Orlowski and
               Judith Hermanns and
               Davide Mottin and
               Panagiotis Karras},
  editor    = {Julia Stoyanovich and
               Jens Teubner and
               Nikos Mamoulis and
               Evaggelia Pitoura and
               Jan M{\"{u}}hlig},
  title     = {Comprehensive Evaluation of Algorithms for Unrestricted Graph Alignment},
  booktitle = {Proceedings 26th International Conference on Extending Database Technology,
               {EDBT} 2023, Ioannina, Greece, March 28-31, 2023},
  pages     = {260--272},
  publisher = {OpenProceedings.org},
  year      = {2023},
  url       = {https://doi.org/10.48786/edbt.2023.21},
  doi       = {10.48786/edbt.2023.21},
  timestamp = {Mon, 08 Aug 2022 09:41:38 +0200},
  biburl    = {https://dblp.org/rec/conf/edbt/SkitsasOHMK23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

mrauha/Framework_GraphAlignment