blob: 40f4513c21bc07ea977ffd39c51cf1a3a7f1e3a4 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
Summary
=======
This paper studies the problem of network inference problem for the RDS
(Respondent Driven Sampling) diffusion process. This random diffusion process
models a standard procedure used in epidemiology studies. Under this model, the
authors formulate the network reconstruction process (finding the unknown graph
over which the diffusion took place) as a MAP (maximum a posteriori)
optimization problem. The contributions are:
* showing that the objective function is log-submodular
* giving a "variational inference" algorithm: the objective function is
approximated by linear lower and upper bounds and solving for those upper and
lower bounds provides an approximate solution to the problem
* experiments showing the validity of the approach
Comments
========
The problem of network reconstruction is important and hadn't been studied from
this perspective in the context of Respondent Driven Sampling. While the
experiments show that the suggested approach works well in practice, I find the
paper to be lacking a conceptual/technical contribution:
* it was already shown that the log likelihood was submodular in [8] for the
closely related continuous-time independent cascade model. Even though the
diffusion process here is slightly different, this result can hardly be
considered novel.
* the suggested approach (approximating the objective function with linear
lower and upper bounds) was alread suggested in [5], including the specific
choice of the lower and upper additive approximations
* the formulas from [5] are barely instantiated to the specific objective
function at hand here. It could have been interesting to show how the general
framework of [5] leads to a simple algorithm for this specific problem, but no
algorithm is provided and very little is said about how the computation should
be performed in practice. For example the paragraph starting at line 252 is
very vague.
* no theoretical guarantees are provided for the approximation obtained by the
suggested approach. Some guarantees were obtained in [5] under a curvature
assumption. It could have been interesting to show which form these assumptions
take in this specific context.
|
