REX: Explaining Relationships between Entity Pairs

1. INTRODUCTION

• Users may find related-entity suggestions puzzling because the reason the entities are connected is often unclear.Informal Yahoo! user studies indicated that adding concrete explanations would increase suggestion relevance and user engagement.Source: §1 · p. 1
• REX takes an already-related entity pair and produces explanations from structured knowledge-base information rather than determining why the pair was selected as related.The paper separates explanation generation from related-entity selection, which may rely on semantically opaque mechanisms such as users querying entities together.Source: §1 · pp. 1–2
• Explanation generation has two stages: enumerate candidate explanations for the entity pair, then rank them by interestingness.The paper identifies efficient processing over large knowledge bases and ranking many candidates as challenges.Source: §1 · p. 2
• REX distinguishes its approach by considering connecting structures more complex than trees and paths and introducing two families of pattern-level interestingness measures.The paper also presents efficient enumeration and ranking algorithms as contributions.Source: §1 · p. 2
• REX formalizes relationship explanations and develops efficient algorithms to enumerate and rank them using multiple interestingness measures.The authors also report user studies and extensive experiments to evaluate effectiveness and efficiency.Source: §1 · p. 2

2.1 Knowledge Base

• The knowledge base is a graph whose nodes are entities and whose labeled edges represent primary relationships, which may be directed or undirected.The running example uses a subset of an entertainment knowledge base.Source: §2.1 · p. 2

2.2 Relationship Explanation

• A relationship explanation pattern connects two target nodes with labeled edges and variable nodes, while its instances are mappings that satisfy the pattern in the knowledge base.Examples include spouse, co-starring, and richer patterns involving producing or collaboration with the same director.Source: §2.2 · pp. 2–3

2.3 Properties of Explanations

• A pattern is essential when every node and edge lies on a simple path between the target nodes.The authors exclude non-essential patterns from the core study even though they may convey meaningful information; such nodes, edges, and attribute constraints could be added in a separate stage.Source: §2.3 · p. 3
• A pattern is non-decomposable when its edges cannot be partitioned into separate patterns that share no non-target node.For example, a spouse edge alongside a co-starring pattern can form a decomposable structure.Source: §2.3 · p. 3
• A minimal explanation has a pattern that is both essential and non-decomposable.These structural properties narrow the space of possible explanations, some of which may not be semantically meaningful.Source: §2.3 · p. 3

3. EXPLANATION ENUMERATION

• NaiveEnum expands graph patterns and filters out nonminimal or instance-free candidates, motivating methods that generate only minimal explanations with instances.Nonminimal patterns cannot be pruned early because they may later expand into minimal ones.Source: §3 · p. 4

3.1 Explanation Enumeration Framework

• Every minimal explanation is covered by paths, so the framework enumerates path patterns and instances, then combines them; a size limit n implies path-length limit n−1.Instances of combined explanations can be computed from the instances of their covering paths rather than evaluated from scratch.Source: §3.1 · p. 4

3.2 Path Explanation Enumeration

• PathEnumBasic joins partial paths grown from both targets, while PathEnumPrioritized uses activation scores to choose which partial paths to expand.The activation score favors expansion from nodes with higher scores, which are updated using neighboring nodes’ degrees.Source: §3.2 · p. 5

3.3 Path Explanation Combination

• Minimal patterns are grouped by the smallest number of covering patterns, and each MinP(k) can be derived from MinP(k−1) and path patterns.MinP(1) contains path patterns.Source: §3.3 · p. 5

3.3.1 PathUnionBasic

• PathUnionBasic repeatedly merges queued explanations with path explanations, keeping minimal patterns that have instances and removing duplicates by graph isomorphism.Merging uses a partial one-to-one node mapping; the resulting pattern is retained only when it has at least one instance.Source: §3.3.1 · pp. 5–6

3.3.2 PathUnion with Pruning

• PathUnionPrune uses Theorem 3 and recorded composition histories to avoid unnecessary merges when enumerating minimal explanations.The theorem constrains how patterns in MinP(k) can be composed from smaller patterns.Source: §3.3.2 · p. 6

AND EXPLANATION RANKING

• Because users may consume only a limited number of explanations, the section motivates ranking them by subjective interestingness and examines monotonicity as a basis for pruning.Anti-monotonicity holds for some measures and can be used in enumeration and ranking.Source: AND EXPLANATION RANKING · pp. 6–7

4.1 Structure-based measures

• Structural measures score pattern topology: size summarizes structural complexity, while random walk uses current through a pattern treated as an electrical network.Pattern size can also be combined with other interestingness measures.Source: §4.1 · p. 7

4.2 Aggregate Measures

• Mcount assigns an explanation the total number of distinct instances, but it is neither monotonic nor anti-monotonic, making pruning difficult.The count measure aggregates instances for a given explanation pattern.Source: Count · p. 7

Monocount

• Monocount uses the fewest distinct assignments across non-target variables and is proposed as an anti-monotonic alternative to Mcount.When there is a direct edge between target entities, monocount is defined as 1.Source: Monocount · p. 7

4.3 Distribution-Based Measures

• Distribution-based measures compare an explanation’s aggregate score across varied target pairs to capture rarity that aggregate counts alone miss.Local distributions vary the end target; global distributions vary both targets.Source: §4.3 · p. 8

4.4 Explanation Ranking

• Anti-monotonic measures such as monocount support pruning during enumeration, while the general ranking framework computes scores for enumerated explanations and returns the top k.For anti-monotonic measures, the algorithm maintains a current top-k list and continues expansion only from explanations still in that list.Source: §4.4 · p. 8

5. EXPERIMENTS

• REX’s evaluation covers explanation enumeration and ranking performance, as well as user-study assessments of explanation quality.The studies examine the necessity of including non-path explanations and the effectiveness of explanations generated by REX.Source: §5 · pp. 8–9
• Figure 7 compares explanation enumeration algorithms.Source: Figure 7 · p. 9
• The user studies assess whether the explanation definition, including non-path explanations, is necessary and whether REX-generated explanations are effective.Source: §5 · p. 9

5.1 Experimental Settings

• The DBpedia entertainment knowledge base contains 200K entities, over 1.3M primary relationships, 20 entity types, and 2,795 primary relationship types.Source: §5.1 · p. 9
• The evaluation pairs are formed by randomly selecting a start entity and then one of its search-engine-suggested related entities.Source: §5.1 · p. 9
• Thirty pairs are sampled for performance evaluation: 10 each from low, medium, and high connectedness groups defined by simple-path counts.The groups are low (0–30), medium (30–100), and high (over 100) paths within a given length limit.Source: §5.1 · p. 9

• The evaluation compares graph enumeration with a path-enumeration-and-union framework and progressively optimized path-enumeration and path-union algorithms.The experiments set the pattern-size limit to 5.Source: §5.2 · p. 9
• PathUnionPrune takes on average one-third the time of PathUnionBasic, while path-enumeration and union combinations improve by orders of magnitude over NaiveEnum across all three entity-pair groups.The shared-component pruning in PathUnionPrune accounts for its improvement over PathUnionBasic.Source: §5.2 · p. 9
• Enumeration time increases linearly with explanation-instance count, reaching as many as 5,000 instances across the 30 tested pairs.Figure 8 plots instance count against enumeration time for PathEnumPrioritized + PathUnionPrune.Source: §5.2 · p. 9, Figure 8 · p. 9

5.3 Performance of Ranking Algorithms

• Pruning improves performance across measures by reducing enumeration time or measure-computation time, depending on the measure.Enumeration dominates for count and monocount; measure computation takes longer for distributional measures.Source: §5.3 · p. 9

5.3.1 Top-k Pruning for Anti-monotonic Measures

• Top-k pruning reduces running time to under 0.5 seconds in all reported cases and can be several hundred times more efficient than full enumeration.Its benefit diminishes as k grows; at very large k, maintaining the list adds overhead and the pruning algorithm approaches or can be slower than non-pruning.Source: Figure 10 · p. 10, Figure 9 · p. 10

5.3.2 ComputingandPruningforDistribution-Based Measures

• Distribution-based measures are not anti-monotonic, so the aggressive pruning for anti-monotonic measures does not apply; the paper instead integrates measure computation with ranking.The local distribution-based position measure illustrates this alternative approach.Source: §5.3.2 · p. 10
• The position computation uses an SQL query to count local-distribution entity pairs whose counts exceed the target pair’s count; that record count gives the explanation’s position.The pattern is encoded in the FROM and WHERE clauses, and the query can be optimized using the current kth explanation’s position.Source: §5.3.2 · p. 10
• Pruning speeds up local distributional measures by 2 times, but global-distribution ranking remains costly even with pruning.The global distribution is estimated from 100 local distributions associated with randomly chosen start entities; combined measures average several times faster than distributional measures alone.Source: §5.3.2 · p. 10, Figure 11 · p. 10

5.4.1 Effectiveness of Interestingness Measures

• Combining size with monocount or local-distribution measures ranked explanations better than any individual measure.The authors describe these as preliminary combinations and leave more detailed study for future work.Source: Table 1 · p. 11, §5.4.1 · p. 11
• For five randomly selected entity pairs, each measure ranked its top-10 explanations; a user rated the randomized, mixed explanations for relevance, and those labels yielded a DCG-style ranking score.Labels were very relevant (2), somewhat relevant (1), or not relevant (0); rank weights were wi = 1/ log2(i + 1), with scores normalized to [0, 100].Source: §5.4.1 · p. 11
• Size, random walk, count, and monocount had similar effectiveness, while the two distribution-based measures statistically outperformed aggregate and structure-based measures.The simplest size measure was slightly better than the other measures in the similar-effectiveness group.Source: §5.4.1 · p. 11
• Distribution-based measures achieved the best effectiveness among individual measures; local distribution performed as well as global distribution and was cheaper to compute.The authors recommend local distribution when a distribution-based measure is desired.Source: §5.4.1 · p. 11

5.4.2 Comparing Path and Non-Path Explanations

• Only 36% of user-judged top-five explanations and 38% of top-ten explanations were paths.The authors conclude that explanations must include non-path patterns.Source: §5.4.2 · p. 11

Relationships between web artifacts

• Prior work connecting search terms or news articles studies web artifacts, whereas REX focuses on entities and uses a knowledge base with aggregate- and distribution-based interestingness measures.The cited studies are and.Source: §6 · p. 11

Database keyword search

• Unlike database keyword-search approaches, REX considers connection structures beyond trees and paths and introduces two families of pattern-level interestingness measures.The cited database literature includes.Source: §6 · p. 11

Graph mining

• Unlike graph-mining methods that return one large connection graph, REX finds and ranks multiple explanations describing different relationship aspects.The graph-mining studies cited are.Source: §6 · p. 12

Frequent graph mining

• REX mines patterns in one large knowledge graph rather than across a transactional database of smaller graphs, and its monocount extends the single-graph pattern-frequency notion in.The cited frequent-subgraph methods are; the passage notes that those prior works do not study distribution-based measures.Source: §6 · p. 12

7. CONCLUSION

• REX formalizes relationship explanations, defines aggregate- and distribution-based ranking measures, and implements scalable algorithms for enumeration and ranking; experiments report efficient discovery of high-quality explanations on real-world data.The conclusion frames the problem as explaining why entity pairs are related, particularly for related-search features.Source: §7 · p. 12