A system, apparatus, and method for video categorization using heterogeneous signals are disclosed. One aspect of the disclosed embodiments is a method for categorizing a plurality of video streams. The method includes determining a plurality of features of at least some of the plurality of video streams, determining a category of a first video stream of the plurality of video stream based on its plurality of features, identifying, using a processor, a relationship between the first video stream and a second video stream of the plurality of videos, the relationship having an associated weight, and updating, using the processor, the category of the first video stream based on a first message determined using the associated weight.