Why the outputs of bfs and dfs algorithms are the same

[danielkorzekwa]

Consider

DIRECTED = np.array([
    [0, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0],
])

#out, probes = graphs.bfs(DIRECTED, 0)
out, probes = graphs.dfs(DIRECTED)
probes

# From probes for both dfs anf bfs algorithms:
'output': {'node': {'pi': {'data': array([0, 0, 0, 1, 1, 2]),
    'type_': 'pointer'}},

How can I evaluate my DL model to conduct BFS or DFS algorithms if both algorithms provide the same output in probes? Is it a mistake in how these algorithms are implemented in the CLRS benchmark or I miss something? Of course, there are hints: pi_h that show the trajectory of the visited nodes, but still the final outputs are the same for BFS and DFS. What if I want to train a DL model without hints?

Proposed solutions: 1) Represent the outputs of bfs/dfs with the indexes of visited nodes in the order or visiting, so for the example above it would be: [0,1,2,3,4,5] for bfs and [0,1,3,4,2,5] for dfs - this would uniquely identify both algorithms.

2) Looking at the Insertion sort example https://arxiv.org/pdf/2205.15659, I can see you want to keep the input and output of the DL model to be a graph of the same size and use edges to indicate the output of an algorithm. So why not using the predecessor node indexes to previously visiting nodes. If the node has not previously visited node, then keep the node index itself, then: bfs: [0,0,0,1,1,2] dfs: [0,0,1,3,4,2]

PS. It took me sometime to figure out what is the meaning of the output for BFS/DFS algorithms - Now I know these are the predecessor nodes in the graph but only for those nodes that were visited during the algorithm run. If the node was not visited, then it would point to itself (what motivates this representation?) This is clear when looking at the hints for pi:

'pi_h': {'data': array([[0, 1, 2, 3, 4, 5],
           [0, 0, 0, 3, 4, 5],
           [0, 0, 0, 1, 1, 2]]),

How about adding better documentation for bfs/dfs algorithms to explain what the output is. Currently there no doc at all in the code: https://github.com/google-deepmind/clrs/blob/master/clrs/_src/algorithms/graphs_test.py

[PetarV-]

Hi Daniel,

Thank you for raising this issue! Let me try to address your points in turn:

How can I evaluate my DL model to conduct BFS or DFS algorithms if both algorithms provide the same output in probes?

You've picked a particular example where BFS and DFS will retrieve the same output value. But actually, for the particular case of BFS and DFS, in most input cases the two algorithms will yield different output values -- this is due to the fact the former explores nodes in a parallel manner, whereas the latter explores them in a sequential / recursive manner. So as long as you train / evaluate across a large enough number of samples, you will tend to observe very different behaviours when learning BFS vs. DFS.

Is it a mistake in how these algorithms are implemented in the CLRS benchmark or I miss something?

No, the algorithms were deliberately implemented in this way.

To clarify on why only the predecessor pointers are the outputs of BFS and DFS and nothing else, our benchmark is guided by the representations utilised in the CLRS textbook (3rd edition) wherever possible (+ parallelisation improvements to hints where simple to do, and tiebreaking to avoid ambiguous outputs). And as can be seen for both BFS (Figure 22.3 in the book) and DFS (Figure 22.4 in the book), the final output of the algorithm is a collection of predecessor pointers for every node.

What if I want to train a DL model without hints?

Then, on those particular examples, your model will receive the same supervision signal. But, as already explained above, for BFS and DFS, this difference is not so important in a distributional sense. There are far more grave offenders, for example, we have four sorting algorithms which always yield exactly the same input/output pairs :)

However, the way in which you propose to "fix" this problem is, if I understand it correctly, to take auxiliary information (order of visiting of nodes), which is already implicitly encoded e.g. in the 'u' hint of DFS and create an output version of it. I would argue that when you do things this way, at least from the perspective of what is "input" and "output" in the textbook, you are effectively learning with a hint. :)

In conclusion: based on my understanding of your issue, the framework is working exactly as we intended it to. It is true that different variants of the algorithms and specs can be constructed such that more auxiliary information is preserved in the outputs, and this might help disambiguate some of the algorithms. We did not want to do this in our reference implementation, because it would arguably deviate from what's inside the textbook.

But there's nothing in CLRS-30 that stops you from doing this modification: in fact, the library is designed to be extensible with new algorithms or algorithm variants.

To give just a few recent examples from published work that relate to DFS:

• Hint-ReLIC (ICML'23; https://proceedings.mlr.press/v202/bevilacqua23a.html) reverses all the node pointers in DFS to enable perfect generalisation on the default CLRS test distribution.
• RAR (LoG'23; https://arxiv.org/abs/2307.00337) makes a very different variant of DFS' hint structure, which enables explicitly-recursive models to perform better.

How about adding better documentation for bfs/dfs algorithms to explain what the output is.

I agree that adding more docs would help the code's readability. This is something we hope to get around to but we're reasonably constrained by time: already the main framework (with all of its internal automations) took several years to build, and we need to balance any maintenance work on CLRS-30 with our other daily commitments.

We of course welcome pull requests of this kind; if you (or anyone else) are keen to contribute by writing some documentation for the algorithms' outputs, this would of course be much appreciated!

Thanks, Petar

[danielkorzekwa]

Great response, thanks. Looking at https://github.com/google-deepmind/clrs/blob/master/clrs/_src/algorithms/graphs_test.py, test_dfs() and test_bfs() actually produce different outputs for the DIRECTED graph.