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

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

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.

Citation

Bonner, S., Brennan, J., Theodoropoulos, G., Kureshi, I., & McGough, A. (2016, August). Efficient Comparison of Massive Graphs Through The Use Of 'Graph Fingerprints'. Presented at Twelfth Workshop on Mining and Learning with Graphs (MLG) at KDD'16., San Francisco, USA

• 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