ETD

• community detection
• graph neural networks
• high-performance computing
• spectral clustering
• temporal networks

Community detection or node clustering is a fundamental task in network analysis, where mesoscale structure may help reveal the function and dynamics of a complex system. Many and diverse applications - including social network analysis, computational biology, and recommendation systems - rely on community detection for goals such as node classification, link prediction, and graph summarization. Motivated by the need for more robust and scalable methods across domains, this research focuses on the task in time-varying attributed graphs - where the network's topology may be subject to change, and nodes and edges may be associated with additional metadata. Its contributions are three-fold: (i) software infrastructure, datasets, and generators for modeling and analyzing temporal graphs; (ii) high-performance algorithms for temporal community detection, based on spectral clustering or heuristic optimization on GPU devices; and (iii) a novel machine learning model that incorporates both spatio-temporal and attribute signals in its objective, improving upon a state-of-the-art graph neural network for end-to-end differentiable community detection. In doing so, this thesis intersects the network science and computer science domains in order to answer its central research question: can neural strategies outperform established baselines? Systematic evaluation on both real-world and synthetic datasets demonstrates that the advantages of neural methods over algorithmic approaches are contingent rather than universal: significant improvements are observed only where temporal or attribute signals carry information that a static, aggregated view of the network would otherwise miss, and provided those signals align with the community structure being recovered. Where this condition does not hold, established algorithms may remain competitive and outperform neural baselines, especially in regimes well studied in the literature; there, their decisive limitation lies not in accuracy, but in tractability and scalability to large temporal graphs or those with a high temporal resolution. These findings position learning-based and classical methods as complementary, the better choice depending on the properties of the dataset at hand - reinforcing a no-free-lunch view of community detection, in which no single method is universally optimal and the most suitable one varies with the data. Together, these contributions advance community detection in temporal graphs by introducing new methods, investigating the conditions under which neural or algorithmic methods are most effective, and providing new tools and resources for further research in the area.

La community detection, o clustering di nodi, è un compito fondamentale nell'analisi delle reti, in cui la struttura mesoscala può contribuire a rivelare la funzione e le dinamiche di un sistema complesso. Numerose e diverse applicazioni - tra cui l'analisi delle reti sociali, la biologia computazionale e i sistemi di raccomandazione - si affidano alla community detection per obiettivi quali la classificazione dei nodi, la link prediction e la summarization dei grafi. Motivata dalla necessità di metodi più robusti e scalabili in molteplici domini, questa ricerca si concentra sul compito nel contesto dei grafi temporali attribuiti - in cui la topologia della rete può essere soggetta a cambiamenti, e i nodi e gli archi possono essere associati a metadati aggiuntivi. I suoi contributi sono di tre tipi: (i) infrastruttura software, dataset e generatori per la modellazione e l'analisi dei grafi temporali; (ii) algoritmi ad alte prestazioni per la community detection temporale, basati su spectral clustering o ottimizzazione euristica su dispositivi GPU; e (iii) un nuovo modello di machine learning che integra nel proprio obiettivo sia i segnali spazio-temporali sia quelli attributivi, migliorando una graph neural network allo stato dell'arte per la community detection in modo end-to-end differenziabile. In tal modo, questa tesi mette in relazione i domini della network science e dell'informatica al fine di rispondere alla sua domanda di ricerca centrale: le strategie neurali possono superare le baseline consolidate? Una valutazione sistematica su dataset sia reali sia sintetici dimostra che i vantaggi dei metodi neurali rispetto agli approcci algoritmici sono contingenti anziché universali: miglioramenti significativi si osservano solo laddove i segnali temporali o attributivi contengono informazioni che una visione statica e aggregata della rete non coglierebbe, e a condizione che tali segnali siano allineati con la struttura di comunità che si intende recuperare. Quando questa condizione non è soddisfatta, gli algoritmi consolidati possono restare competitivi e superare le baseline neurali, specialmente nei regimi ben studiati in letteratura; in tali casi, il loro limite decisivo non risiede nell'accuratezza, ma nella trattabilità e nella scalabilità verso grafi temporali di grandi dimensioni o caratterizzati da un'elevata risoluzione temporale. Questi risultati collocano i metodi basati sull'apprendimento e quelli classici come complementari, dove la scelta migliore dipende dalle proprietà del dataset in esame - rafforzando una visione "no free lunch" della community detection, secondo cui nessun singolo metodo è universalmente ottimale e quello più adatto varia in funzione dei dati. Nel complesso, questi contributi fanno avanzare la community detection nei grafi temporali introducendo nuovi metodi, indagando le condizioni in cui i metodi neurali o algoritmici risultano più efficaci, e fornendo nuovi strumenti e risorse per la ricerca futura nell'ambito.