Provenance of Inferences: A Trail of Proofs in Linked Open Data

Draft - June 4th

Kanghao Lu, Oshani Seneviratne, and Tim Berners-Lee

MIT CSAIL, Cambridge Massachusetts, USA

               ( kennylu | oshani | timbl )@csail.mit.edu

Abstract. With the recent uptake on the linked open data on the Web, there are many interlinked data sets on the Web today. Interesting results that might not be obvious from this raw data itself, can be derived by computing answers to rules using the data and essentially connecting the dots to see the big picture. We describe a novel method to crawl the Web of data and make inferences that satisfy rules of a particular domain and to reinject the derived conclusions, along with their proofs in a proof ontology, back into the read-write Web. We have developed a “Computation Agent” to do this, using rules written in a formal Semantic Web rule language, and a user interface for viewing data along with their proofs that give the justification for that particular data in an intuitive manner.

1 Introduction

Semantic Web is a Web of machine processable data, preferably in RDF and are linked together. The fundamental assumption of Semantic Web is that every important thing has a unique global name in the form of a Universal Resource Identifier (URI). This URI can be dereferenced to obtain a file. From this file, it may be possible to extract some RDF triples. A nonempty subset of these triples compose information about the thing, namely, the subject or the object of the thing. Therefore, Semantic Web provides a platform to include integration of heterogeneous data using explicit semantics, simplified annotation, explicit models for data representation, aggregation and easier re-use of data in unanticipated ways. Application of logic to infer additional information is one of the key benefits of exposing the data on the Semantic Web as “linked open data”.

The linked open data cloud has seen a steady growth since DBPedia [?] project has started in 2007. The DBpedia knowledge base alone currently describes more than 2.6 million things, and the knowledge base consists of 274 million pieces of information (RDF triples) [?]. Some Weblog hosting sites and social networking sites have already begun exporting user profiles in to RDF [?] using the Friend-Of-A-Friend (FOAF) vocabulary [?]. Many other data sets have linked up to this nucleus of DBpedia data set, and to each other, effectively increasing the intelligence of the Web and supporting large scale data integration.

This allows people to use data browsers such as the Tabulator [?] to surf across silos of data that have been converted into linked data.

The recommended method of extracting this vast amount of knowledge exposed through linked data is by SPARQL queries [?]. The SPARQL protocol [?] offers a standard way to serve and access structured data on the Semantic Web. However, SPARQL queries are designed to give an answer based on a particular data set at a given end point. We envision a slightly different system where answers to specific queries are computed using a crawler based computation agent. These answers are updated using the SPARUL protocol [?] along with the method of derivation in the form of a proof using a specific attachment mechanism to the data item the proof corresponds to. This “Computation Agent” will act on any given rule written in the N3 (Notation 3) rule language [?] using any given URI as a seed to start the process of crawling the linked data cloud. Once it finds information that matches the criteria specified in the rule, it will update the derived facts from the computation and the proofs associated with these facts.

The remainder of the paper is organized as follows: In Section 2 we describe the motivation behind implementing such a system and then in Section ?? we illustrate few use cases that could use a computation such as the one we have implemented. In Section 4 we illustrate the system design and implementation. In Section 6 we describe several related work from the Semantic Web world and from outside this area, especially where the inspiration for this system was drawn from. In Section 7 we provide important future directions of our implementation. Finally in Section 8 we provide a summary of the overall system.

2 Motivation

Much of the linked data cloud is interlinked. However there are many data sets that have no explicit semantic associations with each other even though these relationships might be obvious after a simple reasoning process. Once these relationships are exposed through a computation mechanism, the newly found relationships should be contributed back to the linked data cloud. This will allow reuse of these derived facts, without having to reason over the entire graph of data. For someone who may be interested in knowing how a particular fact is derived, a proof tree detailing the derivation steps could be attached with the fact to enable provenance.

For example, in Figure 1, we have a simple linked data graph. There are several different nodes (encoded A - J), and different kinds of relations between these nodes and beyond. (One could assume that node A corresponds to the WebID of Alice, node B corresponds to the WebID of Bob, and the edge between A and B, i.e. ’rel:AB’ corresponds to ‘foaf:knows’. Likewise, other nodes and edges in this graph can be any other entity and relationship exposed as linked data). By merely looking at this graph of data, the relationship between the triple A → E and H → K may not be obvious at a first glance. But after the application of a specific rule we might discover that there is a specific relationship

Fig. 1. Computations on a Linked Data Cloud

between these two triples. Assume that the derivation path of this fact is as outlined in the red arrows where new relationships between triples are created. It would be useful to make these new relationships on the linked open data cloud on the Web, so that somebody else might be able to reuse this. However, to reinforce the trustworthiness of the fact that A → E derives H → K we attach the derivation steps of the proof along with the final outcome. This derivation path is essentially an ‘audit trail’ outlining what data was used in coming to the conclusion that A → E derives H → K.

3 Use Cases

Much of the adoption of the Semantic Web has resulted from a strong need to be able to integrate and analyze data across databases, applications, and communities. It has been fascinating to witness the breadth of solutions that have been implemented to meet these needs. In this section we outline several use cases that portray the utility of the Computation Agent system that we propose.

3.1 Biomedical Data Analysis

Diverse types of data about drugs, patients, diseases, proteins, cells, pathways, and so on are already being effectively integrated on the linked open data cloud. Biomedical researchers often need to be able to ask questions that span many heterogeneous data sources in order to make well-informed decisions that may lead to important scientific breakthroughs. Once an important relationship has been found it would be very useful to other researchers to look for the result only without having to go through the burden of computing it from the beginning. Also, it would be useful to hide all the data behind the result and show only the interesting pieces.

Say for example, that a biomedical researcher finds out that a very specific symptom exhibited by patient X is subdued by a drug administered to him over a given period of time in a specific manner. This leads to the conclusion that the drug has an improved effectivity in fighting a certain disease. This fact obviously has some great benefit to other biomedical researchers. Of course one can issue a SPARQL query to obtain this same piece of information. However, whenever a researcher finds this fact, if he were to make an assertion and create some new data reflecting this discovery, it would relieve the others from the burden of doing the same thing over and over again. Also, for the skeptics of the effectiveness of this new derived fact of the drug, the derivation tree should be available with the data as a form of reinforcement.

read about http : //esw.w3.org/topic/HCLS/ClinicalObservationsInteroperability/DrugMapping.html and add stuff

3.2 Employment Decision Making

When hiring new employees, recruiters almost always use the Web to find out more information about the candidates. Usually, this would be by looking up projects that the applicant has claimed to have worked on in the past, publications and/or articles written by that individual and anything else that might be useful in the application review process. One specific question that reviewers might have is to figure out whether a given applicant has the required programming skills in a particular language. From the linked data point of view, data about and related to the individual might be exposed on the Web as FOAF (Friend Of A Friend), DOAP (Description Of A Project), SIOC (Semantically Interlinked Online Communities) and DOAC (Description Of A Career) ontologies. Therefore, evidence that a famous hacker competent in a particular programming language knows our applicant (using foaf:knows) or that she is a doap:developer of a particular project that uses the said programming language corroborates that the applicant might be competent in the programming language.

3.3 Authentication

Why was I granted access?

4 System Design and Implementation

We introduce the idea of formally descibing a ‘Computing Service’ or an ‘Agent’ using rules grounded in Semantic Web technologies. This ‘Agent’ has the following features:

4.1 Features

Never Ending Crawler There is no limit to the Linked Open Data cloud. Therefore, the required data pertaining to a given query could be somewhere out there. Therefore we have designed our crawler to look for the required data progressively. In other words, it would not stop when a particular data item has been found.

Lightweight Computations Lightweight computations are provided in the form of N3 rules [?]. These rules are used to reveal interesting relationships using publicly available linked data cloud and provides the basis for finding a resource, making an assertion, or even predict events that may happen in the future. Once a result is computed, this result is also contributed back to the linked data cloud. In essence, lightweight computations provide a mechanism for increased understanding of unprocessed raw data without resorting to heavyweight reasoning mechanisms which require many parameters and generated esoteric proofs.

Provenance Preservation Provenance is an important metric to get an idea about where a piece of information came from, the stakeholders involved in generating that piece of information and the trustworthiness of the component data items used in deriving it. The proof entails where the data came from. Therefore, by attaching a proof to a particular data item we are preserving provenance.

Persistence of Derived Results One of the major objectives of this system is that the results are made persistent for later reuse. By making these derived conclusions persistent on a read-enabled Web, we are extending the knowledge of the world. More importantly this prevents reinventing the wheel, which saves time and effort.

Proof Abstraction The proofs are attached to a data item. An intuitive user interface is used to hide the derivation path of the data items and show only the relevant pieces of information. Only when the user demands to know why a particular data item is the way it is, the proof is shown.

4.2 Maximum Information Oriented View

Wikipedia style editing to contribute data

Fig. 2. System Design

2

We have prototyped an ’agent’ which use the existing linked social data on the web to make useful inferences. Based on these inferences, the agent can make suggestions to the concerned parties. Figure 2 outlines the architecture of our system.

4.3 Computation Engine

The Computation Engine is based on CWM (Closed World Machine) [?]. This is a program that can parse and serialize RDF in several formats including RD-F/XML, Notation3, and NTriples, stores triples in a queryable triples database, perform inferences as a forward chaining First Order Predicate Logic inference engine. It can also be used to perform builtin functions such as comparing strings, retrieving resources using an extensible builtins suite.

@@Write about the crawer

We have implemented a system analogous to aTruth Maintenance System (TMS) [?] to keep track of the dependencies by continuously updating them to a SPARQL-Updateable [?] wiki.

4.4 Update and Retrival

@@Write about the server side hacks on the data wiki including the X-Meta header and the Concatenation of N3 files

@@The ontology used - tms

4.5 User Interface

Fig. 3. User Interface Showing the Existence of Proof

@@Explain the scenario

@@Give the rule

@@Include the screen shot of the crawler interface

The user interface of this system is based on the Tabulator. Figure 3 shows an example data item with a question mark next to it, suggesting that a proof is attached with that data item. The number next to the question mark symbolizes how many proofs that particular triple has. Higher the number, the more trustworthy this triple is.

Figure 4 shows what appears when the question mark is clicked. This is Tabulator’s Justification User interface.

@@ Write about Parsing the proof tree

Fig. 4. User Interface on Tabulator Showing the Reasons behind the Conclusion Given

5 Implementation Details

In this section, the details of the current implementation such as protocols and workarounds are described. All these technical decisions are far from being standardized. Therefore, they are subject to change, but we expect later versions of the current implementation to be backward compatible.

5.1 The Proof Vocabulary

The proof visualization relies upon the proof vocabulary. This vocabulary follows from the TAMI project, in particular, the justification pane ??. It looks as follows:

@prefix tms: <http://dig.csail.mit.edu/TAMI/2007/amord/tms#> .
@prefix doap: <http://usefulinc.com/ns/doap#> .
@prefix doac: <http://ramonantonio.net/doac/0.1/#> .
@prefix soft-eng: <http://dig.csail.mit.edu/2009/06/software_engineering#> .
@prefix ken: <http://dig.csail.mit.edu/People/kennyluck#> . #just for URI abbreviation, not a vocabulary
{ ken:I doac:skill "Javascript" . } #subject, the conclusion in formula
tms:justification                        #predicate
[                                        #object, a bnode
  tms:antecedent-expr  [ a tms:And-justification; #a bnode of And-justification
                           tms:sub-expr soft-eng#doap2doac-skill , #the ruleURI, optional for the moment
{                                   #the antecedents in formula
<http://dig.csail.mit.edu/2005/ajar/ajaw/data#Tabulator> doap:developer ken:I;
                                                                                                                        doap:programming-language "Javascript" .
                } ] ] .

which constitues two formula, namely the conclusion and the antecedent, two blank nodes, and effectively 5 triples. This proof is written in Turtle+Formula, which is a subset of the full N3 allowing formula, or graphs, to be subjects or objects ??. The client store of the proof visualization UI is required to support formula as subjects or objects, but the some of the full N3 constructs such as variables and quantification are not needed.

As mentioned from Kagal, the creator of this proof vocabulary, the current output is too verbose, so the proof vocabulary might be revised. But again, we expect the client implementation to be backward compatible.

5.2 The Proof Updating Protocol for a Computing Agent

The updating protocol is adapted from the SPARQL Update protocol, as described in ??:

POST /path-of-updatable-document HTTP/1.1
Content-Type: application/sparql-query
#no spercent encoding
PREFIX ken <http://dig.csail.mit.edu/People/kennyluck#> .
PREFIX doac <http://ramonantonio.net/doac/0.1/#> .
INSERT { ken:I doac:skill "Javascript" . }

A consistent extension of SPARQL Update should allow subjects and objects to be graphs (or formula), see 7. However, since even SPARQL Update itself is not standarized and widely adopted. In order to reduce the amount of work of the SPARQL Update server, we chose the following workaround:

POST /path-of-updatable-document HTTP/1.1
Content-Type: application/sparql-query
X-Meta: http://dig.cail.mit.edu/proof-tmp-storage/3deDQp
#@@oshani, can you make the above line bold face?

#no spercent encoding
PREFIX ken <http://dig.csail.mit.edu/People/kennyluck#> .
PREFIX doac <http://ramonantonio.net/doac/0.1/#> .
INSERT { ken:I doac:skill "Javascript" . }

that is, we give the SPARQL Update server a URI link to the generated temporary proof. Notice that the disadvange of this is that the computing agent has to have the power to write on the Web, which does not hold for normal users, and this is not desirable.

The implemented computing agent generate proofs as desribed by the last section. As a multi-threaded application, the agent sends the data along with a pointer to the proof as long as a deduction is made, in the mean time, the crawling threads are still fetching more data on the Web.

5.3 Providing Proofs from a Server and Retrieving Proofs from a Client

The current proof providing mechanism is HTTP content negotiation. If the client store has the ability to store triples with formula subject or object, when fetching a document, the client’s HTTP Accept header contains the content type representing the N3 format, namely text/n3, the server sends a big document containing proofs of some of the information in the document. If the client store only does flat RDF, the server sends a small document, with all the proofs removed from the big document.

The first author believes all information should be sent along with the proofs, while the last author believes data and proofs should be separated into diffenrent files. The proposed mechanism conceives an extra HTTP header:

GET /data-file HTTP/1.1
HTTP/1.1 200 OK
Link: http://dig.csail.mit.edu/meta-file-for-data-file
#@@ bold face
<data-file-content>

where the Link points to a meta file of the data file containing the information in the data file, and the client can fetch the meta file afterwards. The advantage of this approch is it preserves the integrity of the data file. Notice that the Link header is not yet standardized and as far as the first author knows, no existing HTTP server uses this mechanism yet. It is also not implemented in our system yet.

6 Related Work

@@ Refine the following section

AIR (Accountability In RDF) [?] a policy language that exploits a dependency tracking approach generates proofs with quasi-natural language explanations for a given policy and a log file. The AIR policies are represented in Turtle [?], which is a human readable syntax for RDF, and include the quoting feature of N3Logic [?]. AIR constructs allow policy writers to explicitly control how the reasoning happens by invoking rules according to pattern matches and are based on AMORD constructs [?] ^{1}. AIR consists of an ontology and a reasoner, which when given a set of policies and data in Turtle, attempts to compute compliance of the data with respect to the policies. Each computed compliance result has an associated explanation in Turtle outlining the derivation of the result from the inputs.

The explanation framework in [?] provides natural language explanations for questions about policy decisions including explanations for failed results. In their framework, the explanation generation process is separate from the regular query process and uses abductive reasoning, a method of inferring which hypothesis best explains the facts, to obtain a proof. Parts of their proof language in the proof are then substituted with natural language structures. One problem with this approach is that abductive reasoning is known to produce logically invalid results that can be confirmed inductively [?] and as the proof generation process is different from the query process, it could infer an explanation that is different from that was inferred by the query process. Another problem is that the explanation for failed policy results (e.g. why-not) ends up being the list of all rules that the user did not match. This means that the user has to sort through a lot of potentially irrelevant information and the disclosure of these additional policy rules could also be a privacy risk. In our approach, however, the proof generation happens along with the inference and is not a separate process so the crawler keeps tracks the rules and statements that were actually used to infer the statement (policy decision).

Both WhyNot [?] and the Know system [?] focus explicitly on failed queries and try to suggest changes to the knowledge base that will cause these queries to succeed. Our justification approach is more general and allows failures to be captured in policies so explanations can be provided for both successful and failed policy decisions.

PML (Pro) is a general proof language or ”proof interlingua” that is used to describe proof steps generated by different kinds of reasoning engines. Once our proofs are converted to PML a user could manipulate them in Inference Web (IW), a framework for displaying and manipulating proofs defined in Proof Markup Language (PML) [?]. IW concentrates on displaying proofs whereas our approach is mainly about generating these proofs.

Although it is outside of the domain of Semantic Web, the work done by Bill Lewis has debugging backwards using Omniscient Debugging concept in Java [?].

Federated SPARQL queries

1 AMORD is a production-rule system that features pattern matching, dependency tracking, nesting of rules, and goal direction

[?]

[?]

Yars2 (Yet Another RDF Store, Version 2) presents an end-to-end semantic search engine that uses a graph data model to enable interactive query answering over structured and interlinked data collected from many disparate sources on the Web [?].

Zhao et al. [?] describe various design patterns for representing and querying provenance information relating to mapping links between heterogeneous data from sources in the domain of functional genomics. The paper illustrates the use of named RDF graphs at different levels of granularity to make provenance assertions about linked data. It also demonstrates that these assertions are sufficient to support requirements including data currency, integrity, evidential support and historical queries.

AIR reasoner disadv: document level vs. triple level

7 Future Work

Proper SPARQL update semantics to update graphs instead of triples

GRAPH data.n3 INSERT {<s> <p> <o>}
GRAPH proof.n3 INSERT {proof graph}

For triples that have more than one proof diplay the relative weights - how to measure the importance of it

@@write more!

8 Conclusion

@@ refine

The Web connects people not just machines or documents. Interactions of people on the Web are just as complex as their interactions in the real life, which leads to a complex eco-system on the Web. Therfore, understanding and accounting for the social side on the Web is a vital aspect when it comes to encouraging the growth of the Web. Semantic Web provides a platform to connect people using ontologies like FOAF (Friend Of A Friend), model their interactions on web forums through ontologies such as SIOC (Semantically Interlinked Online Communities). These ontologies, together with many others, lay the groundwork to observe the social interactions of people to make useful observations and linkages. Although putting out the data out there may seem like a threat to an individual’s privacy, the social good that can come out of this is immense. In this paper we provide several use cases expressed in a Semantic Web rule language called Notation 3 (N3) and a software agent implement based on a propagator network which can make useful deductions based on these rules and an input graph.

On the Semantic Web, data happens to be a first class citizen. Such data on the Semantic Web comes from different sources and are thus bound to be distributed. Therefore, services and agents based on the Semantic Web are guaranteed to be data-oriented and distributed.