In contemporary e-commerce platforms, search result pages display two types of items: ad items and organic items. Ad items are determined through an advertising auction system, while organic items are selected by a recommendation system. These systems have distinct optimization objectives, creating the challenge of effectively merging these two components. Recent research has explored merging mechanisms for e-commerce platforms, but none have simultaneously achieved all desirable properties: incentive compatibility, individual rationality, adaptability to multiple slots, integration of inseparable candidates, and avoidance of repeated exposure for ads and organic items. This paper addresses the design of a merging mechanism that satisfies all these properties. We first provide the necessary conditions for the optimal merging mechanisms. Next, we introduce two simple and effective mechanisms, termed the generalized fix mechanism and the generalized change mechanism. Finally, we theoretically prove that both mechanisms offer guaranteed approximation ratios compared to the optimal mechanism in both simplest and general settings.
论文检索
输入标题、作者或关键词，从 11,272 篇学术成果中精准定位
We examine an approval-based model of Liquid Democracy with a budget constraint on voting and delegating costs, aiming to centrally select casting voters ensuring complete representation of the electorate. From a computational complexity perspective, we focus on minimizing overall costs, maintaining short delegation paths, and preventing excessive concentration of voting power. Furthermore, we explore computational aspects of strategic control, specifically, whether external agents can change election components to influence the voting power of certain voters.
We study the problem of computing fair divisions of a set of indivisible goods among agents with additive valuations. For the past many decades, the literature has explored various notions of fairness, that can be primarily seen as either having envy-based or share-based lens. For the discrete setting of resource-allocation problems, envy-free up to any good (EFX) and maximin share (MMS) are widely considered as the flag-bearers of fairness notions in the above two categories, thereby capturing different aspects of fairness herein. Due to lack of existence results of these notions and the fact that a good approximation of EFX or MMS does not imply particularly strong guarantees of the other, it becomes important to understand the compatibility of EFX and MMS allocations with one another. In this work, we identify a novel way to simultaneously achieve MMS guarantees with EFX/EF1 notions of fairness, while beating the best known approximation factors by Chaudhury et al. and Amanatidis et al. Our main contribution is to constructively prove the existence of (i) a partial allocation that is both 2/3-MMS and EFX, and (ii) a complete allocation that is both 2/3-MMS and EF1. Our algorithms run in pseudo-polynomial time if the approximation factor for MMS is relaxed to 2/3 - e for any constant e>0 and in polynomial time if, in addition, the EFX (or EF1) guarantee is relaxed to (1-d)-EFX (or (1-d)-EF1) for any constant d>0. In particular, we improve from the best approximation factor known prior to our work by Chaudhury et al., which computes partial allocations that are 1/2-MMS and EFX in pseudo-polynomial time.
We study the fundamental problem of fairly dividing a set of indivisible items among agents with (general) monotone valuations. The notion of envy-freeness up to any item (EFX) is considered to be one of the most fascinating fairness concepts in this line of work. Unfortunately, despite significant efforts, existence of EFX allocations is a major open problem in fair division, thereby making the study of approximations and relaxations of EFX a natural line of research. Recently, Caragiannis et al. [2023] introduced a promising relaxation of EFX, called epistemic EFX (EEFX). An allocation is EEFX, if for every agent, it is possible to shuffle the items in the remaining bundles so that she becomes ``EFX-satisfied''. Caragiannis et al. [2023] prove existence and polynomial-time computability of EEFX allocations for additive valuations. A natural question asks what happens when we consider valuations more general than additive? We address this important open question and answer it affirmatively by establishing the existence of EEFX allocations for an arbitrary number of agents with general monotone valuations. To the best of our knowledge, besides EF1, EEFX is the only known relaxation of EFX to have such strong existential guarantees. Furthermore, we complement our existential result by proving computational and information-theoretic lower bounds. We prove that even for an arbitrary number of (more than one) agents with identical submodular valuations, it is PLS-hard to compute EEFX allocations and it requires exponentially-many value queries to do so.
Present bias, the tendency to overvalue immediate rewards while undervaluing future ones, is a well-known barrier to achieving long-term goals. As artificial intelligence and behavioral economics increasingly focus on this phenomenon, the need for robust mathematical models to predict behavior and guide effective interventions has become crucial. However, existing models are constrained by their reliance on the discreteness of time and limited discount functions. This study introduces a novel continuous-time mathematical model for agents influenced by present bias. Using the variational principle, we model human behavior, where individuals repeatedly act according to a sequence of states that minimize their perceived cost. Our model not only retains analytical tractability but also accommodates various discount functions. Using this model, we consider intervention optimization problems under exponential and hyperbolic discounting and theoretically derive optimal intervention strategies, offering new insights into managing present-biased behavior.
While Nash equilibria are guaranteed to exist, they may exhibit dense support, making them difficult to understand and execute in some applications. In this paper, we study k-sparse commitments in games where one player is restricted to mixed strategies with support size at most k. Finding k-sparse commitments is known to be computationally hard. We start by showing several structural properties of k-sparse solutions, including that the optimal support may vary dramatically as k increases. These results suggest that naive greedy or double-oracle-based approaches are unlikely to yield practical algorithms. We then develop a simple approach based on mixed integer linear programs (MILPs) for zero-sum games, general-sum Stackelberg games, and various forms of structured sparsity. We also propose practical algorithms for cases where one or both players have large (i.e., practically innumerable) action sets, utilizing a combination of MILPs and incremental strategy generation. We evaluate our methods on synthetic and real-world scenarios based on security applications. In both settings, we observe that even for small support sizes, we can obtain more than 90% of the true Nash value while maintaining a reasonable runtime, demonstrating the significance of our formulation and algorithms.
Spectral Graph Neural Networks effectively handle graphs with different homophily levels, with low-pass filter mining feature smoothness and high-pass filter capturing differences. When these distinct filters could naturally form two opposite views for self-supervised learning, the commonalities between these counterparts for the same node remain unexplored, leading to suboptimal performance. In this paper, a simple yet effective self-supervised contrastive framework, LOHA, is proposed to address this gap. LOHA optimally leverages low-pass and high-pass views by embracing "harmony in diversity". Rather than solely maximizing the difference between these distinct views, which may lead to feature separation, LOHA harmonizes the diversity by treating the propagation of graph signals from both views as a composite feature. Specifically, a novel high-dimensional feature named spectral signal trend is proposed to serve as the basis for the composite feature, which remains relatively unaffected by changing filters and focuses solely on original feature differences. LOHA achieves an average performance improvement of 2.8% over runner-up models on 9 real-world datasets with varying homophily levels. Notably, LOHA even surpasses fully-supervised models on several datasets, which underscores the potential of LOHA in advancing the efficacy of spectral GNNs for diverse graph structures.
Out-of-distribution (OOD) detection aims to identify the test examples that do not belong to the distribution of training data. The distance-based methods, which identify OOD examples based on their distances from the centroids of in-distribution (ID) examples, have demonstrated promising OOD detection performance. However, the objectives utilized in prior approaches are typically designed for classification and thus might not yield sufficient discriminative power to distinguish between ID and OOD examples. Therefore, this paper proposes a prototype-based contrastive learning framework for OOD detection, which is termed provable Discriminative Hyperspherical Embedding (DHE). The proposed framework provides a theoretical analysis of inter-class dispersion, which is proved to be fundamental in reducing the false positive rate (FPR) on OOD examples. Based on this, we devise an angular spread loss to achieve the maximal dispersion of the prototypes of different classes prior to training. Subsequently, a prototype-enhanced contrastive loss is introduced to align embeddings of ID examples closely with their corresponding prototypes. In our proposed DHE, the maximal prototype dispersion is theoretically proved, thereby avoiding the pitfalls of local optima commonly encountered by most existing methods. Experimental results demonstrate the effectiveness of our proposed DHE, which showcases a remarkable reduction in FPR95 (i.e., 5.37% on CIFAR-100) and more than doubling the computational efficiency when compared with the state-of-the-art methods.
Refine then Classify: Robust Graph Neural Networks with Reliable Neighborhood Contrastive Refinement
PDF ↗Graph Neural Networks (GNNs) have exhibited remarkable capabilities for dealing with graph-structured data. However, recent studies have revealed their fragility to adversarial attacks, where imperceptible perturbations to the graph structure can easily mislead predictions. To enhance adversarial robustness, some methods attempt to learn robust representation through improving GNN architectures. Subsequently, another approach suggests that these GNNs might taint feature information and have poor classifier performance, leading to the introduction of Graph Contrastive Learning (GCL) methods to build a refining-classifying pipeline. However, existing methods focus on global-local contrastive strategies, which fails to address the robustness issues inherent in the contexts of adversarial robustness. To address these challenges, we propose a novel paradigm named GRANCE to enhance the robustness of learned representations by shifting the focus to local neighborhoods. Specifically, a dual neighborhood contrastive learning strategy is designed to extract local topological and semantic information. Paired with a neighbor estimator, the strategy can learn robust representations that are resilient to adversarial edges. Additionally, we also provide an improved GNN as classifier. Theoretical analyses provide a stricter lower bound of mutual information, ensuring the convergence of GRANCE. Extensive experiments validate the effectiveness of GRANCE compared to state-of-the-art baselines against various adversarial attacks.
Information diffusion prediction (IDP) is a pivotal task for understanding the dynamics of information propagation within social networks. Conventional models typically adhere to a fixed learning-based paradigm, where the trained prediction model remains static during the inference phase. This paradigm presupposes that the data is independent and identically distributed, an assumption that may not hold true due to the inherently open nature of social media and the uncertainty and variability in user behavior. In this paper, we address the novel problem of out-of-distribution (OOD) shifts within IDP tasks and propose a new test-time training-based model for multi-scale IDP tasks, named Ghidorah. Our approach focuses on adapting a subset of model parameters to accommodate the unique characteristics of test samples through self-supervised learning (SSL) tasks. Ghidorah comprises three components: the macroscopic prediction branch, the microscopic prediction branch, and the auxiliary SSL branch. The auxiliary SSL task employs a masked autoencoder-based loss to fine-tune the model for specific test samples prior to prediction. Furthermore, Ghidorah integrates invariant learning to capture robust representations while mitigating spurious correlations. To our knowledge, Ghidorah is the first work to introduce a test-time training framework specifically designed to address the critical yet often overlooked OOD challenges in IDP. Experimental results across several benchmark datasets validate the superiority of our approach.
Addressing Cold-Start Problem in Click-Through Rate Prediction via Supervised Diffusion Modeling
PDF ↗Predicting Click-Through Rates is a crucial function within recommendation and advertising platforms, as the output of CTR prediction determines the order of items shown to users. The Embedding and MLP paradigm has become a standard approach for industrial recommendation systems and has been widely deployed. However, this paradigm suffers from cold-start problems, where there is either no or only limited user action data available, leading to poorly learned ID embeddings. The cold-start problem hampers the performance of new items. To address this problem, we design a novel diffusion model to generate a warmed-up embedding for new items. Specifically, we define a novel diffusion process between the ID embedding space and the side information space. In addition, we can derive a sub-sequence from the diffusion steps to expedite training, given that our diffusion model is non-Markovian. Our diffusion model is supervised by both the variational inference and binary cross-entropy objectives, enabling it to generate warmed-up embeddings for items in both the cold-start and warm-up phases. Additionally, we have conducted extensive experiments on three recommendation datasets. The results confirmed the effectiveness of our approach.
The recognition of whether or not a predicate should be invented is an important problem in the domain of predicate invention. Despite its significance, existing research has yet to fully harness the rich data available in knowledge graphs. In this paper, we introduce a novel problem formulation, ReLPI (Representation Learning for Predicate Invention in Knowledge Graphs), marking a pioneering effort in this domain. To address the core issues of ReLPI, we devise a scoring function that informs the learning process. By optimizing embeddings towards this scoring function, we endow them with semantic meaning, crucial for capturing the nuances of predicate presence patterns. Furthermore, we present SEmPI (Semantic Embeddings for Predicate Invention), a framework that leverages predicate (relation) embeddings as a trainable medium. SEmPI uncovers latent patterns governing predicate occurrences in knowledge graphs, enabling the invention of novel predicates grounded in these discovered patterns. This approach represents a significant step forward in leveraging data-driven methods for predicate invention in knowledge graphs. We evaluate the proposed approach on FB15k and DRKG datasets, and the results demonstrate the effectiveness of SEmPI in discovering new predicates.
Reinforcement learning (RL) algorithms can improve recommendation performance by capturing long-term user-system interaction. However, current RL-based recommendation tasks seldom consider the dynamism of the environment, and standard RL algorithms are ineffective in recommending items dynamically. In addressing these issues, we design a novel task termed dynamic recommendation, which takes the emergence of real-world recommendable items into consideration. Meanwhile, we propose Adaptive Q-Network (AdaQN) to tackle the dynamic recommendation task. Firstly, AdaQN predicts the value of different action characteristics, particularly during the testing phase, which can capture emerging new action characteristics. The above procedure helps AdaQN in effectively adapting to the dynamic action space. Secondly, AdaQN establishes a stable mapping that projects the discrete action space onto a continuous characteristic space. Finally, AdaQN employs a lightweight Q-network design, which mitigates the complexity of the optimization process. Extensive experiments demonstrate that our approach has achieved state-of-the-art performance in the dynamic recommendation task.
Graph Neural Networks (GNNs) are widely used in graph data mining tasks. Traditional GNNs follow a message passing scheme that can effectively utilize local and structural information. However, the phenomena of over-smoothing and over-squashing limit the receptive field in message passing processes. Graph Transformers were introduced to address these issues, achieving a global receptive field but suffering from the noise of irrelevant nodes and loss of structural information. Therefore, drawing inspiration from fine-grained token-based representation learning in Natural Language Processing (NLP), we propose the Structure-aware Multi-token Graph Transformer (Tokenphormer), which generates multiple tokens to effectively capture local and structural information and explore global information at different levels of granularity. Specifically, we first introduce the walk-token generated by mixed walks consisting of four walk types to explore the graph and capture structure and contextual information flexibly. To ensure local and global information coverage, we also introduce the SGPM-token (obtained through the Self-supervised Graph Pre-train Model, SGPM) and the hop-token, extending the length and density limit of the walk-token, respectively. Finally, these expressive tokens are fed into the Transformer model to learn node representations collaboratively. Experimental results demonstrate that the capability of the proposed Tokenphormer can achieve state-of-the-art performance on node classification tasks.
Spatial-temporal forecasting is crucial and widely applicable in various domains such as traffic, energy, and climate. Benefiting from the abundance of unlabeled spatial-temporal data, self-supervised methods are increasingly adapted to learn spatial-temporal representations. However, it encounters three key challenges: 1) the difficulty in selecting reliable negative pairs due to the homogeneity of variables, hindering contrastive learning methods; 2) overlooking spatial correlations across variables over time; 3) limitations of efficiency and scalability in existing self-supervised learning methods. To tackle these, we propose a lightweight representation-learning model ST-ReP, integrating current value reconstruction and future value prediction into the pre-training framework for spatial-temporal forecasting. And we design a new spatial-temporal encoder to model fine-grained relationships. Moreover, multi-time scale analysis is incorporated into the self-supervised loss to enhance predictive capability. Experimental results across diverse domains demonstrate that the proposed model surpasses pre-training-based baselines, showcasing its ability to learn compact and semantically enriched representations while exhibiting superior scalability.
Graph anomaly detection is crucial for identifying anomalous nodes within graphs and addressing applications like financial fraud detection and social spam detection. Recent spectral graph neural network methods advance graph anomaly detection by focusing on anomalies that notably affect the distribution of graph spectral energy. Such spectrum-based methods rely on two steps: graph wavelet extraction and feature fusion. However, both steps are hand-designed, capturing incomprehensive anomaly information of wavelet-specific features and resulting in their inconsistent feature fusion. To address these problems, we propose a dynamic spectral graph anomaly detection framework DSGAD to adaptively capture comprehensive anomaly information and perform consistent feature fusion. DSGAD introduces dynamic wavelets, consisting of trainable wavelets to adaptively learn anomalous patterns and capture wavelet-specific features with comprehensive anomaly information. Furthermore, the consistent fusion of wavelet-specific features achieves dynamic fusion by combining wavelet-specific feature extraction with energy difference and channel convolution fusion using location correlation. Experimental results on four datasets substantiate the efficacy of our DSGAD method, surpassing state-of-the-art methods in both homogeneous and heterogeneous graphs.
Graph neural networks (GNNs) have gained superior performance in graph-based prediction tasks with a variety of applications such as social analysis and drug discovery. Despite the remarkable progress, their performance often degrades on test graphs with distribution shifts. Existing domain adaptation methods rely on unlabeled test graphs during optimization, limiting their applicability to graphs in the wild. Towards this end, this paper studies the problem of multi-domain generalization on graphs, which utilizes multiple source graphs to learn a GNN with high performance on unseen target graphs. We propose a new approach named Topological Adversarial Learning with Prototypical Mixup (TRACI) to solve the problem. The fundamental principle behind our TRACI is to produce virtual adversarial and mixed graph samples from a data-centric view. In particular, TRACI enhances GNN generalization by employing a gradient-ascent strategy that considers both label prediction entropy and graph topology to craft challenging adversarial samples. Additionally, it generates domain-agnostic node representations by characterizing class-graph pair prototypes through latent distributions and applying multi-sample prototypical Mixup for distribution alignment across graphs. We further provide theoretical analysis showing that TRACI reduces the model's excess risk. Extensive experiments on various benchmark datasets demonstrate that TRACI outperforms state-of-the-art baselines, validating its effectiveness.
From Pairwise to Ranking: Climbing the Ladder to Ideal Collaborative Filtering with Pseudo-Ranking
PDF ↗Intuitively, an ideal collaborative filtering (CF) model should learn from users' full rankings over all items to make optimal top-K recommendations. Due to the absence of such full rankings in practice, most CF models rely on pairwise loss functions to approximate full rankings, resulting in an immense performance gap. In this paper, we provide a novel analysis using the multiple ordinal classification concept to reveal the inevitable gap between a pairwise approximation and the ideal case. However, bridging the gap in practice encounters two formidable challenges: (1) none of the real-world datasets contains full ranking information; (2) there does not exist a loss function that is capable of consuming ranking information. To overcome these challenges, we propose a pseudo-ranking paradigm (PRP) that addresses the lack of ranking information by introducing pseudo-rankings supervised by an original noise injection mechanism. Additionally, we put forward a new ranking loss function designed to handle ranking information effectively. To ensure our method's robustness against potential inaccuracies in pseudo-rankings, we equip the ranking loss function with a gradient-based confidence mechanism to detect and mitigate abnormal gradients. Extensive experiments on four real-world datasets demonstrate that PRP significantly outperforms state-of-the-art methods.
GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs
PDF ↗Graph neural networks (GNNs) have shown significant success in learning graph representations. However, recent studies reveal that GNNs often fail to outperform simple MLPs on heterophilous graph tasks, where connected nodes may differ in features or labels, challenging the homophily assumption. Existing methods addressing this issue often overlook the importance of information granularity and rarely consider implicit relationships between distant nodes. To overcome these limitations, we propose the Granular and Implicit Graph Network (GRAIN), a novel GNN model specifically designed for heterophilous graphs. GRAIN enhances node embeddings by aggregating multi-view information at various granularity levels and incorporating implicit data from distant, non-neighboring nodes. This approach effectively integrates local and global information, resulting in smoother, more accurate node representations. We also introduce an adaptive graph information aggregator that efficiently combines multi-granularity and implicit data, significantly improving node representation quality, as shown by experiments on 13 datasets covering varying homophily and heterophily. GRAIN consistently outperforms 12 state-of-the-art models, excelling on both homophilous and heterophilous graphs.
Simple random negative sampling is a technique used to enhance decision-making in sequential models with numerous potential negative instances, like recommender systems. However, it ignores the patterns that can be discovered in complex sequences to select the most informative negative samples. In this paper, we address this challenge by introducing a Neighborhood-Aware Negative Sampling (NANS) technique in the context of student knowledge modeling (KM) and behavior modeling (BM). In the education domain, KM quantifies student knowledge based on past performance, while BM focuses on behaviors like student preferences of questions. With the vast number of problems to choose from and the intricate relationship between student knowledge and behavior, selecting the proper negative samples becomes a notable challenge in this problem. NANS, along with our proposed multi-objective, multi-task sequential model for KM and BM, NANS-KoBeM frames the simultaneous modeling of student knowledge and question selection as a multi-task learning problem with dual objectives: predicting students’ performance and their question selections.