Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian
- URL: http://arxiv.org/abs/2407.12864v2
- Date: Mon, 9 Sep 2024 10:51:33 GMT
- Title: Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian
- Authors: Maia Trower, NataĊĦa Djurdjevac Conrad, Stefan Klus,
- Abstract summary: We generalize existing spectral algorithms to identify and analyze communities in time-varying graph structures.
We show that thetemporal-directed graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected clusters.
- Score: 0.8643517734716606
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Time-evolving graphs arise frequently when modeling complex dynamical systems such as social networks, traffic flow, and biological processes. Developing techniques to identify and analyze communities in these time-varying graph structures is an important challenge. In this work, we generalize existing spectral clustering algorithms from static to dynamic graphs using canonical correlation analysis (CCA) to capture the temporal evolution of clusters. Based on this extended canonical correlation framework, we define the spatio-temporal graph Laplacian and investigate its spectral properties. We connect these concepts to dynamical systems theory via transfer operators, and illustrate the advantages of our method on benchmark graphs by comparison with existing methods. We show that the spatio-temporal graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs.
Related papers
- Graph Neural Flows for Unveiling Systemic Interactions Among Irregularly Sampled Time Series [5.460420960898444]
We develop a graph-based model that unveils the systemic interactions of time series observed at irregular time points.
We validate our approach on several tasks, including time series classification and forecasting, to demonstrate its efficacy.
arXiv Detail & Related papers (2024-10-17T21:10:39Z) - State Space Models on Temporal Graphs: A First-Principles Study [30.531930200222423]
Research on deep graph learning has shifted from static graphs to temporal graphs in response to real-world complex systems that exhibit dynamic behaviors.
Sequence models such as RNNs or Transformers have long been the predominant backbone networks for modeling such temporal graphs.
We develop GraphSSM, a graph state space model for modeling the dynamics of temporal graphs.
arXiv Detail & Related papers (2024-06-03T02:56:11Z) - Learning Time-aware Graph Structures for Spatially Correlated Time
Series Forecasting [30.93275270960829]
We propose Time-aware Graph Structure Learning (TagSL), which extracts time-aware correlations among time series.
We also present a Graph Convolution-based Gated Recurrent Unit (GCGRU), that jointly captures spatial and temporal dependencies.
Finally, we introduce a unified framework named Time-aware Graph Convolutional Recurrent Network (TGCRN), combining TagSL, GCGRU in an encoder-decoder architecture for multi-step-temporal forecasting.
arXiv Detail & Related papers (2023-12-27T04:23:43Z) - Deep Temporal Graph Clustering [77.02070768950145]
We propose a general framework for deep Temporal Graph Clustering (GC)
GC introduces deep clustering techniques to suit the interaction sequence-based batch-processing pattern of temporal graphs.
Our framework can effectively improve the performance of existing temporal graph learning methods.
arXiv Detail & Related papers (2023-05-18T06:17:50Z) - Space-Time Graph Neural Networks with Stochastic Graph Perturbations [100.31591011966603]
Space-time graph neural networks (ST-GNNs) learn efficient graph representations of time-varying data.
In this paper we revisit the properties of ST-GNNs and prove that they are stable to graph stabilitys.
Our analysis suggests that ST-GNNs are suitable for transfer learning on time-varying graphs.
arXiv Detail & Related papers (2022-10-28T16:59:51Z) - Time-aware Dynamic Graph Embedding for Asynchronous Structural Evolution [60.695162101159134]
Existing works merely view a dynamic graph as a sequence of changes.
We formulate dynamic graphs as temporal edge sequences associated with joining time of.
vertex and timespan of edges.
A time-aware Transformer is proposed to embed.
vertex' dynamic connections and ToEs into the learned.
vertex representations.
arXiv Detail & Related papers (2022-07-01T15:32:56Z) - Learning the Evolutionary and Multi-scale Graph Structure for
Multivariate Time Series Forecasting [50.901984244738806]
We show how to model the evolutionary and multi-scale interactions of time series.
In particular, we first provide a hierarchical graph structure cooperated with the dilated convolution to capture the scale-specific correlations.
A unified neural network is provided to integrate the components above to get the final prediction.
arXiv Detail & Related papers (2022-06-28T08:11:12Z) - Koopman-based spectral clustering of directed and time-evolving graphs [0.3655021726150368]
spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems.
However, clustering directed graphs remains notoriously difficult and there is no universally accepted definition of clusters in directed graphs.
We derive clustering algorithms for directed and time-evolving graphs using relationships between Laplacians and transfer operators.
The resulting clusters can be interpreted as coherent sets, which play an important role in the analysis of transport and mixing processes in fluid flows.
arXiv Detail & Related papers (2022-04-06T17:33:24Z) - Spatio-Temporal Joint Graph Convolutional Networks for Traffic
Forecasting [75.10017445699532]
Recent have shifted their focus towards formulating traffic forecasting as atemporal graph modeling problem.
We propose a novel approach for accurate traffic forecasting on road networks over multiple future time steps.
arXiv Detail & Related papers (2021-11-25T08:45:14Z) - Spectral-Spatial Global Graph Reasoning for Hyperspectral Image
Classification [50.899576891296235]
Convolutional neural networks have been widely applied to hyperspectral image classification.
Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
arXiv Detail & Related papers (2021-06-26T06:24:51Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.