Showing 1–50 of 98 results for author: Gan, J

SeFi-CD: A Semantic First Change Detection Paradigm That Can Detect Any Change You Want

Authors: Ling Zhao, Zhenyang Huang, Dongsheng Kuang, Chengli Peng, Jun Gan, Haifeng Li

Abstract: The existing change detection(CD) methods can be summarized as the visual-first change detection (ViFi-CD) paradigm, which first extracts change features from visual differences and then assigns them specific semantic information. However, CD is essentially dependent on change regions of interest (CRoIs), meaning that the CD results are directly determined by the semantics changes of interest, mak… ▽ More The existing change detection(CD) methods can be summarized as the visual-first change detection (ViFi-CD) paradigm, which first extracts change features from visual differences and then assigns them specific semantic information. However, CD is essentially dependent on change regions of interest (CRoIs), meaning that the CD results are directly determined by the semantics changes of interest, making its primary image factor semantic of interest rather than visual. The ViFi-CD paradigm can only assign specific semantics of interest to specific change features extracted from visual differences, leading to the inevitable omission of potential CRoIs and the inability to adapt to different CRoI CD tasks. In other words, changes in other CRoIs cannot be detected by the ViFi-CD method without retraining the model or significantly modifying the method. This paper introduces a new CD paradigm, the semantic-first CD (SeFi-CD) paradigm. The core idea of SeFi-CD is to first perceive the dynamic semantics of interest and then visually search for change features related to the semantics. Based on the SeFi-CD paradigm, we designed Anything You Want Change Detection (AUWCD). Experiments on public datasets demonstrate that the AUWCD outperforms the current state-of-the-art CD methods, achieving an average F1 score 5.01\% higher than that of these advanced supervised baselines on the SECOND dataset, with a maximum increase of 13.17\%. The proposed SeFi-CD offers a novel CD perspective and approach. △ Less

Submitted 13 July, 2024; originally announced July 2024.

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound

Authors: Philip Cervenjak, Junhao Gan, Seeun William Umboh, Anthony Wirth

Abstract: We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of $n$ elements, a collection of $m$ subsets of this universe, and a cardinality constraint, $k$. The goal is to select a subcollection of at most $k$ sets that maximizes unique coverage, i.e, the number of elements contained in exactly one of the selected sets. The Max Unique Cove… ▽ More We consider the Max Unique Coverage problem, including applications to the data stream model. The input is a universe of $n$ elements, a collection of $m$ subsets of this universe, and a cardinality constraint, $k$. The goal is to select a subcollection of at most $k$ sets that maximizes unique coverage, i.e, the number of elements contained in exactly one of the selected sets. The Max Unique Coverage problem has applications in wireless networks, radio broadcast, and envy-free pricing. Our first main result is a fixed-parameter tractable approximation scheme (FPT-AS) for Max Unique Coverage, parameterized by $k$ and the maximum element frequency, $r$, which can be implemented on a data stream. Our FPT-AS finds a $(1-ε)$-approximation while maintaining a kernel of size $\tilde{O}(k r/ε)$, which can be combined with subsampling to use $\tilde{O}(k^2 r / ε^3)$ space overall. This significantly improves on the previous-best FPT-AS with the same approximation, but a kernel of size $\tilde{O}(k^2 r / ε^2)$. In order to achieve our result, we show upper bounds on the ratio of a collection's coverage to the unique coverage of a maximizing subcollection; this is by constructing explicit algorithms that find a subcollection with unique coverage at least a logarithmic ratio of the collection's coverage. We complement our algorithms with our second main result, showing that $Ω(m / k^2)$ space is necessary to achieve a $(1.5 + o(1))/(\ln k - 1)$-approximation in the data stream. This dramatically improves the previous-best lower bound showing that $Ω(m / k^2)$ is necessary to achieve better than a $e^{-1+1/k}$-approximation. △ Less

Submitted 12 July, 2024; originally announced July 2024.

Comments: 26 pages. Accepted into APPROX 2024

Cost-Effective RF Fingerprinting Based on Hybrid CVNN-RF Classifier with Automated Multi-Dimensional Early-Exit Strategy

Authors: Jiayan Gan, Zhixing Du, Qiang Li, Huaizong Shao, Jingran Lin, Ye Pan, Zhongyi Wen, Shafei Wang

Abstract: While the Internet of Things (IoT) technology is booming and offers huge opportunities for information exchange, it also faces unprecedented security challenges. As an important complement to the physical layer security technologies for IoT, radio frequency fingerprinting (RFF) is of great interest due to its difficulty in counterfeiting. Recently, many machine learning (ML)-based RFF algorithms h… ▽ More While the Internet of Things (IoT) technology is booming and offers huge opportunities for information exchange, it also faces unprecedented security challenges. As an important complement to the physical layer security technologies for IoT, radio frequency fingerprinting (RFF) is of great interest due to its difficulty in counterfeiting. Recently, many machine learning (ML)-based RFF algorithms have emerged. In particular, deep learning (DL) has shown great benefits in automatically extracting complex and subtle features from raw data with high classification accuracy. However, DL algorithms face the computational cost problem as the difficulty of the RFF task and the size of the DNN have increased dramatically. To address the above challenge, this paper proposes a novel costeffective early-exit neural network consisting of a complex-valued neural network (CVNN) backbone with multiple random forest branches, called hybrid CVNN-RF. Unlike conventional studies that use a single fixed DL model to process all RF samples, our hybrid CVNN-RF considers differences in the recognition difficulty of RF samples and introduces an early-exit mechanism to dynamically process the samples. When processing "easy" samples that can be well classified with high confidence, the hybrid CVNN-RF can end early at the random forest branch to reduce computational cost. Conversely, subsequent network layers will be activated to ensure accuracy. To further improve the early-exit rate, an automated multi-dimensional early-exit strategy is proposed to achieve scheduling control from multiple dimensions within the network depth and classification category. Finally, our experiments on the public ADS-B dataset show that the proposed algorithm can reduce the computational cost by 83% while improving the accuracy by 1.6% under a classification task with 100 categories. △ Less

Submitted 21 June, 2024; originally announced June 2024.

Comments: Accepted by IEEE Internet of Things Journal

CLIP-Driven Cloth-Agnostic Feature Learning for Cloth-Changing Person Re-Identification

Authors: Shuang Li, Jiaxu Leng, Guozhang Li, Ji Gan, Haosheng chen, Xinbo Gao

Abstract: Contrastive Language-Image Pre-Training (CLIP) has shown impressive performance in short-term Person Re-Identification (ReID) due to its ability to extract high-level semantic features of pedestrians, yet its direct application to Cloth-Changing Person Re-Identification (CC-ReID) faces challenges due to CLIP's image encoder overly focusing on clothes clues. To address this, we propose a novel fram… ▽ More Contrastive Language-Image Pre-Training (CLIP) has shown impressive performance in short-term Person Re-Identification (ReID) due to its ability to extract high-level semantic features of pedestrians, yet its direct application to Cloth-Changing Person Re-Identification (CC-ReID) faces challenges due to CLIP's image encoder overly focusing on clothes clues. To address this, we propose a novel framework called CLIP-Driven Cloth-Agnostic Feature Learning (CCAF) for CC-ReID. Accordingly, two modules were custom-designed: the Invariant Feature Prompting (IFP) and the Clothes Feature Minimization (CFM). These modules guide the model to extract cloth-agnostic features positively and attenuate clothes-related features negatively. Specifically, IFP is designed to extract fine-grained semantic features unrelated to clothes from the raw image, guided by the cloth-agnostic text prompts. This module first covers the clothes in the raw image at the pixel level to obtain the shielding image and then utilizes CLIP's knowledge to generate cloth-agnostic text prompts. Subsequently, it aligns the raw image-text and the raw image-shielding image in the feature space, emphasizing discriminative clues related to identity but unrelated to clothes. Furthermore, CFM is designed to examine and weaken the image encoder's ability to extract clothes features. It first generates text prompts corresponding to clothes pixels. Then, guided by these clothes text prompts, it iteratively examines and disentangles clothes features from pedestrian features, ultimately retaining inherent discriminative features. Extensive experiments have demonstrated the effectiveness of the proposed CCAF, achieving new state-of-the-art performance on several popular CC-ReID benchmarks without any additional inference time. △ Less

Submitted 13 June, 2024; originally announced June 2024.

Efflex: Efficient and Flexible Pipeline for Spatio-Temporal Trajectory Graph Modeling and Representation Learning

Authors: Ming Cheng, Ziyi Zhou, Bowen Zhang, Ziyu Wang, Jiaqi Gan, Ziang Ren, Weiqi Feng, Yi Lyu, Hefan Zhang, Xingjian Diao

Abstract: In the landscape of spatio-temporal data analytics, effective trajectory representation learning is paramount. To bridge the gap of learning accurate representations with efficient and flexible mechanisms, we introduce Efflex, a comprehensive pipeline for transformative graph modeling and representation learning of the large-volume spatio-temporal trajectories. Efflex pioneers the incorporation of… ▽ More In the landscape of spatio-temporal data analytics, effective trajectory representation learning is paramount. To bridge the gap of learning accurate representations with efficient and flexible mechanisms, we introduce Efflex, a comprehensive pipeline for transformative graph modeling and representation learning of the large-volume spatio-temporal trajectories. Efflex pioneers the incorporation of a multi-scale k-nearest neighbors (KNN) algorithm with feature fusion for graph construction, marking a leap in dimensionality reduction techniques by preserving essential data features. Moreover, the groundbreaking graph construction mechanism and the high-performance lightweight GCN increase embedding extraction speed by up to 36 times faster. We further offer Efflex in two versions, Efflex-L for scenarios demanding high accuracy, and Efflex-B for environments requiring swift data processing. Comprehensive experimentation with the Porto and Geolife datasets validates our approach, positioning Efflex as the state-of-the-art in the domain. Such enhancements in speed and accuracy highlight the versatility of Efflex, underscoring its wide-ranging potential for deployment in time-sensitive and computationally constrained applications. △ Less

Submitted 15 April, 2024; originally announced April 2024.

CFPL-FAS: Class Free Prompt Learning for Generalizable Face Anti-spoofing

Authors: Ajian Liu, Shuai Xue, Jianwen Gan, Jun Wan, Yanyan Liang, Jiankang Deng, Sergio Escalera, Zhen Lei

Abstract: Domain generalization (DG) based Face Anti-Spoofing (FAS) aims to improve the model's performance on unseen domains. Existing methods either rely on domain labels to align domain-invariant feature spaces, or disentangle generalizable features from the whole sample, which inevitably lead to the distortion of semantic feature structures and achieve limited generalization. In this work, we make use o… ▽ More Domain generalization (DG) based Face Anti-Spoofing (FAS) aims to improve the model's performance on unseen domains. Existing methods either rely on domain labels to align domain-invariant feature spaces, or disentangle generalizable features from the whole sample, which inevitably lead to the distortion of semantic feature structures and achieve limited generalization. In this work, we make use of large-scale VLMs like CLIP and leverage the textual feature to dynamically adjust the classifier's weights for exploring generalizable visual features. Specifically, we propose a novel Class Free Prompt Learning (CFPL) paradigm for DG FAS, which utilizes two lightweight transformers, namely Content Q-Former (CQF) and Style Q-Former (SQF), to learn the different semantic prompts conditioned on content and style features by using a set of learnable query vectors, respectively. Thus, the generalizable prompt can be learned by two improvements: (1) A Prompt-Text Matched (PTM) supervision is introduced to ensure CQF learns visual representation that is most informative of the content description. (2) A Diversified Style Prompt (DSP) technology is proposed to diversify the learning of style prompts by mixing feature statistics between instance-specific styles. Finally, the learned text features modulate visual features to generalization through the designed Prompt Modulation (PM). Extensive experiments show that the CFPL is effective and outperforms the state-of-the-art methods on several cross-domain datasets. △ Less

Submitted 21 March, 2024; originally announced March 2024.

Comments: 11 pages, 4 figures

Fast Parallel Algorithms for Submodular $p$-Superseparable Maximization

Authors: Philip Cervenjak, Junhao Gan, Anthony Wirth

Abstract: Maximizing a non-negative, monontone, submodular function $f$ over $n$ elements under a cardinality constraint $k$ (SMCC) is a well-studied NP-hard problem. It has important applications in, e.g., machine learning and influence maximization. Though the theoretical problem admits polynomial-time approximation algorithms, solving it in practice often involves frequently querying submodular functions… ▽ More Maximizing a non-negative, monontone, submodular function $f$ over $n$ elements under a cardinality constraint $k$ (SMCC) is a well-studied NP-hard problem. It has important applications in, e.g., machine learning and influence maximization. Though the theoretical problem admits polynomial-time approximation algorithms, solving it in practice often involves frequently querying submodular functions that are expensive to compute. This has motivated significant research into designing parallel approximation algorithms in the adaptive complexity model; adaptive complexity (adaptivity) measures the number of sequential rounds of $\text{poly}(n)$ function queries an algorithm requires. The state-of-the-art algorithms can achieve $(1-\frac{1}{e}-\varepsilon)$-approximate solutions with $O(\frac{1}{\varepsilon^2}\log n)$ adaptivity, which approaches the known adaptivity lower-bounds. However, the $O(\frac{1}{\varepsilon^2} \log n)$ adaptivity only applies to maximizing worst-case functions that are unlikely to appear in practice. Thus, in this paper, we consider the special class of $p$-superseparable submodular functions, which places a reasonable constraint on $f$, based on the parameter $p$, and is more amenable to maximization, while also having real-world applicability. Our main contribution is the algorithm LS+GS, a finer-grained version of the existing LS+PGB algorithm, designed for instances of SMCC when $f$ is $p$-superseparable; it achieves an expected $(1-\frac{1}{e}-\varepsilon)$-approximate solution with $O(\frac{1}{\varepsilon^2}\log(p k))$ adaptivity independent of $n$. Additionally, unrelated to $p$-superseparability, our LS+GS algorithm uses only $O(\frac{n}{\varepsilon} + \frac{\log n}{\varepsilon^2})$ oracle queries, which has an improved dependence on $\varepsilon^{-1}$ over the state-of-the-art LS+PGB; this is achieved through the design of a novel thresholding subroutine. △ Less

Submitted 2 February, 2024; v1 submitted 21 November, 2023; originally announced November 2023.

Comments: 36 pages. To be published in Approximation and Online Algorithms (Proceedings of the 21st International Workshop, WAOA 2023)

Journal ref: Approximation and Online Algorithms, vol. 14297, p. 219. Springer Nature, 2023

PT-Tuning: Bridging the Gap between Time Series Masked Reconstruction and Forecasting via Prompt Token Tuning

Authors: Hao Liu, Jinrui Gan, Xiaoxuan Fan, Yi Zhang, Chuanxian Luo, Jing Zhang, Guangxin Jiang, Yucheng Qian, Changwei Zhao, Huan Ma, Zhenyu Guo

Abstract: Self-supervised learning has been actively studied in time series domain recently, especially for masked reconstruction. Most of these methods follow the "Pre-training + Fine-tuning" paradigm in which a new decoder replaces the pre-trained decoder to fit for a specific downstream task, leading to inconsistency of upstream and downstream tasks. In this paper, we first point out that the unification… ▽ More Self-supervised learning has been actively studied in time series domain recently, especially for masked reconstruction. Most of these methods follow the "Pre-training + Fine-tuning" paradigm in which a new decoder replaces the pre-trained decoder to fit for a specific downstream task, leading to inconsistency of upstream and downstream tasks. In this paper, we first point out that the unification of task objectives and adaptation for task difficulty are critical for bridging the gap between time series masked reconstruction and forecasting. By reserving the pre-trained mask token during fine-tuning stage, the forecasting task can be taken as a special case of masked reconstruction, where the future values are masked and reconstructed based on history values. It guarantees the consistency of task objectives but there is still a gap in task difficulty. Because masked reconstruction can utilize contextual information while forecasting can only use historical information to reconstruct. To further mitigate the existed gap, we propose a simple yet effective prompt token tuning (PT-Tuning) paradigm, in which all pre-trained parameters are frozen and only a few trainable prompt tokens are added to extended mask tokens in element-wise manner. Extensive experiments on real-world datasets demonstrate the superiority of our proposed paradigm with state-of-the-art performance compared to representation learning and end-to-end supervised forecasting methods. △ Less

Submitted 7 November, 2023; originally announced November 2023.

Shape-centered Representation Learning for Visible-Infrared Person Re-identification

Authors: Shuang Li, Jiaxu Leng, Ji Gan, Mengjingcheng Mo, Xinbo Gao

Abstract: Current Visible-Infrared Person Re-Identification (VI-ReID) methods prioritize extracting distinguishing appearance features, ignoring the natural resistance of body shape against modality changes. Initially, we gauged the discriminative potential of shapes by a straightforward concatenation of shape and appearance features. However, two unresolved issues persist in the utilization of shape featur… ▽ More Current Visible-Infrared Person Re-Identification (VI-ReID) methods prioritize extracting distinguishing appearance features, ignoring the natural resistance of body shape against modality changes. Initially, we gauged the discriminative potential of shapes by a straightforward concatenation of shape and appearance features. However, two unresolved issues persist in the utilization of shape features. One pertains to the dependence on auxiliary models for shape feature extraction in the inference phase, along with the errors in generated infrared shapes due to the intrinsic modality disparity. The other issue involves the inadequately explored correlation between shape and appearance features. To tackle the aforementioned challenges, we propose the Shape-centered Representation Learning framework (ScRL), which focuses on learning shape features and appearance features associated with shapes. Specifically, we devise the Shape Feature Propagation (SFP), facilitating direct extraction of shape features from original images with minimal complexity costs during inference. To restitute inaccuracies in infrared body shapes at the feature level, we present the Infrared Shape Restitution (ISR). Furthermore, to acquire appearance features related to shape, we design the Appearance Feature Enhancement (AFE), which accentuates identity-related features while suppressing identity-unrelated features guided by shape features. Extensive experiments are conducted to validate the effectiveness of the proposed ScRL. Achieving remarkable results, the Rank-1 (mAP) accuracy attains 76.1%, 71.2%, 92.4% (72.6%, 52.9%, 86.7%) on the SYSU-MM01, HITSZ-VCM, RegDB datasets respectively, outperforming existing state-of-the-art methods. △ Less

Submitted 29 October, 2023; v1 submitted 27 October, 2023; originally announced October 2023.

Ranking-based Adaptive Query Generation for DETRs in Crowded Pedestrian Detection

Authors: Feng Gao, Jiaxu Leng, Ji Gan, Xinbo Gao

Abstract: DEtection TRansformer (DETR) and its variants (DETRs) have been successfully applied to crowded pedestrian detection, which achieved promising performance. However, we find that, in different degrees of crowded scenes, the number of DETRs' queries must be adjusted manually, otherwise, the performance would degrade to varying degrees. In this paper, we first analyze the two current query generation… ▽ More DEtection TRansformer (DETR) and its variants (DETRs) have been successfully applied to crowded pedestrian detection, which achieved promising performance. However, we find that, in different degrees of crowded scenes, the number of DETRs' queries must be adjusted manually, otherwise, the performance would degrade to varying degrees. In this paper, we first analyze the two current query generation methods and summarize four guidelines for designing the adaptive query generation method. Then, we propose Rank-based Adaptive Query Generation (RAQG) to alleviate the problem. Specifically, we design a rank prediction head that can predict the rank of the lowest confidence positive training sample produced by the encoder. Based on the predicted rank, we design an adaptive selection method that can adaptively select coarse detection results produced by the encoder to generate queries. Moreover, to train the rank prediction head better, we propose Soft Gradient L1 Loss. The gradient of Soft Gradient L1 Loss is continuous, which can describe the relationship between the loss value and the updated value of model parameters granularly. Our method is simple and effective, which can be plugged into any DETRs to make it query-adaptive in theory. The experimental results on Crowdhuman dataset and Citypersons dataset show that our method can adaptively generate queries for DETRs and achieve competitive results. Especially, our method achieves state-of-the-art 39.4% MR on Crowdhuman dataset. △ Less

Submitted 8 January, 2024; v1 submitted 24 October, 2023; originally announced October 2023.

Comments: 10 pages, 6 figures

Open-Set Knowledge-Based Visual Question Answering with Inference Paths

Authors: Jingru Gan, Xinzhe Han, Shuhui Wang, Qingming Huang

Abstract: Given an image and an associated textual question, the purpose of Knowledge-Based Visual Question Answering (KB-VQA) is to provide a correct answer to the question with the aid of external knowledge bases. Prior KB-VQA models are usually formulated as a retriever-classifier framework, where a pre-trained retriever extracts textual or visual information from knowledge graphs and then makes a predic… ▽ More Given an image and an associated textual question, the purpose of Knowledge-Based Visual Question Answering (KB-VQA) is to provide a correct answer to the question with the aid of external knowledge bases. Prior KB-VQA models are usually formulated as a retriever-classifier framework, where a pre-trained retriever extracts textual or visual information from knowledge graphs and then makes a prediction among the candidates. Despite promising progress, there are two drawbacks with existing models. Firstly, modeling question-answering as multi-class classification limits the answer space to a preset corpus and lacks the ability of flexible reasoning. Secondly, the classifier merely consider "what is the answer" without "how to get the answer", which cannot ground the answer to explicit reasoning paths. In this paper, we confront the challenge of \emph{explainable open-set} KB-VQA, where the system is required to answer questions with entities at wild and retain an explainable reasoning path. To resolve the aforementioned issues, we propose a new retriever-ranker paradigm of KB-VQA, Graph pATH rankER (GATHER for brevity). Specifically, it contains graph constructing, pruning, and path-level ranking, which not only retrieves accurate answers but also provides inference paths that explain the reasoning process. To comprehensively evaluate our model, we reformulate the benchmark dataset OK-VQA with manually corrected entity-level annotations and release it as ConceptVQA. Extensive experiments on real-world questions demonstrate that our framework is not only able to perform open-set question answering across the whole knowledge base but provide explicit reasoning path. △ Less

Submitted 12 October, 2023; originally announced October 2023.

Spiking-Diffusion: Vector Quantized Discrete Diffusion Model with Spiking Neural Networks

Authors: Mingxuan Liu, Jie Gan, Rui Wen, Tao Li, Yongli Chen, Hong Chen

Abstract: Spiking neural networks (SNNs) have tremendous potential for energy-efficient neuromorphic chips due to their binary and event-driven architecture. SNNs have been primarily used in classification tasks, but limited exploration on image generation tasks. To fill the gap, we propose a Spiking-Diffusion model, which is based on the vector quantized discrete diffusion model. First, we develop a vector… ▽ More Spiking neural networks (SNNs) have tremendous potential for energy-efficient neuromorphic chips due to their binary and event-driven architecture. SNNs have been primarily used in classification tasks, but limited exploration on image generation tasks. To fill the gap, we propose a Spiking-Diffusion model, which is based on the vector quantized discrete diffusion model. First, we develop a vector quantized variational autoencoder with SNNs (VQ-SVAE) to learn a discrete latent space for images. In VQ-SVAE, image features are encoded using both the spike firing rate and postsynaptic potential, and an adaptive spike generator is designed to restore embedding features in the form of spike trains. Next, we perform absorbing state diffusion in the discrete latent space and construct a spiking diffusion image decoder (SDID) with SNNs to denoise the image. Our work is the first to build the diffusion model entirely from SNN layers. Experimental results on MNIST, FMNIST, KMNIST, Letters, and Cifar10 demonstrate that Spiking-Diffusion outperforms the existing SNN-based generation model. We achieve FIDs of 37.50, 91.98, 59.23, 67.41, and 120.5 on the above datasets respectively, with reductions of 58.60\%, 18.75\%, 64.51\%, 29.75\%, and 44.88\% in FIDs compared with the state-of-art work. Our code will be available at \url{https://github.com/Arktis2022/Spiking-Diffusion}. △ Less

Submitted 21 September, 2023; v1 submitted 20 August, 2023; originally announced August 2023.

Comments: Under Review

Markov Decision Processes with Time-Varying Geometric Discounting

Authors: Jiarui Gan, Annika Hennes, Rupak Majumdar, Debmalya Mandal, Goran Radanovic

Abstract: Canonical models of Markov decision processes (MDPs) usually consider geometric discounting based on a constant discount factor. While this standard modeling approach has led to many elegant results, some recent studies indicate the necessity of modeling time-varying discounting in certain applications. This paper studies a model of infinite-horizon MDPs with time-varying discount factors. We take… ▽ More Canonical models of Markov decision processes (MDPs) usually consider geometric discounting based on a constant discount factor. While this standard modeling approach has led to many elegant results, some recent studies indicate the necessity of modeling time-varying discounting in certain applications. This paper studies a model of infinite-horizon MDPs with time-varying discount factors. We take a game-theoretic perspective -- whereby each time step is treated as an independent decision maker with their own (fixed) discount factor -- and we study the subgame perfect equilibrium (SPE) of the resulting game as well as the related algorithmic problems. We present a constructive proof of the existence of an SPE and demonstrate the EXPTIME-hardness of computing an SPE. We also turn to the approximate notion of $ε$-SPE and show that an $ε$-SPE exists under milder assumptions. An algorithm is presented to compute an $ε$-SPE, of which an upper bound of the time complexity, as a function of the convergence property of the time-varying discount factor, is provided. △ Less

Submitted 19 July, 2023; originally announced July 2023.

Comments: 24 pages, 3 figures

Journal ref: Proceedings of the AAAI Conference on Artificial Intelligence 37(10) (2023) 11980-11988

High-order Compact Gas-kinetic Scheme for Two-layer Shallow Water Equations on Unstructured Mesh

Authors: Fengxiang Zhao, Jianping Gan, Kun Xu

Abstract: For the two-layer shallow water equations, a high-order compact gas-kinetic scheme (GKS) on triangular mesh is proposed. The two-layer shallow water equations have complex source terms in comparison with the single layer equations. The main focus of this study is to construct a time-accurate evolution solution at a cell interface and to design a well-balanced scheme. The evolution model at a cell… ▽ More For the two-layer shallow water equations, a high-order compact gas-kinetic scheme (GKS) on triangular mesh is proposed. The two-layer shallow water equations have complex source terms in comparison with the single layer equations. The main focus of this study is to construct a time-accurate evolution solution at a cell interface and to design a well-balanced scheme. The evolution model at a cell interface provides not only the numerical fluxes, but also the flow variables. The time-dependent flow variables at the closed cell interfaces can be used to update the cell-averaged gradients for the discretization of the the source terms inside each control volume in the development of the well-balanced scheme. Based on the cell-averaged flow variable and their gradients, high-order initial data reconstruction can be achieved with compact stencils. The compact high-order GKS has advantages to simulate the flow evolution in complex domain covered by unstructured mesh. Many test cases are used to validate the accuracy and robustness of the scheme for the two-layer shallow water equations. △ Less

Submitted 7 June, 2023; originally announced June 2023.

Sequential Principal-Agent Problems with Communication: Efficient Computation and Learning

Authors: Jiarui Gan, Rupak Majumdar, Debmalya Mandal, Goran Radanovic

Abstract: We study a sequential decision making problem between a principal and an agent with incomplete information on both sides. In this model, the principal and the agent interact in a stochastic environment, and each is privy to observations about the state not available to the other. The principal has the power of commitment, both to elicit information from the agent and to provide signals about her o… ▽ More We study a sequential decision making problem between a principal and an agent with incomplete information on both sides. In this model, the principal and the agent interact in a stochastic environment, and each is privy to observations about the state not available to the other. The principal has the power of commitment, both to elicit information from the agent and to provide signals about her own information. The principal and the agent communicate their signals to each other, and select their actions independently based on this communication. Each player receives a payoff based on the state and their joint actions, and the environment moves to a new state. The interaction continues over a finite time horizon, and both players act to optimize their own total payoffs over the horizon. Our model encompasses as special cases stochastic games of incomplete information and POMDPs, as well as sequential Bayesian persuasion and mechanism design problems. We study both computation of optimal policies and learning in our setting. While the general problems are computationally intractable, we study algorithmic solutions under a conditional independence assumption on the underlying state-observation distributions. We present a polynomial-time algorithm to compute the principal's optimal policy up to an additive approximation. Additionally, we show an efficient learning algorithm in the case where the transition probabilities are not known beforehand. The algorithm guarantees sublinear regret for both players. △ Less

Submitted 17 December, 2023; v1 submitted 6 June, 2023; originally announced June 2023.

Robust Stackelberg Equilibria

Authors: Jiarui Gan, Minbiao Han, Jibang Wu, Haifeng Xu

Abstract: This paper provides a systematic study of the robust Stackelberg equilibrium (RSE), which naturally generalizes the widely adopted solution concept of the strong Stackelberg equilibrium (SSE). The RSE accounts for any possible up-to-$δ$ suboptimal follower responses in Stackelberg games and is adopted to improve the robustness of the leader's strategy. While a few variants of robust Stackelberg eq… ▽ More This paper provides a systematic study of the robust Stackelberg equilibrium (RSE), which naturally generalizes the widely adopted solution concept of the strong Stackelberg equilibrium (SSE). The RSE accounts for any possible up-to-$δ$ suboptimal follower responses in Stackelberg games and is adopted to improve the robustness of the leader's strategy. While a few variants of robust Stackelberg equilibrium have been considered in previous literature, the RSE solution concept we consider is importantly different -- in some sense, it relaxes previously studied robust Stackelberg strategies and is applicable to much broader sources of uncertainties. We provide a thorough investigation of several fundamental properties of RSE, including its utility guarantees, algorithmics, and learnability. We first show that the RSE we defined always exists and thus is well-defined. Then we characterize how the leader's utility in RSE changes with the robustness level considered. On the algorithmic side, we show that, in sharp contrast to the tractability of computing an SSE, it is NP-hard to obtain a fully polynomial approximation scheme (FPTAS) for any constant robustness level. Nevertheless, we develop a quasi-polynomial approximation scheme (QPTAS) for RSE. Finally, we examine the learnability of the RSE in a natural learning scenario, where both players' utilities are not known in advance, and provide almost tight sample complexity results on learning the RSE. As a corollary of this result, we also obtain an algorithm for learning SSE, which strictly improves a key result of Bai et al. in terms of both utility guarantee and computational efficiency. △ Less

Submitted 30 October, 2023; v1 submitted 28 April, 2023; originally announced April 2023.

Real-time Multi-person Eyeblink Detection in the Wild for Untrimmed Video

Authors: Wenzheng Zeng, Yang Xiao, Sicheng Wei, Jinfang Gan, Xintao Zhang, Zhiguo Cao, Zhiwen Fang, Joey Tianyi Zhou

Abstract: Real-time eyeblink detection in the wild can widely serve for fatigue detection, face anti-spoofing, emotion analysis, etc. The existing research efforts generally focus on single-person cases towards trimmed video. However, multi-person scenario within untrimmed videos is also important for practical applications, which has not been well concerned yet. To address this, we shed light on this resea… ▽ More Real-time eyeblink detection in the wild can widely serve for fatigue detection, face anti-spoofing, emotion analysis, etc. The existing research efforts generally focus on single-person cases towards trimmed video. However, multi-person scenario within untrimmed videos is also important for practical applications, which has not been well concerned yet. To address this, we shed light on this research field for the first time with essential contributions on dataset, theory, and practices. In particular, a large-scale dataset termed MPEblink that involves 686 untrimmed videos with 8748 eyeblink events is proposed under multi-person conditions. The samples are captured from unconstrained films to reveal "in the wild" characteristics. Meanwhile, a real-time multi-person eyeblink detection method is also proposed. Being different from the existing counterparts, our proposition runs in a one-stage spatio-temporal way with end-to-end learning capacity. Specifically, it simultaneously addresses the sub-tasks of face detection, face tracking, and human instance-level eyeblink detection. This paradigm holds 2 main advantages: (1) eyeblink features can be facilitated via the face's global context (e.g., head pose and illumination condition) with joint optimization and interaction, and (2) addressing these sub-tasks in parallel instead of sequential manner can save time remarkably to meet the real-time running requirement. Experiments on MPEblink verify the essential challenges of real-time multi-person eyeblink detection in the wild for untrimmed video. Our method also outperforms existing approaches by large margins and with a high inference speed. △ Less

Submitted 21 August, 2023; v1 submitted 28 March, 2023; originally announced March 2023.

Comments: Accepted by CVPR 2023

DS-TDNN: Dual-stream Time-delay Neural Network with Global-aware Filter for Speaker Verification

Authors: Yangfu Li, Jiapan Gan, Xiaodan Lin

Abstract: Conventional time-delay neural networks (TDNNs) struggle to handle long-range context, their ability to represent speaker information is therefore limited in long utterances. Existing solutions either depend on increasing model complexity or try to balance between local features and global context to address this issue. To effectively leverage the long-term dependencies of audio signals and constr… ▽ More Conventional time-delay neural networks (TDNNs) struggle to handle long-range context, their ability to represent speaker information is therefore limited in long utterances. Existing solutions either depend on increasing model complexity or try to balance between local features and global context to address this issue. To effectively leverage the long-term dependencies of audio signals and constrain model complexity, we introduce a novel module called Global-aware Filter layer (GF layer) in this work, which employs a set of learnable transform-domain filters between a 1D discrete Fourier transform and its inverse transform to capture global context. Additionally, we develop a dynamic filtering strategy and a sparse regularization method to enhance the performance of the GF layer and prevent overfitting. Based on the GF layer, we present a dual-stream TDNN architecture called DS-TDNN for automatic speaker verification (ASV), which utilizes two unique branches to extract both local and global features in parallel and employs an efficient strategy to fuse different-scale information. Experiments on the Voxceleb and SITW databases demonstrate that the DS-TDNN achieves a relative improvement of 10\% together with a relative decline of 20\% in computational cost over the ECAPA-TDNN in speaker verification task. This improvement will become more evident as the utterance's duration grows. Furthermore, the DS-TDNN also beats popular deep residual models and attention-based systems on utterances of arbitrary length. △ Less

Submitted 1 August, 2023; v1 submitted 20 March, 2023; originally announced March 2023.

Comments: 13 pages 4 figures

MSC Class: 68 ACM Class: I.2.1

k-Prize Weighted Voting Games

Authors: Wei-Chen Lee, David Hyland, Alessandro Abate, Edith Elkind, Jiarui Gan, Julian Gutierrez, Paul Harrenstein, Michael Wooldridge

Abstract: We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts… ▽ More We introduce a natural variant of weighted voting games, which we refer to as k-Prize Weighted Voting Games. Such games consist of n players with weights, and k prizes, of possibly differing values. The players form coalitions, and the i-th largest coalition (by the sum of weights of its members) wins the i-th largest prize, which is then shared among its members. We present four solution concepts to analyse the games in this class, and characterise the existence of stable outcomes in games with three players and two prizes, and in games with uniform prizes. We then explore the efficiency of stable outcomes in terms of Pareto optimality and utilitarian social welfare. Finally, we study the computational complexity of finding stable outcomes. △ Less

Submitted 2 March, 2023; v1 submitted 27 February, 2023; originally announced February 2023.

Comments: Accepted to AAMAS 2023

Learning to Manipulate a Commitment Optimizer

Authors: Yurong Chen, Xiaotie Deng, Jiarui Gan, Yuhao Li

Abstract: It is shown in recent studies that in a Stackelberg game the follower can manipulate the leader by deviating from their true best-response behavior. Such manipulations are computationally tractable and can be highly beneficial for the follower. Meanwhile, they may result in significant payoff losses for the leader, sometimes completely defeating their first-mover advantage. A warning to commitment… ▽ More It is shown in recent studies that in a Stackelberg game the follower can manipulate the leader by deviating from their true best-response behavior. Such manipulations are computationally tractable and can be highly beneficial for the follower. Meanwhile, they may result in significant payoff losses for the leader, sometimes completely defeating their first-mover advantage. A warning to commitment optimizers, the risk these findings indicate appears to be alleviated to some extent by a strict information advantage the manipulations rely on. That is, the follower knows the full information about both players' payoffs whereas the leader only knows their own payoffs. In this paper, we study the manipulation problem with this information advantage relaxed. We consider the scenario where the follower is not given any information about the leader's payoffs to begin with but has to learn to manipulate by interacting with the leader. The follower can gather necessary information by querying the leader's optimal commitments against contrived best-response behaviors. Our results indicate that the information advantage is not entirely indispensable to the follower's manipulations: the follower can learn the optimal way to manipulate in polynomial time with polynomially many queries of the leader's optimal commitment. △ Less

Submitted 26 February, 2023; v1 submitted 23 February, 2023; originally announced February 2023.

Fair $k$-Center: a Coreset Approach in Low Dimensions

Authors: Jinxiang Gan, Mordecai Golin, Zonghan Yang, Yuhao Zhang

Abstract: Center-based clustering techniques are fundamental in some areas of machine learning such as data summarization. Generic $k$-center algorithms can produce biased cluster representatives so there has been a recent interest in fair $k$-center clustering. Our main theoretical contributions are two new $(3+ε)$-approximation algorithms for solving the fair $k$-center problem in (1) the dynamic incremen… ▽ More Center-based clustering techniques are fundamental in some areas of machine learning such as data summarization. Generic $k$-center algorithms can produce biased cluster representatives so there has been a recent interest in fair $k$-center clustering. Our main theoretical contributions are two new $(3+ε)$-approximation algorithms for solving the fair $k$-center problem in (1) the dynamic incremental, i.e., one-pass streaming, model and (2) the MapReduce model. Our dynamic incremental algorithm is the first such algorithm for this problem (previous streaming algorithms required two passes) and our MapReduce one improves upon the previous approximation factor of $(17+ε).$ Both algorithms work by maintaining a small coreset to represent the full point set and their analysis requires that the underlying metric has finite-doubling dimension. We also provide related heuristics for higher dimensional data and experimental results that compare the performance of our algorithms to existing ones. △ Less

Submitted 20 February, 2023; originally announced February 2023.

Fully Dynamic $k$-Center in Low Dimensions via Approximate Furthest Neighbors

Authors: Jinxiang Gan, Mordecai Jay Golin

Abstract: Let $P$ be a set of points in some metric space. The approximate furthest neighbor problem is, given a second point set $C,$ to find a point $p \in P$ that is a $(1+ε)$ approximate furthest neighbor from $C.$ The dynamic version is to maintain $P,$ over insertions and deletions of points, in a way that permits efficiently solving the approximate furthest neighbor problem for the current $P.$ We… ▽ More Let $P$ be a set of points in some metric space. The approximate furthest neighbor problem is, given a second point set $C,$ to find a point $p \in P$ that is a $(1+ε)$ approximate furthest neighbor from $C.$ The dynamic version is to maintain $P,$ over insertions and deletions of points, in a way that permits efficiently solving the approximate furthest neighbor problem for the current $P.$ We provide the first algorithm for solving this problem in metric spaces with finite doubling dimension. Our algorithm is built on top of the navigating net data-structure. An immediate application is two new algorithms for solving the dynamic $k$-center problem. The first dynamically maintains $(2+ε)$ approximate $k$-centers in general metric spaces with bounded doubling dimension and the second maintains $(1+ε)$ approximate Euclidean $k$-centers. Both these dynamic algorithms work by starting with a known corresponding static algorithm for solving approximate $k$-center, and replacing the static exact furthest neighbor subroutine used by that algorithm with our new dynamic approximate furthest neighbor one. Unlike previous algorithms for dynamic $k$-center with those same approximation ratios, our new ones do not require knowing $k$ or $ε$ in advance. In the Euclidean case, our algorithm also seems to be the first deterministic solution. △ Less

Submitted 19 February, 2023; originally announced February 2023.

Online Reinforcement Learning with Uncertain Episode Lengths

Authors: Debmalya Mandal, Goran Radanovic, Jiarui Gan, Adish Singla, Rupak Majumdar

Abstract: Existing episodic reinforcement algorithms assume that the length of an episode is fixed across time and known a priori. In this paper, we consider a general framework of episodic reinforcement learning when the length of each episode is drawn from a distribution. We first establish that this problem is equivalent to online reinforcement learning with general discounting where the learner is tryin… ▽ More Existing episodic reinforcement algorithms assume that the length of an episode is fixed across time and known a priori. In this paper, we consider a general framework of episodic reinforcement learning when the length of each episode is drawn from a distribution. We first establish that this problem is equivalent to online reinforcement learning with general discounting where the learner is trying to optimize the expected discounted sum of rewards over an infinite horizon, but where the discounting function is not necessarily geometric. We show that minimizing regret with this new general discounting is equivalent to minimizing regret with uncertain episode lengths. We then design a reinforcement learning algorithm that minimizes regret with general discounting but acts for the setting with uncertain episode lengths. We instantiate our general bound for different types of discounting, including geometric and polynomial discounting. We also show that we can obtain similar regret bounds even when the uncertainty over the episode lengths is unknown, by estimating the unknown distribution over time. Finally, we compare our learning algorithms with existing value-iteration based episodic RL algorithms in a grid-world environment. △ Less

Submitted 7 February, 2023; originally announced February 2023.

Comments: To appear at AAAI-2023

Generalized Principal-Agency: Contracts, Information, Games and Beyond

Authors: Jiarui Gan, Minbiao Han, Jibang Wu, Haifeng Xu

Abstract: In the principal-agent problem formulated by Myerson'82, agents have private information (type) and make private decisions (action), both of which are unobservable to the principal. Myerson pointed out an elegant linear programming solution that relies on the revelation principle. This paper extends Myerson's results to a more general setting where the principal's action space can be infinite and… ▽ More In the principal-agent problem formulated by Myerson'82, agents have private information (type) and make private decisions (action), both of which are unobservable to the principal. Myerson pointed out an elegant linear programming solution that relies on the revelation principle. This paper extends Myerson's results to a more general setting where the principal's action space can be infinite and subject to additional design constraints. Our generalized principal-agent model unifies several important design problems including contract design, information design, and Bayesian Stackelberg games, and encompasses them as special cases. We first extend the revelation principle to this general model, based on which a polynomial-time algorithm is then derived for computing the optimal mechanism for the principal. This algorithm not only implies new efficient solutions simultaneously for all the aforementioned special cases but also significantly simplifies previously known algorithms designed for special cases. Inspired by the recent interest in the algorithmic design of a single contract and menu of contracts, we study such constrained design problems to our general principal-agent model. In contrast to the above unification, our results here illustrate the other facet of diversity among different principal-agent design problems and demonstrate how their different structures can lead to different complexities: some are tractable whereas others are APX-hard. Finally, we reveal an interesting connection of our model to the problem of information acquisition for decision making and study its algorithmic properties in general. △ Less

Submitted 13 February, 2024; v1 submitted 2 September, 2022; originally announced September 2022.

Socially Fair Reinforcement Learning

Authors: Debmalya Mandal, Jiarui Gan

Abstract: We consider the problem of episodic reinforcement learning where there are multiple stakeholders with different reward functions. Our goal is to output a policy that is socially fair with respect to different reward functions. Prior works have proposed different objectives that a fair policy must optimize including minimum welfare, and generalized Gini welfare. We first take an axiomatic view of t… ▽ More We consider the problem of episodic reinforcement learning where there are multiple stakeholders with different reward functions. Our goal is to output a policy that is socially fair with respect to different reward functions. Prior works have proposed different objectives that a fair policy must optimize including minimum welfare, and generalized Gini welfare. We first take an axiomatic view of the problem, and propose four axioms that any such fair objective must satisfy. We show that the Nash social welfare is the unique objective that uniquely satisfies all four objectives, whereas prior objectives fail to satisfy all four axioms. We then consider the learning version of the problem where the underlying model i.e. Markov decision process is unknown. We consider the problem of minimizing regret with respect to the fair policies maximizing three different fair objectives -- minimum welfare, generalized Gini welfare, and Nash social welfare. Based on optimistic planning, we propose a generic learning algorithm and derive its regret bound with respect to the three different policies. For the objective of Nash social welfare, we also derive a lower bound in regret that grows exponentially with $n$, the number of agents. Finally, we show that for the objective of minimum welfare, one can improve regret by a factor of $O(H)$ for a weaker notion of regret. △ Less

Submitted 3 February, 2023; v1 submitted 26 August, 2022; originally announced August 2022.

Decentralized Online Convex Optimization in Networked Systems

Authors: Yiheng Lin, Judy Gan, Guannan Qu, Yash Kanoria, Adam Wierman

Abstract: We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each t… ▽ More We study the problem of networked online convex optimization, where each agent individually decides on an action at every time step and agents cooperatively seek to minimize the total global cost over a finite horizon. The global cost is made up of three types of local costs: convex node costs, temporal interaction costs, and spatial interaction costs. In deciding their individual action at each time, an agent has access to predictions of local cost functions for the next $k$ time steps in an $r$-hop neighborhood. Our work proposes a novel online algorithm, Localized Predictive Control (LPC), which generalizes predictive control to multi-agent systems. We show that LPC achieves a competitive ratio of $1 + \tilde{O}(ρ_T^k) + \tilde{O}(ρ_S^r)$ in an adversarial setting, where $ρ_T$ and $ρ_S$ are constants in $(0, 1)$ that increase with the relative strength of temporal and spatial interaction costs, respectively. This is the first competitive ratio bound on decentralized predictive control for networked online convex optimization. Further, we show that the dependence on $k$ and $r$ in our results is near optimal by lower bounding the competitive ratio of any decentralized online algorithm. △ Less

Submitted 13 July, 2022; originally announced July 2022.

Detecting Arbitrary Order Beneficial Feature Interactions for Recommender Systems

Authors: Yixin Su, Yunxiang Zhao, Sarah Erfani, Junhao Gan, Rui Zhang

Abstract: 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 fou… ▽ More 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. △ Less

Submitted 28 June, 2022; originally announced June 2022.

Comments: KDD 2022, 11 pages, 12 figures, 5 tables

A robotic leg inspired from an insect leg

Authors: P. Thanh Tran-Ngoc, Leslie Ziqi Lim, Jia Hui Gan, Hong Wang, T. Thang Vo-Doan, Hirotaka Sato

Abstract: While most insect-inspired robots come with a simple tarsus such as a hemispherical foot tip, insect legs have complex tarsal structures and claws, which enable them to walk on complex terrain. Their sharp claws can smoothly attach and detach on plant surfaces by actuating a single muscle. Thus, installing insect-inspired tarsus on legged robots would improve their locomotion on complex terrain. T… ▽ More While most insect-inspired robots come with a simple tarsus such as a hemispherical foot tip, insect legs have complex tarsal structures and claws, which enable them to walk on complex terrain. Their sharp claws can smoothly attach and detach on plant surfaces by actuating a single muscle. Thus, installing insect-inspired tarsus on legged robots would improve their locomotion on complex terrain. This paper shows that the tendon-driven ball-socket structure provides the tarsus both flexibility and rigidity, which is necessary for the beetle to walk on a complex substrate such as a mesh surface. Disabling the tarsus' rigidity by removing the socket and elastic membrane of a tarsal joint, the claws could not attach to the mesh securely. Meanwhile, the beetle struggled to draw the claws out of the substrate when we turned the tarsus rigid by tubing. We then developed a cable-driven bio-inspired tarsus structure to validate the function of the tarsus as well as to show its potential application in the legged robot. With the tarsus, the robotic leg was able to attach and retract smoothly from the mesh substrate when performing a walking cycle. △ Less

Submitted 11 May, 2022; v1 submitted 21 March, 2022; originally announced March 2022.

Comments: 17 pages, 10 figures

Journal ref: Bioinspir. Biomim. 17 (2022) 056008

Edge-based Local Push for Personalized PageRank

Authors: Hanzhi Wang, Zhewei Wei, Junhao Gan, Ye Yuan, Xiaoyong Du, Ji-Rong Wen

Abstract: Personalized PageRank (PPR) is a popular node proximity metric in graph mining and network research. Given a graph G=(V,E) and a source node $s \in V$, a single-source PPR (SSPPR) query asks for the PPR value $\vpi(u)$ with respect to s, which represents the relative importance of node u in the context of the source node s. Among existing algorithms for SSPPR queries, LocalPush is a fundamental me… ▽ More Personalized PageRank (PPR) is a popular node proximity metric in graph mining and network research. Given a graph G=(V,E) and a source node $s \in V$, a single-source PPR (SSPPR) query asks for the PPR value $\vpi(u)$ with respect to s, which represents the relative importance of node u in the context of the source node s. Among existing algorithms for SSPPR queries, LocalPush is a fundamental method which serves as a cornerstone for subsequent algorithms. In LocalPush, a push operation is a crucial primitive operation, which distributes the probability at a node u to ALL u's neighbors via the corresponding edges. Although this push operation works well on unweighted graphs, unfortunately, it can be rather inefficient on weighted graphs. In particular, on unbalanced weighted graphs where only a few of these edges take the majority of the total weight among them, the push operation would have to distribute insignificant probabilities along those edges which just take the minor weights, resulting in expensive overhead. To resolve this issue, we propose the EdgePush algorithm, a novel method for computing SSPPR queries on weighted graphs. EdgePush decomposes the aforementioned push operations in edge-based push, allowing the algorithm to operate at the edge level granularity. Hence, it can flexibly distribute the probabilities according to edge weights. Furthermore, our EdgePush allows a fine-grained termination threshold for each individual edge, leading to a superior complexity over LocalPush. Notably, we prove that EdgePush improves the theoretical query cost of LocalPush by an order of up to O(n) when the graph's weights are unbalanced, both in terms of $\ell_1$-error and normalized additive error. Our experimental results demonstrate that EdgePush significantly outperforms state-of-the-art baselines in terms of query efficiency on large motif-based and real-world weighted graphs. △ Less

Submitted 7 May, 2022; v1 submitted 15 March, 2022; originally announced March 2022.

Comments: VLDB 2022, volume 15, issue 7

Admissible Policy Teaching through Reward Design

Authors: Kiarash Banihashem, Adish Singla, Jiarui Gan, Goran Radanovic

Abstract: We study reward design strategies for incentivizing a reinforcement learning agent to adopt a policy from a set of admissible policies. The goal of the reward designer is to modify the underlying reward function cost-efficiently while ensuring that any approximately optimal deterministic policy under the new reward function is admissible and performs well under the original reward function. This p… ▽ More We study reward design strategies for incentivizing a reinforcement learning agent to adopt a policy from a set of admissible policies. The goal of the reward designer is to modify the underlying reward function cost-efficiently while ensuring that any approximately optimal deterministic policy under the new reward function is admissible and performs well under the original reward function. This problem can be viewed as a dual to the problem of optimal reward poisoning attacks: instead of forcing an agent to adopt a specific policy, the reward designer incentivizes an agent to avoid taking actions that are inadmissible in certain states. Perhaps surprisingly, and in contrast to the problem of optimal reward poisoning attacks, we first show that the reward design problem for admissible policy teaching is computationally challenging, and it is NP-hard to find an approximately optimal reward modification. We then proceed by formulating a surrogate problem whose optimal solution approximates the optimal solution to the reward design problem in our setting, but is more amenable to optimization techniques and analysis. For this surrogate problem, we present characterization results that provide bounds on the value of the optimal solution. Finally, we design a local search algorithm to solve the surrogate problem and showcase its utility using simulation-based experiments. △ Less

Submitted 6 January, 2022; originally announced January 2022.

Advancing COVID-19 Diagnosis with Privacy-Preserving Collaboration in Artificial Intelligence

Authors: Xiang Bai, Hanchen Wang, Liya Ma, Yongchao Xu, Jiefeng Gan, Ziwei Fan, Fan Yang, Ke Ma, Jiehua Yang, Song Bai, Chang Shu, Xinyu Zou, Renhao Huang, Changzheng Zhang, Xiaowu Liu, Dandan Tu, Chuou Xu, Wenqing Zhang, Xi Wang, Anguo Chen, Yu Zeng, Dehua Yang, Ming-Wei Wang, Nagaraj Holalkere, Neil J. Halin , et al. (21 additional authors not shown)

Abstract: Artificial intelligence (AI) provides a promising substitution for streamlining COVID-19 diagnoses. However, concerns surrounding security and trustworthiness impede the collection of large-scale representative medical data, posing a considerable challenge for training a well-generalised model in clinical practices. To address this, we launch the Unified CT-COVID AI Diagnostic Initiative (UCADI),… ▽ More Artificial intelligence (AI) provides a promising substitution for streamlining COVID-19 diagnoses. However, concerns surrounding security and trustworthiness impede the collection of large-scale representative medical data, posing a considerable challenge for training a well-generalised model in clinical practices. To address this, we launch the Unified CT-COVID AI Diagnostic Initiative (UCADI), where the AI model can be distributedly trained and independently executed at each host institution under a federated learning framework (FL) without data sharing. Here we show that our FL model outperformed all the local models by a large yield (test sensitivity /specificity in China: 0.973/0.951, in the UK: 0.730/0.942), achieving comparable performance with a panel of professional radiologists. We further evaluated the model on the hold-out (collected from another two hospitals leaving out the FL) and heterogeneous (acquired with contrast materials) data, provided visual explanations for decisions made by the model, and analysed the trade-offs between the model performance and the communication costs in the federated training process. Our study is based on 9,573 chest computed tomography scans (CTs) from 3,336 patients collected from 23 hospitals located in China and the UK. Collectively, our work advanced the prospects of utilising federated learning for privacy-preserving AI in digital health. △ Less

Submitted 17 November, 2021; originally announced November 2021.

Comments: Nature Machine Intelligence

Sensor Data Augmentation by Resampling for Contrastive Learning in Human Activity Recognition

Authors: Jinqiang Wang, Tao Zhu, Jingyuan Gan, Liming Chen, Huansheng Ning, Yaping Wan

Abstract: While deep learning has contributed to the advancement of sensor-based Human Activity Recognition (HAR), it is usually a costly and challenging supervised task with the needs of a large amount of labeled data. To alleviate this issue, contrastive learning has been applied for sensor-based HAR. Data augmentation is an essential part of contrastive learning and has a significant impact on the perfor… ▽ More While deep learning has contributed to the advancement of sensor-based Human Activity Recognition (HAR), it is usually a costly and challenging supervised task with the needs of a large amount of labeled data. To alleviate this issue, contrastive learning has been applied for sensor-based HAR. Data augmentation is an essential part of contrastive learning and has a significant impact on the performance of downstream tasks. However, current popular augmentation methods do not achieve competitive performance in contrastive learning for sensor-based HAR. Motivated by this issue, we propose a new sensor data augmentation method by resampling, which simulates more realistic activity data by varying the sampling frequency to maximize the coverage of the sampling space. In addition, we extend MoCo, a popular contrastive learning framework, to MoCoHAR for HAR. The resampling augmentation method will be evaluated on two contrastive learning frameworks, SimCLRHAR and MoCoHAR, using UCI-HAR, MotionSensor, and USC-HAD datasets. The experiment results show that the resampling augmentation method outperforms all state-of-the-art methods under a small amount of labeled data, on SimCLRHAR and MoCoHAR, with mean F1-score as the evaluation metric. The results also demonstrate that not all data augmentation methods have positive effects in the contrastive learning framework. △ Less

Submitted 23 March, 2022; v1 submitted 5 September, 2021; originally announced September 2021.

Comments: 13 pages,5 figures

Dynamic Structural Clustering on Graphs

Authors: Boyu Ruan, Junhao Gan, Hao Wu, Anthony Wirth

Abstract: Structural Clustering ($DynClu$) is one of the most popular graph clustering paradigms. In this paper, we consider $StrClu$ under two commonly adapted similarities, namely Jaccard similarity and cosine similarity on a dynamic graph, $G = \langle V, E\rangle$, subject to edge insertions and deletions (updates). The goal is to maintain certain information under updates, so that the $StrClu$ clusteri… ▽ More Structural Clustering ($DynClu$) is one of the most popular graph clustering paradigms. In this paper, we consider $StrClu$ under two commonly adapted similarities, namely Jaccard similarity and cosine similarity on a dynamic graph, $G = \langle V, E\rangle$, subject to edge insertions and deletions (updates). The goal is to maintain certain information under updates, so that the $StrClu$ clustering result on~$G$ can be retrieved in $O(|V| + |E|)$ time, upon request. The state-of-the-art worst-case cost is $O(|V|)$ per update; we improve this update-time bound significantly with the $ρ$-approximate notion. Specifically, for a specified failure probability, $δ^*$, and every sequence of $M$ updates (no need to know $M$'s value in advance), our algorithm, $DynELM$, achieves $O(\log^2 |V| + \log |V| \cdot \log \frac{M}{δ^*})$ amortized cost for each update, at all times in linear space. Moreover, $DynELM$ provides a provable "sandwich" guarantee on the clustering quality at all times after \emph{each update} with probability at least $1 - δ^*$. We further develop $DynELM$ into our ultimate algorithm, $DynStrClu$, which also supports cluster-group-by queries. Given $Q\subseteq V$, this puts the non-empty intersection of $Q$ and each $StrClu$ cluster into a distinct group. $DynStrClu$ not only achieves all the guarantees of $DynELM$, but also runs cluster-group-by queries in $O(|Q|\cdot \log |V|)$ time. We demonstrate the performance of our algorithms via extensive experiments, on 15 real datasets. Experimental results confirm that our algorithms are up to three orders of magnitude more efficient than state-of-the-art competitors, and still provide quality structural clustering results. Furthermore, we study the difference between the two similarities w.r.t. the quality of approximate clustering results. △ Less

Submitted 25 August, 2021; originally announced August 2021.

Approximately Envy-Free Budget-Feasible Allocation

Authors: Jiarui Gan, Bo Li, Xiaowei Wu

Abstract: In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all… ▽ More In the budget-feasible allocation problem, a set of items with varied sizes and values are to be allocated to a group of agents. Each agent has a budget constraint on the total size of items she can receive. The goal is to compute a feasible allocation that is envy-free (EF), in which the agents do not envy each other for the items they receive, nor do they envy a charity, who is endowed with all the unallocated items. Since EF allocations barely exist even without budget constraints, we are interested in the relaxed notion of envy-freeness up to one item (EF1). The computation of both exact and approximate EF1 allocations remains largely open, despite a recent effort by Wu et al. (IJCAI 2021) in showing that any budget-feasible allocation that maximizes the Nash Social Welfare (NSW) is 1/4-approximate EF1. In this paper, we move one step forward by showing that for agents with identical additive valuations, a 1/2-approximate EF1 allocation can be computed in polynomial time. For the uniform-budget and two-agent cases, we propose efficient algorithms for computing an exact EF1 allocation. We also consider the large budget setting, i.e., when the item sizes are infinitesimal compared with the agents' budgets, and show that both the NSW maximizing allocation and the allocation our polynomial-time algorithm computes have an approximation close to 1 regarding EF1. △ Less

Submitted 28 June, 2021; originally announced June 2021.

Bayesian Persuasion in Sequential Decision-Making

Authors: Jiarui Gan, Rupak Majumdar, Goran Radanovic, Adish Singla

Abstract: We study a dynamic model of Bayesian persuasion in sequential decision-making settings. An informed principal observes an external parameter of the world and advises an uninformed agent about actions to take over time. The agent takes actions in each time step based on the current state, the principal's advice/signal, and beliefs about the external parameter. The action of the agent updates the st… ▽ More We study a dynamic model of Bayesian persuasion in sequential decision-making settings. An informed principal observes an external parameter of the world and advises an uninformed agent about actions to take over time. The agent takes actions in each time step based on the current state, the principal's advice/signal, and beliefs about the external parameter. The action of the agent updates the state according to a stochastic process. The model arises naturally in many applications, e.g., an app (the principal) can advice the user (the agent) on possible choices between actions based on additional real-time information the app has. We study the problem of designing a signaling strategy from the principal's point of view. We show that the principal has an optimal strategy against a myopic agent, who only optimizes their rewards locally, and the optimal strategy can be computed in polynomial time. In contrast, it is NP-hard to approximate an optimal policy against a far-sighted agent. Further, if the principal has the power to threaten the agent by not providing future signals, then we can efficiently compute a threat-based strategy. This strategy guarantees the principal's payoff as if playing against an agent who is far-sighted but myopic to future signals. △ Less

Submitted 24 May, 2022; v1 submitted 9 June, 2021; originally announced June 2021.

Calculation of Berry curvature using nonorthogonal atomic orbitals

Authors: Jin Gan, Daye Zheng, Lixin He

Abstract: We present a derivation of the full formula to calculate the Berry curvature on non-orthogonal numerical atomic orbital (NAO) bases.Because usually, the number of NAOs is larger than that of the Wannier bases, we use a orbital contraction method to reduce the basis sizes, which can greatly improve the calculation efficiency without significantly reducing the calculation accuracy. We benchmark the… ▽ More We present a derivation of the full formula to calculate the Berry curvature on non-orthogonal numerical atomic orbital (NAO) bases.Because usually, the number of NAOs is larger than that of the Wannier bases, we use a orbital contraction method to reduce the basis sizes, which can greatly improve the calculation efficiency without significantly reducing the calculation accuracy. We benchmark the formula by calculating the Berry curvature of ferroelectric BaTiO$_3$ and bcc Fe, as well as the anomalous Hall conductivity (AHC) for Fe. The results are in excellent agreement with the finite difference and previous results in the literature. We find that there are corrections terms to the Kubo formula of the Berry curvature. For the full NAO base, the differences between the two methods are negligibly small, but for the reduced bases sets, the correction terms become larger, which may not be neglected in some cases. The formula developed in this work can readily be applied to the non-orthogonal generalized Wannier functions. △ Less

Submitted 30 May, 2021; originally announced May 2021.

Insect-Computer Hybrid System for Autonomous Search and Rescue Mission

Authors: P. Thanh Tran-Ngoc, D. Long Le, Bing Sheng Chong, H. Duoc Nguyen, V. Than Dung, Feng Cao, Yao Li, Kazuki Kai, Jia Hui Gan, T. Thang Vo-Doan, T. Luan Nguyen, Hirotaka Sato

Abstract: There is still a long way to go before artificial mini robots are really used for search and rescue missions in disaster-hit areas due to hindrance in power consumption, computation load of the locomotion, and obstacle-avoidance system. Insect-computer hybrid system, which is the fusion of living insect platform and microcontroller, emerges as an alternative solution. This study demonstrates the f… ▽ More There is still a long way to go before artificial mini robots are really used for search and rescue missions in disaster-hit areas due to hindrance in power consumption, computation load of the locomotion, and obstacle-avoidance system. Insect-computer hybrid system, which is the fusion of living insect platform and microcontroller, emerges as an alternative solution. This study demonstrates the first-ever insect-computer hybrid system conceived for search and rescue missions, which is capable of autonomous navigation and human presence detection in an unstructured environment. Customized navigation control algorithm utilizing the insect's intrinsic navigation capability achieved exploration and negotiation of complex terrains. On-board high-accuracy human presence detection using infrared camera was achieved with a custom machine learning model. Low power consumption suggests system suitability for hour-long operations and its potential for realization in real-life missions. △ Less

Submitted 21 June, 2021; v1 submitted 23 May, 2021; originally announced May 2021.

Comments: Videos are available at https://hirosatontu.wordpress.com/research/

Neural Graph Matching based Collaborative Filtering

Authors: Yixin Su, Rui Zhang, Sarah Erfani, Junhao Gan

Abstract: User and item attributes are essential side-information; their interactions (i.e., their co-occurrence in the sample data) can significantly enhance prediction accuracy in various recommender systems. We identify two different types of attribute interactions, inner interactions and cross interactions: inner interactions are those between only user attributes or those between only item attributes;… ▽ More User and item attributes are essential side-information; their interactions (i.e., their co-occurrence in the sample data) can significantly enhance prediction accuracy in various recommender systems. We identify two different types of attribute interactions, inner interactions and cross interactions: inner interactions are those between only user attributes or those between only item attributes; cross interactions are those between user attributes and item attributes. Existing models do not distinguish these two types of attribute interactions, which may not be the most effective way to exploit the information carried by the interactions. To address this drawback, we propose a neural Graph Matching based Collaborative Filtering model (GMCF), which effectively captures the two types of attribute interactions through modeling and aggregating attribute interactions in a graph matching structure for recommendation. In our model, the two essential recommendation procedures, characteristic learning and preference matching, are explicitly conducted through graph learning (based on inner interactions) and node matching (based on cross interactions), respectively. Experimental results show that our model outperforms state-of-the-art models. Further studies verify the effectiveness of GMCF in improving the accuracy of recommendation. △ Less

Submitted 22 July, 2021; v1 submitted 9 May, 2021; originally announced May 2021.

Comments: 10 pages, 6 figures, 4 tables, SIGIR 2021

Quantum-enhanced bosonic learning machine

Authors: Chi-Huan Nguyen, Ko-Wei Tseng, Gleb Maslennikov, H. C. J. Gan, Dzmitry Matsukevich

Abstract: Quantum processors enable computational speedups for machine learning through parallel manipulation of high-dimensional vectors. Early demonstrations of quantum machine learning have focused on processing information with qubits. In such systems, a larger computational space is provided by the collective space of multiple physical qubits. Alternatively, we can encode and process information in the… ▽ More Quantum processors enable computational speedups for machine learning through parallel manipulation of high-dimensional vectors. Early demonstrations of quantum machine learning have focused on processing information with qubits. In such systems, a larger computational space is provided by the collective space of multiple physical qubits. Alternatively, we can encode and process information in the infinite-dimensional Hilbert space of bosonic systems such as quantum harmonic oscillators. This approach offers a hardware-efficient solution with potential quantum speedups to practical machine learning problems. Here we demonstrate a quantum-enhanced bosonic learning machine operating on quantum data with a system of trapped ions. Core elements of the learning processor are the universal feature-embedding circuit that encodes data into the motional states of ions, and the constant-depth circuit that estimates overlap between two quantum states. We implement the unsupervised K-means algorithm to recognize a pattern in a set of high-dimensional quantum states and use the discovered knowledge to classify unknown quantum states with the supervised k-NN algorithm. These results provide building blocks for exploring machine learning with bosonic processors. △ Less

Submitted 8 April, 2021; originally announced April 2021.

Comments: 10 pages, 8 figures

Quantum computation and simulation with vibrational modes of trapped ions

Authors: Wentao Chen, Jaren Gan, Jing-Ning Zhang, Dzmitry Matuskevich, Kihwan Kim

Abstract: Vibrational degrees of freedom in trapped-ion systems have recently been gaining attention as a quantum resource, beyond the role as a mediator for entangling quantum operations on internal degrees of freedom, because of the large available Hilbert space. The vibrational modes can be represented as quantum harmonic oscillators and thus offer a Hilbert space with infinite dimension. Here we review… ▽ More Vibrational degrees of freedom in trapped-ion systems have recently been gaining attention as a quantum resource, beyond the role as a mediator for entangling quantum operations on internal degrees of freedom, because of the large available Hilbert space. The vibrational modes can be represented as quantum harmonic oscillators and thus offer a Hilbert space with infinite dimension. Here we review recent theoretical and experimental progress in the coherent manipulation of the vibrational modes, including bosonic encoding schemes in quantum information, reliable and efficient measurement techniques, and quantum operations that allow various quantum simulations and quantum computation algorithms. We describe experiments using the vibrational modes, including the preparation of non-classical states, molecular vibronic sampling, and applications in quantum thermodynamics. We finally discuss the potential prospects and challenges of trapped-ion vibrational-mode quantum information processing. △ Less

Submitted 26 March, 2021; originally announced March 2021.

Comments: 19 pages, 12 figures, review paper

Journal ref: Chin. Phys. B, 30(6): 060311 (2021)

Experimental SWAP test of infinite dimensional quantum states

Authors: Chi-Huan Nguyen, Ko-Wei Tseng, Gleb Maslennikov, H. C. J. Gan, Dzmitry Matsukevich

Abstract: Efficient overlap estimation of high-dimensional quantum states is an important task in quantum information and a core element in computational speedups of quantum machine learning. Here we experimentally demonstrate the SWAP test that measures the overlap of two motional states in a system of trapped $^{171}\mathrm{Yb}^+$ ions. To illustrate the versatility of our implementation, we report the ov… ▽ More Efficient overlap estimation of high-dimensional quantum states is an important task in quantum information and a core element in computational speedups of quantum machine learning. Here we experimentally demonstrate the SWAP test that measures the overlap of two motional states in a system of trapped $^{171}\mathrm{Yb}^+$ ions. To illustrate the versatility of our implementation, we report the overlap measurement of a variety of quantum states: Fock states, coherent states, squeezed vacuum states, and cat states. We highlight applications of the SWAP test by measuring the purity of mixed states. Our results enable quantum information processing with high dimensional quantum states. △ Less

Submitted 18 March, 2021; originally announced March 2021.

Comments: 9 pages, 4 figures

Transparent Checkpointing for OpenGL Applications on GPUs

Authors: David Hou, Jun Gan, Yue Li, Younes El Idrissi Yazami, Twinkle Jain

Abstract: This work presents transparent checkpointing of OpenGL applications, refining the split-process technique[1] for application in GPU-based 3D graphics. The split-process technique was earlier applied to checkpointing MPI and CUDA programs, enabling reinitialization of driver libraries. The presented design targets practical, checkpoint-package agnostic checkpointing of OpenGL applications. An ear… ▽ More This work presents transparent checkpointing of OpenGL applications, refining the split-process technique[1] for application in GPU-based 3D graphics. The split-process technique was earlier applied to checkpointing MPI and CUDA programs, enabling reinitialization of driver libraries. The presented design targets practical, checkpoint-package agnostic checkpointing of OpenGL applications. An early prototype is demonstrated on Autodesk Maya. Maya is a complex proprietary media-creation software suite used with large-scale rendering hardware for CGI (Computer-Generated Animation). Transparent checkpointing of Maya provides critically-needed fault tolerance, since Maya is prone to crash when artists use some of its bleeding-edge components. Artists then lose hours of work in re-creating their complex environment. △ Less

Submitted 1 August, 2021; v1 submitted 8 March, 2021; originally announced March 2021.

ACM Class: D.4.5

Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push

Authors: Hao Wu, Junhao Gan, Zhewei Wei, Rui Zhang

Abstract: Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph $G$ with $n$ nodes and $m$ edges, and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for solving two variants of SSPPR:… ▽ More Personalized PageRank (PPR) is a critical measure of the importance of a node t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes the PPR's of all the nodes with respect to s on a directed graph $G$ with $n$ nodes and $m$ edges, and it is an essential operation widely used in graph applications. In this paper, we propose novel algorithms for solving two variants of SSPPR: (i) high-precision queries and (ii) approximate queries. For high-precision queries, Power Iteration (PowItr) and Forward Push (FwdPush) are two fundamental approaches. Given an absolute error threshold $λ$, the only known bound of FwdPush is $O(\frac{m}λ)$, much worse than the $O(m \log \frac{1}λ)$-bound of PowItr. Whether FwdPush can achieve the same running time bound as PowItr does still remains an open question in the research community. We give a positive answer to this question by showing that the running time of a common implementation of FwdPush is actually bounded by $O(m \cdot \log \frac{1}λ)$.Based on this finding, we propose a new algorithm, called Power Iteration with Forward Push (PowerPush), which incorporates the strengths of both PowItr and FwdPush. For approximate queries (with a relative error $ε$), we propose a new algorithm, called SpeedPPR, with overall expected time bounded by $O(n \cdot \log n \cdot \log \frac{1}ε)$ on scale-free graphs. This bound greatly improves the $O(\frac{n \cdot \log n}ε)$ bound of a state-of-the-art algorithm FORA. △ Less

Submitted 24 April, 2021; v1 submitted 10 January, 2021; originally announced January 2021.

Comments: 12 pages

Your College Dorm and Dormmates: Fair Resource Sharing with Externalities

Authors: Jiarui Gan, Bo Li, Yingkai Li

Abstract: We study a fair resource sharing problem, where a set of resources are to be shared among a group of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, who share the same resource with them. Clearly, the strong notion of envy-freeness, where no agent envies… ▽ More We study a fair resource sharing problem, where a set of resources are to be shared among a group of agents. Each agent demands one resource and each resource can serve a limited number of agents. An agent cares about what resource they get as well as the externalities imposed by their mates, who share the same resource with them. Clearly, the strong notion of envy-freeness, where no agent envies another for their resource or mates, cannot always be achieved and we show that even deciding the existence of such a strongly envy-free assignment is an intractable problem. Hence, a more interesting question is whether (and in what situations) a relaxed notion of envy-freeness, the Pareto envy-freeness, can be achieved. Under this relaxed notion, an agent envies another only when they envy both the resource and the mates of the other agent. In particular, we are interested in a dorm assignment problem, where students are to be assigned to dorms with the same capacity and they have dichotomous preference over their dormmates. We show that when the capacity of each dorm is 2, a Pareto envy-free assignment always exists and we present a polynomial-time algorithm to compute such an assignment. Nevertheless, the result breaks immediately when the capacity increases to 3, in which case even Pareto envy-freeness cannot be guaranteed. In addition to the existential results, we also investigate the utility guarantees of (Pareto) envy-free assignments in our model. △ Less

Submitted 13 July, 2023; v1 submitted 8 December, 2020; originally announced December 2020.

Comments: accepted in JAIR 2023

Journal ref: Journal.of.Artificial.Intelligence.Research.77(2023)793-820

Budget-feasible Maximum Nash Social Welfare Allocation is Almost Envy-free

Authors: Xiaowei Wu, Bo Li, Jiarui Gan

Abstract: The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget… ▽ More The Nash social welfare (NSW) is a well-known social welfare measurement that balances individual utilities and the overall efficiency. In the context of fair allocation of indivisible goods, it has been shown by Caragiannis et al. (EC 2016 and TEAC 2019) that an allocation maximizing the NSW is envy-free up to one good (EF1). In this paper, we are interested in the fairness of the NSW in a budget-feasible allocation problem, in which each item has a cost that will be incurred to the agent it is allocated to, and each agent has a budget constraint on the total cost of items she receives. We show that a budget-feasible allocation that maximizes the NSW achieves a 1/4-approximation of EF1 and the approximation ratio is tight. The approximation ratio improves gracefully when the items have small costs compared with the agents' budgets; it converges to 1/2 when the budget-cost ratio approaches infinity. △ Less

Submitted 7 December, 2020; originally announced December 2020.

Comments: 16 pages, 2 figures

Learning Based Distributed Tracking

Authors: Hao Wu, Junhao Gan, Rui Zhang

Abstract: Inspired by the great success of machine learning in the past decade, people have been thinking about the possibility of improving the theoretical results by exploring data distribution. In this paper, we revisit a fundamental problem called Distributed Tracking (DT) under an assumption that the data follows a certain (known or unknown) distribution, and propose a number data-dependent algorithms… ▽ More Inspired by the great success of machine learning in the past decade, people have been thinking about the possibility of improving the theoretical results by exploring data distribution. In this paper, we revisit a fundamental problem called Distributed Tracking (DT) under an assumption that the data follows a certain (known or unknown) distribution, and propose a number data-dependent algorithms with improved theoretical bounds. Informally, in the DT problem, there is a coordinator and k players, where the coordinator holds a threshold N and each player has a counter. At each time stamp, at most one counter can be increased by one. The job of the coordinator is to capture the exact moment when the sum of all these k counters reaches N. The goal is to minimise the communication cost. While our first type of algorithms assume the concrete data distribution is known in advance, our second type of algorithms can learn the distribution on the fly. Both of the algorithms achieve a communication cost bounded byO(k log log N) with high probability, improving the state-of-the-art data-independent bound O(k log N/k). We further propose a number of implementation optimisation heuristics to improve both efficiency and robustness of the algorithms. Finally, we conduct extensive experiments on three real datasets and four synthetic datasets. The experimental results show that the communication cost of our algorithms is as least as 20% of that of the state-of-the-art algorithms. △ Less

Submitted 23 June, 2020; originally announced June 2020.

Personalized PageRank to a Target Node, Revisited

Authors: Hanzhi Wang, Zhewei Wei, Junhao Gan, Sibo Wang, Zengfeng Huang

Abstract: Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node $s$ and a target node $t$, the PPR value $π(s,t)$ represents the probability that a random walk from $s$ terminates at $t$, and thus indicates the bidirectional importance between $s$ and $t$. The majority of the existing work focuses on the single-source queries, which ask… ▽ More Personalized PageRank (PPR) is a widely used node proximity measure in graph mining and network analysis. Given a source node $s$ and a target node $t$, the PPR value $π(s,t)$ represents the probability that a random walk from $s$ terminates at $t$, and thus indicates the bidirectional importance between $s$ and $t$. The majority of the existing work focuses on the single-source queries, which asks for the PPR value of a given source node $s$ and every node $t \in V$. However, the single-source query only reflects the importance of each node $t$ with respect to $s$. In this paper, we consider the {\em single-target PPR query}, which measures the opposite direction of importance for PPR. Given a target node $t$, the single-target PPR query asks for the PPR value of every node $s\in V$ to a given target node $t$. We propose RBS, a novel algorithm that answers approximate single-target queries with optimal computational complexity. We show that RBS improves three concrete applications: heavy hitters PPR query, single-source SimRank computation, and scalable graph neural networks. We conduct experiments to demonstrate that RBS outperforms the state-of-the-art algorithms in terms of both efficiency and precision on real-world benchmark datasets. △ Less

Submitted 24 June, 2020; v1 submitted 21 June, 2020; originally announced June 2020.

Comments: ACM SIGKDD 2020

Optimally Deceiving a Learning Leader in Stackelberg Games

Authors: Georgios Birmpas, Jiarui Gan, Alexandros Hollender, Francisco J. Marmolejo-Cossío, Ninad Rajgopal, Alexandros A. Voudouris

Abstract: Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to manipulation by the follower. Such a learning algorithm operates by querying the best responses or the payoffs of the follower, who consequently can deceive the algorithm by responding as if his payoffs were much differ… ▽ More Recent results in the ML community have revealed that learning algorithms used to compute the optimal strategy for the leader to commit to in a Stackelberg game, are susceptible to manipulation by the follower. Such a learning algorithm operates by querying the best responses or the payoffs of the follower, who consequently can deceive the algorithm by responding as if his payoffs were much different than what they actually are. For this strategic behavior to be successful, the main challenge faced by the follower is to pinpoint the payoffs that would make the learning algorithm compute a commitment so that best responding to it maximizes the follower's utility, according to his true payoffs. While this problem has been considered before, the related literature only focused on the simplified scenario in which the payoff space is finite, thus leaving the general version of the problem unanswered. In this paper, we fill in this gap, by showing that it is always possible for the follower to compute (near-)optimal payoffs for various scenarios about the learning interaction between leader and follower. △ Less

Submitted 11 June, 2020; originally announced June 2020.

Journal ref: Journal of Artificial Intelligence Research, 72:507-531 (2021)

Joint Prediction and Time Estimation of COVID-19 Developing Severe Symptoms using Chest CT Scan

Authors: Xiaofeng Zhu, Bin Song, Feng Shi, Yanbo Chen, Rongyao Hu, Jiangzhang Gan, Wenhai Zhang, Man Li, Liye Wang, Yaozong Gao, Fei Shan, Dinggang Shen

Abstract: With the rapidly worldwide spread of Coronavirus disease (COVID-19), it is of great importance to conduct early diagnosis of COVID-19 and predict the time that patients might convert to the severe stage, for designing effective treatment plan and reducing the clinicians' workloads. In this study, we propose a joint classification and regression method to determine whether the patient would develop… ▽ More With the rapidly worldwide spread of Coronavirus disease (COVID-19), it is of great importance to conduct early diagnosis of COVID-19 and predict the time that patients might convert to the severe stage, for designing effective treatment plan and reducing the clinicians' workloads. In this study, we propose a joint classification and regression method to determine whether the patient would develop severe symptoms in the later time, and if yes, predict the possible conversion time that the patient would spend to convert to the severe stage. To do this, the proposed method takes into account 1) the weight for each sample to reduce the outliers' influence and explore the problem of imbalance classification, and 2) the weight for each feature via a sparsity regularization term to remove the redundant features of high-dimensional data and learn the shared information across the classification task and the regression task. To our knowledge, this study is the first work to predict the disease progression and the conversion time, which could help clinicians to deal with the potential severe cases in time or even save the patients' lives. Experimental analysis was conducted on a real data set from two hospitals with 422 chest computed tomography (CT) scans, where 52 cases were converted to severe on average 5.64 days and 34 cases were severe at admission. Results show that our method achieves the best classification (e.g., 85.91% of accuracy) and regression (e.g., 0.462 of the correlation coefficient) performance, compared to all comparison methods. Moreover, our proposed method yields 76.97% of accuracy for predicting the severe cases, 0.524 of the correlation coefficient, and 0.55 days difference for the converted time. △ Less

Submitted 7 May, 2020; originally announced May 2020.

Journal ref: Medical Image Analysis (2020)

Numerical linked cluster expansions for inhomogeneous systems

Authors: Johann Gan, Kaden R. A. Hazzard

Abstract: We develop a numerical linked cluster expansion (NLCE) method that can be applied directly to inhomogeneous systems, for example Hamiltonians with disorder and dynamics initiated from inhomogeneous initial states. We demonstrate the method by calculating dynamics for single-spin expectations and spin correlations in two-dimensional spin models on a square lattice, starting from a checkerboard stat… ▽ More We develop a numerical linked cluster expansion (NLCE) method that can be applied directly to inhomogeneous systems, for example Hamiltonians with disorder and dynamics initiated from inhomogeneous initial states. We demonstrate the method by calculating dynamics for single-spin expectations and spin correlations in two-dimensional spin models on a square lattice, starting from a checkerboard state. We show that NLCE can give moderate to dramatic improvement over an exact diagonalization of comparable computational cost, and that the advantage in computational resources grows exponentially as the size of the clusters included grows. Although the method applies to any type of NLCE, our explicit benchmarks use the rectangle expansion. Besides showing the capability to treat inhomogeneous systems, these benchmarks demonstrate the rectangle expansion's utility out of equilibrium. △ Less

Submitted 20 May, 2020; v1 submitted 6 May, 2020; originally announced May 2020.

Comments: 9 pages, 6 figures

Journal ref: Phys. Rev. A 102, 013318 (2020)