SCShuang Cui

Shuang Cui

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Shuang Cui has a total of 18 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Submodular Maximization under k -System Constraints in Parallel: A Trifecta of Approximation, Adaptivity, and Query Complexity

    by Shuang Cui, Yu-E Sun, He Huang

    Submodular optimization serves as a foundational framework for numerous data mining tasks requiring the extraction of representative subsets from large-scale datasets under combinatorial constraints. In this paper, we study the fundamental problem of maximizing a general submodular function (not necessarily monotone) under a general k-system constraint, and propose a novel parallel algorithm. For this problem, our algorithm is the first to simultaneously achieve nearly best-known guarantees across three key metrics: an approximation ratio of (1-ε)3 (√k+1)-2, an adaptive complexity of O (√k log2 n), and a query complexity of O (√knlog n), which effectively mitigates the trade-offs in prior work. Moreover, we generalize our approach to solve regularized submodular maximization problems while maintaining the same complexities. To the best of our knowledge, the resulting algorithm is the first parallel algorithm with a provable approximation ratio for this class of problems. We validate our theoretical contributions through extensive experiments on real-world applications, including maximum coverage on networks and movie recommendations. The empirical results strongly show the superiority of our proposed algorithms in terms of objective value, adaptivity, and query efficiency.

  • Open Access

    IMGNN: An Efficient, Effective and Generalizable Algorithm for Influence Maximization in Social Networks

    by Haotian Zhang, Kai Han, Zhizhuo Yin, Shuang Cui, Jing Tang, Pan Hui

    Influence Maximization (IM) is a crucial problem in social network analysis and has been extensively studied. Traditional approaches rely on designing approximation algorithms using network sampling; however, these methods lack generalizability and depend on an explicit definition of the influence diffusion model as input. Recently, researchers have turned to deep learning methods to address the shortcomings of traditional IM algorithms, but current learning-based IM algorithms still suffer from severe deficiencies in scalability and generalizability. In this paper, we propose IMGNN, a simple, efficient, effective, and generalizable algorithm powered by graph neural networks. IMGNN is a learning-based IM algorithm with strong generalization capability that reduces the overhead of model retraining while also providing fast seed set inference speed. As a result, IMGNN achieves better performance in terms of both efficiency and effectiveness compared to existing IM algorithms. Its exceptional generalization capability also enables it to be trained on small-scale graphs and directly infer the seed node set for large-scale graphs. IMGNN achieves these advantages by adopting a novel design for feature construction and model training, utilizing features constructed from influence propagations over graphs with randomly skipped nodes. This approach enables IMGNN to avoid overfitting to specific network structures while employing a unique technique to improve time efficiency by training on smaller networks. We have conducted extensive experiments using real-world social networks with up to 40 million nodes, and the results strongly demonstrate the superiority of IMGNN in terms of influence spread, seed node set inference speed, and generalizability.


  • Open Access

    Fairness in Streaming Submodular Maximization Subject to a Knapsack Constraint

    by Shuang Cui, Kai Han, Shaojie Tang, Feng Li, 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.


  • Open Access

    Streaming Algorithms for Constrained Submodular Maximization

    by Shuang Cui, Kai Han, Jing Tang, He Huang, Xueying 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.


  • Open Access

    Streaming Algorithms for Constrained Submodular Maximization

    by Shuang Cui, Kai Han, Jing Tang, He Huang, Xueying 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.


  • Open Access

    Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives

    by He Huang, Kai Han, Shuang Cui, 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.


  • Open Access

    Constrained Subset Selection from Data Streams for Profit Maximization

    by Shuang Cui, Kai Han, Jing Tang, 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.


  • Open Access

    Streaming Algorithms for Constrained Submodular Maximization

    by Shuang Cui, Kai Han, Jing Tang, He Huang, Xueying Li, Zhiyu Li

    It is of great importance to design streaming algorithms for submodular maximization, as many applications (e.g., crowdsourcing) have large volume of data satisfying the well-known ''diminishing returns'' property, which cannot be handled by offline algorithms requiring full access to the whole dataset. However, streaming submodular maximization has been less studied than the offline algorithms due to the hardness brought by more stringent requirements on memory consumption. In this paper, we consider the fundamental problem of Submodular Maximization under k -System and d -Knapsack constraints (SMSK), which has only been successfully addressed by offline algorithms in previous studies, and we propose the first streaming algorithm for it with provable performance bounds. Our approach adopts a novel algorithmic framework dubbed MultiplexGreedy , making it also perform well under a single k -system constraint. For the special case of SMSK with only d -knapsack constraints, we further propose a streaming algorithm with better performance ratios than the state-of-the-art algorithms. As the SMSK problem generalizes most of the major problems studied in submodular maximization, our algorithms have wide applications in big data processing.