The standard framework of online bidding algorithm design assumes that the seller commits himself to faithfully implementing the rules of the adopted auction. However, the seller may attempt to cheat in execution to increase his revenue if the auction belongs to the class of non-credible auctions. For example, in a second-price auction, the seller could create a fake bid between the highest bid and the second highest bid. This paper focuses on one such case of online bidding in repeated second-price auctions. At each time t, the winner with bid bt is charged not the highest competing bid dt but a manipulated price pt = α0 dt + (1-α0) bt, where the parameter α0 ∈ [0, 1] in essence measures the seller's credibility. Unlike classic repeated-auction settings where the bidder has access to samples (ds)s=1t-1, she can only receive mixed signals of (bs)s=1 t-1, (ds)s=1 t-1 and α0 in this problem. The task for the bidder is to learn not only the bid distributions of her competitors but also the seller's credibility. We establish regret lower bounds in various information models and provide corresponding online bidding algorithms that can achieve near-optimal performance. Specifically, we consider three cases of prior information based on whether the credibility α0 and the distribution of the highest competing bids are known. Our goal is to characterize the landscape of online bidding in non-credible second-price auctions and understand the impact of the seller's credibility on online bidding algorithm design under different information structures.
论文检索
输入标题、作者或关键词，从 447 篇学术成果中精准定位
Conspicuous consumption occurs when a consumer derives value from a good based on its social meaning as a signal of wealth, taste, and/or community affiliation. Common conspicuous goods include designer footwear, country club memberships, and artwork; conspicuous goods also exist in the digital sphere, with non-fungible tokens (NFTs) as a prominent example. The NFT market merits deeper study for two key reasons: first, it is poorly understood relative to its economic scale; and second, it is unusually amenable to analysis because NFT transactions are publicly available on the blockchain, making them useful as a test bed for conspicuous consumption dynamics. This paper introduces a model that incorporates two previously identified elements of conspicuous consumption: the bandwagon effect (goods increase in value as they become more popular) and the snob effect (goods increase in value as they become rarer). Our model resolves the apparent tension between these two effects, exhibiting net complementarity between others' and one's own conspicuous consumption. We also introduce a novel dataset combining NFT transactions with embeddings of the corresponding NFT images computed using an off-the-shelf vision transformer architecture. We use our dataset to validate the model, showing that the bandwagon effect raises an NFT collection's value as more consumers join, while the snob effect drives consumers to seek rarer NFTs within a given collection.
Recently, multilingual Vision-Language Pre-training (mVLP) has shown remarkable progress in learning joint representations across different modalities and languages. However, most existing methods learn semantic alignment at a coarse-grained level and fail to capture fine-grained correlations between different languages and modalities. To address this, we propose a Multi-grained Multilingual Vision-Language Pre-training (M2-VLP) model, which aims to learn cross-lingual cross-modal alignment at different semantic granular levels. In cross-lingual interaction, the model learns the global alignment of parallel sentence pairs and the word-level correlations. In cross-modal interaction, the model aligns images with captions and image regions with corresponding words. To integrate the cross-lingual and cross-modal alignment above, we propose a unified multi-grained contrastive learning paradigm. Under zero-shot cross-lingual and fine-tuned multilingual settings, extensive experiments on vision-language downstream tasks across twenty languages demonstrate the effectiveness of M2-VLP over competitive contrastive models. Code and models are available at https://github.com/ahtamjan/M2-VLP.
Trajectory Similarity Join (TS-Join), as a fundamental operation in trajectory data analytics, has been extensively investigated by existing studies in data science. However, existing solutions are almost designed for offline static trajectories, which cannot ensure real-time feedback. In addition, the join results retrieved from existing solutions generally contain a large proportion of outdated similar pairs, making them inapplicable to evolving trajectories. In this light, we study a novel problem of online time-aware trajectory similarity join: Given a stream of evolving trajectories, we aim to dynamically discover trajectory pairs whose spatio-temporal similarity is no less than a specified threshold in a real-time manner. We innovatively introduce a time-aware exponential-decaying similarity function to eliminate outdated results. To support real-time querying over large populations of trajectories, we develop a Parallel Online Trajectory Similarity Join (POTSJ) framework with workload balancing techniques. We further enhance join efficiency through pruning strategies and tailored approximation techniques. The POTSJ framework we propose, which incorporates these elements, is capable of processing online TS-Join while simultaneously satisfying three key objectives: real-time result updates, comprehensive trajectory evaluation, and scalability. Extensive experiments on real-world datasets validate the efficiency and scalability of our POTSJ framework in processing online TS-Join.
With the explosive growth of online service platforms, an increasing number of people and enterprises are undertaking personal and professional tasks online. In real applications such as trip planning and online marketing, planning sessions for a sequence of activities or services will enable social users to receive the optimal services, improving their experience and reducing the cost of their activities. These online platforms are heterogeneous, including different types of services with different attributes. However, the problem of session planning over heterogeneous platforms has not been studied so far. In this paper, we propose a Motivation-Aware Session Planning (MASP) framework for session planning over heterogeneous social platforms. Specifically, we first propose a novel HeterBERT model to handle the heterogeneity of items at both type and attribute levels. Then, we propose to predict user preference using the motivations behind user activities. Finally, we propose an algorithm together with its optimisations for efficient session generation. The extensive tests prove the high effectiveness and efficiency of MASP.
TensorJSFuzz: Effective Testing of Web-Based Deep Learning Frameworks via Input-Constraint Extraction
PDF ↗As web applications grow in popularity, developers are increasingly integrating deep learning (DL) models into these environments. Web-based DL frameworks (e.g., TensorFlow.js) are essential for building and deploying such applications. Therefore, ensuring the quality of these frameworks is critical. While extensive testing efforts have been made for native DL frameworks such as TensorFlow and PyTorch, web-based DL frameworks have not yet undergone systematic testing. A key challenge is generating syntactically and semantically valid inputs while designing effective test oracles for web environments. To address this, we introduce TensorJSFuzz, a novel method for testing web-based DL frameworks. To ensure input quality, TensorJSFuzz extracts constraints directly from the source code of DL operators. By leveraging Large Language Models (e.g., ChatGPT) to understand the code and extract input constraints, TensorJSFuzz performs type-aware random generation coupled with dependency-aware refinement to create high-quality test inputs. These inputs are then subjected to differential testing across various backends, including CPU, TensorFlow, Wasm, and WebGL. Our experimental results show that TensorJSFuzz outperforms all baselines in generating valid inputs and identifying bugs. In particular, TensorJSFuzz successfully detected 92 bugs, with 30 already confirmed or fixed by developers, demonstrating its effectiveness in improving the robustness of web-based DL frameworks.
In this study, we reveal, for the first time, popular online social networks (especially Twitter) are being extensively abused by miscreants to promote illicit goods and services of diverse categories. This study is made possible by multiple machine learning tools that are designed to detect and analyze Posts of Illicit Promotion (PIPs) as well as revealing their underlying promotion campaigns. Particularly, we observe that PIPs are prevalent on Twitter, along with extensive visibility on other three popular OSNs including YouTube, Facebook, and TikTok. For instance, applying our PIP hunter to the Twitter platform for 6 months has led to the discovery of 12 million distinct PIPs which are widely distributed in 5 major natural languages and 10 illicit categories, e.g., drugs, data leakage, gambling, and weapon sales. Along the discovery of PIPs are 580K Twitter accounts publishing PIPs as well as 37K distinct instant messaging accounts that are embedded in PIPs and serve as next hops of communication with prospective customers. Also, an arms race between Twitter and illicit promotion operators is also observed. Especially, 90% PIPs can survice the first two months since getting published on Twitter, which is likely due to the diverse evasion tactics adopted by miscreants to masquerade PIPs.
Urban fine-grained data map inference, leveraging information from coarse-grained maps, has emerged as a significant area of research due to the growing complexity and data heterogeneity in urban environments. Existing methods have a priori assumption that a coarse-grained data map, one fixed-size granularity, transforms into a fine-grained data map, also one fixed-size granularity. However, in actual scenarios, the collected coarse-grained data maps are often incomplete and have significantly distinct granularities in various urban areas, which results in incomplete heterogeneous data, i.e., multi-granularity data maps in terms of spatial information. Meanwhile, different granularity data maps are needed for various urban downstream tasks, which is a multi-task problem. To that end, this paper proposes a novel framework, a multi-granularity super-resolution data map inference framework (MGSR), designed to harness spatio-temporal information to transform incomplete coarse-grained multi-granularity data maps into fine-grained multi-granularity data maps. Specifically, we design a granularity alignment network to align multi-granularity information and address missing data on each granularity data map by leveraging the other granularity data maps with a well-designed self-supervised task. Then, we introduce a feature extraction network to capture spatio-temporal dependencies and extract features. Finally, we devise a recurrent super-resolution network with shared parameters to infer multi-granularity data maps. We conduct extensive experiments on three real-world benchmark datasets and demonstrate that MGSR significantly outperforms the state-of-the-art methods for multi-granularity urban data map inference and reduces RMSE and MAE by up to 40.1% and 50.3%, respectively. The source code has been released at https://github.com/wn13/MGSR\_code.
Machine unlearning is an emerging field that selectively removes specific data samples from a trained model. This capability is crucial for addressing privacy concerns, complying with data protection regulations, and correcting errors or biases introduced by certain data. Unlike traditional machine learning, where models are typically static once trained, machine unlearning facilitates dynamic updates that enable the model to ''forget'' information without requiring complete retraining from scratch. There are various machine unlearning methods, some of which are more time-efficient when data removal requests are fewer. To decrease the execution time of such machine unlearning methods, we aim to reduce the size of data removal requests based on the fundamental assumption that the removal of certain data would not result in a distinguishable retrained model. We first propose the concept of unnecessary unlearning, which indicates that the model would not alter noticeably after removing some data points. Subsequently, we review existing solutions that can be used to solve our problem. We highlight their limitations in adaptability to different unlearning scenarios and their reliance on manually selected parameters. We consequently put forward FUNU, a method to identify data points that lead to unnecessary unlearning. FUNU circumvents the limitations of existing solutions. The idea is to discover data points within the removal requests that have similar neighbors in the remaining dataset. We utilize a reference model to set parameters for finding neighbors, inspired from the area of model memorization. We provide a theoretical analysis of the privacy guarantee offered by FUNU and conduct extensive experiments to validate its efficacy.
Online hatred has become an increasingly pervasive issue, affecting individuals and communities across various digital platforms. To combat hate speech in such platforms, counter narratives (CNs) are regarded as an effective method. In recent years, there has been growing interest in using generative AI tools to construct CNs. However, most of the generative models produce generic responses to hate speech and can hallucinate, reducing their effectiveness. To address the above limitations, we propose a counter narrative generation method that enhances CNs by providing non-aggressive, fact-based narratives with relevant background knowledge from two distinct sources, including a web search module. Furthermore, we conduct a comprehensive evaluation using multiple metrics, including LLM-based measures for persuasion, factuality, and informativeness, along with human and traditional NLP evaluations. Our method significantly outperforms baselines, achieving an average factuality score of 0.915, compared to 0.741, 0.701, and 0.69 for competitive baselines, and performs well in human evaluations.
Entity Matching (EM) automates the discovery of identity links between entities within different Knowledge Graphs (KGs). Link keys are crucial for EM, serving as rules allowing to identify identity links across different KGs, possibly described using different ontologies. However, the approach for extracting link keys struggles to scale on large KGs. While embedding-based EM methods efficiently handle large KGs they lack explainability. This paper proposes a novel hybrid EM approach to guarantee the scalability link key extraction approach and improve the explainability of embedding-based EM methods. First, embedding-based EM approaches are used to sample the KGs based on the identity links they generate, thereby reducing the search space to relevant sub-graphs for link key extraction. Second, rules (in the form of link keys) are extracted to explain the generation of identity links by the embedding-based methods. Experimental results demonstrate that the proposed approach allows link key extraction to scale on large KGs, preserving the quality of the extracted link keys. Additionally, it shows that link keys can improve the explainability of the identity links generated by embedding-methods, allowing for the regeneration of 77% of the identity links produced for a specific EM task, thereby providing an approximation of the reasons behind their generation.
We study sequential procurement auctions where the sellers are provided with a ''best and final offer'' (BAFO) strategy. This strategy allows each seller i to effectively ''freeze'' their price while remaining active in the auction, and it signals to the buyer, as well as all other sellers, that seller i would reject any price lower than that. This is in contrast to prior work, e.g., on descending auctions, where the options provided to each seller are to either accept a price reduction or reject it and drop out. As a result, the auctions that we consider induce different extensive form games and our goal is to study the subgame perfect equilibria of these games. We focus on settings involving multiple sellers who have full information regarding each other's cost (i.e., the minimum price that they can accept) and a single buyer (the auctioneer) who has no information regarding these costs. Our main result shows that the auctions enhanced with the BAFO strategy can guarantee efficiency in every subgame perfect equilibrium, even if the buyer's valuation function is an arbitrary monotone function. This is in contrast to prior work which required that the buyer's valuation satisfies restrictive properties, like gross substitutes, to achieve efficiency. We then also briefly analyze the seller's cost in the subgame perfect equilibria of these auctions and we show that even if the auctions all return the same outcome, the cost that they induce for the buyer can vary significantly.
Conversational recommender systems (CRS) aim to provide personalized recommendations via interactive dialogues with users. While large language models (LLMs) enhance CRS with their superior understanding of context-aware user preferences, they typically struggle to leverage behavioral data, which have proven to be important for classical collaborative filtering (CF)-based approaches. For this reason, we propose CRAG-Collaborative Retrieval Augmented Generation for LLM-based CRS. To the best of our knowledge, CRAG is the first approach that combines state-of-the-art LLMs with CF for conversational recommendations. Our experiments on two publicly available movie conversational recommendation datasets, i.e., a refined Reddit dataset (which we name Reddit-v2) as well as the Redial dataset, demonstrate the superior item coverage and recommendation performance of CRAG, compared to several CRS baselines. Moreover, we observe that the improvements are mainly due to better recommendation accuracy on recently released movies. The code and data are available at https://github.com/yaochenzhu/CRAG.
With the advancement of WebAssembly, abbreviated as Wasm, various memory bugs and undefined behaviors have emerged, leading to security issues that affect usability and portability. Existing methods struggle to detect these problems in Wasm binaries due to challenges associated with binary instrumentation and the difficulty of defining legal memory bounds.While sanitizers combined with fuzzing are recognized as effective means for identifying bugs, current Wasm sanitizers necessitate compile-time instrumentation, rendering them unsuitable for practical scenarios where only binaries are accessible. In this paper, we propose WBSan, the first Wasm binary sanitizer employing static analysis and Wasm binary instrumentation to detect memory bugs and undefined behaviors. We develop distinct instrumentation patterns tailored for each type of bug and introduce Wasm shadow memory to address complex memory bugs. Our results reveal that WBSan achieves a 16.8% false detection rate, outperforming current Wasm binary checkers and native sanitizers in detecting memory bugs and undefined behaviors. Furthermore, when compared with the binary-only fuzzer, WBSan uncovers more crashes and achieves greater code coverage.
Preserving Label Correlation for Multi-label Text Classification by Prototypical Regularizations
PDF ↗Multi-label text classification (MLTC) assigns multiple labels to a sentence, with the key challenge being capturing label correlations. Existing models prioritize leveraging correlations but often overlook overfitting, while plug-and-play regularization methods fail to preserve correlations effectively. In this paper, we distinguish two types of label correlations: explicit co-occurring correlations and implicit semantic correlations, and propose regularizations on prototypical label embeddings for correlation preservation. Specifically, we first generate the prototypical embedding of multiple co-occurred labels as an intermediate. We then apply a prototypical regularization on the distance between the sentence embedding and corresponding prototypical embedding to alleviate the over-alignment issue caused by binary cross entropy loss and facilitate explicit correlation preservation. We finally extend the vanilla Mixup, which solely mixes multi-hot labels, on prototypical embedding mixing to promote implicit correlation preservation. Empirical studies show the effectiveness of our regularization methods.
Hyper-relational knowledge graphs (HKGs) extend the traditional triplet-based knowledge graph by adding qualifiers to the relationships, making HKGs particularly useful for tasks that require more profound understanding and inference from relationships between entities. However, existing hyper-relational knowledge representation learning methods (HKRL) focus on direct neighbourhood information of entities only by neglecting the relational similarity of the main triple in hyper-relational facts and the attribute details in the qualifiers. In addition, few works extract common and private information across multiple views to minimize noise and interference. This paper proposes a multi-hypergraph disentanglement method for HKRL to address the above issues. Specifically, we first construct four hypergraphs to mine and utilise the inherent structure information of HKGs, and then propose to extract common representations among hypergraphs and private representations within individual hypergraphs to mine the semantic information and the task-relevant information, respectively. Experiment results on four real datasets demonstrate the effectiveness of the proposed method compared to SOTA methods in link prediction tasks on HKGs.
Polynomial Selection in Spectral Graph Neural Networks: An Error-Sum of Function Slices Approach
PDF ↗Spectral graph neural networks are proposed to harness spectral information inherent in graph-structured data through the application of polynomial-defined graph filters, recently achieving notable success in graph-based web applications. Existing studies reveal that various polynomial choices greatly impact spectral GNN performance, underscoring the importance of polynomial selection. However, this selection process remains a critical and unresolved challenge. Although prior work suggests a connection between the approximation capabilities of polynomials and the efficacy of spectral GNNs, there is a lack of theoretical insights into this relationship, rendering polynomial selection a largely heuristic process. To address the issue, this paper examines polynomial selection from an error-sum of function slices perspective. Inspired by the conventional signal decomposition, we represent graph filters as a sum of disjoint function slices. Building on this, we then bridge the polynomial capability and spectral GNN efficacy by proving that the construction error of graph convolution layer is bounded by the sum of polynomial approximation errors on function slices. This result leads us to develop an advanced filter based on trigonometric polynomials, a widely adopted option for approximating narrow signal slices. The proposed filter remains provable parameter efficiency, with a novel Taylor-based parameter decomposition that achieves streamlined, effective implementation. With this foundation, we propose TFGNN, a scalable spectral GNN operating in a decoupled paradigm. We validate the efficacy of TFGNN via benchmark node classification tasks, along with an example graph anomaly detection application to show its practical utility.
Next Point-of-Interest (POI) recommendation has become a crucial task in Location-Based Social Networks (LBSNs), which provide personalized recommendations by predicting the user's next check-in locations. Commonly used models including Recurrent Neural Networks (RNNs) and Graph Convolutional Networks (GCNs) have been widely explored. However, these models face significant challenges, including the difficulty of capturing the hierarchical and tree-like structure of POIs in Euclidean space and the sparsity problem inherent in POI recommendations. To address these challenges, we propose a Hyperbolic Variational Graph Auto-Encoder (HVGAE) for next POI recommendation. Specifically, we utilize a Hyperbolic Graph Convolutional Network (Hyperbolic GCN) to model hierarchical structures and tree-like relationships by converting node embeddings from euclidean space to hyperbolic space. Then we use Variational Graph Auto-Encoder (VGAE) to convert node embeddings to probabilistic distributions, enhancing the capture of deeper latent features and providing a more robust model structure. Furthermore, we combine the Mamba4Rec recommender and Rotary Position Embedding (RoPE) and propose Rotary Position Mamba (RPMamba) to effectively utilize POI embeddings rich in sequential information, which improves the accuracy of the next POI recommendation. Extensive experiments on three public datasets demonstrate the superior performance of the HVGAE model.
Multi-modal time series data is common in web technologies like the Internet of Things (IoT). Existing methods for multi-modal time series representation learning aim to disentangle the modality-shared and modality-specific latent variables. Although achieving notable performances on downstream tasks, they usually assume an orthogonal latent space. However, the modality-specific and modality-shared latent variables might be dependent on real-world scenarios. Therefore, we propose a general generation process, where the modality-shared and modality-specific latent variables are dependent, and further develop a Multi-modAl TEmporal Disentanglement (MATE) model. Specifically, our MATE model is built on a temporally variational inference architecture with the modality-shared and modality-specific prior networks for the disentanglement of latent variables. Furthermore, we establish identifiability results to show that the extracted representation is disentangled. More specifically, we first achieve the subspace identifiability for modality-shared and modality-specific latent variables by leveraging the pairing of multi-modal data. Then we establish the component-wise identifiability of modality-specific latent variables by employing sufficient changes of historical latent variables. Extensive experimental studies on 12 datasets show a general improvement in different downstream tasks, highlighting the effectiveness of our method in real-world scenarios.
The diffusion of culture online is theorized to be influenced by many interacting social factors (e.g., network and identity). However, most existing computational cascade models consider just a single factor (e.g., network or identity). This work offers a new framework for teasing apart the mechanisms underlying hashtag cascades. We curate a new dataset of 1,337 hashtags representing cultural innovation online, develop a 10-factor evaluation framework for comparing empirical and simulated cascades, and show that a combined network+identity model better simulates hashtag cascades than network- or identity-only counterfactuals. We also explore heterogeneity in performance: While a combined network+identity model best predicts the popularity of cascades, a network-only model best predicts cascade growth and an identity-only model best predicts adopter composition. The network+identity model has the highest comparative advantage among hashtags used for expressing racial or regional identity and talking about sports or news. In fact, we are able to predict what combination of network and/or identity best models each hashtag and use this to further improve performance. Our results show the utility of models incorporating the interactions of network, identity, and other social factors in the diffusion of hashtags in social media.