OpenRaiser/Intern-Atlas huggingface dataset:
A contraction-recursive algorithm for treewidth
Venue: arXiv cs.DS 2023
Year: 2023

Let tw(G) denote the treewidth of graph G. Given a graph G and a positive integer k such that tw(G) <= k + 1, we are to decide if tw(G) <= k. We give a certifying algorithm RTW ("R" for recursive) for this task: it returns one or more tree-decompositions of G of width <= k if the answer is YES and a minimal contraction H of G such that tw(H) > k otherwise. RTW uses a heuristic variant of Tamaki's PID algorithm for treewidth (ESA2017), which we call HPID. RTW, given G and k, interleaves the execution of HPID with recursive calls on G /e for edges e of G, where G / e denotes the graph obtained from G by contracting edge e. If we find that tw(G / e) > k, then we have tw(G) > k with the same certificate. If we find that tw(G / e) <= k, we "uncontract" the bags of the certifying tree-decompositions of G / e into bags of G and feed them to HPID to help progress. If the question is not resolved after the recursive calls are made for all edges, we finish HPID in an exhaustive mode. If it turns out that tw(G) > k, then G is a certificate for tw(G') > k for every G' of which G is a contraction, because we have found tw(G / e) <= k for every edge e of G. This final round of HPID guarantees the correctness of the algorithm, while its practical efficiency derives from our methods of "uncontracting" bags of tree-decompositions of G / e to useful bags of G, as well as of exploiting those bags in HPID. Experiments show that our algorithm drastically extends the scope of practically solvable instances. In particular, when applied to the 100 instances in the PACE 2017 bonus set, the number of instances solved by our implementation on a typical laptop, with the timeout of 100, 1000, and 10000 seconds per instance, are 72, 92, and 98 respectively, while these numbers are 11, 38, and 68 for Tamaki's PID solver and 65, 82, and 85 for his new solver (SEA 2022).
Twisted Cubes and their Applications in Type Theory
Venue: arXiv cs.LO 2023
Year: 2023

This thesis captures the ongoing development of twisted cubes, which is a modification of cubes (in a topological sense) where its homotopy type theory does not require paths or higher paths to be invertible. My original motivation to develop the twisted cubes was to resolve the incompatibility between cubical type theory and directed type theory. The development of twisted cubes is still in the early stages and the intermediate goal, for now, is to define a twisted cube category and its twisted cubical sets that can be used to construct a potential definition of (infinity, n)-categories. The intermediate goal above leads me to discover a novel framework that uses graph theory to transform convex polytopes, such as simplices and (standard) cubes, into base categories. Intuitively, an n-dimensional polytope is transformed into a directed graph consists 0-faces (extreme points) of the polytope as its nodes and 1-faces of the polytope as its edges. Then, we define the base category as the full subcategory of the graph category induced by the family of these graphs from all n-dimensional cases. With this framework, the modification from cubes to twisted cubes can formally be done by reversing some edges of cube graphs. Equivalently, the twisted n-cube graph is the result of a certain endofunctor being applied n times to the singleton graph; this endofunctor (called twisted prism functor) duplicates the input, reverses all edges in the first copy, and then pairwisely links nodes from the first copy to the second copy. The core feature of a twisted graph is its unique Hamiltonian path, which is useful to prove many properties of twisted cubes. In particular, the reflexive transitive closure of a twisted graph is isomorphic to the simplex graph counterpart, which remarkably suggests that twisted cubes not only relate to (standard) cubes but also simplices.
Minimizing Age of Information for Mobile Edge Computing Systems: A Nested Index Approach
Venue: arXiv cs.AI 2023
Year: 2023

Exploiting the computational heterogeneity of mobile devices and edge nodes, mobile edge computation (MEC) provides an efficient approach to achieving real-time applications that are sensitive to information freshness, by offloading tasks from mobile devices to edge nodes. We use the metric Age-of-Information (AoI) to evaluate information freshness. An efficient solution to minimize the AoI for the MEC system with multiple users is non-trivial to obtain due to the random computing time. In this paper, we consider multiple users offloading tasks to heterogeneous edge servers in a MEC system. We first reformulate the problem as a Restless Multi-Arm-Bandit (RMAB) problem and establish a hierarchical Markov Decision Process (MDP) to characterize the updating of AoI for the MEC system. Based on the hierarchical MDP, we propose a nested index framework and design a nested index policy with provably asymptotic optimality. Finally, the closed form of the nested index is obtained, which enables the performance tradeoffs between computation complexity and accuracy. Our algorithm leads to an optimality gap reduction of up to 40%, compared to benchmarks. Our algorithm asymptotically approximates the lower bound as the system scalar gets large enough.
Adversarial Learning in Real-World Fraud Detection: Challenges and Perspectives
Venue: arXiv cs.LG 2023
Year: 2023

Data economy relies on data-driven systems and complex machine learning applications are fueled by them. Unfortunately, however, machine learning models are exposed to fraudulent activities and adversarial attacks, which threaten their security and trustworthiness. In the last decade or so, the research interest on adversarial machine learning has grown significantly, revealing how learning applications could be severely impacted by effective attacks. Although early results of adversarial machine learning indicate the huge potential of the approach to specific domains such as image processing, still there is a gap in both the research literature and practice regarding how to generalize adversarial techniques in other domains and applications. Fraud detection is a critical defense mechanism for data economy, as it is for other applications as well, which poses several challenges for machine learning. In this work, we describe how attacks against fraud detection systems differ from other applications of adversarial machine learning, and propose a number of interesting directions to bridge this gap.
A New Learning Approach for Noise Reduction
Venue: arXiv cs.CE 2023
Year: 2023

Noise is a part of data whether the data is from measurement, experiment or ... A few techniques are suggested for noise reduction to improve the data quality in recent years some of which are based on wavelet, orthogonalization and neural networks. The computational cost of existing methods are more than expected and that's why their application in some cases is not beneficial. In this paper, we suggest a low cost techniques based on special linear algebra structures (tridiagonal systems) to improve the signal quality. In this method, we suggest a tridiagonal model for the noise around the most noisy elements. To update the predicted noise, the algorithm is equipped with a learning/feedback approach. The details are described below and based on presented numerical results this algorithm is successful in computing the noise with lower MSE (mean squared error) in computation time specially when the data size is lower than 5000. Our algorithm is used for low-range noise while for high-range noise it is sufficient to use the presented algorithm in hybrid with moving average. The algorithm is implemented in MATLAB 2019b on a computer with Windows 11 having 8GB RAM. It is then tested over many randomly generated experiments. The numerical results confirm the efficiency of presented algorithm in most cases in comparison with existing methods.
Spatio-Temporal Surrogates for Interaction of a Jet with High Explosives: Part I -- Analysis with a Small Sample Size
Venue: arXiv cs.LG 2023
Year: 2023

Computer simulations, especially of complex phenomena, can be expensive, requiring high-performance computing resources. Often, to understand a phenomenon, multiple simulations are run, each with a different set of simulation input parameters. These data are then used to create an interpolant, or surrogate, relating the simulation outputs to the corresponding inputs. When the inputs and outputs are scalars, a simple machine learning model can suffice. However, when the simulation outputs are vector valued, available at locations in two or three spatial dimensions, often with a temporal component, creating a surrogate is more challenging. In this report, we use a two-dimensional problem of a jet interacting with high explosives to understand how we can build high-quality surrogates. The characteristics of our data set are unique - the vector-valued outputs from each simulation are available at over two million spatial locations; each simulation is run for a relatively small number of time steps; the size of the computational domain varies with each simulation; and resource constraints limit the number of simulations we can run. We show how we analyze these extremely large data-sets, set the parameters for the algorithms used in the analysis, and use simple ways to improve the accuracy of the spatio-temporal surrogates without substantially increasing the number of simulations required.
Linear-time Computation of DAWGs, Symmetric Indexing Structures, and MAWs for Integer Alphabets
Venue: arXiv cs.DS 2023
Year: 2023

The directed acyclic word graph (DAWG) of a string $y$ of length $n$ is the smallest (partial) DFA which recognizes all suffixes of $y$ with only $O(n)$ nodes and edges. In this paper, we show how to construct the DAWG for the input string $y$ from the suffix tree for $y$, in $O(n)$ time for integer alphabets of polynomial size in $n$. In so doing, we first describe a folklore algorithm which, given the suffix tree for $y$, constructs the DAWG for the reversed string of $y$ in $O(n)$ time. Then, we present our algorithm that builds the DAWG for $y$ in $O(n)$ time for integer alphabets, from the suffix tree for $y$. We also show that a straightforward modification to our DAWG construction algorithm leads to the first $O(n)$-time algorithm for constructing the affix tree of a given string $y$ over an integer alphabet. Affix trees are a text indexing structure supporting bidirectional pattern searches. We then discuss how our constructions can lead to linear-time algorithms for building other text indexing structures, such as linear-size suffix tries and symmetric CDAWGs in linear time in the case of integer alphabets. As a further application to our $O(n)$-time DAWG construction algorithm, we show that the set $\mathsf{MAW}(y)$ of all minimal absent words (MAWs) of $y$ can be computed in optimal, input- and output-sensitive $O(n + |\mathsf{MAW}(y)|)$ time and $O(n)$ working space for integer alphabets.
PIMCOMP: A Universal Compilation Framework for Crossbar-based PIM DNN Accelerators
Venue: arXiv cs.AR 2023
Year: 2023

Crossbar-based PIM DNN accelerators can provide massively parallel in-situ operations. A specifically designed compiler is important to achieve high performance for a wide variety of DNN workloads. However, some key compilation issues such as parallelism considerations, weight replication selection, and array mapping methods have not been solved. In this work, we propose PIMCOMP - a universal compilation framework for NVM crossbar-based PIM DNN accelerators. PIMCOMP is built on an abstract PIM accelerator architecture, which is compatible with the widely used Crossbar/IMA/Tile/Chip hierarchy. On this basis, we propose four general compilation stages for crossbar-based PIM accelerators: node partitioning, weight replicating, core mapping, and dataflow scheduling. We design two compilation modes with different inter-layer pipeline granularities to support high-throughput and low-latency application scenarios, respectively. Our experimental results show that PIMCMOP yields improvements of 1.6$\times$ and 2.4$\times$ in throughput and latency, respectively, relative to PUMA.
Relation-aware graph structure embedding with co-contrastive learning for drug-drug interaction prediction
Venue: arXiv cs.LG 2023
Year: 2023

Relation-aware graph structure embedding is promising for predicting multi-relational drug-drug interactions (DDIs). Typically, most existing methods begin by constructing a multi-relational DDI graph and then learning relation-aware graph structure embeddings (RaGSEs) of drugs from the DDI graph. Nevertheless, most existing approaches are usually limited in learning RaGSEs of new drugs, leading to serious over-fitting when the test DDIs involve such drugs. To alleviate this issue, we propose a novel DDI prediction method based on relation-aware graph structure embedding with co-contrastive learning, RaGSECo. The proposed RaGSECo constructs two heterogeneous drug graphs: a multi-relational DDI graph and a multi-attribute drug-drug similarity (DDS) graph. The two graphs are used respectively for learning and propagating the RaGSEs of drugs, aiming to ensure all drugs, including new ones, can possess effective RaGSEs. Additionally, we present a novel co-contrastive learning module to learn drug-pairs (DPs) representations. This mechanism learns DP representations from two distinct views (interaction and similarity views) and encourages these views to supervise each other collaboratively to obtain more discriminative DP representations. We evaluate the effectiveness of our RaGSECo on three different tasks using two real datasets. The experimental results demonstrate that RaGSECo outperforms existing state-of-the-art prediction methods.
LPN: Language-guided Prototypical Network for few-shot classification
Venue: arXiv cs.CV 2023
Year: 2023

Few-shot classification aims to adapt to new tasks with limited labeled examples. To fully use the accessible data, recent methods explore suitable measures for the similarity between the query and support images and better high-dimensional features with meta-training and pre-training strategies. However, the potential of multi-modality information has barely been explored, which may bring promising improvement for few-shot classification. In this paper, we propose a Language-guided Prototypical Network (LPN) for few-shot classification, which leverages the complementarity of vision and language modalities via two parallel branches to improve the classifier. Concretely, to introduce language modality with limited samples in the visual task, we leverage a pre-trained text encoder to extract class-level text features directly from class names while processing images with a conventional image encoder. Then, we introduce a language-guided decoder to obtain text features corresponding to each image by aligning class-level features with visual features. Additionally, we utilize class-level features and prototypes to build a refined prototypical head, which generates robust prototypes in the text branch for follow-up measurement. Furthermore, we leverage the class-level features to align the visual features, capturing more class-relevant visual features. Finally, we aggregate the visual and text logits to calibrate the deviation of a single modality, enhancing the overall performance. Extensive experiments demonstrate the competitiveness of LPN against state-of-the-art methods on benchmark datasets.
Exploiting Richness of Learned Compressed Representation of Images for Semantic Segmentation
Venue: arXiv cs.CV 2023
Year: 2023

Autonomous vehicles and Advanced Driving Assistance Systems (ADAS) have the potential to radically change the way we travel. Many such vehicles currently rely on segmentation and object detection algorithms to detect and track objects around its surrounding. The data collected from the vehicles are often sent to cloud servers to facilitate continual/life-long learning of these algorithms. Considering the bandwidth constraints, the data is compressed before sending it to servers, where it is typically decompressed for training and analysis. In this work, we propose the use of a learning-based compression Codec to reduce the overhead in latency incurred for the decompression operation in the standard pipeline. We demonstrate that the learned compressed representation can also be used to perform tasks like semantic segmentation in addition to decompression to obtain the images. We experimentally validate the proposed pipeline on the Cityscapes dataset, where we achieve a compression factor up to $66 \times$ while preserving the information required to perform segmentation with a dice coefficient of $0.84$ as compared to $0.88$ achieved using decompressed images while reducing the overall compute by $11\%$.
Learning to Prompt in the Classroom to Understand AI Limits: A pilot study
Venue: arXiv cs.HC 2023
Year: 2023

Artificial intelligence's (AI) progress holds great promise in tackling pressing societal concerns such as health and climate. Large Language Models (LLM) and the derived chatbots, like ChatGPT, have highly improved the natural language processing capabilities of AI systems allowing them to process an unprecedented amount of unstructured data. However, the ensuing excitement has led to negative sentiments, even as AI methods demonstrate remarkable contributions (e.g. in health and genetics). A key factor contributing to this sentiment is the misleading perception that LLMs can effortlessly provide solutions across domains, ignoring their limitations such as hallucinations and reasoning constraints. Acknowledging AI fallibility is crucial to address the impact of dogmatic overconfidence in possibly erroneous suggestions generated by LLMs. At the same time, it can reduce fear and other negative attitudes toward AI. This necessitates comprehensive AI literacy interventions that educate the public about LLM constraints and effective usage techniques, i.e prompting strategies. With this aim, a pilot educational intervention was performed in a high school with 21 students. It involved presenting high-level concepts about intelligence, AI, and LLMs, followed by practical exercises involving ChatGPT in creating natural educational conversations and applying established prompting strategies. Encouraging preliminary results emerged, including high appreciation of the activity, improved interaction quality with the LLM, reduced negative AI sentiments, and a better grasp of limitations, specifically unreliability, limited understanding of commands leading to unsatisfactory responses, and limited presentation flexibility. Our aim is to explore AI acceptance factors and refine this approach for more controlled future studies.
Separated RoadTopoFormer
Venue: arXiv cs.CV 2023
Year: 2023

Understanding driving scenarios is crucial to realizing autonomous driving. Previous works such as map learning and BEV lane detection neglect the connection relationship between lane instances, and traffic elements detection tasks usually neglect the relationship with lane lines. To address these issues, the task is presented which includes 4 sub-tasks, the detection of traffic elements, the detection of lane centerlines, reasoning connection relationships among lanes, and reasoning assignment relationships between lanes and traffic elements. We present Separated RoadTopoFormer to tackle the issues, which is an end-to-end framework that detects lane centerline and traffic elements with reasoning relationships among them. We optimize each module separately to prevent interaction with each other and aggregate them together with few finetunes. For two detection heads, we adopted a DETR-like architecture to detect objects, and for the relationship head, we concat two instance features from front detectors and feed them to the classifier to obtain relationship probability. Our final submission achieves 0.445 OLS, which is competitive in both sub-task and combined scores.
Secure Deep Learning-based Distributed Intelligence on Pocket-sized Drones
Venue: arXiv cs.RO 2023
Year: 2023

Palm-sized nano-drones are an appealing class of edge nodes, but their limited computational resources prevent running large deep-learning models onboard. Adopting an edge-fog computational paradigm, we can offload part of the computation to the fog; however, this poses security concerns if the fog node, or the communication link, can not be trusted. To tackle this concern, we propose a novel distributed edge-fog execution scheme that validates fog computation by redundantly executing a random subnetwork aboard our nano-drone. Compared to a State-of-the-Art visual pose estimation network that entirely runs onboard, a larger network executed in a distributed way improves the $R^2$ score by +0.19; in case of attack, our approach detects it within 2s with 95% probability.
An Analysis of Untargeted Poisoning Attack and Defense Methods for Federated Online Learning to Rank Systems
Venue: arXiv cs.IR 2023
Year: 2023

Federated online learning to rank (FOLTR) aims to preserve user privacy by not sharing their searchable data and search interactions, while guaranteeing high search effectiveness, especially in contexts where individual users have scarce training data and interactions. For this, FOLTR trains learning to rank models in an online manner -- i.e. by exploiting users' interactions with the search systems (queries, clicks), rather than labels -- and federatively -- i.e. by not aggregating interaction data in a central server for training purposes, but by training instances of a model on each user device on their own private data, and then sharing the model updates, not the data, across a set of users that have formed the federation. Existing FOLTR methods build upon advances in federated learning. While federated learning methods have been shown effective at training machine learning models in a distributed way without the need of data sharing, they can be susceptible to attacks that target either the system's security or its overall effectiveness. In this paper, we consider attacks on FOLTR systems that aim to compromise their search effectiveness. Within this scope, we experiment with and analyse data and model poisoning attack methods to showcase their impact on FOLTR search effectiveness. We also explore the effectiveness of defense methods designed to counteract attacks on FOLTR systems. We contribute an understanding of the effect of attack and defense methods for FOLTR systems, as well as identifying the key factors influencing their effectiveness.
Learning Lie Group Symmetry Transformations with Neural Networks
Venue: arXiv cs.LG 2023
Year: 2023

The problem of detecting and quantifying the presence of symmetries in datasets is useful for model selection, generative modeling, and data analysis, amongst others. While existing methods for hard-coding transformations in neural networks require prior knowledge of the symmetries of the task at hand, this work focuses on discovering and characterizing unknown symmetries present in the dataset, namely, Lie group symmetry transformations beyond the traditional ones usually considered in the field (rotation, scaling, and translation). Specifically, we consider a scenario in which a dataset has been transformed by a one-parameter subgroup of transformations with different parameter values for each data point. Our goal is to characterize the transformation group and the distribution of the parameter values. The results showcase the effectiveness of the approach in both these settings.