Disjoint Sampling - C/C++/PLC APIs

[alexbarghi-nv]

Disjoint sampling requires that each seed vertex have a separate, non-overlapping subgraph.

Pseudocode:

(begin hop k; suppose fanout is [f, f, ...])
for each node n:
  u = get_all_neighbors(n)
  u = select_neighbors(u, n, f)
  add_nodes_to_hop(u)

function select_neighbors(u, n, f):
  for v in u:
    if v in visited and visited[v] != n:
      remove v from u
    visited[v] = n

  return first f nodes from u

[ChuckHastings]

Several questions.

1. There's no randomness in your pseudocode. Should I assume that the for v in u loop is processing the vertices in u in a random order?
2. How do we break ties? That is, suppose vertex v1 and v2 are in the same frontier, and they have a common neighbor v3. Who gets to keep the common neighbor? In the serial code above we finish v1 before we finish v2, so v1 would get v3 (if it's in the first f nodes). On the GPU we'll be processing v1 and v2 in parallel. Is it important which one wins the parallel race? Are we OK with non-deterministic behavior (that is sometimes it will be assigned to v1 and other times to v2)? Or do we need to add some determinism into the computation (tie goes to the smaller vertex id, or something like that)?

This is likely to be expensive. On multi GPUs, we're likely going to need to oversample, shuffle and discard and potentially need to resample if we have to discard too many.

[alexbarghi-nv]

Several questions.

1. There's no randomness in your pseudocode. Should I assume that the for v in u loop is processing the vertices in u in a random order?
2. How do we break ties? That is, suppose vertex v1 and v2 are in the same frontier, and they have a common neighbor v3. Who gets to keep the common neighbor? In the serial code above we finish v1 before we finish v2, so v1 would get v3 (if it's in the first f nodes). On the GPU we'll be processing v1 and v2 in parallel. Is it important which one wins the parallel race? Are we OK with non-deterministic behavior (that is sometimes it will be assigned to v1 and other times to v2)? Or do we need to add some determinism into the computation (tie goes to the smaller vertex id, or something like that)?

This is likely to be expensive. On multi GPUs, we're likely going to need to oversample, shuffle and discard and potentially need to resample if we have to discard too many.

(1) - Yes, they're in a random order.
(2) - Non-determinism is ok, and probably actually a good thing since it will make it more likely that each round generates different subgraphs.
(3) - It's very expensive in the current non-GPU implementation so that's not unexpected. I'm not expecting this to run at the same speed as non-disjoint sampling.