OpenRaiser/Intern-Atlas huggingface dataset:
Steering Graph Neural Networks with Pinning Control
Venue: arXiv cs.LG 2023
Year: 2023

In the semi-supervised setting where labeled data are largely limited, it remains to be a big challenge for message passing based graph neural networks (GNNs) to learn feature representations for the nodes with the same class label that is distributed discontinuously over the graph. To resolve the discontinuous information transmission problem, we propose a control principle to supervise representation learning by leveraging the prototypes (i.e., class centers) of labeled data. Treating graph learning as a discrete dynamic process and the prototypes of labeled data as "desired" class representations, we borrow the pinning control idea from automatic control theory to design learning feedback controllers for the feature learning process, attempting to minimize the differences between message passing derived features and the class prototypes in every round so as to generate class-relevant features. Specifically, we equip every node with an optimal controller in each round through learning the matching relationships between nodes and the class prototypes, enabling nodes to rectify the aggregated information from incompatible neighbors in a graph with strong heterophily. Our experiments demonstrate that the proposed PCGCN model achieves better performances than deep GNNs and other competitive heterophily-oriented methods, especially when the graph has very few labels and strong heterophily.
High-throughput optical neural networks based on temporal computing
Venue: arXiv cs.ET 2023
Year: 2023

An emerging generative artificial intelligence (AI) based on neural networks starts to grow in popularity with a revolutionizing capability of creating new and original content. As giant generative models with millions to billions of parameters are developed, trained and maintained, a massive and energy-efficient computing power is highly required. However, conventional digital computers are struggling to keep up with the pace of the generative model improvements. In this paper, we propose and demonstrate high-throughput optical neural networks based on temporal computing. The core weighted summation operation is realized with the use of high-speed electro-optic modulation and low-speed balanced photodetection. The input data and weight are encoded in a time sequence separately and loaded on an optical signal via two electro-optic modulators sequentially. By precisely controlling the synchronization time of the data and weight loading, the matrix multiplication is performed. Followed by a balanced photodetector, the summation is conducted, thanks to the electron accumulation of the inherent electronic integrator circuit of the low-speed photodetector. Thus, the linear weighted summation operation is implemented based on temporal computing in the optical domain. With the proposed optical linear weighted summation, a fully-connected neural network and convolutional neural network are realized. Thanks to the high-speed feature of temporal computing, a high data throughput of the optical neural network is experimentally demonstrated, and the weighting coefficients can be specified on demand, which enables a strong programmability of the optical neural network. By leveraging wavelength multiplexing technology, a scalable optical neural network could be created with a massive computing power and strong reconfigurability, which holds great potential for future giant AI applications.
Interactive robots as inclusive tools to increase diversity in higher education
Venue: arXiv cs.RO 2023
Year: 2023

There is a major lack of diversity in engineering, technology, and computing subjects in higher education. The resulting underrepresentation of some population groups contributes largely to gender and ethnicity pay gaps and social disadvantages. We aim to increase the diversity among students in such subjects by investigating the use of interactive robots as a tool that can get prospective students from different backgrounds interested in robotics as their field of study. For that, we will survey existing solutions that have proven to be successful in engaging underrepresented groups with technical subjects in educational settings. Moreover, we examine two recent outreach events at the University of Hertfordshire against inclusivity criteria. Based on that, we suggest specific activities for higher education institutions that follow an inclusive approach using interactive robots to attract prospective students at open days and other outreach events. Our suggestions provide tangible actions that can be easily implemented by higher education institutions to make technical subjects more appealing to everyone and thereby tackle inequalities in student uptake.
High-dimensional analysis of double descent for linear regression with random projections
Venue: arXiv cs.LG 2023
Year: 2023

We consider linear regression problems with a varying number of random projections, where we provably exhibit a double descent curve for a fixed prediction problem, with a high-dimensional analysis based on random matrix theory. We first consider the ridge regression estimator and review earlier results using classical notions from non-parametric statistics, namely degrees of freedom, also known as effective dimensionality. We then compute asymptotic equivalents of the generalization performance (in terms of squared bias and variance) of the minimum norm least-squares fit with random projections, providing simple expressions for the double descent phenomenon.
Cooperative Data Collection with Multiple UAVs for Information Freshness in the Internet of Things
Venue: arXiv cs.IT 2023
Year: 2023

Maintaining the freshness of information in the Internet of Things (IoT) is a critical yet challenging problem. In this paper, we study cooperative data collection using multiple Unmanned Aerial Vehicles (UAVs) with the objective of minimizing the total average Age of Information (AoI). We consider various constraints of the UAVs, including kinematic, energy, trajectory, and collision avoidance, in order to optimize the data collection process. Specifically, each UAV, which has limited on-board energy, takes off from its initial location and flies over sensor nodes to collect update packets in cooperation with the other UAVs. The UAVs must land at their final destinations with non-negative residual energy after the specified time duration to ensure they have enough energy to complete their missions. It is crucial to design the trajectories of the UAVs and the transmission scheduling of the sensor nodes to enhance information freshness. We model the multi-UAV data collection problem as a Decentralized Partially Observable Markov Decision Process (Dec-POMDP), as each UAV is unaware of the dynamics of the environment and can only observe a part of the sensors. To address the challenges of this problem, we propose a multi-agent Deep Reinforcement Learning (DRL)-based algorithm with centralized learning and decentralized execution. In addition to the reward shaping, we use action masks to filter out invalid actions and ensure that the constraints are met. Simulation results demonstrate that the proposed algorithms can significantly reduce the total average AoI compared to the baseline algorithms, and the use of the action mask method can improve the convergence speed of the proposed algorithm.
Reinforced Labels: Multi-Agent Deep Reinforcement Learning for Point-Feature Label Placement
Venue: arXiv cs.LG 2023
Year: 2023

Over the recent years, Reinforcement Learning combined with Deep Learning techniques has successfully proven to solve complex problems in various domains, including robotics, self-driving cars, and finance. In this paper, we are introducing Reinforcement Learning (RL) to label placement, a complex task in data visualization that seeks optimal positioning for labels to avoid overlap and ensure legibility. Our novel point-feature label placement method utilizes Multi-Agent Deep Reinforcement Learning to learn the label placement strategy, the first machine-learning-driven labeling method, in contrast to the existing hand-crafted algorithms designed by human experts. To facilitate RL learning, we developed an environment where an agent acts as a proxy for a label, a short textual annotation that augments visualization. Our results show that the strategy trained by our method significantly outperforms the random strategy of an untrained agent and the compared methods designed by human experts in terms of completeness (i.e., the number of placed labels). The trade-off is increased computation time, making the proposed method slower than the compared methods. Nevertheless, our method is ideal for scenarios where the labeling can be computed in advance, and completeness is essential, such as cartographic maps, technical drawings, and medical atlases. Additionally, we conducted a user study to assess the perceived performance. The outcomes revealed that the participants considered the proposed method to be significantly better than the other examined methods. This indicates that the improved completeness is not just reflected in the quantitative metrics but also in the subjective evaluation by the participants.
Coresets for Clustering in Geometric Intersection Graphs
Venue: arXiv cs.CG 2023
Year: 2023

Designing coresets--small-space sketches of the data preserving cost of the solutions within $(1\pm ε)$-approximate factor--is an important research direction in the study of center-based $k$-clustering problems, such as $k$-means or $k$-median. Feldman and Langberg [STOC'11] have shown that for $k$-clustering of $n$ points in general metrics, it is possible to obtain coresets whose size depends logarithmically in $n$. Moreover, such a dependency in $n$ is inevitable in general metrics. A significant amount of recent work in the area is devoted to obtaining coresests whose sizes are independent of $n$ (i.e., ``small'' coresets) for special metrics, like $d$-dimensional Euclidean spaces, doubling metrics, metrics of graphs of bounded treewidth, or those excluding a fixed minor. In this paper, we provide the first constructions of small coresets for $k$-clustering in the metrics induced by geometric intersection graphs, such as Euclidean-weighted Unit Disk/Square Graphs. These constructions follow from a general theorem that identifies two canonical properties of a graph metric sufficient for obtaining small coresets. The proof of our theorem builds on the recent work of Cohen-Addad, Saulpic, and Schwiegelshohn [STOC '21], which ensures small-sized coresets conditioned on the existence of an interesting set of centers, called ``centroid set''. The main technical contribution of our work is the proof of the existence of such a small-sized centroid set for graphs that satisfy the two canonical geometric properties. The new coreset construction helps to design the first $(1+ε)$-approximation for center-based clustering problems in UDGs and USGs, that is fixed-parameter tractable in $k$ and $ε$ (FPT-AS).
WiCE: Real-World Entailment for Claims in Wikipedia
Venue: arXiv cs.CL 2023
Year: 2023

Textual entailment models are increasingly applied in settings like fact-checking, presupposition verification in question answering, or summary evaluation. However, these represent a significant domain shift from existing entailment datasets, and models underperform as a result. We propose WiCE, a new fine-grained textual entailment dataset built on natural claim and evidence pairs extracted from Wikipedia. In addition to standard claim-level entailment, WiCE provides entailment judgments over sub-sentence units of the claim, and a minimal subset of evidence sentences that support each subclaim. To support this, we propose an automatic claim decomposition strategy using GPT-3.5 which we show is also effective at improving entailment models' performance on multiple datasets at test time. Finally, we show that real claims in our dataset involve challenging verification and retrieval problems that existing models fail to address.
Canonical decompositions in monadically stable and bounded shrubdepth graph classes
Venue: arXiv cs.LO 2023
Year: 2023

We use model-theoretic tools originating from stability theory to derive a result we call the Finitary Substitute Lemma, which intuitively says the following. Suppose we work in a stable graph class C, and using a first-order formula ϕ with parameters we are able to define, in every graph G in C, a relation R that satisfies some hereditary first-order assertion ψ. Then we are able to find a first-order formula ϕ' that has the same property, but additionally is finitary: there is finite bound k such that in every graph G in C, different choices of parameters give only at most k different relations R that can be defined using ϕ'. We use the Finitary Substitute Lemma to derive two corollaries about the existence of certain canonical decompositions in classes of well-structured graphs. - We prove that in the Splitter game, which characterizes nowhere dense graph classes, and in the Flipper game, which characterizes monadically stable graph classes, there is a winning strategy for Splitter, respectively Flipper, that can be defined in first-order logic from the game history. Thus, the strategy is canonical. - We show that for any fixed graph class C of bounded shrubdepth, there is an O(n^2)-time algorithm that given an n-vertex graph G in C, computes in an isomorphism-invariant way a structure H of bounded treedepth in which G can be interpreted. A corollary of this result is an O(n^2)-time isomorphism test and canonization algorithm for any fixed class of bounded shrubdepth.
FeatAug-DETR: Enriching One-to-Many Matching for DETRs with Feature Augmentation
Venue: arXiv cs.CV 2023
Year: 2023

One-to-one matching is a crucial design in DETR-like object detection frameworks. It enables the DETR to perform end-to-end detection. However, it also faces challenges of lacking positive sample supervision and slow convergence speed. Several recent works proposed the one-to-many matching mechanism to accelerate training and boost detection performance. We revisit these methods and model them in a unified format of augmenting the object queries. In this paper, we propose two methods that realize one-to-many matching from a different perspective of augmenting images or image features. The first method is One-to-many Matching via Data Augmentation (denoted as DataAug-DETR). It spatially transforms the images and includes multiple augmented versions of each image in the same training batch. Such a simple augmentation strategy already achieves one-to-many matching and surprisingly improves DETR's performance. The second method is One-to-many matching via Feature Augmentation (denoted as FeatAug-DETR). Unlike DataAug-DETR, it augments the image features instead of the original images and includes multiple augmented features in the same batch to realize one-to-many matching. FeatAug-DETR significantly accelerates DETR training and boosts detection performance while keeping the inference speed unchanged. We conduct extensive experiments to evaluate the effectiveness of the proposed approach on DETR variants, including DAB-DETR, Deformable-DETR, and H-Deformable-DETR. Without extra training data, FeatAug-DETR shortens the training convergence periods of Deformable-DETR to 24 epochs and achieves 58.3 AP on COCO val2017 set with Swin-L as the backbone.
DeepSeer: Interactive RNN Explanation and Debugging via State Abstraction
Venue: arXiv cs.HC 2023
Year: 2023

Recurrent Neural Networks (RNNs) have been widely used in Natural Language Processing (NLP) tasks given its superior performance on processing sequential data. However, it is challenging to interpret and debug RNNs due to the inherent complexity and the lack of transparency of RNNs. While many explainable AI (XAI) techniques have been proposed for RNNs, most of them only support local explanations rather than global explanations. In this paper, we present DeepSeer, an interactive system that provides both global and local explanations of RNN behavior in multiple tightly-coordinated views for model understanding and debugging. The core of DeepSeer is a state abstraction method that bundles semantically similar hidden states in an RNN model and abstracts the model as a finite state machine. Users can explore the global model behavior by inspecting text patterns associated with each state and the transitions between states. Users can also dive into individual predictions by inspecting the state trace and intermediate prediction results of a given input. A between-subjects user study with 28 participants shows that, compared with a popular XAI technique, LIME, participants using DeepSeer made a deeper and more comprehensive assessment of RNN model behavior, identified the root causes of incorrect predictions more accurately, and came up with more actionable plans to improve the model performance.
DeepLens: Interactive Out-of-distribution Data Detection in NLP Models
Venue: arXiv cs.HC 2023
Year: 2023

Machine Learning (ML) has been widely used in Natural Language Processing (NLP) applications. A fundamental assumption in ML is that training data and real-world data should follow a similar distribution. However, a deployed ML model may suffer from out-of-distribution (OOD) issues due to distribution shifts in the real-world data. Though many algorithms have been proposed to detect OOD data from text corpora, there is still a lack of interactive tool support for ML developers. In this work, we propose DeepLens, an interactive system that helps users detect and explore OOD issues in massive text corpora. Users can efficiently explore different OOD types in DeepLens with the help of a text clustering method. Users can also dig into a specific text by inspecting salient words highlighted through neuron activation analysis. In a within-subjects user study with 24 participants, participants using DeepLens were able to find nearly twice more types of OOD issues accurately with 22% more confidence compared with a variant of DeepLens that has no interaction or visualization support.
Technical report: Graph Neural Networks go Grammatical
Venue: arXiv cs.LG 2023
Year: 2023

This paper introduces a framework for formally establishing a connection between a portion of an algebraic language and a Graph Neural Network (GNN). The framework leverages Context-Free Grammars (CFG) to organize algebraic operations into generative rules that can be translated into a GNN layer model. As CFGs derived directly from a language tend to contain redundancies in their rules and variables, we present a grammar reduction scheme. By applying this strategy, we define a CFG that conforms to the third-order Weisfeiler-Lehman (3-WL) test using MATLANG. From this 3-WL CFG, we derive a GNN model, named G$^2$N$^2$, which is provably 3-WL compliant. Through various experiments, we demonstrate the superior efficiency of G$^2$N$^2$ compared to other 3-WL GNNs across numerous downstream tasks. Specifically, one experiment highlights the benefits of grammar reduction within our framework.
STEP: Stochastic Traversability Evaluation and Planning for Risk-Aware Off-road Navigation; Results from the DARPA Subterranean Challenge
Venue: arXiv cs.RO 2023
Year: 2023

Although autonomy has gained widespread usage in structured and controlled environments, robotic autonomy in unknown and off-road terrain remains a difficult problem. Extreme, off-road, and unstructured environments such as undeveloped wilderness, caves, rubble, and other post-disaster sites pose unique and challenging problems for autonomous navigation. Based on our participation in the DARPA Subterranean Challenge, we propose an approach to improve autonomous traversal of robots in subterranean environments that are perceptually degraded and completely unknown through a traversability and planning framework called STEP (Stochastic Traversability Evaluation and Planning). We present 1) rapid uncertainty-aware mapping and traversability evaluation, 2) tail risk assessment using the Conditional Value-at-Risk (CVaR), 3) efficient risk and constraint-aware kinodynamic motion planning using sequential quadratic programming-based (SQP) model predictive control (MPC), 4) fast recovery behaviors to account for unexpected scenarios that may cause failure, and 5) risk-based gait adaptation for quadrupedal robots. We illustrate and validate extensive results from our experiments on wheeled and legged robotic platforms in field studies at the Valentine Cave, CA (cave environment), Kentucky Underground, KY (mine environment), and Louisville Mega Cavern, KY (final competition site for the DARPA Subterranean Challenge with tunnel, urban, and cave environments).
Separated and Shared Effects in Higher-Order Languages
Venue: arXiv cs.PL 2023
Year: 2023

Effectful programs interact in ways that go beyond simple input-output, making compositional reasoning challenging. Existing work has shown that when such programs are ``separate'', i.e., when programs do not interfere with each other, it can be easier to reason about them. While reasoning about separated resources has been well-studied, there has been little work on reasoning about separated effects, especially for functional, higher-order programming languages. We propose two higher-order languages that can reason about sharing and separation in effectful programs. Our first language $λ_{\text{INI}}$ has a linear type system and probabilistic semantics, where the two product types capture independent and possibly-dependent pairs. Our second language $λ_{\text{INI}}^2$ is two-level, stratified language, inspired by Benton's linear-non-linear (LNL) calculus. We motivate this language with a probabilistic model, but we also provide a general categorical semantics and exhibit a range of concrete models beyond probabilistic programming. We prove soundness theorems for all of our languages; our general soundness theorem for our categorical models of $λ_{\text{INI}}^2$ uses a categorical gluing construction.
Groups of linear isometries on weighted poset block spaces
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we introduce a new family of metrics, weighted poset block metric, that combine the weighted coordinates poset metric introduced by Panek et al. [(\ref{panek})] and the metric for linear error-block codes introduced by Feng et al. [(\ref{FENG})]. This type of metrics include many classical metrics such as Hamming metric, Lee metric, poset metric, pomset metric, poset block metric, pomset block metric and so on. We give a complete description of the groups of linear isometries of these metric spaces in terms of a semi-direct product. Furthermore, we obtain a Singleton type bound for codes equipped with weighted poset block metric and define MDS codes. As a special case when the poset is a chain, we show that MDS codes are equivalent to perfect codes.