From 124e5e7e441956dad1ceb9dc8987808b8f522d62 Mon Sep 17 00:00:00 2001 From: Thibaut Horel Date: Sat, 16 May 2015 17:32:37 +0200 Subject: First set of reviews --- kdd-2015-77.txt | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 kdd-2015-77.txt (limited to 'kdd-2015-77.txt') diff --git a/kdd-2015-77.txt b/kdd-2015-77.txt new file mode 100644 index 0000000..945c623 --- /dev/null +++ b/kdd-2015-77.txt @@ -0,0 +1,60 @@ +1.What is your confidence in rating this paper? + +Medium - knowledgeable on this topic + +2.How would you rate the novelty of the problem solved in this paper? + +A minor variation of some well studied problems + +3.How would you rate the technical ideas and development in this paper? + +The technical development is incremental without fundamental contributions + +4.How would you rate the empirical study conducted in this paper? + +Acceptable, but there is room for improvement + +5.Repeatability: are the data sets used publicly available (and thus the experiments may be repeated by a third party)?( Required, Visible To Authors Only After Decision Notification ) + +Yes + +6.How would you rate the quality of presentation? + +A very well-written paper, a pleasure to read. No obvious flaws. + +7.What is your overall recommendation?\ + +Weak reject. I vote for rejecting it, although would not be upset if it were accepted. + +8.Should the Best Paper Committee consider this paper for an award? + +No + +9.List up to 3 particular strengths of the paper. If none, just say "none". + +* nice Bayesian approach to learn the weights by updating a Beta distribution after each observation +* interesting approach to improve the running time of online influence maximization by reusing samples across time steps + +10.List up to 3 particular weaknesses of this paper. If none, just say "none". + +* it is assumed that it is known which edges were active or dead during a cascade. I think this is unrealistic. +* two other approaches could have been considered: Thomson sampling and UCB. I find it surprising that the authors did not compare to those. +* it would have been nice to obtain theoretical bounds on the performance (number of influenced nodes) of the algorithms + +11.Detailed comments for the authors; justification of your overall rating. + +This paper studies an online influence maximization problem when the influence probabilities of the independent cascade model are not known. In this problem, an experimenter repeatedly selects a set of nodes to seed and observed the resulting influence cascade. The goal is to maximize the overall number of nodes influenced (the union over all time steps). As more cascades are observed, the experimenter updates her knowledge over the unknown graph parameters, thus facing a standard exploration/exploitation trade-off. + +To the best of my knowledge, this is the first time that the Online Influence Maximization problem is stated exactly in those terms, but the authors fail to mention the Combinatorial Multi-Armed Bandit Framework of Chen et al. which has been applied to influence maximization before. I think something is missing in the statement of the OIM problem: it is not clear what the attained value is compared to. Looking at the experiments, it seems that it is compared (in absolute distance) to the best value attainable using an approximation algorithm with the true value of the parameters. Hence, this is the same criterion as the regret defined by Chen et al and should be defined explicitly. Other criteria could be considered, such as a multiplicative approximation ratio. + +The authors adopt a Bayesian approach to deal with the uncertainty on the graph parameters: the edge weights are modeled using a Beta distribution which is updated as new observations are made. I think this is an interesting approach, however it relies on a very strong (and, in my opinion, unrealistic for practical purposes) assumption: it is assumed that the observer knows which edges were alive or dead during a cascade. This is much stronger than the assumption frequently made in network inference papers where only the time at which nodes became active is observed. + +I found it surprising that the authors did not mention Thomson sampling at all. This is a very common approach when adopting a Bayesian bandit approach. In particular, it seems to me that Thomson sampling addresses precisely the issue mentioned in Section 5.2.1: "When P_i,j is a highly uncertain Beta distribution, any value in [0,1] can be the real influence probability". This will be the case if a sample from the current distribution is used, instead of simply its mean. Similarly, the UCB algorithm is very similar to the Confidence-Bound algorithm suggested by the authors. I think both Thomson sampling and UCB should have been used as baselines in the experiments. + +I appreciated the exposition of section 6 where it is clearly explained how to update the parameters of the Beta distribution when more observations are made. However, I did not understand why alpha could be set to one when trying to find the optimal value of alpha and beta in the maximum likelihood estimation. I also disagree with the statement in 6.3 that the exponential gradient algorithm can be proved to be competitive against the optimal sequence of the theta values. To the best of my knowledge, it is only competitive against the best choice of a *constant* theta. This concerns me because the optimal sequence of theta will intuitively not be constant: theta should decrease as more observations are made. + +Except for the lack of comparison to UCB and Thomson sampling, I found the experiments interesting. In particular, it is nice to see how reusing samples across rounds significantly improves the running time while preserving most of the attained value. + +12.List of typos, grammatical errors and/or concrete suggestions to improve presentation. + +I would have liked to see a formal description of Explore and Exploit used in the epsilon-greedy algorithm. -- cgit v1.2.3-70-g09d2