We address the problem of class agnostic, joint instance segmentation of scene data. While learning-based semantic instance segmentation methods have achieved impressive progress, their use is limited in robotics applications due to reliance on expensive training data annotations and assumptions of single sensor modality or known object classes. We propose a novel graph-based instance segmentation approach that combines information from a 2D image sequence and a 3D point cloud capturing the scene. Our approach propagates information with a general graph representation to produce a segmentation taking into account both geometric and photometric information. This allows us to leverage information from complementary sensor modalities without requiring training data. Our method shows improved object recall and boundary identification over state-of-the-art RGB-D segmentation methods. We demonstrate generality by evaluating on both RGB-D data and a LiDAR+image sensor data.