- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper studies a model for temporal graphs where edges switches on and off according to a -state continuous time Markov process with unknown parameters. Each edge's rate to being on or off depends on parameters set by the two nodes that it connects, and an affinity parameter that is controlled by a parameterised family of time-dependent affinity functions, like polynomials or Fourier functions. The model knows the affinity functions and chooses times to observe the graph, and aims to reconstruct parameters from these observations. The authors propose an algorithm that chooses observation times and adapts to new updates. Their theoretical results mainly focus on why observation time matters and asymptotic information rates from informative observation times, along with examples where information is insufficient from badly chosen observation times. The authors empirically test the algorithm against adapted versions of existing algorithms on synthetic data with polynomial and Fourier affinity functions. I recommend a weak reject to this paper. This paper did produce enormous amounts of analytical and experimental work to the specific theoretical question, but there are no concrete theoretical sample complexity guarentees of the suggested algorithm, and the experiments doesn't necessarily support the algorithm's efficiency claims, where the proposed observation strategy improves parameter estimation at the slowest switching scale but performs marginally better against existing methods otherwise.
Critical strengths
The paper identifies a specific difficult graph recovery problem, identifies the difficulty in recovering switching speeds and provides sharp information rates for the updating pattern of the problem.
The paper provides sufficient conditions for observation times where there is non-vanishing information about the graph and parameters.
The paper identifies the asymptotic information rate for the parameters under the graph updating pattern, establishes where these rates hold and shows counterintuitive cases where observation times can affect the information rates directly.
The paper provides significant synthetic experimental evidence to compare the algorithm with adapted existing algorithms to support the performance of the algorithm, and shows some cases where variants of the algorithm does well.
Critical weaknesses
The theoretical analysis does not provide sufficient evidence for the significance of the proposed method. Theorem characterizes local fisher information, but does not establish overall error rate. Later applications of the theorem only derives information rate regimes for certain affinity families.
An established estimator guarantee and showing the information separation result broadly would directly address this concern.
The problem itself is not well motivated and the presentation misses the problem's relevance to existing literature. The relationship between this model and common temporal graph models in literature and the specific difficulty that this model has needs to be well evidenced and compared thoroughly with existing literature, as well as how resolving this problem can help resolve related problems.
Providing more background or a related works section alongside comparisons to existing literature would directly address this concern. This would be nice to have for both the problem, the algorithm and the theoretical guarantee.
The empirical experiment does not establish a clear advantage of the proposed algorithm. While the experiments show advantage in some settings, it seems much of the gains come from regularization, and the algorithm only shows clear improvement in the slowest tested switching scales.
clarifying the conclusions supported by existing evidence and provide evidence that isolate the scheduling contribution and show its significance would directly address this concern
Minor concerns that did not affect my score:
The setting is underexplained at section , for example theta is not defined in section when the paper uses it immediately in section . Or certain notation are not explained, being one row of was never explained.
Theorem 's results are not well explained, it is unclear what "information in a direction" means, or introducing "nuisance" without defining it.
Section begins by introducing the construction without explaining what it's meant to show.
More unexplained terms like "weighted scenarios" and "candidate pool" makes the paper difficult to follow.
Algorithm would be easier to follow if steps 5 and 7, updating and , were explicitly referenced to the formulas they are following for the update. I was intuitively unclear of how we are updating it.
Questions for authors
1, What motivated this problem? Is there a concrete application or existing learning problem that leads naturally to these assumptions?
2, How exactly are Step-DAD, Inside-Out , and PASOA adapted to this setting? Which parts of the original methods are retained, and what objectives do the adapted methods optimize?
3, Why were polynomial and Fourier affinity families chosen?
4, What explains why the scheduling improvements are concentrated at the slowest tested switching scale? When should we expect adaptation to improve over a fixed anchor–probe schedule?