Skip to main content

Research Repository

Advanced Search

Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints'

Bonner, S; Brennan, J; Theodoropoulos, G; Kureshi, I; McGough, AS

Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints' Thumbnail


Authors

S Bonner

J Brennan

G Theodoropoulos

I Kureshi

AS McGough



Abstract

The problem of how to compare empirical graphs is an area of great interest within the field of network science. The ability to accurately but efficiently compare graphs has a significant impact in such areas as temporal graph evolution, anomaly detection and protein comparison. The comparison problem is compounded when working with graphs containing millions of anonymous, i.e. unlabelled, vertices and edges. Comparison of two or more graphs is highly computationally expensive. Thus reducing a graph to a much smaller feature set – called a fingerprint, which accurately captures the essence of the graph would be highly desirable. Such an approach would have potential applications outside of graph comparisons, especially in the area of machine learning. This paper introduces a feature extraction based approach for the efficient comparison of large topologically similar, but order varying, unlabelled graph datasets. The approach acts by producing a ‘Graph Fingerprint’ which represents both vertex level and global level topological features from a graph. The approach is shown to be efficient when comparing graphs which are highly topologically similar but order varying. The approach scales linearly with the size and complexity of the graphs being fingerprinted.

Presentation Conference Type Conference Paper (Published)
Conference Name Twelfth Workshop on Mining and Learning with Graphs (MLG) at KDD'16.
Start Date Aug 14, 2016
Acceptance Date Jul 22, 2016
Publication Date Aug 14, 2016
Deposit Date Sep 15, 2016
Publicly Available Date Sep 15, 2016
Public URL https://durham-repository.worktribe.com/output/1151250
Publisher URL http://www.mlgworkshop.org/2016/paper/MLG2016_paper_22.pdf

Files





You might also like



Downloadable Citations