OpenRaiser/Intern-Atlas huggingface dataset:
Jet: Multilevel Graph Partitioning on Graphics Processing Units
Venue: arXiv cs.DC 2024
Year: 2024

The multilevel heuristic is the dominant strategy for high-quality sequential and parallel graph partitioning. Partition refinement is a key step of multilevel graph partitioning. In this work, we present Jet, a new parallel algorithm for partition refinement specifically designed for Graphics Processing Units (GPUs). We combine Jet with GPU-aware coarsening to develop a $k$-way graph partitioner, the Jet partitioner. The new partitioner achieves superior quality compared to state-of-the-art shared memory partitioners on a large collection of test graphs.
mPLUG-Owl: Modularization Empowers Large Language Models with Multimodality
Venue: arXiv cs.CL 2024
Year: 2024

Large language models (LLMs) have demonstrated impressive zero-shot abilities on a variety of open-ended tasks, while recent research has also explored the use of LLMs for multi-modal generation. In this study, we introduce mPLUG-Owl, a novel training paradigm that equips LLMs with multi-modal abilities through modularized learning of foundation LLM, a visual knowledge module, and a visual abstractor module. This approach can support multiple modalities and facilitate diverse unimodal and multimodal abilities through modality collaboration. The training paradigm of mPLUG-Owl involves a two-stage method for aligning image and text, which learns visual knowledge with the assistance of LLM while maintaining and even improving the generation abilities of LLM. In the first stage, the visual knowledge module and abstractor module are trained with a frozen LLM module to align the image and text. In the second stage, language-only and multi-modal supervised datasets are used to jointly fine-tune a low-rank adaption (LoRA) module on LLM and the abstractor module by freezing the visual knowledge module. We carefully build a visually-related instruction evaluation set OwlEval. Experimental results show that our model outperforms existing multi-modal models, demonstrating mPLUG-Owl's impressive instruction and visual understanding ability, multi-turn conversation ability, and knowledge reasoning ability. Besides, we observe some unexpected and exciting abilities such as multi-image correlation and scene text understanding, which makes it possible to leverage it for harder real scenarios, such as vision-only document comprehension. Our code, pre-trained model, instruction-tuned models, and evaluation set are available at https://github.com/X-PLUG/mPLUG-Owl. The online demo is available at https://www.modelscope.cn/studios/damo/mPLUG-Owl.
LibCity: A Unified Library Towards Efficient and Comprehensive Urban Spatial-Temporal Prediction
Venue: arXiv cs.LG 2024
Year: 2024

As deep learning technology advances and more urban spatial-temporal data accumulates, an increasing number of deep learning models are being proposed to solve urban spatial-temporal prediction problems. However, there are limitations in the existing field, including open-source data being in various formats and difficult to use, few papers making their code and data openly available, and open-source models often using different frameworks and platforms, making comparisons challenging. A standardized framework is urgently needed to implement and evaluate these methods. To address these issues, we propose LibCity, an open-source library that offers researchers a credible experimental tool and a convenient development framework. In this library, we have reproduced 65 spatial-temporal prediction models and collected 55 spatial-temporal datasets, allowing researchers to conduct comprehensive experiments conveniently. By enabling fair model comparisons, designing a unified data storage format, and simplifying the process of developing new models, LibCity is poised to make significant contributions to the spatial-temporal prediction field.
Dynamic Pricing and Advertising with Demand Learning
Venue: arXiv cs.GT 2024
Year: 2024

We consider a novel pricing and advertising framework, where a seller not only sets product price but also designs flexible 'advertising schemes' to influence customers' valuation of the product. We impose no structural restriction on the seller's feasible advertising strategies and allow her to advertise the product by disclosing or concealing any information. Following the literature in information design, this fully flexible advertising can be modeled as the seller being able to choose any information policy that signals the product quality/characteristic to the customers. Customers observe the advertising signal and infer a Bayesian belief over the products. We aim to investigate two questions in this work: (1) What is the value of advertising? To what extent can advertising enhance a seller's revenue? (2) Without any apriori knowledge of the customers' demand function, how can a seller adaptively learn and optimize both pricing and advertising strategies using past purchase responses? To study the first question, we introduce and study the value of advertising - a revenue gap between using advertising vs not advertising, and we provide a crisp tight characterization for this notion for a broad family of problems. For the second question, we study the seller's dynamic pricing and advertising problem with demand uncertainty. Our main result for this question is a computationally efficient online algorithm that achieves an optimal $O(T^{2/3}(m\log T)^{1/3})$ regret rate when the valuation function is linear in the product quality. Here $m$ is the cardinality of the discrete product quality domain and $T$ is the time horizon. This result requires some mild regularity assumptions on the valuation function, but no Lipschitz or smoothness assumption on the customers' demand function. We also obtain several improved results for the widely considered special case of additive valuations.
Energy-based Models are Zero-Shot Planners for Compositional Scene Rearrangement
Venue: arXiv cs.RO 2024
Year: 2024

Language is compositional; an instruction can express multiple relation constraints to hold among objects in a scene that a robot is tasked to rearrange. Our focus in this work is an instructable scene-rearranging framework that generalizes to longer instructions and to spatial concept compositions never seen at training time. We propose to represent language-instructed spatial concepts with energy functions over relative object arrangements. A language parser maps instructions to corresponding energy functions and an open-vocabulary visual-language model grounds their arguments to relevant objects in the scene. We generate goal scene configurations by gradient descent on the sum of energy functions, one per language predicate in the instruction. Local vision-based policies then re-locate objects to the inferred goal locations. We test our model on established instruction-guided manipulation benchmarks, as well as benchmarks of compositional instructions we introduce. We show our model can execute highly compositional instructions zero-shot in simulation and in the real world. It outperforms language-to-action reactive policies and Large Language Model planners by a large margin, especially for long instructions that involve compositions of multiple spatial concepts. Simulation and real-world robot execution videos, as well as our code and datasets are publicly available on our website: https://ebmplanner.github.io.
A manifold learning-based CSI feedback framework for FDD massive MIMO
Venue: arXiv cs.IT 2024
Year: 2024

Massive multi-input multi-output (MIMO) in Frequency Division Duplex (FDD) mode suffers from heavy feedback overhead for Channel State Information (CSI). In this paper, a novel manifold learning-based CSI feedback framework (MLCF) is proposed to reduce the feedback and improve the spectral efficiency for FDD massive MIMO. Manifold learning (ML) is an effective method for dimensionality reduction. However, most ML algorithms focus only on data compression, and lack the corresponding recovery methods. Moreover, the computational complexity is high when dealing with incremental data. Considering to utilize the intrinsic manifold structure where the CSI samples reside, we propose a landmark selection algorithm to describe the topological skeleton of this manifold. Based on the learned skeleton, the local patch of the incremental CSI on the manifold can be easily determined by its nearest landmarks. This motivates us to propose an incremental CSI compression and reconstruction scheme by keeping the local geometric relationships with landmarks invariant. We theoretically prove the convergence of the proposed landmark selection algorithm. Meanwhile, the upper bound on the error of approximating CSI with landmarks is derived. Simulation results under an industrial channel model of 3GPP demonstrate that the proposed MLCF outperforms existing deep learning based algorithms.
HQP: A Human-Annotated Dataset for Detecting Online Propaganda
Venue: arXiv cs.CL 2024
Year: 2024

Online propaganda poses a severe threat to the integrity of societies. However, existing datasets for detecting online propaganda have a key limitation: they were annotated using weak labels that can be noisy and even incorrect. To address this limitation, our work makes the following contributions: (1) We present HQP: a novel dataset (N = 30,000) for detecting online propaganda with high-quality labels. To the best of our knowledge, HQP is the first large-scale dataset for detecting online propaganda that was created through human annotation. (2) We show empirically that state-of-the-art language models fail in detecting online propaganda when trained with weak labels (AUC: 64.03). In contrast, state-of-the-art language models can accurately detect online propaganda when trained with our high-quality labels (AUC: 92.25), which is an improvement of ~44%. (3) We show that prompt-based learning using a small sample of high-quality labels can still achieve a reasonable performance (AUC: 80.27) while significantly reducing the cost of labeling. (4) We extend HQP to HQP+ to test how well propaganda across different contexts can be detected. Crucially, our work highlights the importance of high-quality labels for sensitive NLP tasks such as propaganda detection.
Causal Reasoning and Large Language Models: Opening a New Frontier for Causality
Venue: arXiv cs.AI 2024
Year: 2024

The causal capabilities of large language models (LLMs) are a matter of significant debate, with critical implications for the use of LLMs in societally impactful domains such as medicine, science, law, and policy. We conduct a "behavorial" study of LLMs to benchmark their capability in generating causal arguments. Across a wide range of tasks, we find that LLMs can generate text corresponding to correct causal arguments with high probability, surpassing the best-performing existing methods. Algorithms based on GPT-3.5 and 4 outperform existing algorithms on a pairwise causal discovery task (97%, 13 points gain), counterfactual reasoning task (92%, 20 points gain) and event causality (86% accuracy in determining necessary and sufficient causes in vignettes). We perform robustness checks across tasks and show that the capabilities cannot be explained by dataset memorization alone, especially since LLMs generalize to novel datasets that were created after the training cutoff date. That said, LLMs exhibit unpredictable failure modes, and we discuss the kinds of errors that may be improved and what are the fundamental limits of LLM-based answers. Overall, by operating on the text metadata, LLMs bring capabilities so far understood to be restricted to humans, such as using collected knowledge to generate causal graphs or identifying background causal context from natural language. As a result, LLMs may be used by human domain experts to save effort in setting up a causal analysis, one of the biggest impediments to the widespread adoption of causal methods. Given that LLMs ignore the actual data, our results also point to a fruitful research direction of developing algorithms that combine LLMs with existing causal techniques. Code and datasets are available at https://github.com/py-why/pywhy-llm.
On-demand Mobility-as-a-Service platform assignment games with guaranteed stable outcomes
Venue: arXiv cs.GT 2024
Year: 2024

Mobility-as-a-Service (MaaS) systems are two-sided markets, with two mutually exclusive sets of agents, i.e., travelers/users and operators, forming a mobility ecosystem in which multiple operators compete or cooperate to serve customers under a governing platform provider. This study proposes a MaaS platform equilibrium model based on many-to-many assignment games incorporating both fixed-route transit services and mobility-on-demand (MOD) services. The matching problem is formulated as a convex multicommodity flow network design problem under congestion that captures the cost of accessing MOD services. The local stability conditions reflect a generalization of Wardrop's principles that include operators' decisions. Due to the presence of congestion, the problem may result in non-stable designs, and a subsidy mechanism from the platform is proposed to guarantee local stability. A new exact solution algorithm to the matching problem is proposed based on a branch and bound framework with a Frank-Wolfe algorithm integrated with Lagrangian relaxation and subgradient optimization, which guarantees the optimality of the matching problem but not stability. A heuristic which integrates stability conditions and subsidy design is proposed, which reaches either an optimal MaaS platform equilibrium solution with global stability, or a feasible locally stable solution that may require subsidy. For the heuristic, a worst-case bound and condition for obtaining an exact solution are both identified. An expanded Sioux Falls network test with 82 nodes and 748 links derives generalizable insights about the model for coopetitive interdependencies between operators sharing the platform, handling congestion effects in MOD services, effects of local stability on investment impacts, and illustrating inequities that may arise under heterogeneous populations.
Fast Path Planning Through Large Collections of Safe Boxes
Venue: arXiv cs.RO 2024
Year: 2024

We present a fast algorithm for the design of smooth paths (or trajectories) that are constrained to lie in a collection of axis-aligned boxes. We consider the case where the number of these safe boxes is large, and basic preprocessing of them (such as finding their intersections) can be done offline. At runtime we quickly generate a smooth path between given initial and terminal positions. Our algorithm designs trajectories that are guaranteed to be safe at all times, and detects infeasibility whenever such a trajectory does not exist. Our algorithm is based on two subproblems that we can solve very efficiently: finding a shortest path in a weighted graph, and solving (multiple) convex optimal-control problems. We demonstrate the proposed path planner on large-scale numerical examples, and we provide an efficient open-source software implementation, fastpathplanning.
LST-Bench: Benchmarking Log-Structured Tables in the Cloud
Venue: arXiv cs.DB 2024
Year: 2024

Data processing engines increasingly leverage distributed file systems for scalable, cost-effective storage. While the Apache Parquet columnar format has become a popular choice for data storage and retrieval, the immutability of Parquet files renders it impractical to meet the demands of frequent updates in contemporary analytical workloads. Log-Structured Tables (LSTs), such as Delta Lake, Apache Iceberg, and Apache Hudi, offer an alternative for scenarios requiring data mutability, providing a balance between efficient updates and the benefits of columnar storage. They provide features like transactions, time-travel, and schema evolution, enhancing usability and enabling access from multiple engines. Moreover, engines like Apache Spark and Trino can be configured to leverage the optimizations and controls offered by LSTs to meet specific business needs. Conventional benchmarks and tools are inadequate for evaluating the transformative changes in the storage layer resulting from these advancements, as they do not allow us to measure the impact of design and optimization choices in this new setting. In this paper, we propose a novel benchmarking approach and metrics that build upon existing benchmarks, aiming to systematically assess LSTs. We develop a framework, LST-Bench, which facilitates effective exploration and evaluation of the collaborative functioning of LSTs and data processing engines through tailored benchmark packages. A package is a mix of use patterns reflecting a target workload; LST-Bench makes it easy to define a wide range of use patterns and combine them into a package, and we include a baseline package for completeness. Our assessment demonstrates the effectiveness of our framework and benchmark packages in extracting valuable insights across diverse environments. The code for LST-Bench is open-sourced and is available at https://github.com/microsoft/lst-bench/ .
Complex Logical Reasoning over Knowledge Graphs using Large Language Models
Venue: arXiv cs.LO 2024
Year: 2024

Reasoning over knowledge graphs (KGs) is a challenging task that requires a deep understanding of the complex relationships between entities and the underlying logic of their relations. Current approaches rely on learning geometries to embed entities in vector space for logical query operations, but they suffer from subpar performance on complex queries and dataset-specific representations. In this paper, we propose a novel decoupled approach, Language-guided Abstract Reasoning over Knowledge graphs (LARK), that formulates complex KG reasoning as a combination of contextual KG search and logical query reasoning, to leverage the strengths of graph extraction algorithms and large language models (LLM), respectively. Our experiments demonstrate that the proposed approach outperforms state-of-the-art KG reasoning methods on standard benchmark datasets across several logical query constructs, with significant performance gain for queries of higher complexity. Furthermore, we show that the performance of our approach improves proportionally to the increase in size of the underlying LLM, enabling the integration of the latest advancements in LLMs for logical reasoning over KGs. Our work presents a new direction for addressing the challenges of complex KG reasoning and paves the way for future research in this area.
A Construction of Arbitrarily Large Type-II $Z$ Complementary Code Set
Venue: arXiv cs.IT 2024
Year: 2024

For a type-I $(K,M,Z,N)$-ZCCS, it follows $K \leq M \left\lfloor \frac{N}{Z}\right\rfloor$. In this paper, we propose a construction of type-II $(p^{k+n},p^k,p^{n+r}-p^r+1,p^{n+r})$-$Z$ complementary code set (ZCCS) using an extended Boolean function, its properties of Hamiltonian paths and the concept of isolated vertices, where $p\ge 2$. However, the proposed type-II ZCCS provides $K = M(N-Z+1)$ codes, where as for type-I $(K,M,N,Z)$-ZCCS, it is $K \leq M \left\lfloor \frac{N}{Z}\right\rfloor$. Therefore, the proposed type-II ZCCS provides a larger number of codes compared to type-I ZCCS. Further, as a special case of the proposed construction, $(p^k,p^k,p^n)$-CCC can be generated, for any integral value of $p\ge2$ and $k\le n$.
An Autonomous Non-monolithic Agent with Multi-mode Exploration based on Options Framework
Venue: arXiv cs.AI 2024
Year: 2024

Most exploration research on reinforcement learning (RL) has paid attention to `the way of exploration', which is `how to explore'. The other exploration research, `when to explore', has not been the main focus of RL exploration research. The issue of `when' of a monolithic exploration in the usual RL exploration behaviour binds an exploratory action to an exploitational action of an agent. Recently, a non-monolithic exploration research has emerged to examine the mode-switching exploration behaviour of humans and animals. The ultimate purpose of our research is to enable an agent to decide when to explore or exploit autonomously. We describe the initial research of an autonomous multi-mode exploration of non-monolithic behaviour in an options framework. The higher performance of our method is shown against the existing non-monolithic exploration method through comparative experimental results.
AutoColor: Learned Light Power Control for Multi-Color Holograms
Venue: arXiv cs.CV 2024
Year: 2024

Multi-color holograms rely on simultaneous illumination from multiple light sources. These multi-color holograms could utilize light sources better than conventional single-color holograms and can improve the dynamic range of holographic displays. In this letter, we introduce AutoColor , the first learned method for estimating the optimal light source powers required for illuminating multi-color holograms. For this purpose, we establish the first multi-color hologram dataset using synthetic images and their depth information. We generate these synthetic images using a trending pipeline combining generative, large language, and monocular depth estimation models. Finally, we train our learned model using our dataset and experimentally demonstrate that AutoColor significantly decreases the number of steps required to optimize multi-color holograms from > 1000 to 70 iteration steps without compromising image quality.
Basic syntax from speech: Spontaneous concatenation in unsupervised deep neural networks
Venue: arXiv cs.CL 2024
Year: 2024

Computational models of syntax are predominantly text-based. Here we propose that the most basic first step in the evolution of syntax can be modeled directly from raw speech in a fully unsupervised way. We focus on one of the most ubiquitous and elementary suboperation of syntax -- concatenation. We introduce spontaneous concatenation: a phenomenon where convolutional neural networks (CNNs) trained on acoustic recordings of individual words start generating outputs with two or even three words concatenated without ever accessing data with multiple words in the input. We replicate this finding in several independently trained models with different hyperparameters and training data. Additionally, networks trained on two words learn to embed words into novel unobserved word combinations. We also show that the concatenated outputs contain precursors to compositionality. To our knowledge, this is a previously unreported property of CNNs trained in the ciwGAN/fiwGAN setting on raw speech and has implications both for our understanding of how these architectures learn as well as for modeling syntax and its evolution in the brain from raw acoustic inputs. We also propose a potential neural mechanism called disinhibition that outlines a possible neural pathway towards concatenation and compositionality and suggests our modeling is useful for generating testable prediction for biological and artificial neural processing of speech.
INDCOR White Paper 2: Interactive Narrative Design for Representing Complexity
Venue: arXiv cs.HC 2024
Year: 2024

This white paper was written by the members of the Work Group focusing on design practices of the COST Action 18230 - Interactive Narrative Design for Complexity Representation (INDCOR, WG1). It presents an overview of Interactive Digital Narratives (IDNs) design for complexity representations through IDN workflows and methodologies, IDN authoring tools and applications. It provides definitions of the central elements of the IDN alongside its best practices, designs and methods. Finally, it describes complexity as a feature of IDN, with related examples. In summary, this white paper serves as an orienting map for the field of IDN design, understanding where we are in the contemporary panorama while charting the grounds of their promising futures.