Identifying state symmetries plays a crucial role in minimiz-ing the number of states explored during search, yet identify-ing precisely all symmetries is computationally hard. In thecontext of learning general policies that solve instances ofarbitrary size from small instances, however, this computa-tional bottleneck is not a problem. In this paper, we addressthe task of identifying all state symmetries through the lensof the graph isomorphism problem. To accomplish this, werepresent states as undirected, labeled graphs that reflect therelational structure of states and the goal. We then use off-the-shelf graph isomorphism algorithms to determine whethertwo states are isomorphic with respect to the goal. The iso-morphism relationship forms equivalent classes that result inan abstract state space that can be used instead of the origi-nal one to learn general policies more efficiently. While thisabstract state space can be used for many different learningtasks, we focus on learning symbolic general policies wherewe show that the proposed approach can lead to significantspeedups.