GraphPulse: Topological representations for temporal graph property prediction
Authors: Kiarash Shamsi
Farimah Poursafaei
Shenyang Huang
Bao Tran Gia Ngo
Baris Coskunuzer
Cuneyt Gurcan Akcora
Venue: ICLR 2024 poster (2024)
Keywords: Temporal Graph Analysis
Topological Data Analysis
Graph Property Prediction
Graph Neural Networks
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: Many real-world networks evolve over time, and predicting the evolution of such networks remains a challenging task. Graph Neural Networks (GNNs) have shown empirical success for learning on static graphs, but they lack the ability to effectively learn from nodes and edges with different timestamps. Consequently, the prediction of future properties in temporal graphs remains a relatively under-explored area.
In this paper, we aim to bridge this gap by introducing a principled framework, named GraphPulse. The framework combines two important techniques for the analysis of temporal graphs within a Newtonian framework. First, we employ the Mapper method, a key tool in topological data analysis, to extract essential clustering information from graph nodes. Next, we harness the sequential modeling capabilities of Recurrent Neural Networks (RNNs) for temporal reasoning regarding the graph's evolution. Through extensive experimentation, we demonstrate that our model enhances the ROC-AUC metric by 10.2\% in comparison to the top-performing state-of-the-art method across various temporal networks. We provide the implementation of GraphPulse at https://github.com/kiarashamsi/GraphPulse.

Published as a conference paper at ICLR 2024
GRAPHPULSE: TOPOLOGICAL REPRESENTATIONS FOR TEMPORAL GRAPH PROPERTY PREDICTION
Kiarash Shamsi'
Farimah Poursafaei Shenyang Huang
Tran Gia Bao Ngo!
Baris Coskunuzer Cuneyt Gurcan Akcora'
'Department of computer science, University of Manitoba, ?Mila Quebec Al Institute,
*School of Computer Science, McGill University, *University of Texas Dallas, 'AT Institute University of Central Florida
(s (shams i 1 @myummn toba toba ca, fari rirmahhh.. poursafaei @mi la. quebee,,, shenyang. huanggmaiial mcgill. ca, ngotlemyumanite ca, coskumuz&ut edu, .aneyt.accorauuc..
ABSTRACT
Many real-world networks evolve over time, and predicting the evolution of such networks remains challenging task. Graph Neural Networks (GNNs) have shown empirical success for learning on static graphs, but they lack the abil- ity to effectively learn from nodes and edges with different timestamps. Con- sequently, the prediction of future properties in temporal graphs remains rel- atively under-explored area. In this paper, we aim to bridge this gap by intro- ducing principled framework, named GraphPulse. The framework combines two important techniques for the analysis of temporal graphs within a Newto- nian framework. First, we employ the Mapper method, key tool in topological data analysis, to extract essential clustering information from graph nodes. Next, we harness the sequential modeling capabilities of Recurrent Neural Networks (RNNs) for temporal reasoning regarding the graph's evolution. Through exten- sive experimentation, metric by 10.2% in comparison to the top-performing state-of-the-art method across various temporal networks. We provide the implementation of GraphPulse at /ttttp:://tttiii com/k wikaaaaaaaaass i/ Crrahhullsssss
demonstrate that model enhances the ROC-AUC
INTRODUCTION
Real-world interaction networks, such financial and cryptocurrency networks, experience contin- uous evolution due to the emergence of new transactions and users. Predicting the dynamic changes in the graph structure of these networks over time poses significant challenge. While Graph Neural Networks have proven effective for learning graph representations in static graphs (Xu et al., 2018), temporal graphs differ significantly because nodes and edges continuously change various times- tamps. Classical GNNs are not well-suited for temporal graphs as they do not effectively utilize crucial temporal information, such as alterations in the graph structure over time. Hence, there is pressing need for novel approach to adapt GNNs successfully to temporal graph settings, giving rise to a new field known as Temporal Graph Neural Networks (TGNNs).
In order to understand the evolution of temporal graph, it is essential to capture the global graph structure across time points and then quantify the changes and evolution that the graph has un- dergone. For instance, in subsequent time step, the graph might introduce a new node or es- tablish an edge between two existing nodes to significantly shorten the graph diameter. While random graph models such as the Sedos-Renyl graph (Erdōs & Rényi, 1960) and the Stochastic Block Models (SBMs) (Holland et al., 1983) have been studied extensively in the static graph litera- ture (Barabási, 2013), there is few theoretical work studying the evolution of temporal graphs in the transition space of graph generative models.
We aim to close this gap and introduce GraphPulse to efficiently capture the evolving structure of a graph over time in an innovative temporal framework. Our principled approach posits two hypotheses. First, we suggest that the evolution of graph can be represented as temporal trajectory

---

Published as a conference paper at ICLR 2024
(a) Daily transaction graph of Ethereum token
TDA Mapper network of the graph in la.
Figure I: Illustration of TDA Mapper Network. The daily transaction graph of an Ethereum token (a) is transformed into concise Mapper network (b), where nodes represent clusters of token investors, and edges are assigned weights based on the shared number of nodes between clusters. Node sizes indicate cluster sizes and node colors are Disconnected components, highlight node groups with divergent graph characteristics compared to the rest of the nodes.
in a Newtonian phase space (Newton, 1833). Second, we propose that topological technique, Mapper (Singh et al., 2007), can be effectively employed to model this trajectory. Mapper generates concise and principled visual representations of data, as exemplified in Figure 1. As third step, we utilize the topological information in a Recurrent Neural Network to predict graph feature in the future.
We demonstrate the effectiveness of our approach in two types of experiments. First, empiri- cally prove that Mapper networks can capture temporal trajectories effectively by considering two common phase spaces for graphs: Erdos-Renyi graphs (Erdös & Rényi, 1960) and Stochastic Block Models (SBMs) (Holland et al., 1983; Barabási, 2013). Subsequently, we introduce a unique task focused on predicting graph properties in dynamic graphs and demonstrate that the GraphPulse out- performs existing Graph Neural Network and Temporal Graph Neural Network models in social and cryptocurrency networks. In nine temporal network scenarios within these contexts, our model consistently surpasses state-of-the-art approaches in eight instances.
Our Contributions:
We present a novel framework, GraphPulse, for analyzing the evolution of temporal graphs, grounded in phase space transition. We empirically show that the TDA Mapper algorithm is highly effective at capturing the evolution of temporal graphs in the phase space.
We introduce a unique and valuable task involving the prediction temporal graph properties in the future. GraphPulse takes advantage of sequential modeling capture temporal variations, and it effectively integrates node feature information into the model using the TDA Mapper algorithm.
We create seven original cryptoasset networks for the temporal graph property task and publish them to serve as temporal benchmark datasets for future research.
Empirically, GraphPulse significantly outperforms oftte--f-thearrr temporal graph learning models in eight out of nine networks from both social and transaction network domains.
2 BACKGROUND AND RELATED WORK
In this section, we first define a temporal or dynamic graph and its property. Then, we give the related work for Topological Data Analysis graphs and temporal graph neural networks.
Discrete Time Dynamic Graphs. A Discrete Time Dynamic Graph (DTDG) is defined as series of snapshot graphs denoted as G (G., It...... Gr,, }. each G., (V, & represents the graph at time step and V; and & C V; x V; are the set of nodes and edges at time respectively. The graph can be directed or undirected and the Nodes can also have attributes.
Temporal Graph Property Prediction. The goal of the Temporal Graph Property Prediction task to predict specific property of temporal graph over future time interval in Discrete Time
2

---

Published as a conference paper at ICLR 2024
Dynamic Graph. Formally, given DTDG G, we define target time interval [n + 81, + d2], where 51 and 62 are non-negative integers with 61 I 82. The objective is to predict the values of the chosen graph property within the specified future interval (n + 6,, + 62)- Examples of graph properties include metrics such as graph density, the count of newly added edges, and the cumulative weight of edges across the graph. Other temporal graph properties include temporal coefficient, and temporal betweenness centrality can also be
global efficiency, cemporal-coreelatin explored in the future (Nicosia et al., 2013).
2.1 TDA & MAPPER
Existing methods in Topological Data Analysis can be categorized into two main approaches: per- sistent homology (PH) and Mapper. PH studies the evolution of topological features (connected components, loops, voids, etc.) of dataset various spatial resolutions Kyriakis et al. (2021). PH has recently been utilized as a powerful feature extractor and combined with deep learning meth- ods (Hofer et al., 2020; Carrière et al., 2020; Chen al., 2021; Horn al., 2021) in node and graph classification tasks. However, PH-based methods face limitations in their application to large networks due to their high computational complexity.
The "Mapper" method was introduced by Singh et al. (2007) and further claborated by Carlsson (2009). This approach serves the purpose of converting complex, high-dimensional data into more comprehensible and coordinate-indeeendee
graphical representation to adeptly capture the underlying topological attributes of the data (Van Veen et al., 2019; Tauzin al., 2021). Over the past decade, the Mapper technique has found fruitful applications in various domains (Lum et al., 2013; Kamruzzaman al., 2019; Zhou et al., 2021) yielding remarkable outcomes. More recently, the Mapper algorithm found utility in the domain of graph representation learning, as highlighted in the works of Hajij et al. (2018); Bodnar et al. (2021). However, to the best of our knowledge, this is the first work to utilize Mapper in temporal Graph ML.
2.2 TEMPORAL GRAPH NEURAL NETWORKS
Temporal Graph Neural Networks (TGNNs) have shown promising performance on tasks such as link prediction and node classification (Rossi et al., 2020: Souza et al., 2022: Pareja al., 2020; You et al., 2022; Huang et al., 2023c). Kazemi et al. (2020) categorize temporal graphs into Discrete Time Dynamic Graphs (DTDGss) (You al., 2022: Gao & Ribeiro, 2022: Pareja et al., 2020; Haji- ramezanali et al., 2019; Yang et al., 2021) and Continous Time Dynamic Graphs (Xu et al., 2020; Rossi et al., 2020; Poursafaei et al., 2022: Souza et al., 2022; Luo & Li, 2022: Jin et al., 2022). In this work, we focus DTDGs where the temporal graph is modelled as sequence of snapshots. Although tasks like link prediction and anomaly detection in temporal graphs have gained popular- ity, there is still lack of exploration in graph-level tasks specifically tailored for temporal graphs. One related task is network change point detection that aims to detect time points where the tempo- ral graph undergoes drastic structural changes (Huang et al., 2020; Miller & Mokryn, 2020; Wang et al., 2017; Huang et al., 2023b;a). While change point detection focus on detecting anomaly from observed network structure, we focus on predicting future graph properties such as network growth or shrinkage in this work.
The study of the expressiveness of GNNs often employs the Weisfeiler-Lehmart (WL) test which tests for graph isomorphism (Xu et al., 2018: Maron et al., 2019; Cotta et al., 2021). On temporal graphs, recent work (Gao & Ribeiro, 2022; Souza et al., 2022) attempts to extend the WI. test to temporal graphs as converting them into static representations. However, real-world temporal net- works typically deviates from the graph isomorphism based analysis due to the continuous addition of nodes and edges at different timestamps. We argue that an alternative framework is necessary to analyze the practical effectiveness of GNNs. We introduce a novel concept, called phase space, for temporal graphs address this need in Section 4.
MAPPER AND TOPOLOGICAL GRAPH REPRESENTATION
In this section, explain the first component of GraphPulse, the Mapper, and its application to single graph. The core principle underlying Topological Data Analysis revolves around uncovering latent data patterns through systematic analysis of data shapes, which are measured across various
3

---

Published as a conference paper at ICLR 2024
resolution scales (Chazal & Michel, 2021; Dey & Wang, 2022). TDA brings forth range of com- pelling advantages, notably pertinent within the realm of graph machine learning. Primarily, TDA scrutinizes data shapes in a manner free from coordinate constraints, enabling systematic compari- son of patterns derived from diverse data collection frameworks. This adaptability proves invaluable, accommodating temporal scenarios such as comparing graphs in distinct time periods.
In this work, we employ the Mapper method as introduced by (Singh et al., 2007: Carlsson, 2009). For compact topological space X' and real-valued function f : X + R. the Mapper algorithm provides a general framework to study the topological changes in X' with respect to the function f. which is commonly referred as a filter function or lens. The choice of lens is crucial in Mapper construction as various lenses provide distinct insights on the data (Singh et al., 2007: Dey & Wang, 2022). In practice, is mostly a point cloud in TRM,, and f is a function from R. to representing some domain information of the data. The output of the Mapper algorithm is the Mapper network, which is considered a meaningful summary of the data, representing clusters and relations between the clusters in the data.
To define the Mapper network, we need to explain the nerve of a cover. Let X' be a point cloud in R- A cover of X' is set of open sets in R. U = {U with X' CUU U. The ID nerve of U is a graph and is denoted as 77 (L4). Each node U in 7/2 (2) represents a cover element Ug and an edge exists between two nodes Ey and v, if U2 n U/ is nonempty for the corresponding cover elements. The appendix Figure 4-a gives an example in which X' is 2D point cloud and the cover M of X consists of collection of rectangles the plane.
While it is possible to use multiple scalar functions, to keep the exposition clear, we describe the Mapper construction with single scalar function ʃ X' R. We start with a finite cover of ((X) C R using intervals, that is, a cover I (1x)==1 of f(x') C R such that f(X) C U2 Ja. see Figure 4. This induces a cover iI of X' by considering the clusters induced by points in (Ta) for each h as cover element. The 1D Mapper network of (X, denoted as r, is nothing but the ID nerve of U1 i.e. 1'x' ;= 7) (24).
For point cloud X, several choices and most important one is the lens function ʃ X' + R. Another choice is the clustering method for the point cloud. Finally, there are two tuning parameters. The first one is called resolution, which is the number of intervals } to cover f(2'.. The second one is called gain which is the percentage of overlaps of these intervals. Note that increasing the resolution gives a finer summary by increasing the number of nodes in the Mapper network and makes the clusters smaller. On the other hand, increasing gain adds more relation (edges) between the nodes (clusters). In Figure 4, the resolution is 6, and the gain is the fixed intersection amount (e.g., 20%) between the intervals I& and Ix+1.
be made to compute the Mapper network Fx. The first
Note that the Mapper construction can be generalized to higher dimensions by choosing the lens function f as a multivariate function, i.c., f : X + Ed (for d 2 2). In most cases, d = 2, and the resulting Mapper network is referred to 2D Mapper network, where the corresponding cover elements of become rectangles.
Mapper for graphs. For any graph G, we take the set of nodes V {Uz...... ..., 2n and use their feature vectors X; E RN as our point cloud Xg = (X.....,,,, C R. Then, we obtaín and use the Mapper network I of this point cloud Xg summary of the feature information stored in the graph G in our approach. The hyperparameters for our Mapper construction (lens function, clustering method, resolution, and gain) are discussed in Section 6.
TRAJECTORIES OF TEMPORAL GRAPHS
In this section explain the second component of the GraphPulse, where we represent graphs in a space, enabling us to directly compare their Mapper representations. The concepts of phase space and trajectory in this section will serve as the foundation on which we will build new temporal framework.
We propose topological model for describing the progression of temporal graphs. Specifically, posit the presence a phase space about a family of temporal graphs, wherein the sequence of tem- poral graphs gives rise to trajectory (path) within this phase space. Subsequently, for each graph,
4

---

Published as a conference paper at ICLR 2024
3
1
5
4
F
1
133
G1
G2
G3
The graph @1 has four nodes and three edges. In G2, graph gains two more nodes two edges. However, only in Ga do two triangular edges emerge in the graph.
(b) Induced TDA Mapper networks 11 and Tas for G1, G2 and Gs by using degree as the node fea- ture. Mapper node sizes (denoted by numbers) indi- cate cluster sizes.
Evolution of Graph Complexity. Mapper representations (b) of snapshot graphs (a) where the Mapper lens uses the number of neighbors.
Figure 2:
induce its topologiaal summary through the Mapper algorithm, which enables us monitor the evolution of these Mapper networks over time.
4.1 TRAJECTORY IN A PHASE SPACE
The core idea for temporal framework is inspired by Newton's laws of motion (Newton, 1833) that specifies how system's variables change over time in response to forces acting upon it. The idea of phase space emerges from Newtonian mechanies as natural extension of these princi- ples (Carroll, 2022). A phase space Р refers to multi-dimensional space where the state of system is represented by set of coordinates corresponding its variables. In our context, one can imagine this notion as correspondence map o P - G where 6 represents the space of graphs, where any point æ in the phase space represents graph ((xx) = G2 E G. Hence, each point in the phase space represents a graph instance: specific configuration of the system's variables, capturing its instantaneous or momentary state (see Appendix Figure for an example). In dy- namical system, the trajectories of system's 'ss evolution over time can be visualized as paths in the phase space. This concept is crucial for analyzing the behavior, stability, and evolution of complex systems by observing how their states change in response various influences or forces.
Formally, let Gp denote a family of graphs parameterized by the parameter space P. To simplify our notation, will employ Erdös Erdös-Rényi Rényi graphs an illustrative example, where P N x [0, 1| (see Appendix Figure 6). In this context, the generative parameters are (n, E P, where n signifies the number of nodes, and p signifies the probability of edge. This notation can be straightforwardly extended to encompass scenarios involving more than two parameters. Consequently. for x E 'P, Ge E 6p corresponds the graph within Sp associated with that parameter We assume a one- to-one correspondence between the elements of P and the graphs within Gp. Consider dynamic graph family (g¹) whose instances Gi, are in 6p, i.e., ğ (Gi, Gi,, r......
... Gi an ordered sequence of graphs. By using one-to-one correspondence, we induce set of trajectories (x²) with x (x), .i..,..... xx), x" P is the the jrh step of the tt trajectory which corresponds to the graph gi E6.
For any point x). E P, we define a vector V2 x1+1 x; where 1 < n. The pair (x), vi) defines a discrete dynamical system in the parameter space P (Galor, 2007). Our idea is to learn this induced discrete dynamical system in the parameter space and obtain some useful feature vectors for future instances. In other words, by using the prediction of future trajectory points of x in parameter spaces, we extract useful feature vectors to predict the future instances of dynamic network G'.
4.2 TRAJECTORY IN THE TOPOLOGICAL SPACE
Consider temporal trajectory & = (xu..... x,, with x; E P.i.. X is an n-step trajectory with the initial point x the final point x,, passing through intermediate points X1, X2, X,-1- While move on the phase space P through &, the original graph family defines a corresponding trajectory = (Go. ... G.) ) in the space of graphs Gp. Similarly, for the same trajectory & C P, we induce the corresponding TDA Mapper trajectory î in the space of graphs where each I, is the TDA Mapper network of G; by using the induced features (Section 3). We give an illustration of our TDA Mapper networks toy example using only node feature (node degree) in Figure 2.

---

Published as a conference paper at ICLR 2024
We hypothesize that trajectories can be captured and analyzed efficiently by using Mapper networks of the snapshot graphs. To test our hypothesis, we run extensive experiments in two well- phase space settings, i.e., vrdös--ééni and Barabási-Albert settings in Appendix A. For given trajectory & = (Xo:.... .x,) in the phase space P, we obtain the corresponding original graph trajectory {Gi) and the corresponding TDA Mapper trajectory {T;)- We compare the structural changes in the original graph trajectory and changes in the TDA Mapper trajectory. In order to mea- sure the structural similarity of graphs, we use similarity measure induced from graph Laplacian eigenvalues (Koutra et al., 2011). Specifically, our results in Appendix Figure 9 show that Map- per based trajectory encodes neighborhood in the phase space more efficiently. Furthermore, as we show in Section 6, our experimental findings demonstrate a significant enhancement in the predictive capacity of our model within real-world networks due to these topological summaries.
4.3 ADVANTAGES OF TDA MAPPER NETWORKS
Our approach introduces novel perspective to representing and visualizing the evolution of dy- namic systems in parameter space. By doing so, we can gain several advantages over using tradi- tional snapshot graphs for trajectory analysis, as follows.
Topological Features. Mapper networks focus on essential topological features, providing a nu- anced view of graph evolution under changing parameters. Consider Figure 2a that shows three graphs of increasing node counts and connectivity. As we transition from G1 to G2, the sole mod- ification involves introducing two nodes while retaining the pattern of satellite nodes linking to a crucial central node. Such a scenario is common on blockchain networks where addresses of blockchain exchanges distribute tokens in airdrops (Victor, 2020). The Mapper encapsulates that Gi and G2 are similar by creating a network of size two with connecting edge for both r and 2. Retaining such essential aspects in networks becomes particularly significant when addressing complex interactions that might not be evident through simple node attributes (e.g., degree) alone.
Compressed Representation. Mapper networks compress complex data into compact yet meaning- ful representations, enhancing visualization and robustness against data fluctuations. In Figure 2a, we can add another triangle A to G3 centered on the existing center graph node, but Mapper would just include the two new graph nodes to the bottom Mapper node (i.e., cluster) of I's without adding a new mapper node.
Ratti-Resolution. Mapper's multi-resolution capability enables detailed exploration of trajecto- ries, revealing fine details and broader trends. As the trajectory moves through parameter space, can identify clusters (i.e., network nodes) and connections, unveiling significant regions and transitions often hidden in raw snapshot graphs. With clear node and edge features, the resulting visualizations offer valuable insights into dynamic system behavior across parameter trajectories.
Due to space limitations, we report a comparative analysis of snapshot graphs and their Mapper networks in the Appendix. In particular, we demonstrate that Mapper networks exhibit greater stability than the original snapshot graphs when subjected to minor perturbations within the phase space. This observation underscores the considerable utility of Mapper summaries in predicting trajectories. We further validate our hypothesis regarding Mapper efficiency through an empirical evaluation of a novel task of predicting graph properties as we discuss in Section 6.
5 GRAPHPULSE
So far, have explained how the Mapper-based topological representations can help track graph trajectories in the phase space. In this section, we describe the overall flow of GraphPulse and detail the third step: sequential modeling.
Our methodology comprises a sequence of three distinct phases, illustrated in the visual repre- sentation provided in Figure 3: partitioning, topological learning, and sequential modeling. The partitioning step involves the conversion of input data into snapshot graphs denoted as ğ = (G., .t....., J., J. In this work, adopt 24-hour snapshots, although our model remains ap- plicable to snapshots of varying durations.
In the topological learning step, we construct TDA Mapper representations for graphs CT1, ,, CTT,. n: each corresponding to graph within (9). To achieve this, first extract graph

---

Published as a conference paper at ICLR 2024
100
Input
TITA Moppor
Trinsaction Netwwork
Labslol
Ninseltz intrysstantly
4/
8:
SSTGGGRU Mode
Output
Gooph ENTTON
Cruph Property
Figure 3: GraphPulse Flowchart. The GraphPulse system workflow starts with snapshot graph ex- traction, followed by the generation of Mapper networks. Next, a sequential LSTM+GRU model is developed, incorporating features from both the original snapshot graphs and the Mapper networks.
node features X' R.Nx from the snapshot graph Gr,, which serve as inputs for the TDA Mapper (see Section 3). Example node features are the count of neighbors and the summation of incoming edge weights, details of which are given in Section 6. TDA Mapper creates n Mapper networks for snapshots, which serve as the input for the sequential modeling step,
explain next.
In the sequential modeling step, we aggregate pertinent features from both snapshot graphs and Mapper networks such the number of nodes and edges (see Section A.3 for selected features). Denoting snapshot graph features as saapshht and Mapper network features as Mapper. where Faaaphhtt includes graph-level characteristic features of the snapshot graph such as the number of nodes and edges, and FMtpper encompasses characteristics such as node count and average node size. The fusion of I' sasppps and Fa provides holistic perspective on the system's evolution. Equipped with these features, we compose a sequence spanning n days, denoted as Sn, serving as input for our specialized sequential model. This sequential model illuminates the dynamic interplay between the changing graph property and the structural insights extracted from Mapper networks in organized manner.
The specific nature of the predicted graph property dictates the form of the sequential model. For instance, for real-valued properties, regression model may be appropriate, while binary properties can be addressed using classification model. This adaptable approach aligns the model's structure with the unique characteristics of the targeted graph property.
EXPERIMENTS
Graph property. We use network growth in terms of edge count the predicted graph property. Formally, let be a graph, / be specific time, and &a be time intervals, and F(11, denote the multi-set of edges between times & and ty. We define the graph property P as:
1, if [E(n, + 61,4n 5z) (E(),
P(G, t1, tn, 8z, 52)
0. otherwise.
Setting n = 7, 7, = and 82 7, we establish a meaningful and practical graph property. This choice of parameters is valuable due to the application of 7-day predictions, which hold significance in both financial contexts, such as Ethereum asset networks (Kim et al., 2021), where they can guide financial decisions, and in the realm of social network infrastructure, like Reddit, where they aid in planning maintenance activities.
Datasets. We perform experiments on MathOverflow (Paranjape et al., 2017) and Reddit-Body (Ku- mar et al., 2018) datasets, and seven ERC20 token networks that we have extracted from the Ethereum blockchain. The ERC20 token networks, consisting of real transaction data from the beginning period of the Ethereum blockchain, provide valuable insights into the dynamics of digital assets. A summary of the statistics of these datasets is presented in Table 2.
Mapper aspects. Section 3 constructed Mapper networks based node features X, which construct by extracting outgoing edge weight sum, incoming edge weight sum, outgoing edge count, and incoming edge count (see Section A.3 for feature definitions.) We used 2D-TSNE as our lens and

---

Published as a conference paper at ICLR 2024
Table 1: ROC-AUC results for the graph property prediction task. The bold results represent the best methods for each dataset, and the underlined results represent the second-best methods.
Dataset
GIN
TDA-GIN
EvolveGCN
GRUGCN
HTGN
GraphPulse
Adex
0.4484-20081
0.6089200574 +0,574
0.7167= 1096
0.6843.0 1894
0.7330=00.054
0.8928:00.00
Bancor
0.5895=200514
0,51 +0.4%6
0.7931 =0 1773
0.8588
0.7412
1.87222:00000
Aragon
0.3915
0.4648
0.7939=20.007
0.7854 0.556
0.7781
0500508
0.8926=00008
Dgd
0,5748
0.5789
0.7460
0.0504
0.686 #000500
0.7804
Coindash
0.5065.:0.0400
0.5015
0.7002 #0.0561
0.7321
#000399
0.0048
0.7004
Iconomi
0.6079=0.065
0,5158 +000651
0.8379 +0.0027
0.8105
#:0.0230
0,822
100013
Centra
0,4252:#0.0916
0,4777=+0.142
0,8663=0 1302
0.9001 +000000
0.9044=0..omm
0,8670#0.0077
Reddit-Body
0.3563=400088
0.5281 +000777
0.7709
0.6591 1:0066
0.6557
0.0000
0.8692::0.0000
Mathoverflow
0.3789=000667
0.5953+t0.044
0.6734
0.7405
0.788 =-0.0509
0.8008 00000000000000
KMeans for the clustering algorithm. We set the Mapper hyperparameters as cls 5, n. cubes 2, and pere-overlap= = 0.4 and study their impact in Section A.4.
F Ismupshot and Mappper- In the sequential modeling step, we collect specific features from both snap- shot graphs and Mapper networks. From the snapshot graphs, we extract three key features: the number of nodes, the number of edges, and the average value of edge weights. Additionally, we leverage Mapper networks to extract five supplementary features: the number of nodes, the number of edges, the maximum cluster size, the average cluster size, and the average value of edge weights.
Models. We compare GraphPulse against two baselines and three sfate-of-the-ar the-thr-rtttt TGNNs models (Appendix B details node, edge features, and graph types in models):
The two baseline approaches adopt the powerful GIN framework (Xu et al., 2018) within a binary graph classification context. We feed static graph into GIN, encompassing edges from days to + denoted as 9 (Ci, U U U... U g(, to predict the graph property. In a second variant of GIN, we integrate cluster membership information from Mapper networks as additional node features model called TDA-GIN This baseline designed to gauge the contribution of the information within Mapper networks.
The state-of-ar art models in TGNNs are EvolvedGCN (Pareja et al., 2020), GRUGCN (Seo et al., 2018) and HTGN (Yang al., 2021). EvolvedGCN focuses evolving graph structures, GRUGCN incorporates variational principles, and HTGN handles discrete time intervals in tem- poral graphs. The models are notable advancements in the field of temporal GNNs.
Implementation details. GIN and TDA-GIN models use a Graph Isomorphism Network with 64 hidden units followed by a target output di- mension of two. Raw RNN and TDA RNN models utilize LSTM and GRU layers with an Adam optimizer and learning rate of x 10-4. A hybrid LSTM-GRU model processes sequences in (7,3) and (7,5) format for input, respectively, We evaluate the models using the AUC-ROC score, a suitable metric for predic- tion assessment. We ran all experiments on Dell PowerEdge R630, featuring an Intel Xeon E5 E5-2650 v3 Processor (10-cores, 2.30 GHz, 20MB Cache) and 192GB of RAM (DDR4- 2133MHz).
Table 2: Dataset statistics. |daily| and Daityl de- note the average number of daily edges and nodes, respectively. [g] indicates the total number of snapshots. *Reported as meears.mottssdaass.
Datasel
Eeaty
Vanny
Duration
|
Adex
259.15
126.41
(0.10,6)
293
Bancur
320.84
154.97
(0.10,24)
311
Aragon
367.99
189.08
(0,11,19)
337
Dgd
90.16
29.32
(2,0,7)
720
Coundash
346.55
(0,9,11)
268
Iconomi
205.57
85.62
(1,6,12)
542
Centra
294.24
140.85
(0.9.5)
261
Reddit-Body
688.84
86
(1,1,20)
399
Mathoverflow
2532.75
124.09
(0.6.16)
183
6.1 EVALUATION RESULTS
Table I shows the ROC-AUC results for the two baselines (GIN, TDA-GIN) and three TGNN mod- els. GIN has > 0.5 AUC only in four of the nine datasets. All results are averages of five runs. Incorporating topologiaal information into GIN node features, TDA-GIN improves the AUC val-
8

---

Published as a conference paper at ICLR 2024
ues in five datasets. The largest gain is noted in the MathOverflow dataset with +0.216. However, the increased AUC values of TDA-GIN are still low.
The temporal GNN models have consistently high AUC values with HTGN having the highest mean AUC of 0.770 across datasets. EvolvedGCN's s mean AUC is 0.764, while GruGCN follows closely with mean AUC of 0. 759. GraphPulse has mean AUC value of 0.849 and has the highest AUC value for eight out of nine datasets.
GraphPulse employs features from both snapshot graphs and Mapper networks within a sequential model. This naturally raises the question: which specific features contribute to the predictive ca- pability of GraphPulse? To address this ques- tion, we conduct an ablation study, where, we uti- lize graph features and Mapper network features in isolation within the same sequential model to predict the targeted graph property. Table in- dicates that the median AUC value for F F'aapstoc" RNN is 0.7981, while for FMagper-RNN RNN, the value is 0.8501. While Mapper-based features result in an overall higher AUC, it's noteworthy that Graph- Pulse achieves considerably higher median AUC of 0.8670, surpassing the AUC of both feature sets in isolation. This observation provides com- pelling evidence that the topological insights ac- quired through Mapper offer complementary information to the snapshot graph- based features.
Table 3: Ablation study. showcasing ROC-AUC values by incorporating graph features Fmuaphht and Mapper network features Fotapar within sequence- based model.
Data
Fmmpshon -RNN
Fiaaper- RNNN
Adex
0,8673 0.0027
0.8831 0.0050
Bancor
0.7981 + 0.0078
0,8501 :: 0.0018
Aragon
0,6898 0.0794
0,8819 0,0014
Dgd
0.7689 0.0090
0.73141
Coindash
0.7676= 0.0025
0.7790= 0.0018
Iconomi
0.8404= 0.0204
0,8417 0.0048
Centra
0.8610= 0.0065
0,8673+ 0.0068
Reddit-Body
0.8690= 0.0070
0.7735 0.0125
Mathoverflow
0.7798= 0.0133
0.7522+ 0.0057
To assess the importance of individual features within the F Muppper-NNe we conduct secondary ablation study within the same sequence model for the Aragon network which has the largest number of nodes and edges per day among our datasets. This study aims to identify key features that sig- nificantly influence the FMaaper-RNN RNN model's per- formance. Table 4 indicates that removing the number of edges (shared nodes between Mapper clusters) causes the biggest drop in AUC values for this dataset. Additionally, effectiveness of GraphPulse through two supple- mentary graph property prediction tests: density growth and node count growth. The detailed results for these tests are presented in Appendix D
Table 4: Ablation study. ROC-AUC values when removing Mapper network feature from Fataper within a sequence based model for the Aragon net- work.
Removed feature
ROC-AUC
Number of nodes
0.8716 0.0087
Number of edges
0.7341 0.0466
Max cluster size
0.8799 0.0024
Average cluster size
0,8650= 0.0089
Average edge weight
0.8530 0.0409
assessed the
Scalability, Due to space limitations, we report the computational complexity and scalability results in Appendix E. Here we note that on the largest token network, GraphPulse completes the training process 26% faster than the time required by the sate-of-the-ard HTGN method. Furthermore, TDA Mapper can process snapshot graphs of 20,000 nodes in under 4 minutes.
7 CONCLUSION
We have introduced GraphPulse, principled approach for predicting graph properties in temporal graphs. By leveraging a combination of snapshot graphs and Mapper networks, GraphPulse capital- izes on both structural and topological insights to enhance prediction accuracy. Through empirical evaluations, we have demonstrated the effectiveness of GraphPulse across diverse datasets, show- casing its superior performance compared to baseline methods. Notably, our approach demonstrates scalability across both training and analysis phases, making it an adaptable solution for large-scale temporal graph scenarios. GraphPulse presents promising advancement in the field of temporal graph property prediction, bridging the gap between structural and topological aspects for accurate predictions.

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY
In line with ICLR's commitment to promoting reproducibility in research, we have taken diligent steps to ensure the reproducibility of our work presented in this paper. We provide open access to our source code, which is available at the following link: https : //github. com/ GraphPull se. This code includes the implementation of our novel models and algorithms, ensur- ing that fellow researchers can readily access and reproduce our experimental results.
ETHICS STATEMENT
We would like to emphasize our commitment to conducting ethical research throughout the course of this study. This research primarily involves the analysis and prediction of temporal graph properties using machine learning techniques. We have taken ethical considerations into account at various stages of our work. Our experiments do not involve human subjects, and we have not accessed any sensitive or private information. The datasets used in this study are publicly available, and for the Ethereum token networks analyzed, the raw data is publicly accessible to anyone on the web. We do not share any address or transaction labels for the token networks. Our chosen graph property, network growth, does not involve any individual address.
ACKNOWLEDGEMENTS
This work was partially supported by the Canadian NSERC Discovery Grant RGPIN-2020-05665: Data Science on Blockchains, the National Science Foundation grants DMS-2202584 and DMS- 2220613, and the Simons Foundation grant # 579977. This research was also supported by the Canadian Institute for Advanced Research (CIFAR AI chair program). Shenyang Huang is sup- ported by Natural Sciences and Engineering Research Council of Canada (NSERC) Postgraduate ScholarshipDocttoral (PGS D) Award and Fonds de recherche du Québec Nature et Technologies (FRQNT) Doctoral Award.
REFERENCES
Lada A Adamic and Bernardo A Huberman. Power-law distribution of the world wide web. Science, (1154461)2215522111 2000.
Jeff Alstott, Ed Bullmore, and Dietmar Plenz. Powerlaw: a python package for analysis heavy- tailed distributions. PloS One, 91)xe85777, 2014.
Albert-Lászió Barabási. Network science. Philosophical
TranaaopaiiaaaTTTatttniiiiooo Transactions of the Royal Society A: Math- ematical, Physical and Engineering Sciences, (71(1187):201 20375, 2013.
Cristian Bodnar, Cätälina Cangea, and Pietro Liò. Deep graph mapper: Seeing graphs through the neural lens. Frontiers in Big Data, 4:680535, 2021.
G. Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2), 2009.
Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signa- tures. Silvia Chiappa and Roberto Calandra (eds.), The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo. Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pp. 2786-2796 Proceedings of Machine Learning Research, 2020. URL http:/ http:::/proceeeingge mlr press/v108. carriere20a html.
Sean Carroll. The Biggest Ideas in the Universe: Space, Time and Motion. Dutton, Hoboken, NJ, 2022. ISBN 9780593186589,
Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers Artificial Intelligence, 4:108, 2021.
Yuzhou Chen, Baris Coskunuzer, and Yulia Gel. Topological relational learning on graphs. Advance in Neural Information Processing Systems, 34:27029-27044 2021.
10

---

Published as a conference paper at ICLR 2024
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. Advances in Neural Information Processing Systems, 34:1713-1726 2021.
Tamal Krishna Dey and Yusu Wang. Computational topology for data analysis. Cambridge Univer- sity Press, 2022.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Oded Galor. Discrete dynamical systems. Springer Science & Business Media, 2007.
Jianfei Gao and Bruno Ribeiro. On the equivalence between temporal and static equivariant graph representations. In International Conference on Machine Learning, pp. 7052-7076. Proceedings of Machine Learning Research, 2022.
Mustafa Hajij, Bei Wang, and Paul Rosen. MOG: mapper graphs for relationship preserving clustering. CoRR, abs/I 804. 1242, 2018. URL htttt::/aaxxv..orgo.e 1b1r////bbb184.122......
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. Advances Neural Information Processing Systems, 32, 2019.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. International Conference on Machine Learning, pp. 4314-4323, 2020.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2): 109-137,, 1983.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borg- wardt. Topological graph neural networks. In International Conference on Learning Representa- tions, 2021.
Shenyang Huang, Yasmeen Hitti, Guillaume Rabusseau, and Reihaneh Rabbany. Laplacian change point detection for dynamic graphs. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 349-358, 2020.
Shenyang Huang, Samy Coulombe, Yasmeen Hitti, Reihanch Rabbany, and Guillaume Rabusseau. Laplacian change point detection for single and multi-view dynamic graphs. arXiv preprint arXiv:2302.01204, 2023a.
Shenyang Huang, Jacob Danovitch, Guillaume Rabusseau, and Reihanch Rabbany. Fast and at- tributed change detection on dynamic graphs with density of states. In Pacific-Asia Conference on Knowledge Discovery & Data Mining, pp. 15-26. Springer, 2023b.
Shenyang Huang, Farimah Poursafaei, Jacob Danovitch, Matthias Fey, Weihua Hu, Emanuele Rossi, Jure Leskovec, Michael M. Bronstein, Guillaume Rabusseau, and Reihaneh Rabbany. Temporal graph benchmark for machine learning temporal graphs. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (eds.), Advance in Neural Information Processing Systems, 2023c.
Ming Jin, Yuan-Fang Li, and Shirui Pan. Neural temporal walks: Motif-aware representation learn- ing on continuous-tin dynamic graphs. Advances in Neural Information Processing Systems, 35:19874-19886, 2022.
Methun Kamruzzaman, Ananth Kalyanaraman, Bala Krishnamoorthy, Stefan Hey, and Patrick Schnable. Hyppo-x: A scalable exploratory framework for analyzing complex phenomics data. IEEE/ACM transactions on computational biology and bioinformatics, 18(4):1535-1544 2019.
Seyed Mehran Kazemi, Rishab Goel, Kshitij Jain, Ivan Kobyzev, Akshay Sethi, Peter Forsyth, and Pascal Poupart. Representation learning for dynamic graphs: A survey, The Journal of Machine Learning Research, 21(1):2648-227 -720, 2020.
Han-Min Kim, Gee- Woo Bock, and Gunwoong Lec. Predicting ethereum prices with machine learning based on blockchain information. Expert Systems with Applications, 184:1 184:115480, 2021.
11

---

Published as a conference paper at ICLR 2024
Danai Koutra, Ankur Parikh, Aaditya Ramdas, and Jing Xiang. Algorithms for graph similarity and subgraph matching. In Proceedings of the Ecological Inference Conference, volume 17. Citeseer, 2011.
Srijan Kumar, William L Hamilton, Jure Leskovec, and Dan Jurafsky. Community interaction and conflict on the web. In Proceedings of the 2018 World Wide Web Conference on World Wide Web, pp. 933-933---33 933. International World Wide Web Conferences Steering Committee, 2018.
Panagiotis Kyriakis, Iordanis Fostiropoulos, and Paul Bogdan. Learning hyperbolic representations of topological features. In International Conference on Learning Representations, 2021.
Ming Li, Paul Vitányi, et al. An introduction to Kolmogorov complexity and its applications, vol- ume 3. Springer, 2008.
Pek Y Lum, Gurjeet Singh, Alan Lehman, Tigran Ishkanov, Mikael Vejdemmo-ohannsoo, Muthu Alagappan, John Carlsson, and Gunnar Carlsson. Extracting insights from the shape of complex data using topology. Scientific reports, 3(1):1236, 2013.
Yuhong Luo and Pan Li. Neighborhood-awwan aware scalable temporal network representation learning. In Learning on Graphs Conference. pp. 1-1. Proceedings of Machine Learning Research, 2022.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems, 32, 2019.
Hadar Miller and Osnat Mokryn, Size agnostic change point detection framework for evolving networks. Plos one, (5(4))e0231033 2020.
Isaac Newton. Philosophiae naturalis principia mathematica, volume 1. G. Brookman, 1833.
Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, and Vito Latora. Graph metries for temporal networks. Temporal networks, pp. 15-40, 2013.
Ashwin Paranjape, Austin R Benson, and Jure Leskovec. Motifs in temporal networks. Proceed- ings of the Tenth ACM International Conference on Web Search and Data Mining, pp. 601-610, 2017.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma. Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B. Schardl, and Charles E. Leiserson. EvolveGCN: Evolving graph convolutional networks for dynamic graphs. Proceedings of the Thirty- Fourth AAAI Conference on Artificial Intelligence, 2020.
Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens Van Der Maaten, Thomas Höllt, Elmar Eise- mann, and Anna Vilanova. Approximated and user steerable tsne for progressive visual analytics. IEEE Transactions on Visualization and Computer Graphics, 23(7):1739- 1752, 2016.
Farimah Poursafaei, Shenyang Huang, Kellin Pelrine, and Reihaneh Rabbany. Towards better eval- uation for dynamic link prediction. Advances in Neural Information Processing Systems, 35: 32928-32941, 2022.
Emanuele Rossi, Ben Chamberlain, Fabrizio Frasca, Davide Eynard, Federico Monti, and Michael Bronstein. Temporal graph networks for deep learning dynamic graphs. arXiv preprint arXiv:2006. 10637, 2020.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In Neural Information Processing: 25th International Conference, ICONIP 2018, Siem Reap, Cambodia, December 13-16, 2018, Pro- ceedings, Part 25, pp. 362-373. Springer, 2018
Gurjeet Singh, Facundo Mémoli, and Gunnar Carlsson. Topological methods for the analysis of high dimensional data sets and 3d object recognition. In Eurographics Symposium Point-Based Graphics, pp. 91-100, 2007.
Amauri Souza, Diego Mesquita, Samuel Kaski, and Vikas Garg. Provably expressive temporal graph networks. Advances in Neural Information Processing Systems, 35:32257-32269, 2022.
12

---

Published as a conference paper at ICLR 2024
Guillaume Tauzin, Umberto Lupo, Lewis Tunstall, Julian Burella Pérez, Matteo Caorsi, Anibal M Alberto Dassatti, and Kathryn Hess. giotto-ida: A topological data analysis toolkit for machine learning and data exploration. The Journal of Machine Learning Research, 22(1):1834-1839 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using I-SNE. The Journal of Ma- chine Learning Research, 9(11), 2008.
Hendrik Jacob Van Veen, Nathaniel Saul, David Eargle, and Sam W Mangham. Kepler mapper: A flexible python implementation of the mapper algorithm. Journal of Open Source Software, (42):1315, 2019.
Friedhelm Victor. Address clustering heuristics for ethereum. In Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers 24, pp. 617-633, Springer, 2020.
Yu Wang, Aniket Chakrabarti, David Sivakoff, and Srinivasan Parthasarathy, Fast change point detection on dynamic social networks. In Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 2017.
Da Xu, Chuanwei Ruan, Evren Körpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning temporal graphs. In 8th International Conference on Learning Represen- tations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL dttps://openreve wee.eeewweeeeeeeeeee...e...eeeee forum?id=zJeWlyyNN
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2018.
Peter T Yamak, Li Yujian, and Pius K Gadosey. A comparison between arima, Istm, and gru for time series forecasting. In Proceedings of the 2019 2nd International Conference on Algorithms, Computing and Artificial Intelligence, pp. 49-55, 2019.
Menglin Yang, Min Zhou, Marcus Kalander, Zengfeng Huang, and Irwin King. Discrete-time tem- poral network embedding via implicit hierarchical learning in hyperbolic space. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 1975-1985, 2021.
Jiaxuan You, Tianyu Du, and Jure Leskovec. ROLAND: graph learning framework for dynamic graphs. Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp. 3356,236, 2022.
Laura A Zager and George C Verghese. Graph similarity scoring and matching, Applied mathematics letters, 21(1) 21(1):86-94, 2008.
Youjia Zhou, Methun Kamruzzaman, Patrick Schnable, Bala Krishnamoorthy, Ananth Kalyanara- man, and Bei Wang. Pheno-mapper: an interactive toolbox for the visual exploration of phe- nomics data. In Proceedings of the 12th ACM Conference on Bioinformatics, Computational Biology, and Health Informatics, pp. 1-10, 2021.
13

---

Published as a conference paper at ICLR 2024
Appendix
A TDA MAPPER & GRAPH TRAJECTORY
TDA Mapper Example. We give a toy example for TDA Mapper networks in Figure 4 where for the point cloud X' we use the height function f X + R as lens. We use 6 intervals I = {I....., I6} detect the clusters in cover of X. In particular, illustrated in Figure 4a, (T2) induces two clusters of points that enclosed by the blue rectangles, while (T, produces a single cluster enclosed by an orange rectangle. The Mapper network in Figure 4c is the nerve of this cover, where each node represents the corresponding cluster and each edge represents that the clusters have non-emply intersections. The final Mapper network gives rough summary/sketch the whole point cloud (Hajij al., 2018). In TDA Mapper graphs, nodes are associated with clusters of data points, and edges are drawn between nodes based on the overlap or commonality of data points between the clusters. The edge weight reflects the strength of this connection, indicating how many data points are included in the overlapped area.
to cover f(Z) (Figure 4b). By using the chosen clustering algorithm,
each f (Ix) for each (Figure 4a). These clusters form elements
A.1 MAPPER TRAJECTORIES
Let G be a graph where a monotonically increasing or decreasing function f. such as the number of unique neighbors, is defined over the nodes, indicating changes by the addition of new nodes or edges. Assume that the addition of new node or edge pair creates a graphlet whose isomorphic copies exist in G. Furthermore, assume that the function remains unchanged over the nodes of G", a modified graph where node features are retained, and over N', the nodes of the new graphlet, which have features similar to those in the existing nodes N (or the changes are for few nodes only and minimal, as in star-shaped graph and new nodes to be added at the periphery). If Mapper is used create 2D representation that assigns data points to specific cubes, the following holds true:
-he addition of N' does not change the position of N within the Mapper network. Specifically, the cluster that contains N can include N' without any modification.
By construction, Mapper identifies clusters based on similar function values. Since N' and N have similar function values, they fall into the same cluster within the Mapper network. The addition of N" does not affect the existing cluster structure since it shares the same function values as N.
Proof:
Consequently, the graphlet's addition to G' does not change the similarity of G to G'.
Proof: Since N and N' fall into the same cluster within the Mapper network, this implies that their topological features are similar in G and G". Therefore, the addition of the graphlet, which did not change the features of N, does not alter the similarity between and G'. In other words, sim(G, G') remains unchanged.
-hee graphlet that added to only changes sim(G, it brings additional information the graph.
a
U1
UP
U3
12
13
14
Is
16
Figure 4: Toy Example of Mapper. For point cloud X' (a), we define lens function X - (b), and the induced covering defines a Mapper network where nodes represent clusters and edges represent related clusters (c).
14

---

Published as a conference paper at ICLR 2024
Proof: By the definition of graph similarity, sim(G, G') quantifies the amount of information shared between the two graphs. If the graphlet introduced into G does not bring any new information or topologiaal changes to G, then sim (G, G") remains the same. It only changes if the graphlet contributes new, distinct features or structure to G.
Kolmogorov complexity Li et al. (2008) supports our argument. Kolmogorov complexity is mea- sure of the shortest possible length of a program that can generate a particular piece of data. In the context of our argument, if the graphlet does not change the structure or features of G, then the shortest program to generate G' and G' remains the same. This indicates that the additional informa- tion brought by the graphlet can be quantified as the difference in program length, further supporting our argument.
A.2 EMPIRICAL EVALUATION FOR MAPPER TRAJECTORIES
To demonstrate the efficiency of TDA Mapper in capturing trajectory (see Figure 8) information within the phase space, we implement the following experimental setup. Initially, we establish a reference graph and construct a grid of neighboring points positioned within the phase space around this reference graph (refer to Figure 6). Each data point within this grid represents a graph instance generated using the specific parameters corresponding its location in the phase space.
Formally, we define nhth -eighhhoooorro (or n-shell) of a graph Gu in the phase space P as the set of all graphs in P whose distance Go is exactly equal with respect to supremum norm. For example, in Figure 5, the red dot represents the reference graph Go. while all light blue graphs represent 1st ---neigbbooroood of Go-
For instance, the reference graph can be an Frdös-Rényl graph characterized by p p= 0.5 and n = 50. Its phase space neighbors are produced by increasing and decreasing the values of n and p. resulting in a graph with the chosen parameter pair. Consider Figure 5 as an example; an immediate neighbor, neighbor 7, is generated with p 0.5 and n 51.
Within this grid, we establish two key criteria. Firstly, ref- erence graph should exhibit greater similarity its 1-hop neighbors compared to those beyond 1-hop. Secondly, the h-hop neighbors should possess similarity values that are nearly identical since they are equidistant from the reference graph.
graee
segienctteed giople
2dd redploourouu gosle
wnghhour gropis woggheastte proplo
To this end, we choose Erdōs-Rényi graphs (Erdōs & Rényí, 1960) for their widespread usage and Stochastic Block Models (Holland al., 1983) for their ability to capture community structures within networks. We ex- perimented
Figure 5: Erdös-Rényi Graph neigh- bourhoods. The red dot indicates the reference graph, with its neighbourhood graphs in the phase space. first neigh- bourhood indexed from I to 8.
sample of 250 reference graphs gener- ated by the Erdös-Rényí graph generator where we varied the number of nodes n from 30 50 and p from 0.21 to 0.4 to make the phase space. For the Barabási-Alber model, the phase base is defined with the number of nodes from 120 to 500 and the number of edges to attach from a new node to existing nodes m from 20 to 100. We randomly choose the value for each parameter for each model 50 times and use that combination of parameters to generate reference graphs five times.
Graph Similarity Measure.
There are numerous graph similarity measures (Zager & Verghese, 2008). In our experiments, we use the eigenvalue method for graph similarity measure (Koutra et al., 2011), where graph similarity is defined based on the eigenvalues of the graph Laplacian. We chose this method because it allows us to compare networks of different sizes, which is ideal for temporal graphs where nodes and edges vary across time snapshots. The eigenvalue method involves utilizing the eigenvalues of the graph Laplacian, and it proves to be suitable for our specific scenario.
Let A, and A₂ be two adjacency matrices of graphs G1 and G2, respectively. Let L1 = D1-A1 and L2 D2-A2 be the Laplacians of the graphs, where D, and D2 are the corresponding diagonal matrices of degrees. Considering that the eigenvalues of L, denoted ()91, 11z;))y... ...). we define
15

---

Published as a conference paper at ICLR 2024
Random Graph Generator
TDA Mapper
P increasss
n incrroases
Extract Node Teatures
Neighbwwsrhodd
1st Neighbonrrioo
nd Neighibourhood
Average Similarity
Neighbourhhod
3 Neightwrrlood
Original Graphs
TDA Graphs
Neighbowrhoo
4th Neiighnnurhood
4 Neighlourhood
1"203 g
4"
Figure 6: Simulating Graph Similarity. We generate k graphs using a graph generator model (e.g., Erdós- Rényi) with parameters (p and n). Average similarity to neighbors in phase spaces is computed, revealing insights into graph continuity across parameter values.
the similarity between the graphs follows:
(9 92) = = - X21)²
where & the smallest value that satisfies the following condition:
S AU
D مد d2 An EE Azi
min
> 0.9
It is understood as the top k eigenvalues containing 90% of the energy Koutra et al. (2011). Please note that this method yields unbounded similarity scores within the [0, oo) range. When the dissim- ilarity score approaches O, it indicates a high degree of dissimilarity between the graphs, whereas higher values suggest greater dissimilarity (Koutra al., 2011).
Similarity Score Comparison. Having selected sim- ilarity function, we now turn our attention to how we compare the Mapper trajectories with those of the snap- shot graphs. Figure illustrates the main idea our ex- periments for comparing the similarity scores of origi- nal graphs and their topological counterparts.
Original graph
Sietienly score
Cuttut eairs Sotan
TDA goaph
Sietkrly
First, for any graph G. we use TDA Mapper to induce summary graph (which the Mapper network of g) by using its node features. We consider the following features to represent the nodes: PageRank, Degree Cen- trality, Closeness Centrality, Betweenness Centrality, clustering coefficient, and the number of neighbors. We consider these features because they can be computed from any graph without node or edge labels, which is preferable our setting where labels might be difficult to collect. For each graph G, the nodes V are represented as point cloud Xe in the feature space Ndd xd Then, by applying TDA Mapper on the point cloud Xg C R-Nxd we obtain its Mapper network lg..
TDA Nipppee
Figure 7: Similarity score comparison. Using original graphs and extracted TDA Mapper graphs based on original node features for similarity score comparison.
Now, consider two neighhoring graphs 91 and G2 in the phase space (e.g., Rrdös-Rényi, Barabási- Albert), and let their similarity score be 812, i.c. $12 sim(G G2). Now, let I and I'2 be their induced Mapper networks. Let Ç12 be their similarity score, i.c., S12 = 1,, By our definition, if (12 smaller than 812, then the induced Mapper networks more similar to the original graphs. This interprets that Mapper networks inherit the similarity information better than the original graphs, hence they capture graph trajectory better.
Results. Tables and 6, we report the median similarity scores for original graphs and TDA Map- per networks in log base for both Frdös-Rénn and Barabási-Albert setting. Due the unstable
16

---

Published as a conference paper at ICLR 2024
Trajectory
201--112
2017 2017-00--1
apha
2017-07-11
207.00-10
2017-07-8 87
300 400
500
000
700
Nodess
Figure 8: Adex Network Trajectory. A seven-day trajectory for the Adex network within the phase space of a and [V.. assume that the network follows a power law model (Adamic & Huberman, 2000), and fit graph data to compute the exponent of the model (see appendix C). For the network, the power law exponent a moves from 2 to 16.
frequency of outliers, hoods instead of the mean since the median is more robust to outliers than the mean. However, both Mapper networks and original graphs become increasingly dissimilar the reference graph the distance (modeled with the k-hop neighbourhood) in the phase space increases. Considering this, see a significant increase in the similarity score in the original graphs while the induced TDA Mapper networks remains highly steady.
the median calculate the average similarity of four neighbour-
Table 5: Dissimilarity scores in the Erdös Erdös-Rényi setting with their standard deviations.
Neighborhood TDA (log10)
Original (log1o)
OTDA
Oorsginal
0.9364
2.0726
0.15
0.25
0.9430
2.6166
0.11
0.23
0.9548
2.9731
0.09
0.22
0.9769
3.2091
0.08
0.22
Table 6: Dissimilarity scores in the Barabási-Albert setting with their standard deviations.
Neighborhood
TDA (logno)
Original (logno)
OTDA
Ooriginal
0.9392
3.6165
0.33
0.20
0.9516
4.0612
0.31
0.19
0.9756
4.3289
0.32
0.20
0.9797
4.5013
0.30
0.20
Figure 9 shows that TDA Mapper yields nearly identical dissimilarity values for the neighbors of the reference graph. The result further offers evidence that TDA Mapper based trajectories would better capture the graph's moves in the phase space.
With the two criteria fulfilled by these empirical results, we conclude that the TDA Mapper can efficiently capture and model graph trajectories in the phase space.
17

---

Published as a conference paper at ICLR 2024
Neighoourood
Negieoumoood
20
orggagl
10
Negioour Indko
Aegiibou Tibee
(a) Prdós-Rényí setting.
(b) Barabási-Alhert setting.
Figure 9: Initial Neighbourhood Comparison. Comparison of similarity scores in the initial neigh- bourhood for Erdōs-Rényi and Barabási-Albert configurations. Refer to Figure 5 for neighbor in- dices. Given the proximity of these neighbors to the reference graph in phase space, expect their dissimilarity to exhibit both low variability and similarity among themselves. Notably, TDA Map- per scores demonstrate greater stability and lower values than the dissimilarity scores of the original graphs.
Stability of Mapper networks. We also want to underline the stability of Mapper networks with respect to small changes, and in particular, their robustness against noise. As Figure shows ev- ery reference graph (red dot) has 8 neighbors (light blue dots) in their first neighbourhood in 2-parameter phase space (e.g., Erdös-Rényí, Barahásii-llerrt) In Figures the first neighbourhoods of the reference graphs, and give the average similarity scores between the reference graphs and these graphs in their first neighbourhood for both Erdös-Rényi. Barabási- Albert settings. Changes in the Erdós- Rénnyi and Barabási-Albert parameters result in fluctuating the dissimilarity score between the original and reference graphs. Each time new neighbor graph is created, the number of nodes and probability p increases or decreases by 2 and 0.05, respectively. These small changes are considered as noise to the graph's trajectory. While there is a fluctuation in dissimilarity scores between the original graph, dissimilarity scores between TDA graphs stable. Therefore, it is concluded that the TDA method is robust to the noise of graph trajectory.
and 9b, we consider
A.3 FEATURES FOR TDA MAPPER
To induce our TDA Mapper networks for given graph G, we use the following node features to induce point cloud XG in the feature space RN and follow the method described in Section 3. The node features we use are as follows:
1. Outgoing Edge Weight Sum: For each node in the snapshot graph, this feature calculates the sum of the weights of all outgoing edges connected to that node. It provides information about the total influence importance of the node in sending information to its neighbors.
2. Incoming Edge Weight Sum: Similar to the previous feature, this one calculates the sum of the weights of all incoming edges connected to each node in the snapshot graph. It represents the total influence or importance of the node in receiving information from its neighbors.
3. Outgoing Edge Count:
This feature keeps track of how many edges leave each node in the snapshot graph. The number of other nodes the node directly connected to as well as its level of connectedness
reflected by this.
4. Incoming Edge Count: The number of incoming edges to each node in the snapshot graph is counted by this feature. gives details on how many nodes are connected to single node directly.
A.4 DEPENDENCY ON MAPPER PARAMETERS
The configurability of TDA Mapper is enhanced by its set of hyperparameters. These parameters provide users with the ability customize TDA Mapper's functionality, allowing for alignment with
18

---

Published as a conference paper at ICLR 2024
Table Similarity scores in the Erdös-Rényí setting with "rough" Mapper parameters, which con- stitute an imposed failure scenario.
neighborhood
TDA (log1o)
Original (logın)
OTDA
Ooriginal
0.0
2.0743
0.0
0.28
2
0.0
2.5988
0.0
0.25
3
0.0
2.9810
0.0
0.24
4
0.0
3.2105
0.0
0.25
their specific data and analytical goals. This adaptability facilitates the comprehensive capture and visualization of topological features within diverse datasets. The hyperparameters of TDA Mapper include:
Number of Cubes (n cubes): Number of hypercubes along each dimension of the pro- jected point cloud using the lens function.
Percentage Overlaps overlaa)) Percentage overlap between adjacent cubes calculated along each dimension.
Number of Clusters (cls): Number of clusters in the K-means algorithm that determines the number of inner clusters formed within each cube.
The effectiveness the GraphPulse can be influenced by the choice parameters in the Mapper algorithm.
In experiments conducted A.2, set the hyperparameters as 2, and
cls = 5, w_cubes perc_overlap (gain)= 0.4 induce our Mapper networks, where cls rep- resents how fine the clustering in the point cloud, n_cubes (interval size) represents how big the clusters are, and finally, roverlp represents how fine the connections between clusters are. Our experimental results in Figure show that Mapper net- work representations remain stable under small changes in the phase space.
ANC
noteworthy that the level of view granularity in Mapper is im- portant parameter. If we increase perc_overlap significantly, this will add an edge between most Mapper clusters, and the resulting Mapper network will be very dense (some- times complete) graph. We show this dependency with the following experiment in the following Mapper setting: cls n.cubes 2, and perc_overlap 0.7. In Table 7, that the resulting TDA graphs are summarizing too much, and there is no change in the Mapper network even if the original graphs changing.
Gubos
Ocerlap
Figure 10: Adex Network Mapper Analysis. 3d AUC plot over Mapper parameter for the Adex network. Predictive performance (ROC-AUC) is consistently above 0.8 for the region 0.2 overlap < 0.45 and 4 < cubes 8.
19

---

Published as a conference paper at ICLR 2024
Table 8: Summary of analyzed models.
Model
Type
Data
Edge Feature
Node Feature
GIN
GNN
(Gn, U U U ... U Gtn
edge weight edge weight
TDA-GIN
GNN
(9,, Uge U U... gt..
mapper cluster membership
EvolvedGCN
TGNN
Gig .i..
edge weight
GRUGCN
TGNN
Gr Gn.9r. ... Gin
edge weight
HTGN
TGNN
g Ir. ... Stn
edge weight
F Fmpppe-RRe RNN
TDA+RNN
TI...., r
edge weight
NA NA
P PauapshotRRN RNN
RNN
g ... Gin ; ... St.
edge weight
GraphPulse
TDA+RNN
edge weight
B BASELINE MODELS
In our evaluation of different models, we included baseline models using Graph Neural Networks (GNNs) and Recurrent Neural Networks (RNNs) to tackle our graph-based based property prediction task. Here, we will provide explanations for all the baseline models employed in our study. Table presents overview of the model summary information.
B.1 GNNS AND OUR MODELS
For the GNN baselines, we employed the Graph Isomorphism Network (GIN) as static model due to its remarkable capacity for capturing both local and global graph structures, making it adaptable for tasks such as graph classification, node classification, and link prediction. Also, we used three state-of-the-art GNN models including EvolvedGCN, GRUGCN, and HTGN as base- lines.
GNNs:
GIN. We extract each snapshot graph and augment it with four essential node features. The follow- ing features are included: Outgoing Edge Weight Sum, Incoming Edge Weight Sum, Outgoing Edge Count, and Incoming Edge Count.
After incorporating these four node features into the graph representation, Based on the chronologi- cal order, the graphs are divided into 80% training and 20% testing data, which are then fed into the model. We employ Graph Isomorphism Network (GIN) model for graph classification. The GIN model consists of four middle layers with 64 hidden units followed by a target output dimension of two, which serves label prediction. We use Adam optimizer with learning rate of 0.0001.
TDA-GIN. The TDA-GIN method is a two-step approach that builds upon the previous static GIN method. First, we extract the same graph with the four node features explained earlier for each node. Additionally, we leverage these node features as input for TDA Mapper algorithm, which forms clusters by grouping similar nodes together. This process yields a new TDA graph, and for each node in this graph, we incorporate the cluster size as node feature.
We perform grid search on parameter combinations determine the ideal combination of TDA Mapper parameters. We choose the most advantageous combination through this optimization pro- cess in order to produce the most instructive TDA graph for learning and classification. The TDA- GIN method enhances the representation and classification of temporal graphs by incorporating TDA techniques into the GIN framework, leading to better prediction performance.
While TDA-GIN incorporates additional structural information through the TDA Mapper represen- tation, has been observed that for temporal tasks, this method may not always yield improved results. The temporal nature of the data brings challenges related to dynamic changes, time depen- dencies, and evolving patterns, which may not be fully captured by the TDA-GIN approach. As result, the benefits gained from TDA-based graph representations may not always translate into superior performance for temporal graph property prediction tasks.
RNNs: For our RNN baseline, developed a hybrid LSTM-GRU model, combining the strengths of both architectures to address the specific challenges posed by our dataset and task. A hybrid LSTM+GRU model often exhibits superior performance compared standalone LSTM and GRU
20

---

Published as a conference paper at ICLR 2024
models due to its ability to effectively combine the unique advantages of both architectures. LSTM excels at capturing long-range dependencies in sequential data, making it suitable for tasks involving context over extended sequences. On the other hand, GRU is computationally more efficient and can capture short-term dependencies effectively (Yamak et al., 2019). By blending these two architec- tures into a hybrid model, we harness the capacity capture both short and long-term dependencies simultaneously. This enables the model to better understand the complex temporal relationships present in the data, which might be challenging for standalone LSTM GRU models to grasp in- dividually. Moreover, A hybrid LSTM+GRU model leverages the diverse internal structures and regularization mechanisms of LSTM and GRU models to improve performance and generalization in sequential data tasks, making it versatile choice. This combination creates an ensemble- effect, enhancing the model's ability to capture different data features and reduce overfitting risk.
F Samppshol -Rais RNN. The - -NNN method entails building a temporal daily pipeline to capture the temporal component of the data. We extract daily graphs for each day from each snapshot, which contains seven days' worth of data. We extract three graph-level features from each graph, including the number of nodes, the number of edges, and the average value of edge weights. We give this feature a constant value if the graph is unweighted. After these features are extracted, sequence of three features is created for seven consecutive days, producing a sequence with the shape (7.3) for each snapshot. To carry the classification task, hybrid LSTM-GRU model gets these sequences and their corresponding labels. Based on the chronological order, the sequences are divided into 80% training and 20% testing data, which are then fed into the model. Our RNN model consists of two LSTM layers, two GRU layers, and a dense layer for classification. Each snapshot has binary classification labels in the model's output. The AUC-ROC the evaluation metrie employed for this task.
F Mapper--RR RNN. The FMapper-RNe RNN method consists of two main steps. In the first step, similar to the previous model, we construct daily graphs from the temporal data. For each daily graph, we utilize the four features previously discussed the initial section to generate a TDA graph. This involves extracting the four features for each node in the daily graphs and subsequently constructing TDA Mapper network for each individual day.
From the TDA daily graphs, we extract five additional features, namely the number of nodes, the number of edges, the maximum cluster size, the average cluster size, and the average value of edge weights with the shape (7,5) for each snapshot. These features are then used to create a sequence representing seven consecutive days. This sequence is fed into the same LSTM-GRU model de- scribed before for the classification task. The subsequent steps are identical to the previous model. The sequences are partitioned into 80% training and 20% testing data, based on the chronologi- cal order, and are employed as input for the hybrid LSTM-GRU model. The model outputs binary classification labels for each snapshot, and the performance is evaluated using the AUC-ROC metric.
B.2 TEMPORAL GRAPH REPRESENTATION LEARNING METHODS
Our work relates to graph representation learning in a dynamic setting. Here, we further elaborate temporal graph learning methods considered as basclines and provide the experimental details.
EvNlveGCN (Pareja et al., 2020) captures the dynamism of a graph sequence, EvolveGCN adapts a GCN architecture and uses an RNN to evolve the GCN parameters through the temporal aspect. In this way, the weights of the GCN are dynamically and automatically updated by the RNN module allowing the GCN module to change even during the test time.
GCRN (or GRUGCN) (Seo et al., 2018) is a deep learning model aiming to predict structured sequences of data. GCRN basically exploits CNN architecture and applies to the graph data to identify the spatial structures. Furthermore, it utilizes an RNN module on top of that to encompass the dynamic of the network.
HTGN (Yang et al., 2021). While most temporal graph representation learning methods focus on modeling structural and temporal dependencies in Euclidean space, Hyperbolic Temporal Graph Networks (HTGN) grasp the high capacity and hierarchical awareness of hyperbolic space. HTGN utilizes hyperbolic graph neural networks and hyperbolic gated recurrent neural networks to capture the evolutionary patterns of dynamic graphs
21

---

Published as a conference paper at ICLR 2024
It noteworthy that these methods mainly optimized for node-level tasks namely node classifica- tion. Since we are focusing on the graph property prediction task, we modify the decoder component of these methods. In particular, we added pooling layer on top of the encoder module to provide graph-level representation. The output of the pooling layer is then fed to the final classifier for the downstream task of graph property prediction.
Experimental Details. The experimental parameters are set according to the best practices proposed in baseline methods (Yang et al., 2021). For all these methods, used the in-degree, out-degree, weighted in-degree, and weighted out-degree of the nodes as their initial features. We set the final embedding dimension as 16, and used mean-pooling layer for generating graph-level representa- tions. All methods are composed of one layer of recurrent units and two-layer graph convolutions. For HTGN, the number of historical windows the HTA module set 5. For all methods, we utilized chronological %80-%2% %20 split of the graph snapshot sequence as our train-validation and test data, respectively.
C THE PHASE SPACE FOR TOKEN NETWORKS
A token network on Ethereum can be conceptualized as dynamic graph-based decentralized ecosystem. In this ecosystem, nodes represent participants or entities within the network, which can include users, smart contracts, even devices. Edges between nodes symbolize various inter- actions and transactions involving tokens. These interactions could include transfers, trades, or other token-related activities.
We model token networks as power law graphs Adamic & Huberman (2000) where the phase space is given with [V] and the exponent a. In power law graphs, P(x) o r- a where x is the node degree. Table 9 shows the a values, as described by Alstott al. (2014), for token networks. A high alpha indicates that there are fewer nodes with very high degrees (hubs) compared to nodes with lower degrees. This leads to more concentrated distribution, where small number of nodes have extremely high degrees, and the majority nodes have relatively low degrees. Different real-world systems exhibit different alpha values, reflecting the diversity in the distribution of node degrees. For instance, in the World Wide Web, alpha values typically range from 2 to 3 Adamic & Huberman (2000). As the table shows, the token networks exhibit significantly high values.
Table 9: a values for the power-law distri- butions of the degree distributions of 7 token datasets
Data
ax
Adex
4.4387
Bancor
3,8886
Aragon
3.3336
Dgd
3.3696
Coindash 4.8846
Iconomi 3.3369
Centra
3.7404
D ADDITIONAL GRAPH PROPERTIES
In addition to network growth in edges, we have carried out two experiments to test the predictive power of GraphPulse: predicting the network growth in node count and density.
Table 10 displays the results of the node count experiments. Among the nine datasets utilized in the experiment, GraphPulse achieves the highest AUC in five datasets and the second -roond-hgghest AUC in the Iconomi dataset. EvolveGCN attains the highest AUC value in the four datasets; however, it produces poor results Adex and Coindash. Among the methods, GraphPulse boasts the highest mean AUC (0.8044). HTGN consistently delivers high AUC results, consequently achieving the second- highest mean AUC at 0.7912.
Table 11 illustrates the results for the density property prediction experiments. In this task, Graph- Pulse outperforms other methods in four of nine datasets and is the second-best method in the Bancor and Aragon datasets. EvolyeGCN attains the highest AUC value in three datasets; however, it pro- duces poor results in Coindash and Bancor. HTGN and GRUGCN both achieve the best result in only dataset. Among the methods, HTGN has the best mean AUC (0.7558). GraphPulse has
22

---

Published as a conference paper at ICLR 2024
the second-best mean AUC (0.7403) however GraphPulse has the best median value (0.7832) and consistently delivers high AUC results for all of the datasets with AUC higher than (0.65)
Table 10: ROC-AUC results for the graph node count prediction task.
Dataset
GIN
TDA-GIN
EvolveGCN
GRUGCN
HTGN
GraphPulse
Adex
0.5499
0.5002:1:00180
0.56991:0360
0.5566:203141
0.7720=0.1100
0.8024
Bancor
0.4724
0,58791000627
0.8078
0.8165:t0..20
20.859
0.8182:+0.115
Aragon
0,5121 =:000188
0.4880++0.0096
0,7020
0.6637
0.6335=0.0223
0.7416=000166
Dgd
0.5400 0.5334.+0.0519
0.8291 +:00609
0.7497
0.7851 +:00006
Coindash
0.4582.::0.066
0.4637
0.6055
0.7900
0.7969
0.8077:+000067
Iconomi
0.6515=+0.0200
0,5512:t0.0335
0.9086-10.0110
0.8505==0.0200
0.8334
0.8582++0.0069
Centra
0.5034=+0.9991
0.5637
0.8221
0.8726::0.0035
0.8753
0.8790=0.0001
Reddit-
0.5365:+00041 0..099
0.9408
0.8147 1:00516
0.8289
0. 0.7283:+0.0092
Mathoverflow
0.6314:t0.0633
0.4559
0.9257
0.8352::0.0185
0..033
0,8404110,001
Table 11: ROC-AUC results for the graph density prediction task.
Dataset
GIN
TDA-GIN
EvolveGCN
GRUGGN
HTGN
GraphPulse
Adex
0.47631000645
0.492910.0206
0. 0.7.34-10.3007
0.7234410.0040
0.7356:10.2419
0.79388100017
Bancor
0.5322010.096
0.5529:44.20
0.58 101
0.8120
0.7492+200753
0.7661 +400007
Aragon
0.4571 1:9.
0.4896:100014
0.7938 10.0887
0.6419::00151
0.6680
0.7832-100050
Dgd
0.5228:+0.0555
0..475
0.871 1 +200292
0.7881 I +:002744
0.8171 =0.0000
0.7958:20.008
Coindash
0.4326
0.4694-10.04m
0.5021 1 15.1506
0.7744410.001
0.7767 0..679
Iconomi
0.7209::00058)
0.5086
0..046::0.0082
0.8927 +:00085
0.8784
1..444
Centra
0.3991 +:004117
1.5622210.0074
0.7196:10.1611
0.8434
0.8491 1.00017
0.8008:10.0000
Reddit-Body
0.4014:10.069
1.5329440.022
1..007.+0.0437
0.6055 1.00633
0.7270 0.0027
Mathoverflow
0.7421 1 +:0.0469
0.5133
0.6720:t0.1883
0..035....0352
5.000352
0.7475
0.00284
0.68446:0001000
E SCALABILITY ANALYSIS
The computational cost of GraphPulse is dom- inated by the cost of reducing our 4D feature data to a 2D form to be used by Mapper. We have used (SNE (Van der Maaten & Hinton, 2008) for the reduction which has a quadratic computational complexity in the number of data points. The cost can be significantly re- duced by using (SNE approximations (Pezzotti et al., 2016). We leave this improvement to future work. Once a lens is selected, creating the TDA Mapper network involves sorting data points (graphs), which is an (n logn) opera- tion where n is the number of graphs.
cost Dgd
100
We demonstrate GraphPulse's scalability through two key aspects: end-to-end model training costs for the most resource-intensive dataset, and the computational overhead of Mapper analysis for daily snapshot graphs.
Figure 11: Methods Training Time. Comparison of Training Time for Methods the Dgd Net- work. GraphPulse completes the training process 26% faster than the time required by the state-of- the-art HTGN method.
Figure 11 illustrates the computational time re- quirements of the considered models on the Dgd network, which boasts the largest number of snapshots (720). Notably, GraphPulse completes training in 1550 seconds, while HTGN demands over 2100 seconds for the same task.
The processing time of GraphPulse encompasses three distinct stages: the extraction of TDA se- quences, the extraction of daily sequences, and the training of the RNN model. Notably, the TDA
23

---

Published as a conference paper at ICLR 2024
TDA costs of daily token networks
Tranecttio Networks
Regisssicn Line
TDA costs of large size graphs
800
600
Time
800
101
200
10000
2000
3000
4000
750
1000 1230
1500
1730
Nodes
Node
(a) Daily cost of TDA Mapper creation for all token networks. Each data point snapshot graph from a token. As shown, most of the daily graphs have less than 750 nodes.
(b) The cost of extracting TDA features for graphs using the Erdös Rényyi graph generation model with p 0.3.
Figure 12: TDA Mapper Scalability. The daily cost of TDA Mapper for token networks is il- lustrated in (a). The mapper cost has a direct relation with the size of the graph. (b) shows the increasing cost of TDA Mapper with the growing size of the graph.
sequence extraction phase is the most time-consuming component of this process. Consequently, the overall execution time for GraphPulse and I'Mappe-RNN is significantly higher when compared the - RNN model, primarily due to the additional computational requirements of TDA sequence extraction.
Given that the extraction of TDA sequences constitutes significant portion of GraphPulse's pro- cessing time, we conducted comprehensive analysis focused on the daily TDA cost. Figure 12 presents the outcomes of this analysis, shedding light on the question of how substantial the daily cost can be while still permitting efficient TDA processing. Remarkably, the results illustrate that TDA remains highly effective, even with graphs containing approximately 20,000 nodes, processing them in under 4 minutes. Furthermore, the experiments reveal that majority of the daily networks processed exhibit fewer than 1,000 nodes, ensuring swift processing. This evidence underscores the scalability of TDA for real-world daily graphs within the GraphPulse framework.
These results collectively underscore GraphPulse's outstanding scalability in temporal graph ma- chine learning. By efficiently managing training costs and Mapper analysis, GraphPulse offers high degree scalability across various datasets, establishing its suitability for larger and more complex temporal graph scenarios.
24


Reviews:
[{"review_id": "MNVPO9aVKB", "reviewer": "Reviewer_ehy4", "summary": "GraphPulse is a novel framework proposed for analyzing and predicting the evolution of temporal graphs through a combination of temporal graph neural networks and topological data analysis (TDA). The paper presents a process that takes snapshots of temporal graphs at fixed intervals, constructs TDA Mapper representations for these snapshots, and then uses these topological features along with snapshot graph features for sequential modeling to predict future graph properties. The paper claims superior performance over existing models in predicting network growth on several datasets, including new cryptocurrency network datasets.", "questions": "1) How does the algorithm perform on other prediction task in addition to the growth rate prediction. Possible metrics include temporal global efficiency, temporal-correlation coefficient, temporal betweenness centrality  and more. [1]\n2) What role does the Newtonian dynamics play in the proposed algorithm?\n\n\n[1] Nicosia, Vincenzo, et al. \"Graph metrics for temporal networks.\" Temporal networks (2013): 15-40.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1. The paper pioneers the integration of TDA into the study of temporal graphs, which represents a significant methodological advancement, potentially unlocking new insights into graph structure and evolution over time.\n\n2. The paper is commended for its clear presentation style and the provision of solid supporting materials, which aid in the understanding and reproducibility of the proposed approach. The introduction of TDA Mapper method and the examples given are very helpful for audiences who do not have prior knowledges on TDA.\n\n3. The proposed algorithm's simplicity and ease of implementation make it accessible for broad application across various temporal graph analysis tasks, facilitating its adoption in practice.", "weaknesses": "1. Focusing solely on the growth rate as a graph property is a limitation; the model's adaptability to other graph properties remains unexplored, which could be a significant aspect to consider for comprehensive temporal graph analysis.\n\n2. The omission of key recent models like PINT[1] and ROLAND[2] from the baseline comparisons limits the evaluation's depth, potentially skewing the perception of the proposed model's performance.\n\n3. The introduction of the Newtonian phase space model is an interesting conceptual proposition but remains unexploited in the actual modeling and theoretical justification, which can be seen as a disconnect between the proposed concepts and their practical implementation.\n\n\n[1] Souza, Amauri, et al. \"Provably expressive temporal graph networks.\" Advances in Neural Information Processing Systems 35 (2022): 32257-32269.\n\n[2] You, Jiaxuan, Tianyu Du, and Jure Leskovec. \"ROLAND: graph learning framework for dynamic graphs.\" Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022.", "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": "", "extra_scores": {}}, {"review_id": "xWESXkN4AS", "reviewer": "Reviewer_NvJb", "summary": "This paper studies the problem of temporal graph learning. The main contribution is GraphPulse, which combines structural and topological insights to predict graph properties. Experiments on ER graphs and SBM graphs demonstrate the superiority of the proposed method.", "questions": "See W1-W2 for details.\n\n===== After rebuttal =====\nI would like to thank the authors for answering precisely and comprehensively to my concerns. The extent of work and the additional experiments presented during this period are noteworthy. These efforts have enhanced my understanding of the model's principles, leading me to a more favorable evaluation. Consequently, I have raised my score to 6.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "S1. The problem is well motivated by the need of tracking evolving graphs.\n\nS2. It’s novel to incorporate the topological technical with dynamic graph represent learning. Using TDA Mapper to learn and predict graph trajectory is interesting.", "weaknesses": "W1. The authors use the set of nodes as the input point cloud of the Mapper network, aggregating the summation of incoming/outcoming edge weights and the counts of incoming/outcoming edges to conduct node features. However, there is a notable absence of retained graph structure information when compared to the original graph structure. In my opinion, the overall structure and the connections between nodes are more crucial and directly effective in the process of learning dynamic graphs. I would suggest the authors to incorporate the connection information into the model.\n\nW2. The current assessment of the graph property focuses on determining whether there is a rise or decline in the number of edges, resulting in a fairly limited perspective. I would suggest the authors utilize more comprehensive graph properties to evaluate model capabilities on temporal graphs, such as changing node counts, density, diameter, degree distribution, and the number of triangles. Additionally, rather than binary classification, predicting the specific number of increased/decreased edges would test a finer-grained understanding of edge dynamics.", "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": "", "extra_scores": {}}, {"review_id": "ZTgRYCau7p", "reviewer": "Reviewer_Qyn2", "summary": "This paper introduces a new framework called GraphPulse for predicting the evolution of temporal graphs, combining topological data analysis and recurrent neural networks. One of the most important insights of this study is that the evolution of a graph can be represented as a temporal trajectory in a Newtonian phase space. This advances the understanding of the principle of graph evolution for this research community. The proposed GraphPulse is evaluated on financial and cryptocurrency transaction networks and compared to state-of-the-art methods, showing a significant performance improvement.", "questions": "Is the GraphPulse applicable in link prediction, edge sign prediction in signed networks, edge/node attribute prediction? Compared to the embedding algorithms that are customized for those particular graph mining applications, what are the advantage of the proposed GraphPulse? It would be better to discuss the application conditions of GraphPulse so that the audience knows under what application conditions GraphPulse will get better performance.", "limitations": "", "rating": 8, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. This paper identified that the evolution of a graph can be represented as a temporal trajectory in a Newtonian phase space and conducted comprehensive studies on it. Existing study [1] has pointed out that the evolution of a dynamic graph can be treated as a trajectory in a latent space without further studying what space it is and any properties the space should have. This study advances the understanding of the principle of graph evolution, which I believe is very valuable to this research community. \n[1] Time-Capturing Dynamic Graph Embedding for Temporal Linkage Evolution, TKDE.\n2. A novel temporal graph embedding framework is proposed, which is highly effective at capturing the evolution of temporal graphs in the phase space. The proposed GraphPulse is technically sound.\n3. GraphPulse demonstrates significant performance improvement compared to state-of-the-art dynamic graph neural networks.\n4. The authors create cryptoasset networks for the temporal graph property task and publish them as temporal benchmark datasets for future research.", "weaknesses": "1. It is unclear how hyperparameters sensitive the model is.\n2. Since GraphPulse is a generic framework applicable to extend the embedding algorithms to embed a temporal graph, the generalizability of GraphPulse should be discussed and tested. It is suggested to replace Mapper with two or more static graph embedding techniques to test the impact on GraphPulse.\n3. There are some typos. For example, in page 18, there are two different “neighborhood” styles of writing.", "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": "", "extra_scores": {}}, {"review_id": "xtv6RYdT4l", "reviewer": "Reviewer_yFgn", "summary": "The paper proposes an approach (GraphPulse) for learning on Discrete Time Dynamic Graphs (DTDGs). GraphPulse relies on the mapper method (a Topological Data Analysis technique used to compress high dimensional data in a small and comprehensible graphical representation) to extract latent topological properties of each graph snapshot. More in detail, provided a sequence of graphs (G_1, G_2, …, G_N), for each graph G_i, the authors extract a finite set of “snapshot” features describing the general properties of G_i (i.e. the\nnumber of nodes, the number of edges, and the average value of edge weights). They then proceed at computing for G_i a compact graphical representation using the mapper method, and from the obtained graph they extract 5 new “mapper” features (the number of nodes, the number of edges, the maximum cluster size, the average cluster size, and the average value of edge weights). The snapshot and mapper features of each graph are then fed in input to a sequential model (LSTM+GRU), which outputs a prediction for the sequence of graphs. To evaluate their method, the authors defined a network growth problem where they aim at predicting whether a given network in a future interval will show more edges than in the past or not.", "questions": "I found it interesting that the authors handcrafted a feature descriptor for both a snapshot and the mapper network. While reading the paper I was expecting to see a GNN for extrapolating graph-wise features that would have then been used in input to the recurrent model. This would have provided (ignoring the construction of the mapper network with a fixed lens function) an end-to-end learnable approach that would have indeed suited a generic classification problem. I wonder if the authors have experimented with such a solution in their experiments and whether this could provide a further boost in performance.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper illustrates an interesting application of a Topological Data Analysis technique for constructing a model able to tackle prediction tasks on DTDGs. While the approach is not quite straightforward to explain due to the multiple steps that are involved, the paper is generally clear (see although some weaknesses on this below). Experimental evaluation on a variety of datasets show good performance of the method for the considered task.", "weaknesses": "While I found the manuscript rather interesting and generally well presented, in some parts I had some difficulties completely understanding the paper. For instance, in Section 3, the clustering method is not really introduced in the mapper method and I found it difficult at first to understand the role that this would have in the overall approach. Similarly, in the experimental section I did not find details on what clustering algorithm or lens function the authors used for computing the Mapper Network (edge weights for the mapper network and mapper hyperparameters in Section 6 are also not defined in the paper). I would greatly appreciate it if the authors could provide some details in their rebuttal on this to clarify my understanding of their paper (and in general improve readability).\n\nFor what concerns the experimental evaluation, the results look promising, however I wonder if using a GIN as a static GNN baseline might not be fair. The goal of the model is to predict whether in a future window of time there will be more edges in the graph than in the past. As such, being able to understand whether the network is growing in size (or not) over time seems a priori a meaningful feature for the model. This information can however not be captured with a GIN, as the only features this has access to are: Outgoing EdgeWeight Sum, Incoming EdgeWeight Sum, Outgoing Edge Count, and Incoming Edge Count; which do not describe such evolution. For this reason I wonder if decorating edge features with the timestamp associated to the time when an edge appears and using an architecture able to compute graph embeddings based on edge features (e.g. a MPNN) could be a better baseline for the given prediction task.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)