A bipartite graph contains inter-set edges between two disjoint vertex sets,
and is widely used to model real-world data, such as user-item purchase
records, author-article publications, and biological interactions between drugs
and proteins. k-Bipartite Graph Clustering (k-BGC) is to partition the target
vertex set in a bipartite graph into k disjoint clusters. The clustering
quality is important to the utility of k-BGC in various applications like
social network analysis, recommendation systems, text mining, and
bioinformatics, to name a few. Existing approaches to k-BGC either output
clustering results with compromised quality due to inadequate exploitation of
high-order information between vertices, or fail to handle sizable bipartite
graphs with billions of edges.
Motivated by this, this paper presents two efficient k-BGC solutions, HOPE
and HOPE+, which achieve state-of-the-art performance on large-scale bipartite
graphs. HOPE obtains high scalability and effectiveness through a new k-BGC
problem formulation based on the novel notion of high-order perspective (HOP)
vectors and an efficient technique for low-rank approximation of HOP vectors.
HOPE+ further elevates the k-BGC performance to another level with a judicious
problem transformation and a highly efficient two-stage optimization framework.
Two variants, HOPE+ (FNEM) and HOPE+ (SNEM) are designed when either the
Frobenius norm or spectral norm is applied in the transformation. Extensive
experiments, comparing HOPE and HOPE+ against 13 competitors on 10 real-world
datasets, exhibit that our solutions, especially HOPE+, are superior to
existing methods in terms of result quality, while being up to orders of
magnitude faster. On the largest dataset MAG with 1.1 billion edges, HOPE+ is
able to produce clusters with the highest clustering accuracy within 31
minutes, which is unmatched by any existing solution for k-BGC.

HOPE and HOPE+ are efficient solutions for k-Bipartite Graph Clustering that achieve state-of-the-art performance on large-scale bipartite graphs, providing high scalability, effectiveness, and superior clustering accuracy within a short runtime.

大规模二分图的高效高质量聚类

Efficient High-Quality Clustering for Large Bipartite Graphs

Hope is characterized as openness of spirit toward the future, a desire,
expectation, and wish for something to happen or to be true that remarkably
affects human's state of mind, emotions, behaviors, and decisions. Hope is
usually associated with concepts of desired expectations and
possibility/probability concerning the future. Despite its importance, hope has
rarely been studied as a social media analysis task. This paper presents a hope
speech dataset that classifies each tweet first into "Hope" and "Not Hope",
then into three fine-grained hope categories: "Generalized Hope", "Realistic
Hope", and "Unrealistic Hope" (along with "Not Hope"). English tweets in the
first half of 2022 were collected to build this dataset. Furthermore, we
describe our annotation process and guidelines in detail and discuss the
challenges of classifying hope and the limitations of the existing hope speech
detection corpora. In addition, we reported several baselines based on
different learning approaches, such as traditional machine learning, deep
learning, and transformers, to benchmark our dataset. We evaluated our
baselines using weighted-averaged and macro-averaged F1-scores. Observations
show that a strict process for annotator selection and detailed annotation
guidelines enhanced the dataset's quality. This strict annotation process
resulted in promising performance for simple machine learning classifiers with
only bi-grams; however, binary and multiclass hope speech detection results
reveal that contextual embedding models have higher performance in this
dataset.

本文介绍了一个用于分类 Twitter 推文的希望言论数据集，并提供了基于不同学习方法的多项基准测试以进行评估和分析。研究中发现，使用严格的注释过程并提供详细的注释指南可以提高数据集的质量。同时，使用上下文嵌入模型进行希望言论检测有更高的性能表现。