Investigating and Optimizing MINDWALC Node Classification to Extract Interpretable Decision Trees from Knowledge Graphs

This work deals with the investigation and optimization of the MINDWALC node classification algorithm with a focus on its ability to learn human-interpretable decision trees from knowledge graph databases. For this, we introduce methods to optimize MINDWALC for a specific use case, in which the processed knowledge graph is strictly divided into its inner background knowledge (knowledge about a given domain) and instance knowledge (knowledge about given instances). We present the following improvement approaches, whereby the basic idea of MINDWALC—namely, to use discriminative walks through the knowledge graph as features—remains untouched. First, we apply relation-tail merging to give MINDWALC the ability to take relation-modified nodes into account. Second, we introduce walks with flexible walking depths, which can be used together with MINDWALC’s original walking strategy and can help to detect more similarities between node instances. In some cases, especially with hierarchical, incomplete tree-like structured graphs, our presented flexible walk can improve the classification performance of MINDWALC significantly. However, on mixed knowledge graph structures, the results are mixed. In summary, we were able to show that our proposed methods significantly optimize MINDWALC on tree-like structured graphs, and that MINDWALC is able to utilize background knowledge to replace missing instance knowledge in a human-comprehensible way. Our test results on our medical toy datasets indicate that our MINDWALC optimizations have the potential to enhance decision-making in medical diagnostics, particularly in domains requiring interpretable AI solutions.