Using Time-Aware Graph Neural Networks to Predict Temporal Centralities in Dynamic Graphs

Summary

In this paper, the authors utilize the De Bruijn Graph Neural Networks (DBGNN) to predict centrality in a dynamic graph, thereby trying to address the challenge of large computation workload on time-respecting paths between pairs of nodes. By giving the problem definition, the authors use DBGNN to predict dynamic graph centrality, and showed the comparison with GCN which treat the graph as static one.

Strengths

1) Finding the temporal centrality of a dynamic graph is an interesting question, which is currently suffering the challenge of large computation; 2) The topic is generally interesting and may capture large readership in NeurIPS. 3) The paper is well-written and easy to follow.

Weaknesses

1) In this paper, the author introduces the problem of temporal centralities and use an existing GNN model [Qarkaxhija, 2022] to establish this task. Therefore, my most concern lies in the contribution of this paper. The authors failed to give theoretical analysis to tell why the use of DBGNN can bring this improvement. 2) The backbone model used in this paper, DBGNN, provides a causality-aware view to unfold embedding learning via dynamic graphs. However, in this paper the authors did not continue this idea in centrality prediction, nor give another explanation, which makes it hard to understand why this utilization is significant. 3) Table 3 is not convincing enough. The authors should compare their computation cost with baselines, including both static GNN and dynamic GNN-based approaches. 4) Mode detailed analysis of using DBGNN should be explored, such as ablation study, parameter analysis, etc.

Questions

1) According to Table 1 and 2 the DBGNN performs better in predicting closeness than betweenness (In Table 2, the DGNN achieves the optimal Spearman’s r among all datasets and hits@10 in 12/13 datasets, while it only achieves 8/13 Spearman’s r and 7/13 hits@10 in Table 1). Can authors provide more detailed analysis of this difference? 2) Will this temporal centrality prediction also be established by other dynamic GNN? Such as EvloveGCN [Pareja, 2020] Roland [You, 2022], WinGNN [Zhu, 2023]. References: [Qarkaxhija, 2022] De Bruijn goes Neural: Causality-Aware Graph Neural Networks for Time Series Data on Dynamic Graphs [Pareja, 2020] EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs [You, 2022] ROLAND: Graph Learning Framework for Dynamic Graphs [Zhu, 2023] WinGNN: Dynamic Graph Neural Networks with Random Gradient Aggregation Window

Rating

5

Confidence

4

Soundness

2

Presentation

3

Contribution

1

Limitations

1) The theoretical analysis of this study is somehow weak; 2) The authors did not show the superiority of this method compared to other state-of-art dynamic GNN models. 3) Result analysis did not give a useful insight.

Summary

In the article, the authors explore the potential of using TGNN to predict node centrality metrics, such as temporal closeness and temporal betweenness. Despite the straightforward and intuitive approach presented, the issue of predicting temporal node centralities has not been previously addressed within the TGNN community, to the best of my knowledge. The authors tested the method on 13 real-world temporal networks. However, the network sizes are relatively small, with the largest network containing 327 nodes and 188,508 temporal edges, especially compared to several networks in the Temporal Graph Benchmark (TGB), such as tgb-reddit. While this may not pose a significant issue, it should be well-motivated and clearly justified in the article (see below for further details).

Strengths

The proposed task is novel and has the potential to open new research directions. The article is well-written and easy to follow. The detailed experimental setup ensures reproducibility.

Weaknesses

The authors should test additional models to gain a clearer understanding of how TGNN performs on this task. Additionally, it would be beneficial to include a baseline that approximates the centralities, such as those referenced in [41, 2, 21]. [2] D. A. Bader, S. Kintali, K. Madduri, and M. Mihail. Approximating betweenness centrality. In Algorithms and Models for the Web-Graph: 5th International Workshop, WAW 2007, San Diego, CA, USA, December 11-12, 2007. Proceedings 5, pages 124–137. Springer, 2007. [21] M. Haghir Chehreghani. An efficient algorithm for approximate betweenness centrality computation. In Proceedings of the 22nd ACM international conference on Information & Knowledge Management, pages 1489–1492, 2013. [41] M. Riondato and E. M. Kornaropoulos. Fast approximation of betweenness centrality through sampling. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 413–422, 2014.

Questions

1. Is there a specific reason the authors chose relatively small temporal networks? 2. It is unclear whether the authors used input features in their analysis. If they did, what was the rationale behind this choice? Since closeness and betweenness do not depend on features, it would be interesting to see how the inclusion/deletion of features affects performance.

Rating

8

Confidence

3

Soundness

3

Presentation

3

Contribution

4

Limitations

The authors clearly explain the potential limitations of their proposed work and suggest future research directions.

Summary

This paper proposes an algorithm using time-aware graph neural networks (DBGNN) to predict temporal path-based centralities in dynamic graphs. Experimental results show that this method outperforms a static Graph Convolutional Network (GCN) and two state-of-the-art time-aware graph learning techniques in predicting temporal centralities.

Strengths

1. Innovative Approach: The paper introduces a novel application of De Bruijn Graph Neural Networks (DBGNN) for predicting temporal path-based centralities, addressing a significant computational challenge in dynamic graphs. 2. Comprehensive Evaluation: The method is experimentally validated on 13 temporal graphs from biological and social systems, demonstrating its effectiveness and robustness across different datasets. 3. Performance Improvement: The proposed DBGNN architecture shows substantial improvements in predicting both betweenness and closeness centrality compared to traditional static GCN and other state-of-the-art time-aware graph learning techniques.

Weaknesses

1. Clarity and Readability: In several instances, the mathematical formulas, particularly the update rules and algorithms, are not directly provided in the manuscript but instead are referenced to external literature for these crucial details. This approach can significantly hinder readers' understanding and evaluation of your work. 2. Generalization: The method is evaluated on specific types of temporal graphs (biological and social systems), and its performance on other types of temporal networks remains untested.

Questions

1. Scalability: How does the DBGNN model scale with increasing size and complexity of the temporal graphs? Are there any specific techniques employed to manage large-scale data? 2. Parameter Sensitivity: How sensitive is the model to hyperparameters such as the order of the De Bruijn graph? What guidelines are provided for selecting these parameters? 3. Real-World Application: Can the authors provide more detailed case studies or examples of how this method can be applied in real-world scenarios, beyond the provided experimental evaluation?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

1. Inadequate optimization of hyperparameters. 2. Lack of utilization of additional node features. 3. Unexplored impact of training data size on model accuracy. 4. Unverified adaptability of the model to a fully inductive setting. 5. Uninvestigated model adjustment strategies for datasets with non-stationary temporal patterns.

Summary

This work aims to predict temporal node centralities such as temporal betweenness and closeness centralities using a time-aware graph neural network based on higher-order De Bruijn graph models. The empirical experiments on 13 datasets shows that the proposed DBGNN model can predict temporal centralities effectively with computational speed up when compared to the exact computation and outperforms baselines. Additionally, the study finds that static embeddings from the last message-passing layer of the architecture better capture temporal centralities than GCN.

Strengths

**novel and important problem**: predicting node centrality in the future is an important and novel problem. Outside of the betweenness and closeness centralities discussed in the paper, this can be a general problem of predicting a property of the node in the future such as predicting user preferences. **approach with significant speed up**: the proposed DBGNN architecture achieves significant speedup when compared to the exact computation of these centralities. Therefore, validating the usefulness of using neural models to speed up these computations. **good performance**: the proposed method outperforms alternative approaches on 13 datasets.

Weaknesses

**limited baselines**: currently only a small number of baselines are included in the comparison. Including more baselines from recent literature can further validate the approach. Some example baselines are NAT[1] and DyGformer[2]. **DBGNN is an existing architecture**: DBGNN architecture has been proposed in previous work (as mentioned in the paper as well). Thus the main contribution of this work come from the application of this model in a novel problem setting [1] Luo Y, Li P. Neighborhood-aware scalable temporal network representation learning. InLearning on Graphs Conference 2022 Dec 21 (pp. 1-1). PMLR. [2] Yu L, Sun L, Du B, Lv W. Towards better dynamic graph learning: New architecture and unified library. Advances in Neural Information Processing Systems. 2023 Dec 15;36:67686-700.

Questions

1. why not directly use Mean Absolute Error (MAE) metric to measure the exact difference between the predicted centralities and the groundtruth one? 2. is it possible to pretrain a DBGNN and use it to predict for unseen networks (but similar to the training one, say from the same domain)? 3. typo in line 58 "13 time temporal graphs" 4. overall the presentation is clear, however some longer sections of text can be divided up and provided with more clear section headings

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

The limitations of the work has been discussed extensively. No negative potential negative societal impact is directly related to this work.

Response to Author Rebuttal

I thank the authors for addressing my concerns, I choose to retain my current score.