ACML 2022 Papers

Multigraph matching is a recent variant of the graph matching problem. In this framework, the optimization procedure considers several graphs and enforces the consistency of the matches along the graphs. This constraint can be formalized as a cycle consistency across the pairwise permutation matrices, which implies the definition of a universe of vertex (Pachauri et al., 2013). The label of each vertex is encoded by a sparse vector and the dimension of this space corresponds to the rank of the bulk permutation matrix, the matrix built from the aggregation of all the pairwise permutation matrices. The matching problem can then be formulated as a non-convex quadratic optimization problem (QAP) under constraints imposed on the rank and the permutations. In this paper, we introduce a novel kernelized multigraph matching technique that handles vectors of attributes on both the vertices and edges of the graphs, while maintaining a low memory usage. We solve the QAP problem using a projected power optimization approach and propose several projectors leading to improved stability of the results. We provide several experiments showingthat our method is competitive against other unsupervised methods.

In many scientific problems such as video surveillance, modern genomics, and finance, data are often collected from diverse measurements across time that exhibit time-dependent heterogeneous properties. Thus, it is important to not only integrate data from multiple sources (called multi-view data), but also to incorporate time dependency for deep understanding of the underlying system. We propose a generative model based on variational autoencoder and a recurrent neural network to infer the latent dynamics for multi-view temporal data. This approach allows us to identify the disentangled latent embeddings across views while accounting for the time factor. We invoke our proposed model for analyzing three datasets on which we demonstrate the effectiveness and the interpretability of the model.

Due to the ongoing coronavirus (COVID-19) pandemic, an unprecedented amount of SARS-CoV-2 sequence data is available. The scale of this data has out-paced traditional methods for its analysis, while machine-learning approaches aimed at clustering and classification of SARS-CoV-2 variants is becoming an attractive alternative. Since the SARS-CoV-2 genome is highly dimensional, considering the much smaller spike region can save a great deal of processing. As the spike protein mediates the attachment of the coronavirus to the host cell, most of the newer and more contagious variants can be characterized by alterations to the spike protein; hence it is often sufficient for characterizing the different SARS-CoV-2 variants. Another important consideration is to have a fast feature embedding generation, which is the subject of this work. Applying any machine learning (ML) model to a biological sequence requires first transforming it into a fixed-length (numerical) form. While there exist several compact embeddings for SARS-CoV-2 spike protein sequences, the generation process is computationally expensive since the features, added to the resulting vectors, are indexed in a naïve fashion. To solve this problem, we propose a fast and alignment-free hashing-based approach to design a fixed-length feature embedding for spike protein sequences, called Hashing2Vec, which can be used as input to any standard ML model. Using real-world data, we show that the proposed embedding is not only efficient to compute but also outperforms current state-of-the-art embedding methods in terms of classification accuracy. In terms of runtime, we achieve up to a 99.8% improvement in the Hashing2Vec-based embedding generation as compared to the baselines on a set of 7K spike amino acid sequences. It also outperforms the baselines on this data in terms of predictive performance and achieves accuracy and ROC-AUC scores of 86% and 84.4%, respectively.

We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features. We follow the strategy of implicit distribution modelling via generative adversarial network (GAN) combined with permutation equivariant message passing architecture operating over the sets of nodes and edges. This enables generating the feature vectors of all the graph objects in one go (in 2 phases) as opposed to a much slower one-by-one generations of sequential models, prevents the need for expensive graph matching procedures usually needed for likelihood-based generative models, and uses efficiently the network capacity by being insensitive to the particular node ordering in the graph representation. To the best of our knowledge, this is the first method that models the feature distribution along the graph skeleton allowing for generations of annotated graphs with user specified structures. Our experiments demonstrate the ability of our model to learn complex structured distributions through quantitative evaluation over three annotated graph datasets.

Multi-source domain adaptation has been intensively studied. The distribution shift in features inherent to specific domains causes the negative transfer problem, degrading a model’s generality to unseen tasks. In Federated Learning (FL), learned model parameters are shared to train a global model that leverages the underlying knowledge across client models trained on separate data domains. Nonetheless, the data confidentiality of FL hinders the effectiveness of traditional domain adaptation methods that require prior knowledge of different domain data. We propose a new federated domain generalization method called Federated Knowledge Alignment (FedKA). FedKA leverages feature distribution matching in a global workspace such that the global model can learn domain-invariant client features under the constraint of unknown client data. FedKA employs a federated voting mechanism that generates target domain pseudo-labels based on the consensus from clients to facilitate global model fine-tuning. We performed extensive experiments, including an ablation study, to evaluate the effectiveness of the proposed method in both image and text classification tasks using different model architectures. The empirical results show that FedKA achieves performance gains of 8.8% and 3.5% in Digit-Five and Office-Caltech10, respectively, and a gain of 0.7% in Amazon Review with extremely limited training data. Moreover, we studied the effectiveness of FedKA in alleviating the negative transfer of FL based on a new criterion called Group Effect. The results show that FedKA can reduce negative transfer, improving the performance gain via model aggregation by 4 times.

Previous literature has shown that bias mitigating algorithms were sometimes prone to overfitting and had poor out-of-sample generalisation. This paper is first and foremost concerned with establishing a mathematical framework to tackle the specific issue of generalisation. Throughout this work, we consider fairness trade-offs and objectives mixing statistical loss over the whole sample and fairness penalties on categories (which could stem from different values of protected attributes), encompassing partial de-biasing. We do so by adopting two different but complementary viewpoints: first, we consider a PAC-type setup and derive probabilistic upper bounds involving sample-only information; second, we leverage an asymptotic framework to derive a closed-form limiting distribution for the difference between the empirical trade-off and the true trade-off. While these results provide guarantees for learning fairness metrics across categories, they also point out to the key (but asymmetric) role played by class imbalance. To summarise, learning fairness without having access to enough category-level samples is hard, and a simple numerical experiment shows that it can lead to spurious results.

In this work, we propose FLVoogd, an updated federated learning method in which servers and clients collaboratively eliminate Byzantine attacks while preserving privacy. In particular, servers use automatic Density-based Spatial Clustering of Applications with Noise (DBSCAN) combined with Secure Multi-party Computation (SMPC) to cluster the benign majority without acquiring sensitive personal information. Meanwhile, clients build dual models and perform test-based distance controlling to adjust their local models toward the global one to achieve personalizing. Our framework is automatic and adaptive that servers/clients don’t need to tune the parameters during the training. In addition, our framework leverages SMPC’s operations, including multiplications, additions, and comparisons, where costly operations, like division and square root, are not required. Evaluations are carried out on some conventional datasets from the image classification field. The result shows that FLVoogd can effectively reject malicious uploads in most scenarios; meanwhile, it avoids data leakage from the server side.

In the real-world, most images are saved in JPEG format, so many forged images are partially or totally composed of JPEG images and then saved in JPEG format again. In this case, exposing forged images can be accomplished by the detection of double JPEG compressions. Although the detection methods of double JPEG compressions have greatly improved, they rely on handcrafted features of image patches and cannot locate forgery at pixel-level. To break this limitation, we propose an end-to-end feature-fusion network (FF-Net) for double compression detection and forgery localization. We find that JPEG compression fingerprint primarily exists on the high-frequency component of an image, and the singly and doubly compression yield different fingerprints. Therefore, we design two encoders cooperatively to learn the compression fingerprint directly from the whole image. A decoder is deployed to locate the regions with different compression fingerprints at pixel-level based on the learned compression fingerprint. The experiment results verify that the proposed FF-Net can detect and locate the forged regions more accurately than these existing detection methods. Besides, it has a good generalization ability that the network trained on one compression case can work in numerous compression cases. Moreover, it can detect different local forgeries, including copy-move, splicing, and object-removal.

With the continuous increase of deep learning applications in safety critical systems, the need for an interpretable decision-making process has become a priority within the research community. While there are many existing explainable artificial intelligence algorithms, a systematic assessment of the suitability of global explanation methods for different applications is not available. In this paper, we respond to this demand by systematically comparing two existing global concept-based explanation methods with our proposed global, model-agnostic concept-based explanation method for time-series data. This method is based on an autoencoder structure and derives abstract global explanations called "prototypes". The results of a human user study and a quantitative analysis show a superior performance of the proposed method, but also highlight the necessity of tailoring explanation methods to the target audience of machine learning models.

Inspired by expert evaluation policy for urban perception, we proposed a novel inverse reinforcement learning (IRL) based framework for predicting urban safety and recovering the corresponding reward function. We also presented a scalable state representation method to model the prediction problem as a Markov decision process (MDP) and use reinforcement learning (RL) to solve the problem. Additionally, we built a dataset called SmallCity based on the crowdsourcing method to conduct the research. As far as we know, this is the first time the IRL approach has been introduced to the urban safety perception and planning field to help experts quantitatively analyze perceptual features. Our results showed that IRL has promising prospects in this field. We will later open-source the crowdsourcing data collection site and the model proposed in this paper.

Few-shot action recognition aims to classify novel action categories using a few training samples. Most current few-shot action recognition methods via episodic training strategy mainly use the same normalization method to normalize feature embeddings, leading to limited performance when the batch size is small. And some methods learn feature embeddings individually without considering the whole task, neglecting important interactive information between videos in the current episode. To address these problems, we propose a novel embedding adaptation network with Transformer (EANT) for few-shot action recognition. Specifically, we first propose an improved self-guided instance normalization (SGIN) module to adaptively learn class-specific feature embeddings in an input-dependent manner. Built upon the learned feature embeddings, we design a Transformer-based embedding learning (TEL) module to learn task-specific feature embeddings by fully capturing rich information cross videos in each episodic task. Furthermore, we utilize semantic knowledge among all sampled training classes as additional supervisory information to improve the generalization ability of the network. By this means, the proposed EANT can be highly effective and informative for few-shot action recognition. Extensive experiments conducted on several challenging few-shot action recognition benchmarks show that the proposed EANT outperforms several state-of-the-art methods by a large margin.

There has been much recent research on human activity recognition (HAR), due to the proliferation of wearable sensors in watches and phones, and the advances of deep learning methods, which avoid the need to manually extract features from raw sensor signals. A significant disadvantage of deep learning applied to HAR is the need for manually labelled training data, which is especially difficult to obtain for HAR datasets. Progress is starting to be made in the unsupervised setting, in the form of deep HAR clustering models, which can assign labels to data without having been given any labels to train on, but there are problems with evaluating deep HAR clustering models, which makes assessing the field and devising new methods difficult. In this paper, we highlight several distinct problems with how deep HAR clustering models are evaluated, describing these problems in detail and conducting careful experiments to explicate the effect that they can have on results. Additionally, we present a new deep clustering model for HAR. When tested under our proposed settings, our model performs better than (or on par with) existing models, while also being more efficient and scalable by avoiding the need for an autoencoder.

Neural Architecture Search (NAS) has been widely applied to automatic neural architecture design. Traditional NAS methods often evaluate a large number of architectures, leading to expensive computation overhead. To speed-up architecture search, recent NAS methods try to employ network estimation strategies for guidance of promising architecture selection. In this paper, we have proposed an efficient evolutionary algorithm for NAS, which adapts the most advanced proxy of synthetic signal bases for architecture estimation. Extensive experiments show that our method outperforms state-of-the-art NAS methods, on NAS-Bench-101 search space and NAS-Bench-201 search space (CIFAR-10, CIFAR-100 and ImageNet16-120). Compared with existing works, our method could identify better architectures with greatly reduced search time.

Neural network sparsification has received a lot of attention in recent years. A number of dynamic sparse training methods have been developed that achieve significant sparsity levels during training, ensuring comparable performance to their dense counterparts. However, most of these methods update all the model parameters using dense gradients. To this end, gradient sparsification is achieved either by non-dynamic (fixed) schedule or computationally expensive dynamic pruning schedule. To alleviate these drawbacks, we propose Dynamic Forward and Backward Sparse Training (DFBST), an algorithm which dynamically sparsifies both the forward and backward passes using trainable masks, leading to a completely sparse training schedule. In contrast to existing sparse training methods, we propose separate learning for forward as well as backward masks. Our approach achieves state of the art performance in terms of both accuracy and sparsity compared to existing dynamic pruning algorithms on benchmark datasets, namely MNIST, CIFAR-10 and CIFAR-100.

A foundational requirement of a deployed ML model is to generalize to data drawn from a testing distribution that is different from training. A popular solution to this problem is to adapt a pre-trained model to novel domains using only unlabeled data. In this paper, we focus on a challenging variant of this problem, where access to the original source data is restricted. While fully test-time adaptation (FTTA) and unsupervised domain adaptation (UDA) are closely related, the advances in UDA are not readily applicable to TTA, since most UDA methods require access to the source data. Hence, we propose a new approach, CATTAn, that bridges UDA and FTTA, by relaxing the need to access entire source data, through a novel deep subspace alignment strategy. With a minimal overhead of storing the subspace basis set for the source data, CATTAn enables unsupervised alignment between source and target data during adaptation. Through extensive experimental evaluation on multiple 2D and 3D vision benchmar ks (ImageNet-C, Office-31, OfficeHome, DomainNet, PointDA-10) and model architectures, we demonstrate significant gains in FTTA performance. Furthermore, we make a number of crucial findings on the utility of the alignment objective even with inherently robust models, pre-trained ViT representations and under low sample availability in the target domain.

High-frequency market making is a algorithmic trading strategy in which an agent provides liquidity at the same time as quoting a bid price and an ask price on a security. The strategy reap profits in the form of the spread between the quoted price placed on the buy and sell prices. Due to complexity in inventory risk, counterparties to trades and information asymmetry, the understanding of high-frequency market making algorithms is relatively unexplored by academics across disciplines. In this paper, we develop realistic simulations of limit order markets and use them to design a high-frequency market making agent using Deep Recurrent Q-Networks. Our approach outperforms a prominent benchmark strategy from literature, which uses temporal-difference reinforcement learning to design market making agents. Using the simulation framework, we analyse how the maker-take fee, a feature of market design, affects market quality and the agent’s profitability. The agents successfully reproduce stylised facts in historical trade data from each simulation.

Accumulated Local Effect (ALE) is a method for accurately estimating feature effects, overcoming fundamental failure modes of previously-existed methods, such as Partial Dependence Plots. However, \textit{ALE’s approximation}, i.e. the method for estimating ALE from the limited samples of the training set, faces two weaknesses. First, it does not scale well in cases where the input has high dimensionality, and, second, it is vulnerable to out-of-distribution (OOD) sampling when the training set is relatively small. In this paper, we propose a novel ALE approximation, called Differential Accumulated Local Effects (DALE), which can be used in cases where the ML model is differentiable and an auto-differentiable framework is accessible. Our proposal has significant computational advantages, making feature effect estimation applicable to high-dimensional Machine Learning scenarios with near-zero computational overhead. Furthermore, DALE does not create artificial points for calculating the feature effect, resolving misleading estimations due to OOD sampling. Finally, we formally prove that, under some hypotheses, DALE is an unbiased estimator of ALE and we present a method for quantifying the standard error of the explanation. Experiments using both synthetic and real datasets demonstrate the value of the proposed approach.

Deep hashing has been widely applied to large-scale image retrieval tasks owing to efficient computation and low storage cost by encoding high-dimensional image data into binary codes. Since binary codes do not contain as much information as float features, the essence of binary encoding is preserving the main context to guarantee retrieval quality. However, the existing hashing methods have great limitations on suppressing redundant background information and accurately encoding from Euclidean space to Hamming space by a simple sign function. In order to solve these problems, a Cross-Scale Context Extracted Hashing Network (CSCE-Net) is proposed in this paper. Firstly, we design a two-branch framework to capture fine-grained local information while maintaining high-level global semantic information. Besides, Attention guided Information Extraction module (AIE) is introduced between two branches, which suppresses areas of low context information cooperated with global sliding windows. Unlike previous methods, our CSCE-Net learns a content-related Dynamic Sign Function (DSF) to replace the original simple sign function. Therefore, the proposed CSCE-Net is context-sensitive and able to perform well on accurate image binary encoding. We further demonstrate that our CSCE-Net is superior to the existing hashing methods, which improves retrieval performance on standard benchmarks.

Effective learning in an visual-based environment is essential for reinforcement learning (RL) agent, while it has been empirically observed that learning from high dimensional observations such as raw pixels is sample-inefficient. For common practice, RL algorithms for image input often use encoders composed of CNNs to extract useful features from high dimensional observations. Recent studies have shown that CNNs have strong inductive bias towards image styles rather than content (i.e. agent shapes), while content is the information that RL algorithms should focus on. Inspired by this, we suggest reducing the intrinsic style bias of CNNs by proposing Contrastive Inductive Bias Controlling Networks for RL. It can help RL algorithms effectively focus on truly noteworthy information like agents’ own characteristics. Our approach incorporates two transfer networks and feature encoder with contrastive learning methods, guiding RL algorithms to learn more efficiently with sampling. Extensive experiments show that the extended framework greatly enhances the performance of existing model-free methods (i.e. SAC), enabling it to reach state-of-the-art performance on the DeepMind control suite benchmark.