Nexus of Similarity between Entities

Abstract

Similarities play a significant role in diverse real-world scenarios. Researchers across various fields have proposed diferent methodologies for measuring entity similarity and expanding sets of entities with similar ones. As a result, modern machines are adept at performing these tasks by taking in some regard relevant interconnected properties shared by entities, which we refer to as nexus of similarity. To complement existing approaches, we present a very general logic-based framework, equipped with a suitable formal semantics, for characterizing nexus of similarity between (tuples of) entities of any knowledge base, namely express such nexus, formally and comprehensively, in a manner that they are both understandable to machines and humans.

Keywords

• Logic-based framework
• Formal semantics
• Nexus of similarity
• Knowledge bases

-

CEUR ceur-ws.org

1. Introduction

In real-life and everyday scenarios, the recognition and reasoning about similarities between entities often play a significant role. Even at a young age, kids begin to informally describe, classify, and compare entities. For example, they can easily recognize that both ⟨Paris⟩ and ⟨Rome⟩ are “cities”, and that ⟨Paris⟩ is more similar to ⟨Rome⟩ than to ⟨Gardaland⟩. Growing up, people become also able to identify and explain relevant interconnected properties shared by entities, hereinafter called

nexus of similarity. Adults can easily agree that ⟨Paris⟩ and ⟨Rome⟩ are both “Europe’s capitals situated on rivers”. Likewise, one can identify nexus of similarity between -ary tuples of entities. For instance, ⟨Tokyo, Tokyo Tower⟩ and ⟨Paris, Eifel Tower ⟩ are fairly similar, as each is a “capital paired with one of its monument being a tower made of metal”.

As we move towards more complex entities such as goods, services, or health conditions, the

challenges become greater, and the stakes become more interesting and valuable. For example, in e-commerce, Amazon’s recommendation system may suggest specific smartphones to a user interested in high-end devices equipped with features like accelerometer, compass, fingerprint, and Android 14. In the tourism industry, travel agencies may recommend other theme parks to IPS-RCRA-SPIRIT 2023: Italian Workshop on Planning and Scheduling, RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, CEUR Workshop Proceedings a family based on those they have previously visited. Streaming services such as Netflix may suggest trailers to their customers based on their previous viewing history and preferences. In medicine, researchers may need to understand why certain individuals are more susceptible to certain diseases than others. Clearly, in all the considered real-world scenarios, nexus of similarity play a crucial role.

For over a century, researchers from various fields have proposed a range of approaches to

measure the semantic similarity between entities, usually expressed in the form of a descriptive rating or a numerical score [2]. For example, computing machines nowadays reached a level of advancement where they are capable of computing a plausibly high similarity score between ⟨Paris⟩ and ⟨Rome⟩, by taking into account somehow that both of them are “European cities”, “places situated on rivers”, “capitals located in states that founded the European Economic

Community”, and so on. Moreover, some approaches are also capable of detecting that ⟨Paris⟩

and ⟨Eifel Tower ⟩ are not very similar, despite their high level of relatedness [3]. Finally, by following the same rationale, machines are also able to classify ⟨Rome⟩ as a “capital” rather then a “state” or a “park”, by comparing similarity scores between the considered entity and some class names.

In the past two decades, inspired by “Google Sets” [4], considerable academic and commercial eforts have been devoted to providing solutions for expanding a given set of entities with similar ones. The most studied tasks here are entity set expansion [5], entity recommendation [6], tuples expansion [7], or entity suggestion [8]. For example, via existing approaches one can expand the set = {⟨ Paris⟩, ⟨Rome⟩} and obtain, for example, ′ = ∪ {⟨ Amsterdam⟩}; then, one can reapply the process starting from ′ to obtain, for example, the expanded set ″ = ′ ∪ {⟨Brussels⟩, ⟨Rio de Janeiro⟩, ⟨Vienna⟩}. Indeed, all the elements of these sets share one or more of the aforementioned properties, namely “European cities”, “places situated on rivers”, etc.

Traditional approaches primarily measure similarities within (hyper)text corpora or tabular

data [9, 10]. In recent years, there has been an increasing trend in exploiting structured knowledge bases (KBs), often represented as knowledge graphs (KGs) [ 11, 12]. Indeed, ‘the heterogeneity, semantic richness and large-scale nature of knowledge base make traditional approaches less efective’ [ 13].

The work conducted thus far is remarkable, as well as the achieved results. However, there

remain some foundational aspects that, in our perspective, warrant further exploration. We propose a very general logic-based framework, equipped with a suitable formal semantics, for characterizing nexus of similarity between (tuples of) entities of any knowledge base, namely express such nexus, formally and comprehensively, so that the resulting explanations are readable by both humans and machines.

In Section 2, we introduce the notion of selective knowledge base, and our nexus explanation

language together with an appropriate semantics taking into account summaries. Moreover, we illustrate how to characterize the nexus of similarity between tuples of entities. In Section 3, we show how to construct logic formulas, called canonical characterizations, that characterize the nexus of similarity between tuples of entities. Finally, in Section 5 we draw our conclusions.

Pacific Park located California partOf

US isa amusement park isa Discovery Cove isa theme park

Gardaland

isa isa isa

Prater located Austria located

Florida partOf located isa Epcot located Italy located

Leolandia

2. Framework

Let us assume that we have the Knowledge Graph (KG) illustrated in Figure 1. This graph

can be naturally encoded as the dataset:

=̄ { isa(Epcot, tp), located(Epcot, Florida), partOf(Florida, US), …}.

Here, tp is a shorthand for theme_park and ap for amusement_park. Additionally, let us

assume that we have an ontology ̄ that specifies some intentional knowledge enriching the extensional knowledge already given by ̄ . As an example, we can consider the following ontology containing a single Datalog rule: =̄ { isa(, ) ←

isa(, ), isa( , )}.

By combining the dataset ̄ and the ontology ,̄ we have the Knowledge Base (KB) =̄ ( , ̄ ) ̄ .

As is customary, an atom is entailed by some knowledge base if it occurs in every model of

; accordingly, the set of atoms entailed by is denoted by ent( ) . In our example, the set of entailed atoms is:

ent( ) ̄ = ∪̄ { isa( 1, 3) ∶ isa( 1, 2) ∈ ∧̄ isa( 2, 3) ∈ }.̄

Consider now a set of -ary tuples of entities, which can be referred to as an anonymous

relation or simply as a unit. For example, we can choose the unit =̄ {⟨ Discovery Cove⟩, ⟨Epcot⟩} consisting of two unary tuples of entities. To express the nexus of similarity between the elements of , it is indeed necessary to first establish a consensus on the relevant features or predicates describing any entity in . Since such features or predicates might vary depending on the specific application scenario, we introduce the notion of summary selector. Definition 1. A summary selector is a computable function that takes as input a KB = (, ) together with an -ary tuple of entities from , selects a subset of ent( ) containing at least all the entities in , and return enriched with a top atom ⊤() for each entity in . ■

For the purposes of our example, let us adopt the simple yet efective selector ̄ that builds,

for each entity in ̄ , the dataset ( , ⟨̄⟩) as the union of the following sets: () = {( ′, ″) ∈ ent( ) ̄ ∶ ′ = }, () = { ′( ′, ″) ∈ ent( ) ̄ ∶ (, ′) ∈ () ∧ ≠ () = {⊤( ′) ∶ ′ is an entity in () ∪ ()} ∪ {⊤()}. isa ∧ ′ ≠ isa},

It is not dificult to see that satisfies Definition

when = Discovery_Cove, we have that

1 and thus it is a summary selector. For instance,

() = { isa(Discovery_Cove, tp), located(Discovery_Cove, Florida)} () = { partOf(Florida, US)} () = {⊤( Discovery_Cove), ⊤(tp), ⊤(Florida), ⊤(US)}

Intuitively, in () we select all knowledge directly connected (at distance 1) to our entity; in

() we select all knowledge connected at distance 2 with our entity, but without involving the relation isa; and in () we select all the necessary top atoms.

Definition 2. A selective knowledge base, SKB for short, is a pair = ( , ) knowledge base and is a summary selector. , where is a

Our goal, now, is to express the nexus of similarity between the tuples of the given with respect to the considered selective knowledge base . According to our running example that considers the unit ̄ and the SKB ,̄ by examining the next formula

1̄ = ← isa(, ap), located(, ), partOf( , US), where is its free variable (also known as output variable), it is evident that 1̄ explains some nexus of similarity between ⟨Discovery Cove⟩ and ⟨Epcot⟩. Indeed, formula 1̄ says that is an “amusement park located in some place which, in turn, is part of US”. However, 1̄ neglects the additional information that both entities are also located in Florida according to their summaries. Indeed, for example, the following formula ̄ = ← isa(, tp), isa(, ap), located(, Florida), partOf(Florida, US), ⊤(), ⊤( ap), ⊤(tp), ⊤(Florida), ⊤(US) better explains the nexus of similarity between the two entities. For characterizing (all) the nexus of similarity between the tuples of ,̄ we have to both fix a suitable explanation language and formalize the notion of characterization.

An (open conjunctive) formula is an expression of the form 1, … , ← 1(t1), … , (t ), ( 1 ) where > 0 is its arity, > 0 is its size often denoted by || , each t is a sequence of terms, each (t ) is an atom, and each is a variable —called free— occurring in some of the atoms of . A formula is nearly connected if each of its atoms is connected to some free variable of . For example, formula 1̄ above is nearly connected. Indeed, both isa(, ap) and located(, ) are connected to the free variable since they explicitly contain ; moreover, also partOf( , US) is connected to since it contains the variable which occurs in an atom already marked as connected to . Diferently, formula 2̄ = ← isa(, ap), partOf( , US) is not nearly connected.

We utilize nearly connected conjunctive formulas, NℂF for short, as the formalism to explain the

nexus of similarity between tuples within a unit, while considering their summaries.

As common in relational databases, a tuple ⟨ 1, … , ⟩ is an answer to over a dataset if there exists a variable substitution that maps each to and each atom of to . The output to over is the set ()

of all answers to over . For example, 1̄() ̄ is the set {⟨Pacific_Park⟩} and 1̄(ent( ))̄ is the set {⟨Pacific_Park⟩, ⟨Discovery_Cove⟩, ⟨Epcot⟩}. Since we deal with summaries, the notion of output of a formula has to be refined. To this end, an instance of a formula according to some selective knowledge base = ( , ) is any tuple which is an answer to over ( , ) . Intuitively, if is not an answer to over its summary ( , ) , then does not express properties of in terms of the considered scenario; if so, we consider not an instance of according to . The set of all -instances is denoted by inst(, ) .

Definition 3.

A nearly connected formula characterizes the nexus of similarity between the tuples of the unit if both the next conditions hold: () inst(, ) ⊇

; for every dataset ′.

() for each nearly connected formula ′ such that inst( ′, ) ⊇ , it holds that ( ′) ⊆ ′( ′) Accordingly, we may also say, for short, that characterizes , that is a characterization for , or that is characterized by (with respect to ). ■

It is now clear that formula 1̄ above expresses some nexus of ,̄ but does not characterize it with respect to .̄ Conversely, ̄ characterizes .̄ In the next section, we show how to construct a (canonical) characterization.

Essentially, having a canonical characterization is important because it shows directly two results, namely: a) a characterization always exists, which obviously is not an immediate result;

b) such a characterization has a bound in its size with respect to the initial input and this bound

is exponential with respect to the cardinality of the input unit, hence it becomes polynomial whenever you fix this parameter. The latter is particularly relevant, as often the sets of entities that we are interested in characterizing in the most diverse scenarios are formed from a few examples.

3. Canonical characterizations

We first recall and adapt to our purposes some well-known notions from database theory. Then,

we show how to explicitly build a canonical characterization of the -ary unit = { 1, … , } according to = ( , )

, called can( , ) .

Definition 4.

Consider the -ary tuples 1̄, … , ℓ̄. Their direct product, hereinafter denoted by = 1, … , .1 Accordingly, given datasets 1, … , , their direct product is the dataset 1̄ ⊗ … ⊗ ℓ̄, is the sequence s̄1, … , s̄ of constants, where s̄ is the sequence 1̄[], … , ̄ ℓ[] , for each 1The direct product of tuples is usually defined as a binary operation. Given two -ary tuples, = ⟨ [1], … , []⟩ and {(⟨ 11, … , 1 ⟩ ⊗ … ⊗ ⟨ 1, … , ⟩) ∶ ( 11, … , 1 ) ∈ 1, … , ( 1, … , ) ∈ } hereinafter denoted by 1 ⊗ … ⊗ .

Let us illustrate these notions with a simple example.

Example 1. Consider the following three binary tuples ⟨1, 2⟩, ⟨3, 4⟩, and ⟨5, 6⟩. Hence, their direct product is the sequence

⟨1, 2⟩ ⊗ ⟨3, 4⟩ ⊗ ⟨5, 6⟩ = 1,3,5, 2,4,6.

Now, consider the following two datasets Then, their direct product is the dataset

1 = {( a, c), ( c, e), ( e, b)} and 2 = {( a, b), ( b, a), ( b, d)}. Note that, since there is no element in 1 capable of being in direct product with the element ( b, d) of 2, the final set of atoms is devoid of the predicate .

For a dataset and an -ary unit = { 1, … , }, the direct product = ⊗ … ⊗ —multiplying

with itself times— has been already used in database theory to check whether admits a conjunctive query (i.e., a constant-free conjunctive formula) such that () = [14].

In particular, let s1, … , s = 1 ⊗ … ⊗ , the query is the following formula s1, … , s ←

⋀ ( 1,…, )∈ (( 1), … , ( )), where, for each constant of the form s occurring in , () = s. In case = (, ∅) and ( , ) = ∪ {⊤() ∶ is an entity in }

for every , then there are cases in which would characterize , but in general this is not guaranteed. The following examples precisely show where the classical direct product breaks and provide some useful insights on how the direct product could be enriched to correctly deal with nearly connected formulas and selective knowledge bases.

Example 2. Let us start by considering the dataset = { ( 1, 3 ), ( 2, 4 ), ( 5, 6 ), ( 3, 5 ), ( 4, 5 )} which is graphically represented in Figure 2 as a directed graph. Let = {⟨1⟩, ⟨2⟩} . Accordingly, ⊗ is depicted in Figure 3. Since ⟨1⟩ ⊗ ⟨2⟩ = 1,2, the expected query is 1,2 ← ( 1,1, 3,3), ( 1,2, 3,4), ( 2,2, 4,4), ( 5,1, 6,3), ( 5,5, 6,6), ( 5,2, 6,4), ( 2,1, 4,3), ( 2,5, 4,6), ( 1,5, 3,6), ( 3,3, 5,5), ( 4,4, 5,5), ′ = ⟨ ′[1], … , ′[]⟩ , then ⊗ ′ is the -ary tuple ⟨⟨ [1], ′[1]⟩, … , ⟨ [], ′[]⟩⟩ . Hence, this operation is associative up to isomorphisms, and it is possible to consider the direct product of more than two tuples [14, 15]. As we are not interested in a reiterate application of the direct product operator, for notational convenience, our direct product of two -ary tuples is not an -ary tuple, but just a sequence of fresh constants. ■ ■ r r r 3,3 3,4 4,4 r r s p 1,5 5,5 2,5 1,1 1,2 2,2 s p r r r 5 r

6 3,6 6,6 4,6 5,1 2,1 5,2 r r r 6,3 4,3 6,4 whose atoms are isomorphic to the dataset depicted in Figure 3. Assume now that the given SKB = ( , ) is such that = (, ∅) and ( , ) = ∪ {⊤() ∶ is an entity in } for every . Clearly, is not a characterization for with respect to . In this case, to obtain the following characterization for with respect to

← ( 1,2, 3,4), ⊤( 1,2), ⊤( 3,4) one can discard from all the atoms that are not connected to 1,2 and add a few ⊤-atoms. Note that, the only residual atom is ( 1,2, 3,4), which is isomorphic to ( 1,2, 3,4) —the one in yellow in Figure 3— which, in turn, is the only one connected to 1,2, despite the fact that is connected.■

Unfortunately, discarding atoms not connected to free variables and adding extra ⊤-atoms is

not enough to always yield to a characterization. This is illustrated via the following example. Example 3. Consider the SKB = ( , ) , where = (, ∅) , = { ( 1, 3 ), ( 2, 3 ), ( 3, 4 )} , and ( ) = ∪ {⊤() ∶ is an entity in } for every tuple . Let = {⟨1⟩, ⟨2⟩} . Accordingly, we have: ⊗ =

{ ( = 1,2 ←

1,1, 3,3), ( 2,2, 3,3), ( 3,3, 4,4), ( 1,2, 3,3), ( 2,1, 3,3) ( 1,3, 3,4), ( 3,1, 4,3), ( 2,3, 3,4), ( 3,2, 4,3)}, ( 1,1, 3,3), ( 2,2, 3,3), ( 3,3, 4,4), ( 1,2, 3,3), ( 2,1, 3,3) ( 1,3, 3,4), ( 3,1, 4,3), ( 2,3, 3,4), ( 3,2, 4,3)}.

By discarding from all the atoms that are not connected to 1,2 and adding the needed ⊤-atoms, we obtain ′ = 1,2 ← ( 1,2, 3,3), ( 2,1, 3,3), ( 1,1, 3,3), ( 2,2, 3,3), ( 3,3, 4,4),

⊤( 1,2), ⊤( 3,3), ⊤( 2,1), ⊤( 1,1), ⊤( 2,2), ⊤( 4,4).

Even if ′ is nearly connected and inst ( ′, ) ⊇ , formula ′ is still not a characterization in general. Indeed, it sufices to consider the following formula

″ = ← ( , 3), ⊤( ), ⊤( 3 ) and the dataset ′ = { ( 1, 1 ), ⊤( 1 )} . It is not dificult to see that ′ does not satisfy condition () of Definition 3 since inst ( ″, ) ⊇ but ′( ′) ⊆ ″( ′) does not hold: 1 is an answer of ′ over ′ but not an answer of ″ over ′.

A possible turn around could be the following: replace in ′ any variable of the form ,…, with the constant . This would produce the following formula ‴ = 1,2 ← ( 1,2, 3), ( 2,1, 3), ( 1, 3 ), ( 2, 3 ), ( 3, 4 ), ⊤( 1,2), ⊤( 3 ), ⊤( 2,1), ⊤( 1 ), ⊤( 2 ), ⊤( 4 ), which, this time, is a characterization for .

Note, however, that in some cases a constant of the form ,…, may give rise to a free variable ,…, . Clearly, if so, it cannot be replaced by , otherwise the arity of the resulting formula would be smaller than the arity of the unit. Unfortunately, as shown by the following example, keeping the the variable ,…, is not enough.2 Example 4. Consider the SKB = ( , ) together with the unit = {⟨1, 1⟩, ⟨1, 2⟩} , where = (, ∅) , = { ( 1, 2 ) , ( 2, 1 ) , ( 2, 1 ) , ( 1, 2 )} , and is such that (⟨1, 1⟩) = { ( 1, 2 ) , ( 1, 2 ) , ⊤( 1 ), ⊤( 2 )} and (⟨1, 2⟩) = { ( 1, 2 ) , ( 2, 1 ) , ⊤( 1 ), ⊤( 2 )}. In this case, by taking into account the summaries of the tuples of , instead of computing ⊗ we compute (⟨1, 1⟩) ⊗ (⟨1, 2⟩) . Hence, we obtain = (⟨1, 1⟩) ⊗ (⟨1, 2⟩) = { ( 1, 2 ), ( 1, 2 ), ⊤( 1 ), ⊤( 2 )} ⊗ { ( 1, 2 ), ( 2, 1 ), ⊤( 1 ), ⊤( 2 )} = = { ( 1,1, 2,2), ( 1,2, 2,1), ⊤( 1,1), ⊤( 1,2), ⊤( 2,1), ⊤( 2,2)}.

Since the direct product between the tuples of is ⟨1, 1⟩ ⊗ ⟨1, 2⟩ = 1,1, 1,2, then the candidate characterization (constructed by using the approach discussed before) should be: = 1,1, 1,2

← ( 1,1, 2), ( 1,2, 2,1), ⊤( 1,1), ⊤( 1,2), ⊤( 2,1), ⊤( 2 ), where only the constant 2,2 is replaced by the constant 2. However, this is not a characterization. Indeed, it violates condition () of Definition 3. To see that, consider the formula ′ = 1,1, 1,2 ←

⊤( 1,1), ⊤( 1,2), ( 1, 2 ), ⊤( 1 ), ⊤( 2 ) together with the dataset ′ = { ( 2, 2 ), ( 2, 2 ), ⊤( 2 )} .

In light of the previous example, it seems that atoms containing constants of the form ,…, occurring in the sequence 1 ⊗ … ⊗ should be “cloned” so that in some of them, ,…, can be replaced by ,…, , while in some other, ,…, can be replaced by . We are now ready to show how to construct the canonical characterization can( , ) .

2To lighten the notation, in what follows instead of writing ( , ) , we will just write ( ) .

■ ■ Step 1. Let s1, … , s = 1 ⊗ … ⊗ denote the sequence of constants used to determine the free variables of can( , ) , and let Fr denote the set collecting these constants (note that, in general, |Fr | ≤ ). According to Example 4, 1 = ⟨1, 1⟩, 2 = ⟨1, 2⟩, s1, s2 = 1,1, 1,2, and Fr is the set { 1,1, 1,2}.

Step 2. Build the dataset = ( 1) ⊗ … ⊗ ( ) used to determine some atoms of can( , ) .

See, for instance, the set of atoms constructed in Example 4. In particular, the domain of is

the set = { 1,1, 1,2, 2,2, 2,1}.

Step 3. Consider any s occurring in , and let s be the set of constants of s. If | s| = 1, then the atoms of containing s might have to be “cloned” to determine some extra atoms of can( , ) . As we already discussed, this is needed whenever s satisfies both | s| = 1 and s ∈ Fr . Accordingly, let Ge = { s ∈ ∶ | s| = 1} be the set of constants used as possible “genes” for such clones. According to Example 4, Ge = { 1,1, 2,2}.

Step 4. For each s ∈ , let Now, for any atom = ( 1, … , ) of , we define and, finally, let ( s) = { { s, s[1]} { s} if s ∈ Fr ∩ Ge otherwise. clones() = {( 1, … , ) ∶ ℎ ∈ ( )} ⧵ {}

= { ′ ∈ clones() ∶ ∈ } be the set of all the clones that complement the atoms of . According to Example 4, Fr ∩ Ge = { 1,1}. Moreover, ( 1,1) = { 1,1, 1}, ( 1,2) = { 1,2}, ( 2,1) = { 2,1}, and ( 2,2) = { 2,2}. Hence, clones() = ∅ , whenever ∈ {( 1,2, 2,1), ⊤( 1,2), ⊤( 2,1), ⊤( 2,2)}; clones( ( 1,1, 2,2)) = { (1, 2,2)}; and clones(⊤( 1,1)) = {⊤( 1 )}. Finally, we have that = { (1, 2,2), ⊤( 1 )} and the domain of is = {1, 2,2}.

Step 5. Let be the mapping { ↦ ∶ ∈ ⧵ } ∪ { s ↦ ( s) ∶ s ∈ } used to transform atoms of ∪ into atoms of can( , ) , where

s if s ∈ Fr ( s) = { s if s ∉ Fr ∪ Ge

s[1] if s ∈ Ge ⧵ Fr .

Consider the next formula (“∧” is used instead of “,”):

According to Example 4, Fr ∪ Ge = { 1,1, 1,2, 2,2} and Ge ⧵ Fr = { 2,2}. Hence, ( 1,1) = 1,1, ( 1,2) = 1,2, ( 2,1) = 2,1, and ( 2,2) = 2. Moreover, ⧵ = {1}and, therefore, = {1 ↦ 1} ∪ { 1,1 ↦ 1,1, 1,2 ↦ 1,2, 2,1 ↦ 2,1, 2,2 ↦ 2}. Then, we have ∪ = { (

1,1, 2,2), ( 1,2, 2,1), ⊤( 1,1), ⊤( 1,2), ⊤( 2,1), ⊤( 2,2), (1, 2,2), ⊤( 1 )}.

Finally, we obtain

← ( 1,1, 2), ( 1,2, 2,1), ⊤( 1,1), ⊤( 1,2), ⊤( 2,1), ⊤( 2 ), ( 1, 2 ), ⊤( 1 ). Step 6.

We are now ready to define the desired canonical characterization can( , ) .

Definition 5. We define can( , ) as the nearly connected formula obtained from Φ( , ) by discarding all and only the atoms that are not connected to any free variable of Φ( , ) .We refer to can( , ) as the canonical characterization of according to .

According to Example 4, since Φ( , )

immediately get that can( , ) = Φ( , ) .

Theorem 1. It holds that can( , ) characterizes .

is already a nearly connected formula, then we

For completeness of exposition, we close the section by showing how to systematically

construct can( , ̄ ) ̄ according to our running example started in Section 2. The direct product of the elements of ̄ is the (unary) sequence ⟨Epcot⟩ ⊗ ⟨Discovery_Cove⟩ = Epcot,Discovery_Cove. Hereinafter, to lighten the notation, we denote Discovery_Cove by D, Epcot by E, and Florida by F. Thus, Fr = { E,D}. Now, to compute = (⟨̄ Epcot⟩) ⊗ (⟨̄ Discovery Cove⟩), we need to exploit the summaries of ⟨Epcot⟩ and ⟨Discovery_Cove⟩ already introduced in the previous section: (⟨̄ E⟩) = {located(E, F), partOf(F, US), isa(E, tp), isa(E, ap),

⊤(E), ⊤(F), ⊤(US), ⊤(tp), ⊤(ap)} (⟨̄ D⟩) = {located(D, F), partOf(F, US), isa(D, tp), isa(D, ap),

⊤(D), ⊤(F), ⊤(US), ⊤(tp), ⊤(ap)}

Therefore, the set of atoms is:

{located( E,D, F,F), partOf( F,F, US,US), isa( E,D, tp,tp), isa( E,D, tp,ap), isa( E,D, ap,tp), isa( E,D, ap,ap), ⊤( E,D), ⊤( E,F), ⊤( E,US), ⊤( E,tp), ⊤( E,ap), ⊤( F,D), ⊤( F,F), ⊤( F,US), ⊤( F,tp), ⊤( F,ap), ⊤( US,D), ⊤( US,F), ⊤( US,US), ⊤( US,tp), ⊤( US,ap)⊤( tp,D), ⊤( tp,F), ⊤( tp,US), ⊤( tp,tp), ⊤( tp,ap), ⊤( ap,D), ⊤( ap,F), ⊤( ap,US), ⊤( ap,tp), ⊤( ap,ap), }. Accordingly, Ge = { F,F, US,US, tp,tp, ap,ap}. This time, since Fr ∩ Ge = ∅, we have that also the set is empty. Therefore, = { E,D ↦ E,D, E,F ↦ E,F, E,US ↦ E,US, E,tp ↦ E,tp, E,ap ↦ E,ap, F,D ↦ F,D, F,F ↦ F, F,US ↦ F,US, F,tp ↦ F,tp, F,ap ↦ F,ap, US,D ↦ US,D, US,F ↦ US,F, US,US ↦ US, US,tp ↦ US,tp, US,ap ↦ US,ap, tp,D ↦ tp,D, tp,F ↦ tp,F, tp,US ↦ tp,US, tp,tp ↦ tp, tp,ap ↦ tp,ap, ap,D ↦ ap,D, ap,F ↦ ap,F, ap,US ↦ ap,US, ap,tp ↦ ap,tp, ap,ap ↦ ap}. Φ( , ̄ ) ̄= E,D ← located( E,D, F), partOf(F, US), isa( E,D, tp), isa( E,D, tp,ap), isa( E,D, ap,tp), isa( E,D, ap), ⊤( E,D), ⊤( E,F), ⊤( E,US), ⊤( E,tp), ⊤( E,ap), ⊤( F,D), ⊤(F), ⊤( F,US), ⊤( F,tp), ⊤( F,ap), ⊤( US,D), ⊤( US,F), ⊤(US), ⊤( US,tp), ⊤( US,ap), ⊤( tp,D), ⊤( tp,F), ⊤( tp,US), ⊤(tp), ⊤( tp,ap), ⊤( ap,D), ⊤( ap,F), ⊤( ap,US), ⊤( ap,tp), ⊤(ap).

Now, we can obtain the canonical characterization

can( , ̄ ) ̄= E,D ← located( E,D, F), partOf(F, US), isa( E,D, tp), isa( E,D, tp,ap), isa( E,D, ap,tp), isa( E,D, ap), ⊤( E,D), ⊤(US), ⊤(tp), ⊤( tp,ap), ⊤(F), ⊤( ap,tp), ⊤(ap), by discarding all the atoms that are not connected to the free variable E,D.

It is worth noting that, by the construction, we have not only proved that a characterization always exists, which is a non-trivial result, but also that, since its construction is clearly exponential in the cardinality of the input unit, whenever you fix this parameter you get something of polynomial size.

4. Related Work

There are some works that show how to construct least general generalizations in specific

settings. We are going to discuss some key approaches using our terminology.

In [16], given a dataset over a single ternary relation triple encoding an RDF graph, a unary

unit of resources, and a characteristic function returning, for any resource ⟨ ⟩ ∈ , a set of

RDF triples connected to (like our summaries which, however, are not necessarily connected),

the authors show how to construct a generalized RDF graph (namely, an RDF graph with blank nodes) being connected and acting as the least common subsumer (LCS) of the resources in (like our canonical characterizations). Hence, NℂFs can be considered an extension of rooted RDF-graphs. Indeed, in [16], the formalism roughly coincides with unary (nearly) connected conjunctive formulas; here the authors adopt this notion to discard irrelevant (i.e., disconnected) properties. To guarantee the existence of LCSs, the authors consider only characteristic functions that return sets containing at least one atom of the form triple( , , ) for some and . Note that, diferently from [ 16], we enforce summaries to be closed under ⊤. In case of unary units as considered by [16], one could avoid top atoms: whenever a characterization does not exist, then one might assume ← ⊤() as a default characterization. Conversely, in case of units of arbitrary arities, there are meaningful characterizations that would not exist if summaries are not closed under ⊤: for example, , ← (), ⊤(), ⊤( ) would not exist as a characterization but it is more informative than the default one, namely , ← ⊤(), ⊤( ) .

Speaking of arbitrary arity, one of the key elements of our framework is precisely its nonlimitation to being able to ask questions only in relation to unary units. The justification for this also lies, just to give an example, in wanting to study similarities between tuples of objects by ifnding so-called ”analogies” as in the case of the common ”a is to b as c is to d” [ 17]. In fact, one way to look at this in our setting is that an analogy between two tuples exists in our context when they have the same characterization when viewed as units. A concrete example of this is the one we gave in the introduction, where we referred to ⟨Tokyo, Tokyo Tower⟩ and ⟨Paris, Eifel Tower ⟩, which are fairly similar, as each is a “capital paired with one of its monuments being a tower made of metal”, or as already stated in [17] the two tuples ⟨Leopard, Cat⟩ and ⟨Wolf, Dog⟩ in which essentially the first element is nothing other than a more ferocious species equipped with fangs who lives in a wild environment with respect to the second element. It is, however, important to note that while in the aforementioned work they give rise to real scores to determine whether an analogy exists or not we should turn to query answering, it will however be the aim of future work to also evaluate adequate metrics for the discovery of nexus of similarity.

In [18], given a KB expressed in the EL(I ) description logic, a unary unit with | | = 1 , and a summary selector always returning ent( ) , the authors study the problem of checking whether an EL(I )-characterization (called most specific concept or MSC) exists and verifying whether a given EL(I ) concept is an MSC. Moreover, the authors also study the variant of these problems where the input unit contains a set of EL(I ) concepts rather then entities, in order to study existence and verification of LCSs.

In [19], under arbitrary (union of) conjunctive queries (U)CQs, KBs with an empty (onto)logi

cal part, and summary selectors always returning the entire dataset, the authors study existence, verification, and construction of characterizations (called fitting CQs).

Finally, it is worth noting that our NℂFs can be considered an extension also of routed CQs [20]. This formalism essentially coincides with nearly connected conjunctive formulas without constants; here, the authors show that, without summaries, CQs and routed CQs are invariant with respect to their instances. However, in case summaries do not coincide with the whole ent( ) , CQs (resp., conjunctive formulas) and routed CQs (resp., NℂFs) behave in diferent ways: in general, instances of characterizations are diferent.

5. Discussion and Conclusion

We start by examining some key design choices that have shaped our framework. After that, we will outline future directions for our research.

As already recognized by [16], when dealing with common properties, the use of summaries

is rather crucial. Indeed, in our framework, avoiding the use of reasonably small summaries has the following negative efects: () characterizations would lose readability for humans; () nexus of similarity would not nicely fit the considered scenario; and () the direct product of two large datasets would be computationally unfeasible. In contrast, the ability to selectively exclude irrelevant features and predicates plays a crucial role in achieving meaningful characterizations.

By focusing on the relevant information, we ensure that resulting characterizations are efective

and tailored to the specific needs of the given application scenario.

NℂFs naturally captures shared interconnected properties since they: ( 1 ) allow the inclusion of constants, which provide informative details; ( 2 ) allow for existential quantification (i.e., nonfree variables), capturing connections beyond constants; ( 3 ) support conjunction and joins, as they inherently express connections between entities; ( 4 ) accommodate multiple free variables to go beyond unary concepts; ( 5 ) prevent disconnected components and disjunction, which go beyond semantic connections; (6) avoid forcing one connected component or acyclicity, as characterizations may not exist; (7) waive negation or universal quantification, as they inherently consider information beyond summaries; and (8) disallow built-in equality, which badly interacts with constants. Regarding the latter, consider the following SKB = ( , ) , where = (, ∅) , = { (, ), (, ), (, ), (, )} , (⟨⟩) = (⟨⟩) = ∪{⊤() ∶ occurs in } , and = {⟨⟩} . Intuitively, and are indistinguishable as they “encounter” exactly the same constants; indeed, they are transposable (i.e., more than automorphic). If we allowed equality, then can( , ) would be of the form ← … = .

Future directions include: () a computational analysis of key reasoning tasks; () further tuning NℂF; () enriching summaries with intentional knowledge or anonymous individuals; for example, by incorporating rules such as isa(, film) → ∃ directed(, ) , films without known directors would share more nexus of similarities with films with known directors; ( ) dealing with entity set expansion; ( ) designing and developing a prototype as a web service that implements the proposed framework on top of Linked Open Data; ( ) the definition of an appropriate metric to evaluate the nexus of similarity; and ( ) conducting experiments and evaluations to test and compare diferent summary selectors.

Acknowledgments

This work contributes to the basic research activities of the WP9.1: “KRR Frameworks for

Green-aware AI” supported by the PNRR project FAIR - Future AI Research (PE00000013), Spoke

9 - Green-aware AI, under the NRRP MUR program funded by the NextGenerationEU.

in Natural Language Processing, EMNLP 2009, 6-7 August 2009, Singapore, A meeting of SIGDAT, a Special Interest Group of the ACL, ACL, 2009, pp. 938–947. URL: https: //aclanthology.org/D09-1098/. [6] R. Blanco, B. B. Cambazoglu, P. Mika, N. Torzec, Entity recommendations in web search, in: H. Alani, L. Kagal, A. Fokoue, P. Groth, C. Biemann, J. X. Parreira, L. Aroyo, N. F.

Noy, C. Welty, K. Janowicz (Eds.), The Semantic Web - ISWC 2013 - 12th International

Semantic Web Conference, Sydney, NSW, Australia, October 21-25, 2013, Proceedings,

Part II, volume 8219 of Lecture Notes in Computer Science, Springer, 2013, pp. 33–48. URL:

https://doi.org/10.1007/978-3-642-41338-4_3. doi:10.1007/978- 3- 642- 41338- 4\_3. [7] N. A. S. Er, T. Abdessalem, S. Bressan, Set of t-uples expansion by example, in:

G. Anderst-Kotsis (Ed.), Proceedings of the 18th International Conference on Information

Integration and Web-based Applications and Services, iiWAS 2016, Singapore, Novem

ber 28-30, 2016, ACM, 2016, pp. 221–230. URL: https://doi.org/10.1145/3011141.3011144. doi:10.1145/3011141.3011144. [8] Y. Zhang, Y. Xiao, S. Hwang, H. Wang, X. S. Wang, W. Wang, Entity suggestion with conceptual expanation, in: C. Sierra (Ed.), Proceedings of the Twenty-Sixth International

Joint Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August

19-25, 2017, ijcai.org, 2017, pp. 4244–4250. URL: https://doi.org/10.24963/ijcai.2017/593. doi:10.24963/ijcai.2017/593. [9] G. Xun, Y. Li, W. X. Zhao, J. Gao, A. Zhang, A correlated topic model using word embeddings, in: C. Sierra (Ed.), Proceedings of the Twenty-Sixth International Joint

Conference on Artificial Intelligence, IJCAI 2017, Melbourne, Australia, August 19

25, 2017, ijcai.org, 2017, pp. 4207–4213. URL: https://doi.org/10.24963/ijcai.2017/588. doi:10.24963/ijcai.2017/588. [10] J. Huang, W. Zhang, Y. Sun, H. Wang, T. Liu, Improving entity recommendation with search log and multi-task learning, in: J. Lang (Ed.), Proceedings of the Twenty-Seventh

International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018,

Stockholm, Sweden, ijcai.org, 2018, pp. 4107–4114. URL: https://doi.org/10.24963/ijcai. 2018/571. doi:10.24963/ijcai.2018/571. [11] J. Chen, Y. Chen, X. Zhang, X. Du, K. Wang, J. Wen, Entity set expansion with semantic features of knowledge graphs, J. Web Semant. 52-53 (2018) 33–44. URL: https://doi.org/10. 1016/j.websem.2018.09.001. doi:10.1016/j.websem.2018.09.001. [12] M. Lissandrini, D. Mottin, T. Palpanas, Y. Velegrakis, Graph-query suggestions for knowledge graph exploration, in: Y. Huang, I. King, T. Liu, M. van Steen (Eds.), WWW ’20: The Web Conference 2020, Taipei, Taiwan, April 20-24, 2020, ACM / IW3C2, 2020, pp. 2549–2555.

URL: https://doi.org/10.1145/3366423.3380005. doi:10.1145/3366423.3380005. [13] H. Ma, Y. Ke, An introduction to entity recommendation and understanding, in:

A. Gangemi, S. Leonardi, A. Panconesi (Eds.), Proceedings of the 24th International Confer

ence on World Wide Web Companion, WWW 2015, Florence, Italy, May 18-22, 2015 - Companion Volume, ACM, 2015, pp. 1521–1522. URL: https://doi.org/10.1145/2740908.2741991. doi:10.1145/2740908.2741991. [14] P. Barceló, M. Romero, The complexity of reverse engineering problems for conjunctive queries, in: M. Benedikt, G. Orsi (Eds.), 20th International Conference on Database Theory,

ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, Schloss Dagstuhl - Leibniz

References

[1] R. De Benedictis , N. Gatti , M. Maratea , A. Murano , E. Scala , L. Serafini , I. Serina , E. Tosello , A. Umbrico , M. Vallati , Preface to the Italian Workshop on Planning and Scheduling , RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023 ), in: Proceedings of the Italian Workshop on Planning and Scheduling , RCRA Workshop on Experimental evaluation of algorithms for solving problems with combinatorial explosion, and SPIRIT Workshop on Strategies, Prediction, Interaction, and Reasoning in Italy (IPS-RCRA-SPIRIT 2023) co-located with 22th International Conference of the Italian Association for Artificial Intelligence (AI* IA 2023 ), 2023 .

[2] W. Gomaa , A. Fahmy , A survey of text similarity approaches , International Journal of Computer Applications 68 ( 2013 ) 13 - 18 .

[3] D. Chandrasekaran , V. Mago , Evolution of semantic similarity - A survey , ACM Comput. Surv . 54 ( 2022 ) 41 : 1 - 41 : 37 . URL: https://doi.org/10.1145/3440755. doi: 10 .1145/3440755 .

[4] J. Cirasella , Google sets, google suggest, and google search history: Three more tools for the reference librarians bag of tricks , The Reference Librarian 48 ( 2007 ). URL: http: //ref.haworthpress.com.

[5] P. Pantel , E. Crestan , A. Borkovsky , A. Popescu , V. Vyas , Web-scale distributional similarity and entity set expansion , in: Proceedings of the 2009 Conference on Empirical Methods