Higher-Order Spectral Clustering of Directed Graphs
Clustering is an important topic in algorithms, and has a number of applications in machine learning, computer vision, statistics, and several other research disciplines. Traditional objectives of graph clustering are to find clusters with low conductance. Not only are these objectives just applicable for undirected graphs, they are also incapable to take the relationships between clusters into account, which could be crucial for many applications. To overcome these downsides, we study directed graphs (digraphs) whose clusters exhibit further "structural" information amongst each other. Based on the Hermitian matrix representation of digraphs, we present a nearly-linear time algorithm for digraph clustering, and further show that our proposed algorithm can be implemented in sublinear time under reasonable assumptions. The significance of our theoretical work is demonstrated by extensive experimental results on the UN Comtrade Dataset: the output clustering of our algorithm exhibits not only how the clusters (sets of countries) relate to each other with respect to their import and export records, but also how these clusters evolve over time, in accordance with known facts in international trade.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringGraph ClusteringSimilar Papers 제목 키워드 기반
Higher-Order Spectral Clustering under Superimposed Stochastic Block Model
Higher-order motif structures and multi-vertex interactions are becoming increasingly important in studies that aim to improve our understanding of functionalities and evolution patterns of networks. To elucidate the rol…
ClusteringCommunity DetectionStochastic Block ModelMotif-Based Spectral Clustering of Weighted Directed Networks
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 c…
ClusteringHigher-Order Spectral Clustering for Geometric Graphs
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalization, which we call higher-order spectral…
ClusteringSpectral Clustering for Directed Graphs via Likelihood Estimation on Stochastic Block Models
Graph clustering is a fundamental task in unsupervised learning with broad real-world applications. While spectral clustering methods for undirected graphs are well-established and guided by a minimum cut optimization co…
ClusteringGraph ClusteringStochastic Block ModelGeneralized Spectral Clustering for Directed and Undirected Graphs
Spectral clustering is a popular approach for clustering undirected graphs, but its extension to directed graphs (digraphs) is much more challenging. A typical workaround is to naively symmetrize the adjacency matrix of …
Clusteringgraph partitioning