Multimedia collections are ubiquitous and contain hundreds of hours of video information. The retrieval of a particular scene of a video (Known Item Search (KIS)) in a large collection is a difficult problem, considering the multimodal character of all video shots and the complexity of the query, either visual or textual. We tackle these challenges by fusing, first, multiple modalities in a nonlinear graph-based way for each subtopic of the query. Then, we fuse the top retrieved video shots per sub-query to provide the final list of retrieved shots, which is re-ranked using temporal information. The framework is evaluated in popular KIS tasks in the context of video shot retrieval and provides the largest Mean Reciprocal Rank scores.