Linear Temporal Logic on Finite Traces (LTLf) is a popular logic to express declarative specifications in Artificial Intelligence (AI). The recent call for explainable AI tools has made relevant the problem of computing efficiently minimal unsatisfiable cores (MUCs) and minimal correction sets (MCSes) of LTLf formulas. Recent work has focused on the extraction of MUCs on formulas in conjunctive form. In this paper, we present a method that operates on arbitrary formulas and computes a more refined notion of MUCs, as introduced by Schuppan, along with the corresponding notion of MCSes. Experiments show that our system, based on Answer Set Programming, outperforms available tools.

Abstract Inferring linear temporal logic over finite traces ($\text{LTL}_{\text{f}}$) formulas from a set of example traces, known as passive learning, presents significant challenges due to its combinatorial nature. In this paper, we introduce a novel approach to $\text{LTL}_{\text{f}}$ passive learning based on inductive logic programming (ILP), leveraging the inductive learning of answer set programs framework. Our ILP-based method effectively exploits the set of example traces to guide the learning process, and experimental results demonstrate that it o ffers a more efficient solution compared to traditional techniques based on propositional satisfiability.

Recent advancements in AI have made LLMs valuable tools for automating the interpretation of textual descriptions of business processes and for converting formal process specifications into natural language. However, there are no practical methodologies or systematic assessments to ensure these automatic translations are faithful. This paper proposes a novel approach, based on an auxiliary bidirectional translation task, to assess LLMs performance quantitatively; also, it also empirically evaluates the performance of state-of-the-art LLMs for bidirectional translations between natural language and declarative formal process specifications. The results reveal substantial variability in performance among the LLMs, highlighting the importance of LLM selection and confirming the need for a robust method for assessing LLMs' outputs.

Abstract Answer set programming (ASP), a well-known declarative logic programming paradigm, has recently found practical application in Process Mining. In particular, ASP has been used to model tasks involving declarative specifications of business processes. In this area, Declare stands out as the most widely adopted declarative process modeling language, offering a means to model processes through sets of constraints valid traces must satisfy, that can be expressed in linear temporal logic over finite traces (LTL $_{\text {f}}$ ). Existing ASP-based solutions encode Declare constraints by modeling the corresponding LTL $_{\text {f}}$ formula or its equivalent automaton which can be obtained using established techniques. In this paper, we introduce a novel encoding for Declare constraints that directly models their semantics as ASP rules, eliminating the need for intermediate representations. We assess the effectiveness of this novel approach on two Process Mining tasks by comparing it with alternative ASP encodings and a Python library for Declare.

The pervasive issue of missing data in statistical analysis and data science significantly impacts the integrity and accuracy of Time-Series Cross-Sectional (TSCS) datasets, extensively used in domains like health sciences and sensor applications. Traditional imputation methods are often inadequate for these datasets as they fail to address the complexities arising from cross-sectional and temporal data gaps. This paper introduces BiTSNet (Bipartite Time Series Network for Data Imputation), a novel approach designed to tackle the unique challenges of TSCS datasets by leveraging a dual representation of data. BiTSNet models cross-sectional time series data as sequences of bipartite graphs, where each graph represents a specific time step, and feature values are depicted as edge weights. Thus, missing values are interpreted as missing edge feature values, allowing BiTSNet to comprehensively capture spatial relationships within each time step and temporal relationships across steps. The framework uses Graph Neural Networks (GNNs) to process spatial dependencies within these bipartite graph representations and employs Recurrent Neural Networks (RNNs) to handle temporal dependencies. This integration enables BiTSNet to learn the intricate intra-time step relationships and the inter-time step dynamics effectively. Our approach not only preserves the longitudinal and cross-sectional integrity of the data but also ensures the production of valid and insightful conclusions from the enriched dataset. We evaluated BiTSNet on several datasets and compared it against the state-of-the-art approaches with encouraging results.

Community detection algorithms that analyze networks to identify communities of nodes are an essential part of the network analysis toolkit used daily by different analysts (e.g., data scientists and law enforcement). However, there is not enough awareness that members of a community$\mathscr {C}$(either revealed or not) inside a network$G$could act strategically to evade such tools either for legitimate (e.g., activist groups in authoritarian regimes) or malicious (e.g., terrorists) purpose. Community deception offers this possibility. By identifying a certain number of$\mathscr {C}$’s member connections to be rewired, community deception algorithms can successfully hide a community that wants to stay below the radar of detection techniques. However, the state-of-the-art deception approaches have focused on networks without attributes, although real-world networks (e.g., Facebook) include attributes (e.g., age and sex) that play a central role in detecting more accurate communities. This article faces three novel challenges introduced when designing deception techniques for networks with attributes. The first concerns how to model and encode attributes most flexibly. The second is about framing attribute-aware community deception as an optimization problem. Finally, the challenge of solving the optimization problem by leveraging network topology and attributes also arises. We leverage a simple way to model network attributes as edge weights, a novel optimization function called community diffusion, and Diffuser a greedy algorithm to optimize diffusion, to solve the above challenges. We evaluated Diffuser against several community detection algorithms and compared it with state-of-the-art deception approaches on various real-world networks. From the evaluation, we can draw two main observations. First, adopting attribute-oblivious deception techniques leads to unsatisfactory results. Second, community diffusion as an optimization function specific to attributed networks is preferred to community safeness, the state-of-the-art deception optimization function, even when recasting the latter as an attribute-aware function.

Temporal changes in data set the need for the development of knowledge representation techniques able to capture these dynamics. Temporal Knowledge Graphs (TKGs) have emerged as a reference tool to represent dynamic, structured and machine-interpretable knowledge that evolves over time. However, characterizing the evolution of TKGs in a meaningful and human-understandable way remains a significant challenge. In this short paper, we argue that Linear Temporal Logic (LTL), with its expressive temporal constructs, is a promising approach for capturing a wide range of temporal behaviors and high-level evolutionary patterns occurring in TKGs.

An opinion diffusion scenario is considered where two marketers compete to diffuse their own opinions over a social network. In particular, they implement social proof marketing approaches that naturally give rise to a strategic setting, where it is crucial to find the appropriate order for targeting the individuals to which provide the incentives to adopt their opinions. The setting is extensively studied from the theoretical and empirical viewpoint, by considering strategies defined in a compact way, such as those that can be defined by selecting the individuals according to their degree of centrality in the underlying network. In addition to depicting a clear picture of the complexity issues arising in the setting, several compact strategies are empirically compared on real-world social networks. Results suggest that the effectiveness of compact strategies is moderately influenced by the characteristic of the network, with some centrality measures naturally emerging as good candidates to define heuristic approaches for marketing campaigns.

Process Mining is a family of techniques that exploit data collected from process execution to analyze and improve process efficiency, quality, and security. Over the years, many modeling languages have been proposed for process model specification, with different expressiveness, features, and computational properties. We propose a new logic-based declarative formalism, called Constraint Formulae, to compose process specifications, expressed in heterogeneous process modeling languages, without altering their original semantics. We formalize common process mining tasks for Constraint Formulae, study their computational properties, and provide an implementation in Answer Set Programming.

LTL on finite traces (LTLf ) is a logic that attracted much attention in recent literature, for its ability to formalize the qualitative behavior of dynamical systems in several application domains. However, its practical usage is still rather limited, as LTLf cannot deal with any quantitative aspect, such as with the costs of realizing some desired behaviour. The paper fills the gap by proposing a weighting framework for LTLf encoding such quantitative aspects in the traces over which it is evaluated. The complexity of reasoning problems on weighted traces is analyzed and compared to that of standard LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of relevant syntactic restrictions. Moreover, a reasoner for LTL on weighted finite traces is presented, and its performances are assessed on benchmark data.

Techniques to hide a community from community detection algorithms are emerging as a new way to protect the privacy of users. Existing techniques either adapt optimization criteria derived from community detection (e.g., minimizing instead of maximizing modularity) or define new ones (e.g., community safeness) to identify a set of updates (e.g., edge addition/deletions) that deceive community detection algorithms from recovering the original structure of a target community C. However, all existing approaches do not take into account the fact that network's edges can be weighted to take into account node similarity or relation strength. The goal of this paper is to present SECRETORUM, a novel community deception approach for community deception in weighted networks.

Graph embedding techniques allow to learn high-quality feature vectors from graph structures and are useful in a variety of tasks, from node classification to clustering. Existing approaches have only focused on learning feature vectors for the nodes and predicates in a knowledge graph. To the best of our knowledge, none of them has tackled the problem of directly learning triple embeddings. The approaches that are closer to this task have focused on homogeneous graphs involving only one type of edge and obtain edge embeddings by applying some operation (e.g., average) on the embeddings of the endpoint nodes. The goal of this paper is to introduce Triple2Vec, a new technique to directly embed knowledge graph triples. We leverage the idea of line graph of a graph and extend it to the context of knowledge graphs. We introduce an edge weighting mechanism for the line graph based on semantic proximity. Embeddings are finally generated by adopting the SkipGram model, where sentences are replaced with graph walks. We evaluate our approach on different real-world knowledge graphs and compared it with related work. We also show an application of triple embeddings in the context of user-item recommendations.

Declarative approaches to control-flow modeling use logic-based languages to formalize a number of constraints that valid traces must satisfy. The most noticeable example is the DECLARE framework based on linear temporal logic. Despite the interest that DECLARE has been attracting, the current knowledge about its formal properties was rather limited. The goal of this paper is to fill this gap by: (i) analyzing the behavioral properties of DECLARE by comparing it with the modeling capabilities of traditional procedural design approaches, in particular, block-structured processes; (ii) analyzing DECLARE from the computational point of view. As for the former point, we identify both the block-structured processes constructs that can be simulated in DECLARE and the features of DECLARE that can be encoded in block-structured processes. As for the latter point, we show that checking whether a given set of DECLARE patterns admits a satisfying trace is an NP-hard problem. In particular, we identify some DECLARE specifications whose satisfying traces are all of exponential length and some useful DECLARE fragments where a satisfying trace whose length is polynomially bounded is guaranteed to exist. The paper also discusses the declare2sat prototype system and the results of a thorough experimental validation.

We tackle fact checking using Knowledge Graphs (KGs) as a source of background knowledge. Our approach leverages the KG schema to generate candidate evidence patterns, that is, schema-level paths that capture the semantics of a target fact in alternative ways. Patterns verified in the data are used to both assemble semantic evidence for a fact and provide a numerical assessment of its truthfulness. We present efficient algorithms to generate and verify evidence patterns, and assemble evidence. We also provide a translation of the core of our algorithms into the SPARQL query language. Not only our approach is faster than the state of the art and offers comparable accuracy, but it can also use any SPARQL-enabled KG.

Linear temporal logic (LTL) is a modal logic where formulas are built over temporal operators relating events happening in different time instants. According to the standard semantics, LTL formulas are interpreted on traces spanning over an infinite timeline. However, applications related to the specification and verification of business processes have recently pointed out the need for defining and reasoning about a variant of LTL, which we name LTLp, whose semantics is defined over process traces, that is, over finite traces such that, at each time instant, precisely one propositional variable (standing for the execution of some given activity) evaluates true. The paper investigates the theoretical underpinnings of LTLp and of a related logic formalism, named LTLf, which had already attracted attention in the literature and where formulas have the same syntax as in LTLp and are evaluated over finite traces, but without any constraint on the number of variables simultaneously evaluating true. The two formalisms are comparatively analyzed, by pointing out similarities and differences. In addition, a thorough complexity analysis has been conducted for reasoning problems about LTLp and LTLf, by considering arbitrary formulas as well as classes of formulas defined in terms of restrictions on the temporal operators that are allowed. Finally, based on the theoretical findings of the paper, a practical reasoner specifically tailored for LTLp and LTLf has been developed by leveraging state-of-the-art SAT solvers. The behavior of the reasoner has been experimentally compared with other systems available in the literature.

In this paper, we research the community deception problem. Tackling this problem consists in developing techniques to hide a target community (C) from community detection algorithms. This need emerges whenever a group (e.g., activists, police enforcements, or network participants in general) want to observe and cooperate in a social network while avoiding to be detected. We introduce and formalize the community deception problem and devise an efficient algorithm that allows to achieve deception by identifying a certain number (b) of C's members connections to be rewired. Deception can be practically achieved in social networks like Facebook by friending or unfriending network members as indicated by our algorithm. We compare our approach with another technique based on modularity. By considering a variety of (large) real networks, we provide a systematic evaluation of the robustness of community detection algorithms to deception techniques. Finally, we open some challenging research questions about the design of detection algorithms robust to deception techniques.

We demonstrate RECAP, a tool that explains relatedness between entities in Knowledge Graphs (KGs) and implements a query by relatedness paradigm that allows to retrieve entities related to those in input. One of the peculiarities of RECAP is that it does not require any data preprocessing and can combine knowledge from multiple KGs. The underlying algorithmic techniques are reduced to the execution of SPARQL queries plus some local refinement. This makes the tool readily available on a large variety of KGs accessible via SPARQL endpoints. To show the general applicability of the tool, we will cover a set of use cases drawn from a variety of knowledge domains (e.g., biology, movies, co-authorship networks) and report on the concrete usage of RECAP in the SENSE4US FP7 project. We will underline the technical aspects of the system and give details on its implementation. The target audience of the demo includes both researchers and practitioners and aims at reporting on the benefits of RECAP in practical knowledge discovery applications.

This paper focuses on LTL on finite traces (LTLf) for which satisfiability is known to be PSPACE-complete. However, little is known about the computational properties of fragments of LTLf. In this paper we fill this gap and make the following contributions. First, we identify several LTLf fragments for which the complexity of satisfiability drops to NP-complete or even P, by considering restrictions on the temporal operators and Boolean connectives being allowed. Second, we study a semantic variant of LTLf, which is of interest in the domain of business processes, where models have the property that precisely one propositional variable evaluates true at each time instant. Third, we introduce a reasoner for LTLf and compare its performance with the state of the art.

Due to the openness and decentralization of the Web, mechanisms to represent and reason about the reliability of RDF data become essential. This paper embarks on a formal analysis of RDF data enriched with trust information by focusing on the characterization of its model-theoretic semantics and on the study of relevant reasoning problems. The impact of trust values on the computational complexity of well-known concepts related to the entailment of RDF graphs is studied. In particular, islands of tractability are identified for classes of acyclic and nearly-acyclic graphs. Moreover, an implementation of the framework and an experimental evaluation on real data are discussed.

We introduce Extended Property Paths (EPPs), a significant enhancement of SPARQL property paths. EPPs allow to capture in a succinct way a larger class of navigational queries than property paths. We present the syntax and formal semantics of EPPs and introduce two different evaluation strategies. The first is based on an algorithm implemented in a custom query processor. The second strategy leverages a translation algorithm of EPPs into SPARQL queries that can be executed on existing SPARQL processors. We compare the two evaluation strategies on real data to highlight their pros and cons.

We demonstrate S+EPPs, a system that provides fast construction of bisimulation summaries using graph analytics platforms, and then enhances existing SPARQL engines to support summary-based exploration and navigational query optimization. The construction component adds a novel optimization to a parallel bisimulation algorithm implemented on a multi-core graph processing framework. We show that for several large, disk resident, real world graphs, full summary construction can be completed in roughly the same time as the data load. The query translation component supports Extended Property Paths (EPPs), an enhancement of SPARQL 1.1 property paths that can express a significantly larger class of navigational queries. EPPs are implemented via rewritings into a widely used SPARQL subset. The optimization component can (transparently to users) translate EPPs defined on instance graphs into EPPs that take advantage of bisimulation summaries. S+EPPs combines the query and optimization translations to enable summary-based optimization of graph traversal queries on top of off-the-shelf SPARQL processors. The demonstration showcases the construction of bisimulation summaries of graphs (ranging from millions to billions of edges), together with the exploration benefits and the navigational query speedups obtained by leveraging summaries stored alongside the original datasets.

The Web of Linked Data is a huge graph of distributed and interlinked datasources fueled by structured information. This new environment calls for formal languages and tools to automatize navigation across datasources (nodes in such graph) and enable semantic-aware and Web-scale search mechanisms. In this article we introduce a declarative navigational language for the Web of Linked Data graph called N auti LOD. N auti LOD enables one to specify datasources via the intertwining of navigation and querying capabilities. It also features a mechanism to specify actions (e.g., send notification messages) that obtain their parameters from datasources reached during the navigation. We provide a formalization of the N auti LOD semantics, which captures both nodes and fragments of the Web of Linked Data. We present algorithms to implement such semantics and study their computational complexity. We discuss an implementation of the features of N auti LOD in a tool called swget, which exploits current Web technologies and protocols. We report on the evaluation of swget and its comparison with related work. Finally, we show the usefulness of capturing Web fragments by providing examples in different knowledge domains.

This paper presents GuLP a graph query language that enables to declaratively express preferences. Preferences enable to order the answers to a query and can be stated in terms of nodes/edge attributes and complex paths. We present the formal syntax and semantics of GuLP and a polynomial time algorithm for evaluating GuLP expressions. We describe an implementation of GuLP in the GuLP-it system, which is available for download. We evaluate the GuLP-it system on real-world and synthetic data.

The massive semantic data sources linked in the Web of Data give new meaning to old features like navigation; introduce new challenges like semantic specification of Web fragments; and make it possible to specify actions relying on semantic data. In this paper we introduce a declarative language to face these challenges. Based on navigational features, it is designed to specify fragments of the Web of Data and actions to be performed based on these data. We implement it in a centralized fashion, and show its power and performance. Finally, we explore the same ideas in a distributed setting, showing their feasibility, potentialities and challenges.

We propose an algorithm, called BI-GRAPPIN, to search for similarities across PPI networks. The technique core consists in computing a maximum weight matching of bipartite graphs to compare the neighborhoods of pairs of proteins in different PPI networks. The idea is that proteins belonging to different networks should be matched look- ing not only at their own sequence similarity, but also at the similarity of proteins they "strongly" interact with, ei- ther directly or indirectly. We implemented the method and tested it on both real and synthetic data, showing its effec- tiveness in solving ambiguous situations and in individuat- ing functionally related proteins. Differently from previous work, the presented algorithm allows to take into account both quantitative and reliability information possibly avail- able about interactions.