Exploring Linked Data with Gremlin

Gremlin is a free Java/Groovy system for traversing graphs, including but not limited to RDF. This post is based on example code from Marko Rodriguez (@twarko) and the Gremlin wiki and mailing list. The test run below goes pretty slowly when run with 4 or 5 loops, since it uses the Web as its database, via entry-by-entry fetches. In this case it’s fetching from DBpedia, but I’ve ran it with a few tweaks against Freebase happily too. The on-demand RDF is handled by the Linked Data Sail developed by Joshua Shinavier; same thing would work directly against a database too. If you like Gremlin you’ll also Joshua’s Ripple work (see screencast, code, wiki).

Why is this interesting? Don’t we already have SPARQL? And SPARQL 1.1 even has paths.  I’d like to see a bit more convergence with SPARQL, but this is a different style of dealing with graph data. The most intriguing difference from SPARQL here is the ability to drop in Turing-complete fragments throughout the ‘query’; for example in the { closure block } shown below. I’m also, for hard-to-articulate reasons, reminded somehow of Apache’s Pig language. Although Pig doesn’t allow arbitrary script, it does encourage a pipeline perspective on data processing.

So in this example we start exploring the graph from one vertex, we’ll call it ‘fry’, representing Stephen Fry’s dbpedia entry. The idea is to collect up information about actors and their co-starring patterns as recorded in Wikipedia.

Here is the full setup code needed; it can be run interactively in the Gremlin commandline console. So it runs quickly we loop only twice.

g = new LinkedDataSailGraph(new MemoryStoreSailGraph())
fry = g.v(‘http://dbpedia.org/resource/Stephen_Fry’)
g.addNamespace(‘wp’, ‘http://dbpedia.org/ontology/’)
m = [:]

From here, everything else is in one line:
fry.in(‘wp:starring’).out(‘wp:starring’).groupCount(m).loop(3){it.loops <2}

This corresponds to a series of steps (which map to TinkerPop / Blueprints / Pipes API calls behind the scenes). I’ve marked the steps in bold here:

  • in: ‘wp:starring’: from our initial vertice, representing Stephen Fry, we step to vertices that point to us with a ‘wp:starring’ link
  • out: from those vertices, we follow outgoing edges marked ‘wp:starring’ (including those back to Stephen Fry), taking us to things that he and his co-stars starred in, i.e. TV shows and films.
  • we then call groupCount and pass it our bookkeeping hashtable, ‘m’. It increments a counter based on ID of current vertex or edge. As we revisit the same vertex later, the total counter for that entity goes up.
  • from this point, we then go back 3 steps, and recurse several times.  e.g. “{ it.loops < 3 }” (this last is a closure; we can drop any code in here…)

This maybe gives a flavour. See the Gremlin Wiki for the real goods. The first version of this post was verbose, as I had Gremlin step explictly into graph edges, and back into vertices each time. Gremlin allows edges to have properties, which is useful both for representing non-RDF data, but also for apps to keep annotations on RDF triples. It also exposes ‘named graph’ URIs on each edge with an ‘ng’ property. You can step from a vertex into an edge with ‘inE’, ‘outE’ and other steps; again check the wiki for details.

From an application and data perspective, the Gremlin system is interesting as it allows quantitatively minded graph explorations to be used alongside classically factual SPARQL. The results below show that it can dig out an actor’s co-stars (and then take account of their co-stars, and so on). This sort of neighbourhood exploration helps balance out the messyness of much Linked Data; rather than relying on explicitly asserted facts from the dataset, we can also add in derived data that comes from counting things expressed in dozens or hundreds of pages.

Once the Gremlin loops are finished, we can examine the state of our book-keeping object, ‘m’:

Back in the gremlin.sh commandline interface (effectively typing in Groovy) we can do this…

gremlin> m2 = m.sort{ a,b -> b.value <=> a.value }

==>v[http://dbpedia.org/resource/Stephen_Fry]=58
==>v[http://dbpedia.org/resource/Hugh_Laurie]=9
==>v[http://dbpedia.org/resource/Tony_Robinson]=6
==>v[http://dbpedia.org/resource/Rowan_Atkinson]=6
==>v[http://dbpedia.org/resource/Miranda_Richardson]=4
==>v[http://dbpedia.org/resource/Tim_McInnerny]=4
==>v[http://dbpedia.org/resource/Tony_Slattery]=3
==>v[http://dbpedia.org/resource/Emma_Thompson]=3
==>v[http://dbpedia.org/resource/Robbie_Coltrane]=3
==>v[http://dbpedia.org/resource/John_Lithgow]=2
==>v[http://dbpedia.org/resource/Emily_Watson]=2
==>v[http://dbpedia.org/resource/Colin_Firth]=2
==>v[http://dbpedia.org/resource/Sandi_Toksvig]=1
==>v[http://dbpedia.org/resource/John_Sessions]=1
==>v[http://dbpedia.org/resource/Greg_Proops]=1
==>v[http://dbpedia.org/resource/Paul_Merton]=1
==>v[http://dbpedia.org/resource/Mike_McShane]=1
==>v[http://dbpedia.org/resource/Ryan_Stiles]=1
==>v[http://dbpedia.org/resource/Colin_Mochrie]=1
==>v[http://dbpedia.org/resource/Josie_Lawrence]=1
[...]

Now how would this look if we looped around a few more times? i.e. re ran our co-star traversal from each of the final vertices we settled on?
Here are the results from a longer run. The difference you see will depend upon the shape of the graph, the kind of link types you’re traversing, and so forth. And also, of course, on the nature of the things in the world that the graph describes. Here are the Gremlin results when we loop 5 times instead of 2:

==>v[http://dbpedia.org/resource/Stephen_Fry]=8160
==>v[http://dbpedia.org/resource/Hugh_Laurie]=3641
==>v[http://dbpedia.org/resource/Rowan_Atkinson]=2481
==>v[http://dbpedia.org/resource/Tony_Robinson]=2168
==>v[http://dbpedia.org/resource/Miranda_Richardson]=1791
==>v[http://dbpedia.org/resource/Tim_McInnerny]=1398
==>v[http://dbpedia.org/resource/Emma_Thompson]=1307
==>v[http://dbpedia.org/resource/Robbie_Coltrane]=1303
==>v[http://dbpedia.org/resource/Tony_Slattery]=911
==>v[http://dbpedia.org/resource/Colin_Firth]=854
==>v[http://dbpedia.org/resource/John_Lithgow]=732 [...]

4 Responses to Exploring Linked Data with Gremlin

  1. danbri says:

    What if we don’t want to traverse back to our first node?

    gremlin> fry.in(‘wp:starring’).out(‘wp:starring’) { it.id != fry.id }

    How to poke around in the results:

    gremlin> m2.subMap((m2.keySet() as List)[0..20])

    Apologies that the examples don’t copy/paste from wordpress into runable code; some character problems in wordpress. Investigating.

  2. danbri says:

    gremlin> g = new LinkedDataSailGraph(new MemoryStoreSailGraph())
    ==>sailgraph[linkeddatasail]
    gremlin> d1 = g.v(‘http://identi.ca/user/114′)
    ==>v[http://identi.ca/user/114]
    gremlin> n1 = d1.out(‘foaf:knows’).out(‘foaf:name’)

    ==>v["kael"]
    ==>v["Dan Brickley"]
    ==>v["Brian Manley"]
    ==>v["Yoan Blanc"]
    ==>v["Robert Mark White"]
    ==>v["Jim Hughes"]
    ==>v["Marco Frattola"]
    ==>v["Mike Amundsen"]
    ==>v["John Goodwin"]
    ==>v["Matt Lee"]
    ==>v["Keith Alexander"]
    ==>v["Marjolein Katsma"]
    ==>v["Ross Singer"]
    ==>v["Jon Phipps"]
    ==>v["Gautier Poupeau"]
    ==>v["Jaakko Rajaniemi"]
    ==>v["Davide Palmisano"]
    ==>v["CaptSolo"]
    [Fatal Error] 31552:3196:1: XML document structures must start and end within the same entity.
    ==>v["Jonas Halvorsen"]
    ==>v["olivier Thereaux"]
    ==>v["Karl Dubost"]
    ==>v["Libby Miller"]
    ==>v["VoCamp"]
    ==>v["Sergio Fern?ndez"]
    ==>v["james melendez"]
    ==>v["Yrj?n? Rankka"]
    ==>v["Marvin Preuss"]
    ==>v["Laurens Holst"]
    ==>v["info dal basso"]
    ==>v["Raphael Troncy"]
    ==>v["Henry J. Story"]
    ==>v["W3C (World Wide Web Consortium)"]
    ==>v["Arto Bendiken"]
    ==>v["Graham Perrin"]
    ==>v["some more individual"]
    ==>v["Bob Ferris"]
    ==>v["Scute New"]
    gremlin>

  3. danbri says:

    Also …

    g = new LinkedDataSailGraph(new MemoryStoreSailGraph())
    c22 = g.v(‘http://dbpedia.org/resource/Catch-22′)
    g.addNamespace(‘dct’, ‘http://purl.org/dc/terms/’)
    m = [:]
    c22.out(‘dct:subject’).in(‘dct:subject’).out(‘dct:subject’).groupCount(m).back(2).loop(1){it.loops<3}

    …top 20:

    ==>v[http://dbpedia.org/resource/Category:Debut_novels]=2636
    ==>v[http://dbpedia.org/resource/Category:American_novels_adapted_into_films]=1684
    ==>v[http://dbpedia.org/resource/Category:Postmodern_literature]=928
    ==>v[http://dbpedia.org/resource/Category:World_War_II_novels]=840
    ==>v[http://dbpedia.org/resource/Category:1961_novels]=614
    ==>v[http://dbpedia.org/resource/Category:American_novels]=592
    ==>v[http://dbpedia.org/resource/Category:Satirical_novels]=466
    ==>v[http://dbpedia.org/resource/Category:Anti-war_novels]=292
    ==>v[http://dbpedia.org/resource/Category:Black_comedy_books]=224
    ==>v[http://dbpedia.org/resource/Category:British_novels]=136
    ==>v[http://dbpedia.org/resource/Category:Metafictional_works]=120
    ==>v[http://dbpedia.org/resource/Category:Novels_by_Joseph_Heller]=112
    ==>v[http://dbpedia.org/resource/Category:21st-century_American_novels]=96
    ==>v[http://dbpedia.org/resource/Category:Catch-22]=94
    ==>v[http://dbpedia.org/resource/Category:Science_fiction_novels]=94
    ==>v[http://dbpedia.org/resource/Category:Novels_adapted_into_films]=88
    ==>v[http://dbpedia.org/resource/Category:2003_novels]=88
    ==>v[http://dbpedia.org/resource/Category:2007_novels]=82
    ==>v[http://dbpedia.org/resource/Category:American_young_adult_novels]=78
    ==>v[http://dbpedia.org/resource/Category:Historical_novels]=68
    ==>v[http://dbpedia.org/resource/Category:2004_novels]=68

  4. Trying this now…wish me luck.

Leave a Reply