I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). Graphs are calculated for each frame. The structure of the graph changes when the objects are moved or modified in the video.

I have two graphs whose number of vertices and the edges between them keep changing with time. I want a similarity metric between two such graphs.

The method used currently is to encode the changes in graph structure in a string. So, we get two strings representing the change in graph structure with time. Now substring matching is done between the two strings and this is used to determine the similarity of the two videos.

I am not sure this is the right way to compare the similarity of two graphs. Something more mathematically concrete should exist. What are some techniques which might be helpful to me? I am not entirely sure whether this is the right place to post this but any pointers to what I should read to model this would be helpful.