Preparation of multi-partite entangled quantum states under realistic experimental conditions invariably results in states with non-unit fidelity to the target state. Purification protocols address the need for higher fidelity states than what can be directly prepared. These protocols consume several noisy input states and return an output state of higher fidelity, succeeding probabilistically. We introduce a recurrence based purification protocol for two-colorable graph states on $d$-dimensional quantum systems (qudits). We analyze the performance of the protocol in terms of the minimal required fidelity of input states as well as the expected number of attempts required to successfully reach a specific target fidelity. We find that not only is the purification regime larger for states of greater qudit dimension, but the expected number of attempts to successfully purify a state may be orders of magnitude lower. We develop error thresholds for the protocol with faulty two-qudit operations using a general uncorrelated error model and study the dependence on system dimension and state node number. We observe that the gate error threshold of the protocol improves with increasing dimension and moreover that the threshold depends on the degree of the graph but is otherwise independent of the number of nodes. The qualitative behaviour of the error threshold is captured by an analytically solvable model in which a restricted class of errors is considered. The error thresholds determined here may serve as one benchmark of assessing whether future experimental implementations of two qudit operations function well enough to realize a practical advantage of replacing qubit with qudit states in a multi-partite quantum information protocol.