OpenRaiser/Intern-Atlas huggingface dataset:
Controlling Epidemic Spread using Probabilistic Diffusion Models on Networks
Venue: arXiv cs.DS 2022
Year: 2022

The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MinINF problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most $B$ edges; similarly the MinINFNode problem involves removing at most $B$ vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of these problems remains generally open. In this paper, we present two bicriteria approximation algorithms for MinINF, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger \cite{karger:mathor99}, and works when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results to tackle the MinINFNode problem.
Tensor-based Channel Tracking for RIS-Empowered Multi-User MIMO Wireless Systems
Venue: arXiv cs.IT 2022
Year: 2022

The accurate estimation of Channel State Information (CSI) is of crucial importance for the successful operation of Multiple-Input Multiple-Output (MIMO) communication systems, especially in a Multi-User (MU) time-varying environment and when employing the emerging technology of Reconfigurable Intelligent Surfaces (RISs). Their predominantly passive nature renders the estimation of the channels involved in the user-RIS-base station link a quite challenging problem. Moreover, the time-varying nature of most of the realistic wireless channels drives up the cost of real-time channel tracking significantly, especially when RISs of massive size are deployed. In this paper, we develop a channel tracking scheme for the uplink of RIS-enabled MU MIMO systems in the presence of channel fading. The starting point is a tensor representation of the received signal and we rely on its PARAllel FACtor (PARAFAC) analysis to both get the initial estimate and track the channel time variation. Simulation results for various system settings are reported, which validate the feasibility and effectiveness of the proposed channel tracking approach.
On the Complexity of Some Variations of Sorting by Transpositions
Venue: arXiv cs.CC 2022
Year: 2022

One of the main challenges in Computational Biology is to find the evolutionary distance between two organisms. In the field of comparative genomics, one way to estimate such distance is to find a minimum cost sequence of rearrangements (large scale mutations) needed to transform one genome into another, which is called the rearrangement distance. In the past decades, these problems were studied considering many types of rearrangements (such as reversals, transpositions, transreversals, and revrevs) and considering the same weight for all rearrangements, or different weights depending on the types of rearrangements. The complexity of the problems involving reversals, transpositions, and both rearrangements is known, even though the hardness proof for the problem combining reversals and transpositions was recently given. In this paper, we enhance the knowledge for these problems by proving that models involving transpositions alongside reversals, transreversals, and revrevs are NP-hard, considering weights w1 for reversals and w2 for the other rearrangements such that w2/w1 is less than or equal to 1.5. In addition, we address a cost function related to the number of fragmentations caused by a rearrangement, proving that the problem of finding a minimum cost sorting sequence, considering the fragmentation cost function with some restrictions, is NP-hard for transpositions and the combination of reversals and transpositions.
Graph Masked Autoencoders with Transformers
Venue: arXiv cs.LG 2022
Year: 2022

Recently, transformers have shown promising performance in learning graph representations. However, there are still some challenges when applying transformers to real-world scenarios due to the fact that deep transformers are hard to train from scratch and the quadratic memory consumption w.r.t. the number of nodes. In this paper, we propose Graph Masked Autoencoders (GMAEs), a self-supervised transformer-based model for learning graph representations. To address the above two challenges, we adopt the masking mechanism and the asymmetric encoder-decoder design. Specifically, GMAE takes partially masked graphs as input, and reconstructs the features of the masked nodes. The encoder and decoder are asymmetric, where the encoder is a deep transformer and the decoder is a shallow transformer. The masking mechanism and the asymmetric design make GMAE a memory-efficient model compared with conventional transformers. We show that, when serving as a conventional self-supervised graph representation model, GMAE achieves state-of-the-art performance on both the graph classification task and the node classification task under common downstream evaluation protocols. We also show that, compared with training in an end-to-end manner from scratch, we can achieve comparable performance after pre-training and fine-tuning using GMAE while simplifying the training process.
Multivariate Time Series Forecasting with Dynamic Graph Neural ODEs
Venue: arXiv cs.LG 2022
Year: 2022

Multivariate time series forecasting has long received significant attention in real-world applications, such as energy consumption and traffic prediction. While recent methods demonstrate good forecasting abilities, they have three fundamental limitations. (i) Discrete neural architectures: Interlacing individually parameterized spatial and temporal blocks to encode rich underlying patterns leads to discontinuous latent state trajectories and higher forecasting numerical errors. (ii) High complexity: Discrete approaches complicate models with dedicated designs and redundant parameters, leading to higher computational and memory overheads. (iii) Reliance on graph priors: Relying on predefined static graph structures limits their effectiveness and practicability in real-world applications. In this paper, we address all the above limitations by proposing a continuous model to forecast $\textbf{M}$ultivariate $\textbf{T}$ime series with dynamic $\textbf{G}$raph neural $\textbf{O}$rdinary $\textbf{D}$ifferential $\textbf{E}$quations ($\texttt{MTGODE}$). Specifically, we first abstract multivariate time series into dynamic graphs with time-evolving node features and unknown graph structures. Then, we design and solve a neural ODE to complement missing graph topologies and unify both spatial and temporal message passing, allowing deeper graph propagation and fine-grained temporal information aggregation to characterize stable and precise latent spatial-temporal dynamics. Our experiments demonstrate the superiorities of $\texttt{MTGODE}$ from various perspectives on five time series benchmark datasets.
TransCG: A Large-Scale Real-World Dataset for Transparent Object Depth Completion and a Grasping Baseline
Venue: arXiv cs.RO 2022
Year: 2022

Transparent objects are common in our daily life and frequently handled in the automated production line. Robust vision-based robotic grasping and manipulation for these objects would be beneficial for automation. However, the majority of current grasping algorithms would fail in this case since they heavily rely on the depth image, while ordinary depth sensors usually fail to produce accurate depth information for transparent objects owing to the reflection and refraction of light. In this work, we address this issue by contributing a large-scale real-world dataset for transparent object depth completion, which contains 57,715 RGB-D images from 130 different scenes. Our dataset is the first large-scale, real-world dataset that provides ground truth depth, surface normals, transparent masks in diverse and cluttered scenes. Cross-domain experiments show that our dataset is more general and can enable better generalization ability for models. Moreover, we propose an end-to-end depth completion network, which takes the RGB image and the inaccurate depth map as inputs and outputs a refined depth map. Experiments demonstrate superior efficacy, efficiency and robustness of our method over previous works, and it is able to process images of high resolutions under limited hardware resources. Real robot experiments show that our method can also be applied to novel transparent object grasping robustly. The full dataset and our method are publicly available at www.graspnet.net/transcg
Multi-Objective Model Selection for Time Series Forecasting
Venue: arXiv cs.LG 2022
Year: 2022

Research on time series forecasting has predominantly focused on developing methods that improve accuracy. However, other criteria such as training time or latency are critical in many real-world applications. We therefore address the question of how to choose an appropriate forecasting model for a given dataset among the plethora of available forecasting methods when accuracy is only one of many criteria. For this, our contributions are two-fold. First, we present a comprehensive benchmark, evaluating 7 classical and 6 deep learning forecasting methods on 44 heterogeneous, publicly available datasets. The benchmark code is open-sourced along with evaluations and forecasts for all methods. These evaluations enable us to answer open questions such as the amount of data required for deep learning models to outperform classical ones. Second, we leverage the benchmark evaluations to learn good defaults that consider multiple objectives such as accuracy and latency. By learning a mapping from forecasting models to performance metrics, we show that our method PARETOSELECT is able to accurately select models from the Pareto front -- alleviating the need to train or evaluate many forecasting models for model selection. To the best of our knowledge, PARETOSELECT constitutes the first method to learn default models in a multi-objective setting.
Scheduling Complexity of Interleaving Search
Venue: arXiv cs.PL 2022
Year: 2022

miniKanren is a lightweight embedded language for logic and relational programming. Many of its useful features come from a distinctive search strategy, called interleaving search. However, with interleaving search conventional ways of reasoning about the complexity and performance of logical programs become irrelevant. We identify an important key component -- scheduling -- which makes the reasoning for miniKanren so different, and present a semi-automatic technique to estimate the scheduling impact via symbolic execution for a reasonably wide class of programs.
Domain Adaptation for Underwater Image Enhancement via Content and Style Separation
Venue: arXiv cs.CV 2022
Year: 2022

Underwater image suffer from color cast, low contrast and hazy effect due to light absorption, refraction and scattering, which degraded the high-level application, e.g, object detection and object tracking. Recent learning-based methods demonstrate astonishing performance on underwater image enhancement, however, most of these works use synthetic pair data for supervised learning and ignore the domain gap to real-world data. To solve this problem, we propose a domain adaptation framework for underwater image enhancement via content and style separation, different from prior works of domain adaptation for underwater image enhancement, which target to minimize the latent discrepancy of synthesis and real-world data, we aim to separate encoded feature into content and style latent and distinguish style latent from different domains, i.e. synthesis, real-world underwater and clean domain, and process domain adaptation and image enhancement in latent space. By latent manipulation, our model provide a user interact interface to adjust different enhanced level for continuous change. Experiment on various public real-world underwater benchmarks demonstrate that the proposed framework is capable to perform domain adaptation for underwater image enhancement and outperform various state-of-the-art underwater image enhancement algorithms in quantity and quality. The model and source code will be available at https://github.com/fordevoted/UIESS
Efficient Classification of Locally Checkable Problems in Regular Trees
Venue: arXiv cs.DC 2022
Year: 2022

We give practical, efficient algorithms that automatically determine the asymptotic distributed round complexity of a given locally checkable graph problem in the $[Θ(\log n), Θ(n)]$ region, in two settings. We present one algorithm for unrooted regular trees and another algorithm for rooted regular trees. The algorithms take the description of a locally checkable labeling problem as input, and the running time is polynomial in the size of the problem description. The algorithms decide if the problem is solvable in $O(\log n)$ rounds. If not, it is known that the complexity has to be $Θ(n^{1/k})$ for some $k = 1, 2, \dotsc$, and in this case the algorithms also output the right value of the exponent $k$. In rooted trees in the $O(\log n)$ case we can then further determine the exact complexity class by using algorithms from prior work; for unrooted trees the more fine-grained classification in the $O(\log n)$ region remains an open question.
From Utility to Capability: A New Paradigm to Conceptualize and Develop Inclusive PETs
Venue: arXiv cs.CY 2022
Year: 2022

The wider adoption of PETs has relied on usability studies, which focus mainly on an assessment of how a specified group of users interface, in particular contexts, with the technical properties of a system. While human centred efforts in usability aim to achieve important technical improvements and drive technology adoption, a focus on the usability of PETs alone is not enough. PETs development and adoption requires a broadening of focus to adequately capture the specific needs of individuals, particularly of vulnerable individuals and or individuals in marginalized populations. We argue for a departure, from the utilitarian evaluation of surface features aimed at maximizing adoption, towards a bottom up evaluation of what real opportunities humans have to use a particular system. We delineate a new paradigm for the way PETs are conceived and developed. To that end, we propose that Amartya Sen s capability approach offers a foundation for the comprehensive evaluation of the opportunities individuals have based on their personal and environmental circumstances which can, in turn, inform the evolution of PETs. This includes considerations of vulnerability, age, education, physical and mental ability, language barriers, gender, access to technology, freedom from oppression among many important contextual factors.
Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we study oracle-efficient algorithms for beyond worst-case analysis of online learning. We focus on two settings. First, the smoothed analysis setting of [RST11,HRS22] where an adversary is constrained to generating samples from distributions whose density is upper bounded by $1/σ$ times the uniform density. Second, the setting of $K$-hint transductive learning, where the learner is given access to $K$ hints per time step that are guaranteed to include the true instance. We give the first known oracle-efficient algorithms for both settings that depend only on the pseudo (or VC) dimension of the class and parameters $σ$ and $K$ that capture the power of the adversary. In particular, we achieve oracle-efficient regret bounds of $ \widetilde{O} ( \sqrt{T dσ^{-1}} ) $ and $ \widetilde{O} ( \sqrt{T dK} ) $ for learning real-valued functions and $ O ( \sqrt{T dσ^{-\frac{1}{2}} } )$ for learning binary-valued functions. For the smoothed analysis setting, our results give the first oracle-efficient algorithm for online learning with smoothed adversaries [HRS22]. This contrasts the computational separation between online learning with worst-case adversaries and offline learning established by [HK16]. Our algorithms also achieve improved bounds for worst-case setting with small domains. In particular, we give an oracle-efficient algorithm with regret of $O ( \sqrt{T(d |\mathcal{X}|)^{1/2} })$, which is a refinement of the earlier $O ( \sqrt{T|\mathcal{X}|})$ bound by [DS16].
Heuristic Adaptability to Input Dynamics for SpMM on GPUs
Venue: arXiv cs.AR 2022
Year: 2022

Sparse Matrix-Matrix Multiplication (SpMM) has served as fundamental components in various domains. Many previous studies exploit GPUs for SpMM acceleration because GPUs provide high bandwidth and parallelism. We point out that a static design does not always improve the performance of SpMM on different input data (e.g., >85\% performance loss with a single algorithm). In this paper, we consider the challenge of input dynamics from a novel auto-tuning perspective, while following issues remain to be solved: (1) Orthogonal design principles considering sparsity. Orthogonal design principles for such a sparse problem should be extracted to form different algorithms, and further used for performance tuning. (2) Nontrivial implementations in the algorithm space. Combining orthogonal design principles to create new algorithms needs to tackle with new challenges like thread race handling. (3) Heuristic adaptability to input dynamics. The heuristic adaptability is required to dynamically optimize code for input dynamics. To tackle these challenges, we first propose a novel three-loop model to extract orthogonal design principles for SpMM on GPUs. The model not only covers previous SpMM designs, but also comes up with new designs absent from previous studies. We propose techniques like conditional reduction to implement algorithms missing in previous studies. We further propose DA-SpMM, a Data-Aware heuristic GPU kernel for SpMM. DA-SpMM adaptively optimizes code considering input dynamics. Extensive experimental results show that, DA-SpMM achieves 1.26x~1.37x speedup compared with the best NVIDIA cuSPARSE algorithm on average, and brings up to 5.59x end-to-end speedup to applications like Graph Neural Networks.
Efficient and Reliable Probabilistic Interactive Learning with Structured Outputs
Venue: arXiv cs.LG 2022
Year: 2022

In this position paper, we study interactive learning for structured output spaces, with a focus on active learning, in which labels are unknown and must be acquired, and on skeptical learning, in which the labels are noisy and may need relabeling. These scenarios require expressive models that guarantee reliable and efficient computation of probabilistic quantities to measure uncertainty. We identify conditions under which a class of probabilistic models -- which we denote CRISPs -- meet all of these conditions, thus delivering tractable computation of the above quantities while preserving expressiveness. Building on prior work on tractable probabilistic circuits, we illustrate how CRISPs enable robust and efficient active and skeptical learning in large structured output spaces.
Cross-Silo Heterogeneous Model Federated Multitask Learning
Venue: arXiv cs.LG 2022
Year: 2022

Federated learning (FL) is a machine learning technique that enables participants to collaboratively train high-quality models without exchanging their private data. Participants utilizing cross-silo federated learning (CS-FL) settings are independent organizations with different task needs, and they are concerned not only with data privacy but also with independently training their unique models due to intellectual property considerations. Most existing FL methods are incapable of satisfying the above scenarios. In this study, we present a novel federated learning method CoFED based on unlabeled data pseudolabeling via a process known as cotraining. CoFED is a federated learning method that is compatible with heterogeneous models, tasks, and training processes. The experimental results suggest that the proposed method outperforms competing ones. This is especially true for non-independent and identically distributed settings and heterogeneous models, where the proposed method achieves a 35% performance improvement.
Two-stage architectural fine-tuning with neural architecture search using early-stopping in image classification
Venue: arXiv cs.CV 2022
Year: 2022

In many deep neural network (DNN) applications, the difficulty of gathering high-quality data in the industry field hinders the practical use of DNN. Thus, the concept of transfer learning has emerged, which leverages the pretrained knowledge of DNNs trained on large-scale datasets. Therefore, this paper suggests two-stage architectural fine-tuning, inspired by neural architecture search (NAS). One of main ideas is mutation, which reduces the search cost using given architectural information. Moreover, early-stopping is considered which cuts NAS costs by terminating the search process in advance. Experimental results verify our proposed method reduces 32.4% computational and 22.3% searching costs.
Generalized Inverse Based Decoding
Venue: arXiv cs.IT 2022
Year: 2022

The concept of Generalized Inverse based Decoding (GID) is introduced, as an algebraic framework for the syndrome decoding problem (SDP) and low weight codeword problem (LWP). The framework has ground on two characterizations by generalized inverses (GIs), one for the null space of a matrix and the other for the solution space of a system of linear equations over a finite field. Generic GID solvers are proposed for SDP and LWP. It is shown that information set decoding (ISD) algorithms, such as Prange, Lee-Brickell, Leon, and Stern's algorithms, are particular cases of GID solvers. All of them search GIs or elements of the null space under various specific strategies. However, as the paper shows the ISD variants do not search through the entire space, while our solvers do even when they use just one Gaussian elimination. Apart from these, our GID framework clearly shows how each ISD algorithm, except for Prange's solution, can be used as an SDP or LWP solver. A tight reduction from our problems, viewed as optimization problems, to the MIN-SAT problem is also provided. Experimental results show a very good behavior of the GID solvers. The domain of easy weights can be reached by a very few iterations and even enlarged.
On-Time Communications Over Fading Channels
Venue: arXiv cs.IT 2022
Year: 2022

We consider the on-time transmissions of a sequence of packets over a fading channel.Different from traditional in-time communications, we investigate how many packets can be received $δ$-on-time, meaning that the packet is received with a deviation no larger than $δ$ slots. In this framework, we first derive the on-time reception rate of the random transmissions over the fading channel when no controlling is used. To improve the on-time reception rate, we further propose to schedule the transmissions by delaying, dropping, or repeating the packets. Specifically, we model the scheduling over the fading channel as a Markov decision process (MDP) and then obtain the optimal scheduling policy using an efficient iterative algorithm. For a given sequence of packet transmissions, we analyze the on-time reception rate for the random transmissions and the optimal scheduling. Our analytical and simulation results show that the on-time reception rate of random transmissions decreases (to zero) with the sequence length.By using the optimal packet scheduling, the on-time reception rate converges to a much larger constant. Moreover, we show that the on-time reception rate increases if the target reception interval and/or the deviation tolerance $δ$ is increased, or the randomness of the fading channel is reduced.