Draft:Graph difference
| Submission declined on 21 September 2024 by Johannes Maximilian (talk). This submission is not adequately supported by reliable sources. Reliable sources are required so that information can be verified. If you need help with referencing, please see Referencing for beginners and Citing sources.
Where to get help
How to improve a draft
You can also browse Wikipedia:Featured articles and Wikipedia:Good articles to find examples of Wikipedia's best writing on topics similar to your proposed article. Improving your odds of a speedy review To improve your odds of a faster review, tag your draft with relevant WikiProject tags using the button below. This will let reviewers know a new draft has been submitted in their area of interest. For instance, if you wrote about a female astronomer, you would want to add the Biography, Astronomy, and Women scientists tags. Editor resources
|  |
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]- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ Hamilton, William L.; Ying, Rex; Leskovec, Jure (2018-04-10), Representation Learning on Graphs: Methods and Applications, arXiv:1709.05584
- ^ 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