diff options
Diffstat (limited to 'nips-2016-471.txt')
| -rw-r--r-- | nips-2016-471.txt | 46 |
1 files changed, 46 insertions, 0 deletions
diff --git a/nips-2016-471.txt b/nips-2016-471.txt new file mode 100644 index 0000000..938ccb2 --- /dev/null +++ b/nips-2016-471.txt @@ -0,0 +1,46 @@ +Summary +======= + +In this paper, the authors study the standard influence maximization problem: +assuming the independent cascade model (a random diffusion process in graphs), +the goal is to select a seed set of k nodes. While the traditional influence +maximization problem focuses on the maximizing the expected "cascade size" +(i.e. number of "infected" vertices at the end of the random process), the +authors note that this is not always desirable in risk-averse settings. The +contributions are: + +* formulating a maximization problem where the objective function is the CVar +(conditional value at risk) risk measure + +* providing a "multiplicative weight update" algorithm to solve the problem. +the algorithm is proved to find a solution within an additive 1/e approximation +of the optimal solution + +* comparing their algorithm experimentally with the standard greedy algorithm +which maximizes the expected cascade size. + +Comments +======== + +The problem is very interesting: a lot of effort has been put into maximizing +expected cascade size in the influence maximization problem, but little is +known as far as "worst case" or "risk measures" are concerned, and I think +there is a lot of value in obtaining these more nuanced results. + +The experiments show very well that the resulting cascade size distribution is +very different when maximizing the Cvar metric as opposed to maximizing +expected size. It is also clear that the distribution obtained when maximizing +CVAR is more desirable in settings where risk needs to be mitigated. + +The algorithm is interesting: the ideas are intuitive and standard (sampling ++ multiplicative updates) but to the best of my knowledge are not traditionally +used in the context of influence maximization. + +My only concern is about the specific choice of objective function: I feel that +the CVAR metric is not very well motivated. Are there any ways to relate it to +the one used in [5] or [20] which seem more intuitive and easier to interpret? +The interpretability is made even harder by not choosing a single seed set +(fixed strategy) but choosing a distribution over seed sets (random strategy) +and maximizing the CVAR of this random strategy. Also, it would be interesting +to know more about the properties of the CVAR objective function: is it +convex/concave in the choice of the random strategy? |