Discrete choice models [49] concern how individuals make choices from a candidate set of alternatives, and have wide applications in many areas, such as recommendation [35], information retrieval [25], economics [31], etc. With the increasing availability of abundant real-world data, more and more often we not only have the record of people's single choice over the candidate set, but also relative rankings of multiple items. Learning discrete choice models from ranking data has thus attracted much research attention [15,24,25]. In this paper, we focus on the problem of learning Multinomial logit (MNL) model, which is one of the most popular discrete choice models and also known as Plackett-Luce model [27,42].
One long-standing technical challenge for learning MNL model from real-world ranking data is that the exact calculation of the MNL likelihood of partial rankings is generally intractable when the number of candidate choices is large. This computational challenge has limited the application of MNL model to some special types of ranking data, such as Top-ranking, where the exact order of the top candidates is required to be known. There are two lines of research that aim to approximate the MNL likelihood of general partial rankings. The rst direction is to use rank breaking [20,21,46], which usually extracts pairwise comparisons from the general partial rankings and treats the pairs as independent observations. To mitigate the information loss in the extraction of pairwise comparisons, Khetan and Oh [21] further proposed generalized rank breaking, which extracts maximal ordered partitions from the general partial rankings to preserve more order information. The second direction is to approximate the likelihood by Markov Chain Monte Carlo (MCMC) sampling [24]. However, both generalized rank breaking and sampling-based methods suffer from an exponential time complexity in terms of the number of candidate choices, which are not suitable for large-scale social network modeling. Recently, Ma et al. [28] demonstrated that the likelihood of Partitioned-Preference rankings, which is a special type of partial rankings but is more general than Top-rankings, can be eciently approximated through a numerical integral approach.
In this paper, our rst contribution is the development of a scalable method for learning MNL from general partial rankings, by combining the idea of generalized rank breaking [21] and the numerial integral approach [28]. We also extend the method to learn the mixture of MNL models by proposing an Expectation-Maximization (EM) algorithm with a novel initialization method to facilitate better convergence. Through simulation study, we demonstrate that the proposed methods are able to achieve signicantly lower computational cost while having similar estimation accuracy compared to state-of-the-art sampling-based baseline methods.
We further demonstrate that the proposed methods are particularly useful on applications to choice-based network formation modeling, which is a new and exciting application domain of the MNL model recently introduced by Overgoor et al. [39]. Concretely, we can view the social network formation process as people making choices of their friends. The formation of each new edge in the network can be viewed as a node choosing to connect another node, over all the candidate nodes available. Most prior choice-based network modeling methods assume the temporal orders of all the edge formation are available and interpret the sequentially established edges as top-rankings [39,40]. However, such assumptions may be unrealistic in practice. On one hand, there are a lot of network data where the temporal formation information is partially missing or even totally unavailable. On the other hand, the temporal information does not necessarily imply the level of preference in the friend choices. Our proposed methods, instead, do not rely on such strong assumptions when being used to learn the MNL models.
We apply the proposed methods to large-scale network formation modeling on both synthetic and real-world networks. We generate synthetic network through mixture of preferential attachment and uniform attachment models. Our empirical results demonstrate that the proposed methods are able to faithfully recover the ground truth parameters of the generative models, while prior choice-based network formation modeling methods fail when the temporal information is missing. Experiments on two real-world networks show that the proposed methods are able to achieve better link predication accuracy than prior baselines, suggesting that the proposed methods are able to achieve a better tness of the data.
Many algorithms have been proposed to learn MNL model from ranking data [1,5,15,21,28,30,36] and its mixture [10,24,34,37,54]. However, few of them is able to learn mixture of MNL models from general partial rankings in a tractable time. Among the existing methods to learn MNL models, some are designed for full rankings [1,54]; some are designed for special cases of partial rankings [15,21,28,30,34,36], e.g., Top-rankings or Partitioned-Preference rankings. But only a few algorithms are proposed to learn MNL models from the most general partial rankings. Moreover, existing methods that can process general partial rankings all suer from the intractable time complexity. Liu et al. [24] proposed an algorithm that samples full rankings from partial rankings to learn the MNL model, but this method is not scalable for large dataset due to its exponential time complexity with respect to the number of items. The algorithm by Khetan and Oh [21] breaks the general partial rankings into maximal-ordered partitions but has to discard a part of hard-to-evaluate data to conne the time complexity. Though the method proposed by Ma et al. [28] is able to learn MNL models in polynomial time, it can handle partitioned preferences at best, which is still not the most general case. Our proposed method combines the algorithms of Khetan and Oh [21] and Ma et al. [28] to tackle this problem using an ecient numerical integral estimation that can be evaluated in polynomial time.
Modeling the formation and growth of network is essential to explore the structure of networks [8,13,16]. Overgoor et al. [39] recently proposed a framework to model the growth of network as discrete choice of incoming and existing nodes. This framework is general enough to include many existing growth patterns, e.g. preferential attachment. Inspired by this framework, a vast number of researches utilize the temporal information of social networks to better understand the dynamics of the networks [23,43,48,51,53]. Many researchers apply this framework in various domains related to networks such as sociology, physics, medical science and etc [9,14,18,19,23,29,38,44,50]. Moreover, many extensions have been made from this framework [3,11,40,48]. In complement of the existing studies, this work applies our proposed MNL learning methods to handle the situations where temporal information of the edge formation is not fully available or where the temporal information does not directly translate to the preference of nodes. In such situations, learning from partial rankings naturally arises.
In this section, we investigate how to eciently learn an MNL model from general partial rankings. We develop a scalable method by combining the ideas from two recent studies [21,28]. We also extend the proposed method to eciently learn a mixture of MNL model with an EM algorithm.
We start by introducing the formal denition of the MNL model, and the intractability problem of estimating the MNL likelihood of general partial rankings.
The MNL model. An MNL model is a popular discrete choice model that characterizes how one makes choices from a group of items. In particular, we assume each individual has an underlying utility score for each of the item, and the observed rankings of the items given by the individuals are noisy version of the utility score order. Now suppose there are # dierent items and denote the set of items, {1, . . . , # }, by b# c. Also denote the set of all possible permutations of b# c as 2 b# c . The MNL model is dened below.
). For an individual with w = [F 1 , . . . , F # ] ) as the underlying utility scores of the # items, under an MNL model, the probability of observing a certain ranking of these items, (8 1 , 8 2 , . . . , 8 # ) 2 2 b# c , is dened as
.
(
Partial rankings. In practice, we often do not observe clear full rankings of the # items. For example, we may know someone's favorite top 5 movies or friends, but rarely their full preferences over all the movies or all the friends. Mathematically, we can represent such partially observed rankings as partially ordered sets (posets). For example, a poset, {(3 2), (3 5), (4 1)}, which is dened on the set of items {1, 2, 3, 4, 5} and indicates that the item 3 is preferred over the item 2 and the item 5; the item 4 is ranked higher than the item 1; but the relative ranking between, e.g., the item 3 and the item 1 is unknown.
There are two well-known properties of posets, which we will utilize in this paper. First, assuming that there is no tied ranking, each poset corresponds to a directed acyclic graph (DAG). See Figure 1 as an example. Second, we can dene extensions and linear extensions of a poset, where the latter can be used to characterize the full rankings that are consistent with a partial ranking.
A poset G 2 is an extension of another poset G 1 if both posets are dened on the same set of items -, and for all elements G, ~2 -, if
additionally a full order of -. And we denote the set of all linear extensions of G 1 on as ⌦(G 1 ; -).
Intractability of the MNL likelihood on partial rankings. Under an MNL model parameterized by utility scores w, the probability of observing a partial ranking G is the total probability of full rankings that are consistent with the observed G, which is given by
For general partial rankings, the number of linear extensions usually grows exponentially with the number of items # . Therefore, the summation over ⌦(G; b# c) in Eq. ( 2) makes the likelihood intractable to calculate. Furthermore, except for a few special types of partial rankings, there is no easy way to simplify Eq. ( 2) into a tractable closed-form formula.
Partitioned-Preference rankings. In Section 3.3, we propose a polynomial-time algorithm that is able to eciently approximate the MNL likelihood of partial rankings for large # . The proposed method is built on top of Ma et al. [28], which proposed a numerical approach for fast calculation of the MNL likelihood of a special type of partial rankings, Partitioned-Preference rankings [22,26,28], as formally dened below.
As a preliminary, we briey review the numerical approach proposed by Ma et al. [28]. At the core of this approach is an alternative formulation of the MNL likelihood of a Partitioned-Preference ranking. It is shown that when the partial ranking takes the form of ( 1 • • • ( " , the likelihood in Eq. ( 2) can be rewritten as
where ' <+1 = [ " ;=<+1 ( ; and F ' <+1 = log Õ 9 2' <+1 exp F 9 . Compared to Eq. ( 2), Eq. ( 3) does not involve the intractable summation over all the linear extensions. While the exact calculation of Eq. ( 3) is still not tractable due to the integrals involved in the formula, these integrals are one-dimensional and can be eciently approximated by numerical integration. Furthermore, the gradients of the likelihood with respect to the utility score w can also be approximated by numerical integration. It is also shown that, to achieve any given numerical precision Y for the likelihood and the gradients, the time complexity of the numerical approach is at most
), which is much more ecient than the exponential complexity if using Eq. (2).
As we have seen at the end of Section 3.1, Partitioned-Preference rankings are a strict subset of partial rankings. Therefore, the numerical approach using Eq. ( 3) cannot be directly applied to approximate the MNL likelihood of more general partial rankings. However, inspired by Ma et al. [28], we can utilize the idea of Generalized Rank Breaking (GRB) [21] to extend the numerical approach to derive a polynomial-time algorithm approximating the MNL likelihood of general partial rankings. Specically, Khetan and Oh [21] demonstrate that, for each general partial ranking, extracting maximal-ordered partitions (which correspond to Partitioned-Pereference rankings) of the corresponding DAG and calculating likelihood of the extracted Partitioned-Preference rankings can be a good proxy of the original likelihood.
Therefore, a natural idea extending the numerical approach [28] to general partial rankings is to rst extract (multiple) Partitioned-Preference rankings from the corresponding DAG, and then use the numerical approach to estimate the likelihood of each Partitioned-Preference ranking.
However, a remaining question is how to calculate the joint likelihood of multiple Partitioned-Preference rankings. Fortunately, we show in the following Proposition 1 that the joint likelihood of multiple Partitioned-Preference rankings can be simply decomposed as the product of individual Partitioned-Preference ranking's. P 1. For two sets of Partitioned-Preference rankings
, where [ " <=1 ( < = ( and [ " 0 <=1 = ) , and (,) ✓ b# c. To ease the notation, we use G ( to denote the partial ranking
We summarize the proposed method for eciently approximating the MNL likelihood of a general partial ranking G in Algorithm 1, which we call it Numerical GRB (NumGRB for short). Model learning. For any model parameterizing the utility scores w, the model parameters can be learned by minimizing the negative log-likelihood through gradient descent methods. The gradients of the likelihood for each Partitioned-Preference ranking can also be eciently calculated through numerical integral. In the rest of this paper, we also call this model learning method as NumGRB. Time complexity of Algorithm 1. The major sub-procedures of Algorithm 1 are (1) nding the strongly connected components (SCCs) of the DAG, (2) extracting the maximal-ordered partition for each SCC by recursively nding the common ancestor algorithm, and (3) calculating the log-likelihood (and its gradients) of each Partitioned-Preference ranking through the numerical approach. Specically, nding the SCCs have time complexity $ (# +⇢), where ⇢ is the number of edges of the DAG. Extracting the Partitioned-Preference rankings overall takes a time complexity of $ (# 3.6 ) [21] (as common ancestors of all the sink nodes of a DAG can be found in time complexity $ (#foot_0.6 ) [5]). Finally, calculating the log-likelihood (and the gradients) using the numerical approach for each SCC has time complexity at most $ (# 3 ). Therefore, the overall time complexity for Algorithm 1 is polynomial-time 2 .
We further extend the proposed method to learn mixture of MNL models, which often leads to better tness of data [55] and is of particular interest for the application to network formation modeling [39,40]. Formally, a mixture of MNL model is dened below. D 4 (M MNL). Given an integer : 1, a mixture of MNL model contains two parts of parameters: 0 = (c 1 , . . . , c : ), where c A 0 for 1 A :, and Õ
1A : c A = 1; (w (1) , . . . ,w (:) ), where w (A ) 2 R # is the parameter of the A -th MNL component. The probability of observing a partial ranking G is dened as % ⇣ G; 0, (w (1) , . . . ,w (:) )
We propose to learn the mixture of MNL with an expectationmaximization (EM) algorithm, where the likelihood of each MNL component is estimated by Algorithm 1. In practice, however, standard EM algorithm with random initialization often converges to bad local optima, which is also observed in the learning of other types of mixture models [17]. As a remedy, we further propose a clustering-based initialization method that greatly stabilizes the convergence of EM.
Clustering-based initialization. It is common to initialize an EM algorithm with clustering methods such as K-means [32]. In our case, however, applying K-means requires us to measure the distance between partial rankings, which is rarely studied. Following the idea that the same item is likely to have similar relative ranks in two dierent rankings if the two ranking are generated from the same MNL component, we propose a novel ranking distance to assist the clustering of ranking data. Formally, we dene the relative rank of an item in a Partitioned-Preference ranking below.
where 1 <(8) " and the <(8)-th partition ( < (8) contains item 8.
Intuitively, A G ( (8) measures the relative rank of an item by the rank of its partition. Then we can dene the ranking distance.
) < 0 , we dene the ranking distance 3 between G ( and G ) as
With the ranking distance dened in Eq. ( 7), we can now use K-means to cluster all the observed partial rankings based on the extracted Partitioned-Preference rankings. To initialize the EM algorithm, we learn a single MNL model on each cluster and then initialize an MNL component with the learned parameters. The full EM algorithm (named NumGRB-EM) is summarized in Algorithm 2. 6 return 0, w (1) , . . . ,w (:) .
In this section, we empirically verify the estimation accuracy and computation cost of the proposed methods through simulation.
We compare the proposed methods, NumGRB for single MNL and NumGRB-EM for mixture of MNL, with a state-of-the-art baseline ELSR-Gibbs [24], which is a sampling-based method that can be applied to learn both single and mixture of MNL. We closely follow the simulation setup by Liu et al. [24] for our experiments. We conduct experiments on synthetic data generated by both single and mixture of MNL.
We treat the the utility scores w of the (mixture of) MNL as free parameters, and respectively apply the proposed methods and ELSR-Gibbs to learn w. We implement the proposed methods with PyTorch [41] and use AdaGrad optimizer [6] with an initial learning rate of 0.5. For the baseline ELSR-Gibbs, we use the ocial implementation 3 released by the authors of Liu et al. [24]. We run Results with varying number of items # . Figure 2 shows the MSE and running time of the proposed NumGRB and the baseline ELSR-Gibbs with # varying from 10 to 100. In terms of MSE, the proposed NumGRB achieves similar estimation accuracy on most congurations of # . The trend that MSE is decreasing with # is due to the artifact that the softmax scores of parameters sum to 1 and larger # implies smaller normalized scores.
In terms of running time, while the proposed NumGRB has a heavier overhead when # is small, the computational cost of ELSR-Gibbs quickly increases and surpasses NumGRB when # becomes larger. It is worth noting that the gure is a log-log plot. The linear curve of NumGRB indicates that it has a polynomialtime complexity, while the curve of ELSR-Gibbs apparently grows faster than linear, as ELSR-Gibbs does not have a polynomial-time guarantee. We are not able to provide experiment comparison for # signicantly larger than 100 because the baseline ELSR-Gibbs suers from numerical errors for large # . In contrast, the proposed NumGRB is still numerically stable for at least # = 1000.
Results with varying number of samples =. Figure 3 shows the MSE and running time of the proposed NumGRB and the baseline ELSR-Gibbs with = varying from 1,000 to 10,000. In terms of MSE, while ELSR-Gibbs appears to have better sample eciency, the dierence is not very large (note the y-axis is now in linear scale to show the dierence). In terms of running time, both methods appear to increase linearly with =, but the computation cost of ELSR-Gibbs increases faster than the proposed NumGRB.
Synthetic data generated by mixture of MNL. Following Liu et al. [24], we generate synthetic data from a 3-mixture of MNL model. We assign equal weights to the 3 mixture components, i.e., c A = 1/3 for A = 1, 2, 3. The conguration for each MNL component is the same as the single MNL described in Section 4.2. When drawing each of the = samples of full rankings, we rst randomly select a mixture component according to c, then draw a full ranking from this MNL component. After we get the = full rankings, we sample partial rankings similarly as for the single MNL.
Results. Figure 4 shows the MSE and running time of the proposed NumGRB-EM and the baseline ELSR-Gibbs with # varying from 10 to 100. We rst note that, as the negative log-likelihood of the mixture model is non-convex, both the proposed NumGRB-EM and the baseline ELSR-Gibbs occasionally converge to bad local optima where some of the mixture components are completely missed by the model. In such a case, the performance is of orders of magnitude worse compared to the performance when all 3 MNL components are recovered. Such bad local optima dominate the average MSE over dierent random trials, making the comparison of average MSE meaningless. For a fair and meaningful comparison, we discard the worst 10 trials among the 50 random trials for each method with each # , in order to make sure trials that do not recover all three components are removed. We also summarize the number of trials that converge to bad local optima for each method. For the baseline ELSR-Gibbs, 82 out of the 500 training (50 random trials on 10 dierent setting of # ) fail to recover all three components. For the proposed NumGRB-EM, only 46 out of the 500 training fail to recover all three components.
In terms of the average MSE, we again observe that the proposed NumGRB-EM achieves similar estimation accuracy as the baseline ELSR-Gibbs on most congurations of # . In terms of the running time, the proposed NumGRB-EM obtains even larger advantage over ELSR-Gibbs, compared to the experiments on single MNL.
We further apply the proposed methods to network formation modeling on both synthetic and real network data.
We rst review the basic discrete-choice-based network formation modeling framework proposed by Overgoor et al. [39]. The central idea is to view the formation of a directed edge from node 8 to node 9 as the process that 8 chooses 9 over a set of alternative nodes, which can then be modeled by a single MNL or a mixture of MNL. One merit of this framework is that it elegantly unies many existing network formation models, such as preferential attachment [2], uniform attachment [4], and latent space model [12]. More importantly, this framework allows one to combine node features with dierent network formation mechanisms into a single model and estimate their relative importance. Next, we review two concrete examples, preferential attachment model and uniform attachment model.
If the formation of new edges in a directed graph follows preferential attachment, the new arriving node connects to an existing node 9 with a probability proportional to a power of their degree 3 9 , i.e.,
where + denotes the candidate set.
If the formation of new edges in a directed graph follows uniform attachment, the new arriving node connects to any existing node 9 in the candidate set + with the same probability, i.e.,
As can be seen in their denitions, the preferential attachment and uniform attachment models can be viewed as MNL models with utility score for 9 being U log 3 9 and 1 respectively. More generally, under the preferential attachment model, the probability for a node sequentially choosing ( 9 1 , 9 2 , . . . , 9 ) to connect can be written as
However, one limitation of most existing methods under this framework [39,40] is that learning the model from an observed network requires the knowledge of full rankings for everyone's all existing edges, which is unrealistic in many real-world scenarios. The proposed methods in this work, NumGRB and NumGRB-EM, can be applied to learn from more general partial rankings of existing edges in a network.
We rst apply the proposed NumGRB-EM on synthetic network data generated by mixture of 4 variants of network formation models. Through our experiments, we demonstrate that (1) the proposed principled method for learning from partial rankings outperforms naive approximation methods; (2) correctly specifying the mixture components not only aects the learning of mixture weights but also improves the model parameter estimation of each mixture component.
Synthetic network data generation. We simulate the growth of a directed network with a synthetic (A, ?)-model following Overgoor et al. [39]. When a new edge is formed, with probability ?, it is formed by uniform attachment, and with probability 1 ?, it is formed by preferential attachment with U = 1. After choosing the attachment pattern, we choose the candidate set + to fully determine the mixture component: with probability A , the candidate set is all nodes in the network that have not been connected by the source node, while with probability 1 A , the candidate set is restricted to the friends-of-friends (FoF) of the source node. Therefore, the synthetic data is generated by a mixture of 4 edge-choice distributions, which we denote as UA (uniform attachment, mixture weight ?A ), PA (preferential attachment, mixture weight (1 ?)A ), UA-FoF (uniform attachment restricted to FoF, mixture weight ? (1 A )), PA-FoF (preferential attachment restricted to FoF, mixture weight (1 ?)(1 A )).
We generate synthetic network data with varying values of (A, ?) pairs. Due to the space limit, the detailed data generation procedure is provided in Appendix A.3.
Experiment setup. The learning task of this experiment is to learn 5 parameters of the mixture model: the mixture weights for the 4 components as well as a shared model parameter U for PA and PA-FoF. And we apply the proposed NumGRB-EM method to learn the parameters from the data.
For the baseline, we note that ELSR-Gibbs is not scalable enough for this experiment setup. We instead implement a naive baseline method (named as Naive) that treats each new edge formation as an independent top-one ranking, such that the calculation of likelihood becomes feasible (but with information lost). For both NumGRB-EM and Naive, we further apply them to learn a 2-mixture (PA and PA-FoF) and a single model (PA only), in order to investigate their performance under mis-specied settings. 1: Estimated model parameters by NumGRB-EM and Naive on the synthetic network data. The results are averaged over 5 random trials and the numbers in brackets indicate the standard error of the mean. The synthetic network data are always generated by 4-mixtures of UA, UA-FoF, PA, and PA-FoF with ground truth U = 1. We generate data with 4 settings for dierent values of A and ?. The columns with heads "4-Mix", "2-Mix", and "Single" refer to the learned models being specied with 4-mixtures, 2-mixtures (PA and PA-FoF), and a single model (PA), respectively. The estimated parameters include the mixture weights for the four components, as well as the parameter U shared by PA and PA-FoF. There are blank entries for "2-Mix" and "Single" as they are not specied.
Results. The experiment results are summarized in Table 1. Comparing NumGRB-EM and Naive, the proposed NumGRB signicantly outperforms Naive in terms of both the estimation of mixture weights and the distribution parameter U in most cases. This veries that a principled method for calculating the likelihood of partial rankings is critical for the model parameter estimation accuracy.
Regarding the specication of the mixture models, we start with the setting A = 1 and ? = 0, which is a special case where the ground truth model is actually a single model following PA. It is not surprising that all models t well in this case because they all contain the PA component. It is worth noting that applying NumGRB-EM to learn 4-mixtures or 2-mixtures is able to faithfully recover the single model case. In more general settings where 0 < A, ? < 1, we can see that, the 4-mixture models trained by the proposed NumGRB-EM method outperform their mis-specied counterparts not only in terms of the mixture weights, but also in terms of the distribution parameter U.
Together, the experiments suggest that both the proposed partial ranking likelihood estimation and the extension to mixture models are helpful for learning choice-based network formation models.
We further apply the proposed method on two real-world network datasets, Flickr [33] and Microsoft Academic Graph 4 , and compare with the method by Overgoor et al. [39]. For both datasets, we closely follow most of the data processing steps by Overgoor et al. [39]. The key dierence between our method for tting the data and Overgoor et al. [39]'s lies in how we interpret the ranking of target nodes given the observed network.
For Flickr, Overgoor et al. [39] use the temporal order of the edge formation in the network to construct the full ranking of the target nodes connected by the source node, with the underlying assumption that earlier formed edges correspond to more preferred target nodes. We think, however, this assumption might be too strong, as it might be hard to tell the relative ranking of two target nodes with edges formed within a small time window. We instead use the temporal window of the edge formation to construct Partitioned-Preference rankings.
For Microsoft Academic Graph, there is even no temporal order available for the formation, as the citation a source node (a new paper) almost formed (at its publication), and therefore the ranking of target nodes (exiting papers) is naturally a Partitioned-Preference ranking with 2 partitions (cited or not cited). Overgoor et al. [39] t the data with the naive method as we described in Section 5.2, which treats each edge as an independent top-one ranking.
For the experiments, we parameterize the utility scores with linear models on node features used by Overgoor et al. [39]. We report both the learned linear coecients and the precision@k metrics for link prediction. Due to space limit, more detailed experiment setups are provided in Appendix A.4.
Graph are provided in Table 2 and Table 3 respectively.
In terms of the precision@k metrics for link prediction, we observe that treating the rankings of target nodes as Partitioned-Preference rankings and train the models with the proposed Num-GRB outperforms the method by Overgoor et al. [39] when there are more features included in the model. The dierence is smaller when there are very few features, which is not surprising as the model is not able to learn sophisticated patterns in these cases.
In terms of the estimated linear coecients, qualitatively the explanations by models trained with both methods have similar trend. Quantitatively, however, some of the estimated coecients by the two methods dier by a large amount. For example, comparing Model #3 and #3* in Table 2, the relative strengths of the 4 The AMiner project [45,47] 1.122 2.264 Precision@1 0.7606 0.7898 0.8238 0.8262 0.7622 0.7898 0.8414 0.8448 Precision@3 0.6215 0.6385 0.6737 0.6756 0.6227 0.6398 0.6796 0.6846 Precision@5 0.5444 0.5573 0.5880 0.5895 0.5464 0.5592 0.5926 0.5948 Table 2: Estimated model parameters and precision@k for link prediction on Flickr. Model #1-4 are trained by the baseline method by Overgoor et al. [39]. Model #1-4* are trained by the proposed NumGRB. For the precision@k metrics, the bold markers denote the best performance and the underline markers denote the better performance between the corresponding baseline and proposed methods. Table 3: Estimated model parameters and precision@k for link prediction on Microsoft Academic Graph. The markers are the same as in Table 2.
coecients between "Has Degree" and "Reciprocal" are very dierent. Researchers facing the results given by Model #3 may interpret that the impact of having zero followers is marginal. However, the results by Model #3* tell a largely dierent story. And the latter is probably a better t of the data (as suggested by the link prediction accuracy).
In practice, we nd it is usually signicantly faster than this worst-case bound.
https://github.com/zhaozb08/MixPL-SPO our experiments on a GeForce RTX 2080 Ti GPU and an Intel(R) Xeon(R) Gold 6230 CPU @ 2.10GHz CPU.We evaluate the estimation accuracy of each method by the mean squared error (MSE) between the learned parameters and ground truth parameters, both normalized with a softmax function. For the mixture of MNL, the average MSE on all components is reported. We also report the running time of each method to evaluate the computation cost.
CONCLUSIONIn this paper, we propose novel methods for fast learning of the MNL model and its mixture from general partial rankings. We verify both the eectiveness and eciency of the proposed methods through simulation studies. We also demonstrate that the proposed methods can be very useful on applications to choice-based network formation modeling, where the formation of edges is viewed as discrete choices from (mixture of) MNL models. Through experiments on both synthetic networks and real-world networks, we show that ecient learning (mixture of) MNL models from partial rankings is necessary for proper estimation of the model parameters, which are critical for downstream network analysis tasks in scientic research.
A few nodes may form less than 5 edges when their candidate set is FoF and the size of the candidate set is less than 5.