Review 28833:
C3, C4, E3, E4 will be changed as suggested. Network size means number of nodes in the whole network.

C1: N is the network size. It is the input, not a parameter. Number of dyads to track is k, a parameter in the algorithm. We sample and track dyads in stead of nodes.
The number of dyads to track, k, is indeed related to network size, N. However, in the experiments we conduct (Table 3, network size no greater than 50k nodes), to sample and track 250 dyads is sufficient and works pretty well. We will add a link to our technical report in which sample size selection is discussed. Can't add more details due to 1500 char limit.

C2: In many cases (UN session, US Congress, etc.), there are natural window sizes (each session is yearly, each Congress is biennial). For the synthetic network, size selection is a trade-off between bias and variance. Currently we choose window size heuristically, and we believe the temporal dependency \alpha (Eq 6) can provide information on window size determination, which is left as future work for now.
C2.2: The dyads are sampled uniformly at random. There is no trick in implementation. We can provide the code when necessary.

E1: This question is related to C1. 1.2G is a combinatorial number: a network with 50k nodes have nchoosek(50k,2) dyads, which equal to 1,249,975,000, and hence 1.2G. Our technical report has more details.

E2: See the 2nd paragraph of Sect 5.1 and the 2nd column of Table 3. Our report has more details.






We thank the reviewer for the insightful comments.
P1: We will clean up the presentation by introducing a table containing explanation of all symbols.
C1: We would like to clarify that N is the number of nodes in the network. The total number of possible dyads hence is (N choose 2). From that we sample k dyads to do the change point detection. This results in an estimator_variance-computational_cost tradeoff.  We have additional experiments showing the impact of this tradeoff that we can include.
 
C2.1: In many cases (UN session, US Congress, etc.), there are natural window sizes (each session is yearly, each Congress is biennial). Currently we choose the dyad count and window size parameters through experimentation and the estimator's variance analysis. We will detail this in the final version of the paper.
C2.2: The dyads are sampled uniformly at random.
E1: Please see C1.
C3,C4,E2,E3,E4: We will address these issues.



We thank the reviewer for the insightful comments.
1: MLE is a natural estimator when one has the likelihood function and the fact that it did not work well was surprising and potentially insightful at least in our mind.  Negative results are often excluded from research papers but we chose to include it for the sake of completeness.
2: We do have additional experiments (varying number of dyads to sample, varying window size etc.) that we could not add due to space constraints.  We will add them in the extended version we plan to put on archived repository.
3: We will correct the formatting problem.


We thank the reviewer for the insightful comments.
1: We will clean up section 4 with more explanations and a table describing all the symbols we used.
2: We do have additional experiments (varying number of dyads to sample, varying window size etc.)  that we could not add due to space constraints.  We will add them in the extended version we plan to put on an archived repository.
3: We can certainly add references to works that explain the latent generation process for evolving graphs.
