Take the 2-minute tour ×

I'm planning on running a machine learning algorithm that learns node values and edge weights. The algorithm is very similar to the value iteration algorithm here. Each node represents a location and each edge is a path to a new location. Each node and edge maintains a value that represents how desirable it is. These values are updated every iteration based on the values of the previous iteration.

I plan on using neo4j as the backend. There will be around 600,000 Nodes and 100,000,000 edges for now, but more may be added later (The graph won't fit in memory). What is the best way to retain the values from the previous iteration? 2 ways that come to mind are:

  1. clone the current database and use 1 copy as the "current iteration" copy and 1 copy as the "previous iteration" copy.
  2. At the end of every iteration move all values of each node and edge to a "previous iteration" property.

How do people usually do this? Is there a better way?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

what is the size of the graph, and how many iterations are you doing? With smaller graphs, I would duplicate the graph in versions, either on disk as a new graph, or just as a subgraph in the same database.

With bigger amounts, I think the property archiving approach is a better one.

share|improve this answer
around 20 iterations on a graph with 600,000 nodes and 100,000,000 edges –  stackOverlord Jan 12 '12 at 4:28
Mmh, this sounds like archiving is the better solution. Do you need to do any operations that span different iterations in the same query? –  Peter Neubauer Jan 17 '12 at 9:54

The MDP article you reference gives a good overview of value and policy iteration, but stops short of mentioning asynchronous dynamic programming. The fact is that you don't need to perform full isolated sweeps of the graph for the values to converge [1]; you can update the vertices one at a time in any order, given that you don't neglect any of them. That is, you don't need to make a copy of the graph at all.

[1] Bertsekas, D., 1982. Distributed dynamic programming. IEEE Transactions on Automatic Control, 27(3), p.610-616.

share|improve this answer
Yes, I will only be needing one previous state and action –  stackOverlord Jan 12 '12 at 4:31
As I understand it, this would be only an edge index and a vertex index. –  Don Reba Jan 12 '12 at 6:05
I'm not quite sure what you mean by "your graph represents the state function". I've updated my question with more details about my problem, sorry for any confusion. –  stackOverlord Jan 12 '12 at 19:33
@stackOverlord, good update. I changed my answer accordingly. –  Don Reba Jan 12 '12 at 22:42
Thanks Don! I'm going to go with your answer for my implementation but I'll accept Peter's answer since it speaks to my original question (even though my question makes some false assumptions). –  stackOverlord Jan 14 '12 at 22:33

Your Answer


