Koopman-based spectral clustering of directed and time-evolving graphs

• URL: http://arxiv.org/abs/2204.02951v1
• Date: Wed, 6 Apr 2022 17:33:24 GMT
• Title: Koopman-based spectral clustering of directed and time-evolving graphs
• Authors: Stefan Klus, Natasa Djurdjevac Conrad
• Abstract summary: 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.
• Score: 0.3655021726150368
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While spectral clustering algorithms for undirected graphs are well established and have been successfully applied to unsupervised machine learning problems ranging from image segmentation and genome sequencing to signal processing and social network analysis, clustering directed graphs remains notoriously difficult. Two of the main challenges are that the eigenvalues and eigenvectors of graph Laplacians associated with directed graphs are in general complex-valued and that there is no universally accepted definition of clusters in directed graphs. We first exploit relationships between the graph Laplacian and transfer operators and in particular between clusters in undirected graphs and metastable sets in stochastic dynamical systems and then use a generalization of the notion of metastability to derive clustering algorithms for directed and time-evolving graphs. 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.

Related papers

• Clustering Time-Evolving Networks Using the Spatio-Temporal Graph Laplacian [0.8643517734716606]
  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.
  arXiv  Detail & Related papers  (2024-07-12T14:31:54Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Deep Contrastive Graph Learning with Clustering-Oriented Guidance [61.103996105756394]
  Graph Convolutional Network (GCN) has exhibited remarkable potential in improving graph-based clustering. Models estimate an initial graph beforehand to apply GCN. Deep Contrastive Graph Learning (DCGL) model is proposed for general data clustering.
  arXiv  Detail & Related papers  (2024-02-25T07:03:37Z)
• Transfer operators on graphs: Spectral clustering and beyond [1.147633309847809]
  We show that spectral clustering of undirected graphs can be interpreted in terms of eigenfunctions of the Koopman operator. We propose novel clustering algorithms for directed graphs based on generalized transfer operators.
  arXiv  Detail & Related papers  (2023-05-19T15:52:08Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Generalized Spectral Clustering for Directed and Undirected Graphs [4.286327408435937]
  We present a generalized spectral clustering framework that can address both directed and undirected graphs. Our approach is based on the spectral relaxation of a new functional that we introduce as the generalized Dirichlet energy of a graph function. We also propose a practical parametrization of the regularizing measure constructed from the iterated powers of the natural random walk on the graph.
  arXiv  Detail & Related papers  (2022-03-07T09:18:42Z)
• Effective and Efficient Graph Learning for Multi-view Clustering [173.8313827799077]
  We propose an effective and efficient graph learning model for multi-view clustering. Our method exploits the view-similar between graphs of different views by the minimization of tensor Schatten p-norm. Our proposed algorithm is time-economical and obtains the stable results and scales well with the data size.
  arXiv  Detail & Related papers  (2021-08-15T13:14:28Z)
• Higher-Order Spectral Clustering of Directed Graphs [8.997952791113232]
  Clustering is an important topic in algorithms, and has a number of applications in machine learning, computer vision, statistics, and several other research disciplines. We present a nearly-linear time algorithm for digraph clustering, and show that our proposed algorithm can be implemented in sublinear time under reasonable assumptions.
  arXiv  Detail & Related papers  (2020-11-10T13:06:37Z)
• Adaptive Graph Auto-Encoder for General Data Clustering [90.8576971748142]
  Graph-based clustering plays an important role in the clustering area. Recent studies about graph convolution neural networks have achieved impressive success on graph type data. We propose a graph auto-encoder for general data clustering, which constructs the graph adaptively according to the generative perspective of graphs.
  arXiv  Detail & Related papers  (2020-02-20T10:11:28Z)

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.