Selecting the right partition in NAUTY
After the correspondence with the creators of nauty, the answer lies in the fact that the cell is selected deterministically so any isomorphic graph will have the same refinement. It's actually one of the ways to reduce the total number of permutations, because it does not need to check all possible discrete partitions. And also it means that nauty does not necessarily give the certificate minimal among all possible discrete partitions, but rather minimal among some subset of them.