Radical ontic structural realism (ROSR) claims that structure exists independently of objects that may instantiate it. Critics of ROSR contend that this claim is conceptually incoherent, insofar as, (i) it entails there can be relations without relata, and (ii) there is a conceptual dependence between relations and relata. In this essay I suggest that (ii) is motivated by a set-theoretic formulation of structure, and that adopting a category-theoretic formulation may provide ROSR with more support. In particular, I consider how a category-theoretic formulation of structure can be developed that denies (ii), and can be made to do work in the context of formulating theories in physics.