Multimedia systems underpin modern digital interactions, facilitating seamless integration and optimization of resources across diverse multimedia applications. To meet growing personalization demands, multimedia systems must efficiently manage competing resource needs, adaptive content, and user-specific data handling. This paper introduces Generative Flow Networks (GFlowNets, GFNs) as a brave new framework for enabling personalized multimedia systems. By integrating multi-candidate generative modeling with flow-based principles, GFlowNets offer a scalable and flexible solution for enhancing user-specific multimedia experiences. To illustrate the effectiveness of GFlowNets, we focus on short video feeds, a multimedia application characterized by high personalization demands and significant resource constraints, as a case study. Our proposed GFlowNet-based personalized feeds algorithm demonstrates superior performance compared to traditional rule-based and reinforcement learning methods across critical metrics, including video quality, resource utilization efficiency, and delivery cost. Moreover, we propose a unified GFlowNet-based framework generalizable to other multimedia systems, highlighting its adaptability and wide-ranging applicability. These findings underscore the potential of GFlowNets to advance personalized multimedia systems by addressing complex optimization challenges and supporting sophisticated multimedia application scenarios.
论文检索
输入标题、作者或关键词，从 1,090 篇学术成果中精准定位
Scalable Vector Graphics (SVG) has become an indispensable technology in front-end development and UI/UX design, due to its inherent advantages in scalability, editability, and rendering efficiency. In the creation of vector graphics, while expressing creative concepts is straightforward, translating them into precise digital artworks is often challenging and time-consuming. To overcome this technical bottleneck and achieve intelligent conversion from concept to final product, we have constructed SVG-1M, a large-scale dataset of high-quality SVG samples with paired textual descriptions. Through innovative data augmentation and annotation processes, we built precisely aligned ''Text instruction-SVG code'' training pairs, with a subset enhanced by Chain-of-Thought (CoT) annotations. This provides rich semantic supervision signals for model learning. Based on this dataset, we propose SVGen, an end-to-end generative model capable of directly converting natural language descriptions into SVG code. This design addresses the challenges of generating semantically accurate vector graphics while preserving complete structural information. We explored various training strategies and introduced a progressive curriculum learning approach, optimized with reinforcement learning algorithms. Notably, this study innovatively applies the CoT paradigm to vector graphics generation, effectively enhancing both the accuracy and interpretability of SVG synthesis. Experimental validation demonstrates that SVGen exhibits significant advantages over general large models in terms of SVG generation quality, while also surpassing optimization-based rendering methods in generation efficiency. The proposed method enables intelligent conversion between natural language and vector graphics, enabling novel workflows like real-time AI-assisted design iteration. Code, model, and data is released at: https://github.com/gitcat-404/SVGen
Multi-view clustering based on anchor graph has gained a lot of attention because of its ability to handle large-scale datasets in linear time. However, the existing methods learn anchors from linear space, ignore the nonlinear manifold characteristics of the original data, and fail to fully consider the geometric topological relationship of anchors in the space, which limits the representability of the anchor graph and makes these algorithms unable to deal with the complex data distribution in real scenarios. In addition, most methods involve the control of multiple hyper-parameters, which often require a significant amount of time for tuning, resulting in algorithms that are not as flexible and scalable as they could be. To address the above problems, this paper proposes Scalable multi-view clustering based on tight anchor distribution (TAD-MVC), where TAD-MVC closely associates neighboring anchors together and learns the degree of closeness between all anchors. In particular, TAD-MVC adaptively evaluates the tightness between anchors and spreads this tight structure with the aim of constraining anchors with a high degree of similarity to the same cluster, while anchors in different clusters will exclude each other as much as possible in order to learn anchors that are sufficiently representative. Experimental results on numerous datasets significantly outperforms the state-of-the-art methods. The code is available at https://github.com/whbdmu/TAD-MVC.
AI-generated counterspeech offers a promising and scalable strategy to curb online toxicity through direct replies that promote civil discourse. However, current counterspeech is one-size-fits-all, lacking adaptation to the moderation context and the users involved. We propose and evaluate multiple strategies for generating tailored counterspeech that is adapted to the moderation context and personalized for the moderated user. We instruct a LLaMA2-13B model to generate counterspeech, experimenting with various configurations based on different contextual information and fine-tuning strategies. We identify the configurations that generate persuasive counterspeech through a combination of quantitative indicators and human evaluations collected via a pre-registered mixed-design crowdsourcing experiment. Results show that contextualized counterspeech can significantly outperform state-of-the-art generic counterspeech in adequacy and persuasiveness, without compromising other characteristics. Our findings also reveal a poor correlation between quantitative indicators and human evaluations, suggesting that these methods assess different aspects and highlighting the need for nuanced evaluation methodologies. The effectiveness of contextualized AI-generated counterspeech and the divergence between human and algorithmic evaluations underscore the importance of increased human-AI collaboration in content moderation.
Web refresh crawling is the problem of keeping a cache of web pages fresh, that is, having the most recent copy available when a page is requested, given a limited bandwidth available to the crawler. Under the assumption that the change and request events, resp., to each web page follow independent Poisson processes, the optimal scheduling policy was derived by Azar et al. 2018. In this paper, we study an extension of this problem where side information indicating content changes, such as various types of web pings, for example, signals from sitemaps, content delivery networks, etc., is available. Incorporating such side information into the crawling policy is challenging, because (i) the signals can be noisy with false positive events and with missing change events; and (ii) the crawler should achieve a fair performance over web pages regardless of the quality of the side information, which might differ from web page to web page. We propose a scalable crawling algorithm which (i) uses the noisy side information in an optimal way under mild assumptions; (ii) can be deployed without heavy centralized computation; (iii) is able to crawl web pages at a constant total rate without spikes in the total bandwidth usage over any time interval, and automatically adapt to the new optimal solution when the total bandwidth changes without centralized computation. Experiments clearly demonstrate the versatility of our approach.
Fair Clustering for Data Summarization: Improved Approximation Algorithms and Complexity Insights
PDF ↗Data summarization tasks are often modeled as k-clustering problems, where the goal is to choose k data points, called cluster centers, that best represent the dataset by minimizing a clustering objective. A popular objective is to minimize the maximum distance between any data point and its nearest center, which is formalized as the k-center problem. While in some applications all data points can be chosen as centers, in the general setting, centers must be chosen from a predefined subset of points, referred as facilities or suppliers; this is known as the k-supplier problem. In this work, we focus on fair data summarization modeled as the fair k-supplier problem, where data consists of several groups, and a minimum number of centers must be selected from each group while minimizing the k-supplier objective. The groups can be disjoint or overlapping, leading to two distinct problem variants each with different computational complexity. We present 3-approximation algorithms for both variants, improving the previously known factor of 5. For disjoint groups, our algorithm runs in polynomial time, while for overlapping groups, we present a fixed-parameter tractable algorithm, where the exponential runtime depends only on the number of groups and centers. We show that these approximation factors match the theoretical lower bounds, assuming standard complexity theory conjectures. Finally, using an open-source implementation, we demonstrate the scalability of our algorithms on large synthetic datasets and assess the price of fairness on real-world data, comparing solution quality with and without fairness constraints.
LP-DIXIT: Evaluating Explanations for Link Predictions on Knowledge Graphs using Large Language Models
PDF ↗Knowledge Graphs provide a machine-readable representation of knowledge conforming to graph-based data models. Link prediction methods predict missing facts in incomplete knowledge graphs, often using scalable embedding based solutions that, however, lack comprehensibility which is crucial in many domains. Filling this gap, explanation methods identify supporting knowledge. For evaluating them, user studies are the obvious choice as users are the main recipients of explanations. However, finding domain experts is often challenging. In contrast, an automated approach is to measure the influence of explanations on the very same link prediction task, thus disregarding the perspective of users. Additionally, current evaluation methods vary across different explanation approaches. We propose LP-DIXIT, the first protocol to evaluate the utility of explanations of link predictions. LP-DIXIT is user-aware, algorithmic and unique for different explanation methods. It builds on a typical setting of user studies, but adopts Large Language Models (LLMs) to mimic users. Specifically, it measures how explanations improve the user (LLM) ability to perform predictions, which is key to trust. We experimentally proved an overall agreement between LP-DIXIT and user evaluations. Moreover, we adopted LP-DIXIT to conduct a comparative study of state-of-the-art explanation methods. The outcomes suggest that less is more: the most effective explanations are those consisting of a single fact.
In this paper, given a user's query set and budget, we aim to use the limited budget to help users assemble a set of datasets that can enrich a base dataset by introducing the maximum number of distinct tuples (i.e., maximizing distinctiveness). We prove this problem to be NP-hard. A greedy algorithm using exact distinctiveness computation attains an approximation ratio of (1-e-1 )/2, but it lacks efficiency and scalability due to its frequent computation of the exact distinctiveness marginal gain of any candidate dataset for selection. This requires scanning through every tuple in candidate datasets and thus is unaffordable in practice. To overcome this limitation, we propose an efficient machine learning (ML)-based method for estimating the distinctiveness marginal gain of any candidate dataset. This effectively eliminates the need to test each tuple individually. Estimating the distinctiveness marginal gain of a dataset involves estimating the number of distinct tuples in the tuple sets returned by each query in a query set across multiple datasets. This can be viewed as the cardinality estimation for a query set on a set of datasets, and the proposed method is the first to tackle this cardinality estimation problem. This is a significant advancement over prior methods that were limited to single-query cardinality estimation on a single dataset and struggled with identifying overlaps among tuple sets returned by each query in a query set across multiple datasets. Extensive experiments using five real-world data pools demonstrate that our algorithm, which utilizes ML-based distinctiveness estimation, outperforms all relevant baselines in effectiveness, efficiency, and scalability. A case study on two downstream ML tasks also highlights its potential to find datasets with more useful tuples to enhance the performance of ML tasks.
Network connectivity minimization is a fundamental problem in controlling the spread of viruses in the Internet and facilitating information propagation in online social networks. The problem aims to identify a budget number of key nodes whose removal would minimize the connectivity of a network. However, the existing solutions heavily rely on the number of edges, making it challenging to handle large and densely connected social networks. In this study, we present a fast algorithm that is independent of the number of edges. To achieve this, we first introduce a surrogate matrix that approximates the residual adjacency matrix with arbitrary small predefined error. We then devise an efficient approach for inferring k influential nodes by optimizing the eigenvalues of the surrogate matrix. Remarkably, the algorithm has a small time complexity of O(knr3), with r being a small tunable number. Our algorithm thereby maintains a linear scalability in terms of the number of nodes and is unaffected by the number of edges. Hence, it has the capability to efficiently handle large and dense social networks. At last, we evaluate its performance against state-of-the-art techniques using diverse real-world datasets. The experimental results demonstrate the superiority of our proposed method in terms of both solution quality and computational efficiency.
Existing foundation models, such as CLIP, aim to learn a unified embedding space for multimodal data, enabling a wide range of downstream web-based applications like search, recommendation, and content classification. However, these models often overlook the inherent graph structures in multimodal datasets, where entities and their relationships are crucial. Multimodal graphs (MMGs) represent such graphs where each node is associated with features from different modalities, while the edges capture the relationships between these entities.On the other hand, existing graph foundation models primarily focus on text-attributed graphs (TAGs) and are not designed to handle the complexities of MMGs. To address these limitations, we propose UniGraph2, a novel cross-domain graph foundation model that enables general representation learning on MMGs, providing a unified embedding space. UniGraph2 employs modality-specific encoders alongside a graph neural network (GNN) to learn a unified low-dimensional embedding space that captures both the multimodal information and the underlying graph structure. We propose a new cross-domain multi-graph pre-training algorithm at scale to ensure effective transfer learning across diverse graph domains and modalities. Additionally, we adopt a Mixture of Experts (MoE) component to align features from different domains and modalities, ensuring coherent and robust embeddings that unify the information across modalities. Extensive experiments on a variety of multimodal graph tasks demonstrate that UniGraph2 significantly outperforms state-of-the-art models in tasks such as representation learning, transfer learning, and multimodal generative tasks, offering a scalable and flexible solution for learning on MMGs.
Centrality measures are essential for identifying important nodes and edges in networks. In this paper, we focus on two forest-based centrality measures on undirected graphs: forest node centrality (FNC) and forest edge centrality (FEC), which capture the influence of nodes and edges through their participation in spanning forests. Both centrality measures can be represented using entries of the forest matrix. To address the challenge of computing the two measures on large networks, we propose two scalable algorithms from different perspectives. The first algorithm IFGN combines two variance reduction techniques to approximate the entries of the forest matrix, applicable to both FNC and FEC.The second algorithm FECE incorporates a new physical interpretation of FEC, allowing for a better overall estimation. We provide error guarantees for both algorithms and demonstrate their efficiency and effectiveness through extensive experiments on various real-world networks.
Facility location problems on graphs are ubiquitous in the real world and hold significant importance, yet their resolution is often impeded by NP-hardness. MIP solvers can find the optimal solutions but fail to handle large instances, while algorithm efficiency has a higher priority in cases of emergency. Recently, machine learning methods have been proposed to tackle such classical problems with fast inference, but they are limited to the myopic constructive pattern and only consider simple cases in Euclidean space. This paper introduces a unified and generalizable approach to tackle facility location problems on weighted graphs with deep reinforcement learning, demonstrating a keen awareness of complex graph structures. Striking a harmonious balance between solution quality and running time, our method stands out with superior efficiency and steady performance. Our model trained on small graphs is highly scalable and consistently generates high-quality solutions, achieving a speedup of more than 2000 times to Gurobi on instances with 1000 nodes. The experiments on Shanghai road networks further demonstrate its practical value in solving real-world problems. The source codes are available at https://github.com/AryaGuo/PPO-swap.
A vast amount of user behavior data is constantly accumulating on today's large recommendation platforms, recording users' various interests and tastes. Preserving knowledge from the old data while new data continually arrives is a vital problem for recommender systems. Existing approaches generally seek to save the knowledge implicitly in the model parameters. However, such a parameter-centric approach lacks scalability and flexibility---the capacity is hard to scale, and the knowledge is inflexible to utilize. Hence, in this work, we propose a framework that turns massive user behavior data to retrievable knowledge (D2K). It is a data-centric approach that is model-agnostic and easy to scale up. Different from only storing unary knowledge such as the user-side or item-side information, D2K propose to store ternary knowledge for recommendation, which is determined by the complete recommendation factors---user, item, and context. The knowledge retrieved by target samples can be directly used to enhance the performance of any recommendation algorithms. Specifically, we introduce a Transformer-based knowledge encoder to transform the old data into knowledge with the user-item-context cross features. A personalized knowledge adaptation unit is devised to effectively exploit the information from the knowledge base by adapting the retrieved knowledge to the target samples. Extensive experiments demonstrate the superiority of the proposed method.
This special day event on Responsible Artificial Intelligence (AI) brings together researchers, practitioners, and policymakers to explore how data mining and machine learning systems can be designed to align with ethical principles, societal values, and human well-being. As AI technologies increasingly influence decisions in healthcare, finance, governance, and social systems, there is a critical need to develop frameworks that embed fairness, accountability, and privacy directly into the foundations of knowledge discovery. This full-day event will feature a mix of invited talks, interactive debates, expert panels, and peer-reviewed research presentations, all focused on the practical integration of ethical design into data-driven systems. The Responsible AI Day builds on the success of Canada's NSERC CREATE Program on Responsible AI, an interdisciplinary initiative training the next generation of AI researchers across computer science, law, bioethics, public health, and media studies. Topics will span scalable AI governance, privacy-preserving computation, algorithmic bias mitigation, and the socio-legal tensions emerging in generative AI. By positioning responsible AI as a sociotechnical challenge, this special day aligns with KDD's mission of advancing data science that is not only technically robust but also socially conscious.
IVMR suite: An Industrial-scale Virtual Machine Rescheduling Dataset and Benchmark for Elastic Cloud Service
PDF ↗Virtual Machine Rescheduling (VMR) plays a crucial role in maintaining service quality and resource efficiency in elastic cloud computing. However, existing datasets and benchmarks primarily focus on VM scheduling tasks, while lacking industrial-scale datasets and standardized evaluation for the more complex and crucial rescheduling problems. To address these challenges, we present IVMR suite, the first industrial-scale suite for VMR research comprising two core components: 1) IVMR-D, an industrial-grade VMR dataset mined from a real cloud data center, integrating complete resource specifications and complex operation constraints. The dataset is systematically structured based on data size and optimization objectives. 2) IVMR-B, a benchmark for the VMR problem that establishes seamless integration of consistent evaluation and the provision of baselines spanning optimization, metaheuristic, heuristic, and machine learning-based methodologies. Our comprehensive experimental evaluation demonstrates that all tested VMR algorithms struggle to effectively balance solution quality with computational efficiency while showing limited scalability across tasks with varying complexity levels. These findings emphasize the urgency of improving VMR algorithms for industrial deployments.
Path planning is a critical challenge for Autonomous Underwater Vehicles (AUVs) due to complex underwater environments, including ocean currents, dynamic obstacles, and limited sensing capabilities. The lack of a standardized benchmarking framework has hindered direct comparisons between algorithms, slowing progress in the field. To address this, we introduce an open-source benchmarking platform for underwater AUV path planning, designed to provide a unified evaluation environment, automated performance assessment, and reproducible experiments. Built on the HoloOcean simulation platform, our benchmark incorporates realistic underwater dynamics, such as ocean currents, static and dynamic obstacles, and sensor models. It supports a range of path planning tasks, from basic obstacle avoidance to complex scenarios with current disturbances. The platform is compatible with classical algorithms (e.g., A*, RRT), evolutionary methods (e.g., GA, ACO), and deep reinforcement learning (e.g., Soft Actor-Critic, SAC). We define key evaluation metrics, including path efficiency (length, smoothness, energy consumption), task success rate, collision rate, and computational cost. Automated tools enable systematic algorithm comparisons across scenarios, generating standardized performance results and visualizations. This open-source, extensible framework aims to advance underwater path planning research by enabling fair comparisons and guiding future algorithm development. It provides a scalable foundation for evaluating AUV path planning methods under simulated real-world conditions, fostering innovation in the field. All source code and experimental configurations will be available on the GitHub Page: https://github.com/IoET-y/UP-bench.
Symbolic Regression (SR) algorithms are powerful machine learning tools that discover mathematical expressions from data, but their evaluation is often hindered by the computational cost of optimizing numerical parameters (also called constants) within candidate expressions. To address this limitation, we introduce POVE (PreOptimized Vault of Expressions), a comprehensive repository of preoptimized symbolic expressions where numerical parameters have been efficiently computed using an established optimization technique in SR (i.e., BFGS) on widely used SR regression problems (i.e., SRBench). In addition to optimized constants, POVE stores the corresponding fitness values, quantifying the accuracy of each expression on its respective regression problem, allowing researchers to directly retrieve both optimized expressions and their precomputed performance metrics from memory (e.g., hash tables or dictionaries). By eliminating the need for computationally expensive numerical optimization steps, POVE enables significantly faster evaluation, large-scale benchmarking, and extensive hyperparameter analysis. It provides a structured and standardized foundation for comparing SR algorithms, assessing their consistency across large numbers of random seeds and investigating the impact of hyperparameters without the overhead of numerical parameter optimization. By offering a collection of precomputed expressions, parameters, and fitness values across diverse regression problems, POVE enhances reproducibility, accelerates experimental workflows, and enables scalable SR research. It serves as a valuable resource for both developing novel SR methodologies and improving existing algorithms by providing a reliable reference for optimal expression discovery. With POVE, SR research can shift away from costly optimization, enabling deeper algorithmic exploration and more comprehensive systematic evaluation. POVE also lowers the barrier to entry for SR research and makes large-scale evaluation significantly more accessible. POVE is publicly available at: https://github.com/kentridgeai/POVE
Cohesive subgraph mining is a fundamental problem in graph theory with numerous real-world applications, such as social network analysis and protein-protein interaction modeling. Among various cohesive subgraphs, the γ-quasi-clique is widely studied for its flexibility in requiring each vertex to connect to at least a γ proportion of other vertices in the subgraph. However, solving the maximum γ-quasi-clique problem is NP-hard and further complicated by the lack of the hereditary property, which makes designing efficient pruning strategies challenging. Existing algorithms, such as DDA and FastQC, either struggle with scalability or exhibit significant performance declines for small values of γ. In this paper, we propose a novel algorithm, IterQC, which reformulates the maximum γ-quasi-clique problem as a series of k-plex problems that possess the hereditary property. IterQC introduces a non-trivial iterative framework and incorporates two key optimization techniques: (1) the pseudo lower bound (pseudo LB) technique, which leverages information across iterations to improve the efficiency of branch-and-bound searches, and (2) the preprocessing technique that reduces problem size and unnecessary iterations. Extensive experiments demonstrate that IterQC achieves up to four orders of magnitude speedup and solves significantly more graph instances compared to state-of-the-art algorithms DDA and FastQC.
Vector quantization (VQ) is an effective technique for data compression and is widely used in approximate nearest neighbor search (ANNs). Based on the multi-codebook quantization (MCQ), most of existing VQ methods focus on the refinement of codebook structure to enhance performance. However, the uneven distribution of raw vectors poses challenges for effective codebook learning. Previous attempts to learn distribution transformations for raw vectors have struggled with minimal accuracy improvements and limited scalability due to poor convergence. To address these problems, we propose a Progressive Distribution Transformation (PDT) algorithm based on denoising autoencoder for VQ optimization. Our approach employs multi-head distribution transformation (MHDT) blocks to progressively learn transformation offsets, allowing raw vectors to be transformed into a quantization-friendly latent space step-by-step. Notably, the proposed PDT algorithm can be seamlessly integrated with diverse existing deep MCQ methods, facilitating end-to-end training and efficient inference. Furthermore, it also enables easy integration with VQ-based ANNs methods. Experimental results show that our method outperforms state-of-the-art MCQ methods by 20.6% and significantly boosts existing deep MCQ techniques by 58.5% in search accuracy across various similarity search datasets, while also exhibiting improved scalability and efficiency. The code has been available at https://github.com/Lenovo-ICI/PDT-VQ.
Online social networks have become an integral part of modern society, profoundly influencing how individuals form and exchange opinions across diverse domains ranging from politics to public health. The Friedkin-Johnsen model serves as a foundational framework for modeling opinion formation dynamics in such networks. In this paper, we address the computational task of efficiently determining the equilibrium opinion vector and associated metrics including polarization and disagreement, applicable to both directed and undirected social networks. We propose a deterministic local algorithm with relative error guarantees, scaling to networks exceeding ten million nodes. Further acceleration is achieved through integration with successive over-relaxation techniques, where a relaxation factor optimizes convergence rates. Extensive experiments on diverse real-world networks validate the practical effectiveness of our approaches, demonstrating significant improvements in computational efficiency and scalability compared to conventional methods.