13
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think the term you want to Google on is "graph edit distance". A relatively recent survey (2010) from GAO et al bit.ly/15pOkWp But, what you are doing seems kosher. They actually suggest just what you're doing on page 118 in the paragraph beginning "A graph may be an attributed relational..." $\endgroup$ Aug 30, 2013 at 14:10
  • $\begingroup$ Maybe I'm under-thinking this but isn't this the same a comparing two sound waves? Because if that is the case an algorithm that may be useful for such purposes is a fft/dft? Ex: perlmonks.org/?node_id=169641 $\endgroup$ Jun 3, 2017 at 3:25

4 Answers 4

10
$\begingroup$

Iterative method to involve neighbors' information is a subfamily of this problem. This spirit is suitable for both directed and indirected graphs, like SimRank, similarity flooding etc. I have implemented a set of algorithms (for both direct and indirected graphs) of this branch in Python. Future similarities would be appended without iteration manner. Enjoy!

Update 12/25/15: I added a C implementation of my proposed TACSim algorithm, which calculates the similarity of weighted directed graphs considering both node and edge neighbors. You can refer to my new research paper if you use it in your research.

  • Chen, Xiaming; Wang Haiyang, Qiang, Siwei; Wang, Yongkun; Jin, Yaohui; Discovering mesostructures of human mobility from city-scale data, Trans. on Big Data, 2016 (Submission).
$\endgroup$
6
$\begingroup$

If you have two graphs, there is no point to measure their similarity using strings. Actually there are lot of researches going on measuring graph similarity.

I also doing research on it and I implemented a algorithm that use neighbor matching to measure the similarity of two directed graphs. I refer existing research paper and implemented in Java.

You can find more details about that in MEASURING GRAPH SIMILARITY USING NEIGHBOR MATCHING. Actually that algorithm should also optimize to improve the accuracy. You can try this algorithm if you are interested and you will have to change it according to you requirement.

$\endgroup$
5
$\begingroup$

There is an increasingly-large body of work on graph kernels for determining similarity.

Here is a nice survey.

$\endgroup$
3
$\begingroup$

There are two important survey papers that covers this topic that I highly recommend:

Conte, Donatello, et al. "Thirty years of graph matching in pattern recognition." International journal of pattern recognition and artificial intelligence 18.03 (2004): 265-298.

Foggia, Pasquale, Gennaro Percannella, and Mario Vento. "Graph matching and learning in pattern recognition in the last 10 years." International Journal of Pattern Recognition and Artificial Intelligence 28.01 (2014): 1450001.

Graph matching is also called "network alignment" in some papers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.