Purpose of probes?

[LSaldyt]

I'm going through the CLRS dataset and trying to understand it -- I'm working on a project that looks at how graph neural networks learn algorithms, and how faithful these algorithms are to the ground truth versions.

One part I'm confused about is why we would want to encode answers and hints as what are called "probes". I'm unfamiliar with this term, and curious if it's mentioned somewhere in the literature or if it's just specific to the CLRS implementation. Are there papers or further documentation on them?

The simplest example would be running bubble sort, which creates the indices of the sorted array as pointers in A_pos, but returns the answer as a probe.

For example, if sorting the array A = [3, 4, 2, 1], the correct A_pos is [3, 2, 0, 1] (so that A[A_pos] = [1, 2, 3, 4]). However, when converted into a probe, A_pos becomes [2, 0, 3, 3], which is output as the "pred" field from CLRS. While I've noticed how probe arrays are created, and that this is invertible, I'm trying to understand why we'd want to use this for training and evaluation, and what the advantage is over just using A_pos.

Thanks!

Also: I'm doing a lot of work related to CLRS, and curious what the best communication method is for questions like this.

[LSaldyt]

As far as I've understood so far, I suppose the probes are in the form of predecessor maps, which perhaps is a more flexible representation especially for graph-problems and graph neural networks specifically?

#113

[PetarV-]

Hi Lucas,

Thanks for raising this issue and your kind interest in CLRS!

One part I'm confused about is why we would want to encode answers and hints as what are called "probes". I'm unfamiliar with this term, and curious if it's mentioned somewhere in the literature or if it's just specific to the CLRS implementation. Are there papers or further documentation on them?

You shouldn't read too much into the terminology around "probes" -- it's by no means an established term in the literature (or in the CLRS textbook); we just used it for the purpose of the paper and implementation to denote "a variable being tracked throughout the algorithm's execution".

The simplest example would be running bubble sort, which creates the indices of the sorted array as pointers in A_pos, but returns the answer as a probe.

The main reason for specially probing A_pos in this case (and many others) is to align the variables to the virtual machine we are modelling within CLRS.

Indeed, the raw values of A_pos being [3, 2, 0, 1] and the predecessor values of pred being [2, 0, 3, 3] conveys exactly the same information. In some sense, it shouldn't matter which one you choose (and, should you wish, you could modify the library to support either option).

The reason why we opt for the "predecessor" format is, as mentioned, to align better with how a GNN would process this data -- keeping in mind their permutation equivariance!

Specifically, when we say pred[0] = 2, this means "the predecessor of the key contained in node 0 is 2". Whereas, when you say A_pos[0] = 3, this means "the item at position 0 is 3". It is evident that the pred version is actually semantically tied to node 0's original key, whereas the A_pos only is tied to its position, and hence less aligned with the computation.

I hope this makes sense!

Also: I'm doing a lot of work related to CLRS, and curious what the best communication method is for questions like this.

That's great to hear! I think GitHub issues are a good way if you believe that answers will benefit the broader public. For more niche questions (and otherwise), I typically prefer direct email communication.

Thanks,
Petar