OpenRaiser/Intern-Atlas huggingface dataset:
Outlining and Filling: Hierarchical Query Graph Generation for Answering Complex Questions over Knowledge Graphs
Venue: arXiv cs.AI 2022
Year: 2022

Query graph construction aims to construct the correct executable SPARQL on the KG to answer natural language questions. Although recent methods have achieved good results using neural network-based query graph ranking, they suffer from three new challenges when handling more complex questions: 1) complicated SPARQL syntax, 2) huge search space, and 3) locally ambiguous query graphs. In this paper, we provide a new solution. As a preparation, we extend the query graph by treating each SPARQL clause as a subgraph consisting of vertices and edges and define a unified graph grammar called AQG to describe the structure of query graphs. Based on these concepts, we propose a novel end-to-end model that performs hierarchical autoregressive decoding to generate query graphs. The high-level decoding generates an AQG as a constraint to prune the search space and reduce the locally ambiguous query graph. The bottom-level decoding accomplishes the query graph construction by selecting appropriate instances from the preprepared candidates to fill the slots in the AQG. The experimental results show that our method greatly improves the SOTA performance on complex KGQA benchmarks. Equipped with pre-trained models, the performance of our method is further improved, achieving SOTA for all three datasets used.
A New Look at Spike-Timing-Dependent Plasticity Networks for Spatio-Temporal Feature Learning
Venue: arXiv cs.CV 2022
Year: 2022

We present new theoretical foundations for unsupervised Spike-Timing-Dependent Plasticity (STDP) learning in spiking neural networks (SNNs). In contrast to empirical parameter search used in most previous works, we provide novel theoretical grounds for SNN and STDP parameter tuning which considerably reduces design time. Using our generic framework, we propose a class of global, action-based and convolutional SNN-STDP architectures for learning spatio-temporal features from event-based cameras. We assess our methods on the N-MNIST, the CIFAR10-DVS and the IBM DVS128 Gesture datasets, all acquired with a real-world event camera. Using our framework, we report significant improvements in classification accuracy compared to both conventional state-of-the-art event-based feature descriptors (+8.2% on CIFAR10-DVS), and compared to state-of-the-art STDP-based systems (+9.3% on N-MNIST, +7.74% on IBM DVS128 Gesture). Our work contributes to both ultra-low-power learning in neuromorphic edge devices, and towards a biologically-plausible, optimization-based theory of cortical vision.
Equivariant Contrastive Learning
Venue: arXiv cs.CV 2022
Year: 2022

In state-of-the-art self-supervised learning (SSL) pre-training produces semantically good representations by encouraging them to be invariant under meaningful transformations prescribed from human knowledge. In fact, the property of invariance is a trivial instance of a broader class called equivariance, which can be intuitively understood as the property that representations transform according to the way the inputs transform. Here, we show that rather than using only invariance, pre-training that encourages non-trivial equivariance to some transformations, while maintaining invariance to other transformations, can be used to improve the semantic quality of representations. Specifically, we extend popular SSL methods to a more general framework which we name Equivariant Self-Supervised Learning (E-SSL). In E-SSL, a simple additional pre-training objective encourages equivariance by predicting the transformations applied to the input. We demonstrate E-SSL's effectiveness empirically on several popular computer vision benchmarks, e.g. improving SimCLR to 72.5% linear probe accuracy on ImageNet. Furthermore, we demonstrate usefulness of E-SSL for applications beyond computer vision; in particular, we show its utility on regression problems in photonics science. Our code, datasets and pre-trained models are available at https://github.com/rdangovs/essl to aid further research in E-SSL.
Multi-Attribute Balanced Sampling for Disentangled GAN Controls
Venue: arXiv cs.LG 2022
Year: 2022

Various controls over the generated data can be extracted from the latent space of a pre-trained GAN, as it implicitly encodes the semantics of the training data. The discovered controls allow to vary semantic attributes in the generated images but usually lead to entangled edits that affect multiple attributes at the same time. Supervised approaches typically sample and annotate a collection of latent codes, then train classifiers in the latent space to identify the controls. Since the data generated by GANs reflects the biases of the original dataset, so do the resulting semantic controls. We propose to address disentanglement by subsampling the generated data to remove over-represented co-occuring attributes thus balancing the semantics of the dataset before training the classifiers. We demonstrate the effectiveness of this approach by extracting disentangled linear directions for face manipulation on two popular GAN architectures, PGGAN and StyleGAN, and two datasets, CelebAHQ and FFHQ. We show that this approach outperforms state-of-the-art classifier-based methods while avoiding the need for disentanglement-enforcing post-processing.
Resource-Efficient Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

Federated Learning (FL) enables distributed training by learners using local data, thereby enhancing privacy and reducing communication. However, it presents numerous challenges relating to the heterogeneity of the data distribution, device capabilities, and participant availability as deployments scale, which can impact both model convergence and bias. Existing FL schemes use random participant selection to improve fairness; however, this can result in inefficient use of resources and lower quality training. In this work, we systematically address the question of resource efficiency in FL, showing the benefits of intelligent participant selection, and incorporation of updates from straggling participants. We demonstrate how these factors enable resource efficiency while also improving trained model quality.
Robust Federated Learning via Over-The-Air Computation
Venue: arXiv cs.LG 2022
Year: 2022

This paper investigates the robustness of over-the-air federated learning to Byzantine attacks. The simple averaging of the model updates via over-the-air computation makes the learning task vulnerable to random or intended modifications of the local model updates of some malicious clients. We propose a robust transmission and aggregation framework to such attacks while preserving the benefits of over-the-air computation for federated learning. For the proposed robust federated learning, the participating clients are randomly divided into groups and a transmission time slot is allocated to each group. The parameter server aggregates the results of the different groups using a robust aggregation technique and conveys the result to the clients for another training round. We also analyze the convergence of the proposed algorithm. Numerical simulations confirm the robustness of the proposed approach to Byzantine attacks.
Brain dynamics via Cumulative Auto-Regressive Self-Attention
Venue: arXiv cs.LG 2022
Year: 2022

Multivariate dynamical processes can often be intuitively described by a weighted connectivity graph between components representing each individual time-series. Even a simple representation of this graph as a Pearson correlation matrix may be informative and predictive as demonstrated in the brain imaging literature. However, there is a consensus expectation that powerful graph neural networks (GNNs) should perform better in similar settings. In this work, we present a model that is considerably shallow than deep GNNs, yet outperforms them in predictive accuracy in a brain imaging application. Our model learns the autoregressive structure of individual time series and estimates directed connectivity graphs between the learned representations via a self-attention mechanism in an end-to-end fashion. The supervised training of the model as a classifier between patients and controls results in a model that generates directed connectivity graphs and highlights the components of the time-series that are predictive for each subject. We demonstrate our results on a functional neuroimaging dataset classifying schizophrenia patients and controls.
Synthesizing Speech from Intracranial Depth Electrodes using an Encoder-Decoder Framework
Venue: arXiv cs.SD 2022
Year: 2022

Speech Neuroprostheses have the potential to enable communication for people with dysarthria or anarthria. Recent advances have demonstrated high-quality text decoding and speech synthesis from electrocorticographic grids placed on the cortical surface. Here, we investigate a less invasive measurement modality in three participants, namely stereotactic EEG (sEEG) that provides sparse sampling from multiple brain regions, including subcortical regions. To evaluate whether sEEG can also be used to synthesize audio from neural recordings, we employ a recurrent encoder-decoder model based on modern deep learning methods. We find that speech can indeed be reconstructed with correlations up to 0.8 from these minimally invasive recordings, despite limited amounts of training data. In particular, the architecture we employ naturally picks up on the temporal nature of the data and thereby outperforms an existing benchmark based on non-regressive convolutional neural networks.
A modified gravity model based on network efficiency for vital nodes identification in complex networks
Venue: arXiv cs.SI 2022
Year: 2022

Vital nodes identification is an essential problem in network science. Various methods have been proposed to solve this problem. In particular, based on the gravity model, a series of improved gravity models are proposed to find vital nodes better in complex networks. However, they still have the room to be improved. In this paper, a novel and improved gravity model, which is named network efficiency gravity centrality model (NEG), integrates gravity model and network efficiency is proposed. Compared to other methods based on different gravity models, the proposed method considers the effect of the nodes on structure robustness of the network better. To solidate the superiority of the proposed method, experiments on varieties of real-world networks are carried out.
AIT* and EIT*: Asymmetric bidirectional sampling-based path planning
Venue: arXiv cs.RO 2022
Year: 2022

Optimal path planning is the problem of finding a valid sequence of states between a start and goal that optimizes an objective. Informed path planning algorithms order their search with problem-specific knowledge expressed as heuristics and can be orders of magnitude more efficient than uninformed algorithms. Heuristics are most effective when they are both accurate and computationally inexpensive to evaluate, but these are often conflicting characteristics. This makes the selection of appropriate heuristics difficult for many problems. This paper presents two almost-surely asymptotically optimal sampling-based path planning algorithms to address this challenge, Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*). These algorithms use an asymmetric bidirectional search in which both searches continuously inform each other. This allows AIT* and EIT* to improve planning performance by simultaneously calculating and exploiting increasingly accurate, problem-specific heuristics. The benefits of AIT* and EIT* relative to other sampling-based algorithms are demonstrated on twelve problems in abstract, robotic, and biomedical domains optimizing path length and obstacle clearance. The experiments show that AIT* and EIT* outperform other algorithms on problems optimizing obstacle clearance, where a priori cost heuristics are often ineffective, and still perform well on problems minimizing path length, where such heuristics are often effective.
Analysis of Receiver Covered by Heterogeneous Receptors in Molecular Communications
Venue: arXiv cs.ET 2022
Year: 2022

This paper analyzes the channel impulse response of an absorbing receiver (RX) covered by multiple non-overlapping heterogeneous receptors with different sizes and arbitrary locations in a molecular communication system. In this system, a point transmitter (TX) is assumed to be uniformly located on a virtual sphere at a fixed distance from the RX. Considering molecule degradation during the propagation from the TX to the RX, the expected molecule hitting rate at the RX over varying locations of the TX is analyzed as a function of the size and location of each receptor. Notably, this analytical result is applicable for different numbers, sizes, and locations of receptors, and its accuracy is demonstrated via particle-based simulations. Numerical results show that (i) the expected number of absorbed molecules at the RX increases with an increasing number of receptors, when the total area of receptors on the RX surface is fixed, and (ii) evenly distributed receptors lead to the largest expected number of absorbed molecules.
Effective Guessing Has Unlikely Consequences
Venue: arXiv cs.CC 2022
Year: 2022

A classic result of Paul, Pippenger, Szemerédi and Trotter states that DTIME(n) is strictly contained in NTIME(n). The natural question then arises: could DTIME(t(n)) be contained in NTIME(n) for some superlinear time-constructible function t(n)? If such a function t(n) does exist, then there also exist effective nondeterministic guessing strategies to speed up deterministic computations. In this work, we prove limitations on the effectiveness of nondeterministic guessing to speed up deterministic computations by showing that the existence of effective nondeterministic guessing strategies would have unlikely consequences. In particular, we show that if a subpolynomial amount of nondeterministic guessing could be used to speed up deterministic computation by a polynomial factor, then P is strictly contained in NTIME(n). Furthermore, even achieving a logarithmic speedup at the cost of making every step nondeterministic would show that SAT is in NTIME(n) under appropriate encodings. Of possibly independent interest, under such encodings we also show that SAT can be decided in O(n lg n) steps on a nondeterministic multitape Turing machine, improving on the well-known O(n(lg n)^c) bound for some constant but undetermined exponent c which is at least 1.
Causal-BALD: Deep Bayesian Active Learning of Outcomes to Infer Treatment-Effects from Observational Data
Venue: arXiv cs.LG 2022
Year: 2022

Estimating personalized treatment effects from high-dimensional observational data is essential in situations where experimental designs are infeasible, unethical, or expensive. Existing approaches rely on fitting deep models on outcomes observed for treated and control populations. However, when measuring individual outcomes is costly, as is the case of a tumor biopsy, a sample-efficient strategy for acquiring each result is required. Deep Bayesian active learning provides a framework for efficient data acquisition by selecting points with high uncertainty. However, existing methods bias training data acquisition towards regions of non-overlapping support between the treated and control populations. These are not sample-efficient because the treatment effect is not identifiable in such regions. We introduce causal, Bayesian acquisition functions grounded in information theory that bias data acquisition towards regions with overlapping support to maximize sample efficiency for learning personalized treatment effects. We demonstrate the performance of the proposed acquisition strategies on synthetic and semi-synthetic datasets IHDP and CMNIST and their extensions, which aim to simulate common dataset biases and pathologies.
Constrained Form-Finding of Tension-Compression Structures using Automatic Differentiation
Venue: arXiv cs.CE 2022
Year: 2022

This paper proposes a computational approach to form-find pin-jointed, bar structures subjected to combinations of tension and compression forces. The generated equilibrium states can meet force and geometric constraints via gradient-based optimization. We achieve this by extending the combinatorial equilibrium modeling (CEM) framework in three important ways. First, we introduce a new topological object, the auxiliary trail, to expand the range of structures that can be form-found with the framework. Then, we leverage automatic differentiation (AD) to obtain an exact value of the gradient of the sequential and iterative calculations of the CEM form-finding algorithm, instead of a numerical approximation. Finally, we encapsulate our research developments into an open-source design tool written in Python that is usable across different CAD platforms and operating systems. After studying four different structures -- a self-stressed planar tensegrity, a tree canopy, a curved bridge, and a spiral staircase -- we demonstrate that our approach enables the solution of constrained form-finding problems on a diverse range of structures more efficiently than in previous work.
TimeMatch: Unsupervised Cross-Region Adaptation by Temporal Shift Estimation
Venue: arXiv cs.CV 2022
Year: 2022

The recent developments of deep learning models that capture complex temporal patterns of crop phenology have greatly advanced crop classification from Satellite Image Time Series (SITS). However, when applied to target regions spatially different from the training region, these models perform poorly without any target labels due to the temporal shift of crop phenology between regions. Although various unsupervised domain adaptation techniques have been proposed in recent years, no method explicitly learns the temporal shift of SITS and thus provides only limited benefits for crop classification. To address this, we propose TimeMatch, which explicitly accounts for the temporal shift for improved SITS-based domain adaptation. In TimeMatch, we first estimate the temporal shift from the target to the source region using the predictions of a source-trained model. Then, we re-train the model for the target region by an iterative algorithm where the estimated shift is used to generate accurate target pseudo-labels. Additionally, we introduce an open-access dataset for cross-region adaptation from SITS in four different regions in Europe. On our dataset, we demonstrate that TimeMatch outperforms all competing methods by 11% in average F1-score across five different adaptation scenarios, setting a new state-of-the-art in cross-region adaptation.
Analog MIMO Communication for One-shot Distributed Principal Component Analysis
Venue: arXiv cs.IT 2022
Year: 2022

A fundamental algorithm for data analytics at the edge of wireless networks is distributed principal component analysis (DPCA), which finds the most important information embedded in a distributed high-dimensional dataset by distributed computation of a reduced-dimension data subspace, called principal components (PCs). In this paper, to support one-shot DPCA in wireless systems, we propose a framework of analog MIMO transmission featuring the uncoded analog transmission of local PCs for estimating the global PCs. To cope with channel distortion and noise, two maximum-likelihood (global) PC estimators are presented corresponding to the cases with and without receive channel state information (CSI). The first design, termed coherent PC estimator, is derived by solving a Procrustes problem and reveals the form of regularized channel inversion where the regulation attempts to alleviate the effects of both receiver noise and data noise. The second one, termed blind PC estimator, is designed based on the subspace channel-rotation-invariance property and computes a centroid of received local PCs on a Grassmann manifold. Using the manifold-perturbation theory, tight bounds on the mean square subspace distance (MSSD) of both estimators are derived for performance evaluation. The results reveal simple scaling laws of MSSD concerning device population, data and channel signal-to-noise ratios (SNRs), and array sizes. More importantly, both estimators are found to have identical scaling laws, suggesting the dispensability of CSI to accelerate DPCA. Simulation results validate the derived results and demonstrate the promising latency performance of the proposed analog MIMO
Adversarial GLUE: A Multi-Task Benchmark for Robustness Evaluation of Language Models
Venue: arXiv cs.CL 2022
Year: 2022

Large-scale pre-trained language models have achieved tremendous success across a wide range of natural language understanding (NLU) tasks, even surpassing human performance. However, recent studies reveal that the robustness of these models can be challenged by carefully crafted textual adversarial examples. While several individual datasets have been proposed to evaluate model robustness, a principled and comprehensive benchmark is still missing. In this paper, we present Adversarial GLUE (AdvGLUE), a new multi-task benchmark to quantitatively and thoroughly explore and evaluate the vulnerabilities of modern large-scale language models under various types of adversarial attacks. In particular, we systematically apply 14 textual adversarial attack methods to GLUE tasks to construct AdvGLUE, which is further validated by humans for reliable annotations. Our findings are summarized as follows. (i) Most existing adversarial attack algorithms are prone to generating invalid or ambiguous adversarial examples, with around 90% of them either changing the original semantic meanings or misleading human annotators as well. Therefore, we perform a careful filtering process to curate a high-quality benchmark. (ii) All the language models and robust training methods we tested perform poorly on AdvGLUE, with scores lagging far behind the benign accuracy. We hope our work will motivate the development of new adversarial attacks that are more stealthy and semantic-preserving, as well as new robust language models against sophisticated adversarial attacks. AdvGLUE is available at https://adversarialglue.github.io.
Modeling Techniques for Machine Learning Fairness: A Survey
Venue: arXiv cs.LG 2022
Year: 2022

Machine learning models are becoming pervasive in high-stakes applications. Despite their clear benefits in terms of performance, the models could show discrimination against minority groups and result in fairness issues in a decision-making process, leading to severe negative impacts on the individuals and the society. In recent years, various techniques have been developed to mitigate the unfairness for machine learning models. Among them, in-processing methods have drawn increasing attention from the community, where fairness is directly taken into consideration during model design to induce intrinsically fair models and fundamentally mitigate fairness issues in outputs and representations. In this survey, we review the current progress of in-processing fairness mitigation techniques. Based on where the fairness is achieved in the model, we categorize them into explicit and implicit methods, where the former directly incorporates fairness metrics in training objectives, and the latter focuses on refining latent representation learning. Finally, we conclude the survey with a discussion of the research challenges in this community to motivate future exploration.