We present a detailed global optimization study of cluster geometries with silica nano-clusters (SiO$_2$)$_N$ as a specific example. In an earlier study (Phys. Rev. Lett., 95: 185505, 2005) we used the Basin Hopping methodology combined with an empirical potential to find low-energy cluster geometries. These often exhibit defects such as dangling oxygens. In this contribution we will present an algorithm for global optimization of cluster geometries, which limits the search specifically to fully-coordinated cluster geometries, i.e. defectless clusters where each silicon atom is bonded to 4 oxygen atoms and each oxygen atom is bonded to 2 silicon atoms. This algorithm is based on performing Monte Carlo moves on the set of graphs rather than in coordinate space, the graph being the network of silicon-oxygen bonds. Promising low-energy geometries are selected for refinement using Density Functional Theory calculations. Clusters of a size of up to 30 SiO$_2$ units have been studied. The properties of low-energy fully-coordinated clusters will be compared to those of clusters with defects.