Graph classification is an important task that appears in many domains. To solve this problem, graphs are commonly described with structural features that make it possible to distinguish between graphs from different classes. Many approaches treat the graph as a whole, but with real-world data, not all parts of a graph are equally important for classification. Patterns that best distinguish between classes may occur only in certain local regions of a graph, while the remaining structure may contain less relevant or noisy information. Such local structural patterns can be captured with graphlets. In this work, we represent a graph with a vector embedding suitable for use in classical machine learning methods. The embedding is based on the number of graphlet occurrences in the input graph, and we evaluate its effectiveness on four real-world molecular graph datasets from the TUDataset collection. We perform graph classification, analyse which graphlets contribute the most to the final model outcome, and explore the size limit of graphlets up to which the approach remains computationally feasible. The results show that graphlet-based embeddings can capture useful structural information, but as graphlet size increases, both the dimensionality of the embedding and the computational cost of the procedure grow as well. Given the available computational resources, we therefore consider graphlets up to seven nodes in size.
|
