臺灣博碩士論文加值系統

具屬性關係之非精確子圖比對為一個困難，且具有結構一致限制的組合最佳化問題，本文提出一個快速篩選法來求解非精確子圖同構問題；以逐漸縮減不可行解搜尋空間，使尋找近似最佳解時，可以限制在一個相較為小的可行解空間。本方法主要分為三階段：建構，修剪和評估；建構階段主要目的是利用屬性值的容差，快速識別兩圖間每個頂點與邊相互對應的初始候選者；修剪階段，則考量整體拓撲結構，以反覆的方式刪除大部分會導致不可行組合的候選頂點與邊。因此在評估階段，可以目標函數評估所有剩餘候選者的對應以求得近似最佳解。
本篩選法亦可有效運用於一個零容差的精確子圖同構問題；當依據一個現存的圖性能指標資料庫，其模擬結果顯示，在數次的修剪與目標函數評估後，可獲得近似最佳解。

Matching inexact sub-graph of attributed relational graphs is a combinatorial optimization problem of difficulty with the constraint of structure consistence. This thesis proposes an efficient screening algorithm to solve the inexact sub-graph isomorphism problems by incrementally reducing the infeasible search space. Hence, searching for near optimal solutions can be confined in a relatively small feasible space. The screening algorithm mainly consists of three stages: Construction, Pruning and Evaluation. The aim of the Construction stage is, by using given tolerances of attribute values, to efficiently choice initial candidates for individual vertices and edges from each label mapping between two graphs. The Pruning stage iteratively eliminates most of these vertices and edge candidates that lead to infeasible combinations by considering the whole topological structure. Consequently, the Evaluation stage, the desired near optimal solutions can be obtained from evaluating all mappings consisted with the remaining candidates based on the objective function measure.
This screening algorithm can also work efficiently using a zero tolerance for exact sub-graph isomorphism. Simulation result indicates that near optimal solutions can be obtained by using few pruning iterations and a small number of objective function evaluations.

中文摘要 i
Abstract ii
Table of Contents iii
List of Figures v
List of Tables vi
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Thesis Organization 2
Chapter 2 Related Work 4
2.1 Graph Matching 4
2.2 Problem Statement 5
Chapter 3 An Screening Algorithm 9
3.1 Concepts of the Proposed Method 9
3.2 Proposed Screening Algorithm 10
3.2.1 Overview of the Screening Algorithm 11
3.2.2 Construction Stage 13
3.2.3 Pruning Stage 16
Chapter 4 Empirical Analysis 21
4.1 Algorithm Efficiency 21
4.2 Parameter Sensitivity 23
Chapter 5 Experiment Results 26
5.1 Directed Graph 26
5.2 VF Algorithm 27
5.3 ESA Algorithm 27
5.4 Comparison 28
Chapter 6 Conclusion 32
References 33
Acknowledgements 38

[1] Gabriel Valiente, Algorithms on trees and graphs, New York : Springer, 2002.
[2] Bruno T. Messmer and Horst Bunke, “A New Algorithm for Error-Tolerant Subgraph Isomorphism Detection,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 20, no. 5, pp. 493-504, May 1998.
[3] Josep Llado s, Enric MartõÂ, and Juan Jose Villanueva,, “Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol.23, no. 10, pp.1137-1143, October 2001.
[4] K. G. Khoo and P. N. Suganthan, “Structural Pattern Recognition Using Genetic Algorithms With Specialized Operators,” IEEE Trans. on Systems, Man, and Cybernetics—Part B, vol. 33, no. 1, pp. 156-165, Feb. 2003.
[5] S.J. Dickinson, A.P. Pentland and A. Rosenfeld, “3-D shape recovery using distributed aspect matching,” IEEE Trans. Pattern Anal. Mach. Intell. vol. 14 pp. 174-198, 1992.
[6] R. Horaud and T. Skordas,” Stereo correspondence through feature grouping and maximal cliques,” IEEE Trans. Pattern Anal. Mach. Intell. vol. 11, pp. 1168-1180, 1989.
[7] A.C.M. Dumay, R.J. van der Geest, J.J. Gerbrands,E. Jansen and J.H.C. Reiber, “Consistent inexact graph matching applied to labeling coronary segments in arteriograms,” Proceedings of the 11th International Conference on Pattern Recognition, vol. C, pp. 439-442, 1992.
[8] Michael A. van Wyk, Tariq S. Durrani, and Barend J. van Wyk , “A RKHS Interpolator-Based Graph Matching Algorithm,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 24, no. 7, pp 988-995, July 2002.
[9] Andrew D.J. Cross, R.C. Wilson and E.R. Hancock, “Inexact graph matching using genetic search,” Pattern Recognition, vol. 30, pp. 953-970, 1997.
[10] Andrew D.J. Cross, Richard Myers, Edwin R. Hancock “Convergence of a hill-climbing genetic algorithm for graph matching,” Pattern Recognition, vol. 33, pp. 1863-1880, 2000.
[11] Richard Myers and Edwin R. Hancock “Least-commitment graph matching with genetic algorithms,” Pattern Recognition, vol. 34, pp. 375-394, 2001.
[12] Yuan-Kai Wang, Kuo-Chin Fan and Jorng-Tzong Horng, “Genetic-Based Search for Error-Correcting Graph Isomorphism,” IEEE Trans. Systems, Man, and Cybernetics─Part B, vol. 27, no. 4, pp. 588-597, August 1997.
[13] Joshua Knowles and David Corne, “A New Evolutionary Approach to the Degree-Constrained Minimum Spanning Tree Problem,” IEEE Transaction on Evolutionary Computation, vol. 4, no.2, pp. 125-134, July 2000.
[14] J.R. Ullman, ”An Algorithm for Subgraph Isomorphism,” J. Assoc. for Computing Machinery, vol. 23, no. 1, pp. 31-42, 1976.
[15] F. Depiero, M. Trived, and S. Serbin, “Graph Matching Using a Direct Classification of Vertex Attendance,” Pattern Recognition, vol. 29, no. 6, pp. 1031-1048, 1996.
[16] L. G. Shapiro and R. M. Haralick, “Structural description and inexact matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. PAMI-3, no. 5, pp. 504–519, 1981.
[17] L.P. Cordella, P. Foggia, C. Sansone and M. Vento, “Performance Evaluation of the VF Graph Matching Algorithm,” Proc. 10th Int’l Conf. Image Analysis and Processing, pp. 1172-1177, Sept. 1999.
[18] L.P. Cordella, P. Foggia, C. Sansone and M. Vento, “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs,” IEEE Transactions on Pattern Analysis and Intelligence, vol. 26, no.10, pp. 1367-1372, October 2004.
[19] W. H. Tsai and K. S. Fu, “Error-correcting isomorphisms of attributed relational graphs for pattern analysis,” IEEE Trans. Systems, Man, and Cybernetics, vol. SMC-9, pp. 757–768, 1979.
[20] R.C. Wilson and E.R. Hancock, “Structural matching by discrete relaxation,” IEEE Trans. Pattern Anal. Mach. Intell. vol.19, pp. 634-648, 1997.
[21] W.J. Christmas, J. Kittler, and M. Petrou, “Structural Matching in Computer Vision Using Probabilistic Relaxation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 17, no. 8, pp. 749-764, Aug. 1995.
[22] R.C. Wilson and E.R. Hancock, “A Bayesian Compatibility Model for Graph Matching,” Pattern Recognition Letters, vol. 17, pp. 263-276, 1996.
[23] P.D. Simic, “Constrained Nets for Graph Matching and Other Quadratic Assignment Problems,” Neural Computation, vol. 3, pp. 268-281, 1991.
[24] D.E. van den Bout and T.K. Miller, III, “Graph Partitioning Using Annealed Neural Networks,” IEEE Trans. Neural Networks, vol. 1, no. 2, pp. 192-203, 1990.
[25] P. Kuner and B. Ueberreiter, “Pattern Recognition by Graph Matching: Combinatorial versus Continuous Optimization,” Int''l J. Pattern Recognition and Artificial Intelligence, vol. 2, no. 3, pp. 527-542, Sept. 1988.
[26] P.N. Suganthan, E.K. Teoh, and D.P. Mital, ”Pattern Recognition by Graph Matching Using the Potts MFT Neural Networks,” Pattern Recognition, vol. 28, no. 7, pp. 997-1009, 1995.
[27] P.N. Suganthan, E.K. Teoh, and D.P. Mital, “Pattern Recognition by Homomorphic Graph Matching Using Hopfield Neural Networks,” Image and Vision Computing, vol. 13, no. 1, pp. 45-60, Feb. 1995.
[28] S. Kirkpatrick, C. D. Gellat, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, pp. 671–680, 1983.
[29] P.P.C. Yip and Y.H. Pao, “Combinatorial optimization with use of guided evolutionary simulated annealing,” IEEE Trans. Neural Networks, vol. 6, pp. 290-295, 1995.
[30] D.S. Seong, Y.K. Choi, H.S. Kim, and K.H. Park, “An Algorithm for Optimal Isomorphism between Two Random Graphs,” Pattern Recognition Letters, vol. 15, pp. 321-327, Apr. 1994.
[31] A.K.C. Wong and M. You, “Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 7, no. 5, pp. 599-609, Sept. 1985.
[32] H. A. Almohamad and S. O. Duffuaa, “A Linear Programming Approach for the Weighted Graph Matching Problem,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol.15, no. 5, pp.522-525, May 1993.
[33] S Umeyama, “An Eigendecomposition Approach to Weighted Graph Matching Problems,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 10, no. 5, pp. 695-703, Sept. 1988.
[34] S. Gold and A. Rangarajan, “A Graduated Assignment Algorithm for Graph Matching,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 18, no. 4, pp. 377-388, April 1996.
[35] S.-Y. Ho, H.-M. Chen, S.-J. Ho and T.-K. Chen, “Design of Accurate Classifiers with a Compact Fuzzy-Rule Base Using an Evolutionary Scatter Partition of Feature Space,” IEEE Trans. Systems, Man, and Cybernetics─Part B. Aug. 2004.
[36] K. Mehlhorn, Graph Algorithms and NP-Completeness. Berlin, Heidelberg: Springer-Verlag, 1984.
[37] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman and Company, 1979.
[38] P. Foggia, C. Sansone and M. Vento, “A Database of Graphs for Isomorphism and Sub-Graph Isomorphism Benchmarking,” Proceedings of the 3rd IAPR-TC15 Workshop on Graph based Representation, Italy, 2001.
[39] L.P. Cordella, P. Foggia, C. Sansone, M. Vento, “Fast Graph Matching for Detecting CAD Image Components, ” 15th International Conference on Pattern Recognition, vol. 2, pp.6034, 2000.