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.

本文针对基于分布的局部聚类问题，提出了结合超图和图模型的新方法，通过组合优化算法求解，并在三角形图案实验中表现出了较高的性能表现。

通过（超）图划分进行本地模体聚类

Local Motif Clustering via (Hyper)Graph Partitioning

Hypergraph partitioning is an important problem in machine learning, computer
vision and network analytics. A widely used method for hypergraph partitioning
relies on minimizing a normalized sum of the costs of partitioning hyperedges
across clusters. Algorithmic solutions based on this approach assume that
different partitions of a hyperedge incur the same cost. However, this
assumption fails to leverage the fact that different subsets of vertices within
the same hyperedge may have different structural importance. We hence propose a
new hypergraph clustering technique, termed inhomogeneous hypergraph
partitioning, which assigns different costs to different hyperedge cuts. We
prove that inhomogeneous partitioning produces a quadratic approximation to the
optimal solution if the inhomogeneous costs satisfy submodularity constraints.
Moreover, we demonstrate that inhomogenous partitioning offers significant
performance improvements in applications such as structure learning of
rankings, subspace segmentation and motif clustering.

提出了一种新的超图聚类技术，称为不均匀超图划分，其将不同的代价分配给不同的超图切割，证明了如果不均匀代价满足次模性约束，则不均匀划分产生了最优解的二次近似，并证明了在许多应用中可以获得显着的性能改进。

不均匀超图聚类与应用

Inhomogeneous Hypergraph Clustering with Applications

Motivated by applications in social network community analysis, we introduce
a new clustering paradigm termed motif clustering. Unlike classical clustering,
motif clustering aims to minimize the number of clustering errors associated
with both edges and certain higher order graph structures (motifs) that
represent "atomic units" of social organizations. Our contributions are
two-fold: We first introduce motif correlation clustering, in which the goal is
to agnostically partition the vertices of a weighted complete graph so that
certain predetermined "important" social subgraphs mostly lie within the same
cluster, while "less relevant" social subgraphs are allowed to lie across
clusters. We then proceed to introduce the notion of motif covers, in which the
goal is to cover the vertices of motifs via the smallest number of (near)
cliques in the graph. Motif cover algorithms provide a natural solution for
overlapping clustering and they also play an important role in latent feature
inference of networks. For both motif correlation clustering and its extension
introduced via the covering problem, we provide hardness results, algorithmic
solutions and community detection results for two well-studied social networks.

本文引入了一种新的聚类范式 —— 模式聚类，该文章探讨了模式聚类在社交网络社区分析中的应用，以及通过模式覆盖算法实现的重叠聚类与潜在特征推断等问题。

社交网络分析中的模式聚类和重叠聚类

Motif Clustering and Overlapping Clustering for Social Network Analysis

Genes are often regulated in living cells by proteins called transcription
factors (TFs) that bind directly to short segments of DNA in close proximity to
specific genes. These binding sites have a conserved nucleotide appearance,
which is called a motif. Several recent studies of transcriptional regulation
require the reduction of a large collection of motifs into clusters based on
the similarity of their nucleotide composition. We present a principled
approach to this clustering problem based upon a Bayesian hierarchical model
that accounts for both within- and between-motif variability. We use a
Dirichlet process prior distribution that allows the number of clusters to vary
and we also present a novel generalization that allows the core width of each
motif to vary. This clustering model is implemented, using a Gibbs sampling
strategy, on several collections of transcription factor motif matrices. Our
clusters provide a means by which to organize transcription factors based on
binding motif similarities, which can be used to reduce motif redundancy within
large databases such as JASPAR and TRANSFAC. Finally, our clustering procedure
has been used in combination with discovery of evolutionarily-conserved motifs
to predict co-regulated genes. An alternative to our Dirichlet process prior
distribution is explored but shows no substantive difference in the clustering
results for our datasets. Our Bayesian clustering model based on the Dirichlet
process has several advantages over traditional clustering methods that could
make our procedure appropriate and useful for many clustering applications.

使用贝叶斯分层模型基于狄利克雷过程，对转录因子 Motif 聚类，减少大数据库中的冗余，该聚类模型可用于许多聚类应用，如预测共同调控的基因。