Shuang Cui
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:
- Kai Han
Shanghai University of Finance and Economics, Shanghai, China
10 shared publications - He Huang
Soochow University, Suzhou, China
8 shared publications - Jing Tang
The Hong Kong University of Science and Technology
7 shared publications - Shaojie Tang
Department of Management Science and Systems, University at Buffalo, Buffalo, New York, USA
3 shared publications - Xueying Li
Alibaba Group, Hangzhou, China
3 shared publications - Zhiyu Li
MemTensor (Shanghai) Technology Co Ltd
3 shared publications
Latest Publications
- Open Access
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 164-175
Submodular Maximization under k -System Constraints in Parallel: A Trifecta of Approximation, Adaptivity, and Query Complexity
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.
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 164-175
Open AccessSubmodular Maximization under k -System Constraints in Parallel: A Trifecta of Approximation, Adaptivity, and Query Complexity
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
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1904-1915
IMGNN: An Efficient, Effective and Generalizable Algorithm for Influence Maximization in Social Networks
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.
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 1904-1915
Open AccessIMGNN: An Efficient, Effective and Generalizable Algorithm for Influence Maximization in Social Networks
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.
- 8 May 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 345
Efficient and effective budget-feasible mechanisms for submodular valuations
- 8 May 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 345
Efficient and effective budget-feasible mechanisms for submodular valuations
- Open Access
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 4710-4721
Linear-Time Algorithms for Representative Subset Selection From Data Streams
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 4710-4721
Open AccessLinear-Time Algorithms for Representative Subset Selection From Data Streams
- Open Access
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 514-525
Fairness in Streaming Submodular Maximization Subject to a Knapsack Constraint
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.
- 24 August 2024
- Published by Association for Computing Machinery (ACM)
- p. 514-525
Open AccessFairness in Streaming Submodular Maximization Subject to a Knapsack Constraint
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
- 26 June 2023
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 51 (1) , 65-66
Streaming Algorithms for Constrained Submodular Maximization
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.
- 26 June 2023
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 51 (1) , 65-66
Open AccessStreaming Algorithms for Constrained Submodular Maximization
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
- 19 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 65-66
Streaming Algorithms for Constrained Submodular Maximization
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.
- 19 June 2023
- Published by Association for Computing Machinery (ACM)
- p. 65-66
Open AccessStreaming Algorithms for Constrained Submodular Maximization
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
- 30 April 2023
- Published by Association for Computing Machinery (ACM)
- p. 3530-3540
Randomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives
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.
- 30 April 2023
- Published by Association for Computing Machinery (ACM)
- p. 3530-3540
Open AccessRandomized Pricing with Deferred Acceptance for Revenue Maximization with Submodular Objectives
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
- 30 April 2023
- Published by Association for Computing Machinery (ACM)
- p. 1822-1831
Constrained Subset Selection from Data Streams for Profit Maximization
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
- Published by Association for Computing Machinery (ACM)
- p. 1822-1831
Open AccessConstrained Subset Selection from Data Streams for Profit Maximization
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
- 8 December 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 6 (3) , 1-32
Streaming Algorithms for Constrained Submodular Maximization
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.
- 8 December 2022
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Measurement and Analysis of Computing Systems
- Vol. 6 (3) , 1-32
Open AccessStreaming Algorithms for Constrained Submodular Maximization
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.