Template-Based Graph Clustering
- URL: http://arxiv.org/abs/2107.01994v1
- Date: Mon, 5 Jul 2021 13:13:34 GMT
- Title: Template-Based Graph Clustering
- Authors: Mateus Riva and Florian Yger and Pietro Gori and Roberto M. Cesar Jr.
and Isabelle Bloch
- Abstract summary: We propose a novel graph clustering method guided by additional information on the underlying structure of the clusters (or communities)
With relevant priors that encode the density of the clusters and their relationships, our method outperforms classical methods, especially for challenging cases.
- Score: 5.4352987210173955
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We propose a novel graph clustering method guided by additional information
on the underlying structure of the clusters (or communities). The problem is
formulated as the matching of a graph to a template with smaller dimension,
hence matching $n$ vertices of the observed graph (to be clustered) to the $k$
vertices of a template graph, using its edges as support information, and
relaxed on the set of orthonormal matrices in order to find a $k$ dimensional
embedding. With relevant priors that encode the density of the clusters and
their relationships, our method outperforms classical methods, especially for
challenging cases.
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) - Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More [30.919536115917726]
We present a probabilistic model based on non-negative matrix factorization which unifies clustering and simplification.
By relaxing the hard clustering to a soft clustering, our algorithm relaxes potentially hard clustering problems to a tractable ones.
arXiv Detail & Related papers (2023-08-12T02:47:57Z) - Deep Graph-Level Clustering Using Pseudo-Label-Guided Mutual Information
Maximization Network [31.38584638254226]
We study the problem of partitioning a set of graphs into different groups such that the graphs in the same group are similar while the graphs in different groups are dissimilar.
To solve the problem, we propose a novel method called Deep Graph-Level Clustering (DGLC)
Our DGLC achieves graph-level representation learning and graph-level clustering in an end-to-end manner.
arXiv Detail & Related papers (2023-02-05T12:28:08Z) - GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton.
The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases.
In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
arXiv Detail & Related papers (2022-12-01T11:49:07Z) - Fine-grained Graph Learning for Multi-view Subspace Clustering [2.4094285826152593]
We propose a fine-grained graph learning framework for multi-view subspace clustering (FGL-MSC)
The main challenge is how to optimize the fine-grained fusion weights while generating the learned graph that fits the clustering task.
Experiments on eight real-world datasets show that the proposed framework has comparable performance to the state-of-the-art methods.
arXiv Detail & Related papers (2022-01-12T18:00:29Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs)
A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data.
We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
arXiv Detail & Related papers (2021-11-12T07:08:13Z) - 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) - Scaling Graph Clustering with Distributed Sketches [1.1011268090482575]
We present a method inspired by spectral clustering where we instead use matrix sketches derived from random dimension-reducing projections.
We show that our method produces embeddings that yield performant clustering results given a fully-dynamic block model stream.
We also discuss the effects of block model parameters upon the required dimensionality of the subsequent embeddings, and show how random projections could significantly improve the performance of graph clustering in distributed memory.
arXiv Detail & Related papers (2020-07-24T17:38:04Z) - Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph.
We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z) - 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.