Graph-structured data have become increasingly important in modern machine learning, as many real-world systems—such as biological networks, social interactions, an‎d molecular structures—are naturally represented as graphs. A fundamental challenge in this field is to measure the similarity between graphs, which is crucial for tasks such as classification, clustering, an‎d pattern recognition. Graph kernels provide a powerful framework for this purpose by mapping graphs into a high-dimensional feature space, where similarity can be efficiently computed through kernel-based learning algorithms. This thesis focuses on the study an‎d eva‎luation of the {Multi-scale Wasserstein Shortest-Path (MWSP)} graph kernel, a recently proposed method that combines the advantages of multi-scale structural representation an‎d optimal transport theory. The MWSP kernel constructs truncated breadth-first search (BFS) trees rooted at each node to capture shortest-path patterns across multiple scales. Then, it employs the Wasserstein distance to measure the similarity between distributions of node-level embeddings, providing a fine-grained representation of both local an‎d global graph structures. This approach enhances the expressive power of graph kernels an‎d achieves high classification accuracy on a variety of benchmark datasets. In addition to reproducing an‎d analyzing the MWSP kernel, this thesis proposes an {optimized sparse matrix representation} for its computational components. The proposed modification significantly reduces memory consumption without compromising classification accuracy, thereby improving scalability an‎d enabling the kernel to be applied to larger graph datasets. Comprehensive experiments confirm that the sparse implementation maintains the effectiveness of the original MWSP kernel while achieving more efficient resource utilization.

بهناز عمومي

زينب مالكي

حسين فلسفين , نيلوفر احمدي پور