Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper provide a method for high-order structure prediction problem. Specifically, the paper first defines a high-order structure on graphs named graph simplicial complex (GSC). Then the paper introduces a feature generation method used for the high-order structures. The features are also used in the proposed method for high-order structure prediction. The proposed method is based on a nonparametric kernel which carries the feature similarities of high-order structures. With this kernel the method uses a Bernoulli distribution for the prediction of the existence of the high-order structure in unseen times. 

In my opinion, the paper has the following strengths and weaknesses. 

For strengths, first, the kernel estimator based method does not require learning process and shows good efficiency in the prediction tasks. The kernel estimator also plays an important role in capturing the high-order interactions in the evolving graphs. Second, the paper provides with theoretical analysis on the consistency and asymptotic normality of the proposed kernel estimator. The theories show possibility of inferring the estimation error and the confidence intervals for predictions. 

For weaknesses, first, the paper ought to make further clarification on the essential differences (and maybe even better, the advantages) between the defined GSC with the traditional high-order structures, such as simplex, hyperedges, or just small graphs. Also experimentally the paper should show more of the advantages of using GSCs. For example, the experiment only use d=1 and 2. Perhaps the experiment should show its advantage when dealing with much higher-order structure predictions rather than these simple cases. Second, the presentation of the paper needs further polish. The paper defines notations on-the-fly, and it makes the readers not easy to follow. For example, if we only look at the notations related to G, there are G_t, G_{-}^{(d)}, G_{t,p}, G'_t(), G_t(d), G_{t-}^{(d)}, and they are defined here and there in Section 3. The readers will need to make their own notation table just to follow the paper. I personally failed at looking for the definition of G_{t-}^{(d)}. In Definition 3, it looks like it is a vertex set, but in the time complexity analysis it becomes a number.  Also, in the time complexity analysis, does the complexity of counting number of simplices of each d need to be considered? Third, for the experiments, the paper should consider using more dynamic methods of link prediction especially when you are only comparing the results of prediction lower-order structures. In Table 1, what is the runtime for baselines, training or making predictions? Overall the experiments need to be more concrete. Last but not least, this paper might not be a good fit for ICLR community since it does not focus on the representation learning methods. 
review_title: The paper develops a nonparametric kernel estimator based method for high-order structure prediction in evolving graphs.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This paper presents an estimator that predict higher-order structure in time-varying graphs. The authors present an kernel-based estimator, prove that it is consistent when the indicator variable for whether a particular (d+1)-dimensional simplex is Bernoulli distributed with a function g. The authors prove that their estimator is asymptotically normal.  The authors also present some experiments on real-world data

Some comments and questions:

1. A concrete example that motivates this problem would be useful in the introduction. As someone who hadn't encountered this problem previously I found it hard to keep a motivational example in my mind while reading this paper.

2. In equation 7, should it be |\tilde{g}_T -g|, that is, is the absolute value missing? Otherwise, I dont see why \tilde{g}_T - g represents the error here. Relatedly it would be nice if the authors provide some intuition behind why the two terms in the equation correspond to the variance and bias respectively.

3. It would be nice if the authors could give an example of a scenario where the process is alpha-mixing.

4. Proposition 1 makes a reference to Theorem 3 (which is deep within the appendix), mentioning this in the proposition statement would be nice. 

5. The statement of Theorem 2 conditions of S_C which is undefined. 
review_title: Presents an estimator for higher-order structure prediction in graphs and provide asymptotic guarantees for it.

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary:

-	The paper goes beyond the task of link prediction between vertices, but focuses on predicting formation of higher-order structures, which involves multiple vertices simultaneously. For instance, given that authors A, B and C have a paper together, task of inferring authors A, B, C having another paper with a fourth author D is an example of higher-order relationship. 

-	More specifically, authors propose a kernel estimator which predicts the evolution of the graph through simplices and how they evolve with respect to some local neighborhoods. Their estimator considers how the graph, subsequently the simplices, have evolved within some window of history. The inference process is somewhat guided by a scoring mechanism that takes into account the past interactions between vertices.

-	The paper proves consistency of the estimator, meaning that the estimator converges to the true function in probability. Additionally, they prove asymptotic normality (in the sense of Central Limit Theorem) of the estimator. 

-	The authors present numerical performance of their method against various other methods based on 4 dynamic graph datasets.

Strengths:

-	For the problem of predicting higher-order (incremental) structures in an evolving graph, authors propose a method which predicts formation of higher order simplices from existing ones, while capturing substructures between vertices of the simplices. They back their intuitions up by proving theoretical guarantees for the consistency and asymptotic normality of their estimator, which implies favorable statistical properties.
-	Authors explain the differences and similarities between existing inference strategies clearly, enabling the reader to understand for which task the proposed method is specialized. 
-	Experimentally, authors argue that their method shows superior performance against various different methods, such as hyperedge-based higher-order prediction algorithms as well as heuristic, random walk and deep learning-based methods. For the task of predicting d+1-simplices from existing d-simplices, the method shows superior performance in most of the settings.

Weaknesses:

-	Section 4, which is a critical part of the paper as it presents the theoretical guarantees with respect to the proposed estimator, is rather complicated and lacks explanations of theorems, definitions and assumptions. In my opinion, this section requires further elaborations as to give some intuition. For instance, what the implications of consistency of the estimator are in practice and why $\alpha$-mixing property is necessary could be explained further.
-	It is important to distinguish between the settings for which the proposed method and the existing work are designed for. None of the existing methods were designed to predict higher-order simplices from existing lower-order simplices. Hyperedge-based methods predict interaction of a group of nodes, while Benson et. al. predict closed simplices from open simplices. Link prediction methods focus on single edge evolutions. These tasks are not aligned with each other and prior work is not designed for the experimental setup proposed in the paper. I believe the experiment does not reflect the whole potential of other methods and is biased towards the current method, but conveys the message that proposed algorithm has superior performance for the particular task in question.
-	Using history of the evolving graph requires additional storage load, which is not discussed in details. It is argued that the proposed method has comparable/improved run-time performance, but space complexity is also very crucial, especially when graphs have growing number of edges and many vertices. In my opinion, this is an important ground of comparison which should be presented with more details.

Additional Comments/Questions:

-	Why would you give higher score when two vertices co-occur in a higher dimensional simplex in the past?
-	 How would you compare storage requirements of your approach to existing higher-order prediction algorithms as in Benson et. al. 2018 or hypergraph-based approaches?
-	Definition of sub-complex includes $B_{t,k}$ but the value of $k$ is not specified. Do you pick a single, fixed $k$ across all definition? This is not properly defined and creates a confusion.
-	Section “4.1 Consistency” has a confusing presentation of definitions and concepts. Definition of $S_C$ is not clearly presented and I believe bias/variance terms for the estimator may need further intuitions and explanations.
-	I couldn’t see any insight for how information is encoded by the proposed method. Specifically, how are simplices (closed simplices) inferred from the dataset? How are open and closed simplices are distinguished from the raw data?

Score:

I vote for accepting the paper, but my decision is borderline. I haven’t checked the proofs in details but I appreciate the analytical effort that was put into this paper. Having consistency and asymptotic normality results strengthens the claims for the proposed estimator. However, I am not totally sure in which real-world tasks this method has significant advantages and would outperform existing methods because the experimental setting is designed for the task of inferring (d+1)-simplices from d-simplices. I am open for further discussion with the authors regarding my concerns and their future comments/responses. 

review_title: Reviewer #3

Meta-review: This paper proposes a method for predicting higher-order structure in time-varying graphs. The paper was reviewed by three expert reviewers, and while they expressed appreciation for the sensible solution, they have remaining concerns about the novel contributions and comparisons (analytical and empirical) with previous approaches. Also, the paper would be clearer if examples are used to illustrate the important points of the paper. The authors are encouraged to continue research, taking into consideration the detailed comments provided by the reviewers.
Decision: Reject