Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of embedding dynamic networks, i.e., providing a node embedding representation for a network that varies with time (a vector representation for each node at each time point). The paper provides a theoretical development showing that an existing method denominated unfolded adjacency spectral embedding (UASE) satisfies desirable stability properties in the embedding across time and across nodes.
main_review: The paper nicely motivates the need for stable embeddings for dynamic networks in the introduction. The example in Section 2 is a good illustration of the main concept, though somewhat naive. In particular, the fact that finding independent embeddings for each time point (right column) leads to embeddings that are not stable across time is quite expected, but I think that it is fine to show this as a motivation. I enjoyed the mathematical exposition in Section 3, which is the bulk of the contribution. The result is shown for a fairly general setting, and the discussion after corollary 5 about implications for specific random graph models is helpful. 

Section 4, on the other hand, is in my view a weak point of the paper. After having established a stability result for UASE, the authors want to show that other methods are not stable. To do this, they start with a high-level somewhat imprecise categorization of the existing methods into three classes, where the distinction between class 1 and 3 is very thin and the authors justify through an example in (9). The authors then give a few examples of how some of the methods in these categories are not stable. Somewhat ambiguous sentences like “seemingly never providing both [types of stability]” are a bit in contrast with the mathematical precision of Section 3.

The experiments in Section 5 are modest but achieve their objective. Since the paper is not proposing a new methodology but rather a theoretical analysis of stability, there is no need for exhaustive experimentation.

All in all, I deem this paper as a nice analytical contribution to a timely problem.
limitations_and_societal_impact: no comment.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper the authors study the problem of graph embedding for a series of time-evolving graphs, under the general Random Dot Product Graph framework. They focus on the UASE strategy, comparing it with omnibus and vanilla ASE of each graph, and they provide empirical and theoretical proofs of its capability to preserve the locations of nodes along time, and also to capture relationships between similar nodes in each embedding.
main_review: As stated by the authors, the originality of the paper is not on the UASE method itself, but in the analysis of its properties and the proofs of the results regarding those stability properties. The related work is correctly cited, including some recent papers, and a couple of very relevant reviews. And the difference between this work and the existing literature is clear.
As far as I understand, the results are new.

The paper is also techically sound. The results on the convergence of the embeddings are in line with previous recent results, and provide important properties. 
The experimental evaluation is correct and convincing. However, I would have liked to see the performance of omnibus and independent ASE for the Lyon dataset, to further show the strenghts of UASE respect to those two.
Also, I think there should be a comparison on the complexity of the three methods. Basically all three are based on a spectral decomposition, but the dimension of the matrices are different (and in the case of independent ASE, there are T decompositions of $n\times n$ matrices).


The paper is very well written. Both the introduction and the motivating example are very didactical and illustrative. There are some very minor undefined concepts, but in general the quality of the presentation is excellent.

I think the results of this paper are important. It provides a very useful (existing) technique, UASE, now with theoretical guarantees of spatial and temporal consistency.

Minor comments:

In Fig1, the "First two dimensions of the embeddings" are shown, for the tree methods. I couldn't find the original dimension of the embedding used for this example (is it 2 originally?)

(very minor) The MRDPG abbreviation is not defined per se. It is written (multilayer RDPG) two lines above the use of MRDPG.
Also, it would be nice to add a sentence saying that the MRDPG is like a RDPG model but for the concatenaton of the adjacency matrices, or something short like that.

limitations_and_societal_impact: There is a line, stating that the case when T grows presents significant computational challenges. I think this should be further stressed.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies the problem of stability of an embedding of a dynamic network. This corresponds to deriving a time varying vectorial representation for each node such that nodes behaving similarly at a given time have similar positions (cross-sectional stability), and a node behaving similarly across different times has a constant position (longitudinal stability). Assuming  a dynamic random geometric graph model, the authors show for this model that (1) the unfolded adjacency spectral embedding (UASE) procedure satisfies the aforementioned stability properties, and (2) other methods such as omnibus or time-averaged spectral embedding lack one form of stability.
main_review: The problem studied is an interesting one since dynamic/multi-layer graph related problems appear in many applications. The main issue I have is that the overall presentation of the paper lacks clarity in general, which makes it quite difficult to follow and understand at many places. I have elaborated on this below. Keeping aside this issue for now, I think the technical results in the paper are interesting. However, I am not completely convinced whether they are strong enough for acceptance. The UASE method is but one of several other (much more robust) methods that exist in the literature for handling dynamic or more generally, multi-layer graphs. Therefore, while it is interesting to mathematically analyze UASE, I am currently inclined to believe that this is insufficient for acceptance.

Further remarks:

1.	When the latent position model is defined, it will be good to explain at that point how the SBM and other standard community models are obtained as special cases. This is presently done much later on pg. 5.

2.	The parameter $d$ determines the length of the vector in the embedding, but it should be explained how one can choose this, and what it intuitively corresponds to. For e.g., in the setting where the graphs are identical copies of each other, does it correspond to the number of communities? 

3.	There needs to be a notations paragraph that outlines the notation used throughout, this will improve the exposition. Moreover, at some places, it will help to specify the dimensions of the underlying quantities. For e.g. in line 10, $\mathbf{Z}_i \in \mathbb{R}^{k \times T} ?$ for $i=1,\dots,n$?

4.	In line 110, what is GRDPG? In the eigendecomposition of f in eq. (2), there needs to be some explanation on how the smoothness of f is related to the eigenvalues, and some examples of f for which $D < \infty$. 

5.	Proposition 1 is particularly difficult to interpret – partially because of unclear notation (what are the sizes of $\mathbf{X}, \mathbf{Y}$ and $\mathbf{\Lambda}$? How are $\mathbf{X}, \mathbf{\Lambda}$ defined?), and partially because no explanation is provided as to why this proposition is useful. 

6.	As a general remark, it will help to divide a section using “\paragraph” with an appropriate heading for each paragraph in order to make the exposition clearer for the reader. 

7.	In eq. (4), it is unclear to me what the parameter $d$ corresponds to intuitively and how we can choose it, this is related to my comment earlier. In line 134, the sparsity factor has a $\sqrt{n}$ in the denominator but shouldn’t this perhaps be $n$ (in light of the error scaling in theorem 2). The statement of theorem 2 should also have the condition on $\rho_n$. It is also not clear to me how the bound depends on $d$. Clearly $d$ can depend on $n$ so it can’t be hidden within big-Oh. For the same reason, it should also be clarified how $\rho_n$ depends on $d$.

8.	It is important to sketch the proof ideas for Theorems 2 and 3 since these are the main results of the paper. Also, in Corollary 5, the first bullet perhaps has a typo since $t’$ should be $t$? In the second bullet, what does “under a sparse regime mean”?

-------------------------------- Post author response ---------------------------

I thank the authors for their detailed response to my comments and for the clarifications regarding certain technical aspects which I hope will be taken into account in the revision. However, I personally do not find the results in the paper to be strong enough in their current form, and so, I will keep my original score of 5. 

limitations_and_societal_impact: Section 6 does discuss potential societal impact, but I couldn’t find a discussion on the limitations of the results in the paper.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper analyses several consistency (stability) properties of the unfolded adjacency embedding (UASE), a spectral embedding method for dynamically evolving graphs. Specifically it is shown that UASE yields cross-sectionally and longitudinally stable embeddings. This is contrasted with other (spectral) embedding methods which generally do not achieve these properties.
main_review: The paper mainly focuses on the analysis of a particular spectral embedding method, UASE, and establishes some important properties of this spectral embedding. The obtained results are overall interesting and appear to have been established in a rigorous way (admittedly I did not check all the fine details).

In my view, the strongest contribution of this paper is a theoretical one (as encapsulated by the provided theorems); the results are not groundbreaking but significant enough, in my opinion, as the proven stability properties are important for application purposes.
My strongest concerns with the paper are with respect to the presentation of the results and the novelty of this work.

In terms of presentations I found the paper to be of very mixed quality. The introduction, the motivating example and the examples read sufficiently well. However, I found the the "main sections" 3 and 4 to be relatively poorly written and difficult to parse.
A few examples:
- "We can associate to the function f a compact, self-adjoint operator" --> how is this done precisely? Are we effectively assuming that we have a graphon like structure here?
- the acronyms GRDPG, RDPG etc are never defined, \Phi is not defined and moreover there is another map \phi appearing before, which may lead to confusion
- the linear maps in Proposition 1, and in particular the dimension d_t are never really explained.

One major point that is not discussed at all is the low-rank assumption on f that is made and its consequences, which seems crucial.
How can this be relaxed? What effects would there be if the assumption is dropped? Would t be sufficient if the eigenvalues are decaying fast enough?

Similarly the assumption on the sparsity of the results would appear to merit more discussion. It appears that the authors consider effectively dense graphs; whereas in most practical applications we would encounter sparse networks.

It would also be of interest to get some insight into how these theoretical results differ from previous results on (low rank network models) in terms of the additional difficulties etc. that are encountered in the proofs. At first glance it seems that the results presented here are reasonably straightforward extensions of results that have been obtain on random dot product graphs etc.

---------------
Update after author response.

As said in my review my strongest concern was with the presentation of some of the results, and the answer provided by the authors appears satisfying to me. I have thus raised my score.

limitations_and_societal_impact: The discussion on the limitations of the methods appear to be very short. In particular the assumption of an underlying low-rank distribution and of the sparsity level are not discussed in sufficient detail in my opinion.
review_title: null

Meta-review: The paper's main contribution is to prove that a specific spectral embedding scheme applied to time-varying graphs, which associates to each node a corresponding time series, ensures in a particular latent position model of random graph two types of stability (cross-sectional and longitudinal). The theory is supplemented by experiments done on a dataset from school in Lyon, France describing student relationships over time. The reviewers generally appreciated the paper's contribution, one review evaluating the results to be slightly below the bar for acceptance. 
In agreement with the reviews, I believe the paper's objective to be of interest and to be successfully achieved by the authors' work. While the results may in retrospect appear natural and somehow not very surprising, I would not hold this against the authors, hence my recommendation to accept. 
Decision: Accept (Poster)