SCALING CHOICE MODELS TO RELATIONAL SOCIAL NETWORK DATA THROUGH SAMPLING OF ALTERNATIVES

Many prediction problems on social networks, including anomaly detection and recommendations,
can be framed as modeling a sequence of relational events, and leveraging that model for prediction.
Discrete choice models have recently been advanced as a natural approach to modeling relational
events as “choices”, a framework that envelops and extends many long-studied models of network
formation. However, choices in social networks typically tend to concentrate in an individual’s social
neighborhood, which often is a small subset of the network. Meanwhile, efficient inference for choice
models becomes very difficult when features are rare within the population (if encoding “is a friend
of a friend” as a feature) or when using mixture models (which can restrict one or more modes of
the mixture to friends or friends-of-friends).
In this work, we identify two avenues for scaling choice models to overcome these challenges. Pri-
marily, we study the use of importance sampling—a standard technique for approximate inference—
and find it can greatly speed up the inference of conditional logit models of network choice. Addi-
tionally, we introduce a model simplification technique for mixture models that we call “de-mixing”,
whereby standard mixture models of network formation are reformulated to operate their modes over
disjoint choice sets. This reformulation reduces mixed logit models to conditional logit models, cir-
cumventing standard challenges with maximizing the likelihoods of mixture models and opening the
door to straight-forward importance sampling. We illustrate the relative gains of the two improve-
ments on synthetic datasets with known ground truth behavior as well as on a large-scale dataset
of public transactions on the Venmo platform. We find that non-uniform importance sampling is
especially effective for rare features that commonly drive network formation. Model de-mixing,
meanwhile, makes it possible to efficiently estimate conditional logit models that reliably approxi-
mate otherwise challenging mixture models.

Supaniratisai, Pakapol and Ugander, Johan and Overgoor, Jan. (2019). SCALING CHOICE MODELS TO RELATIONAL SOCIAL
NETWORK DATA THROUGH SAMPLING OF ALTERNATIVES. Stanford Digital Repository. Available at: https://purl.stanford.edu/vz502vg2815