WWW 2025 Papers

We study the problem of finding the optimal bidding strategy for an advertiser in a multi-platform auction setting. The competition on a platform is captured by a value and a cost function, mapping bidding strategies to value and cost respectively. We assume a diminishing returns property, whereby the marginal cost is increasing in value. The advertiser uses an autobidder that selects a bidding strategy for each platform, aiming to maximize total value subject to budget and return-on-spend constraint. The advertiser has no prior information and learns about the value and cost functions by querying a platform with a specific bidding strategy. Our goal is to design an algorithm that finds the optimal bidding strategy with a small number of queries. We first present an algorithm that requires \(O(m \log (mn) \log n)\) queries, where $m$ is the number of platforms and $n$ is the number of possible bidding strategies in each platform. Moreover, we adopt the learning-augmented framework and propose an algorithm that utilizes a (possibly erroneous) prediction of the optimal bidding strategy. We provide a $O(m \log (m\eta) \log \eta)$ query-complexity bound on our algorithm as a function of the prediction error $\eta$. This guarantee gracefully degrades to \(O(m \log (mn) \log n)\). This achieves a ``best-of-both-worlds'' scenario: \(O(m)\) queries when given a correct prediction, and \(O(m \log (mn) \log n)\) even for an arbitrary incorrect prediction.

Retrieval-Augmented Generation (RAG) has been an effective approach to mitigate hallucinations in large language models (LLMs) by incorporating up-to-date and domain-specific knowledge. Recently, there has been a trend of storing up-to-date or copyrighted data in RAG knowledge databases instead of using it for LLM training. This practice has raised concerns about Membership Inference Attacks (MIAs), which aim to detect if a specific target document is stored in the RAG system's knowledge database so as to protect the rights of data producers. While research has focused on enhancing the trustworthiness of RAG systems, existing MIAs for RAG systems remain largely insufficient. Previous work either relies solely on the RAG system's judgment or is easily influenced by other documents or the LLM's internal knowledge, which is unreliable and lacks explainability. To address these limitations, we propose a **M**ask-**B**ased Membership Inference **A**ttacks (MBA) framework. Our framework first employs a masking algorithm that effectively masks a certain number of words in the target document. The masked text is then used to prompt the RAG system, and the RAG system is required to predict the mask values. If the target document appears in the knowledge database, the masked text will retrieve the complete target document as context, allowing for accurate mask prediction. Finally, we adopt a simple yet effective threshold-based method to infer the membership of target document by analyzing the accuracy of mask prediction. Our mask-based approach is more document-specific, making the RAG system's generation less susceptible to distractions from other documents or the LLM's internal knowledge. Extensive experiments demonstrate the effectiveness of our approach compared to existing baseline models.

In recent years, graph neural networks (GNNs) have been commonly utilized for social recommendation systems. However, real-world scenarios often present challenges related to user privacy and business constraints, inhibiting direct access to valuable social information from other platforms. While many existing methods have tackled matrix factorization-based social recommendations without direct social data access, developing GNN-based federated social recommendation models under similar conditions remains largely unexplored. To address this issue, we propose a novel vertical federated social recommendation method leveraging privacy-preserving two-party graph convolution networks (P4GCN) to enhance recommendation accuracy without requiring direct access to sensitive social information. First, we introduce a Sandwich-Encryption module to ensure comprehensive data privacy during the collaborative computing process. Second, we provide a thorough theoretical analysis of the privacy guarantees, considering the participation of both curious and honest parties. Extensive experiments on four real-world datasets demonstrate that P4GCN outperforms state-of-the-art methods in terms of recommendation accuracy.

Cross-site scripting (XSS) constantly remains one of the most prevalent attacks on the Web. In this work, we question its current taxonomy, i.e., the client- or server-side reflected (non-persistent) or stored (persistent) matrix. The Web has extensively changed. Consequently, considering XSS with the lenses of this famous matrix has become at least imprecise, at most impossible for many code injection scenarios where (i) a service worker or an edge worker generates HTTP responses and can reflect or persist XSS payloads infecting not only JavaScript in web pages but also Web assembly, web workers and affecting one or many users automatically; (ii) an attacker sends a web push message directly to a browser push service to trigger code execution in a dormant service worker; or (iii) a cross-origin adversary tampers with code stored by a vulnerable website on the user’s physical/permanent file system, etc. Our proposal –to get out of the matrix and not enter another rigid one– expresses the essence of XSS as code infection and affection attack, and allows for clearly specifying the different actors and components involved, their environments, contexts and storages, as well as their recurrence and persistence seen as a continuum rather than a binary marker. From a defensive perspective, we showcase the challenges and limitations of current mechanisms at mitigating XSS targetting the entire attack surface of modern websites. Finally, we demonstrate an abuse of the Service-Worker-Allowed header (SWA) to control entire domains with malicious service workers.

As online cloud services expand rapidly, layer-7 load balancing has become indispensable for maintaining service availability and performance. The emergence of programmable switches with both high performance and a certain degree of flexibility has made it possible to apply programmable switches to load balancing. Nevertheless, the meager memory capacity and the relatively sluggish speed of table entry insertion and deletion of programmable switches have severely constrained their performance. To this end, we introduce Miresga, a hybrid and high-performance layer-7 load balancing system by co-designing hardware and software. The core idea of Miresga is to maximize the utilization of hardware and software resources by rationally partitioning the layer-7 load balancing task, thereby improving performance. To achieve this, Miresga offloads the elephant flows, which account for the majority of traffic, to programmable switches that excel at packet processing, and Miresga utilizes general-purpose servers with stronger computational capabilities to parse application layer protocols and apply load balancing rules. To alleviate memory pressure on the programmable switch, Miresga employs a back-end agent to handle memory-intensive tasks, working in conjunction with the programmable switch to complete the offloaded tasks. This design leverages the performance advantages of the programmable switch while avoiding bottlenecks caused by its limited memory and table insertion speed. We implement the Miresga prototype with a 3.2 Tbps Intel Tofino switch and general-purpose servers. The evaluation results show that Miresga achieves $3.9\times$ throughput and $0.4\times$ latency compared to software load balancing solutions. Compared to state-of-the-art design employing programmable switches, Miresga achieves almost the same throughput and latency for delivering large objects and $5.0\times$ throughput and $0.2\times$ latency when transmitting small objects.

Information feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in feed, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user's interests or information search, the goal is to design an algorithm that maximizes the reward (e.g., clicks) by placing advertisements interleaved with the organic content under two considerations: (1) an advertisement can only be inserted after a relevant content item; (2) the users' attention decays after consuming content or advertisements. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, in contrast to the best-known practical algorithm that only achieves an approximation factor of 4. Our algorithms exploit a counter-intuitive structure about the problem, that is, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the studied problem, showing the strong empirical performance of our algorithms.

Graph node importance estimation, a classical problem in network analysis, underpins various web applications. To improve estimation accuracy, previous methods either exploit intrinsic topological characteristics, e.g., graph centrality, or leverage additional information, e.g., data heterogeneity, for node feature enhancement. However, these methods follow the supervised learning setting, overlooking the fact that ground-truth node-importance data are usually partially labeled in practice. In this work, we propose the first semi-supervised node importance estimation framework, i.e., EASING, to improve learning quality for unlabeled data in heterogeneous graphs. Different from previous approaches, EASING explicitly captures uncertainty to reflect the confidence of model predictions. To jointly estimate the importance values and uncertainties, EASING incorporates DJE, a deep encoder-decoder neural architecture. DJE introduces distribution modeling for graph nodes, where the distribution representations are decoded to derive both importance and uncertainty estimates, after encoding the rich heterogeneous graph information. Additionally, DJE facilitates effective pseudo-label generation for the unlabeled data to enrich the training samples. Then based on both labeled and pseudo-labeled data, EASING develops effective semi-supervised heteroscedastic learning with the varying node uncertainty regularization. Extensive experiments on three real-world datasets highlight the superior performance of EASING compared to competing methods and demonstrate the effectiveness of each individual module. Codes are available via https://anonymous.4open.science/r/EASING-2F70/.

Large Language Models (LLMs) possess remarkable capabilities in storing and retrieving vast factual knowledge but often retain outdated or incorrect information from web corpora. While full retraining is costly, locate-and-edit model editing methods offer an feasible alternative. Current methods typically follow a two-stage paradigm: (1) identifying critical layers for knowledge storage and (2) updating their parameters to store new knowledge. However, both of these two phases have their inherent limitations. In stage 1, layers identification is independent of the to-be-updated knowledge, ignoring the varying storage patterns of different knowledge types. Meanwhile, Stage 2 suffers from high computational overhead due to independent gradient descent for each piece of knowledge. To solve these, we propose an Explainable and effiCient model Editing method, termed ECE. Specifically, in Stage 1, ECE integrates the concept of LLMs explainability into the editing process, enabling the adaptive identification of the crucial neurons based on the input knowledge. In Stage 2, ECE clusters similar knowledge based on the explanation results, allowing batch optimization in a single gradient step, significantly reducing time consumption without sacrificing effectiveness. Extensive experiments demonstrate that ECE can achieve superior performance while delivering a 3.27× speedup in editing efficiency, showcasing the potential of explainability-driven editing methods for LLMs.

Network traffic anomaly detection is pivotal in cybersecurity, especially as data volume grows and security requirement intensifies. This study addresses critical limitations in existing reconstruction-based methods, which quantify anomalies relying on intra-sample differences and struggle to detect drifted anomalies. In response, we propose a novel approach, the Uncertainty-Inspired Inter-Sample Differences method (UnDiff), which leverages model uncertainty to enhance anomaly detection capabilities, particularly in scenarios involving anomaly drift. By employing evidential learning, the UnDiff model gathers evidence to minimize uncertainty in normal network traffic, enhancing its ability to differentiate between normal and anomalous traffic. To overcome the limitations of intra-sample difference quantification in reconstruction-based methods, we propose a novel anomaly score based on inter-sample uncertainty deviation that directly quantifies the anomaly degree. Benefiting from a concise model design and parameterized uncertainty quantification, UnDiff achieves high efficiency. Extensive experiments on three benchmarks demonstrate UnDiff's superior performance in detecting both undrifted and drifted anomalies with minimal computational overhead. This research contributes to the field of network security by introducing a new uncertainty-based modeling paradigm and a novel uncertainty-inspired anomaly score.

Multimodal knowledge graphs inevitably contain numerous errors due to the absence of human supervision in their automated construction and updating processes. These errors can significantly degrade the performance of downstream applications that rely on them. Existing researches on knowledge graph error detection primarily focus on leveraging graph structural and textual information to identify triplet errors in unimodal knowledge graphs. However, unlike unimodal knowledge graphs, multimodal knowledge graphs also suffer from mismatches between images and their corresponding entities, referred to as modality errors. These modality errors not only hinder the performance of downstream applications but also impede our effective utilization of the abundant complementary information provided by the visual modality for detecting triplet errors. To this end, we introduce a novel task of multimodal knowledge graph error detection (MKGED) in this paper, aiming at simultaneously identifying both modality errors and triplet errors. Given the lack of datasets for evaluating this task, we first establish two comprehensive MKGED datasets. Furthermore, we propose a novel framework, KGDMC, to address the MKGED task. Within KGDMC, we devise a disentanglement modality reconstruction (DMR) module for modality error detection. This module disentangles each original modality representation into two disjoint components: modality-specific representations and modality-invariant representations, leveraging the cross-modality reconstruction process to detect mismatched visual modalities. Additionally, for the triplet error detection, we propose a multi-grained triplet confidence (MTC) module, incorporating local triplet confidence, global structure confidence, and global path confidence, to collaboratively detect mismatched triplets. Extensive experiments on our constructed two datasets demonstrate the superiority of our proposed framework.

Graph neural networks (GNNs) with differential privacy (DP) offer a reliable solution for safeguarding sensitive information within graph data. Nonetheless, existing DP-based privacy-preserving GNN learning frameworks generally overlook the local topological heterogeneity of graph nodes and tailor the same privacy budget for all nodes, which may lead to either overprotection or underprotection of some nodes, potentially diminishing model utility or posing privacy leakage risks. To address this issue, we propose a Topology-aware Differential Privacy Graph Neural Network learning framework (TDP-GNN), which can achieve personalized privacy protection for each node with improved privacy-utility guarantees. Specifically, TDP-GNN first identifies the topological importance of each node via an adjacency information entropy method. Then, the personalized topology-aware privacy budget is designed to quantify the privacy sensitivity of each node and adaptively allocate the privacy protection strength. Besides, a weighted neighborhood aggregation mechanism is proposed during the message-passing process of GNN training, which can eliminate the impact of the introduced differentiated DP noise on the utility of the GNN model. Since TDP-GNN is based on node-level local DP, it can be seamlessly integrated into any GNN architecture in a plug-and-play manner while ensuring formal privacy guarantees. Theoretical analysis indicates that TDP-GNN achieves $\epsilon$-differential privacy over the entire graph nodes while providing personalized privacy protection. Extensive experiments demonstrate that TDP-GNN consistently yields better utilities when applied to various GNN architectures (e.g., GCN and GraphSAGE) across a diverse set of benchmarks.

Docker has transformed modern software development, enabling the widespread reuse of containerized applications. Currently, Docker images are primarily distributed through centralized registries, among which Docker Hub is the largest, allowing developers to share and reuse images easily. The threats within these images also spread through the supply chain via dependency relationships, posing risks to anyone using the image and all images built based on it. However, it is unclear to what extent the threats within Docker images are distributed and propagated. In this paper, we investigate five potential security risks in three dimensions of Docker image information, including sensitive command parameters, secret leakage, software vulnerabilities, misconfigurations, and malicious files. We propose a security analysis framework DITECTOR based on these security issues. We utilize it to conduct a large-scale security measurement of the Docker image ecosystem. We collect descriptions of over 12 million image repositories from Docker Hub and construct an image dependency graph based on the layer information of the images. We select two sets of influential images for the Docker image ecosystem: high-pull-count images and high-dependency-weight images, totaling 33,952 images for inspection. Our findings are alarming: 93.7% of analyzed images contain known vulnerabilities, 4,437 images have secret leaks, 50 images contain misconfigurations, and 31 images execute malicious files. Furthermore, we identify 334 downstream images affected by malicious images based on the image dependency graph and uncover patterns of attack propagation within the supply chain. We have discussed the measures to mitigate these issues, reported our findings to the relevant parties, and received positive responses.

A polyglot is a file that is valid in two or more formats. Polyglot files pose a problem for file-upload and generative AI web interfaces that rely on format identification to determine how to securely handle incoming files. In this work we found that existing file-format and embedded-file detection tools, even those developed specifically for polyglot files, fail to reliably detect polyglot files used in the wild. To address this issue, we studied the use of polyglot files by malicious actors in the wild, finding 30 polyglot samples and 15 attack chains that leveraged polyglot files. Using knowledge from our survey of polyglot usage in the wild—the first of its kind—we created a novel data set based on adversary techniques. We then trained a machine learning detection solution, PolyConv, using this data set. PolyConv achieves a precision-recall area-under-curve score of 0.999 with an F1 score of 99.20% for polyglot detection and 99.47% for file-format identification, significantly outperforming all other tools tested. We developed a content disarmament and reconstruction tool, ImSan, that successfully sanitized 100% of the tested image-based polyglots, which were the most common type found via the survey. Our work provides concrete tools and suggestions to enable defenders to better defend themselves against polyglot files, as well as directions for future work to create more robust file specifications and methods of disarmament.

We propose a novel framework that addresses a critical limitation in Graph Self-Supervised Learning (GSSL) for graph classification: the underestimation of topological information. Traditional GSSL, despite its success in various benchmarks, often fails to fully leverage the expressive power of Graph Neural Networks (GNNs), particularly in capturing complex structural properties. This limitation stems from two main factors: (1) the inadequacy of conventional GNNs in representing sophisticated topological features, and (2) the focus of self-supervised learning solely on final graph representations. To address these issues, we introduce GenHopNet, a GNN framework that integrates a k-hop message-passing scheme, enhancing its ability to capture local structural information without explicit substructure extraction. We theoretically demonstrate that GenHopNet surpasses the expressiveness of the classical Weisfeiler-Lehman (WL) test for graph isomorphism. Furthermore, we propose a structural- and positional-aware GSSL framework that incorporates topological information throughout the learning process. This approach enables the learning of representations that are both sensitive to graph topology and invariant to specific structural and feature augmentations. Comprehensive experiments on graph classification datasets, including those designed to test structural sensitivity, show that our methods consistently outperform most of the existing approaches in accuracy while maintaining computational efficiency. Our work significantly advances GSSL's capability in distinguishing graphs with similar local structures but different global topologies.

Knowledge Graph Query Embedding (KGQE) aims to embed First-Order Logic (FOL) queries in a low-dimensional KG space for complex reasoning over incomplete KGs. To enhance the generalization of KGQE models, recent studies integrate various external information (such as entity types and relation context) to better capture the logical semantics of FOL queries. The whole process is commonly referred to as Query Pattern Learning (QPL). However, current QPL methods typically suffer from the pattern-entity alignment bias problem, leading to the learned defective query patterns limiting KGQE models' performance. To address this problem, we propose an effective Query Instruction Parsing Plugin (QIPP) that leverages the context awareness of Pre-trained Language Models (PLMs) to capture latent query patterns from code-like query instructions. Unlike the external information introduced by previous QPL methods, we first propose code-like instructions to express FOL queries in an alternative format. This format utilizes textual variables and nested tuples to convey the logical semantics within FOL queries, serving as raw materials for a PLM-based instruction encoder to obtain complete query patterns. Building on this, we design a query-guided instruction decoder to adapt query patterns to KGQE models. To further enhance QIPP's effectiveness across various KGQE models, we propose a query pattern injection mechanism based on compressed optimization boundaries and an adaptive normalization component, allowing KGQE models to utilize query patterns more efficiently. Extensive experiments demonstrate that our plug-and-play method improves the performance of eight basic KGQE models and outperforms two state-of-the-art QPL methods.

The classic clique model has properties of hereditaries and cohesiveness. Here hereditaries means a subgraph of a clique is still a clique. Counting small cliques in a graph is a fundamental operation of numerous applications. However, the clique model is often too restrictive for practical use, leading to the focus on other relaxed-cliques with properties of hereditaries and cohesiveness. To address this issue, we investigate a new problem of counting general hereditary cohesive subgraphs (\hcs). All subgraphs with properties of hereditaries and cohesiveness can be called a kind of \hcs. To count \hcs, we propose a general framework called \hcspivot, which can be applied to count all kinds of \hcs. \hcspivot can count most \hcs combinatorially without explicitly listing them. Two additional noteworthy features of \hcspivot are its ability to (1) simultaneously count \hcs of any size and (2) simultaneously count \hcs for each node or each edge. Based on our \hcspivot framework, we propose two novel algorithms with several carefully designed pruning techniques to count $s$-defective cliques and $s$-plexes, which are two specific types of \hcs. We conduct extensive experiments on 8 large real-world graphs, and the results demonstrate the high efficiency and effectiveness of our solutions.

In text-based person search endeavors, data generation has emerged as a prevailing practice, addressing concerns over privacy preservation and the arduous task of manual annotation. Although the number of synthesized data can be infinite in theory, the scientific conundrum persists that how much generated data optimally fuels subsequent model training. We observe that only a subset of the data in these constructed datasets plays a decisive role. Therefore, we introduce a new Filtering-WoRA paradigm, which contains a filtering algorithm to identify this crucial data subset and WoRA (Weighted Low-Rank Adaptation) learning strategy for light fine-tuning. The filtering algorithm is based on the cross-modality relevance to remove the lots of coarse matching synthesis pairs. As the number of data decreases, we do not need to fine-tune the entire model. Therefore, we propose a WoRA learning strategy to efficiently update a minimal portion of model parameters. WoRA streamlines the learning process, enabling heightened efficiency in extracting knowledge from fewer, yet potent, data instances. Extensive experimentation validates the efficacy of pretraining, where our model achieves advanced and efficient retrieval performance on challenging real-world benchmarks. Notably, on the CUHK-PEDES dataset, we have achieved a competitive mAP of 67.02% while reducing model training time by 19.82%.

Large language models (LLMs), with advanced linguistic capabilities, have been employed in reranking tasks through a sequence-to-sequence approach. In this paradigm, multiple passages are reranked in a listwise manner and a textual reranked permutation is generated. However, due to the limited context window of LLMs, this reranking paradigm requires a sliding window strategy to iteratively handle larger candidate sets. This not only increases computational costs but also restricts the LLM from fully capturing all the comparison information for all candidates. To address these challenges, we propose a novel self-calibrated listwise reranking method, which aims to leverage LLMs to produce global relevance scores for ranking. To achieve it, we first propose the relevance-aware listwise reranking framework, which incorporates explicit list-view relevance scores to improve reranking efficiency and enable global comparison across the entire candidate set. Second, to ensure the comparability of the computed scores, we propose self-calibrated training that uses point-view relevance assessments generated internally by the LLM itself to calibrate the list-view relevance assessments. Extensive experiments and comprehensive analysis on the BEIR benchmark and TREC Deep Learning Tracks demonstrate the effectiveness and efficiency of our proposed method.

Graph condensation has emerged as an intriguing technique to save the expensive training costs of Graph Neural Networks (GNNs) by substituting a condensed small graph with the original graph. Despite the promising results achieved, previous methods usually employ an entangled paradigm of redundant parameters (nodes, edges, GNNs), which incurs complex joint optimization during condensation. This paradigm has considerably impeded the scalability of graph condensation, making it challenging to condense extremely large-scale graphs and generate high-fidelity condensed graphs. Therefore, we propose to disentangle the condensation process into a two-stage GNN-free paradigm, independently condensing nodes and generating edges while eliminating the need to optimize GNNs at the same time. The node condensation module avoids the complexity of GNNs by focusing on node feature alignment with anchors of the original graph, while the edge translation module constructs the edges of the condensed nodes by transferring the original structure knowledge with neighborhood anchors. This simple yet effective approach achieves at least 10 times faster than state-of-the-art methods with comparable accuracy on medium-scale graphs. Moreover, the proposed DisCo can successfully scale up to the Ogbn-papers100M graph containing over 100 million nodes with flexible reduction rates and improves performance on the second-largest Ogbn-products dataset by over 5\%. Extensive downstream tasks and ablation study on five common datasets further demonstrate the effectiveness of the proposed DisCo framework. The source code will be made publicly available.