Shuang Cui

Shuang Cui

Auto-generated profile, based on publicly available information

Shuang Cui

Soochow University, Suzhou, Jiangsu, China

Research Focus & Metrics

Academic Career Length

6Years (2021-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
18 February 2021 in Proceedings of the ACM on Measurement and Analysis of Computing Systems
Verified
Journal Article
Open access
KHKai Han
Kai Han
SCShuang Cui
Shuang Cui
TZTianshuai Zhu
Tianshuai Zhu
EZEnpei Zhang
Enpei Zhang
BWBenwei Wu
Benwei Wu
HHe Huang
He Huang
Data summarization, i.e., selecting representative subsets of manageable size out of massive data, is often modeled as a submodular optimization problem. Although there exist extensive algorithms for submodular optimization, many of them incur large computational overheads and hence are not suitable for mining big data. In this work, we consider the fundamental problem of (non-monotone) submodular function maximization with a knapsack constraint, and propose simple yet effective and efficient algorithms for it. Specifically, we propose a deterministic algorithm with approximation ratio 6 and a randomized algorithm with approximation ratio 4, and show that both of them can be accelerated to achieve nearly linear running time at the cost of weakening the approximation ratio by an additive factor of ε. We then consider a more restrictive setting without full access to the whole dataset, and propose streaming algorithms with approximation ratios of 8+ε and 6+ε that make one pass and two passes over the data stream, respectively. As a by-product, we also propose a two-pass streaming algorithm with an approximation ratio of 2+ε when the considered submodular function is monotone. To the best of our knowledge, our algorithms achieve the best performance bounds compared to the state-of-the-art approximation algorithms with efficient implementation for the same problem. Finally, we evaluate our algorithms in two concrete submodular data summarization applications for revenue maximization in social networks and image summarization, and the empirical results show that our algorithms outperform the existing ones in terms of both effectiveness and efficiency.

30 April 2023
Verified
Conference Paper
Open access
SCShuang Cui
Shuang Cui
KHKai Han
Kai Han
JTJing Tang
Jing Tang
HHe Huang
He Huang
The problem of constrained subset selection from a large data stream for profit maximization has many applications in web data mining and machine learning, such as social advertising, team formation and recommendation systems. Such a problem can be formulated as maximizing a regularized submodular function under certain constraints. In this paper, we consider a generalized k-system constraint, which captures various requirements in real-world applications. For this problem, we propose the first streaming algorithm with provable performance bounds, leveraging a novel multitudinous distorted filter framework. The empirical performance of our algorithm is extensively evaluated in several applications including web data mining and recommendation systems, and the experimental results demonstrate the superiorities of our algorithm in terms of both effectiveness and efficiency.

30 April 2023
Verified
Conference Paper
Open access
HHe Huang
He Huang
KHKai Han
Kai Han
SCShuang Cui
Shuang Cui
JTJing Tang
Jing Tang
A lot of applications in web economics need to maximize the revenue under a budget for payments and also guarantee the truthfulness of users, so Budget-Feasible Mechanism (BFM) Design has aroused great interests during last decade. Most of the existing BFMs concentrate on maximizing a monotone submodular function subject to a knapsack constraint, which is insufficient for many applications with complex objectives or constraints. Observing this, the recent studies (e.g., [4, 5, 11]) have considered non-monotone submodular objectives or more complex constraints such as a k-system constraint. In this study, we follow this line of research and propose truthful BFMs with improved performance bounds for non-monotone submodular objectives with or without a k-system constraint. Our BFMs leverage the idea of providing random prices to users while deferring the decision on the final winning set, and are also based on a novel randomized algorithm for the canonical constrained submodular maximization problem achieving better performance bounds compared to the state-of-the-art. Finally, the effectiveness and efficiency of our approach are demonstrated by extensive experiments on several applications about social network marketing, crowdsourcing and personalized recommendation.

8 May 2025 in Artificial Intelligence
Verified
Journal Article
Closed access
KHKai Han
Kai Han
HZHaotian Zhang
Haotian Zhang
SCShuang Cui
Shuang Cui

24 August 2024
Verified
Conference Paper
Open access
SCShuang Cui
Shuang Cui
KHKai Han
Kai Han
STShaojie Tang
Shaojie Tang
FLFeng Li
Feng Li
Jun LuoJun Luo
Jun Luo
Submodular optimization has been identified as a powerful tool for many data mining applications, where a representative subset of moderate size needs to be extracted from a large-scale dataset. In scenarios where data points possess sensitive attributes such as age, gender, or race, it becomes imperative to integrate fairness measures into submodular optimization to mitigate bias and discrimination. In this paper, we study the fundamental problem of fair submodular maximization subject to a knapsack constraint and propose the first streaming algorithm for it with provable performance guarantees for both monotone and non-monotone submodular functions. As a byproduct, we also propose a streaming algorithm for submodular maximization subject to a partition matroid and a knapsack constraint, significantly improving the performance bounds achieved by previous work. We conduct extensive experiments on real-world applications such as movie recommendation, image summarization, and maximum coverage in social networks. The experimental results strongly demonstrate the superiority of our proposed algorithms in terms of both fairness and utility.

19 June 2023
Verified
Conference Paper
Open access
SCShuang Cui
Shuang Cui
KHKai Han
Kai Han
JTJing Tang
Jing Tang
HHe Huang
He Huang
XLXueying Li
Xueying Li
ZLZhiyu Li
Zhiyu Li
Due to the pervasive "diminishing returns" property appeared in data-intensive applications, submodular maximization problems have aroused great attention from both the machine learning community and the computation theory community. During the last decades, a lot of algorithms have been proposed for submodular maximization subject to various constraints [4, 6, 8], and these algorithms can be used in numerous applications including sensor placement [9], clustering [5], network design [13], and so on. The existing algorithms for submodular maximization can be roughly classified into offline algorithms and streaming algorithms; the former assume full access to the whole dataset at any time (e.g.,[4, 10]), while the latter only require an amount of space which is nearly linear in the maximum size of a feasible solution (e.g., [1, 7]). Apparently, streaming algorithms are more useful in big data applications, as the whole data set is usually too large to be fit into memory in practice. However, compared to the offline algorithms, the existing streaming algorithms for submodular maximization generally have weaker capabilities in that they handle more limited problem constraints or achieve weaker performance bounds, due to the more stringent requirements under the streaming setting. Another classification of the existing algorithms is that they concentrate on either monotone or non-monotone submodular functions. As monotone submodular function is a special case of non-monotone submodular function, we will concentrate on non-monotone submodular maximization in this paper.