Problems for which algorithms based on partition refinement run faster than in loglinear time
Some linear time modular decomposition algorithms use (some type of) partition refinement, see e.g. these algorithms for directed and undirected graphs.