Jump to content

Draft:Graph difference

From Wikipedia, the free encyclopedia

Graph difference or Structural difference is defined as a measure of the number of modifications required to transform an input graph into another.[1] Graph difference is not unique and depends upon the distance measure used. Distance Measures proposed for computing graph difference include Gernet distance[2], Graph edit distance[3], and Wasserstein distance[4].

Problem of computing graph difference is equivalent to computing the Maximum Common Subgraph and is NP-Complete.[5]

Applications

[edit]

Graph differencing algorithms are used in applications that use graph models such as pattern recognition, machine learning, software configuration management, version control, model-based development, bioinformatics, and cheminformatics.[6]

In model-based development, attributed graph differencing between two versions of a model (e.g., Simulink models, UML diagrams, state charts, etc.) represented as attributed graphs, aid in the indentification of changes such as additions, deletions, and modifications from one version of the model to another.[7]

In pattern recognition and machine learning, Graph representation learning computes graph difference to extract features encoding structural information of the underlying graph and discover new patterns.[8]

In biological systems, such as protein interaction networks, graph difference is computed to discover molecular properties such as therapeutic properties.[9]

References

[edit]
  1. ^ Shapiro, Linda G.; Haralick, Robert M. (1981). "Structural Descriptions and Inexact Matching". IEEE Transactions on Pattern Analysis and Machine Intelligence. PAMI-3 (5): 504–519. doi:10.1109/TPAMI.1981.4767144. ISSN 0162-8828. PMID 21868971.
  2. ^ Gernet, Dieter (1979). "Measuring the similarity of complex structures by means of graph grammars". Bulletin of the European Association of Theoretical Computer Science (EATCS) (7): 3–9.
  3. ^ Sanfeliu, Alberto; Fu, King-Sun (1983). "A distance measure between attributed relational graphs for pattern recognition". IEEE Transactions on Systems, Man, and Cybernetics. SMC-13 (3): 353–362. doi:10.1109/TSMC.1983.6313167. ISSN 0018-9472.
  4. ^ Han, Yuehui; Hui, Le; Jiang, Haobo; Qian, Jianjun; Xie, Jin (2022). "Generative Subgraph Contrast for Self-Supervised Graph Representation Learning". In Avidan, Shai; Brostow, Gabriel; Cissé, Moustapha; Farinella, Giovanni Maria; Hassner, Tal (eds.). Computer Vision – ECCV 2022. Lecture Notes in Computer Science. Vol. 13690. Cham: Springer Nature Switzerland. pp. 91–107. doi:10.1007/978-3-031-20056-4_6. ISBN 978-3-031-20056-4.
  5. ^ Bunke, H. (1997-08-01). "On a relation between graph edit distance and maximum common subgraph". Pattern Recognition Letters. 18 (8): 689–694. Bibcode:1997PaReL..18..689B. doi:10.1016/S0167-8655(97)00060-3. ISSN 0167-8655.
  6. ^ Bhowmick, Sanjukta; Bell, Patrick; Taufer, Michela (2023). "A Survey of Graph Comparison Methods with Applications to Nondeterminism in High-Performance Computing". The International Journal of High Performance Computing Applications. 37 (3–4): 306–327. doi:10.1177/10943420231166610. ISSN 1094-3420.
  7. ^ Nguyen, Tien N. (2022-11-09). "SimuV: Model-based configuration management for Simulink models". Proceedings of the 25th International Conference on Model Driven Engineering Languages and Systems: Companion Proceedings. MODELS '22. New York, NY, USA: Association for Computing Machinery. pp. 85–86. doi:10.1145/3550356.3559578. ISBN 978-1-4503-9467-3.
  8. ^ Hamilton, William L.; Ying, Rex; Leskovec, Jure (2018-04-10), Representation Learning on Graphs: Methods and Applications, arXiv:1709.05584
  9. ^ Duvenaud, David; Maclaurin, Dougal; Aguilera-Iparraguirre, Jorge; Gómez-Bombarelli, Rafael; Hirzel, Timothy; Aspuru-Guzik, Alán; Adams, Ryan P. (2015-11-03), Convolutional Networks on Graphs for Learning Molecular Fingerprints, arXiv:1509.09292