Higher-Order Spectral Clustering of Directed Graphs
- URL: http://arxiv.org/abs/2011.05080v1
- Date: Tue, 10 Nov 2020 13:06:37 GMT
- Title: Higher-Order Spectral Clustering of Directed Graphs
- Authors: Steinar Laenen and He Sun
- Abstract summary: 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.
- Score: 8.997952791113232
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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.
Related papers
- 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) - A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised
Learning [33.05104609131764]
Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data.
This paper formalizes a graph-theoretic framework tailored for the open-world setting.
Our graph-theoretic framework illuminates practical algorithms and provides guarantees.
arXiv Detail & Related papers (2023-11-06T21:15:09Z) - 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) - On Learning the Structure of Clusters in Graphs [3.8073142980733]
In many real-world applications, we find that the clusters have a significant high-level structure.
This is often overlooked in the design and analysis of graph clustering algorithms.
This thesis addresses the natural question of whether the structure of clusters can be learned efficiently.
arXiv Detail & Related papers (2022-12-29T15:26:19Z) - 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) - Graph Representation Learning via Contrasting Cluster Assignments [57.87743170674533]
We propose a novel unsupervised graph representation model by contrasting cluster assignments, called as GRCCA.
It is motivated to make good use of local and global information synthetically through combining clustering algorithms and contrastive learning.
GRCCA has strong competitiveness in most tasks.
arXiv Detail & Related papers (2021-12-15T07:28:58Z) - 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) - Local Algorithms for Finding Densely Connected Clusters [3.2901541059183432]
Local graph clustering is an important technique for analysing massive graphs.
Recent studies highlight the importance of the inter-connection between clusters when analysing real-world datasets.
arXiv Detail & Related papers (2021-06-09T17:40:45Z) - Graph Contrastive Clustering [131.67881457114316]
We propose a novel graph contrastive learning framework, which is then applied to the clustering task and we come up with the Graph Constrastive Clustering(GCC) method.
Specifically, on the one hand, the graph Laplacian based contrastive loss is proposed to learn more discriminative and clustering-friendly features.
On the other hand, a novel graph-based contrastive learning strategy is proposed to learn more compact clustering assignments.
arXiv Detail & Related papers (2021-04-03T15:32:49Z) - Learning to Cluster Faces via Confidence and Connectivity Estimation [136.5291151775236]
We propose a fully learnable clustering framework without requiring a large number of overlapped subgraphs.
Our method significantly improves clustering accuracy and thus performance of the recognition models trained on top, yet it is an order of magnitude more efficient than existing supervised methods.
arXiv Detail & Related papers (2020-04-01T13:39:37Z)
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.