We present a hierarchical graph-based approach for unknown object discovery in RGB-D point clouds captured with a Kinect-like sensor from unstructured scenes. A two-step approach is proposed which first extracts meaningful regions from an input scene through over-segmentation. Secondly, a procedure is introduced to detect compositions of such regions that can represent primitive-shaped object candidates like boxes or cylinders. Complex-shaped objects are interpreted as a composition of primitive-shaped objects, for instance, a teddy bear can consist of two convex-shaped arms, legs, a convex-shaped head and torso. An ensemble of classifiers is trained to learn patterns from the appearances of such neighboring primitive shapes that constitute complex-shaped objects. Therein the appearance is described by a set of features from the texture and geometry domain. For the experiments, a dataset was prepared which is publicly available, containing a set of scenes which consists of 296 human-annotated object instances in total. Experiments show that the proposed hierarchical approach is capable to extract meaningful regions: an under-segmentation rate of 2.6% has been achieved. Furthermore, objects are segmented with a segmentation rate of 92.9% which reflects the capability of our approach to detect potential object candidates within unstructured scenes.