Fuchs, Mathias (2023). The MatchingGraph. (Thesis). Universität Bern, Bern

Text
23fuchs_m.pdf  Thesis Available under License Creative Commons: AttributionNoncommercialNo Derivative Works (CCBYNCND 4.0). Download (12MB)  Preview 
Abstract
The increasing amount of data available and the rate at which it is being collected is driving the rapid development of intelligent information processing and pattern recognition systems. Often the underlying data is inherently complex, making it difficult to represent it using linear, vectorial data structures. Graphs offer a versatile alternative for formal data representation. Actually, quite a number of graphbased pattern recognition methods have been proposed, and a considerable part of these methods rely on graph matching. This thesis introduces a novel method for encoding specific graph matching information into a metagraph, termed matchinggraph. The basic idea is to formalize the stable cores of individual classes of graphs – discovered during intraclass matching. This metagraph is useful in several applications ranging from the analysis of inherent patterns, over graph classification, to graph augmentation. The benefits of the matchinggraphs are evaluated in three parts. First, their usefulness in classification scenarios is evaluated in two approaches. The first approach is a distancebased classifier that focuses on the matchinggraphs during dissimilarity computation. The second approach uses sets of matchinggraphs to embed input graphs into a vector space. The basic idea is to first generate hundreds of matchinggraphs, and then represent each graph g as a vector that shows the occurrence of, or the distance to, each matchinggraph. In a thorough experimental evaluation on realworld data sets it is empirically confirmed that these novel approaches are able to improve the classification accuracy of systems that rely on comparable information as well as stateoftheart methods. The second part of the research targets a prevalent challenge in graphbased pattern recognition, viz. computing the maximum common subgraph (MCS). Current exact algorithms compute the MCS with exponential time complexity. In this second part, it is investigated whether matchinggraphs, computable in polynomial time, provide a suitable approximation for the MCS. Results show that, for specific graphs, a matchinggraph equals the maximum common edge subgraph, thereby establishing an upper limit to the size of the maximum common induced subgraph. The experimental evaluation further confirms that matchinggraphs outperform existing algorithms in terms of computation time and classification accuracy. The third part of this thesis addresses the problem of graph augmentation. Regardless of the actual representation formalism used, it is inevitable that supervised pattern recognition algorithms need access to large sets of labeled training samples. However, in some cases, this requirement cannot be met because the set of labeled samples is inherently limited. The last part shows that matchinggraphs can be used to augment graph training sets in order to make the training of a classifier more robust. The benefit of this approach is empirically validated in two different experiments. First, the augmentation approach is studied on very small graph data sets in conjunction with a graph kernel classifier, and second, the augmentation approach is studied on data sets with reasonable size in conjunction with a graph neural network classifier.
Item Type:  Thesis 

Dissertation Type:  Single 
Date of Defense:  14 September 2023 
Subjects:  000 Computer science, knowledge & systems 500 Science > 510 Mathematics 
Institute / Center:  08 Faculty of Science > Institute of Computer Science (INF) 
Depositing User:  Hammer Igor 
Date Deposited:  08 Feb 2024 13:33 
Last Modified:  14 Sep 2024 22:25 
URI:  https://boristheses.unibe.ch/id/eprint/4869 
Actions (login required)
View Item 