Author name cluster

Daria Stepanova

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

10 papers

1 author row

TMLR Journal 2026 Journal Article

Explaining Graph Neural Networks for Node Similarity on Graphs

Daniel Daza
Cuong Xuan Chu
Trung-Kien Tran
Daria Stepanova
Michael Cochez
Paul Groth

Similarity search is a fundamental task for exploiting information in various applications dealing with graph data, such as citation networks or knowledge graphs. Prior work on the explainability of graph neural networks (GNNs) has focused on supervised tasks, such as node classification and link prediction. However, the challenge of explaining similarities between node embeddings has been left unaddressed. We take a step towards filling this gap by formulating the problem, identifying desirable properties of explanations of similarity, and proposing intervention-based metrics that qualitatively assess them. Using our framework, we evaluate the performance of representative methods for explaining GNNs, based on the concepts of mutual information (MI) and gradient-based (GB) explanations. We find that unlike MI explanations, GB explanations have three desirable properties. First, they are actionable: selecting particular inputs results in predictable changes in similarity scores of corresponding nodes. Second, they are consistent: the effect of selecting certain inputs hardly overlaps with the effect of discarding them. Third, they can be pruned significantly to obtain sparse explanations that retain the effect on similarity scores. These important findings highlight the utility of our metrics as a framework for evaluating the quality of explanations of node similarities in GNNs.

PDF Details

AIJ Journal 2024 Journal Article

Adaptive large-neighbourhood search for optimisation in answer-set programming

Thomas Eiter
Tobias Geibinger
Nelson Higuera Ruiz
Nysret Musliu
Johannes Oetsch
Dave Pfliegler
Daria Stepanova

Answer-set programming (ASP) is a prominent approach to declarative problem solving that is increasingly used to tackle challenging optimisation problems. We present an approach to leverage ASP optimisation by using large-neighbourhood search (LNS), which is a meta-heuristic where parts of a solution are iteratively destroyed and reconstructed in an attempt to improve an overall objective. In our LNS framework, neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. Furthermore, our framework is self-adaptive, i. e. , it also incorporates portfolios for the LNS operators along with selection strategies to adjust search parameters on the fly. The implementation of our framework, the system ALASPO, currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon that allow for difference and full integer constraints, respectively. It utilises multi-shot solving to efficiently realise the LNS loop and in this way avoids program regrounding. We describe our LNS framework for ASP as well as its implementation, discuss methodological aspects, and demonstrate the effectiveness of the adaptive LNS approach for ASP on different optimisation benchmarks, some of which are notoriously difficult, as well as real-world applications for shift planning, configuration of railway-safety systems, parallel machine scheduling, and test laboratory scheduling.

Details DOI

KR Conference 2022 System Paper

ALASPO: An Adaptive Large-Neighbourhood ASP Optimiser

Thomas Eiter
Tobias Geibinger
Nelson Higuera
Nysret Musliu
Johannes Oetsch
Daria Stepanova

We present the system ALASPO which implements Adaptive Large-neighbourhood search for Answer Set Programming (ASP) Optimisation. Large-neighbourhood search (LNS) is a meta-heuristic where parts of a solution are destroyed and reconstructed in an attempt to improve an overall objective. ALASPO currently supports the ASP solver clingo, as well as its extensions clingo-dl and clingcon for difference and full integer constraints, and multi-shot solving for an efficient implementation of the LNS loop. Neighbourhoods can be defined in code or declaratively as part of the ASP encoding. While the method underlying ALASPO has been described in previous work, ALASPO also incorporates portfolios for the LNS operators along with self-adaptive selection strategies as a technical novelty. This improves usability considerably at no loss of solution quality, but on the contrary often yields benefits. To demonstrate this, we evaluate ALASPO on different optimisation benchmarks.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Large-Neighbourhood Search for Optimisation in Answer-Set Solving

Thomas Eiter
Tobias Geibinger
Nelson Higuera Ruiz
Nysret Musliu
Johannes Oetsch
Daria Stepanova

While Answer-Set Programming (ASP) is a prominent approach to declarative problem solving, optimisation problems can still be a challenge for it. Large-Neighbourhood Search (LNS) is a metaheuristic for optimisation where parts of a solution are alternately destroyed and reconstructed that has high but untapped potential for ASP solving. We present a framework for LNS optimisation in answer-set solving in which neighbourhoods can be specified either declaratively as part of the ASP encoding or automatically generated by code. To effectively explore different neighbourhoods, we focus on multi-shot solving as it allows to avoid program regrounding. We illustrate the framework on different optimisation problems some of which are notoriously difficult, including shift planning and a parallel machine scheduling problem from semi-conductor production, which demonstrate the effectiveness of the LNS approach.

PDF Details

KR Conference 2021 Conference Paper

Answer-Set Programming for Lexicographical Makespan Optimisation in Parallel Machine Scheduling

Thomas Eiter
Tobias Geibinger
Nysret Musliu
Johannes Oetsch
Peter Skočovský
Daria Stepanova

We deal with a challenging scheduling problem on parallel-machines with sequence-dependent setup times and release dates from a real-world application of semiconductor work-shop production. There, jobs can only be processed by dedicated machines, thus few machines can determine the makespan almost regardless of how jobs are scheduled on the remaining ones. This causes problems when machines fail and jobs need to be rescheduled. Instead of optimising only the makespan, we put the individual machine spans in non-ascending order and lexicographically minimise the resulting tuples. This achieves that all machines complete as early as possible and increases the robustness of the schedule. We study the application of Answer-Set Programming (ASP) to solve this problem. While ASP eases modelling, the combination of timing constraints and the considered objective function challenges current solving technology. The former issue is addressed by using an extension of ASP by difference logic. For the latter, we devise different algorithms that use multi-shot solving. To tackle industrial-sized instances, we study different approximations and heuristics. Our experimental results show that ASP is indeed a promising KRR paradigm for this problem and is competitive with state-of-the-art CP and MIP solvers.

PDF Details DOI

IJCAI Conference 2018 Conference Paper

Completeness-aware Rule Learning from Knowledge Graphs

Thomas Pellissier Tanon
Daria Stepanova
Simon Razniewski
Paramita Mirza
Gerhard Weikum

Knowledge graphs (KGs) are huge collections of primarily encyclopedic facts that are widely used in entity recognition, structured search, question answering, and similar. Rule mining is commonly applied to discover patterns in KGs. However, unlike in traditional association rule mining, KGs provide a setting with a high degree of incompleteness, which may result in the wrong estimation of the quality of mined rules, leading to erroneous beliefs such as all artists have won an award. In this paper we propose to use (in-)completeness meta-information to better assess the quality of rules learned from incomplete KGs. We introduce completeness-aware scoring functions for relational association rules. Experimental evaluation both on real and synthetic datasets shows that the proposed rule ranking approaches have remarkably higher accuracy than the state-of-the-art methods in uncovering missing facts.

PDF Details

JAIR Journal 2016 Journal Article

Computing Repairs of Inconsistent DL-Programs over EL Ontologies

Thomas Eiter
Michael Fink
Daria Stepanova

Description Logic (DL) ontologies and non-monotonic rules are two prominent Knowledge Representation (KR) formalisms with complementary features that are essential for various applications. Nonmonotonic Description Logic (DL) programs combine these formalisms thus providing support for rule-based reasoning on top of DL ontologies using a well-defined query interface represented by so-called DL-atoms. Unfortunately, interaction of the rules and the ontology may incur inconsistencies such that a DL-program lacks answer sets (i.e., models), and thus yields no information. This issue is addressed by recently defined repair answer sets, for computing which an effective practical algorithm was proposed for DL-Lite A ontologies that reduces a repair computation to constraint matching based on so-called support sets. However, the algorithm exploits particular features of DL-Lite A and can not be readily applied to repairing DL-programs over other prominent DLs like EL. compared to DL-Lite A, in EL support sets may neither be small nor only few support sets might exist, and completeness of the algorithm may need to be given up when the support information is bounded. We thus provide an approach for computing repairs for DL-programs over EL ontologies based on partial (incomplete) support families. The latter are constructed using datalog query rewriting techniques as well as ontology approximation based on logical difference between EL-terminologies. We show how the maximal size and number of support sets for a given DL-atom can be estimated by analyzing the properties of a support hypergraph, which characterizes a relevant set of TBox axioms needed for query derivation. We present a declarative implementation of the repair approach and experimentally evaluate it on a set of benchmark problems; the promising results witness practical feasibility of our repair approach.

PDF Details DOI

AIJ Journal 2016 Journal Article

Data repair of inconsistent nonmonotonic description logic programs

Thomas Eiter
Michael Fink
Daria Stepanova

Combining Description Logic (DL) ontologies and nonmonotonic rules has gained increasing attention in the past decade, due to the growing range of applications of DLs. A well-known proposal for such a combination are non-monotonic DL-programs, which support rule-based reasoning on top of DL ontologies in a loose coupling, using a well-defined query interface. However, inconsistency may easily arise as a result of the interaction of the rules and the ontology, such that no answer set (i. e. , model) of a DL-program exists; this makes the program useless. To overcome this problem, we present a framework for repairing inconsistencies in DL-programs by exchanging formulas of an ontology formulated in DL- Lite A, which is a prominent DL that allows for tractable reasoning. Viewing the data part of the ontology as a source of inconsistency, we define program repairs and repair answer sets based on them. We analyze the complexity of the notion, and we extend an algorithm for evaluating DL-programs to compute repair answer sets, under optional selection of preferred repairs that satisfy additional constraints. The algorithm induces a generalized ontology repair problem, in which the entailment respectively non-entailment of queries to the ontology, subject to possible updates, must be achieved by a data change. While this problem is intractable in general, we identify several tractable classes of preferred repairs that are useful in practice. For the class of deletion repairs among them, we optimize the algorithm by reducing query evaluation to constraint matching, based on the novel concept of support set, which roughly speaking is a portion of the data from which entailment of an ontology query follows. Our repair approach is implemented within an answer set program system, using a declarative method for repair computation. An experimental evaluation on a suite of benchmark problems shows the effectiveness of our approach and promising results, both regarding performance and quality of the obtained repairs. While we concentrate on DL- Lite A ontologies, our notions extend to other DLs, for which more general computation approaches may be used.

Details DOI

AAAI Conference 2014 Conference Paper

Exploiting Support Sets for Answer Set Programs with External Evaluations

Thomas Eiter
Michael Fink
Christoph Redl
Daria Stepanova

Answer set programs (ASP) with external evaluations are a declarative means to capture advanced applications. However, their evaluation can be expensive due to external source accesses. In this paper we consider HEX-programs that provide external atoms as a bidirectional interface to external sources and present a novel evaluation method based on support sets, which informally are portions of the input to an external atom that will determine its output for any completion of the partial input. Support sets allow one to shortcut the external source access, which can be completely eliminated. This is particularly attractive if a compact representation of suitable support sets is efficiently constructible. We discuss some applications with this property, among them description logic programs over DL-Lite ontologies, and present experimental results showing that support sets can significantly improve efficiency.

PDF Details

IJCAI Conference 2013 Conference Paper

Data Repair of Inconsistent DL-Programs

Thomas Eiter
Michael Fink
Daria Stepanova

Nonmonotonic Description Logic (DL) programs support rule-based reasoning on top of Description Logic ontologies, using a well-defined query interface. However, the interaction of the rules and the ontology may cause inconsistency such that no answer set (i. e. model) exists. We thus consider repairing DL-programs, i. e. , changing formulas to obtain consistency. Viewing the data part of the ontology as the source of inconsistency, we define program repairs and repair answer sets based on changes to it. We analyze the complexity of the notion, and we extend an algorithm for evaluating DL-programs to compute repair answer sets, under optional selection of preferred repairs. The extension involves a generalized ontology repair problem, in which the entailment and non-entailment of sets of queries with updates to the ontology must be achieved. While this is intractable in general, we identify for the Description Logic DL-LiteA some tractable classes of preferred repairs that are useful in practice.

PDF Details DOI