References for Graph Similarity

Similarity

[BK 98] Bunke H., Shearer K.: A Graph Distance Metric Based on the Maximal Common Subgraph. Pattern Recognition Letters, Elsevier Science, (19)3-4: 255-259 (1998) [Abstract]
[CFS+ 98] Cordella L.P., Foggia P., Sansone C., Tortorella F., Vento M.: Graph Matching: A Fast Algorithm and its Evaluation. Proc. 14th Int. Conf. on Pattern Recognition, 1582-1584 (1998)
  • cf. [CFSV 98]; Vergleich mit [Ull 76] - [Paper] - System VF (Uni Napoli)
    • [CKS 98] Chartrand G., Kubicki G., Schultz M.: Graph Similarity and Distance in Graphs. Aequationes Mathematicae 55(1-2): 129-145 (1998) [Abstract]
  • graphs must have same number of nodes; no labels
    • [Gab 76] Gabow H.N.: An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs. Journal of the ACM 23(2): 221-234 (1976) [Citations]
    [GS 96] Goddard W., Swart H.C.: Distance Between Graphs under Edge Operations. Discrete Mathematics, Elsevier Science, 161: 121-132 (1996) [Abstract]
  • Edge slides and edge rotations; only graphs with equal number of nodes
    • [GT 89] Gabow H.N., Tarjan R.E.: Faster Scaling Algorithms for Network Problems. SIAM Journal on Computing 18(5): 1013-1036 (1989)
    [Jum 94] Jumarie G.: Informational Similarity of Graphs in Syntactic Pattern Recognition. Pattern Recognition Letters 15(12): 1177-1181 (1994) [Abstract]
    [JWZ 94] Jiang T., Wang L., Zhang K.: Alignment of Trees - An Alternative to Tree Edit. Proc. CPM Combinatorial Pattern Matching, LNCS 807, 75-86 (1994)
    [PM 99] Papadopoulos A.N., Manolopoulos Y.: Structure-Based Similarity Search with Graph Histograms. Proc. DEXA/IWOSS Int. Workshop on Similarity Search, IEEE Comp. Soc., 174-178 (1999) [Abstract]
  • Distance based vs. feature based graph similarity
    • [PSZ 98] Pelillo M., Siddiqi K., Zucker S.W.: Matching Hierarchical Structures Using Association Graphs. Proc. ECCV 5th European Conf. on Computer Vision, LNCS 1407, 3-16 (1998)
    [SCKP 94] Dong Su Seong, Young Kyu Choi, Ho Sung Kim, Kyu Ho Park: An Algorithm for Optimal Isomorphism between Two Random Graphs. Pattern Recognition Letters, Elsevier Science, 15(4): 321-327 (1994) [Abstract]
  • Entropy based similarity; cf. [SKP 93]
    • [SD 76] Schmidt D.C., Druffel L.E.: A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices. Journal of the ACM 23(3): 433-445 (1976)
    [Sel 77] Selkow S.M.: The Tree-to-Tree Editing Problem. Information Processing Letters 6(6): 184-186 (1977)
    [SKP 93] Dong Su Seong, Ho Sung Kim, Kyu Ho Park: Incremental Clustering of Attributed Graphs. IEEE Trans. on Systems, Man, and Cybernetics (SMC) 23(5): 1399-1411 (1993)
  • Random Graphs; entropy based similarity; cf. [SCKP 94]
    • [Tai 79] Tai K.-C.: The Tree-to-Tree Correction Problem. Journal of the ACM 26(3): 422-433 (1979)
    [Ull 76] Ullmann J.R.: An Algorithm for Subgraph Isomorphism. Journal of the ACM 23(1): 31-42 (1976)
    [WH 95] Wilson R.C., Hancock E.R.: Relational Matching with Dynamic Graph Structures. Proc. ICCV 5th Int. Conf. on Computer Vision, 450-456 (1995)
    [Wil 99] Will T.G.: Switching Distance Between Graphs with the Same Degrees. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 12(3): 298-306 (1999) [Abstract]
    [WSS+ 98] Wang J.T.L., Shapiro B.A., Shasha D., Zhang K., Currey K.M.: An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees. IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) 20(8): 889-895 (1998) [Abstract] [Paper]
    [WWS+ 00] Wang J.T.L., Wang X., Shasha D., Shapiro B.A., Zhang K., Zheng X., Weinberg Z.: An Approximate Search Engine for Structural Databases. Proc. ACM SIGMOD, Demonstration, (2000)
    Several interesting applications (tree databases) including:
  • National Cancer Institute 3D structure database --> Daten nicht zugaenglich
  • TreeBase, Herbaria Harvard -> /nfs/bioinf/PHYLO_TREES
  • Phylogenetics databases and information (Berkeley)
  • Protein Data Bank (PDB)
  • Structure Group at NCBI
    • [WZJS 94] Wang J.T.L., Zhang K., Jeong K., Shasha D.: A System for Approximate Tree Matching. IEEE Transactions on Knowledge and Data Engineering (TKDE) 6(4): 559-571 (1994) [Paper] [Software]
    [Zha 93] Zhang K.: A New Editing based Distance between Unordered Labeled Trees. Proc. CPM Combinatorial Pattern Matching, LNCS 684, 254-265 (1993)
  • Conf. version of [Zha 96]
    • [Zha 96] Zhang K.: A Constrained Edit Distance Between Unordered Labeled Trees. Algorithmica 15: 205-222 (1996) [Abstract]
  • Extended version of [Zha 93]
    • [ZJ 94] Zhang K., Jiang T.: Some MAX SNP-hard Results Concerning Unordered Labeled Trees. Information Processing Letters 49(5): 249-254 (1994) [Abstract]
    [ZS 89] Zhang K., Shasha D.: Simple Fast Algorithms for the Editing Distance between Trees and Related Problems. SIAM Journal on Computing 18(6): 1245-1262 (1989)
    [ZSS 92] Zhang K., Statman R., Shasha D.: On the Editing Distance Between Unordered Labeled Trees. Information Processing Letters 42(3): 133-139 (1992)
  • Cited in [Zha 96]
    • [ZSW 94] Zhang K., Shasha D., Wang J.T.L.: Approximate Tree Matching in the Presence of Variable Length Don't Cares. Journal of Algorithms 16(1): 33-66 (1994) [Paper]
    [ZWS 95] Zhang K., Wang J.T.L., Shasha D.: On the Editing Distance between Undirected Acyclic Graphs and Related Problems. Proc. CPM Combinatorial Pattern Matching, LNCS 937, 395-407 (1995)
  • Conf. version of [ZWS 96]
    • [ZWS 96] Zhang K., Wang J.T.L., Shasha D.: On the Editing Distance between Undirected Acyclic Graphs. Int. Journal of Foundations of Computer Science 7(1): 43-57 (1996)
  • Extended version of [ZWS 95]

    • Open References

    [BA 83] Bunke H., Allermann G.: Inexact Graph Matching for Structural Pattern Recognition. Pattern Recognition Letters 1(4): 245-253 (1983)
    [Blu 93] Blum N.: New Approach to Maximum Matching in General Graphs. Research Report 8546, Univ. Bonn (1993)
    [Bun 97] Bunke H.: On a Relation Between Graph Edit Distance and Maximum Common Subgraph. Pattern Recognition Letters, Elsevier Science, (18)8: 689-694 (1997) [Abstract]
    [CFSV 96] Cordella L., Foggia P., Sansone C., Vento M.: An Efficient Algorithm for the Inexact Matching of ARG Using a Contextual Transformational Model. Proc. 13th ICPR, IEEE CS Press, Vol. III, 180-184 (1996)
  • Vergleich mit [Ull 76]
    • [CFSV 98] Cordella L., Foggia P., Sansone C., Vento M.: Performance Evaluation of the VF Graph Matching Algorithm. Proc. 10th Int. Conf. on Image Analysis and Processing, IEEE (1998) [Abstract]
  • cf. [CFS+ 98] - Vergleich mit [Ull 76]
    • [GT 91] Gabow H.N., Tarjan R.E.: Faster Scaling Algorithms for General Graph-Matching Problems. Journal of the ACM 38(4): 815-853 (1991) [Citations]
    [MWH 98] Myers R., Wilson R.C., Hancock E.R.: Bayesian Graph Edit Distance. Proc. 10th Int. Conf. on Image Analysis and Processing, IEEE (1998) [Abstract]
    [Peu 98] Peura M.: Attribute Trees in Image Analysis ž Heuristic Matching and Learning Techniques. Proc. 10th Int. Conf. on Image Analysis and Processing, IEEE (1998) [Abstract]
    [PF 97] Petrakis E.G.M., Faloutsos C.: Similarity Searching in Medical Image Databases. IEEE Trans. on Knowledge and Data Engineering (TKDE) 9(3): 435-447 (1997) [Abstract]
    [PSZ 98] Pelillo M., Siddiqi K., Zucker S.W.: Attributed Tree Matching and Maximum Weight Cliques. Proc. 10th Int. Conf. on Image Analysis and Processing, IEEE (1998) [Abstract]
    [SCC+ 96] Seed G.M., Clark D.E.R., Corney J.R., Tuttle R., Little G.: Object-oriented graph-based geometric feature recognition, The Computer Journal, Volume 39, Issue 9, pp. 808-811 (1996) [Abstract]
    [Tom 99] Tomescu I.: Some Extremal Properties of the Degree Distance of a Graph. Discrete Applied Mathematics 98(1): 159-163 (1999) [Abstract]
    [TT 88] Tanaka E., Tanaka K.: The Tree-To-Tree Editing Problem. Int. Journal of Pattern Recognition and Artificial Intelligence 2(2): 221-240 (1988)
    [WW 98] Wang X., Wang J.T.L.: Fast Similarity Search in Databases of 3D Objects. Proc. 10th IEEE Int. Conf. on Tools with Artificial Intelligence, Taipei, Taiwan, 16-23 (1998) [Abstract]
    [Zha 93] Zhang K.: Fast Algorithms for the Constrained Editing Distance Between Ordered Labeled Trees and Related Problems. Technical Report No. 361, Dept. of Computer Science, University of Western Ontario, Canada (1993)

    Biological Pathways

    [DSB ??] Dandekar T., Schuster S., Bork P.: Metabolic Pathway Analysis. Overview
    [FS 99] Forst C.V., Schulten K.: Evolution of Metabolisms: A New Method for the Comparison of Metabolic Pathways. Proc. RECOMB 3rd Int. Conf. on Computational Molecular Biology, ACM Press, 174-181 (1999)
    [FS 99] Forst C.V., Schulten K.: Evolution of Metabolisms: A New Method for the Comparison of Metabolic Pathways Using Genomic Information. J. Comput. Biol. 6(3/4): 343-360 (1999)
    [GBO+ 97] Goto S., Bono H., Ogata H., Fujibuch W., Hishioka T., Sato K., Kanehisa M.: Organizing and Computing Metabolic Pathway Data in Terms of Binary Relations. Proc. PSB Pacific Symposium on Biocomputing 2: 175-186 (1997) [Paper]
    [GNK 98] Goto S., Nishioka T., Kanehisa M.: LIGAND: Chemical Database for Enzyme Reactions. Bioinformatics 14: 591-599 (1998) [User Manual http://www.genome.ad.jp/dbget/ligand.html]
    [IK 97] Igarashi T., Kaminuma T.: Development of a Cell Signaling Networks Database. Proc. PSB Pacific Symposium on Biocomputing 2: 187-197 (1997) [Paper]
    [KM 94] Karp P., Mavrovouniotis M.: Representing, Analyzing, and Synthesizing Biochemical Pathways. IEEE Expert 9(2): 11-21 (1994) [Abstract] [Paper]
    [KP 94] Karp P.D., Paley S.M.: Representations of Metabolic Knowledge: Pathways. Proc. ISMB 2nd Int. Conf on Intelligent Systems for Molecular Biology, AAAI Press (1994) [Abstract] [Paper]
    [KP 94] Karp P.D., Paley S.M.: Automated Drawing of Metabolic Pathways. Proc. 3rd Int. Conf. on Bioinformatics and Genome Research (1994) [Abstract] [Paper]
    [KR 93] Karp P., Riley M.: Representations of Metabolic Knowledge, Proc. ISMB 1st Int. Conf. on Intelligent Systems for Molecular Biology, AAAI Press, 207-215 (1993) [Abstract] [Paper]
    [KR 97] Karp P.D., Riley M.: Computation in Biological Pathways. Proc. PSB Pacific Symposium on Biocomputing 2: 18 (1997) [Paper]
    [Mit 97] Mittenthal J.E.: An Algorithm to Assemble Pathways from Processes. Proc. PSB Pacific Symposium on Biocomputing 2:292-303 (1997) [Paper]
    [SSPH 99] Schilling C.H., Schuster S., Palsson B.O., Heinrich R.: Metabolic Pathway Analysis: Basic Concepts and Scientific Applications in the Post-Genomic Era. Biotechnol. Prog. 15: 296-303 (1999) [Abstract] [Paper]

    Other Applications

    [HKKM 97] Han E.-H., Karypis G., Kumar V., Mobasher B.: Clustering In A High-Dimensional Space Using Hypergraph Models. Tech. Rep. #97-019, CS Dept., U Minnesota (1997) [Paper]
    [HKKM 98] Han E.-H., Karypis G., Kumar V., Mobasher B.: Hypergraph Based Clustering in High-Dimensional Data Sets: A Summary of Results. IEEE Data Engineering Bulletin 21(1): 15-21 (1998) [Abstract] [Paper]
    [KHK 99] Karypis G., Han E.-H., Kumar V.: Chameleon: Hierarchical Clustering Using Dynamic Modeling. IEEE Computer 32(8): 68-75 (1999) [Abstract] [Paper] [Software METIS]
    [KHK 99] Karypis G., Han E.-H., Kumar V.: Multilevel Refinement for Hierarchical Clustering. Tech. Rep. #99-020, CS Dept., U Minnesota (1999) [Paper]
    [Pav 72] Pavlidis T.: Representation of Figures by Labeled Graphs. Pattern Recognition 4(1): 5-17 (1972)
    [SS 97] Shen X., Spann M.: Segmentation of 2D and 3D Images through a Hierarchical Clustering Based on Region Modelling. Proc. IEEE Int. Conf. on Image Processing (ICIP), Vol.III (1997) [Abstract]
  • short/preliminary version of [SSN 98]
    • [SSN 98] Shen X., Spann M., Nacken P.F.M.: Segmentation of 2D and 3D Images through Hierarchical Clustering based on Region Modelling. Pattern Recognition 31(9): 1295-1320 (1998) [Abstract]
    [WFKM 97] Wiskott L., Fellous J.-M., Krüger N., von der Malsburg C.: Face Recognition by Elastic Bunch Graph Matching. IEEE Trans. on Pattern Analysis and Machine Intelligence (PAMI) 19(7) (1997) [Abstract]
    [WSS 99] Wang J.T.L., Shapiro B.A., Shasha D. (eds.): Pattern Discovery in Biomolecular Data. Oxford University Press (1999) [Content]

  • Ruhr-Uni Bochum: Elastic Graph Matching Computer Vision Graph Matching for Scene Analysis
  • U Birmingham: Segmentation
  • Harvard U: Herbaria Tree Database

    • Miscellaneous

    [AYZ 94] Alon N., Yuster R., Zwick U.: Color-Coding: a New Method for Finding Simple Paths, Cycles and Other Small Subgraphs Within Large Graphs (Extended Abstract). Proc. STOC'94, 326-335 (1994) [Paper]
    [AYZ 95] Alon N., Yuster R., Zwick U.: Color-Coding. Journal of the ACM 42:844-856 (1995) [Paper]
    [BE 82] Reuven Bar-Yehuda, S. Even: On Approximating a Vertex Cover for Planar Graphs. Proc. STOC, 303-309 (1982)
    [BFF 85] Béla Bollobás, Trevor I. Fenner, Alan M. Frieze: An Algorithm for Finding Hamilton Cycles in a Random Graph. Proc. STOC, 430-439 (1985)
    [BGM 82] László Babai, D. Yu. Grigoryev, David M. Mount: Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. Proc. STOC, 310-324 (1982)
    [CGG+ 95] Chiang Y.-J., Goodrich M.T., Grove E.F., Tamassia R., Vengroff D.E., Vitter J.S.: External-memory graph algorithms. In Proc. ACM-SIAM Symp. on Discrete Algorithms, 139-149 (1995) [Abstract]
    [FM 80] Filotti I.S., Mayer J.N.: A Polynomial-time Algorithm for Determining the Isomorphism of Graphs of Fixed Genus (Working Paper). Proc. STOC, 236-243 (1980)
    [FMR 79] Filotti I.S., Miller G.L., Reif J.H.: On Determining the Genus of a Graph in O(v^O(g)) Steps. Conf. Record of the Eleventh Annual ACM Symposium on Theory of Computing (STOC), 27-37 (1979)
    [GPG 90] Gyssens M., Paredaens J., Gucht D.V.: A graph oriented object database model. Proc. ACM PODS (1990) [Abstract]
    [HI 92] Heath L.S., Istrail S.: The Pagenumber of Genus g Graphs is O(g). Journal of the ACM 39(3): 479-501 (1992) [Abstract]
    [Hof 80] Christoph M. Hoffmann: Testing Isomorphism on Cone Graphs (Extended Abstract). Proc. STOC, 244-251 (1980)
    [HW 74] Hopcroft J.E., Wong J.K.: Linear Time Algorithm for Isomorphism of Planar Graphs (Preliminary Report). Proc. STOC, 172-184 (1974)
    [KRS 93] Kenyon C., Randall D., Sinclair A.: Matchings in Lattice Graphs. (Preliminary Version) STOC'93, 738-746 (1993)
    [Lic 80] David Lichtenstein: Isomorphism for Graphs Embeddable on the Projective Plane. Proc. STOC, 218-224 (1980)
    [LS 95] Liu D.-R., Shekhar S.: A Similarity Graph-Based Approach to Declustering Problems and Its Application towards Paralleling Grid Files. Proc. ICDE, 373-381 (1995)
    [LS 96] Liu D.-R., Shekhar S.: Partitioning Similarity Graphs: A Framework for Declustering Problems. Information Systems 21(6): 475-496 (1996) [Paper]
    [Mil 77] Gary L. Miller: Graph Isomorphism, General Remarks. Proc. STOC, 143-150 (1977)
    [Mil 80] Gary L. Miller: Isomorphism Testing for Graphs of Bounded Genus. Proc. STOC, 225-235 (1980)
    [Pfa 72] Pfaltz J.L.: Graph Structures. Journal of the ACM 19(3): 411-422 (1972)
    [SL 95] Shekhar S., Liu D.-R.: CCAM: A Connectivity-Clustered Access Method for Aggregate Queries on Transportation Networks: A Summary of Results. Proc. ICDE'95, 410-419 (1995)
    [SL 97] Shekhar S., Liu D.-R.: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. TKDE 9(1): 102-119 (1997)
    [SS 87] Saharon Shelah, Joel Spencer: Threshold Spectra for Random Graphs. Proc. STOC, 421-424 (1987)
    [SW 99] Stell J.G., Worboys M.F.: Generalizing Graphs Using Amalgamation and Selection. Proc. SSD'99, LNCS 1651, 19-32 (1999)

    Graph Drawing / Visualization

    daVinci (Uni Bremen): Knotendefinitionen unuebersichtlich in Kantendefinitionen integriert.
    Graphlet (Uni Passau): GML Manual
    Graphviz (AT&T Research), Grappa and Webdot
    VGJ (Auburn U): Java, GML
    DIVA (UC Berkeley)

    Bibliographies

    Lists
  • 13.3 Graph Matching and Relaxation
  • 13.3.2 Graph Matching (e.g. Pictorial Data)
  • I.S.Filotti
  • DBLP?title=graph
    • Journals
  • SIAM Journal on Discrete Mathematics (SIDMA)
  • SIAM Journal on Computing (SICOMP)
  • Journal of the ACM (JACM)
  • Discrete Mathematics (Elsevier Science)
  • Information Processing Letters (Elsevier Science)
  • Pattern Recognition Letters (Elsevier Science) search?graph