Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed

Graph Neural Tangent Kernel (GNTK) fuses graph neural networks and graph kernels, simplifies the process of graph representation learning, interprets the training dynamics of graph neural networks, and serves various applications like protein identification, image segmentation, and social network analysis. In practice, graph data carries complex information among entities that inevitably evolves over time, and previous static graph neural tangent kernel methods may be stuck in the sub-optimal solution in terms of both effectiveness and efficiency. As a result, extending the advantage of GNTK to temporal graphs becomes a critical problem. To this end, we propose the temporal graph neural tangent kernel, which not only extends the simplicity and interpretation ability of GNTK to the temporal setting but also leads to rigorous temporal graph classification error bounds. Furthermore, we prove that when the input temporal graph grows over time in the number of nodes, our temporal graph neural tangent kernel will converge in the limit to the graphon NTK value, which implies the transferability and robustness of the proposed kernel method, named Temporal Graph Neural Tangent Kernel with Graphon-Guaranteed or Temp-G³NTK. In addition to the theoretical analysis, we also perform extensive experiments, not only demonstrating the superiority of Temp-G³NTK in the temporal graph classification task, but also showing that Temp-G³NTK can achieve very competitive performance in node-level tasks like node classification compared with various SOTA graph kernel and representation learning baselines. Our code is available at https://github.com/kthrn22/TempGNTK.