Content-based Video Retrieval (CBVR) wird auf Medienfreigabeplattformen beispielsweise für Anwendungen wie Videoempfehlungen und -filterung eingesetzt. Um Datenbanken zu verwalten, die bis zu Milliarden von Videos umfassen, werden bevorzugt videobasierte Ansätze verwendet, die feste Embeddings mit fester Größe nutzen, da diese aufgrund ihrer Effizienz vorteilhaft sind. In diesem Paper stellen wir Video Region Attention Graph Networks (VRAG) vor, welche die derzeit beste Leistung videobasierter Methoden verbessert. Wir repräsentieren Videos mit einer feineren Granularität mittels regionenbasierter Merkmale und kodieren videobasierte räumlich-zeitliche Dynamiken durch Beziehungen zwischen Regionen. Unser VRAG erfasst die Beziehungen zwischen Regionen basierend auf ihrem semantischen Inhalt mittels Self-Attention und permutationssicherer Aggregation durch Graph-Convolution. Darüber hinaus zeigen wir, dass die Leistungsunterschiede zwischen videobasierten und framebasierten Methoden reduziert werden können, indem Videos in Shots segmentiert und Shot-Embeddings für die Videoabfrage verwendet werden. Wir evaluieren unser VRAG an mehreren Aufgaben des Video-Retrieval und erreichen dabei eine neue state-of-the-art-Leistung für videobasierte Abfragen. Zudem zeigt unser shotbasiertes VRAG eine höhere Retrieval-Genauigkeit im Vergleich zu anderen bestehenden videobasierten Methoden und kommt der Leistung framebasierter Ansätze bei schnellerer Auswertung deutlich näher. Schließlich wird unser Code öffentlich verfügbar gemacht.