OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Maximal Matching and Maximal Independent Set on Hypergraphs
Venue: arXiv cs.DS 2022
Year: 2022

We investigate the distributed complexity of maximal matching and maximal independent set (MIS) in hypergraphs in the LOCAL model. A maximal matching of a hypergraph $H=(V_H,E_H)$ is a maximal disjoint set $M\subseteq E_H$ of hyperedges and an MIS $S\subseteq V_H$ is a maximal set of nodes such that no hyperedge is fully contained in $S$. Both problems can be solved by a simple sequential greedy algorithm, which can be implemented naively in $O(Δr + \log^* n)$ rounds, where $Δ$ is the maximum degree, $r$ is the rank, and $n$ is the number of nodes. We show that for maximal matching, this naive algorithm is optimal in the following sense. Any deterministic algorithm for solving the problem requires $Ω(\min\{Δr, \log_{Δr} n\})$ rounds, and any randomized one requires $Ω(\min\{Δr, \log_{Δr} \log n\})$ rounds. Hence, for any algorithm with a complexity of the form $O(f(Δ, r) + g(n))$, we have $f(Δ, r) \in Ω(Δr)$ if $g(n)$ is not too large, and in particular if $g(n) = \log^* n$ (which is the optimal asymptotic dependency on $n$ due to Linial's lower bound [FOCS'87]). Our lower bound proof is based on the round elimination framework, and its structure is inspired by a new round elimination fixed point that we give for the $Δ$-vertex coloring problem in hypergraphs. For the MIS problem on hypergraphs, we show that for $Δ\ll r$, there are significant improvements over the naive $O(Δr + \log^* n)$-round algorithm. We give two deterministic algorithms for the problem. We show that a hypergraph MIS can be computed in $O(Δ^2\cdot\log r + Δ\cdot\log r\cdot \log^* r + \log^* n)$ rounds. We further show that at the cost of a worse dependency on $Δ$, the dependency on $r$ can be removed almost entirely, by giving an algorithm with complexity $Δ^{O(Δ)}\cdot\log^* r + O(\log^* n)$.
Grounding Scene Graphs on Natural Images via Visio-Lingual Message Passing
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents a framework for jointly grounding objects that follow certain semantic relationship constraints given in a scene graph. A typical natural scene contains several objects, often exhibiting visual relationships of varied complexities between them. These inter-object relationships provide strong contextual cues toward improving grounding performance compared to a traditional object query-only-based localization task. A scene graph is an efficient and structured way to represent all the objects and their semantic relationships in the image. In an attempt towards bridging these two modalities representing scenes and utilizing contextual information for improving object localization, we rigorously study the problem of grounding scene graphs on natural images. To this end, we propose a novel graph neural network-based approach referred to as Visio-Lingual Message PAssing Graph Neural Network (VL-MPAG Net). In VL-MPAG Net, we first construct a directed graph with object proposals as nodes and an edge between a pair of nodes representing a plausible relation between them. Then a three-step inter-graph and intra-graph message passing is performed to learn the context-dependent representation of the proposals and query objects. These object representations are used to score the proposals to generate object localization. The proposed method significantly outperforms the baselines on four public datasets.
The role of prior information and computational power in Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

Science consists on conceiving hypotheses, confronting them with empirical evidence, and keeping only hypotheses which have not yet been falsified. Under deductive reasoning they are conceived in view of a theory and confronted with empirical evidence in an attempt to falsify it, and under inductive reasoning they are conceived based on observation, confronted with empirical evidence and a theory is established based on the not falsified hypotheses. When the hypotheses testing can be performed with quantitative data, the confrontation can be achieved with Machine Learning methods, whose quality is highly dependent on the hypotheses' complexity, hence on the proper insertion of prior information into the set of hypotheses seeking to decrease its complexity without loosing good hypotheses. However, Machine Learning tools have been applied under the pragmatic view of instrumentalism, which is concerned only with the performance of the methods and not with the understanding of their behavior, leading to methods which are not fully understood. In this context, we discuss how prior information and computational power can be employed to solve a learning problem, but while prior information and a careful design of the hypotheses space has as advantage the interpretability of the results, employing high computational power has the advantage of a higher performance. We discuss why learning methods which combine both should work better from an understanding and performance perspective, arguing in favor of basic theoretical research on Machine Learning, in special about how properties of classifiers may be identified in parameters of modern learning models.
Enhancing Patent Retrieval using Text and Knowledge Graph Embeddings: A Technical Note
Venue: arXiv cs.IR 2022
Year: 2022

Patent retrieval influences several applications within engineering design research, education, and practice as well as applications that concern innovation, intellectual property, and knowledge management etc. In this article, we propose a method to retrieve patents relevant to an initial set of patents, by synthesizing state-of-the-art techniques among natural language processing and knowledge graph embedding. Our method involves a patent embedding that captures text, citation, and inventor information, which individually represent different facets of knowledge communicated through a patent document. We obtain text embeddings using Sentence-BERT applied to titles and abstracts. We obtain citation and inventor embeddings through TransE that is trained using the corresponding knowledge graphs. We identify using a classification task that the concatenation of text, citation, and inventor embeddings offers a plausible representation of a patent. While the proposed patent embedding could be used to associate a pair of patents, we observe using a recall task that multiple initial patents could be associated with a target patent using mean cosine similarity, which could then be utilized to rank all target patents and retrieve the most relevant ones. We apply the proposed patent retrieval method to a set of patents corresponding to a product family and an inventor's portfolio.
Sybil-Proof Diffusion Auction in Social Networks
Venue: arXiv cs.GT 2022
Year: 2022

A diffusion auction is a market to sell commodities over a social network, where the challenge is to incentivize existing buyers to invite their neighbors in the network to join the market. Existing mechanisms have been designed to solve the challenge in various settings, aiming at desirable properties such as non-deficiency, incentive compatibility and social welfare maximization. Since the mechanisms are employed in dynamic networks with ever-changing structures, buyers could easily generate fake nodes in the network to manipulate the mechanisms for their own benefits, which is commonly known as the Sybil attack. We observe that strategic agents may gain an unfair advantage in existing mechanisms through such attacks. To resist this potential attack, we propose two diffusion auction mechanisms, the Sybil tax mechanism (STM) and the Sybil cluster mechanism (SCM), to achieve both Sybil-proofness and incentive compatibility in the single-item setting. Our proposal provides the first mechanisms to protect the interests of buyers against Sybil attacks with a mild sacrifice of social welfare and revenue.
Probing Statistical Representations For End-To-End ASR
Venue: arXiv cs.CL 2022
Year: 2022

End-to-End automatic speech recognition (ASR) models aim to learn a generalised speech representation to perform recognition. In this domain there is little research to analyse internal representation dependencies and their relationship to modelling approaches. This paper investigates cross-domain language model dependencies within transformer architectures using SVCCA and uses these insights to exploit modelling approaches. It was found that specific neural representations within the transformer layers exhibit correlated behaviour which impacts recognition performance. Altogether, this work provides analysis of the modelling approaches affecting contextual dependencies and ASR performance, and can be used to create or adapt better performing End-to-End ASR models and also for downstream tasks.
Adaptive Batch Normalization for Training Data with Heterogeneous Features
Venue: arXiv cs.LG 2022
Year: 2022

Batch Normalization (BN) is an important preprocessing step to many deep learning applications. Since it is a data-dependent process, for some homogeneous datasets it is a redundant or even a performance-degrading process. In this paper, we propose an early-stage feasibility assessment method for estimating the benefits of applying BN on the given data batches. The proposed method uses a novel threshold-based approach to classify the training data batches into two sets according to their need for normalization. The need for normalization is decided based on the feature heterogeneity of the considered batch. The proposed approach is a pre-training processing, which implies no training overhead. The evaluation results show that the proposed approach achieves better performance mostly in small batch sizes than the traditional BN using MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100 datasets. Additionally, the network stability is increased by reducing the occurrence of internal variable transformation.
Federated Hypergradient Descent
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we explore combining automatic hyperparameter tuning and optimization for federated learning (FL) in an online, one-shot procedure. We apply a principled approach on a method for adaptive client learning rate, number of local steps, and batch size. In our federated learning applications, our primary motivations are minimizing communication budget as well as local computational resources in the training pipeline. Conventionally, hyperparameter tuning methods involve at least some degree of trial-and-error, which is known to be sample inefficient. In order to address our motivations, we propose FATHOM (Federated AuTomatic Hyperparameter OptiMization) as a one-shot online procedure. We investigate the challenges and solutions of deriving analytical gradients with respect to the hyperparameters of interest. Our approach is inspired by the fact that, with the exception of local data, we have full knowledge of all components involved in our training process, and this fact can be exploited in our algorithm impactfully. We show that FATHOM is more communication efficient than Federated Averaging (FedAvg) with optimized, static valued hyperparameters, and is also more computationally efficient overall. As a communication efficient, one-shot online procedure, FATHOM solves the bottleneck of costly communication and limited local computation, by eliminating a potentially wasteful tuning process, and by optimizing the hyperparamters adaptively throughout the training procedure without trial-and-error. We show our numerical results through extensive empirical experiments with the Federated EMNIST-62 (FEMNIST) and Federated Stack Overflow (FSO) datasets, using FedJAX as our baseline framework.
Variable Parameter Analysis for Scheduling One Machine
Venue: arXiv cs.DS 2022
Year: 2022

In contrast to the fixed parameter analysis (FPA), in the variable parameter analysis (VPA) the value of the target problem parameter is not fixed, it rather depends on the structure of a given problem instance and tends to have a favorable asymptotic behavior when the size of the input increases. While applying the VPA to an intractable optimization problem with $n$ objects, the exponential-time dependence in enumeration of the feasible solution set is attributed solely to the variable parameter $ν$, $ν<<n$. As opposed to the FPA, the VPA does not imply any restriction on some problem parameters, it rather takes an advantage of a favorable nature of the problem, which permits to reduce the cost of enumeration of the solution space. Our main technical contribution is a variable parameter algorithm for a strongly $\mathsf{NP}$-hard single-machine scheduling problem to minimize maximum job lateness. The target variable parameter $ν$ is the number of jobs with some specific characteristics, the ``emerging'' ones. The solution process is separated in two phases. At phase 1 a partial solution including $n-ν$ non-emerging jobs is constructed in a low degree polynomial time. At phase 2 less than $ν!$ permutations of the $ν$ emerging jobs are considered. Each of them are incorporated into the partial schedule of phase 1. Doe to the results of an earlier conducted experimental study, $ν/n$ varied from $1/4$ for small problem instances to $1/10$ for the largest tested problem instances, so that that the ratio becomes closer to 0 for large $n$s.
Robust Time Series Chain Discovery with Incremental Nearest Neighbors
Venue: arXiv cs.LG 2022
Year: 2022

Time series motif discovery has been a fundamental task to identify meaningful repeated patterns in time series. Recently, time series chains were introduced as an expansion of time series motifs to identify the continuous evolving patterns in time series data. Informally, a time series chain (TSC) is a temporally ordered set of time series subsequences, in which every subsequence is similar to the one that precedes it, but the last and the first can be arbitrarily dissimilar. TSCs are shown to be able to reveal latent continuous evolving trends in the time series, and identify precursors of unusual events in complex systems. Despite its promising interpretability, unfortunately, we have observed that existing TSC definitions lack the ability to accurately cover the evolving part of a time series: the discovered chains can be easily cut by noise and can include non-evolving patterns, making them impractical in real-world applications. Inspired by a recent work that tracks how the nearest neighbor of a time series subsequence changes over time, we introduce a new TSC definition which is much more robust to noise in the data, in the sense that they can better locate the evolving patterns while excluding the non-evolving ones. We further propose two new quality metrics to rank the discovered chains. With extensive empirical evaluations, we demonstrate that the proposed TSC definition is significantly more robust to noise than the state of the art, and the top ranked chains discovered can reveal meaningful regularities in a variety of real world datasets.
Privacy-preserving Deep Learning based Record Linkage
Venue: arXiv cs.CR 2022
Year: 2022

Deep learning-based linkage of records across different databases is becoming increasingly useful in data integration and mining applications to discover new insights from multiple sources of data. However, due to privacy and confidentiality concerns, organisations often are not willing or allowed to share their sensitive data with any external parties, thus making it challenging to build/train deep learning models for record linkage across different organizations' databases. To overcome this limitation, we propose the first deep learning-based multi-party privacy-preserving record linkage (PPRL) protocol that can be used to link sensitive databases held by multiple different organisations. In our approach, each database owner first trains a local deep learning model, which is then uploaded to a secure environment and securely aggregated to create a global model. The global model is then used by a linkage unit to distinguish unlabelled record pairs as matches and non-matches. We utilise differential privacy to achieve provable privacy protection against re-identification attacks. We evaluate the linkage quality and scalability of our approach using several large real-world databases, showing that it can achieve high linkage quality while providing sufficient privacy protection against existing attacks.
Deep Learning based Defect classification and detection in SEM images: A Mask R-CNN approach
Venue: arXiv cs.CV 2022
Year: 2022

In this research work, we have demonstrated the application of Mask-RCNN (Regional Convolutional Neural Network), a deep-learning algorithm for computer vision and specifically object detection, to semiconductor defect inspection domain. Stochastic defect detection and classification during semiconductor manufacturing has grown to be a challenging task as we continuously shrink circuit pattern dimensions (e.g., for pitches less than 32 nm). Defect inspection and analysis by state-of-the-art optical and e-beam inspection tools is generally driven by some rule-based techniques, which in turn often causes to misclassification and thereby necessitating human expert intervention. In this work, we have revisited and extended our previous deep learning-based defect classification and detection method towards improved defect instance segmentation in SEM images with precise extent of defect as well as generating a mask for each defect category/instance. This also enables to extract and calibrate each segmented mask and quantify the pixels that make up each mask, which in turn enables us to count each categorical defect instances as well as to calculate the surface area in terms of pixels. We are aiming at detecting and segmenting different types of inter-class stochastic defect patterns such as bridge, break, and line collapse as well as to differentiate accurately between intra-class multi-categorical defect bridge scenarios (as thin/single/multi-line/horizontal/non-horizontal) for aggressive pitches as well as thin resists (High NA applications). Our proposed approach demonstrates its effectiveness both quantitatively and qualitatively.
Benchmarking Quality-Diversity Algorithms on Neuroevolution for Reinforcement Learning
Venue: arXiv cs.NE 2022
Year: 2022

We present a Quality-Diversity benchmark suite for Deep Neuroevolution in Reinforcement Learning domains for robot control. The suite includes the definition of tasks, environments, behavioral descriptors, and fitness. We specify different benchmarks based on the complexity of both the task and the agent controlled by a deep neural network. The benchmark uses standard Quality-Diversity metrics, including coverage, QD-score, maximum fitness, and an archive profile metric to quantify the relation between coverage and fitness. We also present how to quantify the robustness of the solutions with respect to environmental stochasticity by introducing corrected versions of the same metrics. We believe that our benchmark is a valuable tool for the community to compare and improve their findings. The source code is available online: https://github.com/adaptive-intelligent-robotics/QDax
Adversarial Defense via Neural Oscillation inspired Gradient Masking
Venue: arXiv cs.LG 2022
Year: 2022

Spiking neural networks (SNNs) attract great attention due to their low power consumption, low latency, and biological plausibility. As they are widely deployed in neuromorphic devices for low-power brain-inspired computing, security issues become increasingly important. However, compared to deep neural networks (DNNs), SNNs currently lack specifically designed defense methods against adversarial attacks. Inspired by neural membrane potential oscillation, we propose a novel neural model that incorporates the bio-inspired oscillation mechanism to enhance the security of SNNs. Our experiments show that SNNs with neural oscillation neurons have better resistance to adversarial attacks than ordinary SNNs with LIF neurons on kinds of architectures and datasets. Furthermore, we propose a defense method that changes model's gradients by replacing the form of oscillation, which hides the original training gradients and confuses the attacker into using gradients of 'fake' neurons to generate invalid adversarial samples. Our experiments suggest that the proposed defense method can effectively resist both single-step and iterative attacks with comparable defense effectiveness and much less computational costs than adversarial training methods on DNNs. To the best of our knowledge, this is the first work that establishes adversarial defense through masking surrogate gradients on SNNs.
Residual Skill Policies: Learning an Adaptable Skill-based Action Space for Reinforcement Learning for Robotics
Venue: arXiv cs.RO 2022
Year: 2022

Skill-based reinforcement learning (RL) has emerged as a promising strategy to leverage prior knowledge for accelerated robot learning. Skills are typically extracted from expert demonstrations and are embedded into a latent space from which they can be sampled as actions by a high-level RL agent. However, this skill space is expansive, and not all skills are relevant for a given robot state, making exploration difficult. Furthermore, the downstream RL agent is limited to learning structurally similar tasks to those used to construct the skill space. We firstly propose accelerating exploration in the skill space using state-conditioned generative models to directly bias the high-level agent towards only sampling skills relevant to a given state based on prior experience. Next, we propose a low-level residual policy for fine-grained skill adaptation enabling downstream RL agents to adapt to unseen task variations. Finally, we validate our approach across four challenging manipulation tasks that differ from those used to build the skill space, demonstrating our ability to learn across task variations while significantly accelerating exploration, outperforming prior works. Code and videos are available on our project website: https://krishanrana.github.io/reskill.
Collaborative Bi-Aggregation for Directed Graph Embedding
Venue: arXiv cs.SI 2022
Year: 2022

Directed graphs model asymmetric relationships between nodes and research on directed graph embedding is of great significance in downstream graph analysis and inference. Learning source and target embedding of nodes separately to preserve edge asymmetry has become the dominant approach, but also poses challenge for learning representations of low or even zero in/out degree nodes that are ubiquitous in sparse graphs. In this paper, a collaborative bi-directional aggregation method (COBA) for directed graphs embedding is proposed by introducing spatial-based graph convolution. Firstly, the source and target embeddings of the central node are learned by aggregating from the counterparts of the source and target neighbors, respectively; Secondly, the source/target embeddings of the zero in/out degree central nodes are enhanced by aggregating the counterparts of opposite-directional neighbors (i.e. target/source neighbors); Finally, source and target embeddings of the same node are correlated to achieve collaborative aggregation. Extensive experiments on real-world datasets demonstrate that the COBA comprehensively outperforms state-of-the-art methods on multiple tasks and meanwhile validates the effectiveness of proposed aggregation strategies.
DaI: Decrypt and Infer the Quality of Real-Time Video Streaming
Venue: arXiv cs.MM 2022
Year: 2022

Inferring the quality of network services is the vital basis of optimization for network operators. However, prevailing real-time video streaming applications adopt encryption for security, leaving it a problem to extract Quality of Service (QoS) indicators of real-time video. In this paper, we propose DaI, a traffic-based real-time video quality estimator. DaI can partially decrypt the encrypted real-time video data and applies machine learning methods to estimate key objective Quality of Experience (QoE) metrics of real-time video. According to the experimental results, DaI can estimate objective QoE metrics with an average accuracy of 79%.