Selecting Walk Schemes for Database Embedding
Yuval Lev Lubarsky Jan Tönshoff Martin Grohe Benny Kimelfeld
Machinery for data analysis often requires a numeric representation of the
input. Towards that, a common practice is to embed components of structured
data into a high-dimensional vector space. We study the embedding of the tuples
of a relational database, where existing techniques are often based on
optimization tasks over a collection of random walks from the database. The
focus of this paper is on the recent FoRWaRD algorithm that is designed for
dynamic databases, where walks are sampled by following foreign keys between
tuples. Importantly, different walks have different schemas, or "walk schemes",
that are derived by listing the relations and attributes along the walk. Also
importantly, different walk schemes describe relationships of different natures
in the database. We show that by focusing on a few informative walk schemes, we
can obtain tuple embedding significantly faster, while retaining the quality.
We define the problem of scheme selection for tuple embedding, devise several
approaches and strategies for scheme selection, and conduct a thorough
empirical study of the performance over a collection of downstream tasks. Our
results confirm that with effective strategies for scheme selection, we can
obtain high-quality embeddings considerably (e.g., three times) faster,
preserve the extensibility to newly inserted tuples, and even achieve an
increase in the precision of some tasks.