Explainable Graph Analysis in Declarative and Logical Languages

Mentored by Markus Krötzsch, Carsten Lutz
at TU Dresden

Graphs appear in many applications, and computer science has a rich and diverse arsenal of graph processing algorithms. In the specific area of knowledge graphs and graph databases, declarative approaches that are based on mathematical logic have been applied successfully. Their strengths are their verifiable behavior and high degree of explainability, fostering trust and reliability. However, individual logics are typically restricted to a narrow class of algorithms, while many other graph-based computations are either impossible or only possible under asymptotic performance penalties. The goal of this topic is to investigate declarative extensions of logical languages that overcome these limitations.

Concrete starting points for the PhD research can be the existing logic-based graph rule engine Nemo (as a representative of the state of the art), and various important algorithms that are not currently supported, such as (a) classic graph algorithms such as Tarjan’s algorithm; (b) algorithms for graph isomorphism and comparison (diffing); or (c) value propagation algorithms, e.g., for graph neural networks (GNNs) or Weisfeiler-Lemann-type algorithms – to name a few. The scope can be refined (e.g., to trees) or widened (e.g., to hypergraphs). Main research objectives in each case are:

• Discover new ways of expressing algorithms in logic (possibly using new language constructs)
• Understand the properties of the extended formalism (complexity, expressive power, interplay with other extensions)
• Explore methods for efficient implementation with these features.

Work Environment

As a member of the Chair for Knowledge-Based Systems, you are part of a successful team of enthusiastic researchers of diverse backgrounds. You are working in the inspiring environment of the International Center for Computational Logic (ICCL) and of TU Dresden as one of the leading German research universities. Dresden is a highly livable city with a rich culture and beautiful natural surroundings.

SECAI offers a first-class environment for advancing your career. You can work with internationally renowned researchers and benefit from the school’s strong networks in industry and research. The graduation of highly qualified researchers is a central project goal in SECAI and doctoral students receive strong support for their professional and personal development.

Prerequisites

• Very good university degree (M.Sc. or an equivalent) in computer science or related disciplines (such as computational logic or mathematics with a focus on CS topics)
• Acquaintance with logic programming approaches such as Datalog, ASP, and existential rules
• Working knowledge of a higher system programming language such as Rust or C++
• Familiarity with knowledge graph data models and query languages, especially RDF and SPARQL
• Background knowledge in theoretical computer science, especially complexity theory and database theory