OpenRaiser/Intern-Atlas huggingface dataset:
Factorization and pseudofactorization of weighted graphs
Venue: arXiv cs.DS 2021
Year: 2021

For unweighted graphs, finding isometric embeddings is closely related to decompositions of $G$ into Cartesian products of smaller graphs. When $G$ is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of $G$. When $G$ is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of $G$. Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph $G$, where $G$ satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any $m$-edge, $n$-vertex graph with positive integer edge weights can be factored in $O(m^2)$ time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of $O(m^2+n^2\log\log n)$ time. We also show that a pseudofactorization for such a graph can be computed in $O(mn)$ time, plus the time to solve APSP, resulting in an $O(mn+n^2\log\log n)$ running time.
Swarm consensus
Venue: arXiv cs.DS 2021
Year: 2021

The strength of gnomes lies in their coordinated action. Being small and subtle creatures themselves, the forest gnomes can form large swarms acting as one giant creature. This unusual defense strategy requires a lot of skill and training. Directing a swarm is not an easy task! Initially, gnomes used leader-based control algorithms, although those have been proven to be vulnerable to abuse and failure. After thorough research and study, gnomes developed their own leaderless consensus algorithm based on very simple rules. It is based on gossip in a network of a known diameter $d$. One of the gnomes proposes a plan which then spreads gnome to gnome. If there is an agreement, gnomes act \emph{all at once}. If there are conflicting plans (an extreme rarity), they try again. The resulting upper bound on the swarm's reaction time is its round-trip time $2dt$, where $t$ is the command relay time. The original algorithm is non-Byzantine; all gnomes must be sane and sober. While working on the algorithm, gnomes discovered \emph{swarm time}, a sibling concept to L.Lamport's logical time. That led to a Byzantine-ready version of the algorithm.
Heuristic Hyperparameter Optimization for Convolutional Neural Networks using Genetic Algorithm
Venue: arXiv cs.NE 2021
Year: 2021

In recent years, people from all over the world are suffering from one of the most severe diseases in history, known as Coronavirus disease 2019, COVID-19 for short. When the virus reaches the lungs, it has a higher probability to cause lung pneumonia and sepsis. X-ray image is a powerful tool in identifying the typical features of the infection for COVID-19 patients. The radiologists and pathologists observe that ground-glass opacity appears in the chest X-ray for infected patient \cite{cozzi2021ground}, and it could be used as one of the criteria during the diagnosis process. In the past few years, deep learning has proven to be one of the most powerful methods in the field of image classification. Due to significant differences in Chest X-Ray between normal and infected people \cite{rousan2020chest}, deep models could be used to identify the presence of the disease given a patient's Chest X-Ray. Many deep models are complex, and it evolves with lots of input parameters. Designers sometimes struggle with the tuning process for deep models, especially when they build up the model from scratch. Genetic Algorithm, inspired by the biological evolution process, plays a key role in solving such complex problems. In this paper, I proposed a genetic-based approach to optimize the Convolutional Neural Network(CNN) for the Chest X-Ray classification task.
Secretary Matching With Vertex Arrivals and No Rejections
Venue: arXiv cs.DS 2021
Year: 2021

Most prior work on online matching problems has been with the flexibility of keeping some vertices unmatched. We study three related online matching problems with the constraint of matching every vertex, i.e., with no rejections. We adopt a model in which vertices arrive in uniformly random order and the non-negative edge-weights are arbitrary. For the capacitated online bipartite matching problem, in which the vertices of one side of the graph are offline and those of the other side arrive online, we give a 4.62-competitive algorithm when the capacity of each offline vertex is 2. For the online general (non-bipartite) matching problem, where all vertices arrive online, we give a 3.34-competitive algorithm. We also study the online roommate matching problem (Huzhang et al. 2017), in which each room (offline vertex) holds 2 persons (online vertices). Persons derive non-negative additive utilities from their room as well as roommate. In this model, with the goal of maximizing the social welfare, we give a 7.96-competitive algorithm. This is an improvement over the 24.72 approximation factor in (Huzhang et al. 2017).
Contention Based Proportional Fairness (CBPF) Transmission Scheme for Time Slotted Channel Hopping Networks
Venue: arXiv cs.NI 2021
Year: 2021

Time Slotted Channel Hopping (TSCH) is a Medium Access Control (MAC) protocol introduced in IEEE802.15.4e standard, addressing low power requirements of the Internet of Things (IoT) and Low Power Lossy Networks (LLNs). The 6TiSCH Operation sublayer (6top) of IEEE802.15.4e defines the schedule that includes sleep, transmit and receive routines of the nodes. However, the design of schedule is not specified by the standard. In this paper, we propose a contention based proportional fairness (CBPF) transmission scheme for TSCH networks to maximize the system throughput addressing fair allocation of resources to the nodes. We propose a convex programming based method to achieve the fairness and throughput objectives. We model TSCH MAC as a multichannel slotted aloha and analyse it for a schedule given by the 6top layer. Performance metrics like throughput, delay and energy spent per successful transmission are derived and validated through simulations. The proposed CBPF transmission scheme has been implemented in the IoT-LAB public testbed to evaluate its performance and to compare with the existing scheduling algorithms.
MuxLink: Circumventing Learning-Resilient MUX-Locking Using Graph Neural Network-based Link Prediction
Venue: arXiv cs.CR 2021
Year: 2021

Logic locking has received considerable interest as a prominent technique for protecting the design intellectual property from untrusted entities, especially the foundry. Recently, machine learning (ML)-based attacks have questioned the security guarantees of logic locking, and have demonstrated considerable success in deciphering the secret key without relying on an oracle, hence, proving to be very useful for an adversary in the fab. Such ML-based attacks have triggered the development of learning-resilient locking techniques. The most advanced state-of-the-art deceptive MUX-based locking (D-MUX) and the symmetric MUX-based locking techniques have recently demonstrated resilience against existing ML-based attacks. Both defense techniques obfuscate the design by inserting key-controlled MUX logic, ensuring that all the secret inputs to the MUXes are equiprobable. In this work, we show that these techniques primarily introduce local and limited changes to the circuit without altering the global structure of the design. By leveraging this observation, we propose a novel graph neural network (GNN)-based link prediction attack, MuxLink, that successfully breaks both the D-MUX and symmetric MUX-locking techniques, relying only on the underlying structure of the locked design, i.e., in an oracle-less setting. Our trained GNN model learns the structure of the given circuit and the composition of gates around the non-obfuscated wires, thereby generating meaningful link embeddings that help decipher the secret inputs to the MUXes. The proposed MuxLink achieves key prediction accuracy and precision up to 100% on D-MUX and symmetric MUX-locked ISCAS-85 and ITC-99 benchmarks, fully unlocking the designs. We open-source MuxLink [1].
An Adaptive Graph Pre-training Framework for Localized Collaborative Filtering
Venue: arXiv cs.IR 2021
Year: 2021

Graph neural networks (GNNs) have been widely applied in the recommendation tasks and have obtained very appealing performance. However, most GNN-based recommendation methods suffer from the problem of data sparsity in practice. Meanwhile, pre-training techniques have achieved great success in mitigating data sparsity in various domains such as natural language processing (NLP) and computer vision (CV). Thus, graph pre-training has the great potential to alleviate data sparsity in GNN-based recommendations. However, pre-training GNNs for recommendations face unique challenges. For example, user-item interaction graphs in different recommendation tasks have distinct sets of users and items, and they often present different properties. Therefore, the successful mechanisms commonly used in NLP and CV to transfer knowledge from pre-training tasks to downstream tasks such as sharing learned embeddings or feature extractors are not directly applicable to existing GNN-based recommendations models. To tackle these challenges, we delicately design an adaptive graph pre-training framework for localized collaborative filtering (ADAPT). It does not require transferring user/item embeddings, and is able to capture both the common knowledge across different graphs and the uniqueness for each graph. Extensive experimental results have demonstrated the effectiveness and superiority of ADAPT.
Modeling Image Quantization Tradeoffs for Optimal Compression
Venue: arXiv cs.IT 2021
Year: 2021

All Lossy compression algorithms employ similar compression schemes -- frequency domain transform followed by quantization and lossless encoding schemes. They target tradeoffs by quantizating high frequency data to increase compression rates which come at the cost of higher image distortion. We propose a new method of optimizing quantization tables using Deep Learning and a minimax loss function that more accurately measures the tradeoffs between rate and distortion parameters (RD) than previous methods. We design a convolutional neural network (CNN) that learns a mapping between image blocks and quantization tables in an unsupervised manner. By processing images across all channels at once, we can achieve stronger performance by also measuring tradeoffs in information loss between different channels. We initially target optimization on JPEG images but feel that this can be expanded to any lossy compressor.
Exploring Category-correlated Feature for Few-shot Image Classification
Venue: arXiv cs.CV 2021
Year: 2021

Few-shot classification aims to adapt classifiers to novel classes with a few training samples. However, the insufficiency of training data may cause a biased estimation of feature distribution in a certain class. To alleviate this problem, we present a simple yet effective feature rectification method by exploring the category correlation between novel and base classes as the prior knowledge. We explicitly capture such correlation by mapping features into a latent vector with dimension matching the number of base classes, treating it as the logarithm probability of the feature over base classes. Based on this latent vector, the rectified feature is directly constructed by a decoder, which we expect maintaining category-related information while removing other stochastic factors, and consequently being closer to its class centroid. Furthermore, by changing the temperature value in softmax, we can re-balance the feature rectification and reconstruction for better performance. Our method is generic, flexible and agnostic to any feature extractor and classifier, readily to be embedded into existing FSL approaches. Experiments verify that our method is capable of rectifying biased features, especially when the feature is far from the class centroid. The proposed approach consistently obtains considerable performance gains on three widely used benchmarks, evaluated with different backbones and classifiers. The code will be made public.
Progressive Feature Transmission for Split Inference at the Wireless Edge
Venue: arXiv cs.IT 2021
Year: 2021

In edge inference, an edge server provides remote-inference services to edge devices. This requires the edge devices to upload high-dimensional features of data samples over resource-constrained wireless channels, which creates a communication bottleneck. The conventional solution of feature pruning requires that the device has access to the inference model, which is unavailable in the current scenario of split inference. To address this issue, we propose the progressive feature transmission (ProgressFTX) protocol, which minimizes the overhead by progressively transmitting features until a target confidence level is reached. The optimal control policy of the protocol to accelerate inference is derived and it comprises two key operations. The first is importance-aware feature selection at the server, for which it is shown to be optimal to select the most important features, characterized by the largest discriminant gains of the corresponding feature dimensions. The second is transmission-termination control by the server for which the optimal policy is shown to exhibit a threshold structure. Specifically, the transmission is stopped when the incremental uncertainty reduction by further feature transmission is outweighed by its communication cost. The indices of the selected features and transmission decision are fed back to the device in each slot. The optimal policy is first derived for the tractable case of linear classification and then extended to the more complex case of classification using a convolutional neural network. Both Gaussian and fading channels are considered. Experimental results are obtained for both a statistical data model and a real dataset. It is seen that ProgressFTX can substantially reduce the communication latency compared to conventional feature pruning and random feature transmission.
Mechanism Design without Money for Fair Allocations
Venue: arXiv cs.GT 2021
Year: 2021

Fairness is well studied in the context of resource allocation. Researchers have proposed various fairness notions like envy-freeness (EF), and its relaxations, proportionality and max-min share (MMS). There is vast literature on the existential and computational aspects of such notions. While computing fair allocations, any algorithm assumes agents' truthful reporting of their valuations towards the resources. Whereas in real-world web-based applications for fair division, the agents involved are strategic and may manipulate for individual utility gain. In this paper, we study strategy-proof mechanisms without monetary transfer, which satisfies the various fairness criteria. We know that for additive valuations, designing truthful mechanisms for EF, MMS and proportionality is impossible. Here we show that there cannot be a truthful mechanism for EFX and the existing algorithms for EF1 are manipulable. We then study the particular case of single-minded agents. For this case, we provide a Serial Dictatorship Mechanism that is strategy-proof and satisfies all the fairness criteria except EF.
Levels of Autonomous Radiology
Venue: arXiv cs.CV 2021
Year: 2021

Radiology, being one of the younger disciplines of medicine with a history of just over a century, has witnessed tremendous technological advancements and has revolutionized the way we practice medicine today. In the last few decades, medical imaging modalities have generated seismic amounts of medical data. The development and adoption of Artificial Intelligence (AI) applications using this data will lead to the next phase of evolution in radiology. It will include automating laborious manual tasks such as annotations, report-generation, etc., along with the initial radiological assessment of cases to aid radiologists in their evaluation workflow. We propose a level-wise classification for the progression of automation in radiology, explaining AI assistance at each level with corresponding challenges and solutions. We hope that such discussions can help us address the challenges in a structured way and take the necessary steps to ensure the smooth adoption of new technologies in radiology.
Supervised Learning for Multi Zone Sound Field Reproduction under Harsh Environmental Conditions
Venue: arXiv cs.SD 2021
Year: 2021

This manuscript presents an approach for multi zone sound field reproduction using supervised learning. Traditional multi zone sound field reproduction methods assume constant speed of sound, neglecting nonlinear effects like wind and temperature stratification. We show how to overcome these restrictions using supervised learning of transfer functions. The quality of the solution is measured by the acoustic contrast and the reproduction error. Our results show that for the chosen setup, even with relatively small wind speeds, the acoustic contrast and reproduction error can be improved by up to 16 dB, when wind is considered in the trained model.
Machine Learning-based Prediction of Porosity for Concrete Containing Supplementary Cementitious Materials
Venue: arXiv cs.LG 2021
Year: 2021

Porosity has been identified as the key indicator of the durability properties of concrete exposed to aggressive environments. This paper applies ensemble learning to predict porosity of high-performance concrete containing supplementary cementitious materials. The concrete samples utilized in this study are characterized by eight composition features including w/b ratio, binder content, fly ash, GGBS, superplasticizer, coarse/fine aggregate ratio, curing condition and curing days. The assembled database consists of 240 data records, featuring 74 unique concrete mixture designs. The proposed machine learning algorithms are trained on 180 observations (75%) chosen randomly from the data set and then tested on the remaining 60 observations (25%). The numerical experiments suggest that the regression tree ensembles can accurately predict the porosity of concrete from its mixture compositions. Gradient boosting trees generally outperforms random forests in terms of prediction accuracy. For random forests, the out-of-bag error based hyperparameter tuning strategy is found to be much more efficient than k-Fold Cross-Validation.
TASSY -- A Text Annotation Survey System
Venue: arXiv cs.CL 2021
Year: 2021

We present a free and open-source tool for creating web-based surveys that include text annotation tasks. Existing tools offer either text annotation or survey functionality but not both. Combining the two input types is particularly relevant for investigating a reader's perception of a text which also depends on the reader's background, such as age, gender, and education. Our tool caters primarily to the needs of researchers in the Library and Information Sciences, the Social Sciences, and the Humanities who apply Content Analysis to investigate, e.g., media bias, political communication, or fake news.
Branching Time Active Inference with Bayesian Filtering
Venue: arXiv cs.LG 2021
Year: 2021

Branching Time Active Inference (Champion et al., 2021b,a) is a framework proposing to look at planning as a form of Bayesian model expansion. Its root can be found in Active Inference (Friston et al., 2016; Da Costa et al., 2020; Champion et al., 2021c), a neuroscientific framework widely used for brain modelling, as well as in Monte Carlo Tree Search (Browne et al., 2012), a method broadly applied in the Reinforcement Learning literature. Up to now, the inference of the latent variables was carried out by taking advantage of the flexibility offered by Variational Message Passing (Winn and Bishop, 2005), an iterative process that can be understood as sending messages along the edges of a factor graph (Forney, 2001). In this paper, we harness the efficiency of an alternative method for inference called Bayesian Filtering (Fox et al., 2003), which does not require the iteration of the update equations until convergence of the Variational Free Energy. Instead, this scheme alternates between two phases: integration of evidence and prediction of future states. Both of those phases can be performed efficiently and this provides a seventy times speed up over the state-of-the-art.
Towards A Reliable Ground-Truth For Biased Language Detection
Venue: arXiv cs.CL 2021
Year: 2021

Reference texts such as encyclopedias and news articles can manifest biased language when objective reporting is substituted by subjective writing. Existing methods to detect bias mostly rely on annotated data to train machine learning models. However, low annotator agreement and comparability is a substantial drawback in available media bias corpora. To evaluate data collection options, we collect and compare labels obtained from two popular crowdsourcing platforms. Our results demonstrate the existing crowdsourcing approaches' lack of data quality, underlining the need for a trained expert framework to gather a more reliable dataset. By creating such a framework and gathering a first dataset, we are able to improve Krippendorff's $α$ = 0.144 (crowdsourcing labels) to $α$ = 0.419 (expert labels). We conclude that detailed annotator training increases data quality, improving the performance of existing bias detection systems. We will continue to extend our dataset in the future.
Sentiment Dynamics of Success: Fractal Scaling of Story Arcs Predicts Reader Preferences
Venue: arXiv cs.CL 2021
Year: 2021

We explore the correlation between the sentiment arcs of H. C. Andersen's fairy tales and their popularity, measured as their average score on the platform GoodReads. Specifically, we do not conceive a story's overall sentimental trend as predictive \textit{per se}, but we focus on its coherence and predictability over time as represented by the arc's Hurst exponent. We find that degrading Hurst values tend to imply degrading quality scores, while a Hurst exponent between .55 and .65 might indicate a "sweet spot" for literary appreciation.