Re: deterministic naming of blank nodes

Hey Gregg, David,

It's good to see that there's some ongoing work in the W3C on this topic!

I had a quick look though the proposals in question.

http://json-ld.github.io/normalization/spec/index.html

Hmm ... but to be honest, I could only get a very high level 
understanding of the algorithms in 4.4.2/4.8.2. It seems on a high-level 
like the algorithms are similar to what's in the paper but I can't tell 
for sure ... maybe a more formal type of pseudo-code would be better for 
presenting these algorithms? (Indeed I can definitely appreciate it's 
challenging to get this sort of stuff on paper and keep it readable.) 
 From the gist though, both seem to go in the same direction.

Cheers,
Aidan

On 20/05/2015 16:37, Gregg Kellogg wrote:
> Just so readers of this thread are aware, the W3C Credentials Community Group has been fostering an RDF Dataset Normalization specification [1] which was previously initiated as part of JSON-LD, although it concerns itself exclusively with RDF Datasets and canonical N-Quads. The goal is to use this as a basis for a future Recommendation.
>
> The algorithm was created by Dave Longley, and I understand that it is substantially the same as Aidan’s (it would be good to have an independent analysis). The specification needs a lot of work to motivate specific use cases and create normative language for describing the particular branches necessary to resolve isomorphism ambiguities and challenging graph topographies. There is a fair test suite already created (see [1]). Ideally, Aidan’s paper could form the basis of a formal description of the algorithm, with the existing algorithms described in an appendix, to the degree not required for interoperability.
>
> I’ve just completed my own implementation in Ruby [2] to join other implementations in Python and JavaScript [3], [4].
>
> We would welcome feedback and collaborators, as the expertise required for this is outside of the normal domain for the Credentials Community Group.
>
> Gregg
>
> [1] http://json-ld.github.io/normalization/
> [2] https://github.com/ruby-rdf/rdf-normalize
> [3] https://github.com/digitalbazaar/pyld
> [4] https://github.com/digitalbazaar/jsonld.js
>
>> On May 12, 2015, at 11:14 PM, ahogan@dcc.uchile.cl wrote:
>>
>> Hi,
>>
>> Sorry for resurrecting old threads but this discussion sort of prompted me
>> to work on the topic of "deterministic naming of blank nodes" and I
>> thought that it might be time (six months or so later) to report back on
>> some findings.
>>
>> The result is the paper here:
>>
>> Aidan Hogan. "Skolemising Blank Nodes while Preserving Isomorphism". In
>> WWW, Florence, Italy, May 18–22, 2015 (to appear).
>> Available from: http://aidanhogan.com/docs/skolems_blank_nodes_www.pdf
>>
>> I'll be presenting it next Friday if anyone happens to be around the
>> Florence area.
>>
>> Roughly speaking, the paper presents an algorithm for deterministically
>> labelling blank nodes of any RDF graph such that the labels of two
>> isomorphic RDF graphs will "correspond". This could be used to find
>> isomorphic RDF graphs in a large set of RDF graphs (without needing
>> pairwise checks), for computing signatures, or for Skolemising in such a
>> way that the output of two RDF graphs will be equal if and only if they
>> are isomorphic.
>>
>> The algorithm again works for general RDF graphs and doesn't assume any
>> well-behavedness or similar. The algorithm is exponential (based roughly
>> on a Nauty-style recursion) but the experiments show that, in terms of
>> isomorphism at least, you would have to have really really really *really*
>> weird RDF graphs to run into any real trouble (we're talking cliques of
>> blank nodes with k>55 or Miyazki graphs or similar). We skolemised all the
>> individual graphs in the BTC-14 collection ... the slowest took 31–40
>> seconds, mainly due to its size: 7.3 million triples with 254 thousand
>> blank nodes.
>>
>> One drawback of the current approach is that at the moment you have to
>> load the RDF graph into memory, which may be prohibitive for very very
>> large graphs (of connected blank nodes), but I'm not sure how often that
>> happens in practice. (It wasn't a problem for any of the graphs in the
>> BTC-14 dataset for example.)
>>
>> There's also a software package available here:
>>
>> https://github.com/aidhog/blabel/wiki
>>
>> Of course the usual disclaimers about research code apply!
>>
>> Anyways, I thought these results might be of interest and hopefully might
>> have applications in the context of Skolemisation or signing RDF graphs or
>> similar.
>>
>> Best,
>> Aidan
>>
>> On 21/10/2014 04:30, Laurens Rietveld wrote:
>>> Coincidentally, I will present SampLD[1] in two hours at the ISWC (11.00
>>> local time, sala 300), which might be suitable for your experiment.
>>> SampLD is a scalable approach for sampling RDF graphs, solely using the
>>> topology of the graph:
>>>
>>>     The Linked Data cloud has grown to become the largest knowledge base
>>>     ever constructed.
>>>     Its size is now turning into a major bottleneck for many
>>>     applications. In order to facilitate access to this structured
>>>     information, this paper proposes an automatic sampling method
>>>     targeted at maximizing answer coverage for applications using SPARQL
>>>     querying.
>>>     The approach presented in this paper is novel: no similar RDF
>>>     sampling approach exist. Additionally, the concept of creating a
>>>     sample aimed at maximizing SPARQL answer coverage, is unique.
>>>     We empirically show that the relevance of triples for sampling (a
>>>     semantic notion) is influenced by the topology of the graph (purely
>>>     structural), and can be determined
>>>     without prior knowledge of the queries.
>>>     Experiments show a significantly higher recall of topology based
>>>     sampling methods over random and naive baseline approaches (e.g. up
>>>     to 90% for Open-BioMed at a sample size of 6%).
>>>
>>>
>>> And, to support LOD-scale experiments, you might be interested in the
>>> LOD Laundromat[2,3] as well, presented this Thursday at ISWC as well.
>>> Here, we (re)publish clean, sanitized versions of Linked Data sets as
>>> sorted gzipped n-triples (13 billion triples and counting), with
>>> corresponding meta-data (e.g. the number of blank nodes in this
>> dataset[4]).
>>>
>>> Best, Laurens
>>>
>>> [1]
>>> http://laurensrietveld.nl/pdf/Structural_Properties_as_Proxy_for_Semantic_Relevance_in_RDF_Graph_Sampling.pdf
>>> [2]
>>> http://laurensrietveld.nl/pdf/LOD_Laundromat_-_A_Uniform_Way_of_Publishing_Other_Peoples_Dirty_Data.pdf
>>> [3] http://lodlaundromat.org
>>> [4]
>>> http://lodlaundromat.org/sparql/?query=PREFIX+llm%3A+%3Chttp%3A%2F%2Flodlaundromat.org%2Fmetrics%2Fontology%2F%3E%0APREFIX+void%3A+%3Chttp%3A%2F%2Frdfs.org%2Fns%2Fvoid%23%3E%0ASELECT+*+WHERE+%7B%0A++%5B%5D+llm%3Ametrics%2Fllm%3AdistinctBlankNodes+%3FnumBnodes+%3B%0A++++%09void%3AdataDump+%3Fdownload%0A%7D+ORDER+BY+DESC(%3FnumBnodes)+LIMIT+100
>>> --
>>>
>>> VU University Amsterdam____
>>>
>>> Faculty of Exact Sciences____
>>>
>>> Department of Computer Science____
>>>
>>> De Boelelaan 1081 A____
>>>
>>> 1081 HV Amsterdam____
>>>
>>> The Netherlands
>>>
>>> www.laurensrietveld.nl <http://www.laurensrietveld.nl>
>>>
>>> laurens.rietveld@vu.nl <mailto:laurens.rietveld@vu.nl>
>>>
>>> Visiting address:
>>>
>>> De Boelelaan 1081____
>>>
>>> Science Building Room T312
>>>
>>>
>>> On Mon, Oct 20, 2014 at 5:47 PM, Sandro Hawke <sandro@w3.org
>>> <mailto:sandro@w3.org>> wrote:
>>>
>>>     On 10/07/2014 10:25 PM, Sampo Syreeni wrote:
>>>> On 2014-10-07, Sandro Hawke wrote:
>>>>
>>>>> That may be true, but it is hard for me to see how any benefit this
>>>>> could bring would outweigh the absolute pain in the ass it would be
>>>>> for everyone to change their RDF stacks.
>>>
>>>     It was not me who said that.   That was Alan Ruttenberg.
>>>
>>>>
>>>> So, why not subdivide the process? It ought to be easy and efficient
>>>> enough to detect a rather expansive subset of graphs which do admit
>>>> unique and efficient labeling. At the very least graphs which only
>> use
>>>> a blank node precisely twice (to define something and to refer to it
>>>> once as in the bracket notation) are pretty simple, using a simple
>>>> hash table with counters -- that perhaps being the commonest case as
>>>> well.
>>>>
>>>> If the test succeeds, define a unique labeling based on the rest of
>>>> the attributes of the triple and lexical ordering; if not, ask the
>>>> user whether general graph isomorphism comparison is wanted, and if
>>>> so, do that, somehow signaling that it really went that far (perhaps
>>>> inband in the format of the labels? or out of band as the case may
>>>> be); if not, or if you can't do graph isomorphism in your code, then
>>>> slap on nonunique labels, again differentiating them somehow from the
>>>> first two cases.
>>>>
>>>> That is certainly not an easy or clean solution, but it doesn't break
>>>> the stack, and it works in most of the places where you want to do
>>>> fast path processing under the assumption that in fact the labels are
>>>> canonical, and can be relied upon to have 1-1 correpondence from
>>>> syntax to node.
>>>
>>>     I agree.   Does anyone have a good sampling of the LOD cloud we could
>>>     easily use for this experiment?
>>>
>>>            -- Sandro
>>
>>
>>
>

Received on Tuesday, 26 May 2015 21:00:56 UTC