Clustering Time-Evolving Networks Using the Dynamic Graph Laplacian
- URL: http://arxiv.org/abs/2407.12864v1
- Date: Fri, 12 Jul 2024 14:31:54 GMT
- Title: Clustering Time-Evolving Networks Using the Dynamic Graph Laplacian
- Authors: Maia Trower, NataĊĦa Djurdjevac Conrad, Stefan Klus,
- Abstract summary: We generalize existing spectral clustering algorithms to capture the temporal evolution of clusters.
We show that the dynamic graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs.
- 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 dynamic 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 dynamic graph Laplacian allows for a clear interpretation of cluster structure evolution over time for directed and undirected graphs.
Related papers
- 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) - Inferring dynamic regulatory interaction graphs from time series data
with perturbations [14.935318448625718]
We propose Regulatory Temporal Interaction Network Inference (RiTINI) for inferring time-varying interaction graphs in complex systems.
RiTINI uses a novel combination of space-and-time graph attentions and graph neural ordinary differential equations (ODEs)
We evaluate RiTINI's performance on various simulated and real-world datasets.
arXiv Detail & Related papers (2023-06-13T14:25:26Z) - 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) - Decoupled Graph Neural Networks for Large Dynamic Graphs [14.635923016087503]
We propose a decoupled graph neural network for large dynamic graphs.
We show that our algorithm achieves state-of-the-art performance in both kinds of dynamic graphs.
arXiv Detail & Related papers (2023-05-14T23:00:10Z) - Learning Dynamic Graph Embeddings with Neural Controlled Differential
Equations [21.936437653875245]
This paper focuses on representation learning for dynamic graphs with temporal interactions.
We propose a generic differential model for dynamic graphs that characterises the continuously dynamic evolution of node embedding trajectories.
Our framework exhibits several desirable characteristics, including the ability to express dynamics on evolving graphs without integration by segments.
arXiv Detail & Related papers (2023-02-22T12:59:38Z) - 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) - Structural Landmarking and Interaction Modelling: on Resolution Dilemmas
in Graph Classification [50.83222170524406]
We study the intrinsic difficulty in graph classification under the unified concept of resolution dilemmas''
We propose SLIM'', an inductive neural network model for Structural Landmarking and Interaction Modelling.
arXiv Detail & Related papers (2020-06-29T01:01:42Z) - Tensor Graph Convolutional Networks for Multi-relational and Robust
Learning [74.05478502080658]
This paper introduces a tensor-graph convolutional network (TGCN) for scalable semi-supervised learning (SSL) from data associated with a collection of graphs, that are represented by a tensor.
The proposed architecture achieves markedly improved performance relative to standard GCNs, copes with state-of-the-art adversarial attacks, and leads to remarkable SSL performance over protein-to-protein interaction networks.
arXiv Detail & Related papers (2020-03-15T02:33:21Z)
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.