  Entity-Relationship (E-R) Search is a complex case of Entity Search where the
goal is to search for multiple unknown entities and relationships connecting
them. We assume that a E-R query can be decomposed as a sequence of sub-queries
each containing keywords related to a specific entity or relationship. We adopt
a probabilistic formulation of the E-R search problem. When creating specific
representations for entities (e.g. context terms) and for pairs of entities
(i.e. relationships) it is possible to create a graph of probabilistic
dependencies between sub-queries and entity plus relationship representations.
To the best of our knowledge this represents the first probabilistic model of
E-R search. We propose and develop a novel supervised Early Fusion-based model
for E-R search, the Entity-Relationship Dependence Model (ERDM). It uses Markov
Random Field to model term dependencies of E-R sub-queries and
entity/relationship documents. We performed experiments with more than 800M
entities and relationships extractions from ClueWeb-09-B with FACC1 entity
linking. We obtained promising results using 3 different query collections
comprising 469 E-R queries, with results showing that it is possible to perform
E-R search without using fix and pre-defined entity and relationship types,
enabling a wide range of queries to be addressed.
