Higher-order Structure Prediction in Evolving Graph Simplicial Complexes
Authors: Manohar Kaul
Masaaki Imaizumi
Venue:  (2021)
Keywords: Higher-order
graph simplicial complex
link prediction

Abstract: Dynamic graphs are rife with higher-order interactions, such as co-authorship relationships and protein-protein interactions in biological networks, that naturally arise between more than two nodes at once. In spite of the ubiquitous presence of such higher-order interactions, limited attention has been paid to the higher-order counterpart of the popular pairwise link prediction problem. Existing higher-order structure prediction methods are mostly based on heuristic feature extraction procedures, which work well in practice but lack theoretical guarantees. Such heuristics are primarily focused on predicting links in a static snapshot of the graph. Moreover, these heuristic-based methods fail to effectively utilize and benefit from the knowledge of latent substructures already present within the higher-order structures. In this paper, we overcome these obstacles by capturing higher-order interactions succinctly as simplices, model their neighborhood by face-vectors, and develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process (i.e., a sequence of graph snapshots). Our method substantially outperforms several baseline higher-order prediction methods. As a theoretical achievement, we prove the consistency and asymptotic normality in terms of Wasserstein distance of our estimator using Stein's method.

Under review as a conference paper at ICLR 2021
HIGHER-ORDER STRUCTURE PREDICTION IN EVOLV- ING GRAPH SIMPLICIAL COMPLEXES
Anonymous authors
Paper under double-blind review
ABSTRACT
Dynamic graphs are rife with higher-order interactions, such as co-authorship relationships and protein-protein interactions in biological networks, that natu- rally arise between more than two nodes at once. In spite of the ubiquitous presence of such higher-order interactions, limited attention has been paid to the higher-order counterpart of the popular pairwise link prediction problem. Existing higher-order structure prediction methods are mostly based on heuristic feature extraction procedures, which work well in practice but lack theoretical guaran- tees. Such heuristics are primarily focused on predicting links of the graph. Moreover, these heuristic- seuridtic-based methods fail to effectively utilize and benefit from the knowledge of latent substructures already present within the higher-order structures. In this paper, overcome these obstacles by captur- ing higher-order interactions succinctly as simplices, model their neighborhood by face-vectors, and develop a nonparametric kernel estimator for simplices that views the evolving graph from the perspective of a time process (i.e., sequence of graph snapshots). Our method substantially outperforms several baseline higher- order prediction methods. As theoretical achievement, prove the consistency and asymptotic normality in terms of Wasserstein distance of our estimator using Stein's 's method.
static snapshot
INTRODUCTION
Numerous types of networks like social (Liben-Nowell & Kleinberg 2007a). biological (Airoldi jet al. 2006), and chemical reaction networks (Wegscheider 1911) are highly dynamic, as they evolve and grow rapidly via the appearance of new interactions, represented as the introduction of new links/ / edges between the nodes of a network. Identifying the underlying mechanisms by which such networks evolve over time is a fundamental question that is not yet fully understood. Typically, insight into the temporal evolution of networks has been obtained via a classical inferential problem called link prediction, where given snapshot of the network at time t along with its linkage pattem, the task is to assess whether a pair of nodes will be linked at a later time L' > L.
While inferring pairwise links is important problem, it is oftentimes observed that most of the real-world graphs exhibit higher-order group-wise interactions that involve more than two nodes once. Examples illustrating human group behavior involve co-author relationship on a single paper and network of e-mails to multiple recipients. In nature too, one can observe several proteins interacting together in biological network simultaneously.
In spite of their significance, in comparison to single edge inference, relatively fewer works have studied the problem of predicting higher-order group-wise interactions. Benson al. (2018) orig- inally introduced a simplex to model group-wise interactions between nodes in graph. They pro- posed predicting a simplicial closure event, whereby an open simplex (with just pairwise interactions between member vertices) transitions to a closed simplex (where all member vertices participate in (Middle) shows an ex-
the higher-order relationship simultaneously), in the near future. Figure [ ample of such transition from open triangle to a closed one. Recently, several works have proposed modeling higher-orden interactions as hyperedges in hypergraph (Xu et al. 2013] Zhang et al. 20188 Yoon al. 2020 Patil et al.) 2020). Given hyperedge h2 at time t. the inference task is to predict the future arrival of a new hyperedge h,r, which covers a larger set of vertices than h4 and contains all the vertices in hy Figure (Right) illustrates this hyperedge prediction task.

---

Under review as a conference paper at ICLR 2021
Simplex (Our Proposal)
Simplex (Benson al. (2018))
Hypergraph
D
Time
Time f'xtt
Time
Time
Time
Time
Figure 1: [[eft]] Given a 4-node graph, at time I, the 2-simplex [A, B, C] also contains 1-simplices
[A, B), [B, C1 and [A, CJ. At time t' > t. the 2-simplex evolves (by connecting with D) to a 3- simplex [A, B. C, D] which additionally contains I-simplices [A, D). [B, DJ and [C, D), along with 2-simplices [A, B, DI, [A, C, D] and [B, C, D). [Middle] Simplex setting with Benson al. (2018). The method predicts [A, B, C1 (closed triangle) at time t' > t from an open triangle with links/edges [A, B). [B, C1 and [A, C1 time t. [Right] Hypergraph represents a triple [A, B, C1 as a hyperedge, without any of its subsets. It cannot distinguish between [[A, B), [B, CJ, CJ] and [A, C,
Although prediction models based on either simplicial closure event prediction or hyperedge arrival, deal with higher-order structures, they both fail to capture the highly complex and non-linear evo- lution of higher-order structures over time. Both these kinds of models have two major limitations. First, they predict structures from single static snapshor of the graph, thus not viewing the evolu- tion process of adding new edges as a time process. Second, their feature extraction is mostly based on popular heuristics (Adamic & Adar 2003 Brin & Page 2012 Jeh & Widom, 2002 Zhou al., [009a]|Barabal Barabási & Albert 1999; Bhatia et al. 2019) that work well in practice but are not accompa- nied by strong theoretical guarantees. In addition the aforementioned shortcomings. hypergraph based methods model higher-order structures as hyperedges, which omit lower-dimensional sub- structures present within single hyperedge. As a consequence, they cannot distinguish between various substructure relationships. For example. hyperedge [A, B. CJ in Figure [ (Right) cannot distinguish between group relationships like [[A, B), [B, [A, C7] (a set of pairwise interactions) versus [4, B, C) (all A, B and C' simultaneously in a relationship). This problem is remedied by the use of simplices because they naturally model these substructures as a collection of subsets (i.e., faces) of the simplex.
We provide real-world examples of where our simplicial complex based approach can play a signif- icant role. (i) Organic Chemistry: It is quite common to have the same set of elements interacting with each other in different configurations, which result in very different functioning compounds (Ma et al. 2011). Specifically, R-thalidomide and S-thalidomide are two different configurations of thalidomide, where the R-form was meant to help sedate pregmant women, while the S-form unfor- tunately resulted in birth defects. This is famous example in stereo chemistry show the conse- quences of mistaking two extremely close configurations (differing by a single bond) as being the same. Structure prediction avoid such phenomenon in drug synthesis allows chemists achieve much higher yield and avoid wastage of expensive resources. (ii) Gene expression networks: Gene networks have nodes that represent genes and edges connect genes which have similar expression patterns (Zhang& & Horvath |2rvath|2005). Subgraphs called modules are tightly connected genes in such a gene expression network. Genomies research provides evidence that higher-order gene expression relationships (like second and third-order) and their measurements can have very important implica- tions for cancer prognosis. When making structural predictions in these aforementioned examples, our simplicial complex based approach provides much more fine-grained control over competing methods by capturing subtler differences in configurations.
To combat these challenges, our approach views the evolving graph time process under the framework of nonparametric time series prediction, which models the evolution of higher-order structures (as simplices) and their local neighborhoods (spatial dimension) over a moving time win- dow (temporal dimension). Our inference problem is then modeled as predicting the evolution to higher-dimensional simplex at time I' > given simplex at time l. It is important to note that this task is more general and greatly diverges from the task proposed by Benson et al. (2018). Our
We handle the incremental model (edge insertions only) as opposed to the harder fully dynamic model (edge insertions and deletions allowed) for which most previous methods cannot provide theoretical guarantees.
2

---

Under review as a conference paper at ICLR 2021
task requires just single simplex in order to predict digher-dimensional simplex т, whose face subset is Ø, whereas Benson et al. (2018) requires the presence of all constituent a faces in order to predict For example, in [ensso et al. 2018) (also shown in Figure (Middle)) all faces [A, B), [B, CJ and [A, CJ (open triangle) need to be present in order to predict a closed triangle [A, B, C| Contrastingly, in approach, just single face/edge like [4, B] [B, CJ [A,C]. suffices to predict its evolution to [A, B, CJ. Figure (Left) illustrates an additional example of our proposal to predict 3-simplex [A, B, C, D] given only one of its faces [A, B, CJC.
To this effect, we succinctly capture the features characterizing the local neighborhood of a sim- plex as a combination of a face-vector (Björne & Kalai 2006), which is a well-established vector signature in combinatorial topology literature and a novel scoring function function which infers the affinity of sub-simplices based on the strength their past interactions. Based on these features, we de- sign kernel estimator to infer future evolution to higher- dimessooa simplices and prove both the consistency and asymptotic normality of our estimator.
Our contributions: (a) We propose a kernel estimator that predicts higher-order interactions in an evolving network. (b) We prove the consistency and asymptotic normality of our kernel estimator. (c) We evaluate our method on real-world dynamic networks by proposing higher-order link predic- tion baselines and observe significant gains in prediction accuracy in comparison to the baselines.
1.1 RELATED STUDIES
Single link prediction: Most literature that predicts a single edge/link can be broadly classified
as based on: (i) heuristics. (ii) random-walks or (iii) graph neural networks (GNNs). (i) Heuristic methods comprise of Common neighbors, Adamic-adar (Adamic & Adar (2003). PageRank (Brin &
Page 2012). SimRank (Jeh & Widom 2002), resource allocation (Zhou et al. (2009)). preferential
attachment (Barabási & Albert 1999), persistence homology based ranking (Bhatia et al. 2019),
and similarity- basedd methods (Liben- Nowell Kleinberg [2007b; Lü & Zhou (201T). (ii) Random
walk based methods consist of DeepWalk (Perozzi et al. 2014) Vede2 (Grover & Leskovec
2016b) and SpectralWalk (Sharma al., 2020). (iii) Finally, for both link prediction and node
classification tasks, recent works mainly GNN-based methods such VGAE (Kipf & Welling 2016), WYS (Abu-El-Haija et al. 2018). and SEAL (Zhang Chen 2018b).
Higher-order link prediction: Benson et al. 2018) are the first to introduce higher-order link prediction problem where they study the likelihoods of future higher-order group interactions as sim- plicial closure events (explained earlier). Furthermore, there studies using hypergraphs which
also help naturally represent group relations (Xu et al., 2013 Zhang et al.) 2018 Yoon et al. 2020) Patil al. 2020). Especially, represent higher-order relationships, Yoon al. (020)) proposed n-projected graphs. For larger n, i.e., higher-order groups, the enumeration of subsets, and keep- ing track of node co-occurrences quickly becomes infeasible. In comparison to a hypergraph, our graph simplicial complex is closed under taking subsets, which enables us to better encode more information for improved inference.
2 PRELIMINARY: GRAPH SIMPLICIAL COMPLEX (GSC)
We start with a general notion of an abstract sim- plicial complex (ASC), then define simplex us- ing ASCs. We specialize this definition to graphs and define a graph simplicial complex (GSC).
4
5
6
5
[ 10, 77
Definition (Abstract simplicial complex and simplex). An abstract simplicial complex (ASC) a collection A finite non-empty sets, such that if is element of A, then so is every non- empty subset of a. The element a of A is called simplex of A; its dimension is one less than the number of its elements.
11
12
13
15
12
14
15
G--1
Ge
Figure 2: Example of evolution of GSC G. The yellow triangles are 2-simplices. In the k-ball around 1-simplex [9, 10] (in red), a 1-simplex [10,7] is added at time t.
Now, we analyze graphs using the definition of ASCs. Let G (V, F)) be finite graph with
3

---

Under review as a conference paper at ICLR 2021
vertex set V and edge set E. A graph simpicial complex (GSC) G G is an ASC consisting of subsets of V. In particular, G is a collection of subgraphs of G. With graphs, we denote a d- dimensional simplex (or d-simplex) of GSC by ((d) [vo, ",,..., val. Each non-empty subset of ((d) is called a face of o(d),
We define several notions related to GSCs, that are useful for describing the evolution of graphs. Definition 2 (Filtered GSC), For I C IN, a filtered GSC indexed over / is a family (Gt)er of GSCs such that for every S in I. Ge C Gr holds.
Obviously, Gro C -r, .... Gt, is a discrete filtration induced by the arrival times of the simplices: 9r, \ Gr.-, = ot. This depicts a higher-order analogue of an evolving graph (incremental model), which allows attaching new simplices each time-step an existing GSC to build new GSC. A fil- tered GSC Gt.p for the last p discrete time steps is defined as Gr.p = (gr) = =
where Gr 9r-1-
We define notion for dealing with the neighborhood around given simplex (( G. We intro- duce a set of all simplices of dimension d' or less from G, i... g(d) == (ald) E g d d'). f is a vertex set and g0¹ is the set of edges and vertices. We also write ~ j whenever vertices i and adjacent in __ and write ~ j to indicate that vertex j l k-reachable from i.e., there exists a path of length at most k. connecting and j in __ Then, we define ball around (())
Definition (k-ball centered at vertex and simplex). At time I, we define a k-ball centered at vertex i by (1) {j : i ~e and i. _ We also define k-ball centered at a simplex o(d) as B, (d) == Unvert(otn) (i), where Vert(a(dd) denotes all vertexes in ((d)
Now, we define sub-complex ((((()) S Ge as the GSC that contains all the simplices in G spanned by the vertices in the k-ball (o()))
PREDICTING THE ARRIVAL OF HIGHER-ORDER SIMPLICES
We consider the prediction of simplex's 's arrival in the setting described below. Consider filtered GSC Gr.p. At time t, given a d-dimensional simplex ((4) (N0, va], predict the formation of (d + 1)-simplex r(d+1) [vo. [....... Ug ?] with new vertex ह E B, (o(()),.) Here, we restrict to be k-reachable from o (d) In order to find out which simplices and vertices are most likely to appear in (d+1)) at time &
need to design features for o (d) and 7.
3.1 FEATURE DESIGN FOR SIMPLEX
We develop a feature design of simplex associated with the notion of k-balls. The design is organized into two main elements: (i) face-vector with sub-complex, and (ii) a scoring function.
(i) Face vector of sub-complex: We first define a face-vector of a fixed GSC. The face-vector is an important topological invarian the GSC.
Definition (face-vector). A combinatorial statistic of G is the face-vector (or f-vector) as f(g) fo.1.fo..... fd- where fk f& (G) records the number of k-dimensional faces (k)) E G.
We then define the feature of a simplex (d)) at time t, denoted by N((a(d)= = (())(((())) In words, the feature is compactly represented as the face-vector of sub-complex G((a(()). Our face- vector representation of node's neighborhood can be considered as higher-order analogue of the Weisfeiler-Lehmer (WL) kernel [Shrvaashize et al. (2011) on unlabeled graphs, which for each vertex, iteratively aggregates the vertex degrees of its immediate neighbors to compute unique vector of the target vertex that captures the structure of its extended neighborhood.
(ii) Scoring function: The purpose of this function is extract the features of using its proximity to o(d) To this end, we begin by describing affinity between two vertices. Given two vertices
A topological invariant is property that is preserved by homeomorphismss.
4

---

Under review as a conference paper at ICLR 2021
Table 1 Notation table
Basic
G (V,E)
graph with vertex set V and edge set E graph simplicial complex (collection of subgraphs of G)
old) pur... Vill
d-dimensional simplex (d-simplex)
(d-11 [10 Udl 0]
+ 1-simplex for prediction
Gop - 191-p .... ge5
GSCs from the previous p time steps
gld) (old) E 9 d dd)
set of simplices of dimension d' or less
Local simplex
(i, = (j : : Mrk J. i E g (0)
k-ball centered at vertex i k-ball centered at simplex g(d)
Bex(a(()) = UnVert(ocon (2, ((((())
all simplices from 9, spanned by vertices in (
Feature of simplex
JK (x( [(G) = (1-1, So.... Ja.
total number of k-simplices ((6) E
face-vector of G
Ne(ald)) -[((((((()
feature of (d)
s(c,e')
weighted sum of past co-occurrences of u, o' E ((d)
he(old) v) Ei s(U,, 8)
scoring function
Filodd) V) (Ne(oold), (o(o04,0) 2)) feature vector
Pi(a!d),
set of o (()), ū with corresponding feature F
2, vf E _o we denote by s(u, e²) the weighted sum of all past co-occurrences of vertices and v' in ((d), where the weight is from a(d) We then devise a scoring function h(:, :) that assigns an integral score to the possible introduction of a vertex Ü to d-simplex o(d) [vo, "* val as
(o(
(d) 0)
( 0).
1=0
Intuitively, the scoring function describes higher co-occurrence between ((d) and T at time f, indi- cates higher likelihood of forming a (d + 1)-simplex rdd+1) [o(d), ö) together future time 1+ We give higher score to past co-occurrences of vertex pairs in higher dimensional simplices.
Feature vector: Finally, for a given d-simplex (dd) at time f, and possible introduction of new vertex 8 E (o)),, we assign a feature vector
(((a((), 8) (NN.( R)).
We denote the set of all such possible (o(4), T) pairs with their corresponding feature vectors equal to F as (o(a(d) F). Furthermore, among the pairs in Pa(a((), F), we denote by P. (a((), F) those set of pairs with feature vectors equal to F that actually form -(d+ = [a(4), ū at time t, i.e., ((d) appears as face in (d+1) at time 6. Note the distinction that not all d-simplices counted in (o(a FF) end up being promoted to higher (d + 1)-simplices in the next time step. Table provides a list of notations.
3.2 PREDICTION MODEL AND KERNEL ESTIMATOR
For the prediction, we define an indicator variable that displays the appearance new simplex. Given a d-simplex ((d) [vo..... va] E Gr, the arrival at time + (d + 1)-simplex (d++)) [vo, ",, , 8] with a new vertex E (r, is captured by the following variable
[1 if (d) is face of (d-1). otherwise.
(1+1(1(0111)
Prediction model: Our approach for the prediction is model the indicator variable. Namely, we assume that the indicator variable follows the following distribution:
Yes (d-1)) Gt.p
(4)
5

---

Under review as a conference paper at ICLR 2021
where 0 - 9()) < is function of the feature vector Ft(o(())) 8). In words, the indicator vari- able Ye+1 ()(+t)) is Bernoulli distributed with success probability given by function g (FF(( B)), conditioned on having seen the last p states of GSC G.. This model describes that the appearance probabilities for two simplices o; and o are likely be similar, if their feature vector is also similar.
Estimator with Kernels: We utilize kernel method to estimate the success probability of the model (Equation 4 based observed simplices time t. Let Ge(d) be set of d-dimensional simplices at time from St.p- Also, for brevity, let F represent feature Fi(o(d)) Fm)) with some
1, a(d and Um subject to Un E (o, (())) Let || - F']1 denote the Liddittance between two feature vectors, and also define I---ball T(F,6) = {F' |P F'l11 S 6).
We define our kernel function K (-,-) as follows. With two features F' and F", we define it as
K (F,, F' I[F= F + 3I { F'lla 5
(5)
+ ([T(F,8)
where 3
is the bandwidth parameter, and is the indicator function. Given the feature with only integer components, we are interested in only those close by feature vectors that are either exactly the same as I' or lie within an Laaball of radius ó centered on f. This explains the choice of kernel function with discrete indicator variables.
Now, we define our estimator. At time T, we fix ((d) and ú and set F = =F(oldd) ū) our estimator of ((F) in (Equation 4 is written as follows:
Eoj00 ESG(ld) EG( IRLEBr K (F.Fu(o)),, (0) (1o) Fnl)
Gr (F)
(6)
-x- (() (Bv(ld) IineBr K (F
(d) kn)
complexyy of our estimator: As both the face-vectors and counts Pc+1 / P (updated in data cube) computed simultaneously, they incur the same time overhead. At time t, for d- simplex ((d) it takes O(VV& + [Ex)) time to compute a k-ball around o(1), where V/8 and Eg are the set of vertices and edges in the k-hop subgraph of vertex. We must check this k-ball of (()) against pl ( number of simplices (with dimension at most d) from the previous p time steps, by intersecting against them to get counts for the face vector and data cube. Each intersection test takes O(VV& time. Recall that (9i) denoted the total number of d-simplices in G.. V&2 and Eş are the of vertices and edges in the k-hop subgraph of a vertex. We must check this b- of ((d) against ((d) number of simplices (with dimension at most d) from the previous time steps. So, the entire computation across T time chunks has a time complexity of O(T + (E
-topletyyo of our estimator: For single simplex, our estimator requires storing: () pair of integer counts, namely (P)(.-)) dimensional face vector which takes storage O(d + 1). As the total number of simplices is denoted by fa(),, we arrive at a total storage cost of (dda(GG))
). PT ())))) in a datacube, which costs O(1) and (ii) d 1-
4 THEORETICAL PROPERTY OF THE ESTIMATOR
We show that our estimator has theoretical validity: (i) consistency and (ii) asymptotic normality. (i) The consistency guarantees 9r achieves zero error as T' increases by converging to g. (ii) The asymptotic normality implies that the error タT - 9 converges to a normal distribution, which is useful to evaluate the size of the error and can be applied statistical tests and confidence analysis. Both properties are very important in statistics (Van der Vaart 2000).
Asymptotic Normality
Consistency
T
gT
g
GT 9
4.1 CONSISTENCY
We study the consistency of our estimator. To discuss the property of the estimators with GSCs, necessary to organize the Markov property, that the GSC evolution process clearly exhibits. It is

---

Under review as a conference paper at ICLR 2021
well-known that there exists set of irreducible closed communication classes C in the state space S. We denote the time of entering class C by Te and the event as (Tc)). Let Sç denote the event S, C, where S, is the state of the Markov chain at time t. Then, (Tc) n Sc the event that the chain enters class C' at time To and remains in that communication class indefinitely.
With the event Sc, we provide the bias-variance decomposition of 9r 9. which is common for theoretical analysis of estimators. The bias represents an error due to the expressive power of the model and the variance represents the over-fitting error due to algorithm uncertainty. By analyzing these terms separately, we can analyze the overall prediction error. We define two 2j=1 9,(d)) ((iti) .F) and dr (T
functions as (F) = (T p) E p)- Dtp Σ (6(()) (G(ld) 1P=11) (d) P)). For the sake of brevity, we fix F and denote (1) Eihr Scl B(drr Sc Then, by Proposition in the supplementary material, we decompose gr as
by gr- Similarly, g. dor and d, used. Also, define term
hT gdr| - EihT gdr Scl
(F C)Edd Scl +o(1).
ØT g
dr
dr
=:Vr (variance)
=:8, (bias)
To bound the variance term Vr, we make an assumption that our Markov chain X, exhibits a- mixing property which describes a dependent property of the dynamic process. It is one of the most common and well-used assumptions describing time- dene-depnddent processes including dynamic graphs (Sarkar et al. 2014b). Precisely, we present the definition of a-mixing:
Definition (a-mixing). A stochastic process X, is a-mixing, if a coefficient a(r), defined as (rr) sup (IPr(An B) Pr(A))r(B)] A E(X,)), E(X))) 2r
satisfies ((r) events of the stochastic process up to and including t1.
xo. Here, E((X,)) and E(X+)) are the sigma-algebras of past and future
This definition implies that time-dependent processes get close to independent as time passes. That is, events at time f and + 10000 are close to independent, while events at time and t + 1 can be correlated. The simplest example is the evolution of stock prices in financial markets: the movement of stock prices today does not correlate with the movement of stock prices 10 years ago.
To bound the bias term Br, we impose a smoothness condition on g. similar assumption is often used in the problem of predicting links (c.g. Assumption in Sarkar al. (2014a)). Our assumption a general and weaker version of the common assumption.
Assumption (Smoothness on g). There exists function K R + R in the Schwartz space (i.e. it is infinitely differentiable and converging to zero faster than any polynomial as - +00) with parameter > 0 such that [g( (F) g(F') ((n( F'
//b)). F'I(/b)
as 0, VF, F.
We utilize all the assumptions, then prove the consistency of ğr.
Theorem 1 (Consistency). Suppose that the GSC filtration process is a-mixing, 3 = o(1), and Assumption 7 holds. Then, for any F and conditional on Sc, our estimator (F) is well-defined with probability tending to 1, and (F) - gF(F) 3 0 holds as T + 00.
4.2 ASYMPTOTIC NORMALITY
We show the asymptotic normality of the proposed estimator. That is, we prove that the error of the estimator converges weakly to normal distribution. This property allows for more detailed investigations, such as correcting for errors in estimators or performing statistical tests.
Technically speaking, we develop distribution approximation result with Wasserstein distance (ill- lani 2008) and Stein's 's method (Stein et al.) (986) to handle the dependency property of GSCs. We interested in approximating random variable Zn, by Gaussian random variable, where 7,, is a sum n mean-centered random variables (A, ) where A; corresponds to a random variable
(d) in our GSC, which is dependent on other d-simplices which depends the i-th d-simplex a;

---

Under review as a conference paper at ICLR 2021
(d) Here, let dh be the Wasserstein distance be- whose neighborhoods largely overlap with that of o; tween the underlying distributions of the random variables, and N is a standard Gaussian variable. Then, we develop the general results for Zn. We provide the following theoretical result. Its formal statement is Theorem 3, which is deferred to the supplementary material due to its complexity.
Proposition (Gaussian approximation for dependent variables; Simple version of Theorem B). Suppose Zn Ei= A4, where {A:]ī=o is generated by zero-mean random variables Xa. Xi. .x,, satisfying the a-mixxng condition, such A, X,, with B, EI -i= X²). Also, suppose that Pr[[Xi] S L} = 1 holds for = 1,- ,. with some constant L > 0. Then, with
an existing finite constant > 0, we have (w, S E
TL B
- na(n)).
This result extends Sunklodas (2007) in the sense of Markov chains on GSCs that satisfy the a- mixing condition. This extension makes it possible study the contributing effect of neighboring d-simplices (represented as a set of weakly dependent r.v.s) on a central d-simplex.
We provide the asymptotic normality of our estimator. It shows that our estimator converges to a normal distribution in terms of the Wasserstein distance, which leads to weak convergence. To achieve the result, we utilize the decomposed terms VT and Br from ( Then, regard VT as a sum of dependent random variables and apply the result developed in Proposition | Let o² be a limit of variance of the numerator in D as T - oc. We recall that Sc denotes the event S, C, where S, is the state of the Markov chain at time t. Theorem 2 (Asymptotic Normality). Suppose that Assumption 2 holds, the GSC filtration process is c--mixing, and a > O. If 3 = o(2) and b o(T-1/2), then, for any F and conditioned on Se, the following holds: v VT(r - g(F) 4 (O0,0000 (C/C))) as T xo.
By using this property, we can make detailed inferences based on the distribution of the estimation emror. For example, it is possible create confidence intervals for predictions and perform statistical tests to rigorously test hypotheses about simplex arrivals.
5 REAL-WORLD. DATA EXPERIMENTS
We empirically evaluate the performance of our proposed estimator on real-world dynamic graphs compared to baselines. The basic premise in our experiments is to capture local and higher-order properties surrounding d-simplex up to time t to predict the appearance of new (d + 1)-simplex at time t' > which contains ((d) its face. Note that compare method to other closely related methods that were designed to solve different structure prediction tasks.
Datasets: We report results on real-world dynamic graph datasets sourced from Benson et al. 2018)) Each dataset contains n nodes, m formed edges, and x timestamped simplices (represented as a set of nodes). There are four datasets named Enron (n = 143, m 1.8K, 5K), EU (n 998, m = 29.3K, x = 8K), Contact (n = 327, m 5.8K, x = 10K), and NDC (National Drug Code) (n 1.1K, m- 6.2K, x 12K).
Experimental setup: We first ordered by arrival times and grouped the timestamped simplices into T' time slices. For most of our experiments, T was set to 20, except for d = 2, where T was set to 6 and 12 for EU and NDC, respectively. Then, we randomly sampled a set of d-simplices from the time slices in the range [1, T 1]. Those d-simplices paired with vertex that successfully formed a face in a (d + ))-simplex in the T-th time slice were classified as positive samples, while the rest were deemed as negative samples. We picked an equal number of positive and negative samples for evaluation. For K-fold coss-validation for B, we swapped the 7-th time slice with one of the K slices preceding the T-th time slice for each fold. K was set to All experiments where repeated 10 times and average AUC scores and runtimes are reported.
Compared methods: As naive baselines, we averaged the results of single-edge prediction methods, where a new edge would form between each node in the d-simplex and the vertex to be paired with. Specifically, we compare our estimator with: (i) heuristic (Adanic-Adar (AA) (Adamic & Adar 2001). Jaccard Coefficient (JC) (Salton & McGill 1986), and Preferential attachment (PA) (Mitzen- macher 2004), (ii) deep-learning based (Node2vec (NV) (Grover & Leskovec) 2016a), and SEAL
(SL. (Zhang & Chen 2018a)), and (iii) temporal graph network based (TGAT (TT) da Xu et al.
8

---

Under review as a conference paper at ICLR 2021
Table AUC scores and runtimes for baselines versus our method's estimator for d 1 and d
Enron
Contact
NDC
EU
Enron
Contact
NDC
EU
(d =
1) AUC/ / runtime (sec)
(d 2) AUC/ / runtime (sec)
AA
0.54 /8 0.57
10.18 0.30 / 0.38 0.61 00.15
0.31
0.33 /0.20 0.47 0.25
0.228
JC
0.42/0.20
0,63/0.2
0.16 0.37 0.65
0.41/0.16
0.44/0.21 0.23 / 0.24
0.32/0.23
PA
0.55
0.60/0.28
0.55 /0.11
0.38/0.09
0.52/0.15
0.63 /0.20
0.74 0.224
0.34/ 0.118
NV
/
0.25/ 155
0.30/406
0.67 280
0.49/71
0.45 / 155
0.49 3989
0.40/
SL
0.54 152
0.91 / 241
0.33 260
0.57 /431
0.48 152
0.54 241
0.40 / 260
0.29 /31
TT
0.62 / 180
0,80/202
0,42 285
0.61
/420
0.70 180
0.78 / 205
0,45 / 285
0.67 / 422
TN
0.67 2212
/
0,48 / 280
5
0.62
0.70 241
0.46 281
0.64 512
HP
0.26 /226/22 22
0.64 142
0.57 / 54
0.45 / 17
0.26 22
0.76 144
0.45 58
0.41 18
Ours 0.88 / 1.08 0.87 / 7.56 (8=0.1)
0.78 / 5.84 (8=0.1)
0.83 / 1.48 (3=10)
0.94/2.25
0.83 / 2.76 0.96 / 0.76
0.80 / 0.642 (8=10)
(9=1)
(B=0.01)
(3=0.01)
(B=0.01)
2020 and TGN (TN) Rossi al. (2200) link prediction methods. We note that (Benson et al. 2018] for predicting a "simplicial closure" has the closest motivation to our method, yet has diver- gent objectives, therefore omit comparison their work. For hyper-edge prediction (HP), picked the recent most representative work by Yoon et al. (2020) to compare against, although this work only works for static non-evolving hypergraphs.
5.1 RESULTS AND DISCUSSION
We averaged the classification accuracy and runtimes of our estimator and the baselines. We per- formed two sets of experiments on the arrival (d 1--impllx and summarize it in Table 2 for d [1,2}. 2}. We also report the bandwidth 8 for estimator selected by cross-valin vols-valii
Predicting 2-simplex (d = 1): We observe that our method is nearly two orders of magnitude faster than the deep learning based methods (NV and SL) and nearly order of magnitude faster than the hypergraph prediction method (HP). While the single edge heuristic methods are relatively faster, their AUC scores not comparable our method's AUC scores. Also, achieve nearly 30% improvement (in Enron) over the next best performing prediction method.
Predicting 3-simplex (d 2): The gap in AUC scores between our method and the baselines are far more pro- nounced. Our runtimes also improve due the far fewer
number of simplices with dimensions exceeding 3. As observed in Yoon al. (2020) about slight drops in ac- curacy for higher-dimensione hyper-edges, we also note that in HP, the AUC score remains the same or drops slightly compared to prediction at 1.
Enno NDC
0.7
BU
0.8
Predicsed Simplex Dimension
Advantage of higher dimensional simplices: We per- form additional experiments by increasing d from 1 to 8 and show that handling high-dimensional simplices ex- hibits high prediction accuracy. In Figure 3 the predic- tion is basically improves as increases.
Figure 3: AUC score predicted by our estimator for future formation of d- simplex, given d 1-simplex.
Empirical summary: Traditional estimators fail to accurately capture the rich latent information present in higher-order structures (and their sub-structures) that evolve over time. Our estimator succinctly captures this information via the f-vector and weighted scoring (o(d), v) pair formation depending the dimension of the simplex in which the pair co-occur in the past.
6 CONCLUSION
We modeled the higher-order interaction simplex and demonstrated novel kernel estimator to solve the higher-order structure prediction problem. From a theoretical standpoint, we proved the consistency and asymptotic normality of our estimator. We empirically argue that estimator outperforms hypergraph based and higher-order link prediction baselines from both heuristic and deep-learning based pairwise link prediction methods.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-El- Abu-El-Haija, Bryan Perozzi, Rami Al-Rfou, and Alexander A Alemi Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, pp. 9180-99 9180-9190, 2018.
Lada A. Adamic and Eytan Adar. Friends and neighbors the web. SOCIAL NETWORKS, 25: 21 1-20,, 2001.
Lada A Adamic and Eytan Adar. Friends and neighbors on the web. Social networks, 25(3):211-230, 2003.
Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, Eric P. Xing, and Tommi Jaakkola. Mixed membership stochastic block models for relational data with application to ponteinppoteein inter- actions. In In Proceedings of the International Biometrics Society Anmual Meeting, 2006.
Albert-LászIó Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Austin R. Benson, Rediet Abebe, Michael T. Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115 (48):E11221-P)) 1230, 2018. doi: 10. (0.1073/paas118006311111 1800683115.
Sumit Bhatia, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. persistent homology per- spective to the link prediction problem. volume 881 of Studies in Computational Intelligence, pp- 27-39. Springer, 2019.
Anders Björner and Gil Kalai. On f-vectors and homology. Annals of the New York Academy of Sciences, 555:63 80, 12 2006.
Sergey Brin and Lawrence Page. Reprint of: The anatomy of a large-scale hypertextual web search engine. Computer networks, 56(18))3825-3823 2012.
L.H.Y. Chen, L. Goldstein, and Q.M. Shao. Normal Approximation by Stein's 's Method. Springer Verlag, 2010.
da Xu, chuanwei ruan, evren korpeoglu, sushant kumar, and kannan achan. Inductive representation learning on temporal graphs. In International Conference on Learning Representations (ICLR), 2020.
Aditya Grover and Jure Leskovec. Node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '16. pp. 855 355, 2016a.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855 864. ACM, 2016b.
Glen Jeh and Jennifer Widom. Simrank: a measure of structural-context similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 538 543. ACM, 2002.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. NIPS Workshop on Bayesian Deep Learning. 2016.
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 1817)1011-1031, May 2007a. URL httlhtttpp/dxx.d..crrr
10C2/asi.v58:
David Liben-Nowell and Jon Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7):101--0031 2007b.
Linyuan Lü and Tao Zhou. Link prediction in complex networks: A survey. Physica A: statistical mechanics and its applications, 390(6):1 150-11170 15000 2011.
10

---

Under review as a conference paper at ICLR 2021
Shuangge Ma, Michael R Kosorok, Jian Huang, and Ying Dai. Incorporating higher-order repre- sentative features improves prediction in network- based cancer prognosis analysis. BMC medical genomics, 4(1):5, 2011.
M. Mitzenmacher. brief history of generative models for power law and lognormal distributions. Internet Mathematics, 1(2):226-251 251,, 2004.
Prasanna Patil, Govind Sharma, and M. Narasimha Murty, Negative sampling for hyperlink predic- tion in networks. volume 12085 of Lecture Notes in Computer Science, pp. 607-619. Springer, 2020.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning on dynamic graphs. In ICML 2020 Work- shop on Graph Representation Learning. 2020.
Gerard Salton and Michael J. McGill. Introduction to Modern Information Retrieval. McGraw-Hill, Inc., USA, 1986. ISBN 0070544840.
Purnamrita Sarkar, Deepayan Chakrabarti, and Michael Jordan. Nonparametrie link prediction in large scale dynamic networks. Electron. J. Statist., 8(2):2022-2055, 2014a. doi: 10.1214/
14-EJS943.
Purnamrita Sarkar, Deepayan Chakrabarti, Michael Jordan, et al. Nonparametric link prediction in large scale dynamic networks. Electronic Journal of Statistics, 82)):002-2065,, 2014b.
Charu Sharma, Jatin Chauhan, and Manohar Kaul. Learning representations using spectral-biased random walks on graphs, 2020.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M.
Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561, 2011.
C. Stein, JSTOR (Organization), and Institute of Mathematical Statistics. Approximate Computation of Expectations. IMS Lecture Notes. 1986.
Sunklodas. On normal approximation for strongly mixing random variables. Acta Applicandae Mathematicae, 97:251 1600 06 2007.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Rud Wegscheider. Über simultane gleichgewichte und die beziehungen zwischen thermodynamik und reactionskinetik homogener systeme. Monatshefte für Chemie und verwandte Teile anderer Wissenschaften, 32(8):849-906, 1911.
Ye Xu, Dan Rockmore, and Adam M. Kleinbaum. Hyperlink prediction in hypernetworks using latent social features. Johannes Fürnkranz, Fyke Hüllermeier, and Tomoyuki Higuchi (eds.), Discovery Science, pp. 324-339, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
Se-eun Yoon, H. Song, Kijung Shin, and Yi. How much and when do we need higher-order informationin hypergraphs? a case study on hyperedge prediction. Proceedings of The Web Conference 2020, 2020.
Bin Zhang and Steve Horvath. A general framework for weighted gene co-expression network analysis. Statistical applications in genetics and molecular biology, 4(1), 2005.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. arXiv preprint arXiv: vrXivv1802.0940 09991, 2018a.

---

Under review as a conference paper at ICLR 2021
Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018b.
Muhan Zhang, Zhicheng Cui, Shali Jiang, and Yixin Chen. Beyond link prediction: Predicting hyperlinks in adjacency space, 2018.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B, 71 (14):6223-633) 2009a.
Tao Zhou, Linyuan Lü, and Yi-Cheng Zhang. Predicting missing links via local information. The European Physical Journal B: Condensed Matter and Complex Systems, 71(4):623-630, 2009b.
12

---

Under review as a conference paper at ICLR 2021
Supplementary Materials of Higher-order Link Prediction in Dynamic Graph Simplicial Complexes
A EXAMPLE OF SIMPLEX AND RELATED NOTIONS
Example 1. We begin by computing the k-balls centered at 1-simplex [9, 10] Gr and Gr-1, re- spectively.
The k-ball at time / for h: (i.e., 1-hop vertices only) centered [9, 10] is:
(1,, 10)) = B (9) U Br, (10)). This is the union of k-balls at underlying vertices 9 and 10
according to Definition 3
Bt,1 (19, 10]) = Bt,1 ((10)
= =(9, =9,, 8, 5, 6, 10) U (10, 14, 14,, (9, 13,8, 5,6, 14, 15)
Similarly, The k-ball at previous time step t - for k 1 (i.e., 1-hop vertices only) centered at [9, 10] is:
B ( = =B:- B1- (19) U B 1,1
= =99, 13, 8,5, 10) {10, 14, [19, 13, 8, 5, 6, 10, 14, 11,
Notice that there is only a difference of vertex 7 missing from set B B (19, as compared to set Bt,1 (19, 10)) time t.
Now, we calculate the subcomplex spanned by Br, ([,, 10)) Ther
(19, 10)) = [[]) [13]. [8], [5], [6], [10], [14], [11), [15]. [7]. 99, 10), [9, 6]. [9, 5) [9, 8). [9, 13), [10, 6). [10, 7], [10, 11), [10, 15), [10, 14), [10,
(8)
[9,6, 6, 10), [10, 14, 15]}
Now, we compute the compressed f-vector notation of (] 10)) get ((] 10])) = (1. 10, 11, Finally, the neighborhood Nr([9, 10)) = (1, 10, 11,
B FURTHER DETAILS OF THE EXPERIMENT
B. DATASETS
We report results real-world dynamic graph datasets sourced from Benson et. al. Benson et al. (0018). Each dataset is a set of timestamped simplices (represented as set nodes). In each dataset, let n, m, and denote the number of nodes, edges formed, and timestamped simplices, respectively. Enron (n = 143, m = 1.8K, x = 5K) and EU (n = 998, m = 29.3K, x 8K) model email addresses and all recipients of email form simplex in
email networks where nodes the network. Contact (n = 327, m = 5.8K, x 10K) a proximity graph where nodes represent persons and simplex is set of persons in close proximity each other. NDC m = 6.2K, x 12K) is a drug network from the National Drug Code directory, where nodes are class labels and a simplex formed when a of class labels appear together on single drug.
1.1K,
B.2 COMPARED METHODS
Adamic-Adhe Adar Adamic & Adar 2001 and the Jaccard Coefficient Salton & McGill (1986) measure link probability between two nodes based on the closeness their respective feature vectors. Prefer- ential attachment Mitzenmacheri (2044) has received considerable attention model of growth of
all simplices placed line each in increasing order of their dimension
13

---

Under review as a conference paper at ICLR 2021
networks they model future link probability the product of the current number of neighbors of the two nodes. Motivated by resource allocation in transportation networks (much alike the Optimal Transport (OT) problem), Resource allocation index Zhou et al. (2009b) proposes a node tries to transmit a unit resource to node y via common neighbors that play the role of transmitters and sim- ilarity is measured by the amount of the resource y received from Node2vec (Grover& & Leskoved (016aa) and SEAL Zhang & Chen 20)8a) are deep-learning based graph embedding methods that are used in link prediction.
Remark (Difference between our setting and simplical closure). The closest work [Benson et al. (2018) proposed predicting "simplicial closure" event where at time i there exists a set of nodes which are pairwise edge connected and the task is to predict whether at time & + there will arrive simplex which covers all these nodes. This phenomenon was termed as simplicial closure. For example, authors A, B and C' have all co-authored in pairs (i.e., {A, B}, {A, C} and {B,C) C)) and simplicial closure event would take place at + 1, if simplex {A, B, C) arrives, implying that all three authors co-author on a single paper. Our prediction task significantly diverges and aims to solve a different problem. Considering our previous example, we are given single co-authorship relationship between say A and B at time t, we predict whether authors A and B will co-author with third author C (ternary co-authorship relationship) on single paper time + in the future.
C PROOF FOR CONSISTENCY
For preparation, we rewrite the estimator 9r- Plugging in the definition of our kernel (Equation 5 into the equation of our estimator (Equation 6 along with the definitions of P.(.,-) and P7 (.. to replace the indicator variables with actual counts, we obtain the following simplification of Equa- Then, it is reformulated as
tion 6
ØT (F) Ee Eop (1P7L1009)) # -o (Pe+110))) F)I+ 8 E (d) .
+ Ever(no PP P77+ (o, (4)
.)])
(9)
When we set 3 O, look for other pairs whose feature corresponds to F and calculate fraction of how many such close by pairs actually form a (d + 1i-simplex at time + 1. This fraction is summed across various d-simplices 0 by varying j and also across various discrete time steps by varying t'. Setting 3 > 0 allows estimator smooth
close by features.
turns out simpler to study a proxy estimator Tr, which omits the smoothing of the original one. We will show that it is asymptotically equivalent to g. Let (d) denote the total number of d-simplices in GSC Ge at time I. Then, for a feature F, we define the proxy estimator as
(F( = (F)
(10)
dr(F))
where the terms are defined as
T- (d))
(o (d) .F]
T (G.(d)
P F)
1
To((F) = T
and dT = T
(d)
(g(()
Observe that Σ (c(( ranges over the total number of d-simplices in G and note that |9, (d) changes with time step Recall that the terms ( and P.+1(-.)) count all actual and possible
formation of (a|-0) [mm] ((d + 1)-simplex) that have the same feature vector F. Lemma in the
supplementary material proves (TT(F) gr(FF) > as - O. First of all, we show the validity of the proxy estimator Ør.
Lemma (Approximation by proxy). We obtain
Orr (F)) 0
'In practice, the total number of d-simplices is much less than the maximum possible cliques with vertices.
14

---

Under review as a conference paper at ICLR 2021
Proof of Lemmal 7 Recall that ((F,8) denotes the set of features at L1 distance most ó from F. We denote by [I(F,8) 8)1 the cardinality of this set.
Or(F) = hr(F)+ +1
(F) +
where C BEj E,Er(P,))) P (o, finiteness of features in (.+) and Pa-1( (:)),, we have that C₁ = C2 = 0(3). Both C₁ and C2 are non-negative integers. So,
(4) {)] and C2 3 EEi E, P s)]. Due
(P( + (T((F)
Ør (F)
0(8)
(F) +C2 dr(F)
In the last step, the second fraction is positive constant and can thus be ignored from asymptotic analysis because both hr and dr are bounded.
Next, we prove the convergence of the proxy estimator Ør (F). As the first step. we describe the detail of its decomposition in To simplify the notation, we will drop F from all estimator notations.
Proposition 2. As written in Equation
we obtain
01 VT + By.
Furthermore, with the event Sc, there exist a stochastic terms qe for such as
(T (P) tt= 9e
VT
dr
Proof of Proposition
With the definition of (BF C), we have
ht dr
Gr 9
g
(11)
.ur gdr
dr
PTr gdrl
-ETTer gdr |Sc]
-ETT gdr Sc
dr EîT gdr |c]]
fTr -gdrl
Ehr Scl
gbidr Scl
dr
dr
for gdrl
Ebhr gdd |So] Br(F, C)E(dr Scl
dr
dr
VT BT.
(12)
We interested in the asymptotic behavior of the Markov chain time T Fr (a; (d) Um). Recall that the terms IP (: and Pr+1( count all actual and possible forma-
Let F denote
tion of [o( Jmm]] ((d+1)-simplex that result the same feature vector F at time T++ Our Markov chain has finite state space and hence belongs to closed communication class with probability approaching
We provide a statistical consistency conditional on Sc for any communication
class C.
For given time step f, we define
Gr(d))
(r((t)
(d) PP (a) .F)
(13)
(G((d)
15

---

Under review as a conference paper at ICLR 2021
(x(d)
dr((): (Q((d) Σ | F)I
- Note that For _ 7-p 2tpp (1) and dr - Et=p dT))..
Let us set
q: = ( - -0)
(1) Scl
(14)
Note that qe is the numerator of the stochastic term in Equation and bounded deterministic function of Sc at a given time step t.
For the stochastic term dr which appears in the denominator, show its convergence. The follow- ing two lemmas provide the result.
Lemma 2. If the GSC process a-mixing, then, as T oo, we obtain
(ar(hr(F))Scc) - 0, and (F))Sc - 0,
for any F.
Proof of Lemma 2 We show that variance divided by T' converges to a non-negative constant. Let UT == E, 2t/v VT, where di. (as shown Equation 14p bounded deterministic function of the state of X₁ time t. As demonstrated in Sarkar ct. al. Sarkar al. (211a).. we too break
our weighted sum UT across three time intervals: (i) [1, Tc 1. (ii) [T. Ic + M 1]. and (ii) [Tc + M, 7), where M is constant. Now, from Sarkar et al. 2014a), simply apply Lemma 5.7
to get that (Ur (Tc)), Sc) Sc] - de, for some de 2 and from Lemma 5.8, we have that Var(E(Us E(Tc), Se) o(1).
Now, since the law of total variance provides
Var(Ur Sc) = F[[ar(Ur 8(Tc), Scl + Var(F[U, ((Tc), Sc)
we use the previous results from Lemmas 5.7 and 5.8 Sarkar et al. 2014a) to get
Var(Ur (Sc) de T 0, for some constant a. 2
Plugging in the definition of gr into UT and calculating Var(Ur Sc), it follows trivially that Var(hr Sc) and Var(dr (Sc) 0 as T + sc. We refer readers to Remark 5.10 in Sarkar et al. 2201aa) 4ah to see how these results also hold in the case when C is aperiodic.
Lemma 3. If the GSC process is a-mixing, then there exist a function R(C) with a deterministic function of class C denote, such as
lim (Fdr(F) ((Tc), Scl = R(C), and lim Eld Scl = R(C). T-
T-000
Proof of Lemma
We know by definition that
T
(d))
PP4z(0, (d)
F)] (e(d)
B((r(F) ((Tc). T
F.
E(Tc),
(15)
(a (d) F)] [.(d]]
This is average of terms F.
E(Tc), Sc
spanning across d-simplices with indices
j E (1,-.... (d))) and discrete time steps & E (p...., 11.
For ease notation, let
X, (o+1(0) (d) F)I [9,(d]
X, denotes the total number of possible (d 1)-simplices with d-face as oft)) divided by the total number of d-simplices in Ge-
16

---

Under review as a conference paper at ICLR 2021
In the R.H.S. of Equation 15 the term inside the summation is simplified
E (8(Tc), Sol = Σ xPr[X,= = x E(Tc),
We know that both (a) Markov chain. Let [YY denote an indicator variable whether "Y in state S" or not.
(d) F¹) and Ge(d) are fully determined given the current state S, of the
We have,
Pr[XX 8(Tc), Is((X P))r 8 E(Tc),
As result, the R.H.S. of Equation 15 becomes
ΣEΣ
=ls(( $ Scl
(16)
7
Let X(S) Σn (X, = x) as this term is fully determined by state Then, Equation can be rewritten as
E((s) Σ. Pr(S, S| ((Tc), Scl
(17)
T
Due to stationarity, the average E, Pr(S. S ((ECT),, will converge to constant function
of state S, denoted by R(S). Given that X(S) is bounded and the average term converges to constant R(S), we say that Equation 17 converges to some constant R(CC) > 0, where R(C) is deterministic function of communication class C. This proves the first part.
A simple application of the tower property of expectation followed by the dominated convergence theorem shows that limy F)) Scl = Rc. This completes the proof for the result.
Then, we are ready to prove the convergence of the variance term.
Proposition 3 (Variance). If the GSC filtration process is a-mixing, then, conditional on Sc, obtain VT 3g as T 00.
(T (T-p)- E. dr
Proof of Proposition By Proposition the term Vy is written
For the denominator, Lemma shows that E[dr Scl + R(C)), where R(C) a positive deter-
ministic function of class C. Also, Lemma states that Var(dr Sc) + 0 holds as T + co. Thus, dr 3 R(C)= O holds. Also, Vr is asymptotically well defined for class C.
For the nominator, Lemma also shows that limo 4 Sc) 0 as T + oc and Biq. Sc] therefore we have limy 1/T gr S By the continuous mapping theorem, we obtain the statement.
0 conditioned Sc.
Next, we discuss the bias term Br. To this aim, we rewrite the term By (F, C) as follows:
Br(F,C) (F) Scl ((F))((r(FF Scl)
E[dr(F) Sc]
Lemma 4. Given that Assumption holds and that when + oc, the bandwidth parameter O. Then, we have that BT C) = 0(6) o(1) as co.
Proof of Lemma For L E [p, T 1). j E (x(()) and fixed feature vector F, the numerator of (F C¹) can be expressed
average of terms of the form
P (o (, (d)
Put1 (o,0 FF]] (d))
A, = E
Sc
E
Sc
g(F)
(18)
17

---

Under review as a conference paper at ICLR 2021
The first term in Equation 18 can be rewritten using the tower property
1T+ (1)
F))
E(Tc), Sc
Se
(e(dd)
|P:4, (o (i)
When we condition on {(T)), it makes Also, for t 2 Te, we have
conditionally independent of Sc, if > Tc.
I (o)
(d)
.F)
[P41(0, (4) .F) 9c(d) o (F (..)
E
(G(d)
E(Tc),
=
(19)
where En )
|P (o. [f)_))] (G)
Given the result in Equation 19 and the fact that the term
is bounded results in
" (d) F)]
8(Tc),
(20)
(d)
(a-1(0))) (d) F))
g(
(Fr(o, (T,)) $4 + > 4
(d)
(o-1(0)) (d) F)
(d) , (.)) cT 1).
(d)
where e > 0 an existing constant.
Now, the numerator of Br C)) can be upper bounded as
I F)
EA/T
AUT
<
(o(Fi(o [.)) g(F)) Sc
(21)
T
(d(d)
+ d' Σ Pr[Te > 1//..
The second term in Equation 21 vanishes as T + co because is order ((E(Tc]/T). Thus, the numerator of BT C)) is an average of terms of the form
P (Pt1(o)"))
(d) F)) (d)
I
(((F,(o)9,,,,) (w)) - 2(F)) Sc
(22)
Our feature vector counts and simplex neighborhoods are finite because (G(( is bounded. The
expectation in Equation 22 is just a summation of finite terms. We set F² Fo(o T,,,, and make use of our smoothness assumption | so that
I9(F") g(F) = (xx(-11F - F" l//6).
We also use Lemma to say that the denominator of our bias term converges to constant R(C)). So,
Br(F,C)
O(b).
The last equality follows the property of in the Schwartz space. Now, since BF O(b) and 6 - 0 as T - 20, then we have that (T C*) = o(1). This completes the proof.
Then, we prove the convergence of the bias. Then, we have the result:
Proposition 4 (Bias). If Assumption holds, then, conditional on Sc. Br B holds as T co.
Proof of Proposition Proposition 2 shows that Br = (r
similarly shown in the proof of Proposition Further, Lemma states that By (F, C') = o(b). Combining the results, we obtain the statement.
By Lemma 2 and obtain dr R(C) 0 as T
n
18

---

Under review as a conference paper at ICLR 2021
Now, can prove the consistency (Theorem
Proof of Theorem ! For the result of Ôr, we apply the results of Proposition 3 and to the decom- position in the equation then obtain the statement.
For the result of 9r, we additionally combine the result of Lemma]
then obtain the statement.
D PROOF FOR ASYMPTOTIC NORMALITY
D. INTRODUCTION TO WASSERSTEIN DISTANCE AND APPROXIMATION TECHNIQUE
We denote by (R( the space of such bounded functions h that are 1-Lipschitz. More formally,
[h(z) h(w)
| sup h(x)] < and Lip(h) 1, where Lip(h) = sup =ER
2// x yl
So, E BL(R).
We now make use of the Wasserstein metric to measure the distance between distributions. There- fore, our estimator represented as W can be shown to converge to Z. when the Wasserstein distance between W and Z's underlying distributions converges zero. We have that
du (W,2)
sup [Bh(W)= - Eb(Z)
(23)
he (R)(RR)
D.1.1 INTRODUCTION TO STEIN'S METHOD FOR NORMAL APPROXIMATION
Stein Stein et al. 1986) introduced powerful technique to estimate the rate of convergence of sums of weakly dependent r.v.s to the standard normal distribution. A remarkable feature of Stein's 's method is that can be applied in many circumstances where dependence plays role, therefore we propose an adaptation of Stein's 's method to our setting of dynamic GSCs.
Given a standard normal r.v. Z, Stein's lemma (stated below) provides characterization of Z's distribution.
Lemma (Stein's Lemma Chen et al. (2010). IFW has a standard normal distribution, then
E."(WW) = ((W),,
(24)
for all absolutely continuous functions R + R with EJJ((Z) < x.. Conversely, if Equa- tion 24 holds for all bounded, continuous, and piecewise continuously differentiable functions f with El (Z)) < oc, then W has standard normal distribution.
In order to show that a rv. W has distribution close to that of target distribution of Z. one must compare the values of expectations of the two distributions on some collection of bounded functions
h: R + R. Here, Stein's 's lemma (Lemma 5) shows that W 4 Z, if
E (W) E|W f(W)] = 0
(25)
holds. Observe that distribution of W is close to that of Z's distribution, then evaluating the L.H.S of Equation 25 when W is replaced by Z would result in a small value. Putting these difference equations together, the following linear differential equation known as Stein't 's equation is arrived at
f'(W) W W(W) = h(W) - EA(Z)
(26)
The f that satisfy Equation 26 with h E BL(R) must satisfy the following conditions for all y,, = R
Il 2, $2 s 22/T
(27)
( f() < D|21
where ho(()) EE)()) sup.20 {(2), 02 sup,20 x(1 -11x((())) (x)), and g(x) /)/
(where (x:) is the distribution function and Φ(x) = o' (')r). Then, D (a + 02) [n a1.0 2
19

---

Under review as a conference paper at ICLR 2021
constant. Additionally, have bound on the covariance, given the dependent r.v.'s are also bounded.
P & = P C2) then Cov Cov(XX S 42)
(28)
We take similar approach to Sarkar et. al. Sarkar et al. 2014a) in terms of using the Wasserstein distance to bound the normal approximation. We first define the dependency our GSCs and then propose notion of a mixing in our context of GSCs. We obtain tighter bound than the bound pro- posed in Sarrar al. (2014a), by instead following an approach proposed by Sunklodas [Sunklodas) 2007
D.2 GAUSSIAN APPROXIMATION FOR DEPENDENT VARIABLES WITH GSC
In our model, we assume the r.v. A, to represent a d-simplex (d) in a GSC G. order to have a notion of a-mixing in setting, must first define distance between two d-simplices o and jj- We drop the (d) superscript for brevity and ease of notation. We define this distance as the Hausdorff distance between simplices as
{ sup inf dg(u, t'), sup inf weay Dea 40(0,00)
du(o,, o5) = max
(29)
vEor n'Ea;
where (U, counts the number of edges in the geodesic connecting vertices and of in g()).
In Stein's 's method, the sum of dependent L.v's is studied by breaking the sum Zn into two sets based on the in mixing coefficient (r)). In our setting, given a fixed d-simplex dı, we study two partial sums pertaining to: 1) all d-simplices that are at most r-apart from A₁ and 2) the remaining partial sum after removing the variables pertaining 1) from Z,,-
With this notion of distance between sets of r.v's, we modify with slight deviations from proposition in Sunklodas et. al. [Sunklodas (2007) to accommodate our a-mixing Markov chains based on GSCs. For sequence of r.v.'s X1, X2, satisfying the a- a-mixing condition, we write
X B
Zn
A
A
B²
E
x,)
t=0
We assume B, > O.
TT(m) denotes the contribution of d-simplices that are further than m away from o, and z za,,, r) denotes the partial sum of Lv''s representing simplices that are exactly away from A, Therefore, Em x²(0,,) gets us all those d-simplices that are greater than or equal to m away from a,, We interested in the contribution of simplices away from o, we vary from 0 to m. With Proposition 5 we proceed to derive an upper bound on dn (Zn, N) (i.e., the Wasserstein distance between Zn and N).
Proposition 5. Let S(a,,r) r) denote the set of d-simplices whose Hausdorff distance equals r. More formally,
S(o,, r) toz ddrlo,, 0;) =r]
Additionally, let & denote a mean-centered version of rv. X. Then,
x(0,r))= =
Σ Ap
(z(o,, 0) = At)
T (m) Un I(o,.r). = 0,1, (T)- = Zn.)
Suppose that IEZ, = 0, EZ 1, and EA < 00 for all i = 1,... ,,. Let be a r.v. uniformly distributed in [0, and independent of other rw''s. Let f IR -+ R. be differentiable function such that supzem [z)) < co. Then we have
F.f'(Z..) IF.,,, F +... Fg
20

---

Under review as a conference paper at ICLR 2021
where
11
RA ( + (
1=1
E2 Σ E.A (TT
2r
E3
E1 =
Σ r))
1=
1 gg
1=1 r21 922r+1
Es
BA
Σ
18(00) Eg =
EAZO ET
Σ EAREO!
12
9=0
i=1 921
and
8 = f )(
Theorem 3. Consider a sequence ofnv'ss X1, X2, that satisfy a-mixing condition (Definition) 5
Let E.X, = 0, Pr[|Xa & L} = 1, for = 1,... n, for some constant L >> O. Then, for every (R),
nL
du (Z N) S D)
Σ
EIA
ra(r)
B
where D) is finite constant which depends D and max; (S(o,,)))
Proof of Theorem Given a d-simplex and its corresponding n.v. A, recall that S(a,, denotes the set of d-simplices that are at Hausdorff distance r away from o;. We additionally define Sm to denote the maximum cardinality of S( r) for all i and fixed r, i.e.,
Sn max (S(a,,7)
In order to upper bound the Wasserstein distance between Zn and N, we estimate the difference EZ(Z,) (N( using Proposition It was shown in Proposition that this difference is sum of terms F,, ... F7. We will proceed by individually bounding each term.
Bounding Fj:
n
EAx(orr) [(CT + -(T
E1
(30)
We can upper bound term (i) in Equation 30tiiionn00sse using Equation 27 by
Dle]lz(o..r)) s D(a(o.,)))
(since |e| S 1)
Then,
(((,,r) [T(T!" - < D(x(o,,)))
[(T
(31)
Now, we upper bound x(),,r) as
x(o;.r) r) S Sm
(32)
Bn
since each normalized n.v. in Zn is upper bounded by L/ Bn. The L.H.S, of Equation 31 upper bounded by D.2
1
B
We know that
Cov 4: a(0,)))
-
(33)
21

---

Under review as a conference paper at ICLR 2021
= ( (I (F(() +cx(ow.)) - -
(0)
+ EA,, Bx((,,)) [F(T e
Notice that term (ii) is nothing but the summand in Equation (Equation 28 to obtain
30
We apply the covariance bounds
I Bn
T a(r) S 4DS
1
(ii)
DSS
((rr
(34)
B
B
Then, we have that
L3 ADS
nL 2-1
E1
B3 a(())
S 4DS
Σ a(r).
(35)
B
Here, the summation Σ Σ appears, because there are only n variables that should measure the dependence between each other.
Bounding Eg:
Eg =
Σ EAA ((T + -
(36)
(612)
Using Equation 27 we have that term (iti) I D|A.). Then, [Bal can simply be bounded as
n
|E S D Σ
E|A 3
(37)
1=1
Bounding Eg:
2r EA,
Exl
(38)
im
r2
2r
2r EA r) E (5(0)
<
Σ
EA
r))
(iv)
(0)
Let us focus on bounding terms (iv) and (w), separately.
For term (iv): We can further split it as
E A (0
(39)
We have previously worked out the bounds for terms A, and 2(0,,)). Therefore, we now focus our attention on bounding 8(9)
g( = -)
(40)
= -((((") +x(orr))) - )())()))
(using Equation 27
L
D
Sm Bm,B
Bn
22

---

Under review as a conference paper at ICLR 2021
Therefore, term b (in term (év)) is upper bounded by DS L B
Applying the covariance bound (Equation 28 we have that
I,2 a(r) - 4DS m Ba a()
I
(iv) W 4
D m B
(41)
Bn
For term (v): We have calculated some bounds previously, so we can again split (v)
as
I.
a(r))
D Sm I.
E Ag
x(
E
Sm
(42)
Bn
Bn
BT
d
using Equ 28 on
using Eqn Sqnf-1oon
L
4DS a(r)
m B3
Now, combining the inequalities for terms (iv) and (v), we have that
L ((r) 8DS
nL
Es
Σ g=++1
8DS
ra(()
(43)
B3
B3
Bounding Ed: We have that
Ed
Σ
EA,
(44)
1=1 r 1 11922241
< 4DS2 nI.3
alg rr)
B3
r21 922r+1
nT.3
< 4D5? m
ra(r)
because Er21 Egzert1 alg- - r) < nー ra(r).
Now, using our previous bounds, the remaining terms, i.e. Es). [Eel. and |Ez] are bounded as follows:
nL.3
Esl < 4DS2
ra(r)
(45)
B3
nL3
Eg
< 22
a(r)
B3
Ez < E
1
t=0
Finally, we combine these bounds to arrive at our final upper bound as
nT,33 B3
- E...f(Z.)). C(Sm. D)
E 3
ra(r)
(46)
where C(Sm; D) is a constant term depending on constants Km and D. This completes our proof.
D.3 DEFERRED PROOF
In this section, establish our estimator's result the asymptotic normality.
23

---

Under review as a conference paper at ICLR 2021
Let n [d)( denote the total number of d-simplices in GSC G. at time t. Recall from Equation 13 that
1 n
(t(()=
Σ
P (a) (4)
F)I
n1 1=1
(r(() =
1
(0 (d) F)I
12 1=1
Also, from Equation 14
we have
qt (tr gdz (f) gdz(t) Scl
Additionally, let us define a variable pr for convenience as follows
Pr hr (t) (t) (thr((t) gdz (t) (TTc),
Note that Pt conditioned on both E(Tc) and Sc, while de is just conditioned on Sc. Keeping these expressions in mind, we begin by showing the weak convergence with pr.
Lemma 6. Under Assumption 7 given pt for any finite Tc and 0
Σ
P./TT 3 o0
conditioned on E(Tc) n Sc T 00
12
Proof of Lemma 0
Given normalized r.v. WT which is of weakly dependent r.v.'s
Σi2ToMM Pe
Wr
Var (EizTeHaPH (c)
where Ps is already bounded and mean-centered. We have to show that our upper bound Theo- rem converges zero, that according to Stein's lemma we have
Wr 3 (0,
conditioned on E(Tc) nSc
Recall that by Lemma 5.7 in Sarkar et al. (2014a). we have
Var
Σ Pe 1 /T -2
12Tc+M
Now, we show that conditioned on event E(Tc) Sc, our bound in Theorem 3 has convergence rate of OTT-1/2).
Note that our Pt corresponds to A; and 7 to n in Theorem 3 As pt is a function of S,, it involves p+1 GSCs (G--tt1, Ge+1) and the distance between the and j-th GSC is defined dist(i,)) max(li - (p + 1), 0). Therefore, you will observe that we have for r(a,, r) only 2 states that distance apart from o,, i... A; F and A + r. Therefore. S, (l)).
Given that Pr([pe] < D} = 1, for = 1, .T and for some constant bound L > 0, we have
T-1
Σ
Elpp 3 T
ra(r)
(ignoring some constant terms)
(47)
B
1=1
3 T B
+
ra(r)
We additionally impose that E ra(r) because we use decaying function for a(-) and BZ 2 Tf with positive constant co. We choose
1
a(r) s C1 (2olgr))
24

---

Under review as a conference paper at ICLR 2021
for 2 and fixed p
1, where C1 oo is constant. Then,
L T
1 Σ ra(r))
1+ + +
E rloorr)
(48)
B
3/2
VT
0
where (L, C1, co) is a positive and finite constant only depending on the quantities within the parenthesis. The inequality follows the fact B4. cgT Thus, achieve asymptotic bound of 1/2-)/3). This completes our proof.
The weak convergence with implies the weak convergence with Qr. by simple application of Lemma 7.2 in Sarkar et al. 22014a).
Lemma (Lemma 7.2 Sarkar al. (2014a)). Suppose Lommollhods. Then, under Assumption and assuming 0,
Conditioned on Sc. S
as AT 00
We now prove the weak convergence of our estimator.
Proof of Theorem 2 By the definition of ğr g in Theorem achieve
VT(or g) vT Ir) + Vārr 99)
= =(VT33 T/2 E. + T2/2 BrEidr|Scl
dr
dr
We are able to assess the convergence each item. Since Lemma 3 shows F[dr |cc] + R(C) and
Lemma shows Var(dr|Sc) + O, we obtain dy B R(C). By Lemma 7 1 E, converges to (10 2 Further, Lemma proves BT = O(b). Combining these results with the Slutsky's lemma, we get the following results:
-) - +
where Wf. is a random variable such as
WT S N(0,02/R(C))
With the settings B = o(T-1/2) and (T-1/22) we obtain the statement.
25


Reviews:
[{"review_id": "uBp2EOU5S0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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\n\nSome comments and questions:\n\n1. 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.\n\n2. 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.\n\n3. It would be nice if the authors could give an example of a scenario where the process is alpha-mixing.\n\n4. Proposition 1 makes a reference to Theorem 3 (which is deep within the appendix), mentioning this in the proposition statement would be nice. \n\n5. The statement of Theorem 2 conditions of S_C which is undefined. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Jrd2km6-jP_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nIn my opinion, the paper has the following strengths and weaknesses. \n\nFor 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. \n\nFor 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "3Z1eC_-aXe3", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\n\n-\tThe 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. \n\n-\tMore 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.\n\n-\tThe 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. \n\n-\tThe authors present numerical performance of their method against various other methods based on 4 dynamic graph datasets.\n\nStrengths:\n\n-\tFor 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.\n-\tAuthors explain the differences and similarities between existing inference strategies clearly, enabling the reader to understand for which task the proposed method is specialized. \n-\tExperimentally, 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.\n\nWeaknesses:\n\n-\tSection 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.\n-\tIt 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.\n-\tUsing 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.\n\nAdditional Comments/Questions:\n\n-\tWhy would you give higher score when two vertices co-occur in a higher dimensional simplex in the past?\n-\t 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?\n-\tDefinition 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.\n-\tSection “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.\n-\tI 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?\n\nScore:\n\nI 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. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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