TIM is a knowledge graph matching system with an architecture of Tiered Iterative Matchers that matches ontologies and instances simultaneously. The main idea behind Tim is to create matches based on existing matches and their connections within the knowledge graph. This is the first year where Tim is participating in the OAEI knowledge graph track and it achieves the highest performance for class and property matching as well as the second best performance for instance matching. Furthermore, Tim is the fastest non-baseline system participating in the knowledge graph track.
Let and be the two input knowledge graphs that contain the classes and , the properties and , and the instances and . Furthermore, let ∼= for ∈ ∪ ∪ , ∈ ∪ ∪ mean that is matched to . The ∼= relation is injective both ways, i.e., we only create 1-to-1 matches and reject any new matching attempt if the source component or target component of the match is already matched to something else.
For checking the equivalence of elements from the KGs based on the current state of the matching process, we define the function that maps target elements to their IRI, source elements that are matched to a target element to the target elements IRI, unmatched source elements to their own IRI, and literals to their lexical representation. Formally, () = ⎧⎪IRI() : if ∈ ( ∪ ∪ ) ⎪⎨IRI() : if ∈ ( ∪ ∪ ) ∧ ∃ ∼= ⎪IRI() : if ∈ ( ∪ ∪ ) ∧ ∄ ∼= ⎪⎩lexicalRepresentation() : if is a literal Based on this, we define triple representations that map triples consisting of ⟨head, rel, tail⟩ to a string representation with being a symbol that is not present in either input knowledge graph and + being string concatenation.
HRT(head,rel,tail) = (head) + + (rel) + + (tail).
Two triple representations are only equal if all components of both components are matched to their respective counterpart in the other triple.
Sometimes not all parts of the triple should be included in the representation, for example if we only want to check if the head and rel component of two triples are equal given the existing matches. Hence, we define representations for parts of a triple HR(head,rel,tail) based on the head and relation component, HT(head,rel,tail) based on the head and tail component, and RT(head,rel,tail) based on the relation and tail component: HR(head,rel,tail) = (head) + + (rel) HT(head,rel,tail) = (head) + + (tail)
RT(head,rel,tail) = (rel) + + (tail)
The architecture of Tim based on iterative matchers and bootstrap matchers is visualized in Figure 1. The iterative matchers are tiered by precision with the first iterative matcher having the highest precision. When the first iterative matcher is run and finds a match, the matcher is run again to be able to find more matches based on this match. When the first iterative matcher does not find a new match, then the second iterative matcher is run. As long as no new match is found by any matcher, the next tier matcher is run. When a new match gets found, the process starts at the first iterative matcher again because lower tier matchers can find more accurate matches that could conflict with matches found by subsequent matchers.
After the last iterative matcher does not find any new match, the first bootstrap matcher that was not run yet is run. As long as the bootstrap matchers do not find any new match, the next bootstrap matchers is run as by definition no iterative matcher cannot find a new match. When a new match is found, the first iterative matcher is run again. When all bootstrap matchers were run already and the iterative matchers do not find any new match, the process ends.
The iterative matchers build matches upon already existing matches. They are based mostly on the structure of the input knowledge graphs and match pairs that share similar connections to other instance pairs that were matched before. Properties are matched by unique occurrences and classes are matched based on the overlap of matched instance pairs with classes in the other KG. We summarize the iterative matchers of Tim in Table 1.
h c t a M w e N
no bootstrap matcher that was not run before
N e w M a t c h Matches instances that have the same label and alternative label, and belong to matching classes.
Matches instances that have the same label and alternative label, and are both the tail component in a triple where the head components got matched since the last iteration of this matcher and relation components are matched.
Matches instances that have at least two common triple representations (excluding labels) based on relation and tail component where the instances are the head component, and depending on the tier have: an equivalent label and an equivalent altLabel (Tier 3); an equivalent label (Tier 4); an equivalent alternative label (Tier 5); a source instance label equivalent to a target instance altLabel (Tier 6); a source instance altLabel equivalent to a target instance label (Tier 7).
The same as Tier 3-7 except that one common triple representation is enough. Matches properties that have a unique triple representation based on head and tail component. Matches instances that have two common unique triple representations based on the relation and tail component.
Matches classes when the overlap between instances belonging to these classes is greater than the mean instance overlap for already matched classes (excluding class pairs with less than 20% overlap).
The bootstrap matchers are used to create more seed matches in case the iterative matchers do not have any new matches available to build new matches upon. Most of the bootstrap matchers are simple and rely on matching classes, properties, or instances that have the same IRI, same label, similar words in the label, or unique attributes. We summarize the bootstrap matchers of Tim in Table 2.
Matches the classes whose labels have more than a 50% jaccard overlap (split by spaces) starting with the highest overlap pairs.
Matches the properties whose labels have more than a 50% jaccard overlap (split by spaces) starting with the highest overlap pairs.
Matches instances that have an equivalent label and equivalent altLabel.
Matches instance pairs where the source and target instance have one unique common triple representation based on the relation and tail component.
Matches instance pairs that have a common word (separated by spaces) in any literal attribute that is unique to that pair. 2. Results Since Tim is specifically designed to work on knowledge graphs that contain both ontology elements and instance information, Tim only produces significant results when the instances are present in the input KGs. While Tim is able to produce a mapping even when no instances are present in the input, only the very easy to find matches are included in the mapping; e.g., classes with equivalent labels. This is caused by all iterative matchers requiring instance information to function.
As Tim’s main focus is the knowledge graph track, we asses the results in the following with Tim’s
results for this track shown in Table 3. For the full results including other systems, see [
Tim produces better results than all participants from the last years edition. The only competitor that was able to surpass Tim in parts of the results is the newly participating DogMa system.
For the class mappings, Tim placed first for three out of five datasets and second for the remaining two. Additionally, Tim achieves the best overall class F-measure. The most outstanding result is generated for the datasets about Startrek where Tim surpasses all other systems by at least 0.14 F-measure. For the property mappings, Tim again achieves the best overall property F-measure with the first place for four datasets and the second place for one dataset. For the instance mappings, Tim places second behind DogMa in the overall comparison. Tim only places at the top spot two times for the instance datasets and places second three times. While the diference to DogMa is very small for most datasets, the diference amounts to 0.08 for the starwars-swg dataset.
Considering the runtime, overall Tim is the fastest non-baseline matcher1 with a total runtime of only 34 minutes and 13 seconds while the second fastest matcher (LogMap) needed over 56 minutes to ifnish the alignment process. Tim’s achieved time is only three times as much time as needed for the baseline matchers that only compare labels. Hence, we consider our matcher incredibly eficient. 3. General Comments
Throughout all results, Tim currently prioritizes precision over recall. The system provides better results than all systems that were participating in the last year and achieves best as well as second best rankings in this years version.
Up until this point, we have not done a lot of optimizations on Tim. Some points we will improve in the future are the following:
For the iterative matchers, there are still a lot of possibilities. Currently, for the iterative matchers 3-12 (see Table 1), the process is only executed to match head instances based on common triple representations on the basis of relations and tail instances. This could easily be expanded to also work the other way around, i.e. matching tail instances that have common triple representations based on the head and relation component. Furthermore, the iterative matchers strongly rely on equivalent labels and alternative labels, which could be relaxed to similar labels to increase recall.
The bootstrap matchers possess significantly more potential capabilities than those presently realized in the current version of Tim. They do not consider lexical or phonetical similarities, which can be beneficial for finding additional matches.
Additionally, the architecture could be adjusted to enable certain iterative matchers to activate only after a specified number of matches have been identified or once a predefined set of bootstrap matchers has been executed. This adjustment would help prevent erroneous matches produced by iterative matchers when only a limited number of matches are available (in particular, iterative matcher 15 is prone to such errors under sparse matching conditions).
We really enjoyed the test cases extracted from wikis using DBkWik[
We believe that this can be easily fixed in the next years version, for example by removing all instances from https://starwars.fandom.com that end with /Legends, and changing the alignment file to let correspondences containing an instance from legends to point to the canon instance instead. Alternatively, the gold standard could be extended by including both the canon as well as the legends version for instances that currently are only linked to one of them. 1DogMa is excluded from this because it has no runtime information available as only it’s alignment files were submitted 4. Conclusion Within this system paper, we presented Tim, a knowledge graph matching system using an architecture of tiered iterative matchers that jointly align ontologies and instances. The approach leverages structural information about the knowledge graphs utilizing previously established matches to discover new matches. Throughout the evaluation on the knowledge graph track, Tim demonstrates a strong performance, achieving best or second-best results in this years edition, outperforming all previously established systems from the last years edition. Notably, the system showed a high degree of eficiency with a total runtime significantly below all non-baseline competitors.
In future work, we are going to add additional matchers into Tim further increasing the accuracy especially regarding instance matching. Furthermore, we are going to optimize the runtime even more to make the approach scalable to even bigger datasets.
Acknowledgments This work has been supported by the Ministry of Culture and Science of North Rhine-Westphalia (MKW NRW) within the project SAIL under the grant no NW21-059D. This work has been supported within the project "WHALE" (LFN 1-04) funded under the Lamarr Fellow Network programme by the Ministry of Culture and Science of North Rhine-Westphalia (MKW NRW). This project has received funding from the European Union’s Horizon Europe research and innovation programme under grant agreement No 101070305.
Declaration on Generative AI The authors have not employed any Generative AI tools.