Fuchs, Mathias (2023). The Matching-Graph. (Thesis). Universität Bern, Bern
|
Text
23fuchs_m.pdf - Thesis Available under License Creative Commons: Attribution-Noncommercial-No Derivative Works (CC-BY-NC-ND 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 graph-based 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 meta-graph, termed matching-graph. The basic idea is to formalize the stable cores of individual classes of graphs – discovered during intra-class matching. This meta-graph is useful in several applications ranging from the analysis of inherent patterns, over graph classification, to graph augmentation. The benefits of the matching-graphs are evaluated in three parts. First, their usefulness in classification scenarios is evaluated in two approaches. The first approach is a distance-based classifier that focuses on the matching-graphs during dissimilarity computation. The second approach uses sets of matching-graphs to embed input graphs into a vector space. The basic idea is to first generate hundreds of matching-graphs, and then represent each graph g as a vector that shows the occurrence of, or the distance to, each matching-graph. In a thorough experimental evaluation on real-world 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 state-of-the-art methods. The second part of the research targets a prevalent challenge in graph-based 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 matching-graphs, computable in polynomial time, provide a suitable approximation for the MCS. Results show that, for specific graphs, a matching-graph 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 matching-graphs 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 matching-graphs 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: | 09 Feb 2024 03:14 |
| URI: | https://boristheses.unibe.ch/id/eprint/4869 |
Actions (login required)
 |
View Item |