Certain aspects and features of this disclosure relate to graph-based video instance segmentation. In one example, a reference instance of an object in a reference frame and features in a target frame are identified and used to produce a graph of nodes and edges. Each node represents a feature in the target frame or the reference instance of the object in the reference frame. Each edge of the graph represents a spatiotemporal relationship between the feature in the target frame and the reference instance of the object. Embeddings of the nodes and edges of the graph are iteratively updated based on the spatiotemporal relationship between a feature in the target frame and the reference instance of the object in the reference frame, resulting in a fused node embedding that can be used for detecting the target instance of the object.