Skip to main content
main-content

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the Second International Workshop on Graph Structures for Knowledge Representation and Reasoning, GKR 2011, held in Barcelona, Spain, in July 2011 as satellite event of IJCAI 2011, the 22nd International Joint Conference on Artificial Intelligence. The 7 revised full papers presented together with 1 invited paper were carefully reviewed and selected from 12 submissions. The papers feature current research involved in the development and application of graph-based knowledge representation formalisms and reasoning techniques and investigate further developments of knowledge representation and reasoning graph based techniques. Topics addressed are such as: bayesian networks, semantic networks, conceptual graphs, formal concept analysis, cp-nets, gai-nets, euler diagrams, existential graphs all of which have been successfully used in a number of applications (semantic Web, recommender systems, bioinformatics etc.).

Inhaltsverzeichnis

Frontmatter

Local Characterizations of Causal Bayesian Networks

Abstract
The standard definition of causal Bayesian networks (CBNs) invokes a global condition according to which the distribution resulting from any intervention can be decomposed into a truncated product dictated by its respective mutilated subgraph. We analyze alternative formulations which emphasizes local aspects of the causal process and can serve therefore as more meaningful criteria for coherence testing and network construction. We first examine a definition based on “modularity” and prove its equivalence to the global definition. We then introduce two new definitions, the first interprets the missing edges in the graph, and the second interprets “zero direct effect” (i.e., ceteris paribus). We show that these formulations are equivalent but carry different semantic content.
Elias Bareinboim, Carlos Brito, Judea Pearl

Boolean Formulas of Simple Conceptual Graphs ( $\mathcal{SGBF}$ )

Abstract
This paper presents a conceptual graph formalism called simple graph boolean formulas that extends the \(\mathcal{SG}\) with boolean connectors. This formalism is used to define categories of objects in a classification service that can be turned into a legal content management system. We define the \(\mathcal{SGBF}\) of graph boolean formulas, present two decidable fragments of this formalism (relying on the first order logic BSR and guarded fragments), and describe the functional architecture of a generic classification service that can be used in the legal domain.
Olivier Carloni

Conflict, Consistency and Truth-Dependencies in Graph Representations of Answer Set Logic Programs

Abstract
In this paper, we propose a formalization of the features that a graph representation of logic programs under the answers set semantics should in our opinion exhibit in order to be a satisfactory and useful representation formalism. We introduce a concept of isomorphism (or structural equivalence) between a program and its corresponding graph. We argue that isomorphic representations can be a good software engineering tool for understanding program behavior, for checking consistency, for being able to create, debug and combine good programs, and for developing program analysis techniques.
Stefania Costantini, Alessandro Provetti

Bucket and Mini-bucket Schemes for M Best Solutions over Graphical Models

Abstract
The paper focuses on the task of generating the first m best solutions for a combinatorial optimization problem defined over a graphical model (e.g., the m most probable explanations for a Bayesian network). We show that the m-best task can be expressed within the unifying framework of semirings making known inference algorithms defined and their correctness and completeness for the m-best task immediately implied. We subsequently describe elim-m-opt, a new bucket elimination algorithm for solving the m-best task, provide algorithms for its defining combination and marginalization operators and analyze its worst-case performance. An extension of the algorithm to the mini-bucket framework provides bounds for each of the m best solutions. Empirical demonstrations of the algorithms with emphasis on their potential for approximations are provided.
Natalia Flerova, Emma Rollon, Rina Dechter

Supporting Argumentation Systems by Graph Representation and Computation

Abstract
Argumentation is a reasoning model based on arguments and on attacks between arguments. It consists in evaluating the acceptability of arguments, according to a given semantics. Due to its generality, Dung’s framework for abstract argumentation systems, proposed in 1995, is a reference in the domain. Argumentation systems are commonly represented by graph structures, where nodes and edges respectively represent arguments and attacks between arguments. However beyond this graphical support, graph operations have not been considered as reasoning tools in argumentation systems. This paper proposes a conceptual graph representation of an argumentation system and a computation of argument acceptability relying on conceptual graph default rules.
Jérôme Fortin, Rallou Thomopoulos, Jean-Rémi Bourguet, Marie-Laure Mugnier

Representing CSPs with Set-Labeled Diagrams: A Compilation Map

Abstract
Constraint Satisfaction Problems (CSPs) offer a powerful framework for representing a great variety of problems. Unfortunately, most of the operations associated with CSPs are NP-hard. As some of these operations must be addressed online, compilation structures for CSPs have been proposed, e.g. finite-state automata and Multivalued Decision Diagrams (MDDs).
The aim of this paper is to draw a compilation map of these structures. We cast all of them as fragments of a more general framework that we call Set-labeled Diagrams (SDs), as they are rooted, directed acyclic graphs with variable-labeled nodes and set-labeled edges; contrary to MDDs and Binary Decision Diagrams, SDs are not required to be deterministic (the sets labeling the edges going out of a node are not necessarily disjoint), ordered nor even read-once.
We study the relative succinctness of different subclasses of SDs, as well as the complexity of classically considered queries and transformations. We show that a particular subset of SDs, satisfying a focusing property, has theoretical capabilities very close to those of Decomposable Negation Normal Forms (DNNFs), although they do not satisfy the decomposability property stricto sensu.
Alexandre Niveau, Hélène Fargier, Cédric Pralet

A Semantic Web Interface Using Patterns: The SWIP System

Abstract
Our purpose is to hide the complexity of formulating a query expressed in a graph query language such as SPARQL. We propose a mechanism allowing queries to be expressed in a very simple pivot language, mainly composed of keywords and relations between keywords. Our system associates the keywords with the corresponding elements of the ontology (classes, relations, instances). Then it selects pre-written query patterns, and instanciates them with regard to the keywords of the initial query. Several possible queries are generated, ranked and then shown to the user. These queries are presented by means of natural language sentences. The user then selects the query he/she is interested in and the SPARQL query is built.
Camille Pradel, Ollivier Haemmerlé, Nathalie Hernandez

Visually Interacting with a Knowledge Base Using Frames, Logic, and Propositional Graphs

Abstract
The knowledge base of a knowledge representation and reasoning system can simultaneously be thought of as being logic-, frame-, and graph-based. We present a method for naturally extending this three-fold view to methods for visual interaction with the knowledge base in the context of SNePS 3 and its newly developed user interface. Addition to, and querying of, the knowledge base are tasks well suited to a frame or logical representation. Visualization and exploration on the other hand are best done through the use of propositional graphs. We show how these interaction techniques, which are extensions of the underlying knowledge base representation, augment each other to allow users to manipulate and view large knowledge bases.
Daniel R. Schlegel, Stuart C. Shapiro

Backmatter

Weitere Informationen