Junhao Gan

Yixin Su, Yunxiang Zhao, Sarah Erfani et al.

Detecting beneficial feature interactions is essential in recommender systems, and existing approaches achieve this by examining all the possible feature interactions. However, the cost of examining all the possible higher-order feature interactions is prohibitive (exponentially growing with the order increasing). Hence existing approaches only detect limited order (e.g., combinations of up to four features) beneficial feature interactions, which may miss beneficial feature interactions with orders higher than the limitation. In this paper, we propose a hypergraph neural network based model named HIRS. HIRS is the first work that directly generates beneficial feature interactions of arbitrary orders and makes recommendation predictions accordingly. The number of generated feature interactions can be specified to be much smaller than the number of all the possible interactions and hence, our model admits a much lower running time. To achieve an effective algorithm, we exploit three properties of beneficial feature interactions, and propose deep-infomax-based methods to guide the interaction generation. Our experimental results show that HIRS outperforms state-of-the-art algorithms by up to 5% in terms of recommendation accuracy.

Junhao Gan, Xiao Sun, Seeun William Umboh

We consider the parametrized setting of the classical metrical service system (MSS) problem first studied by Bubeck and Rabani (APPROX/RANDOM 2020). In this setting, the adversary is restricted to a set of $m$ distinct request types, known to the algorithm in advance. The goal is to obtain competitive ratio bounds in terms of $m$. In this work, we make significant progress in understanding the landscape of parametrized MSS and resolve several open problems from Bubeck and Rabani. Our first main result is a tight bound for parametrized MSS on weighted stars. Previously, Bubeck and Rabani gave a randomized lower bound of $Ω(m)$ and deterministic upper bound of $O(2^m)$. We show that, surprisingly, a deterministic $O(m)$-competitive algorithm exists, matching the randomized lower bound. Our key insight is an interval covering formulation of MSS on weighted stars which enables an application of the primal-dual method. Our second main contribution is an improved lower bound construction for parametrized MSS on hierarchically separated trees (HSTs). Bubeck and Rabani's construction gave a $ω(1)$ lower bound when $m \geq 6$. Our improved lower bounds are tight for $2$-level HSTs and also rule out $O(1)$-competitive algorithms on HSTs when the parameter $m\geq 4$. We also complement these results by giving a deterministic $O(1)$-competitive algorithm on general metrics when $m=2$ while showing that it is impossible when $m\geq 3$.

Philip Cervenjak, Junhao Gan, Naonori Kakimura et al.

Connected Submodular Maximization (CSM) is a graph problem with important applications to wireless network deployment, path planning, epidemic outbreaks, and cancer genome studies. In CSM, we are given a graph $G$, a non-negative monotone submodular function $f$ on subsets of the vertex set of $G$, and an integer $k$. The goal is to select a tree in $G$, with $k$ edges, whose vertex set maximizes $f$. We also study the more general Directed and Directed Rooted variants of CSM (DCSM and DRCSM respectively). In both variants, $G$ is directed and the solution must be an out-tree in $G$, with $k$ edges, whose vertex set maximizes $f$; DRCSM further specifies a vertex to be the root of the selected out-tree. For CSM, several previous works have proposed polynomial time approximation algorithms; the state-of-the-art polynomial time algorithm achieves a $Ω(\frac{1}{\sqrt{k}})$-approximation. We can also parameterize the approximation factor by the radius of the optimal solution, denoted by $r$; the state-of-the-art polynomial time algorithm achieves a $Ω(\frac{1}{r})$-approximation. In this paper, we improve on the state-of-the-art approximation factor for CSM with respect to $r$ as well as $k$, noting that $r \leq k$. We propose a polynomial time framework that, for (Directed) CSM, achieves a $Ω(\frac{\varepsilon^{3}}{{r}^{\varepsilon}})$-approximation for every constant $\varepsilon \in (0, 1]$. For DRCSM, our framework achieves a $Ω(\frac{δ\varepsilon^{3}}{{r}^{\varepsilon}})$-approximation that violates the size constraint by at most a factor of $1 + δ$ for every $δ\in [\frac{1}{k}, 1]$. A key component of our framework is GreedyRadius, which is an algorithm for DRCSM that takes another algorithm with a bicriteria approximation factor in terms of $k$ and outputs a solution with the same bicriteria approximation factor (up to constants) in terms of $r$.

Yixin Su, Wei Jiang, Fangquan Lin et al.

In recommender systems, the patterns of user behaviors (e.g., purchase, click) may vary greatly in different contexts (e.g., time and location). This is because user behavior is jointly determined by two types of factors: intrinsic factors, which reflect consistent user preference, and extrinsic factors, which reflect external incentives that may vary in different contexts. Differentiating between intrinsic and extrinsic factors helps learn user behaviors better. However, existing studies have only considered differentiating them from a single, pre-defined context (e.g., time or location), ignoring the fact that a user's extrinsic factors may be influenced by the interplay of various contexts at the same time. In this paper, we propose the Intrinsic-Extrinsic Disentangled Recommendation (IEDR) model, a generic framework that differentiates intrinsic from extrinsic factors considering various contexts simultaneously, enabling more accurate differentiation of factors and hence the improvement of recommendation accuracy. IEDR contains a context-invariant contrastive learning component to capture intrinsic factors, and a disentanglement component to extract extrinsic factors under the interplay of various contexts. The two components work together to achieve effective factor learning. Extensive experiments on real-world datasets demonstrate IEDR's effectiveness in learning disentangled factors and significantly improving recommendation accuracy by up to 4% in NDCG.

Yuxiang Wang, Junhao Gan, Jianzhong Qi

Table Question Answering (TableQA) attracts strong interests due to the prevalence of web information presented in the form of semi-structured tables. Despite many efforts, TableQA over large tables remains an open challenge. This is because large tables may overwhelm models that try to comprehend them in full to locate question answers. Recent studies reduce input table size by decomposing tables into smaller, question-relevant sub-tables via generating programs to parse the tables. However, such solutions are subject to program generation and execution errors and are difficult to ensure decomposition quality. To address this issue, we propose TaDRe, a TableQA model that incorporates both pre- and post-table decomposition refinements to ensure table decomposition quality, hence achieving highly accurate TableQA results. To evaluate TaDRe, we construct two new large-table TableQA benchmarks via LLM-driven table expansion and QA pair generation. Extensive experiments on both the new and public benchmarks show that TaDRe achieves state-of-the-art performance on large-table TableQA tasks.