High Efficiency and Quality: Large Graphs Matching

Publisher:
ACM
Publication Type:
Conference Proceeding
Citation:
Proceedings of 2011 ACM International Conference on Information and Knowledge Management, 2011, pp. 1755 - 1764
Issue Date:
2011-01
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2013002388OK.pdf Published version560.13 kB
Adobe PDF
Graph matching plays an essential role in many real applications. In this paper, we study how to match two large graphs by maximizing the number of matched edges, which is known as maximum common subgraph matching and is NP-hard. To find exact matching, it cannot handle a graph with more than 30 nodes. To find an approximate matching, the quality can be very poor. We propose a novel two-step approach which can efficiently match two large graphs over thousands of nodes with high matching quality. In the first step, we propose an anchor-selection/expansion approach to compute a good initial matching. In the second step, we propose a new approach to refine the initial matching. We give the optimality of our refinement and discuss how to randomly refine the matching with different combinations. We conducted extensive testing using real and synthetic datasets, and will report our findings.
Please use this identifier to cite or link to this item: