OpenRaiser/Intern-Atlas huggingface dataset:
Motif-Backdoor: Rethinking the Backdoor Attack on Graph Neural Networks via Motifs
Venue: arXiv cs.LG 2023
Year: 2023

Graph neural network (GNN) with a powerful representation capability has been widely applied to various areas, such as biological gene prediction, social recommendation, etc. Recent works have exposed that GNN is vulnerable to the backdoor attack, i.e., models trained with maliciously crafted training samples are easily fooled by patched samples. Most of the proposed studies launch the backdoor attack using a trigger that either is the randomly generated subgraph (e.g., erdős-rényi backdoor) for less computational burden, or the gradient-based generative subgraph (e.g., graph trojaning attack) to enable a more effective attack. However, the interpretation of how is the trigger structure and the effect of the backdoor attack related has been overlooked in the current literature. Motifs, recurrent and statistically significant sub-graphs in graphs, contain rich structure information. In this paper, we are rethinking the trigger from the perspective of motifs, and propose a motif-based backdoor attack, denoted as Motif-Backdoor. It contributes from three aspects. (i) Interpretation: it provides an in-depth explanation for backdoor effectiveness by the validity of the trigger structure from motifs, leading to some novel insights, e.g., using subgraphs that appear less frequently in the graph as the trigger can achieve better attack performance. (ii) Effectiveness: Motif-Backdoor reaches the state-of-the-art (SOTA) attack performance in both black-box and defensive scenarios. (iii) Efficiency: based on the graph motif distribution, Motif-Backdoor can quickly obtain an effective trigger structure without target model feedback or subgraph model generation. Extensive experimental results show that Motif-Backdoor realizes the SOTA performance on three popular models and four public datasets compared with five baselines.
Line Graph Contrastive Learning for Link Prediction
Venue: arXiv cs.LG 2023
Year: 2023

Link prediction tasks focus on predicting possible future connections. Most existing researches measure the likelihood of links by different similarity scores on node pairs and predict links between nodes. However, the similarity-based approaches have some challenges in information loss on nodes and generalization ability on similarity indexes. To address the above issues, we propose a Line Graph Contrastive Learning(LGCL) method to obtain rich information with multiple perspectives. LGCL obtains a subgraph view by h-hop subgraph sampling with target node pairs. After transforming the sampled subgraph into a line graph, the link prediction task is converted into a node classification task, which graph convolution progress can learn edge embeddings from graphs more effectively. Then we design a novel cross-scale contrastive learning framework on the line graph and the subgraph to maximize the mutual information of them, so that fuses the structure and feature information. The experimental results demonstrate that the proposed LGCL outperforms the state-of-the-art methods and has better performance on generalization and robustness.
Preference-Learning Emitters for Mixed-Initiative Quality-Diversity Algorithms
Venue: arXiv cs.NE 2023
Year: 2023

In mixed-initiative co-creation tasks, wherein a human and a machine jointly create items, it is important to provide multiple relevant suggestions to the designer. Quality-diversity algorithms are commonly used for this purpose, as they can provide diverse suggestions that represent salient areas of the solution space, showcasing designs with high fitness and wide variety. Because generated suggestions drive the search process, it is important that they provide inspiration, but also stay aligned with the designer's intentions. Additionally, often many interactions with the system are required before the designer is content with a solution. In this work, we tackle these challenges with an interactive constrained MAP-Elites system that leverages emitters to learn the preferences of the designer and then use them in automated steps. By learning preferences, the generated designs remain aligned with the designer's intent, and by applying automatic steps, we generate more solutions per user interaction, giving a larger number of choices to the designer and thereby speeding up the search. We propose a general framework for preference-learning emitters (PLEs) and apply it to a procedural content generation task in the video game Space Engineers. We built an interactive application for our algorithm and performed a user study with players.
Tight analysis of the lazy algorithm for open online dial-a-ride
Venue: arXiv cs.DS 2023
Year: 2023

In the open online dial-a-ride problem, a single server has to deliver transportation requests appearing over time in some metric space, subject to minimizing the completion time. We improve on the best known upper bounds on the competitive ratio on general metric spaces and on the half-line, for both the preemptive and non-preemptive version of the problem. We achieve this by revisiting the algorithm $\textsc{Lazy}$ recently suggested in [WAOA, 2022] and giving an improved and tight analysis. More precisely, we show that it has competitive ratio $2.457$ on general metric spaces and $2.366$ on the half-line. This is the first upper bound that beats known lower bounds of 2.5 for schedule-based algorithms as well as the natural $\textsc{Replan}$ algorithm.
The Debate Over Understanding in AI's Large Language Models
Venue: arXiv cs.LG 2023
Year: 2023

We survey a current, heated debate in the AI research community on whether large pre-trained language models can be said to "understand" language -- and the physical and social situations language encodes -- in any important sense. We describe arguments that have been made for and against such understanding, and key questions for the broader sciences of intelligence that have arisen in light of these arguments. We contend that a new science of intelligence can be developed that will provide insight into distinct modes of understanding, their strengths and limitations, and the challenge of integrating diverse forms of cognition.
OneProvenance: Efficient Extraction of Dynamic Coarse-Grained Provenance from Database Logs [Technical Report]
Venue: arXiv cs.DB 2023
Year: 2023

Provenance encodes information that connects datasets, their generation workflows, and associated metadata (e.g., who or when executed a query). As such, it is instrumental for a wide range of critical governance applications (e.g., observability and auditing). Unfortunately, in the context of database systems, extracting coarse-grained provenance is a long-standing problem due to the complexity and sheer volume of database workflows. Provenance extraction from query event logs has been recently proposed as favorable because, in principle, can result in meaningful provenance graphs for provenance applications. Current approaches, however, (a) add substantial overhead to the database and provenance extraction workflows and (b)~extract provenance that is noisy, omits query execution dependencies, and is not rich enough for upstream applications. To address these problems, we introduce OneProvenance: an efficient provenance extraction system from query event logs. OneProvenance addresses the unique challenges of log-based extraction by (a)~identifying query execution dependencies through efficient log analysis, (b) extracting provenance through novel event transformations that account for query dependencies, and (c)~introducing effective filtering optimizations. Our thorough experimental analysis shows that OneProvenance can improve extraction by up to ~18X compared to state-of-the-art baselines; our optimizations reduce the extraction noise and optimize performance even further. OneProvenance is deployed at scale by Microsoft Purview and actively supports customer provenance extraction needs (https://bit.ly/3N2JVGF).
From exemplar to copy: the scribal appropriation of a Hadewijch manuscript computationally explored
Venue: arXiv cs.CL 2023
Year: 2023

This study is devoted to two of the oldest known manuscripts in which the oeuvre of the medieval mystical author Hadewijch has been preserved: Brussels, KBR, 2879-2880 (ms. A) and Brussels, KBR, 2877-2878 (ms. B). On the basis of codicological and contextual arguments, it is assumed that the scribe who produced B used A as an exemplar. While the similarities in both layout and content between the two manuscripts are striking, the present article seeks to identify the differences. After all, regardless of the intention to produce a copy that closely follows the exemplar, subtle linguistic variation is apparent. Divergences relate to spelling conventions, but also to the way in which words are abbreviated (and the extent to which abbreviations occur). The present study investigates the spelling profiles of the scribes who produced mss. A and B in a computational way. In the first part of this study, we will present both manuscripts in more detail, after which we will consider prior research carried out on scribal profiling. The current study both builds and expands on Kestemont (2015). Next, we outline the methodology used to analyse and measure the degree of scribal appropriation that took place when ms. B was copied off the exemplar ms. A. After this, we will discuss the results obtained, focusing on the scribal variation that can be found both at the level of individual words and n-grams. To this end, we use machine learning to identify the most distinctive features that separate manuscript A from B. Finally, we look at possible diachronic trends in the appropriation by B's scribe of his exemplar. We argue that scribal takeovers in the exemplar impacts the practice of the copying scribe, while transitions to a different content matter cause little to no effect.
Towards standardizing Korean Grammatical Error Correction: Datasets and Annotation
Venue: arXiv cs.CL 2023
Year: 2023

Research on Korean grammatical error correction (GEC) is limited, compared to other major languages such as English. We attribute this problematic circumstance to the lack of a carefully designed evaluation benchmark for Korean GEC. In this work, we collect three datasets from different sources (Kor-Lang8, Kor-Native, and Kor-Learner) that covers a wide range of Korean grammatical errors. Considering the nature of Korean grammar, We then define 14 error types for Korean and provide KAGAS (Korean Automatic Grammatical error Annotation System), which can automatically annotate error types from parallel corpora. We use KAGAS on our datasets to make an evaluation benchmark for Korean, and present baseline models trained from our datasets. We show that the model trained with our datasets significantly outperforms the currently used statistical Korean GEC system (Hanspell) on a wider range of error types, demonstrating the diversity and usefulness of the datasets. The implementations and datasets are open-sourced.
Towards customizable reinforcement learning agents: Enabling preference specification through online vocabulary expansion
Venue: arXiv cs.AI 2023
Year: 2023

There is a growing interest in developing automated agents that can work alongside humans. In addition to completing the assigned task, such an agent will undoubtedly be expected to behave in a manner that is preferred by the human. This requires the human to communicate their preferences to the agent. To achieve this, the current approaches either require the users to specify the reward function or the preference is interactively learned from queries that ask the user to compare behavior. The former approach can be challenging if the internal representation used by the agent is inscrutable to the human while the latter is unnecessarily cumbersome for the user if their preference can be specified more easily in symbolic terms. In this work, we propose PRESCA (PREference Specification through Concept Acquisition), a system that allows users to specify their preferences in terms of concepts that they understand. PRESCA maintains a set of such concepts in a shared vocabulary. If the relevant concept is not in the shared vocabulary, then it is learned. To make learning a new concept more feedback efficient, PRESCA leverages causal associations between the target concept and concepts that are already known. In addition, we use a novel data augmentation approach to further reduce required feedback. We evaluate PRESCA by using it on a Minecraft environment and show that it can effectively align the agent with the user's preference.
Exact Gradient Computation for Spiking Neural Networks Through Forward Propagation
Venue: arXiv cs.NE 2023
Year: 2023

Spiking neural networks (SNN) have recently emerged as alternatives to traditional neural networks, owing to energy efficiency benefits and capacity to better capture biological neuronal mechanisms. However, the classic backpropagation algorithm for training traditional networks has been notoriously difficult to apply to SNN due to the hard-thresholding and discontinuities at spike times. Therefore, a large majority of prior work believes exact gradients for SNN w.r.t. their weights do not exist and has focused on approximation methods to produce surrogate gradients. In this paper, (1) by applying the implicit function theorem to SNN at the discrete spike times, we prove that, albeit being non-differentiable in time, SNNs have well-defined gradients w.r.t. their weights, and (2) we propose a novel training algorithm, called \emph{forward propagation} (FP), that computes exact gradients for SNN. FP exploits the causality structure between the spikes and allows us to parallelize computation forward in time. It can be used with other algorithms that simulate the forward pass, and it also provides insights on why other related algorithms such as Hebbian learning and also recently-proposed surrogate gradient methods may perform well.
Student-centric Model of Learning Management System Activity and Academic Performance: from Correlation to Causation
Venue: arXiv cs.CY 2023
Year: 2023

In recent years, there is a lot of interest in modeling students' digital traces in Learning Management System (LMS) to understand students' learning behavior patterns including aspects of meta-cognition and self-regulation, with the ultimate goal to turn those insights into actionable information to support students to improve their learning outcomes. In achieving this goal, however, there are two main issues that need to be addressed given the existing literature. Firstly, most of the current work is course-centered (i.e. models are built from data for a specific course) rather than student-centered; secondly, a vast majority of the models are correlational rather than causal. Those issues make it challenging to identify the most promising actionable factors for intervention at the student level where most of the campus-wide academic support is designed for. In this paper, we explored a student-centric analytical framework for LMS activity data that can provide not only correlational but causal insights mined from observational data. We demonstrated this approach using a dataset of 1651 computing major students at a public university in the US during one semester in the Fall of 2019. This dataset includes students' fine-grained LMS interaction logs and administrative data, e.g. demographics and academic performance. In addition, we expand the repository of LMS behavior indicators to include those that can characterize the time-of-the-day of login (e.g. chronotype). Our analysis showed that student login volume, compared with other login behavior indicators, is both strongly correlated and causally linked to student academic performance, especially among students with low academic performance. We envision that those insights will provide convincing evidence for college student support groups to launch student-centered and targeted interventions that are effective and scalable.
Quotatives Indicate Decline in Objectivity in U.S. Political News
Venue: arXiv cs.CY 2023
Year: 2023

According to journalistic standards, direct quotes should be attributed to sources with objective quotatives such as "said" and "told", as nonobjective quotatives, like "argued" and "insisted" would influence the readers' perception of the quote and the quoted person. In this paper, we analyze the adherence to this journalistic norm to study trends in objectivity in political news across U.S. outlets of different ideological leanings. We ask: 1) How has the usage of nonobjective quotatives evolved? and 2) How do news outlets use nonobjective quotatives when covering politicians of different parties? To answer these questions, we developed a dependency-parsing-based method to extract quotatives and applied it to Quotebank, a web-scale corpus of attributed quotes, obtaining nearly 7 million quotes, each enriched with the quoted speaker's political party and the ideological leaning of the outlet that published the quote. We find that while partisan outlets are the ones that most often use nonobjective quotatives, between 2013 and 2020, the outlets that increased their usage of nonobjective quotatives the most were "moderate" centrist news outlets (around 0.6 percentage points, or 20% in relative percentage over 7 years). Further, we find that outlets use nonobjective quotatives more often when quoting politicians of the opposing ideology (e.g., left-leaning outlets quoting Republicans), and that this "quotative bias" is rising at a swift pace, increasing up to 0.5 percentage points, or 25% in relative percentage, per year. These findings suggest an overall decline in journalistic objectivity in U.S. political news.
Human-centered Benchmarking for Socially-compliant Robot Navigation
Venue: arXiv cs.RO 2023
Year: 2023

Social compatibility is one of the most important parameters for service robots. It characterizes the quality of interaction between a robot and a human. In this paper, a human-centered benchmarking framework is proposed for socially-compliant robot navigation. In an end-to-end manner, four open-source robot navigation methods are benchmarked, two of which are socially-compliant. All aspects of the benchmarking are clarified to ensure the reproducibility and replicability of the experiments. The social compatibility of robot navigation methods with the Robotic Social Attributes Scale (RoSAS) is measured. After that, the correspondence between RoSAS and the robot-centered metrics is validated. Based on experiments, the extra robot time ratio and the extra distance ratio are the most suitable to judge social compatibility.
The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy
Venue: arXiv cs.IT 2023
Year: 2023

Multi-reference alignment (MRA) is the problem of recovering a signal from its multiple noisy copies, each acted upon by a random group element. MRA is mainly motivated by single-particle cryo-electron microscopy (cryo-EM) that has recently joined X-ray crystallography as one of the two leading technologies to reconstruct biological molecular structures. Previous papers have shown that in the high noise regime, the sample complexity of MRA and cryo-EM is $n=ω(σ^{2d})$, where $n$ is the number of observations, $σ^2$ is the variance of the noise, and $d$ is the lowest-order moment of the observations that uniquely determines the signal. In particular, it was shown that in many cases, $d=3$ for generic signals, and thus the sample complexity is $n=ω(σ^6)$. In this paper, we analyze the second moment of the MRA and cryo-EM models. First, we show that in both models the second moment determines the signal up to a set of unitary matrices, whose dimension is governed by the decomposition of the space of signals into irreducible representations of the group. Second, we derive sparsity conditions under which a signal can be recovered from the second moment, implying sample complexity of $n=ω(σ^4)$. Notably, we show that the sample complexity of cryo-EM is $n=ω(σ^4)$ if at most one third of the coefficients representing the molecular structure are non-zero; this bound is near-optimal. The analysis is based on tools from representation theory and algebraic geometry. We also derive bounds on recovering a sparse signal from its power spectrum, which is the main computational problem of X-ray crystallography.
Convolutional Codes with Optimum Bidirectional Distance Profile
Venue: arXiv cs.IT 2023
Year: 2023

We define the bidirectional distance profile (BDP) of a convolutional code as the minimum of the distance profiles of the code and its corresponding "reverse" code. We present tables of codes with the optimum BDP (OBDP), which minimize the average complexity of bidirectional sequential decoding algorithms. The computer search is accelerated by the facts that optimum distance profile (ODP) codes of larger memory must have ODP codes of smaller memory as their "prefixes", and that OBDP codes can be obtained by "concatenating" ODP and reverse ODP codes of smaller memory. We compare the performance of OBDP codes and other codes by simulation.
Improving the Transferability of Adversarial Attacks on Face Recognition with Beneficial Perturbation Feature Augmentation
Venue: arXiv cs.CV 2023
Year: 2023

Face recognition (FR) models can be easily fooled by adversarial examples, which are crafted by adding imperceptible perturbations on benign face images. The existence of adversarial face examples poses a great threat to the security of society. In order to build a more sustainable digital nation, in this paper, we improve the transferability of adversarial face examples to expose more blind spots of existing FR models. Though generating hard samples has shown its effectiveness in improving the generalization of models in training tasks, the effectiveness of utilizing this idea to improve the transferability of adversarial face examples remains unexplored. To this end, based on the property of hard samples and the symmetry between training tasks and adversarial attack tasks, we propose the concept of hard models, which have similar effects as hard samples for adversarial attack tasks. Utilizing the concept of hard models, we propose a novel attack method called Beneficial Perturbation Feature Augmentation Attack (BPFA), which reduces the overfitting of adversarial examples to surrogate FR models by constantly generating new hard models to craft the adversarial examples. Specifically, in the backpropagation, BPFA records the gradients on pre-selected feature maps and uses the gradient on the input image to craft the adversarial example. In the next forward propagation, BPFA leverages the recorded gradients to add beneficial perturbations on their corresponding feature maps to increase the loss. Extensive experiments demonstrate that BPFA can significantly boost the transferability of adversarial attacks on FR.
The MacWilliams Identity for the Skew Rank Metric
Venue: arXiv cs.IT 2023
Year: 2023

The weight distribution of an error correcting code is a crucial statistic in determining it's performance. One key tool for relating the weight of a code to that of it's dual is the MacWilliams Identity, first developed for the Hamming metric. This identity has two forms: one is a functional transformation of the weight enumerators, while the other is a direct relation of the weight distributions via (generalised) Krawtchouk polynomials. The functional transformation form can in particular be used to derive important moment identities for the weight distribution of codes. In this paper, we focus on codes in the skew rank metric. In these codes, the codewords are skew-symmetric matrices, and the distance between two matrices is the skew rank metric, which is half the rank of their difference. This paper develops a $q$-analog MacWilliams Identity in the form of a functional transformation for codes based on skew-symmetric matrices under their associated skew rank metric. The method introduces a skew-$q$ algebra and uses generalised Krawtchouk polynomials. Based on this new MacWilliams Identity, we then derive several moments of the skew rank distribution for these codes.