A set of categorical items is a common data structure used in various applications, such as customer orders in online shopping. With the rise of big data and e-commerce, there is an increasing need to store such a large number of set data efficiently. This paper presents a novel lossless compression method that uses binary trees for set compression. The compressed code is generated by performing a depth-first search for items in the set on the binary tree. We prove that finding the optimal tree for minimizing the total code length for a given collection of sets is NP-hard, and the problem even remains NP-hard when we only need to assign items to the leaf nodes of a given tree. A heuristic algorithm is then proposed for building trees. To further improve the compression efficiency, we incorporate the entropy coding method into the coding process. Moreover, we reveal the underlying probabilistic expression of the binary tree model and present the conditional independence structure of the model. To validate the effectiveness of the proposed method, empirical studies are conducted on two real-world online e-commerce datasets. The results show that the proposed coding method significantly reduces the storage space required for set data and the tree structure for compressing sets can help identify conditional independent items.

Transformer-based models have gained significant traction in sequential recommender systems (SRSs) for their ability to capture user-item interactions effectively. However, these models often suffer from high computational costs and slow inference. Meanwhile, existing efficient SRS approaches struggle to embed high-quality semantic and positional information into latent representations. To tackle these challenges, this paper introduces GLINT-RU, a lightweight and efficient SRS leveraging a single-layer dense selective Gated Recurrent Units (GRU) module to accelerate inference. By incorporating a dense selective gate, GLINT-RU adaptively captures temporal dependencies and fine-grained positional information, generating high-quality latent representations. Additionally, a parallel mixing block infuses fine-grained positional features into user-item interactions, enhancing both recommendation quality and efficiency. Extensive experiments on three datasets demonstrate that GLINT-RU achieves superior prediction accuracy and inference speed, outperforming baselines based on RNNs, Transformers, MLPs, and SSMs. These results establish GLINT-RU as a powerful and efficient solution for SRSs. The implementation code is publicly available for reproducibility. https://github.com/szhang-cityu/GLINT-RU.

Service composition (SC) is a pivotal step in allocating budgeted cloud services to fulfill requests arriving on the service platform. These requests usually arrive in an online pattern, i.e., we do not know which request comes next until the request realizes itself. In addition, new services and service providers are eager to join the platform. Thus, a legitimate concern arises: how to allocate services with such service replenishment for the online setting, especially when no prior knowledge is available for the replenishment or requests? To tackle this challenging problem, we develop a Dual-Price based Online Learning (DPOL) algorithm, and prove that DPOL can achieve a sub-linear regret bound of against the offline benchmark, where T is the length of the planning horizon. Also, numerical experiments on synthetic datasets validate that the performance of our algorithms outperforms other baseline policies.

Recent years have witnessed a growing trend toward employing deep reinforcement learning (Deep-RL) to derive heuristics for combinatorial optimization (CO) problems on graphs. Maximum Coverage Problem (MCP) and its probabilistic variant on social networks, Influence Maximization (IM), have been particularly prominent in this line of research. In this paper, we present a comprehensive benchmark study that thoroughly investigates the effectiveness and efficiency of five recent Deep-RL methods for MCP and IM. These methods were published in top data science venues, namely S2V-DQN, Geometric-QN, GCOMB, RL4IM, and LeNSE. Our findings reveal that, across various scenarios, the Lazy Greedy algorithmconsistently outperforms allDeep-RL methods for MCP. In the case of IM, theoretically sound algorithms like IMM and OPIM demonstrate superior performance compared to Deep-RL methods in most scenarios. Notably, we observe anabnormal phenomenonin IM problem where Deep-RL methods slightly outperform IMM and OPIM when the influence spread nearly does not increase as the budget increases. Furthermore, our experimental results highlight common issues when applying Deep-RL methods to MCP and IM in practical settings. Finally, we discuss potential avenues for improving Deep-RL methods. Our benchmark study sheds light on potential challenges in current deep reinforcement learning research for solving combinatorial optimization problems.

Optimizing the assortment of products to display to customers is key to increasing revenue for both offline and online retailers. To trade-off between exploring customers’ preferences and exploiting customers’ choices learned from data, in this article, by adopting the Multi-Nomial Logit (MNL) choice model to capture customers’ choices over products, we study the problem of optimizing assortments over a planning horizon$T$for maximizing the profit of the retailer. To make the problem setting more practical, we consider both the inventory constraint and the limited switches constraint, where the retailer is forced to stop the sales when the resources are depleted and is forbidden to switch the assortment shown to customers too many times. Such a setting suits the case when an online retailer wants to optimize the assortment selection for a population of customers dynamically. We develop an efficient UCB-like algorithm to optimize the assortments while learning customers’ choices from data. We prove that our algorithm can achieve a sub-linear regret bound$\tilde{O}(T^{\max \lbrace 2/3-\alpha /3,1/2\rbrace })$if$O(T^\alpha)$switches are allowed. Extensive numerical experiments show that our algorithm outperforms baselines, and the gap between our algorithm's performance and the theoretical upper bound is small.

Graph learning methods have achieved remarkable performance in various domains such as social recommendation, financial fraud detection, and so on. In real applications, the underlying graph is often dynamically evolving and thus, some recent studies focus on integrating the temporal topology information of graphs into the GNN for learning graph embedding. However, the robustness of training GNNs for dynamic graphs has not been discussed so far. The major reason is how to attack dynamic graph embedding still remains largely untouched, let alone how to defend against the attacks. To enable robust training of GNNs for dynamic graphs, in this paper, we investigate the problem of how to generate attacks and defend against attacks for dynamic graph embedding. Attacking dynamic graph embedding is more challenging than attacking static graph embedding as we need to understand the temporal dynamics of graphs as well as its impact on the embedding and the injected perturbations should be distinguished from the natural evolution. In addition, the defense is very challenging as the perturbations may be hidden within the natural evolution. To tackle these technical challenges, in this paper, we first develop a novel gradient-based attack method from an optimization perspective to generate perturbations to fool dynamic graph learning methods, where a key idea is to use gradient dynamics to attack the natural dynamics of the graph. Further, we borrow the idea of the attack method and integrate it with adversarial training to train a more robust dynamic graph learning method to defend against hand-crafted attacks. Finally, extensive experiments on two real-world datasets demonstrate the effectiveness of the proposed attack and defense method, where our defense method not only achieves comparable performance on clean graphs but also significantly increases the defense performance on attacked graphs.

Maximizing a monotone submodular function is a fundamental task in data mining, machine learning, economics, and statistics. In this paper, we present two communication-efficient decentralized online algorithms for the monotone continuous DR-submodular maximization problem, both of which reduce the number of per-function gradient evaluations and per-round communication complexity from T3/2 to 1. The first one, One-shot Decentralized Meta-Frank-Wolfe~(Mono-DMFW), achieves a (1-1/e)-regret bound of O(T4/5). As far as we know, this is the first one-shot and projection-free decentralized online algorithm for monotone continuous DR-submodular maximization. Next, inspired by the non-oblivious boosting function[29], we propose the Decentralized Online Boosting Gradient Ascent (DOBGA) algorithm, which attains a (1-1/e)-regret of O(√T). To the best of our knowledge, this is the first result to obtain the optimal O(√T) against a (1-1/e)-approximation with only one gradient inquiry for each local objective function per step. Finally, various experimental results confirm the effectiveness of the proposed methods.

In this article, we present a fast real-time tangled memory network that segments the objects effectively and efficiently for semi-supervised video object segmentation (VOS). We propose a tangled reference encoder and a memory bank organization mechanism based on a state estimator to fully utilize the mask features and alleviate memory overhead and computational burden brought by the unlimited memory bank used in many memory-based methods. First, the tangled memory network exploits the mask features that uncover abundant object information like edges and contours but are not fully explored in existing methods. Specifically, a tangled two-stream reference encoder is designed to extract and fuse the features from both RGB frames and the predicted masks. Second, to indicate the quality of the predicted mask and feedback the online prediction state for organizing the memory bank, we devise a target state estimator to learn the IoU score between the predicted mask and ground truth. Moreover, to accelerate the forward process and avoid memory overflow, we use a memory bank of fixed size to store historical features by designing a new efficient memory bank organization mechanism based on the mask state score provided by the state estimator. We conduct comprehensive experiments on the public benchmarks DAVIS and YouTube-VOS, demonstrating that our method obtains competitive results while running at high speed (66 FPS on the DAVIS16-val set).

The ability to predict future customer orders is of significant value to retailers in making many crucial operational decisions. Different from next basket prediction or temporal set prediction, which focuses on predicting a subset of items for a single user, this paper aims for the distributional information of future orders, i.e., the possible subsets of items and their frequencies (probabilities), which is required for decisions such as assortment selection for front-end warehouses and capacity evaluation for fulfillment centers. Based on key statistics of a real order dataset from Tmall supermarket, we show the challenges of order prediction. Motivated by our analysis that biased models of order distribution can still help improve the quality of order prediction, we design a generative model to capture the order distribution for customer order prediction. Our model utilizes representation learning to embed items into a Euclidean space and design a highly efficient SGD algorithm to learn the item embeddings. Future order prediction is done by calibrating orders obtained by random walks over the embedding graph. The experiments show that our model outperforms all the existing methods. The benefit of our model is also illustrated with an application to assortment selection for front-end warehouses.

The Kolmogorov-Smirnov (KS) test is popularly used in many applications, such as anomaly detection, astronomy, database security and AI systems. One challenge remained untouched is how we can obtain an explanation on why a test set fails the KS test. In this paper, we tackle the problem of producing counterfactual explanations for test data failing the KS test. Concept-wise, we propose the notion of most comprehensible counterfactual explanations, which accommodates both the KS test data and the user domain knowledge in producing explanations. Computation-wise, we develop an efficient algorithm MOCHE (for MOst CompreHensible Explanation) that avoids enumerating and checking an exponential number of subsets of the test set failing the KS test. MOCHE not only guarantees to produce the most comprehensible counterfactual explanations, but also is orders of magnitudes faster than the baselines. Experiment-wise, we present a systematic empirical study on a series of benchmark real datasets to verify the effectiveness, efficiency and scalability of most comprehensible counterfactual explanations and MOCHE.

Given a set V , the problem of unconstrained submodular maximization with modular costs (USM-MC) asks for a subset S ⊆ V that maximizes f ( S ) - c ( S ), where f is a non-negative, monotone, and submodular function that gauges the utility of S , and c is a non-negative and modular function that measures the cost of S. This problem finds applications in numerous practical scenarios, such as profit maximization in viral marketing on social media. This paper presents ROI-Greedy, a polynomial time algorithm for USM-MC that returns a solution S satisfying [EQUATION], where S * is the optimal solution to USM-MC. To our knowledge, ROI-Greedy is the first algorithm that provides such a strong approximation guarantee. In addition, we show that this worst-case guarantee is tight , in the sense that no polynomial time algorithm can ensure [EQUATION], for any ϵ > 0. Further, we devise a non-trivial extension of ROI-Greedy to solve the profit maximization problem, where the precise value of f ( S ) for any set S is unknown and can only be approximated via sampling. Extensive experiments on benchmark datasets demonstrate that ROI-Greedy significantly outperforms competing methods in terms of the tradeoff between efficiency and solution quality.

Influence analysis aims at detecting influential vertices in networks and utilizing them in cost-effective business strategies. Influence analysis in large-scale networks is a key technique in many important applications ranging from viral marketing and online advertisement to recommender systems, and thus has attracted great interest from both academia and industry. Early investigations on influence analysis often assume static networks. However, it is well recognized that real networks like social networks and the web network are not static but evolve rapidly over time. Thus, to make the results of influence analysis in real networks up-to-date, we have to take network evolution into consideration. Incorporating evolution of networks into influence analysis raises many new challenges, since an evolving network often updates at a fast rate and, except for the network owner, the evolution is usually even not entirely known to people. In this survey, we provide an overview on recent research in influence analysis in evolving networks, which has not been systematically reviewed in literature. We first revisit mathematical models of evolving networks and commonly used influence models. Then, we review recent research in five major tasks of evolving network influence analysis. We also discuss some future directions to explore.

Imagine we are introducing a new product through a social network, where we know for each user in the network the function of purchase probability with respect to discount. Then, what discounts should we offer to those social network users so that, under a predefined budget, the adoption of the product is maximized in expectation? Although influence maximization has been extensively explored, this appealing practical problem still cannot be answered by the existing influence maximization methods. In this article, we tackle the problem systematically. We formulate the general continuous influence maximization problem, investigate the essential properties, and develop a general coordinate descent algorithmic framework as well as the engineering techniques for practical implementation. Our investigation does not assume any specific influence model and thus is general and principled. At the same time, using the most popularly adopted triggering model as a concrete example, we demonstrate that more efficient methods are feasible under specific influence models. Our extensive empirical study on four benchmark real-world networks with synthesized purchase probability curves clearly illustrates that continuous influence maximization can improve influence spread significantly with very moderate extra running time comparing to the classical influence maximization methods.

Tracking influential users in a dynamic social network is a fundamental step in fruitful applications, such as social recommendation, network topology optimization, and blocking rumour spreading. The major obstacle in mining top influential users is that estimating users' influence spreads is \#P-hard under most influence propagation models. Previous studies along this line either seek heuristic solutions or may return meaningless results due to the lack of prior knowledge about users' influence in the dynamic network. In this paper, we tackle the problem of tracking top-k influential individuals in a dynamic social network. When a top-k query is issued, our algorithm returns a set S of more than k users. With high probability, our algorithm guarantees that S contains all real top-k influential users and there exists a relative error ε < 1$ such that the least influential user in S has influence at least $(1-ε) I^k$, where $I^k$ is the influence of the k-th most influential user and we can adjust ε via parameter settings. Controlling such a relative error enables us to obtain meaningful results even when we know nothing about the value of $I^k$ or $I^k$ changes over time in the dynamic network. In addition to the thorough theoretical results, our experimental results on large real networks clearly demonstrate the effectiveness and efficiency of our algorithm.

Given a database network where each vertex is associated with a transaction database, we are interested in finding theme communities. Here, a theme community is a cohesive subgraph such that a common pattern is frequent in all transaction databases associated with the vertices in the subgraph. Finding all theme communities from a database network enjoys many novel applications. However, it is challenging since even counting the number of all theme communities in a database network is #P-hard. Inspired by the observation that a theme community shrinks when the length of the pattern increases, we investigate several properties of theme communities and develop TCFI, a scalable algorithm that uses these properties to effectively prune the patterns that cannot form any theme community. We also design TC-Tree, a scalable algorithm that decomposes and indexes theme communities efficiently. Retrieving a ranked list of theme communities from a TC-Tree of hundreds of millions of theme communities takes less than 1 second. Extensive experiments and a case study demonstrate the effectiveness and scalability of TCFI and TC-Tree in discovering and querying meaningful theme communities from large database networks.

Given a temporal weighted graph that consists of a potentially endless stream of updates, we are interested in finding density bursting subgraphs (DBS for short), where a DBS is a subgraph that accumulates its density at the fastest speed. Online DBS detection enjoys many novel applications. At the same time, it is challenging since the time duration of a DBS can be arbitrarily long but a limited size storage can buffer only up to a certain number of updates. To tackle this problem, we observe the critical decomposability of DBSs and show that a DBS with a long time duration can be decomposed into a set of indecomposable DBSs with equal or larger burstiness. We further prove that the time duration of an indecomposable DBS is upper bounded and propose an efficient method TopkDBSOL to detect indecomposable DBSs in an online manner. Extensive experiments demonstrate the effectiveness, efficiency and scalability of TopkDBSOL in detecting significant DBSs from temporal graphs in real applications.

Dense subgraph discovery is a key primitive in many graph mining applications, such as detecting communities in social networks and mining gene correlation from biological data. Most studies on dense subgraph mining only deal with one graph. However, in many applications, we have more than one graph describing relations among a same group of entities. In this paper, given two graphs sharing the same set of vertices, we investigate the problem of detecting subgraphs that contrast the most with respect to density. We call such subgraphs Density Contrast Subgraphs, or DCS in short. Two widely used graph density measures, average degree and graph affinity, are considered. For both density measures, mining DCS is equivalent to mining the densest subgraph from a "difference" graph, which may have both positive and negative edge weights. Due to the existence of negative edge weights, existing dense subgraph detection algorithms cannot identify the subgraph we need. We prove the computational hardness of mining DCS under the two graph density measures and develop efficient algorithms to find DCS. We also conduct extensive experiments on several real-world datasets to evaluate our algorithms. The experimental results show that our algorithms are both effective and efficient.

For a long time, PageRank has been widely used for authority computation and has been adopted as a solid baseline for evaluating social influence related applications. However, when measuring the authority of network nodes, the traditional PageRank method does not take the nodes’ prior knowledge into consideration. Also, the connection between PageRank and social influence modeling methods is not clearly established. To that end, this article provides a focused study on understanding PageRank as well as the relationship between PageRank and social influence analysis. Along this line, we first propose a linear social influence model and reveal that this model generalizes the PageRank-based authority computation by introducing some constraints. Then, we show that the authority computation by PageRank can be enhanced if exploiting more reasonable constraints (e.g., from prior knowledge). Next, to deal with the computational challenge of linear model with general constraints, we provide an upper bound for identifying nodes with top authorities. Moreover, we extend the proposed linear model for better measuring the authority of the given node sets, and we also demonstrate the way to quickly identify the top authoritative node sets. Finally, extensive experimental evaluations on four real-world networks validate the effectiveness of the proposed linear model with respect to different constraint settings. The results show that the methods with more reasonable constraints can lead to better ranking and recommendation performance. Meanwhile, the upper bounds formed by PageRank values could be used to quickly locate the nodes and node sets with the highest authorities.

In a social network, even about the same information the excitement between different users are different. If we want to spread a piece of new information and maximize the expected total amount of excitement, which seed users should we choose? This problem indeed is substantially different from the renowned influence maximization problem and cannot be tackled using the existing approaches. In this paper, motivated by the demand in a few interesting applications, we model the novel problem of activity maximization, and tackle the problem systematically. We first analyze the complexity and the approximability of the problem. We develop an upper bound and a lower bound that are submodular so that the Sandwich framework can be applied. We then devise a polling-based randomized algorithm that guarantees a data dependent approximation factor. Our experiments on four real data sets clearly verify the effectiveness and scalability of our method, as well as the advantage of our method against the other heuristic methods.

In this paper, we tackle a challenging problem inherent in a series of applications: tracking the influential nodes in dynamic networks. Specifically, we model a dynamic network as a stream of edge weight updates. This general model embraces many practical scenarios as special cases, such as edge and node insertions, deletions as well as evolving weighted graphs. Under the popularly adopted linear threshold model and independent cascade model, we consider two essential versions of the problem: finding the nodes whose influences passing a user specified threshold and finding the top-k most influential nodes. Our key idea is to use the polling-based methods and maintain a sample of random RR sets so that we can approximate the influence of nodes with provable quality guarantees. We develop an efficient algorithm that incrementally updates the sample random RR sets against network changes. We also design methods to determine the proper sample sizes for the two versions of the problem so that we can provide strong quality guarantees and, at the same time, be efficient in both space and time. In addition to the thorough theoretical results, our experimental results on five real network data sets clearly demonstrate the effectiveness and efficiency of our algorithms.

Imagine we are introducing a new product through a social network, where we know for each user in the network the purchase probability curve with respect to discount. Then, what discount should we offer to those social network users so that the adoption of the product is maximized in expectation under a predefined budget? Although influence maximization has been extensively explored, surprisingly, this appealing practical problem still cannot be answered by the existing influence maximization methods. In this paper, we tackle the problem systematically. We formulate the general continuous influence maximization problem, investigate the essential properties, and develop a general coordinate descent algorithm as well as the engineering techniques for practical implementation. Our investigation does not assume any specific influence model and thus is general and principled. At the same time, using the most popularly adopted independent influence model as a concrete example, we demonstrate that more efficient methods are feasible under specific influence models. Our extensive empirical study on four benchmark real world networks with synthesized purchase probability curves clearly illustrates that continuous influence maximization can improve influence spread significantly with very moderate extra running time comparing to the classical influence maximization methods.