OpenRaiser/Intern-Atlas huggingface dataset:
A simple yet effective baseline for non-attributed graph classification
Venue: arXiv cs.LG 2022
Year: 2022

Graphs are complex objects that do not lend themselves easily to typical learning tasks. Recently, a range of approaches based on graph kernels or graph neural networks have been developed for graph classification and for representation learning on graphs in general. As the developed methodologies become more sophisticated, it is important to understand which components of the increasingly complex methods are necessary or most effective. As a first step, we develop a simple yet meaningful graph representation, and explore its effectiveness in graph classification. We test our baseline representation for the graph classification task on a range of graph datasets. Interestingly, this simple representation achieves similar performance as the state-of-the-art graph kernels and graph neural networks for non-attributed graph classification. Its performance on classifying attributed graphs is slightly weaker as it does not incorporate attributes. However, given its simplicity and efficiency, we believe that it still serves as an effective baseline for attributed graph classification. Our graph representation is efficient (linear-time) to compute. We also provide a simple connection with the graph neural networks. Note that these observations are only for the task of graph classification while existing methods are often designed for a broader scope including node embedding and link prediction. The results are also likely biased due to the limited amount of benchmark datasets available. Nevertheless, the good performance of our simple baseline calls for the development of new, more comprehensive benchmark datasets so as to better evaluate and analyze different graph learning methods. Furthermore, given the computational efficiency of our graph summary, we believe that it is a good candidate as a baseline method for future graph classification (or even other graph learning) studies.
A Geometric Approach of Gradient Descent Algorithms in Linear Neural Networks
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we propose a geometric framework to analyze the convergence properties of gradient descent trajectories in the context of linear neural networks. We translate a well-known empirical observation of linear neural nets into a conjecture that we call the \emph{overfitting conjecture} which states that, for almost all training data and initial conditions, the trajectory of the corresponding gradient descent system converges to a global minimum. This would imply that the solution achieved by vanilla gradient descent algorithms is equivalent to that of the least-squares estimation, for linear neural networks of an arbitrary number of hidden layers. Built upon a key invariance property induced by the network structure, we first establish convergence of gradient descent trajectories to critical points of the square loss function in the case of linear networks of arbitrary depth. Our second result is the proof of the \emph{overfitting conjecture} in the case of single-hidden-layer linear networks with an argument based on the notion of normal hyperbolicity and under a generic property on the training data (i.e., holding for almost all training data).
Reactive Task and Motion Planning for Robust Whole-Body Dynamic Locomotion in Constrained Environments
Venue: arXiv cs.RO 2022
Year: 2022

Contact-based decision and planning methods are becoming increasingly important to endow higher levels of autonomy for legged robots. Formal synthesis methods derived from symbolic systems have great potential for reasoning about high-level locomotion decisions and achieving complex maneuvering behaviors with correctness guarantees. This study takes a first step toward formally devising an architecture composed of task planning and control of whole-body dynamic locomotion behaviors in constrained and dynamically changing environments. At the high level, we formulate a two-player temporal logic game between the multi-limb locomotion planner and its dynamic environment to synthesize a winning strategy that delivers symbolic locomotion actions. These locomotion actions satisfy the desired high-level task specifications expressed in a fragment of temporal logic. Those actions are sent to a robust finite transition system that synthesizes a locomotion controller that fulfills state reachability constraints. This controller is further executed via a low-level motion planner that generates feasible locomotion trajectories. We construct a set of dynamic locomotion models for legged robots to serve as a template library for handling diverse environmental events. We devise a replanning strategy that takes into consideration sudden environmental changes or large state disturbances to increase the robustness of the resulting locomotion behaviors. We formally prove the correctness of the layered locomotion framework guaranteeing a robust implementation by the motion planning layer. Simulations of reactive locomotion behaviors in diverse environments indicate that our framework has the potential to serve as a theoretical foundation for intelligent locomotion behaviors.
Practical Deep Reinforcement Learning Approach for Stock Trading
Venue: arXiv cs.LG 2022
Year: 2022

Stock trading strategy plays a crucial role in investment companies. However, it is challenging to obtain optimal strategy in the complex and dynamic stock market. We explore the potential of deep reinforcement learning to optimize stock trading strategy and thus maximize investment return. 30 stocks are selected as our trading stocks and their daily prices are used as the training and trading market environment. We train a deep reinforcement learning agent and obtain an adaptive trading strategy. The agent's performance is evaluated and compared with Dow Jones Industrial Average and the traditional min-variance portfolio allocation strategy. The proposed deep reinforcement learning approach is shown to outperform the two baselines in terms of both the Sharpe ratio and cumulative returns.
Weakly Supervised Silhouette-based Semantic Scene Change Detection
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents a novel semantic scene change detection scheme with only weak supervision. A straightforward approach for this task is to train a semantic change detection network directly from a large-scale dataset in an end-to-end manner. However, a specific dataset for this task, which is usually labor-intensive and time-consuming, becomes indispensable. To avoid this problem, we propose to train this kind of network from existing datasets by dividing this task into change detection and semantic extraction. On the other hand, the difference in camera viewpoints, for example, images of the same scene captured from a vehicle-mounted camera at different time points, usually brings a challenge to the change detection task. To address this challenge, we propose a new siamese network structure with the introduction of correlation layer. In addition, we collect and annotate a publicly available dataset for semantic change detection to evaluate the proposed method. The experimental results verified both the robustness to viewpoint difference in change detection task and the effectiveness for semantic change detection of the proposed networks. Our code and dataset are available at https://kensakurada.github.io/pscd.
Graph Node-Feature Convolution for Representation Learning
Venue: arXiv cs.LG 2022
Year: 2022

Graph convolutional network (GCN) is an emerging neural network approach. It learns new representation of a node by aggregating feature vectors of all neighbors in the aggregation process without considering whether the neighbors or features are useful or not. Recent methods have improved solutions by sampling a fixed size set of neighbors, or assigning different weights to different neighbors in the aggregation process, but features within a feature vector are still treated equally in the aggregation process. In this paper, we introduce a new convolution operation on regular size feature maps constructed from features of a fixed node bandwidth via sampling to get the first-level node representation, which is then passed to a standard GCN to learn the second-level node representation. Experiments show that our method outperforms competing methods in semi-supervised node classification tasks. Furthermore, our method opens new doors for exploring new GCN architectures, particularly deeper GCN models.
The CEO Problem with $r$th Power of Difference and Logarithmic Distortions
Venue: arXiv cs.IT 2022
Year: 2022

The CEO problem has received much attention since first introduced by Berger et al., but there are limited results on non-Gaussian models with non-quadratic distortion measures. In this work, we extend the quadratic Gaussian CEO problem to two non-Gaussian settings with general $r$th power of difference distortion. Assuming an identical observation channel across agents, we study the asymptotics of distortion decay as the number of agents and sum-rate, $R_{sum}$, grow without bound, while individual rates vanish. The first setting is a regular source-observation model with $r$th power of difference distortion, which subsumes the quadratic Gaussian CEO problem, and we establish that the distortion decays at $\mathcal{O}(R_{sum}^{-r/2})$ when $r \ge 2$. We use sample median estimation after the Berger-Tung scheme for achievability. The other setting is a \emph{non-regular} source-observation model, including uniform additive noise models, with $r$th power of difference distortion for which estimation-theoretic regularity conditions do not hold. The distortion decay $\mathcal{O}(R_{sum}^{-r})$ when $r \ge 1$ is obtained for the non-regular model by midrange estimator following the Berger-Tung scheme. We also provide converses based on the Shannon lower bound for the regular model and the Chazan-Zakai-Ziv bound for the non-regular model, respectively. Lastly, we provide a sufficient condition for the regular model, under which quadratic and logarithmic distortions are asymptotically equivalent by an entropy power relationship as the number of agents grows. This proof relies on the Bernstein-von Mises theorem.
Comparator automata in quantitative verification
Venue: arXiv cs.FL 2022
Year: 2022

The notion of comparison between system runs is fundamental in formal verification. This concept is implicitly present in the verification of qualitative systems, and is more pronounced in the verification of quantitative systems. In this work, we identify a novel mode of comparison in quantitative systems: the online comparison of the aggregate values of two sequences of quantitative weights. This notion is embodied by comparator automata (comparators, in short), a new class of automata that read two infinite sequences of weights synchronously and relate their aggregate values. We show that aggregate functions that can be represented with Büchi automaton result in comparators that are finite-state and accept by the Büchi condition as well. Such $ω$-regular comparators further lead to generic algorithms for a number of well-studied problems, including the quantitative inclusion and winning strategies in quantitative graph games with incomplete information, as well as related non-decision problems, such as obtaining a finite representation of all counterexamples in the quantitative inclusion problem. We study comparators for two aggregate functions: discounted-sum and limit-average. We prove that the discounted-sum comparator is $ω$-regular iff the discount-factor is an integer. Not every aggregate function, however, has an $ω$-regular comparator. Specifically, we show that the language of sequence-pairs for which limit-average aggregates exist is neither $ω$-regular nor $ω$-context-free. Given this result, we introduce the notion of prefix-average as a relaxation of limit-average aggregation, and show that it admits $ω$-context-free comparators i.e. comparator automata expressed by Büchi pushdown automata.
Reliable Agglomerative Clustering
Venue: arXiv cs.LG 2022
Year: 2022

Standard agglomerative clustering suggests establishing a new reliable linkage at every step. However, in order to provide adaptive, density-consistent and flexible solutions, we study extracting all the reliable linkages at each step, instead of the smallest one. Such a strategy can be applied with all common criteria for agglomerative hierarchical clustering. We also study that this strategy with the single linkage criterion yields a minimum spanning tree algorithm. We perform experiments on several real-world datasets to demonstrate the performance of this strategy compared to the standard alternative.
Autoencoders and Generative Adversarial Networks for Imbalanced Sequence Classification
Venue: arXiv cs.LG 2022
Year: 2022

Generative Adversarial Networks (GANs) have been used in many different applications to generate realistic synthetic data. We introduce a novel GAN with Autoencoder (GAN-AE) architecture to generate synthetic samples for variable length, multi-feature sequence datasets. In this model, we develop a GAN architecture with an additional autoencoder component, where recurrent neural networks (RNNs) are used for each component of the model in order to generate synthetic data to improve classification accuracy for a highly imbalanced medical device dataset. In addition to the medical device dataset, we also evaluate the GAN-AE performance on two additional datasets and demonstrate the application of GAN-AE to a sequence-to-sequence task where both synthetic sequence inputs and sequence outputs must be generated. To evaluate the quality of the synthetic data, we train encoder-decoder models both with and without the synthetic data and compare the classification model performance. We show that a model trained with GAN-AE generated synthetic data outperforms models trained with synthetic data generated both with standard oversampling techniques such as SMOTE and Autoencoders as well as with state of the art GAN-based models.
Mean Estimation from One-Bit Measurements
Venue: arXiv cs.IT 2022
Year: 2022

We consider the problem of estimating the mean of a symmetric log-concave distribution under the constraint that only a single bit per sample from this distribution is available to the estimator. We study the mean squared error as a function of the sample size (and hence the number of bits). We consider three settings: first, a centralized setting, where an encoder may release $n$ bits given a sample of size $n$, and for which there is no asymptotic penalty for quantization; second, an adaptive setting in which each bit is a function of the current observation and previously recorded bits, where we show that the optimal relative efficiency compared to the sample mean is precisely the efficiency of the median; lastly, we show that in a distributed setting where each bit is only a function of a local sample, no estimator can achieve optimal efficiency uniformly over the parameter space. We additionally complement our results in the adaptive setting by showing that \emph{one} round of adaptivity is sufficient to achieve optimal mean-square error.
On Output Activation Functions for Adversarial Losses: A Theoretical Analysis via Variational Divergence Minimization and An Empirical Study on MNIST Classification
Venue: arXiv cs.LG 2022
Year: 2022

Recent years have seen adversarial losses been applied to many fields. Their applications extend beyond the originally proposed generative modeling to conditional generative and discriminative settings. While prior work has proposed various output activation functions and regularization approaches, some open questions still remain unanswered. In this paper, we aim to study the following two research questions: 1) What types of output activation functions form a well-behaved adversarial loss? 2) How different combinations of output activation functions and regularization approaches perform empirically against one another? To answer the first question, we adopt the perspective of variational divergence minimization and consider an adversarial loss well-behaved if it behaves as a divergence-like measure between the data and model distributions. Using a generalized formulation for adversarial losses, we derive the necessary and sufficient conditions of a well-behaved adversarial loss. Our analysis reveals a large class of theoretically valid adversarial losses. For the second question, we propose a simple comparative framework for adversarial losses using discriminative adversarial networks. The proposed framework allows us to efficiently evaluate adversarial losses using a standard evaluation metric such as the classification accuracy. With the proposed framework, we evaluate a comprehensive set of 168 combinations of twelve output activation functions and fourteen regularization approaches on the handwritten digit classification problem to decouple their effects. Our empirical findings suggest that there is no single winning combination of output activation functions and regularization approaches across all settings. Our theoretical and empirical results may together serve as a reference for choosing or designing adversarial losses in future research.
Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division
Venue: arXiv cs.DS 2022
Year: 2022

A matching in a bipartite graph with parts X and Y is called envy-free if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-(2n-2) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-floor(2n/3) maximin-share allocation of discrete bads among n agents.
Toward a Dichotomy for Approximation of $H$-coloring
Venue: arXiv cs.DS 2022
Year: 2022

Given two (di)graphs G, H and a cost function $c:V(G)\times V(H) \to \mathbb{Q}_{\geq 0}\cup\{+\infty\}$, in the minimum cost homomorphism problem, MinHOM(H), goal is finding a homomorphism $f:V(G)\to V(H)$ (a.k.a H-coloring) that minimizes $\sum\limits_{v\in V(G)}c(v,f(v))$. The complexity of exact minimization of this problem is well understood [34], and the class of digraphs H, for which the MinHOM(H) is polynomial time solvable is a small subset of all digraphs. In this paper, we consider the approximation of MinHOM within a constant factor. For digraphs, MinHOM(H) is not approximable if H contains a digraph asteroidal triple (DAT). We take a major step toward a dichotomy classification of approximable cases. We give a dichotomy classification for approximating the MinHOM(H) when H is a graph. For digraphs, we provide constant factor approximation algorithms for two important classes of digraphs, namely bi-arc digraphs (digraphs with a conservative semi-lattice polymorphism or min-ordering), and k-arc digraphs (digraphs with an extended min-ordering). Specifically, we show that: 1. Dichotomy for Graphs: MinHOM(H) has a $2|V(H)|$-approximation algorithm if graph H admits a conservative majority polymorphims (i.e. H is a bi-arc graph), otherwise, it is inapproximable; 2. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a bi-arc digraph; 3. MinHOM(H) has a $|V(H)|^2$-approximation algorithm if H is a k-arc digraph. In conclusion, we show the importance of these results and provide insights for achieving a dichotomy classification of approximable cases. Our constant factors depend on the size of H. However, the implementation of our algorithms provides a much better approximation ratio. It leaves open to investigate a classification of digraphs H, where MinHOM(H) admits a constant factor approximation algorithm that is independent of H.
Cross-Sensor Periocular Biometrics in a Global Pandemic: Comparative Benchmark and Novel Multialgorithmic Approach
Venue: arXiv cs.CV 2022
Year: 2022

The massive availability of cameras results in a wide variability of imaging conditions, producing large intra-class variations and a significant performance drop if heterogeneous images are compared for person recognition. However, as biometrics is deployed, it is common to replace damaged or obsolete hardware, or to exchange information between heterogeneous applications. Variations in spectral bands can also occur. For example, surveillance face images (typically acquired in the visible spectrum, VIS) may need to be compared against a legacy iris database (typically acquired in near-infrared, NIR). Here, we propose a multialgorithmic approach to cope with periocular images from different sensors. With face masks in the front line against COVID-19, periocular recognition is regaining popularity since it is the only face region that remains visible. We integrate different comparators with a fusion scheme based on linear logistic regression, in which scores are represented by log-likelihood ratios. This allows easy interpretation of scores and the use of Bayes thresholds for optimal decision-making since scores from different comparators are in the same probabilistic range. We evaluate our approach in the context of the Cross-Eyed Competition, whose aim was to compare recognition approaches when NIR and VIS periocular images are matched. Our approach achieves EER=0.2% and FRR of just 0.47% at FAR=0.01%, representing the best overall approach of the competition. Experiments are also reported with a database of VIS images from different smartphones. We also discuss the impact of template size and computation times, with the most computationally heavy comparator playing an important role in the results. Lastly, the proposed method is shown to outperform other popular fusion approaches, such as the average of scores, SVMs or Random Forest.
Analyzing Data Selection Techniques with Tools from the Theory of Information Losses
Venue: arXiv cs.LG 2022
Year: 2022

In this paper, we present and illustrate some new tools for rigorously analyzing training data selection methods. These tools focus on the information theoretic losses that occur when sampling data. We use this framework to prove that two methods, Facility Location Selection and Transductive Experimental Design, reduce these losses. These are meant to act as generalizable theoretical examples of applying the field of Information Theoretic Deep Learning Theory to the fields of data selection and active learning. Both analyses yield insight into their respective methods and increase their interpretability. In the case of Transductive Experimental Design, the provided analysis greatly increases the method's scope as well.