Document (#23080)

Author

Mugnier, M.-L.

Title

Knowledge representation and reasonings based on graph homomorphisms

Source

Conceptual structures: logical, linguistic, and computational issues. 8th International Conference on Conceptual Structures, ICCS 2000, Darmstadt, Germany, August 14-18, 2000. Ed.: B. Ganter et al

Imprint

Berlin : Springer

Year

2000

Pages

S.172-192

Series

Lecture notes in computer science; vol.1867: Lecture notes on artificial intelligence

Abstract

The main conceptual contribution in this paper is to present an approach to knowledge representation and reasonings based on labeled graphs and labeled graph homomorphism. Strengths and weaknesses of this graph-based approach are discussed. Main technical contributions are the followings. Fundamental results about the kernel of this approach, the so-called simple graphs model are synthesized. It is then shown that the basic deduction problem on simple graphs is essentially the same problem as conjunctive query containment in databases and constraint satisfaction; polynomial parcimonious transformations between these problems are exhibited. Grounded on the simple graphs model, a knowledge representation and reasoning model allowing to deal with facts, production rules, transformation rules, and constraints is presented, as an illustration of the graph-based approach.

Similar documents (content)

1. Song, N.; Cheng, H.; Zhou, H.; Wang, X.: Linking scholarly contents : the design and construction of an argumentation graph (2022) 0.29

   0.28568196 = sum of:
     0.28568196 = product of:
       1.0202928 = sum of:
         0.008029515 = weight(abstract_txt:this in 2106) [ClassicSimilarity], result of:
           0.008029515 = score(doc=2106,freq=1.0), product of:
             0.042713117 = queryWeight, product of:
               1.0667521 = boost
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.016640248 = queryNorm
             0.18798709 = fieldWeight in 2106, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.05141215 = weight(abstract_txt:knowledge in 2106) [ClassicSimilarity], result of:
           0.05141215 = score(doc=2106,freq=4.0), product of:
             0.09278097 = queryWeight, product of:
               1.5722164 = boost
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.016640248 = queryNorm
             0.5541239 = fieldWeight in 2106, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.036411196 = weight(abstract_txt:model in 2106) [ClassicSimilarity], result of:
           0.036411196 = score(doc=2106,freq=1.0), product of:
             0.11701954 = queryWeight, product of:
               1.7656802 = boost
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.016640248 = queryNorm
             0.31115484 = fieldWeight in 2106, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.02478305 = weight(abstract_txt:based in 2106) [ClassicSimilarity], result of:
           0.02478305 = score(doc=2106,freq=1.0), product of:
             0.0996593 = queryWeight, product of:
               1.8815299 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016640248 = queryNorm
             0.24867775 = fieldWeight in 2106, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.097431734 = weight(abstract_txt:representation in 2106) [ClassicSimilarity], result of:
           0.097431734 = score(doc=2106,freq=2.0), product of:
             0.17901608 = queryWeight, product of:
               2.1838806 = boost
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.016640248 = queryNorm
             0.54426247 = fieldWeight in 2106, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.52991194 = weight(abstract_txt:graph in 2106) [ClassicSimilarity], result of:
           0.52991194 = score(doc=2106,freq=6.0), product of:
             0.42250645 = queryWeight, product of:
               3.8740828 = boost
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.016640248 = queryNorm
             1.2542102 = fieldWeight in 2106, product of:
               2.4494898 = tf(freq=6.0), with freq of:
                 6.0 = termFreq=6.0
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
         0.27231315 = weight(abstract_txt:graphs in 2106) [ClassicSimilarity], result of:
           0.27231315 = score(doc=2106,freq=1.0), product of:
             0.49256143 = queryWeight, product of:
               4.1829476 = boost
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.016640248 = queryNorm
             0.55285114 = fieldWeight in 2106, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.078125 = fieldNorm(doc=2106)
       0.28 = coord(7/25)
   

2. Auer, S.; Oelen, A.; Haris, A.M.; Stocker, M.; D'Souza, J.; Farfar, K.E.; Vogt, L.; Prinz, M.; Wiens, V.; Jaradeh, M.Y.: Improving access to scientific literature with knowledge graphs : an experiment using library guidelines to judge information integrity (2020) 0.22

   0.22352369 = sum of:
     0.22352369 = product of:
       0.7982989 = sum of:
         0.009084359 = weight(abstract_txt:this in 1317) [ClassicSimilarity], result of:
           0.009084359 = score(doc=1317,freq=2.0), product of:
             0.042713117 = queryWeight, product of:
               1.0667521 = boost
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.016640248 = queryNorm
             0.21268311 = fieldWeight in 1317, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.0544095 = weight(abstract_txt:knowledge in 1317) [ClassicSimilarity], result of:
           0.0544095 = score(doc=1317,freq=7.0), product of:
             0.09278097 = queryWeight, product of:
               1.5722164 = boost
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.016640248 = queryNorm
             0.58642954 = fieldWeight in 1317, product of:
               2.6457512 = tf(freq=7.0), with freq of:
                 7.0 = termFreq=7.0
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.01982644 = weight(abstract_txt:based in 1317) [ClassicSimilarity], result of:
           0.01982644 = score(doc=1317,freq=1.0), product of:
             0.0996593 = queryWeight, product of:
               1.8815299 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016640248 = queryNorm
             0.1989422 = fieldWeight in 1317, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.07794539 = weight(abstract_txt:representation in 1317) [ClassicSimilarity], result of:
           0.07794539 = score(doc=1317,freq=2.0), product of:
             0.17901608 = queryWeight, product of:
               2.1838806 = boost
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.016640248 = queryNorm
             0.43541 = fieldWeight in 1317, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.032189727 = weight(abstract_txt:approach in 1317) [ClassicSimilarity], result of:
           0.032189727 = score(doc=1317,freq=1.0), product of:
             0.13766795 = queryWeight, product of:
               2.211407 = boost
               3.741144 = idf(docFreq=2864, maxDocs=44421)
               0.016640248 = queryNorm
             0.2338215 = fieldWeight in 1317, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.741144 = idf(docFreq=2864, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.38699293 = weight(abstract_txt:graph in 1317) [ClassicSimilarity], result of:
           0.38699293 = score(doc=1317,freq=5.0), product of:
             0.42250645 = queryWeight, product of:
               3.8740828 = boost
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.016640248 = queryNorm
             0.9159456 = fieldWeight in 1317, product of:
               2.236068 = tf(freq=5.0), with freq of:
                 5.0 = termFreq=5.0
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
         0.21785052 = weight(abstract_txt:graphs in 1317) [ClassicSimilarity], result of:
           0.21785052 = score(doc=1317,freq=1.0), product of:
             0.49256143 = queryWeight, product of:
               4.1829476 = boost
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.016640248 = queryNorm
             0.44228092 = fieldWeight in 1317, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.0625 = fieldNorm(doc=1317)
       0.28 = coord(7/25)
   

3. Yang, L.; Chen, H.; Li, Z.; Ding, X.; Wu, X.: Give us the facts : enhancing Large Language Models with knowledge graphs for fact-aware language modeling (2024) 0.22

   0.21987823 = sum of:
     0.21987823 = product of:
       0.6871195 = sum of:
         0.051167116 = weight(abstract_txt:grounded in 2337) [ClassicSimilarity], result of:
           0.051167116 = score(doc=2337,freq=1.0), product of:
             0.11812141 = queryWeight, product of:
               1.0242041 = boost
               6.930783 = idf(docFreq=117, maxDocs=44421)
               0.016640248 = queryNorm
             0.43317392 = fieldWeight in 2337, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.930783 = idf(docFreq=117, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.057140082 = weight(abstract_txt:facts in 2337) [ClassicSimilarity], result of:
           0.057140082 = score(doc=2337,freq=1.0), product of:
             0.12714382 = queryWeight, product of:
               1.0626001 = boost
               7.190608 = idf(docFreq=90, maxDocs=44421)
               0.016640248 = queryNorm
             0.449413 = fieldWeight in 2337, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.190608 = idf(docFreq=90, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.009084359 = weight(abstract_txt:this in 2337) [ClassicSimilarity], result of:
           0.009084359 = score(doc=2337,freq=2.0), product of:
             0.042713117 = queryWeight, product of:
               1.0667521 = boost
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.016640248 = queryNorm
             0.21268311 = fieldWeight in 2337, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.058166206 = weight(abstract_txt:knowledge in 2337) [ClassicSimilarity], result of:
           0.058166206 = score(doc=2337,freq=8.0), product of:
             0.09278097 = queryWeight, product of:
               1.5722164 = boost
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.016640248 = queryNorm
             0.62691957 = fieldWeight in 2337, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.02912896 = weight(abstract_txt:model in 2337) [ClassicSimilarity], result of:
           0.02912896 = score(doc=2337,freq=1.0), product of:
             0.11701954 = queryWeight, product of:
               1.7656802 = boost
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.016640248 = queryNorm
             0.24892388 = fieldWeight in 2337, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.01982644 = weight(abstract_txt:based in 2337) [ClassicSimilarity], result of:
           0.01982644 = score(doc=2337,freq=1.0), product of:
             0.0996593 = queryWeight, product of:
               1.8815299 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016640248 = queryNorm
             0.1989422 = fieldWeight in 2337, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.24475582 = weight(abstract_txt:graph in 2337) [ClassicSimilarity], result of:
           0.24475582 = score(doc=2337,freq=2.0), product of:
             0.42250645 = queryWeight, product of:
               3.8740828 = boost
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.016640248 = queryNorm
             0.57929486 = fieldWeight in 2337, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
         0.21785052 = weight(abstract_txt:graphs in 2337) [ClassicSimilarity], result of:
           0.21785052 = score(doc=2337,freq=1.0), product of:
             0.49256143 = queryWeight, product of:
               4.1829476 = boost
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.016640248 = queryNorm
             0.44228092 = fieldWeight in 2337, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.0764947 = idf(docFreq=101, maxDocs=44421)
               0.0625 = fieldNorm(doc=2337)
       0.32 = coord(8/25)
   

4. Tang, X.-B.; Fu, W.-G.; Liu, Y.: Knowledge big graph fusing ontology with property graph : a case study of financial ownership network (2021) 0.18

   0.17881434 = sum of:
     0.17881434 = product of:
       0.7450597 = sum of:
         0.011126022 = weight(abstract_txt:this in 1235) [ClassicSimilarity], result of:
           0.011126022 = score(doc=1235,freq=3.0), product of:
             0.042713117 = queryWeight, product of:
               1.0667521 = boost
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.016640248 = queryNorm
             0.26048255 = fieldWeight in 1235, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
         0.08307997 = weight(abstract_txt:constraint in 1235) [ClassicSimilarity], result of:
           0.08307997 = score(doc=1235,freq=1.0), product of:
             0.16317949 = queryWeight, product of:
               1.2038019 = boost
               8.146119 = idf(docFreq=34, maxDocs=44421)
               0.016640248 = queryNorm
             0.50913244 = fieldWeight in 1235, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.146119 = idf(docFreq=34, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
         0.0650318 = weight(abstract_txt:knowledge in 1235) [ClassicSimilarity], result of:
           0.0650318 = score(doc=1235,freq=10.0), product of:
             0.09278097 = queryWeight, product of:
               1.5722164 = boost
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.016640248 = queryNorm
             0.7009174 = fieldWeight in 1235, product of:
               3.1622777 = tf(freq=10.0), with freq of:
                 10.0 = termFreq=10.0
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
         0.04119457 = weight(abstract_txt:model in 1235) [ClassicSimilarity], result of:
           0.04119457 = score(doc=1235,freq=2.0), product of:
             0.11701954 = queryWeight, product of:
               1.7656802 = boost
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.016640248 = queryNorm
             0.35203153 = fieldWeight in 1235, product of:
               1.4142135 = tf(freq=2.0), with freq of:
                 2.0 = termFreq=2.0
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
         0.055115715 = weight(abstract_txt:representation in 1235) [ClassicSimilarity], result of:
           0.055115715 = score(doc=1235,freq=1.0), product of:
             0.17901608 = queryWeight, product of:
               2.1838806 = boost
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.016640248 = queryNorm
             0.30788136 = fieldWeight in 1235, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               4.9261017 = idf(docFreq=875, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
         0.48951164 = weight(abstract_txt:graph in 1235) [ClassicSimilarity], result of:
           0.48951164 = score(doc=1235,freq=8.0), product of:
             0.42250645 = queryWeight, product of:
               3.8740828 = boost
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.016640248 = queryNorm
             1.1585897 = fieldWeight in 1235, product of:
               2.828427 = tf(freq=8.0), with freq of:
                 8.0 = termFreq=8.0
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.0625 = fieldNorm(doc=1235)
       0.24 = coord(6/25)
   

5. Yang, P.; Gao, W.; Tan, Q.; Wong, K.-F.: ¬A link-bridged topic model for cross-domain document classification (2013) 0.18

   0.17587887 = sum of:
     0.17587887 = product of:
       0.54962146 = sum of:
         0.0064236117 = weight(abstract_txt:this in 3706) [ClassicSimilarity], result of:
           0.0064236117 = score(doc=3706,freq=1.0), product of:
             0.042713117 = queryWeight, product of:
               1.0667521 = boost
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.016640248 = queryNorm
             0.15038967 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               2.4062347 = idf(docFreq=10885, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.093805805 = weight(abstract_txt:kernel in 3706) [ClassicSimilarity], result of:
           0.093805805 = score(doc=3706,freq=1.0), product of:
             0.17693801 = queryWeight, product of:
               1.2535244 = boost
               8.482592 = idf(docFreq=24, maxDocs=44421)
               0.016640248 = queryNorm
             0.530162 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               8.482592 = idf(docFreq=24, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.04112972 = weight(abstract_txt:knowledge in 3706) [ClassicSimilarity], result of:
           0.04112972 = score(doc=3706,freq=4.0), product of:
             0.09278097 = queryWeight, product of:
               1.5722164 = boost
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.016640248 = queryNorm
             0.44329908 = fieldWeight in 3706, product of:
               2.0 = tf(freq=4.0), with freq of:
                 4.0 = termFreq=4.0
               3.5463927 = idf(docFreq=3480, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.050452836 = weight(abstract_txt:model in 3706) [ClassicSimilarity], result of:
           0.050452836 = score(doc=3706,freq=3.0), product of:
             0.11701954 = queryWeight, product of:
               1.7656802 = boost
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.016640248 = queryNorm
             0.4311488 = fieldWeight in 3706, product of:
               1.7320508 = tf(freq=3.0), with freq of:
                 3.0 = termFreq=3.0
               3.9827821 = idf(docFreq=2249, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.01982644 = weight(abstract_txt:based in 3706) [ClassicSimilarity], result of:
           0.01982644 = score(doc=3706,freq=1.0), product of:
             0.0996593 = queryWeight, product of:
               1.8815299 = boost
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.016640248 = queryNorm
             0.1989422 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.1830752 = idf(docFreq=5005, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.032189727 = weight(abstract_txt:approach in 3706) [ClassicSimilarity], result of:
           0.032189727 = score(doc=3706,freq=1.0), product of:
             0.13766795 = queryWeight, product of:
               2.211407 = boost
               3.741144 = idf(docFreq=2864, maxDocs=44421)
               0.016640248 = queryNorm
             0.2338215 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               3.741144 = idf(docFreq=2864, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.13272482 = weight(abstract_txt:labeled in 3706) [ClassicSimilarity], result of:
           0.13272482 = score(doc=3706,freq=1.0), product of:
             0.28096104 = queryWeight, product of:
               2.2338822 = boost
               7.558333 = idf(docFreq=62, maxDocs=44421)
               0.016640248 = queryNorm
             0.4723958 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               7.558333 = idf(docFreq=62, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
         0.1730685 = weight(abstract_txt:graph in 3706) [ClassicSimilarity], result of:
           0.1730685 = score(doc=3706,freq=1.0), product of:
             0.42250645 = queryWeight, product of:
               3.8740828 = boost
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.016640248 = queryNorm
             0.40962332 = fieldWeight in 3706, product of:
               1.0 = tf(freq=1.0), with freq of:
                 1.0 = termFreq=1.0
               6.553973 = idf(docFreq=171, maxDocs=44421)
               0.0625 = fieldNorm(doc=3706)
       0.32 = coord(8/25)