OpenRaiser/Intern-Atlas huggingface dataset:
Heuristic computation of exact treewidth
Venue: arXiv cs.DS 2022
Year: 2022

We are interested in computing the treewidth $\tw(G)$ of a given graph $G$. Our approach is to design heuristic algorithms for computing a sequence of improving upper bounds and a sequence of improving lower bounds, which would hopefully converge to $\tw(G)$ from both sides. The upper bound algorithm extends and simplifies Tamaki's unpublished work on a heuristic use of the dynamic programming algorithm for deciding treewidth due to Bouchitté and Todinca. The lower bound algorithm is based on the well-known fact that, for every minor $H$ of $G$, we have $\tw(H) \leq \tw(G)$. Starting from a greedily computed minor $H_0$ of $G$, the algorithm tries to construct a sequence of minors $H_0$, $H_1$, \ldots $H_k$ with $\tw(H_i) < \tw(H_{i + 1})$ for $0 \leq i < k$ and hopefully $\tw(H_k) = \tw(G)$. We have implemented a treewidth solver based on this approach and have evaluated it on the bonus instances from the exact treewidth track of PACE 2017 algorithm implementation challenge. The results show that our approach is extremely effective in tackling instances that are hard for conventional solvers. Our solver has an additional advantage over conventional ones in that it attaches a compact certificate to the lower bound it computes.
Policy Learning and Evaluation with Randomized Quasi-Monte Carlo
Venue: arXiv cs.LG 2022
Year: 2022

Reinforcement learning constantly deals with hard integrals, for example when computing expectations in policy evaluation and policy iteration. These integrals are rarely analytically solvable and typically estimated with the Monte Carlo method, which induces high variance in policy values and gradients. In this work, we propose to replace Monte Carlo samples with low-discrepancy point sets. We combine policy gradient methods with Randomized Quasi-Monte Carlo, yielding variance-reduced formulations of policy gradient and actor-critic algorithms. These formulations are effective for policy evaluation and policy improvement, as they outperform state-of-the-art algorithms on standardized continuous control benchmarks. Our empirical analyses validate the intuition that replacing Monte Carlo with Quasi-Monte Carlo yields significantly more accurate gradient estimates.
Heterogeneous Graph Learning for Explainable Recommendation over Academic Networks
Venue: arXiv cs.SI 2022
Year: 2022

With the explosive growth of new graduates with research degrees every year, unprecedented challenges arise for early-career researchers to find a job at a suitable institution. This study aims to understand the behavior of academic job transition and hence recommend suitable institutions for PhD graduates. Specifically, we design a deep learning model to predict the career move of early-career researchers and provide suggestions. The design is built on top of scholarly/academic networks, which contains abundant information about scientific collaboration among scholars and institutions. We construct a heterogeneous scholarly network to facilitate the exploring of the behavior of career moves and the recommendation of institutions for scholars. We devise an unsupervised learning model called HAI (Heterogeneous graph Attention InfoMax) which aggregates attention mechanism and mutual information for institution recommendation. Moreover, we propose scholar attention and meta-path attention to discover the hidden relationships between several meta-paths. With these mechanisms, HAI provides ordered recommendations with explainability. We evaluate HAI upon a real-world dataset against baseline methods. Experimental results verify the effectiveness and efficiency of our approach.
Near-optimal Top-k Pattern Mining
Venue: arXiv cs.DB 2022
Year: 2022

Nowadays, frequent pattern mining (FPM) on large graphs receives increasing attention, since it is crucial to a variety of applications, e.g., social analysis. Informally, the FPM problem is defined as finding all the patterns in a large graph with frequency above a user-defined threshold. However, this problem is nontrivial due to the unaffordable computational and space costs in the mining process. In light of this, we propose a cost-effective approach to mining near-optimal top-k patterns. Our approach applies a "level-wise" strategy to incrementally detect frequent patterns, hence is able to terminate as soon as top-k patterns are discovered. Moreover, we develop a technique to compute the lower bound of support with smart traverse strategy and compact data structures. Extensive experimental studies on real-life and synthetic graphs show that our approach performs well, i.e., it outperforms traditional counterparts in efficiency, memory footprint, recall and scalability.
$\rm{C {\small IS}}^2$: A Simplified Commonsense Inference Evaluation for Story Prose
Venue: arXiv cs.CL 2022
Year: 2022

Transformers have been showing near-human performance on a variety of tasks, but they are not without their limitations. We discuss the issue of conflating results of transformers that are instructed to do multiple tasks simultaneously. In particular, we focus on the domain of commonsense reasoning within story prose, which we call contextual commonsense inference (CCI). We look at the GLUCOSE (Mostafazadeh et al. 2020) dataset and task for predicting implicit commonsense inferences between story sentences. Since the GLUCOSE task simultaneously generates sentences and predicts the CCI relation, there is a conflation in the results. Is the model really measuring CCI or is its ability to generate grammatical text carrying the results? In this paper, we introduce the task contextual commonsense inference in sentence selection ($\rm{C {\small IS}}^2$), a simplified task that avoids conflation by eliminating language generation altogether. Our findings emphasize the necessity of future work to disentangle language generation from the desired NLP tasks at hand.
CGraph: Graph Based Extensible Predictive Domain Threat Intelligence Platform
Venue: arXiv cs.CR 2022
Year: 2022

Ability to effectively investigate indicators of compromise and associated network resources involved in cyber attacks is paramount not only to identify affected network resources but also to detect related malicious resources. Today, most of the cyber threat intelligence platforms are reactive in that they can identify attack resources only after the attack is carried out. Further, these systems have limited functionality to investigate associated network resources. In this work, we propose an extensible predictive cyber threat intelligence platform called cGraph that addresses the above limitations. cGraph is built as a graph-first system where investigators can explore network resources utilizing a graph based API. Further, cGraph provides real-time predictive capabilities based on state-of-the-art inference algorithms to predict malicious domains from network graphs with a few known malicious and benign seeds. To the best of our knowledge, cGraph is the only threat intelligence platform to do so. cGraph is extensible in that additional network resources can be added to the system transparently.
Online Control of Unknown Time-Varying Dynamical Systems
Venue: arXiv cs.LG 2022
Year: 2022

We study online control of time-varying linear systems with unknown dynamics in the nonstochastic control model. At a high level, we demonstrate that this setting is \emph{qualitatively harder} than that of either unknown time-invariant or known time-varying dynamics, and complement our negative results with algorithmic upper bounds in regimes where sublinear regret is possible. More specifically, we study regret bounds with respect to common classes of policies: Disturbance Action (SLS), Disturbance Response (Youla), and linear feedback policies. While these three classes are essentially equivalent for LTI systems, we demonstrate that these equivalences break down for time-varying systems. We prove a lower bound that no algorithm can obtain sublinear regret with respect to the first two classes unless a certain measure of system variability also scales sublinearly in the horizon. Furthermore, we show that offline planning over the state linear feedback policies is NP-hard, suggesting hardness of the online learning problem. On the positive side, we give an efficient algorithm that attains a sublinear regret bound against the class of Disturbance Response policies up to the aforementioned system variability term. In fact, our algorithm enjoys sublinear \emph{adaptive} regret bounds, which is a strictly stronger metric than standard regret and is more appropriate for time-varying systems. We sketch extensions to Disturbance Action policies and partial observation, and propose an inefficient algorithm for regret against linear state feedback policies.
Turn Tree into Graph: Automatic Code Review via Simplified AST Driven Graph Convolutional Network
Venue: arXiv cs.SE 2022
Year: 2022

Automatic code review (ACR), which can relieve the costs of manual inspection, is an indispensable and essential task in software engineering. To deal with ACR, existing work is to serialize the abstract syntax tree (AST). However, making sense of the whole AST with sequence encoding approach is a daunting task, mostly due to some redundant nodes in AST hinder the transmission of node information. Not to mention that the serialized representation is inadequate to grasp the information of tree structure in AST. In this paper, we first present a new large-scale Apache Automatic Code Review (AACR) dataset for ACR task since there is still no publicly available dataset in this task. The release of this dataset would push forward the research in this field. Based on it, we propose a novel Simplified AST based Graph Convolutional Network (SimAST-GCN) to deal with ACR task. Concretely, to improve the efficiency of node information dissemination, we first simplify the AST of code by deleting the redundant nodes that do not contain connection attributes, and thus deriving a Simplified AST. Then, we construct a relation graph for each code based on the Simplified AST to properly embody the relations among code fragments of the tree structure into the graph. Subsequently, in the light of the merit of graph structure, we explore a graph convolution networks architecture that follows an attention mechanism to leverage the crucial implications of code fragments to derive code representations. Finally, we exploit a simple but effective subtraction operation in the representations between the original and revised code, enabling the revised difference to be preferably learned for deciding the results of ACR. Experimental results on the AACR dataset illustrate that our proposed model outperforms the state-of-the-art methods.
Towards a Better Understanding of Online Influence: Differences in Twitter CommunicationBetween Companies and Influencers
Venue: arXiv cs.SI 2022
Year: 2022

In the last decade, Social Media platforms such as Twitter have gained importance in the various marketing strategies of companies. This work aims to examine the presence of influential content on a textual level, by investigating characteristics of tweets in the context of social impact theory, and its dimension immediacy. To this end, we analysed influential Twitter communication data during Black Friday 2018 with methods from social media analytics such as sentiment analysis and degree centrality. Results show significant differences in communication style between companies and influencers. Companies published longer textual content and created more tweets with a positive sentiment and more first-person pronouns than influencers. These findings shall serve as a basis for a future experimental study to examine the impact of text presence on consumer cognition and the willingness to purchase.
Privacy-preserving Similarity Calculation of Speaker Features Using Fully Homomorphic Encryption
Venue: arXiv cs.CR 2022
Year: 2022

Recent advances in machine learning techniques are enabling Automated Speech Recognition (ASR) more accurate and practical. The evidence of this can be seen in the rising number of smart devices with voice processing capabilities. More and more devices around us are in-built with ASR technology. This poses serious privacy threats as speech contains unique biometric characteristics and personal data. However, the privacy concern can be mitigated if the voice features are processed in the encrypted domain. Within this context, this paper proposes an algorithm to redesign the back-end of the speaker verification system using fully homomorphic encryption techniques. The solution exploits the Cheon-Kim-Kim-Song (CKKS) fully homomorphic encryption scheme to obtain a real-time and non-interactive solution. The proposed solution contains a novel approach based on Newton Raphson method to overcome the limitation of CKKS scheme (i.e., calculating an inverse square-root of an encrypted number). This provides an efficient solution with less multiplicative depths for a negligible loss in accuracy. The proposed algorithm is validated using a well-known speech dataset. The proposed algorithm performs encrypted-domain verification in real-time (with less than 1.3 seconds delay) for a 2.8\% equal-error-rate loss compared to plain-domain verification.
VLDB 2021: Designing a Hybrid Conference
Venue: arXiv cs.DB 2022
Year: 2022

In 2020, while main database conferences one by one had to adopt a virtual format as a result of the ongoing COVID-19 pandemic, we decided to hold VLDB 2021 in hybrid format. This paper describes how we defined the hybrid format for VLDB 2021 going through the key design decisions. In addition, we list the lessons learned from running such a conference. Our goal is to share this knowledge with fellow conference organizers who target a hybrid conference format as well, which is on its way to becoming the norm rather than the exception. For readers who are more interested in the highlights rather than details, a short version of this report appears in SIGMOD Record.
Distributed k-Means with Outliers in General Metrics
Venue: arXiv cs.DC 2022
Year: 2022

Center-based clustering is a pivotal primitive for unsupervised learning and data analysis. A popular variant is undoubtedly the k-means problem, which, given a set $P$ of points from a metric space and a parameter $k<|P|$, requires to determine a subset $S$ of $k$ centers minimizing the sum of all squared distances of points in $P$ from their closest center. A more general formulation, known as k-means with $z$ outliers, introduced to deal with noisy datasets, features a further parameter $z$ and allows up to $z$ points of $P$ (outliers) to be disregarded when computing the aforementioned sum. We present a distributed coreset-based 3-round approximation algorithm for k-means with $z$ outliers for general metric spaces, using MapReduce as a computational model. Our distributed algorithm requires sublinear local memory per reducer, and yields a solution whose approximation ratio is an additive term $O(γ)$ away from the one achievable by the best known sequential (possibly bicriteria) algorithm, where $γ$ can be made arbitrarily small. An important feature of our algorithm is that it obliviously adapts to the intrinsic complexity of the dataset, captured by the doubling dimension $D$ of the metric space. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance tradeoffs for general metrics.
An Intrusion Response System utilizing Deep Q-Networks and System Partitions
Venue: arXiv cs.CR 2022
Year: 2022

Intrusion Response is a relatively new field of research. Recent approaches for the creation of Intrusion Response Systems (IRSs) use Reinforcement Learning (RL) as a primary technique for the optimal or near-optimal selection of the proper countermeasure to take in order to stop or mitigate an ongoing attack. However, most of them do not consider the fact that systems can change over time or, in other words, that systems exhibit a non-stationary behavior. Furthermore, stateful approaches, such as those based on RL, suffer the curse of dimensionality, due to a state space growing exponentially with the size of the protected system. In this paper, we introduce and develop an IRS software prototype, named irs-partition. It leverages the partitioning of the protected system and Deep Q-Networks to address the curse of dimensionality by supporting a multi-agent formulation. Furthermore, it exploits transfer learning to follow the evolution of non-stationary systems.
More to Less (M2L): Enhanced Health Recognition in the Wild with Reduced Modality of Wearable Sensors
Venue: arXiv cs.LG 2022
Year: 2022

Accurately recognizing health-related conditions from wearable data is crucial for improved healthcare outcomes. To improve the recognition accuracy, various approaches have focused on how to effectively fuse information from multiple sensors. Fusing multiple sensors is a common scenario in many applications, but may not always be feasible in real-world scenarios. For example, although combining bio-signals from multiple sensors (i.e., a chest pad sensor and a wrist wearable sensor) has been proved effective for improved performance, wearing multiple devices might be impractical in the free-living context. To solve the challenges, we propose an effective more to less (M2L) learning framework to improve testing performance with reduced sensors through leveraging the complementary information of multiple modalities during training. More specifically, different sensors may carry different but complementary information, and our model is designed to enforce collaborations among different modalities, where positive knowledge transfer is encouraged and negative knowledge transfer is suppressed, so that better representation is learned for individual modalities. Our experimental results show that our framework achieves comparable performance when compared with the full modalities. Our code and results will be available at https://github.com/compwell-org/More2Less.git.
Cost-Efficient Distributed Learning via Combinatorial Multi-Armed Bandits
Venue: arXiv cs.IT 2022
Year: 2022

We consider the distributed SGD problem, where a main node distributes gradient calculations among $n$ workers. By assigning tasks to all the workers and waiting only for the $k$ fastest ones, the main node can trade-off the algorithm's error with its runtime by gradually increasing $k$ as the algorithm evolves. However, this strategy, referred to as adaptive $k$-sync, neglects the cost of unused computations and of communicating models to workers that reveal a straggling behavior. We propose a cost-efficient scheme that assigns tasks only to $k$ workers, and gradually increases $k$. We introduce the use of a combinatorial multi-armed bandit model to learn which workers are the fastest while assigning gradient calculations. Assuming workers with exponentially distributed response times parameterized by different means, we give empirical and theoretical guarantees on the regret of our strategy, i.e., the extra time spent to learn the mean response times of the workers. Furthermore, we propose and analyze a strategy applicable to a large class of response time distributions. Compared to adaptive $k$-sync, our scheme achieves significantly lower errors with the same computational efforts and less downlink communication while being inferior in terms of speed.
Contextualize differential privacy in image database: a lightweight image differential privacy approach based on principle component analysis inverse
Venue: arXiv cs.CR 2022
Year: 2022

Differential privacy (DP) has been the de-facto standard to preserve privacy-sensitive information in database. Nevertheless, there lacks a clear and convincing contextualization of DP in image database, where individual images' indistinguishable contribution to a certain analysis can be achieved and observed when DP is exerted. As a result, the privacy-accuracy trade-off due to integrating DP is insufficiently demonstrated in the context of differentially-private image database. This work aims at contextualizing DP in image database by an explicit and intuitive demonstration of integrating conceptional differential privacy with images. To this end, we design a lightweight approach dedicating to privatizing image database as a whole and preserving the statistical semantics of the image database to an adjustable level, while making individual images' contribution to such statistics indistinguishable. The designed approach leverages principle component analysis (PCA) to reduce the raw image with large amount of attributes to a lower dimensional space whereby DP is performed, so as to decrease the DP load of calculating sensitivity attribute-by-attribute. The DP-exerted image data, which is not visible in its privatized format, is visualized through PCA inverse such that both a human and machine inspector can evaluate the privatization and quantify the privacy-accuracy trade-off in an analysis on the privatized image database. Using the devised approach, we demonstrate the contextualization of DP in images by two use cases based on deep learning models, where we show the indistinguishability of individual images induced by DP and the privatized images' retention of statistical semantics in deep learning tasks, which is elaborated by quantitative analyses on the privacy-accuracy trade-off under different privatization settings.
Vision Models Are More Robust And Fair When Pretrained On Uncurated Images Without Supervision
Venue: arXiv cs.CV 2022
Year: 2022

Discriminative self-supervised learning allows training models on any random group of internet images, and possibly recover salient information that helps differentiate between the images. Applied to ImageNet, this leads to object centric features that perform on par with supervised features on most object-centric downstream tasks. In this work, we question if using this ability, we can learn any salient and more representative information present in diverse unbounded set of images from across the globe. To do so, we train models on billions of random images without any data pre-processing or prior assumptions about what we want the model to learn. We scale our model size to dense 10 billion parameters to avoid underfitting on a large data size. We extensively study and validate our model performance on over 50 benchmarks including fairness, robustness to distribution shift, geographical diversity, fine grained recognition, image copy detection and many image classification datasets. The resulting model, not only captures well semantic information, it also captures information about artistic style and learns salient information such as geolocations and multilingual word embeddings based on visual content only. More importantly, we discover that such model is more robust, more fair, less harmful and less biased than supervised models or models trained on object centric datasets such as ImageNet.