Given the ubiquity of Uncertain Graphs (UGs), the field of UG mining has garnered increasing attention. Among various mining tasks, query processing stands out as the most fundamental and crucial. Current methods for query answering on UGs primarily rely on Monte-Carlo sampling and heuristic approaches. However, these techniques either struggle with a significant efficiency-accuracy trade-off or lack generalization over different graphs and queries. To circumvent these limitations, this work proposes a novel index-based method for query answering on UGs. We construct a labeling index framework, which can answer queries by pre-computed and stored operators. To the best of our knowledge, this is the first index frame-work that can deal with reliability, expected reliable distance and distance-constrained reliability queries, providing lower or upper bounded query answer results. By transferring the time consuming sampling process into the offline index operator computation, the query answering only needs to traverse a limited number of operators, which accelerates the response time of query answering with several orders of magnitude. We further utilize the vertex cover and its h-hop extension to prune the index structure, thereby reducing the space complexity. Experimental results on five real-world datasets demonstrate that the proposed index framework is both effective and efficient.

With the capacity to capture high-order collaborative signals, Graph Neural Networks (GNNs) have emerged as powerful methods in Recommender Systems (RS). However, their efficacy often hinges on the assumption that training and testing data share the same distribution (\aka IID assumption), and exhibits significant declines under distribution shifts. Distribution shifts commonly arises in RS, often attributed to the dynamic nature of user preferences or ubiquitous biases during data collection in RS. Despite its significance, researches on GNN-based recommendation against distribution shift are still sparse. To bridge this gap, we propose Distributionally Robust GNN (DR-GNN) that incorporates Distributional Robust Optimization (DRO) into the GNN-based recommendation. DR-GNN addresses two core challenges: 1) To enable DRO to cater to graph data intertwined with GNN, we reinterpret GNN as a graph smoothing regularizer, thereby facilitating the nuanced application of DRO; 2) Given the typically sparse nature of recommendation data, which might impede robust optimization, we introduce slight perturbations in the training distribution to expand its support. Notably, while DR-GNN involves complex optimization, it can be implemented easily and efficiently. Our extensive experiments validate the effectiveness of DR-GNN against three typical distribution shifts. The code is available at https://github.com/WANGBohaO-jpg/DR-GNN.

Implicit feedback (e.g., user clicks) is widely used in building recommender systems (RS). However, the inherent notorious exposure bias significantly affects recommendation performance. Exposure bias refers a phenomenon that implicit feedback is influenced by user exposure and does not precisely reflect user preference. Current methods for addressing exposure bias primarily reduce confidence in unclicked data, employ exposure models, or leverage propensity scores. Regrettably, these approaches often lead to biased estimations or elevated model variance, yielding sub-optimal results. To overcome these limitations, we propose a new method ReCRec that Reasons the C auses behind the implicit feedback for debiased R ec ommendation . ReCRec identifies three scenarios behind unclicked data—i.e., unexposed, dislike, or a combination of both. A reasoning module is employed to infer the category to which each instance pertains. Consequently, the model is capable of extracting reliable positive and negative signals from unclicked data, thereby facilitating more accurate learning of user preferences. We also conduct thorough theoretical analyses to demonstrate the debiased nature and low variance of ReCRec. Extensive experiments on both semi-synthetic and real-world datasets validate its superiority over state-of-the-art methods.

In recommendation systems (RS), user behavior data is observational rather than experimental, resulting in widespread bias in the data. Consequently, tackling bias has emerged as a major challenge in the field of recommendation systems. Recently, Doubly Robust Learning (DR) has gained significant attention due to its remarkable performance and robust properties. However, our experimental findings indicate that existing DR methods are severely impacted by the presence of so-called Poisonous Imputation, where the imputation significantly deviates from the truth and becomes counterproductive.

Recommendation fromimplicit feedbackis a highly challenging task due to the lack of reliable negative feedback data. Existing methods address this challenge by treating all the un-observed data as negative (dislike) but downweight the confidence of these data. However, this treatment causes two problems: (1) Confidence weights of the unobserved data are usually assigned manually, which lack flexibility and may create empirical bias on evaluating user's preference. (2) To handle massive volume of the unobserved feedback data, most of the existing methods rely on stochastic inference and data sampling strategies. However, since a user is only aware of a very small fraction of items in a large dataset, it is difficult for existing samplers to selectinformativetraining instances in which the user really dislikes the item rather than does not know it. To address the above two problems, we propose two novel recommendation methods SamWalker and SamWalker++ that support both adaptive confidence assignment and efficient model learning. SamWalker models data confidence with a social network-aware function, which can adaptively specify different weights to different data according to users’social contexts. However, the social network information may not be available in many recommender systems, which hinders application of SamWalker. Thus, we further propose SamWalker++, which does not require any side information and models data confidence with a constructed pseudo-social network. In the pseudo-social network, similar users are connected with specific item nodes or community nodes. This way, the inference of one's data confidence can benefit from the knowledge from other similar users. We also develop fast random-walk-based sampling strategies for our SamWalker and SamWalker++ to adaptively draw informative training instances, which can speed up gradient estimation and reduce sampling variance. Extensive experiments on five real-world datasets demonstrate the superiority of the proposed SamWalker and SamWalker++.

Spread of negative influence (N-Inf) in a networked system seems to be inevitable, e.g., epidemic spread in human networks, rumors in an online social network and computer virus plaguing the Internet etc. The widespread of N-Inf might cause severe damage and hence the Influence Blocking (IB) problem is attracting ample research interest. The IB problem aims at minimizing the N-Inf spread by immunization, i.e. selecting k (budget size) immunization nodes (Imm-nodes) to prevent the N-Inf from spreading. However, existing works for IB problem are all formulated as a one-shot task: selecting all the k Imm-nodes at the very beginning of N-Inf spread. In real world, unforeseen events might occur and one-shot policies will lack reserved measures to handle these situations. A more reasonable policy is to adaptively invest the budget based on the observation of N-Inf spread along as the time goes by. With the adaptive policy, we can both reserve resources for handling unforeseen events and save unnecessary costs if the spread of N-Inf dies out quickly. Motivated by the above considerations, we propose a novel Adaptive Influence Blocking (AIB) problem. Given the intermediate observations of N-Inf spread, the AIB problem aims at selecting Imm-nodes adaptively. We design a k-R (k-nodes-per-Round) policy which selects k Imm-nodes for each round until the budget is exhausted, and an α-T (α-Tolerance) policy which selects a new Imm-node if the expected N-Inf spread exceeds a threshold α. Scalable algorithms with provable approximation guarantees and error bounds are implemented for these policies and significant improvements on time complexity are achieved. Experimental results on real-world datasets demonstrate the effectiveness and scalability of the proposed methods.

Recommendation from implicit feedback is a highly challenging task due to the lack of reliable negative feedback data. Only positive feedback are observed and the unobserved feedback can be attributed to two reasons: unknow or dislike. Existing methods address this challenge by treating all the un-observed data as negative (dislike) but downweight the confidence of these data. However, this treatment causes two problems: (1) Confidence weights of the unobserved data are usually assigned manually, which lack flexible and may create empirical bias in evaluating user's preference. (2) To handle massive volume of the unobserved feedback data, most of the existing methods rely on stochastic inference and data sampling strategies. However, since users are only aware of a very small fraction of items in a large dataset, it is difficult for existing samplers to select informative training instances in which the user really dislikes the item rather than does not know it.

With the explosive growth of online social networks, many social recommendation methods have been proposed and demonstrated that social information has potential to improve the recommendation performance. However, existing social recommendation methods always assume that the data is missing at random (MAR) but this is rarely the case. In fact, by analysing two real-world social recommendation datasets, we observed the following interesting phenomena: (1) users tend to consume and rate the items that they like and the items that have been consumed by their friends. (2) When the items have been consumed by more friends, the average values of the observed ratings will become smaller, not larger as assumed by the existing models. To model these phenomena, we integrate the missing not at random (MNAR) assumption in social recommendation and propose a new social recommendation method SPMF-MNAR, which models the observation process of rating data based on user's preference and social influence. Extensive experiments conducted on large real-world datasets validate that SPMF-MNAR achieves better performance than existing social recommendation methods and the non-social methods based on MNAR assumption.