I noticed that the most convenient way to deal with quotient structures (like the rational numbers or other equivalence classes) within ZFC is to select a unique representant from each equivalence class, which is possible due to global choice. Then I noticed that this strategy also seems to work quite well in practice, i.e. graph canonization is not really less practical than more general approaches to graph isomorphism. On a theoretical level however, it's hard to clear up the relation between graph canonization and graph isomorphism. The most basic problem is that graph canonization is not a decision problem, and there is no obvious way to reduce it to a decision problem either. In fact, it doesn't fit any problem type which comes to my mind!
Some computational problem types based on different types of requested output:
- decision problem
- optimization problem
- search problem
- counting problem
- function problem
Some computational problem types based on different types of expected input:
- offline/online problem
- (non-)promise problem
Yuval Filmus suggests that it is a canonization problem. However, all publications about canonization problems seem to treat questions closely related to graph canonization. I would rather prefer a wider problem class, maybe invariant (property) problem could be a nice class, if it could be suitably nailed down (and formalized).