[Furnace] A Graph Algorithm-Based TinkerPop Project? -- or simply, DerivedGraph?

[Marko Rodriguez]

Hello,

For over a year now I've been wanting to introduce a new TinkerPop project called "Furnace." The purpose of Furnace is to provide property graph algorithms.

http://markorodriguez.com/2011/02/08/property-graph-algorithms/

The idea being that with multi-relational graphs (graphs with edge labels), there are, for instance, as many PageRanks as there are path-types in a graph.

http://markorodriguez.files.wordpress.com/2011/02/derived-graphs.png

Thus, in my mind, Furnace would look something like this:

Map<Vertex,Double> rank = PageRank.evaluate(Graph graph, Pipe step);

Thus, if we were in Groovy and using Gremlin, you could do:

PageRank.evaluate(g, _().out('knows').out('knows'))

..to calculate PageRank over the inferred FOAF graph that exists within the explicit "knows" graph.

Furnace would then have a library of standard graph algorithms that allow for inferred relations to be specified:

ShortestPath

PageRank

EigenvectorCentrality

AssortativeMixing

Diameter

Radius

...any standard graph algorithm.

For example: What is the shortest "went to the same school as a friend of mine" path between me and Stephen?

So while this sounds all dandy and fine and great, my concern all this time has been, "Can this notion of a derived/inferred/abstract/implicit graph be put into another TinkerPop project?." If so,J then something like JUNG would suffice for the algorithm implementations. 

https://github.com/tinkerpop/blueprints/wiki/JUNG-Ouplementation

Here is what I mean---imagine in Blueprints (?maybe Frames?) that there was a utility graph implementation called DerivedGraph (much like EventGraph or ReadOnlyGraph):

DerivedGraph dg = new DerivedGraph(Graph graph, ... ??)

DerivedVertex vertex = dg.getVertex(1);

Iterable<DerivedEdge> edges = vertex.getOutEdges("foaf");

...where "foaf" maps to some computation. E.g. _().out('knows').out('knows'). As such:

GraphJung jung = new GraphJung(dg);

PageRank pg = new PageRank(jung, "foaf"); // I forget the specific JUNG API call, but its something like that.

Map<Vertex,Double> rank = pg.evaluate();

The notion of a DerivedGraph would have various applications and would relegate the need for another TinkerPop project pointless because of the dependency with JUNG. (Or, we could do Furnace as to be more memory safe than JUNG (e.g. use persistent HashMaps for rankings) and can extend it with algorithms that JUNG doesn't have (e.g. AssortativeMixing).

So that is the state of my thoughts on the matter. My question then to the community is:

 

"What is the best way to implement DerviedGraph? ... Does anyone have a good idea of how DerivedGraph should be implemented?"

...hints: it relates to inference in RDF world.

Thanks,

Marko.

http://markorodriguez.com

[Russell Jurney]

I'm not sure. At the moment, I'm implementing algorithms in JRuby/Pacer as an extension of TinkerGraph, and sometimes in my own branch of blueprints which is... not sustainable.  

The idea of a DerivedGraph appeals to me, as I've basically done the same thing by extending TinkerGraph in my own project, including the use of JUNG, etc. 

Russell Jurney

twitter.com/rjurney

russell...@gmail.com

datasyndrome.com

[Joshua Shinavier]

Hey Marko.

Cool ideas. My $0.02:

+1 to API-level support for ranking. Btw. the "weighted iterator"
interface I have been pushing for in Blueprints could be used both for
full text query results and for ranking results. That's a little
different than a Map<Vertex,Double> in that you can't easily look up
the ranking of any particular vertex (element). On the other hand,
it's better suited to lazy evaluation via query pipelines.

+1 to DerivedGraph / virtual graphs. I'm not sure this even needs to
be a single class or interface; it's more of a concept which can be
realized in different ways. For example, we could create a
PageRankGraph as an implementation of Graph, which is constructed with
a pipeline argument and a property name (e.g. "pagerank") and is
layered on top of any other Graph. It would behave identically to
that Graph except that when you look up a PageRank value by calling
v.getProperty("pagerank") on one of its vertices, you would trigger
the ranking operation (if the Graph has changed since the last lookup.
Otherwise you would just retrieve the latest computed value for that
vertex). The "pagerank" properties could either be materialized in
the underlying Graph or stored separately, e.g. in a persistent hash
map or just in memory.
Maybe PageRankGraph would extend an abstract class which applies
ranking algorithms to a graph and provides the results as properties.
However, there could be other kinds of derived graphs which actually
add or subtract vertices and edges (such as virtual subgraphs).

At the same time, I think a case can be made for a new TinkerPop
project (or maybe just a new Blueprints module....
blueprints-algorithms?) with efficient implementations of ranking
algorithms that can be applied to large graphs.

Dunno which of the above becomes Furnace... ?

Best,

Josh

[Russell Jurney]

I'd hate to have a new class for each graph operation. That's a lot of classes.

Russell Jurney
twitter.com/rjurney
russell...@gmail.com
datasyndrome.com

[Lukasz]

Does this actually mean that Furnace can't be used with Gremlin at the moment? I've tried the installation method described here:

https://groups.google.com/forum/#!topic/gremlin-users/iYpjj9waWt0

but getting error (repository missing?):

gremlin> Grape.grab([group:'com.tinkerpop.furnace', module:'furnace', version:'0.1-SNAPSHOT'])
Error grabbing Grapes -- [unresolved dependency: com.tinkerpop.furnace#furnace;0.1-SNAPSHOT: not found]

I would really love to be able to use CommunityGenerator, as it seems to be the best way (compared to igraph, networkx etc. generators) to create networks with clear community structure.

I'm on OS X 10.6.8 and my Gremlin is 2.4.0, pre-build (I am only starting with tinkerpop/neo4j etc. and bit scared of maven)

cheers,
Lukasz

[Lukasz]

Well, I'm sorry, this post was meant for "status of furnace" thread. Still, I would appreciate any help on getting Furnace to work with Gremlin.
L

[Stephen Mallette]

To use Furnace in Gremlin you can either build Furnace locally and then do that Grape call (check the version number if you do that as it has changed) or you can try to add a resolver for the sonatype snapshot repo:

Grape.addResolver([name: 'sonatype-snapshots', root: 'https://oss.sonatype.org/content/repositories/snapshots', m2Compatible: 'true'])

Stephen

--
You received this message because you are subscribed to the Google Groups "Gremlin-users" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gremlin-user...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Lukasz]

Thank you Stephen, I went for local  build after all (I used maven on cloned git, and I guess I just copied target jar file to gremlin's lib directory and it seemed to work).

BTW is Furnace accessible from Bulbs?

L.

--

[Stephen Mallette]

copying the jars works as well.  glad it is working.  you should be able to access furnace via bulbs (i.e. sending raw gremlin scripts to rexster) if you copy the furnace jar to the rexster ext directory and configure rexster.xml with the appropriate <imports> as described on the rexster configuration page:

https://github.com/tinkerpop/rexster/wiki/Rexster-Configuration#other-elements

[Sridhar Ramachandran]

Hi Marko,

You could use Pixy for graphs derived using inferences based on first-order logic, where vertices in the derived graph are a subset of the vertices in the base graph. The same design works without Pixy (discussed at the end).

Here's the pseudo-code for the usage:

PixyTheory pt = new PixyTheory('''person(X) :- property(X, 'type', 'person'). foaf(X, Y) :- out(X, 'friend', Z), out(Z, 'friend', Z).''')
DerivedGraph dg = pt.subGraph('person', 'foaf'); // person/1 is the vertex predicate and foaf/2 is the out predicate

Here's the outline of the implementation with Pixy:

public class DerivedGraph implements Graph {
    Graph g;
    PixyTheory pt;

    public DerivedGraph(Graph g, PixyTheory baseTheory, String vertexPredicate, String outPredicate) {
        this.g = g;
        this.pt = baseTheory.extend(
            "my_out(Vout, Vin) :- " + outPredicate + "(Vout, Vin), " + vertexPredicate + "(Vin). " +
            "my_in(Vin, Vout) :- " + outPredicate + "(Vout, Vin), " + vertexPredicate + "(Vout). " +
            "my_both(V1, V2) :- my_out(V1, V2). " +
            "my_both(V1, V2) :- my_in(V1, V2). ");
    }

    public Vertex getVertex(Object id) {
        // Writing Groovy style
        // The GremlinPipeline starting with as() can be pre-computed
        return g.V(id).as('v').makePipe(vertexPredicate + "($)").transform({ it, m -> new VertexWrapper(m.v) });
    }

    public Iterable<Vertex> getVertices() {
        return g.V().as('v').as('v').makePipe(vertexPredicate + "($)").transform({ it, m -> new VertexWrapper(m.v) });
    }

    // Edges not supported

    public class VertexWrapper implements Vertex {
        Vertex v;

        public VertexWrapper(Vertex v) {
           this.v = v;
        }

        public Iterable<Vertex> getVertices(final Direction direction, String... labels) {
           // Labels not supported
           return v.makePipe("my_" + direction.toString().toLowerCase + "($, &)").transform({ new VertexWrapper(it) });
        }

        public Iterable<Edge> getEdges(final Direction direction, String... labels) {
           // Labels not supported
           // EdgeWrapper is a POJO holding Vin and Vout
           return v.as('v1').makePipe("my_" + direction.toString().toLowerCase + "($, &v2)").transform({ it, m -> new EdgeWrapper(direction, v1, v2) });;
        }
    }
}

The same design works without Pixy, if the DerivedGraph takes 3 Pipes for the vertexFilter, inStep and outStep. This will require the user to provide the correct 'in' step. In the above case, Pixy does the work of finding the reverse path.

Regards,

Sridhar.
Founder, LambdaZen LLC