Previous work on interactive 3D labeling focused on improving user experience based on virtual/augmented reality and, thereby, speeding-up the labeling of scenes. In this article, we present a novel interactive, collaborative VR-based 3D labeling system for live-captured scenes by multiple remotely connected users based on sparse multi-user input with automatic label propagation and completion. Hence, our system is particularly beneficial in the case of multiple users that are able to label different scene parts from the respectively adequate views in parallel. Our proposed system relies on 1) the RGB-D capture of an environment by a user, 2) a reconstruction client that integrates this stream into a 3D model, 3) a server that gets scene updates and manages the global 3D scene model as well as client requests and the integration/propagation of labels, 4) labeling clients that allow an independent VR-based scene exploration and labeling for each user, and 5) remotely connected users that provide a sparse 3D labeling used to control the label propagation over objects and the label prediction to other scene parts. Our evaluation demonstrates the intuitive collaborative 3D labeling experience as well as its capability to meet the efficiency constraints regarding reconstruction speed, data streaming, visualization, and labeling.