ArXiv

Learning and Clustering on Temporal Graphs: Principles, Primitives, and Pooling

2026-08-04 · 14:01 UTC ·Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani ·1 min read
Authors
Nelson Aloysio Reis de Almeida Passos, Emanuele Carlini, Salvatore Trani
Categories
cs.LG, cs.SI
arXiv
https://arxiv.org/abs/2608.03696v1
PDF
https://arxiv.org/pdf/2608.03696v1

Brief

Temporal-graph clustering is treated through spectral theory, primitives, and pooling: the authors develop GPU-accelerated temporal backends to scale spectral clustering and multislice modularity optimization, link graph neural nets and community detection via detectability thresholds in stochastic block models, and conclude algorithmic methods suit attribute-poor settings while neural models excel when signals align; full text (4 pages, 1 figure) available on arXiv.

Why it matters

Passos, Carlini, and Trani (arXiv 2608.03696v1, published 2026-08-04; accepted at ECML PKDD 2026) connect temporal-graph learning and community detection via shared spectral foundations and detectability thresholds in stochastic block model regimes.

Key details

  • They implement GPU-accelerated temporal primitives that make spectral clustering and multislice modularity optimization tractable for temporal clustering, arguing algorithmic (non-neural) methods are preferable when attributes are absent or weak, while neural models outperform when structural, temporal, and attribute signals align.
Source evidence

Abstract

This work focuses on the problem of learning on temporal graphs, with particular emphasis on the task of clustering: obtaining coarse-grained representations by aggregating information from nodes, edges, and temporal dynamics - a task related to pooling in machine learning on graphs, or community detection in network science. Although graph neural networks reach state-of-the-art performance across many downstream graph tasks, their advantage over established descriptive and inferential clustering algorithms is far less settled, especially under demands of efficiency and recovery accuracy. We frame this tension through three linked perspectives: principles, connecting graph learning and community detection through shared spectral foundations and detectability thresholds in stochastic block model regimes; primitives, making spectral clustering and multislice modularity optimization tractable through GPU-accelerated temporal backends; and pooling, viewing principled community detection as a theory-grounded coarse-graining operator for temporal graphs. Our results indicate that algorithmic methods remain the appropriate tool where attributes are absent or weak - scalability rather than accuracy being the binding obstacle - while neural models are most compelling when structural, temporal, and attribute signals align. By making temporal clustering scalable, GPU-accelerated primitives suggest a route toward theory-grounded pooling, while raising a central question: when does community-based coarse-graining preserve the dynamics needed for downstream learning tasks?

Comment: 4 pages, 1 figure. Accepted at ECML PKDD 2026 (Nectar Track)