Stream of Updates on Graph

User 1245 | 1/28/2015, 5:58:22 PM

Hi

Does GraphLab have the feature which takes the adding of edges/vertices to the already built graph (like stream of updates on the graph) ?

Comments

User 1190 | 1/28/2015, 6:26:29 PM

SGraph in GraphLab-Create does support incremental updates. You can add new vertices and edges to existing SGraph. In case of collision, e.g. adding vertices with same id or edges with same source/destination id, the behavior is as follows: - duplicate edges are allowed. - duplicate vertices will be merged. If you add a new vertex with the same id as existing an existing vertex, the new vertex data will overwrite the existing vertex data.

However, the SGraph is designed for bulk analysis and not optimized for transactional updates. The support for incremental changes to the graph structure is mainly for the programming convenience. When you have stream of updates, you may want to consider buffer the updates, and issue the query in batch.


User 1245 | 1/29/2015, 4:41:49 AM

Will it re evaluate the whole graph again with updates(like addition of vertices & edges) or it only recomputes the only required vertices? For example: time taken for execution of graph 'g' is t, then incremental update is happened to the graph and recomputational time for the graph 'g' + (incremental update) is 't2' ; 't2' < 't' ? or 't2' >='t' ?

Is there any graph algorithm where i can understand this incremental feature of GraphLab ? is SGraph can be created in only python or in c++ also ? Can you give some example program for better understanding ?


User 1245 | 2/2/2015, 8:33:11 PM

Can some one rectify my doubt ?


User 19 | 2/3/2015, 1:07:13 AM

Hi ssudheer050,

As Jay mentioned, it is possible to add new vertices and edges to an existing SGraph, and adding vertices will require a computation time t2 < t (using your notation). There is some computation required to deduplicate vertices, so (as Jay said) the SGraph is not optimized for transactional updates

The most detailed information is in the <a href="https://dato.com/products/create/docs/generated/graphlab.SGraph.addvertices.html#graphlab.SGraph.addvertices">API docs</a> and the <a href="http://dato.com/learn/userguide/index.html#WorkingwithdataGraphdata">"Modifying Graphs" section of the User Guide</a>.

SGraphs can be created and manipulated via the C++ SDK.

If you have any more questions, please let us know!


User 1245 | 2/4/2015, 6:17:22 PM

Does graphlab has streaming feature for the graph computations ?


User 1190 | 2/4/2015, 7:45:53 PM

@ssudheer050 , in your example, t2 < t.


User 1245 | 2/11/2015, 10:06:52 AM

Can any one explain the logic on how graphlab handled the stream of updates on graph with out recomputation


User 1245 | 2/12/2015, 4:23:16 AM

Can some one rectify my doubt ?


User 1189 | 2/12/2015, 6:21:54 PM

Hi,

As mentioned above, the SGraph supports bulk updates (inserting of new vertices/edges, and efficient update of individual fields).

I am not sure what you mean by "computation/recomputation". Do you mean, for instance, the computation of PageRank? We do not have, builtin, the ability to perform incremental computation of PageRank after a graph modification. The PageRank computation will have to restart from scratch (or at best, a warm start).

Techniques for doing this do exist in certain cases though. For instance, it is easy to see that shortest path can support such incremental computation as long as you are only adding vertices/edges; never removing. (More generally there is a certain contraction property that has to be proved.)

Yucheng


User 1245 | 2/16/2015, 12:06:14 PM

Hi, My doubt is- suppose for graph 'G' the pagerank computation has done --> now edges and vertices are added --> now the computation starts from scratch for the updated graph or it will use the lastly computed data ?


User 954 | 2/16/2015, 6:26:36 PM

Hi, the page rank computation will start from the scratch. The incremental computation for many graph analytics is still an open problem. We can come up with customized incremental solution for some algorithms ( such as shortest path problem ), but a general incremental computation framework is a challenging problem.

some reference in this context: http://research.microsoft.com/apps/pubs/?id=201100


User 1245 | 2/17/2015, 1:07:04 PM

Can it be done using the snapshots of the graph ?