GraphPulse: Topological representations for temporal graph property prediction

We thank the reviewer for their time and valuable feedback.

W1 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)

A: Thank you for your valuable feedback. We have addressed your comments by adding parameter definitions to the Appendix A.4. We added further clarification for our lens and clustering methods in Section 6 of the main paper. Moreover we included a definition for edge weight in TDA graphs in Appendix A. Your feedback helped us further improve the clarity of our paper. We will also address your comments below. For the lens function, we are using a 2D-TSNE and for the clustering algorithm, we used the KMeans algorithm for clustering the points inside each cubes. Also regarding the hyperparameters definition of the TDA mapper, our mapper includes three hyperparameters:

• Number of Cubes (n_cubes): Number of hypercubes along each dimension of the projected point cloud using the lens function.

• Percentage of Overlaps (perc_overlap): Percentage of 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.

Finally, 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.

W2 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

A: Thank you for the review. In fact, static baselines are a good first check on what graph neural networks can achieve but we do not expect them to yield SOTA results in temporal graph tasks. For this reason, we employ three well-known SOTA methods in our experiments and show that GraphPulse outperforms all of them. In response to your suggestion, we conducted a new experiment for the time stamped Adex dataset. We introduced the time (day) of edge appearance as an additional edge feature in our GIN model. Indeed, as you suggested, these modifications led to notable improvements in the static GIN results. Overall, we still observe that our GraphPulse method and other temporal baselines outperforms static GIN as expected.

Q1 I wonder if the authors have experimented with such a solution in their experiments and whether this could provide a further boost in performance

A: Thank you for your suggestion. Indeed, designing an end-to-end learnable approach is an interesting idea and your suggestion is employed by the EvolveGCN method, which is a baseline compared in our experiments. The input to EvolveGCN is a sequence of graph snapshots and it captures the network's dynamic by using an RNN to update the GCN parameters over time. Here, for each timestamp, all the node embeddings are aggregated (via mean pooling) to generate a graph-level embedding and then EvolveGCN is adapted to train end-to-end for the temporal graph property prediction task. Empirically, we show that our GraphPulse method consistently outperforms EvolveGCN. We plan to explore the possibility of applying Mapper directly to the graph without relying on node features as a future direction for an end-to-end approach based on GraphPulse.

Thank you for your response, that clarifies my last doubt. In light of the review and the additional experiments of Tables 10 and 11 the authors provide, I'm willing to raise my score to acceptance

We thank the reviewer for their time and valuable feedback.

W1 It is unclear how hyperparameters sensitive the model is.

A: Thanks for raising this point. Due to the page limit for the main text, a comprehensive hyperparameter sensitivity analysis was included in Appendix A.4. The key finding from this analysis is that within a well-defined and extensive region within the hyperparameter space, GraphPulse consistently achieves the best performances, with an AUC exceeding 0.7 as illustrated in Figure 10.

W2 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

A: We thank the reviewer for raising this question. We believe that the topological information extracted from Mapper is a key component to GraphPulse as seen in experiments (Section 6) and using Mapper in GraphPulse is an important architectural choice. In terms of generalizability, GraphPulse can generalize to multiple graph properties such as growth, density, node count, and more, and achieve SOTA performance on all of them. We also tested GraphPulse extensively on nine networks from two distinct domains and GraphPulse is able to generalize to all of them with strong performance on each. Indeed as the reviewer suggested, GraphPulse is a generic framework that could incorporate other embedding algorithms and future work can utilize additional embedding algorithms.

W3 There are some typos. For example, in page 18, there are two different “neighborhood” styles of writing

A: Thank you for the review. We will consolidate our writing and remove one of the conflicting styles. We have fixed the neighborhood issue in the paper.

Q1 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?

A: We thank the reviewer for discussing this point. We design the GraphPulse framework to generate graph level embeddings for the temporal graph property prediction task. Edge level tasks such as link prediction and edge sign prediction are not directly applicable for GraphPulse. However, the topological features captured by TDA also provide node embeddings which can be beneficial to node and edge level tasks.

The real advantage of GraphPulse is that it represents graphs in a Newtonian phase space, as illustrated in Figure 8. By constructing the phase space, we can treat the graphs as if they were particles in a dynamic system. This enables us to predict the trajectory of the graph, i.e., where the graph will be at the next time step, based on its current state. Based on the trajectory, we can predict new nodes (in Figure 2a, the first two graphs where a node is added), we can predict motifs (Figure 2a, the third graph is developing triangles and can be expected to get denser), we can identify node features (Figure 2a, leaf nodes co-appearing in the mapper cluster having similar features). GraphPulse allows for customized applications due to the fact that the mapper tool is highly customizable, and once the mapper network is created, we can represent graphs, node subsets or edge subsets in a phase space to be used by GraphPulse.

We thank the reviewer for their time and valuable feedback.

W1 I would suggest the authors to incorporate the connection information into the model

A: We thank the reviewer for raising this point. In this work, we focus on the graph property prediction task which requires a global understanding of the graph structure. Empirically, we find that the combination of Mapper representation and aggregated node features outperforms SOTA temporal GNNs based on local message passing. This might be because GraphPulse can effectively capture a global view of graph evolution based on simple node statistics and node features. In the literature, it is known that classical message passing based GNNs can suffer from various issues such as limited expressiveness (up to 1-WL test), over-squashing, and over-smoothing. How to best capture the global graph structure for GNNs remains one of the open research directions. Thus in this work, our proposed GraphPulse acts as a first approach for temporal graph property prediction and we leave it to future work to further improve upon GraphPulse by further encoding the global graph structure.

W2 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

A: We express our gratitude to the reviewer for bringing up this point. In this work, as a first approach, we formulate the temporal graph property prediction task as a binary classification task indicating the increase/decrease of graph properties in the future. This formulation can directly be applied to important applications such as deciding if the number of transactions in a cryptocurrency network will grow in the future or if the number of users will increase in a social network. As the reviewer pointed out, the next step would be to predict the extent of growth and decrease as a regression task which is left as an important future work due to the fact that regression tasks are much less studied in graph representation learning literature in general as compared to classification tasks and they pose additional challenges; for example, the magnitude of different properties can vary significantly over time.

We also thank the reviewer for suggesting additional graph properties for evaluation. In this rebuttal, we have experimented with two additional properties, namely density and node counts (as kindly suggested by the reviewer). The detailed results are reported in Table 10 and Table 11 in Appendix D and we observe that GraphPulse performs the best overall. This suggests that the GraphPulse framework can generalize to a variety of graph properties.

We thank the reviewer for their time and valuable feedback.

W1 Focusing solely on the growth rate as a graph property is a limitation

A: We thank the reviewer for raising this point. Indeed exploring additional graph properties is an important direction. In this revision, we have added two additional properties: graph density and node counts growth in Appendix D, Table 10 and Table 11. We observe that GraphPulse significantly outperforms all baselines, which shows it is generalizable across multiple graph properties.

W2 The omission of key recent models like PINT[1] and ROLAND[2] from the baseline comparisons

A: We thank the reviewer for pointing out these references. The PINT model is designed for continuous time dynamic graphs (CTDGs), a different setting than our discrete time dynamic graph (DTDG) setting and it is non-trivial to extract graph level embedding for CTDG methods as the node embeddings are updated based on each edges (rather than each graph snapshot). ROLAND is a notable work in bringing static GNNs to a dynamic setting (as opposed to a specific new model). While ROLAND is a great framework for dynamic graphs, it is not trivial to compare its problem setting with our considered setting as explained below.

In the live-update setting of the ROLAND, the prediction labels at timestamp $t-1$ (i.e., $y_{t-1}$) are first split into $y_{t-1}^{train}$ and $y_{t-1}^{val}$, where the $y_{t-1}^{train}$ is used for fine-tuning the model and $y_{t-1}^{val}$ is used for validation evaluation. Then, at time $t+1$ where the $y_t$ are observed, the performance of the model is tested. This process is repeated for each time interval, and the average performance over all graph snapshots is reported.

It should be noted that the aforementioned evaluation procedure of ROLAND is different from our considered setting which is in line with the standard fixed split evaluation (adopted in previous works such as EvolveGCN and HTGN). In our evaluation, we construct the training, validation, and test sets by chronologically splitting the available graph snapshot sequence. We evaluate the trained model for every snapshot of the test set, however, the model is not updated based on the test observations.

W3 The introduction of the Newtonian phase space model is an interesting conceptual proposition but remains unexploited in the actual modeling and theoretical justification

A: We thank the reviewer for highlighting this point. By formulating the temporal graph learning problem through the lens of Newtonian space, we establish a discrete dynamical system. This framework allows us to assess our methodology using TDA Mapper through extensive experiments as detailed in Appendix A. It is important to note that a comprehensive theoretical justification for motion in a phase space, even in its simplest form, requires formulating equations for a discrete dynamical system derived from the specific context. In our approach, we opted for a more pragmatic strategy, validating our model within a known phase space and demonstrating its utility across various settings.

GraphPulse undertook the crucial step of ensuring the construction of a valid and valuable phase space. We achieve this validation by using the visually explainable tool; i.e., TDA Mapper (refer to Figure 2). Building on this, the graphs can be directly put into a phase space where their trajectories can be studied. In Figure 8 of the Appendix, we show such a trajectory.

Q1 How does the algorithm perform on other prediction task in addition to the growth rate prediction?

A: We thank the reviewer for the reference (added to the Related Work Section) and for proposing the additional measures that are definitely interesting to explore. As mentioned above, in this rebuttal, we showed that GraphPulse is able to generalize to graph properties including density and node count. Due to the time limit of the rebuttal phase, we are considering adding other properties later in the future.

Q2 What role does the Newtonian dynamics play in the proposed algorithm?

A: The core idea for our temporal framework is inspired by Newton’s laws of motion and we formulate temporal graph property prediction as predicting the trajectory of a motion in a phase space. First, a novel perspective is presented by connecting temporal graph property prediction with discrete dynamical systems, a well-established mathematical field. Second, such a connection allows us to test the hypothesis that our TDA Mapper approach aids in predicting graph trajectories. To validate this, we conducted extensive experiments in various phase spaces with different settings, as detailed in Appendix A. These experiments not only support our intuition but also explain the significance of TDA Mapper in extracting complex feature information from token networks, contributing to trajectory prediction.

Thank you for your thoughtful feedback and for highlighting these important considerations.

Regarding the use of ROLAND as a baseline, we did not include it because ROLAND's framework involves splitting each graph snapshot into a training set and validation set at each step. Given that our focus is on graph property prediction at the graph level, we felt this approach wasn't directly applicable to our work. Our focus was on a standard setting that is closely aligned with real-world applications, where updating models continuously is often challenging due to constraints like model size, data volume, or computational complexity. Additionally, in such settings, test data may not always be reliable for real-time model updates, leading us to adopt an evaluation setup distinct from that of ROLAND.

Regarding the live-update setting, we chose to concentrate on the fixed-split approach as it better reflects scenarios where continuous model updates are not always practical. We acknowledge the significance of the live-update setting, particularly in light of the strong results it has yielded in other works, including ROLAND. Our decision was based on ensuring our model's robustness and relevance in environments where continuous updates may not be feasible.

We sincerely appreciate your insightful questions and hope this explanation clarifies our approach. If you would like to discuss further, please reach out to us by email. Thank you again for engaging with our work.