Guangyi Zhang
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
Guangyi Zhang has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Aristides Gionis
KTH Royal Institute of Technology, Stockholm, Sweden and Digital Futures, Stockholm, Sweden
7 shared publications - Nikolaj Tatti
University of Helsinki, Helsinki, Finland
5 shared publications - Anne Juuti
Helsinki University Hospital
1 shared publication - Haoyi Zhou
Beihang University
1 shared publication - Ilie Sarpe
KTH Royal Institute of Technology, Stockholm, Sweden
1 shared publication - Jianwei Liao
Southwest University
1 shared publication
Latest Publications
- Open Access
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 5927-5938
Accelerating Influence Function Estimation for Large Language Models: A Practical Design
Influence functions provide a principled framework for tracing model predictions back to training data, yet existing methods remain impractical for large language models due to prohibitive storage and I/O costs. Prior approaches face two critical barriers: the Fidelity Gap from coarse curvature approximations, and the I/O bottleneck from materializing per-example gradients, which renders million-scale datasets infeasible. We propose StructInf, a structure-aware influence estimation framework that addresses both gaps through system-algorithm co-design. For fidelity, we first replace the indefinite Hessian with an adaptive block-diagonal damped empirical Fisher surrogate, computed via quadratically convergent Newton--Schulz iterations. For efficiency, we then introduce a streaming algorithm that eliminates per-example gradient storage entirely, reducing space complexity from O(N • d) to O(d) and enabling processing of million-scale training instances on consumer hardware, where N denotes the number of training instances and d the parameter size. We further identify and resolve Split-View Bias, a distributed pitfall where naive averaging of local curvatures fails, via a distributed gradient calibration strategy that synchronizes global statistics with minimal communication. Finally, we conduct comprehensive experiments to evaluate StructInf against other baselines. Unlike prior methods requiring hours of pre-computation or TB-scale storage, StructInf enables real-time data selection during training. Across GLUE and instruction-tuning benchmarks, StructInf achieves up to +26% AUC on MRPC and average 7× speedup for 7B-scale models, making high-fidelity influence analysis practical on a single RTX 4090. These results suggest that practical IF for LoRA-tuned LLMs benefits from joint optimization of curvature modeling, memory management, and distributed coordination.
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 5927-5938
Open AccessAccelerating Influence Function Estimation for Large Language Models: A Practical Design
Influence functions provide a principled framework for tracing model predictions back to training data, yet existing methods remain impractical for large language models due to prohibitive storage and I/O costs. Prior approaches face two critical barriers: the Fidelity Gap from coarse curvature approximations, and the I/O bottleneck from materializing per-example gradients, which renders million-scale datasets infeasible. We propose StructInf, a structure-aware influence estimation framework that addresses both gaps through system-algorithm co-design. For fidelity, we first replace the indefinite Hessian with an adaptive block-diagonal damped empirical Fisher surrogate, computed via quadratically convergent Newton--Schulz iterations. For efficiency, we then introduce a streaming algorithm that eliminates per-example gradient storage entirely, reducing space complexity from O(N • d) to O(d) and enabling processing of million-scale training instances on consumer hardware, where N denotes the number of training instances and d the parameter size. We further identify and resolve Split-View Bias, a distributed pitfall where naive averaging of local curvatures fails, via a distributed gradient calibration strategy that synchronizes global statistics with minimal communication. Finally, we conduct comprehensive experiments to evaluate StructInf against other baselines. Unlike prior methods requiring hours of pre-computation or TB-scale storage, StructInf enables real-time data selection during training. Across GLUE and instruction-tuning benchmarks, StructInf achieves up to +26% AUC on MRPC and average 7× speedup for 7B-scale models, making high-fidelity influence analysis practical on a single RTX 4090. These results suggest that practical IF for LoRA-tuned LLMs benefits from joint optimization of curvature modeling, memory management, and distributed coordination.
- Open Access
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-27
LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework
Inverted indexes (a.k.a. posting lists) are core data structures in search engines and database systems, where compression is crucial to reduce memory footprint and accelerate query processing. The key challenge lies in encoding a sorted list of integer identifiers in a compact, lossless form while supporting fast decoding. Motivated by recent studies on learned data structures, this work presents LICO, a novel L earned I nverted index CO mpression framework that encodes sorted integers with error-bounded machine learning models and auxiliary residual arrays for lossless reconstruction. Compared to classical schemes such as P4Delta and Elias-Fano, and recent learning-based approaches such as LA-vector and LeCo, LICO offers three key advantages: (1) a succinct data structure explicitly designed for leveraging parallelism offered by modern hardware; (2) fully automatic adaptation to data distributions without hand-tuned hyperparameters; and (3) rigorous theoretical guarantees on compression ratios. Extensive experiments on web-scale datasets and query workloads show that LICO achieves Pareto-optimal trade-offs between index size and query latency. All code and artifacts are available at: https://github.com/xianyuzhuruc/LICO.
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-27
Open AccessLICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework
Inverted indexes (a.k.a. posting lists) are core data structures in search engines and database systems, where compression is crucial to reduce memory footprint and accelerate query processing. The key challenge lies in encoding a sorted list of integer identifiers in a compact, lossless form while supporting fast decoding. Motivated by recent studies on learned data structures, this work presents LICO, a novel L earned I nverted index CO mpression framework that encodes sorted integers with error-bounded machine learning models and auxiliary residual arrays for lossless reconstruction. Compared to classical schemes such as P4Delta and Elias-Fano, and recent learning-based approaches such as LA-vector and LeCo, LICO offers three key advantages: (1) a succinct data structure explicitly designed for leveraging parallelism offered by modern hardware; (2) fully automatic adaptation to data distributions without hand-tuned hyperparameters; and (3) rigorous theoretical guarantees on compression ratios. Extensive experiments on web-scale datasets and query workloads show that LICO achieves Pareto-optimal trade-offs between index size and query latency. All code and artifacts are available at: https://github.com/xianyuzhuruc/LICO.
- Open Access
- 10 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 4096-4105
SpeedSteiner: A Fast O ( k 1/2 )-Approximation Algorithm for Directed Steiner Tree
- 10 November 2025
- Published by Association for Computing Machinery (ACM)
- p. 4096-4105
Open AccessSpeedSteiner: A Fast O ( k 1/2 )-Approximation Algorithm for Directed Steiner Tree
- Open Access
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 3193-3203
Efficient and Practical Approximation Algorithms for Advertising in Content Feeds
- 22 April 2025
- Published by Association for Computing Machinery (ACM)
- p. 3193-3203
Open AccessEfficient and Practical Approximation Algorithms for Advertising in Content Feeds
- Open Access
- 30 September 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (4) , 1-28
Discovering Top-k Relevant and Diversified Rules
This paper studies the problem of discovering top- k relevant and diversified rules. Given a real-life dataset, it is to mine a set of k rules that are as close to users' interest as possible, and meanwhile, as diverse to each other as possible. It aims to reduce excessive irrelevant rules commonly returned by rule discovery. As a testbed, we consider Entity Enhancing Rules (REEs), which subsume popular data quality rules as special cases. We train a relevance model to learn users' prior knowledge, rank rules based on users' need, and propose four diversity measures to assess the diversity between rules. Based on these measures, we formulate a new discovery problem. We show that the bi-criteria discovery problem is NP-complete and hard to approximate. This said, we develop a practical algorithm for the problem, and prove its approximation bounds under certain conditions. Moreover, we develop optimization techniques to speed up the process, and parallelize the algorithm such that it guarantees to reduce runtime when given more processors. Using real-life data, we empirically verify that on average, the top-10 REEs discovered by our algorithm is able to catch 77.5% of errors detected by the entire set Σ all of REEs and achieve F_1 = 0.74 for real error detection; moreover, discovering top-ranked REEs is 62.4X faster than mining Σ all .
- 30 September 2024
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 2 (4) , 1-28
Open AccessDiscovering Top-k Relevant and Diversified Rules
This paper studies the problem of discovering top- k relevant and diversified rules. Given a real-life dataset, it is to mine a set of k rules that are as close to users' interest as possible, and meanwhile, as diverse to each other as possible. It aims to reduce excessive irrelevant rules commonly returned by rule discovery. As a testbed, we consider Entity Enhancing Rules (REEs), which subsume popular data quality rules as special cases. We train a relevance model to learn users' prior knowledge, rank rules based on users' need, and propose four diversity measures to assess the diversity between rules. Based on these measures, we formulate a new discovery problem. We show that the bi-criteria discovery problem is NP-complete and hard to approximate. This said, we develop a practical algorithm for the problem, and prove its approximation bounds under certain conditions. Moreover, we develop optimization techniques to speed up the process, and parallelize the algorithm such that it guarantees to reduce runtime when given more processors. Using real-life data, we empirically verify that on average, the top-10 REEs discovered by our algorithm is able to catch 77.5% of errors detected by the entire set Σ all of REEs and achieve F_1 = 0.74 for real error detection; moreover, discovering top-ranked REEs is 62.4X faster than mining Σ all .
- Open Access
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 3229-3238
Finding Favourite Tuples on Data Streams with Provably Few Comparisons
One of the most fundamental tasks in data science is to assist a user with unknown preferences in finding high-utility tuples within a large database. To accurately elicit the unknown user preferences, a widely-adopted way is by asking the user to compare pairs of tuples. In this paper, we study the problem of identifying one or more high-utility tuples by adaptively receiving user input on a minimum number of pairwise comparisons. We devise a single-pass streaming algorithm, which processes each tuple in the stream at most once, while ensuring that the memory size and the number of requested comparisons are in the worst case logarithmic in n, where n is the number of all tuples. An important variant of the problem, which can help to reduce human error in comparisons, is to allow users to declare ties when confronted with pairs of tuples of nearly equal utility. We show that the theoretical guarantees of our method can be maintained for this important problem variant. In addition, we show how to enhance existing pruning techniques in the literature by leveraging powerful tools from mathematical programming. Finally, we systematically evaluate all proposed algorithms over both synthetic and real-life datasets, examine their scalability, and demonstrate their superior performance over existing methods.
- 4 August 2023
- Published by Association for Computing Machinery (ACM)
- p. 3229-3238
Open AccessFinding Favourite Tuples on Data Streams with Provably Few Comparisons
One of the most fundamental tasks in data science is to assist a user with unknown preferences in finding high-utility tuples within a large database. To accurately elicit the unknown user preferences, a widely-adopted way is by asking the user to compare pairs of tuples. In this paper, we study the problem of identifying one or more high-utility tuples by adaptively receiving user input on a minimum number of pairwise comparisons. We devise a single-pass streaming algorithm, which processes each tuple in the stream at most once, while ensuring that the memory size and the number of requested comparisons are in the worst case logarithmic in n, where n is the number of all tuples. An important variant of the problem, which can help to reduce human error in comparisons, is to allow users to declare ties when confronted with pairs of tuples of nearly equal utility. We show that the theoretical guarantees of our method can be maintained for this important problem variant. In addition, we show how to enhance existing pruning techniques in the literature by leveraging powerful tools from mathematical programming. Finally, we systematically evaluate all proposed algorithms over both synthetic and real-life datasets, examine their scalability, and demonstrate their superior performance over existing methods.
- Open Access
Ranking with submodular functions on the fly
Maximizing submodular functions have been studied extensively for a wide range of subset-selection problems. However, much less attention has been given to the role of submodularity in sequence-selection and ranking problems. A recently-introduced framework, named \emph{maximum submodular ranking} (MSR), tackles a family of ranking problems that arise naturally when resources are shared among multiple demands with different budgets. For example, the MSR framework can be used to rank web pages for multiple user intents. In this paper, we extend the MSR framework in the streaming setting. In particular, we consider two different streaming models and we propose practical approximation algorithms. In the first streaming model, called \emph{function arriving}, we assume that submodular functions (demands) arrive continuously in a stream, while in the second model, called \emph{item arriving}, we assume that items (resources) arrive continuously. Furthermore, we study the MSR problem with additional constraints on the output sequence, such as a matroid constraint that can ensure fair exposure among items from different groups. These extensions significantly broaden the range of problems that can be captured by the MSR framework. On the practical side, we develop several novel applications based on the MSR formulation, and empirically evaluate the performance of the proposed~methods.
Open AccessRanking with submodular functions on the fly
Maximizing submodular functions have been studied extensively for a wide range of subset-selection problems. However, much less attention has been given to the role of submodularity in sequence-selection and ranking problems. A recently-introduced framework, named \emph{maximum submodular ranking} (MSR), tackles a family of ranking problems that arise naturally when resources are shared among multiple demands with different budgets. For example, the MSR framework can be used to rank web pages for multiple user intents. In this paper, we extend the MSR framework in the streaming setting. In particular, we consider two different streaming models and we propose practical approximation algorithms. In the first streaming model, called \emph{function arriving}, we assume that submodular functions (demands) arrive continuously in a stream, while in the second model, called \emph{item arriving}, we assume that items (resources) arrive continuously. Furthermore, we study the MSR problem with additional constraints on the output sequence, such as a matroid constraint that can ensure fair exposure among items from different groups. These extensions significantly broaden the range of problems that can be captured by the MSR framework. On the practical side, we develop several novel applications based on the MSR formulation, and empirically evaluate the performance of the proposed~methods.
- Open Access
- 28 November 2022
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 37 (1) , 434-475
Regularized impurity reduction: accurate decision trees with complexity guarantees
Decision trees are popular classification models, providing high accuracy and intuitive explanations. However, as the tree size grows the model interpretability deteriorates. Traditional tree-induction algorithms, such as C4.5 and CART, rely on impurity-reduction functions that promote the discriminative power of each split. Thus, although these traditional methods are accurate in practice, there has been no theoretical guarantee that they will produce small trees. In this paper, we justify the use of a general family of impurity functions, including the popular functions of entropy and Gini-index, in scenarios where small trees are desirable, by showing that a simple enhancement can equip them with complexity guarantees. We consider a general setting, where objects to be classified are drawn from an arbitrary probability distribution, classification can be binary or multi-class, and splitting tests are associated with non-uniform costs. As a measure of tree complexity, we adopt the expected cost to classify an object drawn from the input distribution, which, in the uniform-cost case, is the expected number of tests. We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. This approximation factor is tight up to a constant factor under mild assumptions. The algorithm recursively selects a test that maximizes a greedy criterion defined as a weighted sum of three components. The first two components encourage the selection of tests that improve the balance and the cost-efficiency of the tree, respectively, while the third impurity-reduction component encourages the selection of more discriminative tests. As shown in our empirical evaluation, compared to the original heuristics, the enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
- 28 November 2022
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 37 (1) , 434-475
Open AccessRegularized impurity reduction: accurate decision trees with complexity guarantees
Decision trees are popular classification models, providing high accuracy and intuitive explanations. However, as the tree size grows the model interpretability deteriorates. Traditional tree-induction algorithms, such as C4.5 and CART, rely on impurity-reduction functions that promote the discriminative power of each split. Thus, although these traditional methods are accurate in practice, there has been no theoretical guarantee that they will produce small trees. In this paper, we justify the use of a general family of impurity functions, including the popular functions of entropy and Gini-index, in scenarios where small trees are desirable, by showing that a simple enhancement can equip them with complexity guarantees. We consider a general setting, where objects to be classified are drawn from an arbitrary probability distribution, classification can be binary or multi-class, and splitting tests are associated with non-uniform costs. As a measure of tree complexity, we adopt the expected cost to classify an object drawn from the input distribution, which, in the uniform-cost case, is the expected number of tests. We propose a tree-induction algorithm that gives a logarithmic approximation guarantee on the tree complexity. This approximation factor is tight up to a constant factor under mild assumptions. The algorithm recursively selects a test that maximizes a greedy criterion defined as a weighted sum of three components. The first two components encourage the selection of tests that improve the balance and the cost-efficiency of the tree, respectively, while the third impurity-reduction component encourages the selection of more discriminative tests. As shown in our empirical evaluation, compared to the original heuristics, the enhanced algorithms strike an excellent balance between predictive accuracy and tree complexity.
- Open Access
Coresets remembered and items forgotten: submodular maximization with deletions
In recent years we have witnessed an increase on the development of methods for submodular optimization, which have been motivated by the wide applicability of submodular functions in real-world data-science problems. In this paper, we contribute to this line of work by considering the problem of robust submodular maximization against unexpected deletions, which may occur due to privacy issues or user preferences. Specifically, we consider the minimum number of items an algorithm has to remember, in order to achieve a non-trivial approximation guarantee against adversarial deletion of up to $d$ items. We refer to the set of items that an algorithm has to keep before adversarial deletions as a deletion-robust coreset. Our theoretical contributions are two-fold. First, we propose a single-pass streaming algorithm that yields a $(1-2\epsilon)/(4p)$-approximation for maximizing a non-decreasing submodular function under a general p-matroid constraint and requires a coreset of size $k + d/\epsilon$, where $k$ is the maximum size of a feasible solution. To the best of our knowledge, this is the first work to achieve an (asymptotically) optimal coreset, as no constant-factor approximation is possible with a coreset of size sublinear in $d$. Second, we devise an effective offline algorithm that guarantees stronger approximation ratios with a coreset of size $O(d \log(k)/\epsilon)$. We also demonstrate the superior empirical performance of the proposed algorithms in real-life applications.Open AccessCoresets remembered and items forgotten: submodular maximization with deletions
In recent years we have witnessed an increase on the development of methods for submodular optimization, which have been motivated by the wide applicability of submodular functions in real-world data-science problems. In this paper, we contribute to this line of work by considering the problem of robust submodular maximization against unexpected deletions, which may occur due to privacy issues or user preferences. Specifically, we consider the minimum number of items an algorithm has to remember, in order to achieve a non-trivial approximation guarantee against adversarial deletion of up to $d$ items. We refer to the set of items that an algorithm has to keep before adversarial deletions as a deletion-robust coreset. Our theoretical contributions are two-fold. First, we propose a single-pass streaming algorithm that yields a $(1-2\epsilon)/(4p)$-approximation for maximizing a non-decreasing submodular function under a general p-matroid constraint and requires a coreset of size $k + d/\epsilon$, where $k$ is the maximum size of a feasible solution. To the best of our knowledge, this is the first work to achieve an (asymptotically) optimal coreset, as no constant-factor approximation is possible with a coreset of size sublinear in $d$. Second, we devise an effective offline algorithm that guarantees stronger approximation ratios with a coreset of size $O(d \log(k)/\epsilon)$. We also demonstrate the superior empirical performance of the proposed algorithms in real-life applications. - Open Access
- 23 April 2022
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 36 (3) , 1197-1218
Ranking with submodular functions on a budget
Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular functions has mainly been restricted in the context of selecting a set of items. On the other hand, many real-world applications require a solution that is a ranking over a set of items. The problem of ranking in the context of submodular function maximization has been considered before, but to a much lesser extent than item-selection formulations. In this paper, we explore a novel formulation for ranking items with submodular valuations and budget constraints. We refer to this problem asmax-submodular ranking( $$\text {MSR}$$ ). In more detail, given a set of items and a set of non-decreasing submodular functions, where each function is associated with a budget, we aim to find a ranking of the set of items that maximizes the sum of values achieved by all functions under the budget constraints. For the $$\text {MSR}$$ problem with cardinality- and knapsack-type budget constraints we propose practical algorithms with approximation guarantees. In addition, we perform an empirical evaluation, which demonstrates the superior performance of the proposed algorithms against strong baselines.- 23 April 2022
- Published by Springer Nature in Data Mining and Knowledge Discovery
- Vol. 36 (3) , 1197-1218
Open AccessRanking with submodular functions on a budget
Submodular maximization has been the backbone of many important machine-learning problems, and has applications to viral marketing, diversification, sensor placement, and more. However, the study of maximizing submodular functions has mainly been restricted in the context of selecting a set of items. On the other hand, many real-world applications require a solution that is a ranking over a set of items. The problem of ranking in the context of submodular function maximization has been considered before, but to a much lesser extent than item-selection formulations. In this paper, we explore a novel formulation for ranking items with submodular valuations and budget constraints. We refer to this problem asmax-submodular ranking( $$\text {MSR}$$ ). In more detail, given a set of items and a set of non-decreasing submodular functions, where each function is associated with a budget, we aim to find a ranking of the set of items that maximizes the sum of values achieved by all functions under the budget constraints. For the $$\text {MSR}$$ problem with cardinality- and knapsack-type budget constraints we propose practical algorithms with approximation guarantees. In addition, we perform an empirical evaluation, which demonstrates the superior performance of the proposed algorithms against strong baselines.