How are Cross Edges handled in transversals?

Questions
#1

In breadth first search transversals, edges between nodes in the same frontier are cross edges.

  1. Do these cross edges connecting nodes in the same fronteir send messages or not?

  2. Are cross-edges labeled in transversals in a manner accessible to Reduce/Message/Apply some how or not?

  3. In bidirectional graphs, with a directed cross edge pointing both ways between two nodes, what is the execution order? Which node does the send first? Or does only one do the send? How do the send/receive sit in relation to the Apply? Or is this undefined?

I’ve looked at the documentation and code on this and don’t see any obvious answers.

Parallel BFS/DFS transversal implementation?
#2

These are good questions. There are two types of message propagation:

  • Node-based propagation first traverses a graph and generates frontiers in node sets. It then triggers the pull message passing API that collect messages from all predecessors and perform update.
  • Edge-based propagation first traverses a graph and generates frontiers in edge sets. It then triggers the send_and_recv message passing API that only sends messages along the given edge set.

In both modes, the order is always send -> receive -> apply. Node-based propagation APIs have name prop_node_XXX where XXX is the traversal algorithm. Likewise, edge-based propagation APIs have name prop_edge_YYY. The description is here: https://docs.dgl.ai/api/python/propagate.html.

We can then answer your questions.

  • Do these cross edges connecting nodes in the same fronteir send messages or not?

Yes they do. Because prop_nodes_bfs is a node-based propagation, all the nodes in each frontier call the pull operation that gathers messages from either nodes in the previous frontiers or within the current one.

  • Are cross-edges labeled in transversals in a manner accessible to Reduce/Message/Apply some how or not?

Yes they are. Cross-edges do participate in message passing at each step.

  • In bidirectional graphs, with a directed cross edge pointing both ways between two nodes, what is the execution order? Which node does the send first? Or does only one do the send? How do the send/receive sit in relation to the Apply? Or is this undefined?

The send/recv/apply will happen synchronously for both nodes. This is similar to update_all where nodes will receive messages from each others.

#3

How are the cross edges labeled? How can the send/receive/apply code tell which edges are cross edges and which ones are not?

#4

We don’t distinguish them with other edges. For example, suppose there are two node frontiers [0] [1, 2] and edges are (0, 1) (2, 1) (1, 2). In prop_nodes_bfs, pull on the second frontier will trigger send on all edges and recv/apply on node 1 and 2.

#5

Got it. I see. That is not the desired behavior for our application. Is there any way to put the cross edges into a different inbox than the non-cross edges?

#6

You can generate the edge frontiers manually and then call DGLGraph.prop_edges. The API essentially calls send_and_recv on each edge frontier set. You can split the cross-edge and non-cross-edge to two edge sets so to perform message passing differently.

1 Like