TMetaNet: Topological Meta-Learning Framework for Dynamic Link Prediction

Q1: A possible weakness is some of the baselines are not very new. Ablation, sensitivity, and robustness studies under the ROLAND setting ?

A1:We have added DeGNN [1] (ICLR23') as a baseline, with experimental results shown below. ∗ indicates statistical significance (p-value < 0.05).

ROLAND setting

WinGNN setting

We are currently implementing [2] and will post the results when they are ready. The results demonstrate that TMetaNet outperforms DeGNN under both ROLAND and WinGNN settings, validating the TMetaNet effectiveness of TMetaNet for dynamic graph learning.

[1] Decoupled Graph Neural Networks for Large Dynamic Graphs [2] SEGODE: a structure-enhanced graph neural ordinary differential equation network model for temporal link prediction

Additionally, we have supplemented the Ablation, sensitivity, and robustness experiments under the Roland setting, with results shown below.

Ablation

Sensitivity MRR

Robustness MRR

These findings are consistent with the results under the WinGNN setting, proving that TMetaNet is also effective under the Roland setting.

Q2: As a submission to a conference related to computer science, the paper could give more space to address how the algorithm is implemented. For example, move the content in the Appendix to the main sections. This will make the paper more coherent and help readers understand how the method is implemented.

A2:Thank you for your suggestion. We will adjust the paper layout to accommodate more algorithmic details.

Q3: The upper part of Figure 2 (G1, D1, G1∪G2) or similar illustration can be additionally presented near the background section to help understand the important concepts.

A3: In Fig 2 (in the main body), $D_1$ should actually be $D(G_1)$, representing the Dowker complex corresponding to graph $G_1$, and we have updated the figure accordingly. Additionally, we have added the definition of $D(G_t)$ in Definition 4.1. In this paper, $D(G_t)$ is equivalent to $D(L_t,W_t)$. The definition of $G_1 \cup G_2$ has been added to the background section, representing the intersection of two adjacent graphs.

Q4:What proportion of nodes are selected as landmarks and witnesses in some exemplary cases? Can the authors present some examples?

A4:Section 6.3 of the paper discusses DZP's parameter sensitivity on the UCI dataset, where ε and δ represent the parameters for constructing landmarks. The statistics of landmarks under different parameters are as follows:

As can be seen from Figure 3 in the main body, the experimental results corresponding to 1_1 are generally better, indicating that too few landmarks will reduce the ability to capture higher-order structures.

Q1: High-order graph information.

A: For higher-order information, we mean various types of graph (sub)structures formed by interactions of multiple nodes simultaneously. Why is this information important and when? Suppose, we design a certain fraudulent scheme for money laundering. To conceal these illegal activities, it is unlikely that only two nodes would be involved (it’ll be easier to identify fraud!). Indeed, to hide criminal traces, money laundering schemes include many parties (nodes). How to identify particular multi-node patterns (i.e., higher-order information) that may be important? We can leverage the tools of persistent homology (PH). PH looks at the graph at multiple resolutions and tracks when specific multi-node patterns (described by simplices of various orders) appear or disappear as we monotonically change resolution scales. Those topological patterns staying with us longer are likelier to be important. (Note the appearance of weird patterns may serve, e.g., as a signal of money laundering.) Generally, wherever the problem at hand can be characterized by the inherent importance of such intrinsic multi-node interactions, e.g., link prediction due to social or protein-protein interactions, extracting higher-order structural information and integrating it into ML model will likely help. Other tasks, such as graph classification may benefit less. What we are doing in this paper is that extract the most essential time-evolving higher-order information for link prediction in dynamic networks and also use it to guide parameter updates in meta-learning models, which to the best of our knowledge has never been done before.

Q2: The stability proof & assumptions.

A: We follow the standard practice in pure mathematics, where each statement in the derivation chain is either justified by previously published results or if it is newly derived, it is properly placed in a context of the previously obtained and published results. Specifically, we have explicitly restated the Lipschitz continuity assumption within our discrete-time DZP framework, and the ε-interleaving and bottleneck distance bound are also adapted to our discrete DZP setting. The theoretical results Theorem B.9, B.10 are new and have not been appeared before.

Q3: Significance.

A: TMetaNet learns learning rates based on corresponding models under different settings (ROLAND & WinGNN). Compared to ROLAND, TMetaNet is more suitable for WinGNN which learns from all snapshots within a certain window length which is also reflected in significance, we have more significant results under WinGNN.

Q4: Essential References.

A: Neural ODEs and Graph Neural ODEs describe dynamical processes on graphs from the perspective of dynamical systems, while SNPE approaches graph probability distributions from a probabilistic inference perspective on high-dimensional data. Our work starts from a known graph structure and leverages higher-order graph topology in a form of time-varying Dowker zigzag persistence, to enhance link prediction performance on dynamic graphs. Given the recent premise of simplicial models for dynamic systems on networks, we believe that combining persistent homology with methods like Graph Neural ODEs would be a highly promising future direction, we will add all suggested papers to Related Work section.

Q5: Limited exploration of real-world noise.

A: Our robustness experiments consider the widely used structural Evasion and Poisoning attacks, and we have added the new Reddit-title experiment under the ROLAND setting. The below table shows that TMetaNet still maintains competitive robustness under the ROLAND setting.

Robustness MRR

Q6: Citations and eqs.

A: We have made the changes in the paper.

Q7: Higher-order graphs & dynamic link prediction.

A: As noted above, we focus on dynamic higher-order graph information, induced by simultaneous multi-node interactions/interdependencies. Correlation methods focus inherently on linear dependencies and are not feasible for assessment of such joint multi-node interdependencies. The suggested papers relate to dynamic systems, assessment of Granger causality in time series using graphs, relational inference on time series through diffusion generative modeling, and structural inference. These papers neither consider higher-order multi-node graph information, nor dynamic link prediction. (However, we believe that our ZDP can potentially be integrated with structural inference). The closest approach to our ZDP is to use network motifs. However, in contrast to ZDP, network motifs are essentially ad-hoc, typically limited to 4-nodes only, are not easily generalizable for weighted networks, and do not enjoy important mathematical properties such as stability.

Q1: Lemma B.3.

A: To clarify briefly: given two tripods $R_1:\mathcal{G}^X \leftarrow W_1 \rightarrow \mathcal{G}^Y$ and $R_2:\mathcal{G}^Y \leftarrow W_2 \rightarrow \mathcal{G}^Z$ , each satisfying temporal consistency, their composite tripod is defined via fiber product: $W=\{(w_1,w_2)\in W_1\times W_2\mid\pi_2^{(1)}(w_1)=\pi_1^{(2)}(w_2)\}.$ Temporal consistency holds because nodes align through intermediate set $V_t^Y$: $(\pi_1^R)^{-1}(V_t^X)\leftrightarrow(\pi_2^{(1)})^{-1}(V_t^Y)=(\pi_1^{(2)})^{-1}(V_t^Y)\leftrightarrow(\pi_2^R)^{-1}(V_t^Z)$

Q2: Task-splitting of Fig.5.

A: ROLAND splits each snapshot $G_t$ into train/val/test sets. The model trains on $G_{t-1}$'s training set, validates on $G_t$'s validation set, and tests on $G_t$'s test set, utilizing all snapshots for both training and testing. WinGNN uses chronological splitting, dividing the sequence into training and testing periods. E.g., in a 6-snapshot sequence, WinGNN uses the first 4 snapshots for training and the last 2 for testing.

Q3: Recent SOTA baselines.

A: We have run DeGNN [1] as a baseline (∗ indicates statistical significance). We found that TMetaNet outperforms DeGNN in both settings. We are currently implementing [2] and will post the results later. The topology [3] refers to the specific connection states between nodes in a dynamic graph and their changes over time. In our paper, we use term topology in terms of algebraic and computational topology on graphs, i.e., shape characteristics of various orders which provide important information about higher-order structural organization of the graph.

ROLAND setting

WinGNN setting

Q4: Scalability of TMetaNet.

A: On ALPHA data, compared to VR complexes Zigzag Persistence, our method reduces the computational overhead by 46% on average per snapshot during complex construction. When dealing with extremely large-scale graphs, we can sample from snapshots or remove nodes according to degree centrality from low to high to obtain subgraphs that preserve global higher-order features, and then calculate the learning rates.

Q5: Insufficient explanations.

A: For Reddit-Body data, the differences between adjacent snapshots are relatively small, leading to suboptimal performance under the ROLAND setting, as the complementary information gains yielded by our method are less profound. However, under the WinGNN settings where we aggregate training within a certain window length, extracted topological signals are more prominent; TMetaNet more efficiently leverages the underlying higher-order graph topology, and outperforms the baseline. These findings indicate that extracted time-evolving topological information and the associated induced learning rates have higher value under more heterogeneous dynamics and less value for more homogeneous cases.

Q6: The starting point.

A: Topological information has been indeed incorporated into graph learning tasks before, largely for static scenarios and most recently for dynamic scenarios. However, there are no studies yet on explicit integration of time-evolving topological information for dynamic link prediction. This is also the first work that specifically focuses on using time-evolving topological representation to guide parameter updates in meta-learning models. Finally, models for dynamic link prediction and graph meta-learning using even conventional topological information are yet in their nascency. Our method makes a step forward toward this important direction by explicitly incorporating the essential time-evolving topological information in a mathematically rigorous and computationally more efficient manner.

Q7: CTDGs.

A: Indeed, CTDGs provide a more fine-grained node evolution process through event streams, by using representations via ODEs. However, CTDGs primarily focus on pairwise node interactions and do not account for simultaneous multi-node structures. TMetaNet and CTDGs can effectively complement each other. One approach is to use PDE rather than ODE in CTDG, where PDE describes dependencies across all nodes in the neighborhood and TMetaNet is used to parametrize the resulting coupled dynamics. Another direction is to use CTDG for identification and reconstruction of the dynamic landmarks in TMetaNet.

Q1: This approach, while innovative, may not fully address the complexity of evolving graph structures.

A1: We agree that our approach may not fully address the full complexity of evolving graph structures. However, we argue that given the currently existing methods, we achieve almost as much as possible. In particular, by using zigzag persistence, our proposed model inherently captures higher-order topological structures across different timestamps in both spatial and temporal dimensions. Additionally, Dowker complex can efficiently handle large-scale graphs by focusing on more compact and expressive components of the graph topology, resulting in higher scalability, comparing to more conventional persistence homology methods for graphs (and scalability nowadays is arguably one of the primary roadblocks on adopting PH tools, especially, for dynamic scenarios). Considering the uncertainty and complexities of evolving graph structures, zigzag persistence and Dowker complex provide stable representations of the graph’s topology even in presence of noise or incomplete data. Certainly, our approach can be extended further, for example, by using zigzag persistence along multiple geometric dimensions, i.e. zigzag multi-persistence. However, such techniques are barely explored even in pure mathematics.

Q2: The motivation for employing adaptive learning rates derived from topological features requires more explanation or stronger theoretical justification.

A2: Thank you for your suggestion. Qualitatively speaking, persistent homology captures essential "shape" features across scales, directly reflecting graph structure. By shape here, we understand properties invariant under continuous transformations, e.g., bending, stretching, and twisting. When structural changes between snapshots are minimal, persistent homology features remain stable, allowing smaller learning rates as parameter updates stabilize. Conversely, significant structural changes produce substantial shifts in persistent homology features, necessitating larger learning rates to adapt.

We designed an experiment to illustrate this point. Starting from a random BA network A with 500 nodes, we randomly changed m% of the edges between each snapshot 50 times. Experiments are run under both TMetaNet and fixed learning rate methods, where m takes values of 5, 20, 50, 90. The experimental results of MRR are:

The performance of the fixed learning rate method drops faster with increasing m, while TMetaNet's performance drops relatively less, indicating that TMetaNet can better adapt to the changes in the graph structure and maintain good performance when facing random perturbations of the graph structure.

Q3: The authors adopted two settings to train the model and the results are clearly provided. According to Table 1, TMetaNet's performance under "WinGNN Setting" is significantly better than that under "Live Update Setting" consistently while the other methods' performance are not.

A3: Our baseline performance is close to what WinGNN and ROLAND reported, which aligns with the observation that performance under live update setting is better than WinGNN. We believe this difference mainly stems from variations in how our method is implemented under different settings. In the WinGNN setting, we configure TMetaNet's learning rate updates based on WinGNN's model without temporal encoders. Since WinGNN itself uses meta-learning to update node embeddings, TMetaNet's meta-learning rate updates can more significantly enhance WinGNN's performance, as shown in the table. This explains why TMetaNet performs better under the WinGNN setting compared to the live update setting.

Q4:Are there any existing works that use PH for dynamic graphs?

A4:Yes, there are several works that apply PH to dynamic graphs. For example, [1] designs a stable distance between dynamic graphs based on persistent homology; [2] uses neural networks to approximate Dowker persistent homology for dynamic graphs, and [3] applies PH in diffusion models for dynamic graphs. These papers, along with other related approaches, primarily focus on using PH to represent dynamic graphs for downstream tasks, while our work specifically focuses on using time-evolving PH to guide parameter updates in meta-learning models. Furthermore, there are yet no studies on explicit integration of {\bf time-evolving topological information} for link prediction, either in a form of zigzag persistence or any other alternative approach.

[1] Stable distance of persistent homology for dynamic graph comparison [2] Dynamic Neural Dowker Network: Approximating Persistent Homology in Dynamic Directed Graphs [3] Topological Zigzag Spaghetti for Diffusion-based Generation and Prediction on Graphs