Problem
Lyft has data on who rides, who drives, where and when. A driver's location history alone needs a histogram of more than 9,000 geohash cells (Geohash-6, Gh6) for the San Francisco Bay Area, mostly zeros. Simple time features such as hour of day or hour of week do not show which hours behave alike. Trained graph embeddings can capture patterns that such straightforward features miss.
Example from the article: a driver's pickups over several months are summarized by a 32-dimensional vector instead of a 9,000-long histogram, and the vector still shows whether the driver works in San Francisco or the East Bay.
Solution in brief
Draw riders, drivers, locations and time slots as nodes of a graph, with an edge for each ride relation. Train low-dimensional vectors per node so that the dot product of two vectors is high for connected nodes. Feed these vectors to models as compact features.
Questions this case answers
- How to compress a long, sparse history of interactions between entities and places into a short dense vector usable as a model feature
- How to learn a shared vector space for different entity types so that similarity between them reflects how often they interact
- How to describe a driver's or rider's whole ride history by locations in a compact vector that a model can use as input?
- How to represent hour of the week so that a model sees weekday commute hours and weekend evening hours as different groups?
Tools and methods
- Graph embeddings — encoder maps each node to a d-dimensional vector, similarity function ties vectors to graph edges.
- PyTorch BigGraph — the training package that Lyft's algorithm extends.
- Negative sampling — random unconnected nodes serve as negative examples next to real edges.
- Dot-product similarity — compares any two embeddings, even of different entity types.
- Adagrad — optimizer that minimizes the loss.
Google or a one-time email code. No password.