Local Motif Clustering via (Hyper)Graph Partitioning
- URL: http://arxiv.org/abs/2205.06176v1
- Date: Wed, 11 May 2022 12:16:01 GMT
- Title: Local Motif Clustering via (Hyper)Graph Partitioning
- Authors: Adil Chhabra, Marcelo Fonseca Faraj and Christian Schulz
- Abstract summary: We build a hypergraph and a graph model which both represent the motif-distribution around the seed node.
We solve these models using sophisticated algorithms designed for (hyper)graph.
Our algorithm computes communities with a motif conductance value being one third on average in comparison against the communities computed by the state-of-the-art tool MAPPR.
- Score: 1.9121961872220465
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A widely-used operation on graphs is local clustering, i.e., extracting a
well-characterized community around a seed node without the need to process the
whole graph. Recently local motif clustering has been proposed: it looks for a
local cluster based on the distribution of motifs. Since this local clustering
perspective is relatively new, most approaches proposed for it are extensions
of statistical and numerical methods previously used for edge-based local
clustering, while the available combinatorial approaches are still few and
relatively simple. In this work, we build a hypergraph and a graph model which
both represent the motif-distribution around the seed node. We solve these
models using sophisticated combinatorial algorithms designed for (hyper)graph
partitioning. In extensive experiments with the triangle motif, we observe that
our algorithm computes communities with a motif conductance value being one
third on average in comparison against the communities computed by the
state-of-the-art tool MAPPR while being 6.3 times faster on average.
Related papers
- MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity
and Degree Descent Criterion [0.6906005491572401]
spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability.
We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition.
The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
arXiv Detail & Related papers (2023-12-07T06:19:39Z) - Reinforcement Graph Clustering with Unknown Cluster Number [91.4861135742095]
We propose a new deep graph clustering method termed Reinforcement Graph Clustering.
In our proposed method, cluster number determination and unsupervised representation learning are unified into a uniform framework.
In order to conduct feedback actions, the clustering-oriented reward function is proposed to enhance the cohesion of the same clusters and separate the different clusters.
arXiv Detail & Related papers (2023-08-13T18:12:28Z) - Dink-Net: Neural Clustering on Large Graphs [59.10189693120368]
A deep graph clustering method (Dink-Net) is proposed with the idea of dilation and shrink.
By discriminating nodes, whether being corrupted by augmentations, representations are learned in a self-supervised manner.
The clustering distribution is optimized by minimizing the proposed cluster dilation loss and cluster shrink loss.
Compared to the runner-up, Dink-Net 9.62% achieves NMI improvement on the ogbn-papers100M dataset with 111 million nodes and 1.6 billion edges.
arXiv Detail & Related papers (2023-05-28T15:33:24Z) - 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) - Skew-Symmetric Adjacency Matrices for Clustering Directed Graphs [5.301300942803395]
Cut-based directed graph (digraph) clustering often focuses on finding dense within-cluster or sparse between-cluster connections.
For flow-based clusterings the edges between clusters tend to be oriented in one direction and have been found in migration data, food webs, and trade data.
arXiv Detail & Related papers (2022-03-02T20:07:04Z) - 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) - Structured Graph Learning for Clustering and Semi-supervised
Classification [74.35376212789132]
We propose a graph learning framework to preserve both the local and global structure of data.
Our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure.
Our model is equivalent to a combination of kernel k-means and k-means methods under certain condition.
arXiv Detail & Related papers (2020-08-31T08:41:20Z) - 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) - Incorporating User's Preference into Attributed Graph Clustering [14.082520165369885]
We propose two quality measures for a local cluster: Graph Unimodality (GU) and Attribute Unimodality (AU)
The local cluster detected by LOCLU concentrates on the region of interest, provides efficient information flow in the graph and exhibits a unimodal data distribution in the subspace of the designated attributes.
arXiv Detail & Related papers (2020-03-24T19:07:22Z) - Minimizing Localized Ratio Cut Objectives in Hypergraphs [32.80813008862995]
We present a framework for local hypergraph clustering based on minimizing localized ratio cut objectives.
Our algorithm is strongly-local, meaning that its runtime depends only on the size of the input set, and does not need to explore the entire hypergraph to find good local clusters.
arXiv Detail & Related papers (2020-02-21T17:42:22Z)
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.