Bonner, S. and Brennan, J. and Theodoropoulos, G. and Kureshi, I. and McGough, A.S. (2016) 'Efficient comparison of massive graphs through the use of 'graph fingerprints'.', Twelfth Workshop on Mining and Learning with Graphs (MLG) at KDD'16. San Francisco, USA, 14 August 2016.
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.
|Item Type:||Conference item (Paper)|
|Full text:||(AM) Accepted Manuscript|
Download PDF (316Kb)
|Publisher Web site:||http://www.mlgworkshop.org/2016/paper/MLG2016_paper_22.pdf|
|Date accepted:||22 July 2016|
|Date deposited:||15 September 2016|
|Date of first online publication:||August 2016|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|