Motif-Based Spectral Clustering of Weighted Directed Networks

• URL: http://arxiv.org/abs/2004.01293v2
• Date: Thu, 10 Sep 2020 18:25:01 GMT
• Title: Motif-Based Spectral Clustering of Weighted Directed Networks
• Authors: William George Underwood, Andrew Elliott, Mihai Cucuringu
• Abstract summary: Clustering is an essential technique for network analysis, with applications in a diverse range of fields. One approach is to capture and cluster higher-order structures using motif adjacency matrices. We present new and computationally useful matrix formulae for motif adjacency matrices on weighted networks.
• Score: 6.1448102196124195
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Clustering is an essential technique for network analysis, with applications in a diverse range of fields. Although spectral clustering is a popular and effective method, it fails to consider higher-order structure and can perform poorly on directed networks. One approach is to capture and cluster higher-order structures using motif adjacency matrices. However, current formulations fail to take edge weights into account, and thus are somewhat limited when weight is a key component of the network under study. We address these shortcomings by exploring motif-based weighted spectral clustering methods. We present new and computationally useful matrix formulae for motif adjacency matrices on weighted networks, which can be used to construct efficient algorithms for any anchored or non-anchored motif on three nodes. In a very sparse regime, our proposed method can handle graphs with a million nodes and tens of millions of edges. We further use our framework to construct a motif-based approach for clustering bipartite networks. We provide comprehensive experimental results, demonstrating (i) the scalability of our approach, (ii) advantages of higher-order clustering on synthetic examples, and (iii) the effectiveness of our techniques on a variety of real world data sets; and compare against several techniques from the literature. We conclude that motif-based spectral clustering is a valuable tool for analysis of directed and bipartite weighted networks, which is also scalable and easy to implement.

Related papers

• Unified Multi-View Orthonormal Non-Negative Graph Based Clustering Framework [74.25493157757943]
  We formulate a novel clustering model, which exploits the non-negative feature property and incorporates the multi-view information into a unified joint learning framework. We also explore, for the first time, the multi-model non-negative graph-based approach to clustering data based on deep features.
  arXiv  Detail & Related papers  (2022-11-03T08:18:27Z)
• DeepCluE: Enhanced Image Clustering via Multi-layer Ensembles in Deep Neural Networks [53.88811980967342]
  This paper presents a Deep Clustering via Ensembles (DeepCluE) approach. It bridges the gap between deep clustering and ensemble clustering by harnessing the power of multiple layers in deep neural networks. Experimental results on six image datasets confirm the advantages of DeepCluE over the state-of-the-art deep clustering approaches.
  arXiv  Detail & Related papers  (2022-06-01T09:51:38Z)
• Perfect Spectral Clustering with Discrete Covariates [68.8204255655161]
  We propose a spectral algorithm that achieves perfect clustering with high probability on a class of large, sparse networks. Our method is the first to offer a guarantee of consistent latent structure recovery using spectral clustering.
  arXiv  Detail & Related papers  (2022-05-17T01:41:06Z)
• A Modular Framework for Centrality and Clustering in Complex Networks [0.6423239719448168]
  In this paper, we study two important such network analysis techniques, namely, centrality and clustering. An information-flow based model is adopted for clustering, which itself builds upon an information theoretic measure for computing centrality. Our clustering naturally inherits the flexibility to accommodate edge directionality, as well as different interpretations and interplay between edge weights and node degrees.
  arXiv  Detail & Related papers  (2021-11-23T03:01:29Z)
• Network Clustering for Latent State and Changepoint Detection [0.0]
  We propose a convex approach for the task of network clustering. We provide an efficient algorithm for convex network clustering and demonstrate its effectiveness on synthetic examples.
  arXiv  Detail & Related papers  (2021-11-01T21:51:45Z)
• Attention-driven Graph Clustering Network [49.040136530379094]
  We propose a novel deep clustering method named Attention-driven Graph Clustering Network (AGCN) AGCN exploits a heterogeneous-wise fusion module to dynamically fuse the node attribute feature and the topological graph feature. AGCN can jointly perform feature learning and cluster assignment in an unsupervised fashion.
  arXiv  Detail & Related papers  (2021-08-12T02:30:38Z)
• Spectral clustering via adaptive layer aggregation for multi-layer networks [6.0073653636512585]
  We propose integrative spectral clustering approaches based on effective convex layer aggregations. We show that our methods are remarkably competitive compared to several popularly used methods.
  arXiv  Detail & Related papers  (2020-12-07T21:58:18Z)
• Scalable Hierarchical Agglomerative Clustering [65.66407726145619]
  Existing scalable hierarchical clustering methods sacrifice quality for speed. We present a scalable, agglomerative method for hierarchical clustering that does not sacrifice quality and scales to billions of data points.
  arXiv  Detail & Related papers  (2020-10-22T15:58:35Z)
• KCoreMotif: An Efficient Graph Clustering Algorithm for Large Networks by Exploiting k-core Decomposition and Motifs [6.1734015475373765]
  Spectral clustering is one of the most commonly used algorithms for graph-structured data (networks) We propose an efficient graph clustering algorithm, KCoreMotif, specifically for large networks by exploiting k-core decomposition and motifs. Comparative results demonstrate that the proposed graph clustering algorithm is accurate yet efficient for large networks.
  arXiv  Detail & Related papers  (2020-08-21T12:21:05Z)
• Local Graph Clustering with Network Lasso [90.66817876491052]
  We study the statistical and computational properties of a network Lasso method for local graph clustering. The clusters delivered by nLasso can be characterized elegantly via network flows between cluster boundary and seed nodes.
  arXiv  Detail & Related papers  (2020-04-25T17:52:05Z)
• Randomized spectral co-clustering for large-scale directed networks [15.486507430729052]
  Co-clustering aims to cluster the senders and receivers of directed networks simultaneously. We leverage sketching techniques and derive two randomized spectral co-clustering algorithms. We establish their approximation error rates and misclustering error rates, indicating better bounds than the state-of-the-art results of co-clustering literature.
  arXiv  Detail & Related papers  (2020-04-25T15:00:55Z)

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.