One Quarter Each (on Average) Ensures Proportionality

We consider the problem of fair allocation of m indivisible items to a group of n agents with subsidy (money). Our work mainly focuses on the allocation of chores but most of our results extend to the allocation of goods as well. We consider the case when agents have (general) additive cost functions. Assuming that the maximum cost of an item to an agent can be compensated by one dollar, we show that a total of n/4 dollars of subsidy suffices to ensure a proportional allocation. Moreover, we show that n/4 is tight in the sense that there exists an instance with n agents for which every proportional allocation requires a total subsidy of at least n/4. We also consider the weighted case and show that a total subsidy of (n-1)/2 suffices to ensure a weighted proportional allocation.

Revisiting Proportional Allocation with Subsidy: Simplification and Improvements

In this paper, we revisit the problem of fair allocation with subsidy. We first consider the allocation of m indivisible chores to n agents with additive cost functions. Under the assumption that the maximum cost of an item can be compensated by one dollar, Wu et al. (WINE 2023) showed that a total of n/4 dollars suffices to guarantee a proportional allocation, by rounding fractional allocations. Their subsidy guarantee is optimal when n is even. For odd n, there is still a small gap between the upper and lower bounds for the total subsidy. In this paper, we propose a much simpler algorithm for the problem, which does not require rounding fractional allocations, and achieves an optimal subsidy guarantee for all values of n. We further show that our algorithm and analysis framework can be extended to the mixture of (subjective) goods and chores, achieving the optimal subsidy guarantee.

HyperFM: Fact-Centric Multimodal Fusion for Link Prediction over Hyper-Relational Knowledge Graphs

With the ubiquity of hyper-relational facts in modern Knowledge Graphs (KGs), existing link prediction techniques mostly focus on learning the sophisticated relationships among multiple entities and relations contained in a fact, while ignoring the multimodal information, which often provides additional clues to boost link prediction performance. Nevertheless, traditional multimodal fusion approaches, which are mainly designed for triple facts under either entity-centric or relation-guided fusion schemes, fail to integrate multimodal information with the rich context of the hyper-relational fact consisting of multiple entities and relations. Against this background, we propose HyperFM, a Hyper-relational Fact-centric Multimodal Fusion technique. It effectively captures the intricate interactions between different data modalities while accommodating the hyper-relational structure of the KG in a fact-centric manner via a customized Hypergraph Transformer. We evaluate HyperFM against a sizeable collection of baselines in link prediction tasks on two real-world KG datasets. Results show that HyperFM consistently achieves the best performance, yielding an average improvement of 6.0-6.8% over the best-performing baselines on the two datasets. Moreover, a series of ablation studies systematically validate our fact-centric fusion scheme.

CasFT: Future Trend Modeling for Information Popularity Prediction with Dynamic Cues-Driven Diffusion Models

The rapid spread of diverse information on online social platforms has prompted both academia and industry to realize the importance of predicting content popularity, which could benefit a wide range of applications, such as recommendation systems and strategic decision-making. Recent works mainly focused on extracting spatiotemporal patterns inherent in the information diffusion process within a given observation period so as to predict its popularity over a future period of time. However, these works often overlook the future popularity trend, as future popularity could either increase exponentially or stagnate, introducing uncertainties to the prediction performance. Additionally, how to transfer the preceding-term dynamics learned from the observed diffusion process into future-term trends remains an unexplored challenge. Against this background, we propose CasFT, which leverages observed information Cascades and dynamic cues extracted via neural ODEs as conditions to guide the generation of Future popularity-increasing Trends through a diffusion model. These generated trends are then combined with the spatiotemporal patterns in the observed information cascade to make the final popularity prediction. Extensive experiments conducted on three real-world datasets demonstrate that CasFT significantly improves the prediction accuracy compared to state-of-the-art approaches.

Topological Learning for Spatio-Temporal Prediction

In spatio-temporal prediction tasks, topological learning plays a crucial role in capturing the complex spatial-temporal relation between nodes. Topological information can be classified into two types: Group-level and Individual-level. Group-level topological information, derived from sensor clusters, reflects the spatial arrangement of sensors and provides a topology-distance relation for spatio-temporal prediction. Individual-level topological information, provided by users, reflects the historical interaction between users and items, offering a topology-preference relation for spatio-temporal prediction. In this talk, I will first introduce what topological learning is and why it is important for spatio-temporal prediction. Then, I will propose specific topological learning strategies to better capture two types of topological relations: (1) Group-level, with an application in traffic speed prediction, I propose the Dual Cross-Scale Transformer to capture topology-free, hierarchical, and dynamic topological relations between roads. (2) Individual-level, with an application in POI recommendation, I propose the Preference Evolution Transformer to capture the asymmetric and dynamic topological relations between users, as well as the general and unique topological relations between users and POIs. Finally, I will conclude the talk and look ahead to the future of applying topological learning in more applications.

Robust Time Series Forecasting Under Distribution Shift

Time series forecasting is a common task where models learn temporal and spatial information from historical observations to predict future values. However, distribution shift frequently occurs in time series, causing significant performance degradation in forecasting models. To address this issue, a common approach is to decouple time series into invariant and variant patterns, learning them separately and then combining them for forecasting. Since distribution shift is pervasive in time series, it needs to be properly addressed across various tasks such as offline forecasting, Variable Subset Forecasting (VSF), and online forecasting. This presentation will share effective strategies for handling distribution shift in these different forecasting scenarios.