Closed and Maximal Patterns on Dissimilarity-Based Graph Embedding for Supervised Classification

Abstract

This paper presents a comparative analysis of
the performance of Dissimilarity-based Graph Embedding,
built from all frequent, closed, and maximal graph patterns
for supervised classification. Dissimilarity-based Graph
Embedding employs a dissimilarity metric to transform
a graph into a vector representation by computing each
entry of the vector as the dissimilarity between a graph
and each graph pattern mined from a graph collection.
Given that the number of graph patterns mined can be too
large, subsets such as closed and maximal patterns are
used to reduce the number of graph patterns, leading to
more compact and non-redundant representations. Our
study employed four benchmark graph collections and six
different supervised classifiers. The experimental results
enabled us to identify which type of graph pattern (all
frequent, closed, or maximal) allows a Dissimilarity-based
Graph Embedding that yields the highest performance in
supervised classification