Logo PTI Logo FedCSIS

Proceedings of the 18th Conference on Computer Science and Intelligence Systems

Annals of Computer Science and Information Systems, Volume 35

A Graph Matching Algorithm to extend Wise Systems with Semantic

, , ,

DOI: http://dx.doi.org/10.15439/2023F4672

Citation: Proceedings of the 18th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 35, pages 411–420 ()

Full text

Abstract. Software technology has exponentially evolved leading to the development of intelligent applications using artificial intelligence models and techniques. Such development impacts all scientific and social fields: home automation, medicine, communication, etc. To make those new applications useful to a larger number of people, researchers are working on how to integrate artificial intelligence into real world while respecting the notion of calm technology. This paper fits in the context of the development of intelligent systems termed ``wise systems'' that aim at satisfying the calm technology requirement. Those systems are based on the concept of ``Wise Object'': a software entity -- object, service, component, application, etc. -- able to learn by itself how it is expected to behave and how it is used by a human or another software entity. During its learning process, a Wise Object constructs a graph that represents its behavior and the way it is used. A major weakness of Wise Objects is that the numerical information that they generate is mostly meaningless to humans. Therefore the objective of the work presented in this paper is to extend Wise Objects with semantics that enable them communicate with humans whose attention will consequently be less involved. In this paper, we address the issue of how to relate two different views using two state-based formalisms: State Transition Graph for views generated by the Wise Objects and Input Output Symbolic Transition System for conceptual views. Our proposal extends previous work done to extend the generated information with the conceptual knowledge using a matching algorithm founded on graph morphism. The first version of the algorithm has several limitations and constraints on the graphs that make it difficult to use in realistic cases. In this paper, we propose to generalize the algorithm and raise those restrictions. To illustrate the complete process, the construction of a sample graph matching on a home-automation system is considered.

References

  1. M. Weiser and J. S. Brown, “Designing calm technology,” POWERGRID JOURNAL, vol. 1, 1996.
  2. A. Tugui, “Calm technologies in a multimedia world,” Ubiquity, vol. 2004, 03 2004. http://dx.doi.org/10.1145/985616.985617
  3. I. Alloui, D. Esale, and F. Vernier, “Wise objects for calm technology,” in Proceedings of the 10th International Conference on Software Engineering and Applications - ICSOFT-EA, (ICSOFT 2015), INSTICC. SciTePress, 2015. http://dx.doi.org/10.5220/0005560104680471 pp. 468–471 – Section 2.
  4. S. Lejamble, I. Alloui, S. Monnet, and F. Vernier, “A new software architecture for the wise object framework: Multidimensional separation of concerns,” in Proceedings of the 17th International Conference on Software Technologies - ICSOFT,, INSTICC. SciTePress, 2022. http://dx.doi.org/10.5220/0011355000003266 pp. 567–574.
  5. R. A. Flores-Mendez, “Towards a standardization of multi-agent system framework,” XRDS, vol. 5, no. 4, p. 18–24, jun 1999. http://dx.doi.org/10.1145/331648.331659
  6. A. Dorri, S. S. Kanhere, and R. Jurdak, “Multi-agent systems: A survey,” IEEE Access, vol. 6, pp. 1–1, 2018. http://dx.doi.org/10.1109/ACCESS.2018.2831228
  7. D. Bonino and F. Corno, “Dogont - ontology modeling for intelligent domotic environments,” in The Semantic Web - ISWC 2008, A. Sheth, S. Staab, M. Dean, M. Paolucci, D. Maynard, T. Finin, and K. Thirunarayan, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-88564-1_51 pp. 790–803.
  8. H. K. Ngankam, H. Pigot, M. Frappier, O. Souza, H. Camila, and S. Giroux, “Formal specification for ambient assisted living scenarios,” UCAmI, pp. 508–519, 11 2017. http://dx.doi.org/10.1007/978-3-319-67585-5_51
  9. J.-B. Woo and Y.-K. Lim, “User experience in do-it-yourself-style smart homes,” in Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, ser. UbiComp ’15. New York, NY, USA: Association for Computing Machinery, 2015. http://dx.doi.org/10.1145/2750858.2806063 p. 779–790.
  10. R. Radziszewski, H. Ngankam, H. Pigot, V. Grégoire, D. Lorrain, and S. Giroux, “An ambient assisted living nighttime wandering system for elderly,” in Proceedings of the 18th International Conference on Information Integration and Web-Based Applications and Services, ser. iiWAS ’16. New York, NY, USA: Association for Computing Machinery, 2016. http://dx.doi.org/10.1145/3011141.3011171 p. 368–374.
  11. R. S. Michalski, “A theory and methodology of inductive learning,” Artificial Intelligence, vol. 20, no. 2, pp. 111–161, 1983. http://dx.doi.org/10.1016/0004-3702(83)90016-4
  12. M. Weiser, “The computer for the 21st century,” Scientific American, vol. 265, no. 3, pp. 66–75, January 1991. http://dx.doi.org/10.1145/329124.329126
  13. Y. Brun, G. D. M. Serugendo, C. Gacek, H. Giese, H. Kienle, M. Litoiu, H. Muller, M. Pezzè, and M. Shaw, Engineering Self-Adaptive Systems through Feedback Loops. Springer Berlin Heidelberg, 2009, pp. 48–70.
  14. J. Kephart and D. Chess, “The vision of autonomic computing,” Computer, vol. 36, pp. 41 – 50, 02 2003. http://dx.doi.org/10.1109/MC.2003.1160055
  15. H. Sachs, M. Stiebitz, and R. Wilson, “An historical note: Euler’s königsberg letters,” Journal of Graph Theory, vol. 12, pp. 133–139, 10 2006. http://dx.doi.org/10.1002/jgt.3190120114
  16. C. Constant, T. Jéron, H. Marchand, and V. Rusu, “Integrating Formal Verification and Conformance Testing for Reactive Systems,” IEEE Transactions on Software Engineering, vol. 33, no. 8, pp. 558–574, Aug. 2007. http://dx.doi.org/10.1109/TSE.2007.70707
  17. C. Camille, J. Thierry, M. Hervé, and R. Vlad, “Validation of Reactive Systems,” in Modeling and Verification of Real-TIME Systems - For-malisms and software Tools, S, Merz, N, and Navet, Eds. Hermès Science, Jan. 2008, pp. 51–76. ISBN 978-1848210134
  18. I. Boudhiba, C. Gaston, L. G. Pascale, and V. Prevosto, “Input Output Symbolic Transition Systems Enriched by Program Calls and Contracts: a detailed example of vending machine,” Laboratoire MAS - Centrale-Supelec, Research Report, 2015.
  19. J. Dörpinghaus, T. Hübenthal, and J. Faber, “A novel link prediction approach on clinical knowledge graphs utilizing graph structures,” in Proceedings of the 17th Conference on Computer Science and Intelligence Systems, ser. Annals of Computer Science and Information Systems, vol. 30. IEEE, 2022. http://dx.doi.org/10.15439/2022F36 p. 43–52.
  20. A. Dahhani, I. Alloui, S. Monnet, and F. Vernier, “Towards a semantic model for wise systems - a graph matching algorithm,” in ADVCOMP 2022, The Sixteenth International Conference on Advanced Engineering Computing and Applications in Sciences, S. Laura Garcia, Universitat Politecnica de Valencia, Ed., vol. 34, Nov. 2022. ISBN 2308-4499 pp. 27–34.
  21. M. R. Garey and D. S. Johnson, Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co., 1979. ISBN 0716710455
  22. V. A. Cicirello, “Survey of graph matching algorithms,” Geometric and Intelligent Computing Laboratory, Drexel University, Technical Report, March 1999.
  23. T. Davenport and L. Prusak, Working Knowledge: How Organizations Manage What They Know. Harvard Business School Press, 01 1998, vol. 1. ISBN 1578513014
  24. P. Moreaux, F. Sartor, and F. Vernier, “An effective approach for home services management,” in 2012 20th Euromicro International Conference on Parallel, Distributed and Network-based Processing, 2012. http://dx.doi.org/10.1109/PDP.2012.45 pp. 47–51.
  25. M. N. Nicolescu and M. J. Mataric, “Extending behavior-based systems capabilities using an abstract behavior representation,” in AAAI 2000, North Falmouth, MA, 2000, pp. 27–34.
  26. V. Rusu, H. Marchand, V. Tschaen, T. Jéron, and B. Jeannet, “From safety verification to safety testing,” in Testing of Communicating Systems, 03 2004. http://dx.doi.org/10.1007/978-3-540-24704-3_11. ISBN 978-3-540-21219-5 pp. 160–176.
  27. V. Rusu, H. Marchand, and T. Jéron, “Automatic verification and conformance testing for validating safety properties of reactive systems,” in Formal Methods 2005 (FM05), ser. Lecture Notes in Computer Science, vol. 3582. Newcastle, United Kingdom: Springer-Verlag, Jul. 2005. http://dx.doi.org/10.1007/11526841_14 pp. 189–204.
  28. C. Gaston, P. Le Gall, N. Rapin, and A. Touil, “Symbolic execution techniques for test purpose definition,” in Testing of Communicating Systems. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11754008_1 pp. 1–18.
  29. M. Mashaal, Bourbaki, ser. Bourbaki : A secret society of mathematicians. American Mathematical Society, Jun. 2006. ISBN 9780821839676
  30. A. Salomaa, I. N. Sneddon, H. M. Stark, and J.-P. Kahane, Theory of Automata : International Series of Monographs in Pure and Applied Mathematics, ser. International series in pure and applied mathematics. - page.1-2. London : Elsevier Science, 2015., 1969-2015. ISBN 978-1483121970
  31. G. Hahn and C. Tardif, Graph homomorphisms: structure and symmetry. Dordrecht: Springer Netherlands, 1997, pp. 107–166. ISBN 978-94-015-8937-6
  32. M. Eshera and K.-S. Fu, “An image understanding system using attributed symbolic representation and inexact graph-matching,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-8, pp. 604–618, 1986. http://dx.doi.org/10.1109/TPAMI.1986.4767835
  33. W.-H. Tsai and K.-S. Fu, “Error-correcting isomorphisms of attributed relational graphs for pattern analysis,” IEEE Transactions on Systems, Man, and Cybernetics, vol. 9, no. 12, pp. 757–768, 1979. http://dx.doi.org/10.1109/TSMC.1979.4310127
  34. M. Zaslavskiy, “Graph matching and its application in computer vision and bioinformatics,” Theses, École Nationale Supérieure des Mines de Paris, Jan. 2010.
  35. E. Bengoetxea, “Inexact graph matching using estimation of distribution algorithms,” Ph.D. dissertation, Ecole Nationale Supérieure des Télécommunications, Paris, France, Dec 2002.
  36. J. R. Ullmann, “An algorithm for subgraph isomorphism,” J. ACM, vol. 23, no. 1, p. 31–42, jan 1976. http://dx.doi.org/10.1145/321921.321925
  37. H. Bunke and G. Allermann, “Inexact graph matching for structural pattern recognition,” Pattern Recognition Letters, vol. 1, no. 4, pp. 245–253, 1983. http://dx.doi.org/10.1016/0167-8655(83)90033-8
  38. M. Neuhaus, K. Riesen, and H. Bunke, “Fast suboptimal algorithms for the computation of graph edit distance,” in Structural, Syntactic, and Statistical Pattern Recognition. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. ISBN 978-3-540-37241-7 pp. 163–172.
  39. D. A. Basin, “A term equality problem equivalent to graph isomorphism,” Information Processing Letters, vol. 51, no. 2, pp. 61–66, 1994. http://dx.doi.org/10.1016/0020-0190(94)00084-0
  40. M. A. Abdulrahim, Parallel algorithms for labeled graph matching. Colorado School of Mines1500 Illinois St. Golden, CO, 1998.
  41. J. E. Hopcroft and J. K. Wong, “Linear time algorithm for isomorphism of planar graphs (preliminary report),” in Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, ser. STOC ’74. Association for Computing Machinery, 1974. http://dx.doi.org/https://dx.doi.org/10.1145/800119.803896 p. 172–184.