Search

Traditional defect prediction approaches often use metrics that measure the complexity of the design or implementing code of a software system, such as the number of lines of code in a source file. In this paper, we explore a different approach based on content of source code. Our key assumption is that source code of a software system contains information about its technical aspects and those aspects might have different levels of defect-proneness. Thus, content-based features such as words, topics, data types, and package names extracted from a source code file could be used to predict its defects. We have performed an extensive empirical evaluation and found that: i) such content-based features have higher predictive power than code complexity metrics and ii) the use of feature selection, reduction, and combination further improves the prediction performance.

Software security incidents occur everyday and thousands of software security reports are announced each month. Thus, it is difficult for software security researchers, engineers, and other stakeholders to follow software security topics of their interests in real-time. In this paper, we propose, SOSK, a novel tool for this problem. SOSK allows a user to import a collection of software security reports. It pre-processes and extracts the most important keywords from the textual description of the reports. Based on the similarity of embedding vectors of keywords, SOSK can expand and/or refine a keyword set from a much smaller set of user-provided keywords. Thus, SOSK allows users to define any topic of their interests and retrieve security reports relevant to that topic effectively. Our preliminary evaluation shows that SOSK can expand keywords and retrieve reports relevant to user requests.

We prove that for every complete graph $K_t$, all graphs $G$ with no induced subgraph isomorphic to a subdivision of $K_t$ have a stable subset of size at least $|G|/{\rm polylog}|G|$. This is close to best possible, because for $t\ge 6$, not all such graphs $G$ have a stable set of linear size, even if $G$ is triangle-free.

When $H$ is a forest, the Gy\'arf\'as-Sumner conjecture implies that every graph $G$ with no induced subgraph isomorphic to $H$ and with bounded clique number has a stable set of linear size. We cannot prove that, but we prove that every such graph $G$ has a stable set of size $|G|^{1-o(1)}$. If $H$ is not a forest, there need not be such a stable set. Second, we prove that when $H$ is a ``multibroom'', there {\em is} a stable set of linear size. As a consequence, we deduce that all multibrooms satisfy a ``fractional colouring'' version of the Gy\'arf\'as-Sumner conjecture. Finally, we discuss extensions of our results to the multicolour setting.

A {\em $k$-kernel} in a digraph $G$ is a stable set $X$ of vertices such that every vertex of $G$ can be joined from $X$ by a directed path of length at most $k$. We prove three results about $k$-kernels. First, it was conjectured by Erd\H{o}s and Sz\'ekely in 1976 that every digraph $G$ with no source has a 2-kernel $|K|$ with $|K|\le |G|/2$. We prove this conjecture when $G$ is a ``split digraph'' (that is, its vertex set can be partitioned into a tournament and a stable set), improving a result of Langlois et al., who proved that every split digraph $G$ with no source has a 2-kernel of size at most $2|G|/3$. Second, the Erd\H{o}s-Sz\'ekely conjecture implies that in every digraph $G$ there is a 2-kernel $K$ such that the union of $K$ and its out-neighbours has size at least $|G|/2$. We prove that this is true if $V(G)$ can be partitioned into a tournament and an acyclic set. Third, in a recent paper, Spiro asked whether, for all $k\ge 3$, every strongly-connected digraph $G$ has a $k$-kernel of size at most about $|G|/(k+1)$. This remains open, but we prove that there is one of size at most about $|G|/(k-1)$.

Gcd-graphs over the ring of integers modulo $n$ are a natural generalization of unitary Cayley graphs. The study of these graphs has foundations in various mathematical fields, including number theory, ring theory, and representation theory. Using the theory of Ramanujan sums, it is known that these gcd-graphs have integral spectra; i.e., all their eigenvalues are integers. In this work, inspired by the analogy between number fields and function fields, we define and study gcd-graphs over polynomial rings with coefficients in finite fields. We establish some fundamental properties of these graphs, emphasizing their analogy to their counterparts over $\mathbb{Z}.$, Comment: Comments are welcome!

Due to their elegant and simple nature, unitary Cayley graphs have been an active research topic in the literature. These graphs are naturally connected to several branches of mathematics, including number theory, finite algebra, representation theory, and graph theory. In this article, we study the perfectness property of these graphs. More precisely, we provide a complete classification of perfect unitary Cayley graphs associated with finite rings., Comment: Comments are welcome!

Detecting and attributing temperature increases due to climate change is crucial for understanding global warming and guiding adaptation strategies. The complexity of distinguishing human-induced climate signals from natural variability has challenged traditional detection and attribution (D&A) approaches, which seek to identify specific "fingerprints" in climate response variables. Deep learning offers potential for discerning these complex patterns in expansive spatial datasets. However, lack of standard protocols has hindered consistent comparisons across studies. We introduce ClimDetect, a standardized dataset of over 816k daily climate snapshots, designed to enhance model accuracy in identifying climate change signals. ClimDetect integrates various input and target variables used in past research, ensuring comparability and consistency. We also explore the application of vision transformers (ViT) to climate data, a novel and modernizing approach in this context. Our open-access data and code serve as a benchmark for advancing climate science through improved model evaluations. ClimDetect is publicly accessible via Huggingface dataet respository at: https://huggingface.co/datasets/ClimDetect/ClimDetect.

Changepoint detection, a technique for identifying significant shifts within data sequences, is crucial in various fields such as finance, genomics, medicine, etc. Dynamic programming changepoint detection algorithms are employed to identify the locations of changepoints within a sequence, which rely on a penalty parameter to regulate the number of changepoints. To estimate this penalty parameter, previous work uses simple models such as linear or tree-based models. This study introduces a novel deep learning method for predicting penalty parameters, leading to demonstrably improved changepoint detection accuracy on large benchmark supervised labeled datasets compared to previous methods., Comment: 17 pages, 7 figures

With the proliferation of the Internet of Things (IoT) and the rising interconnectedness of devices, network security faces significant challenges, especially from anomalous activities. While traditional machine learning-based intrusion detection systems (ML-IDS) effectively employ supervised learning methods, they possess limitations such as the requirement for labeled data and challenges with high dimensionality. Recent unsupervised ML-IDS approaches such as AutoEncoders and Generative Adversarial Networks (GAN) offer alternative solutions but pose challenges in deployment onto resource-constrained IoT devices and in interpretability. To address these concerns, this paper proposes a novel federated unsupervised anomaly detection framework, FedPCA, that leverages Principal Component Analysis (PCA) and the Alternating Directions Method Multipliers (ADMM) to learn common representations of distributed non-i.i.d. datasets. Building on the FedPCA framework, we propose two algorithms, FEDPE in Euclidean space and FEDPG on Grassmann manifolds. Our approach enables real-time threat detection and mitigation at the device level, enhancing network resilience while ensuring privacy. Moreover, the proposed algorithms are accompanied by theoretical convergence rates even under a subsampling scheme, a novel result. Experimental results on the UNSW-NB15 and TON-IoT datasets show that our proposed methods offer performance in anomaly detection comparable to nonlinear baselines, while providing significant improvements in communication and memory efficiency, underscoring their potential for securing IoT networks., Comment: Accepted for publication at IEEE/ACM Transactions on Networking

Optimizing black-box functions is a fundamental problem in science and engineering. To solve this problem, many approaches learn a surrogate function that estimates the underlying objective from limited historical evaluations. Large Language Models (LLMs), with their strong pattern-matching capabilities via pretraining on vast amounts of data, stand out as a potential candidate for surrogate modeling. However, directly prompting a pretrained language model to produce predictions is not feasible in many scientific domains due to the scarcity of domain-specific data in the pretraining corpora and the challenges of articulating complex problems in natural language. In this work, we introduce LICO, a general-purpose model that extends arbitrary base LLMs for black-box optimization, with a particular application to the molecular domain. To achieve this, we equip the language model with a separate embedding layer and prediction layer, and train the model to perform in-context predictions on a diverse set of functions defined over the domain. Once trained, LICO can generalize to unseen molecule properties simply via in-context prompting. LICO achieves state-of-the-art performance on PMO, a challenging molecular optimization benchmark comprising over 20 objective functions.

In-context learning is a key paradigm in large language models (LLMs) that enables them to generalize to new tasks and domains by simply prompting these models with a few exemplars without explicit parameter updates. Many attempts have been made to understand in-context learning in LLMs as a function of model scale, pretraining data, and other factors. In this work, we propose a new mechanism to probe and understand in-context learning from the lens of decision boundaries for in-context binary classification. Decision boundaries are straightforward to visualize and provide important information about the qualitative behavior of the inductive biases of standard classifiers. To our surprise, we find that the decision boundaries learned by current LLMs in simple binary classification tasks are often irregular and non-smooth, regardless of linear separability in the underlying task. This paper investigates the factors influencing these decision boundaries and explores methods to enhance their generalizability. We assess various approaches, including training-free and fine-tuning methods for LLMs, the impact of model architecture, and the effectiveness of active prompting techniques for smoothing decision boundaries in a data-efficient manner. Our findings provide a deeper understanding of in-context learning dynamics and offer practical improvements for enhancing robustness and generalizability of in-context learning., Comment: 18 pages, code at https://github.com/siyan-zhao/ICL_decision_boundary

While astonishingly capable, large Language Models (LLM) can sometimes produce outputs that deviate from human expectations. Such deviations necessitate an alignment phase to prevent disseminating untruthful, toxic, or biased information. Traditional alignment methods based on reinforcement learning often struggle with the identified instability, whereas preference optimization methods are limited by their overfitting to pre-collected hard-label datasets. In this paper, we propose a novel LLM alignment framework named $i$REPO, which utilizes implicit Reward pairwise difference regression for Empirical Preference Optimization. Particularly, $i$REPO employs self-generated datasets labelled by empirical human (or AI annotator) preference to iteratively refine the aligned policy through a novel regression-based loss function. Furthermore, we introduce an innovative algorithm backed by theoretical guarantees for achieving optimal results under ideal assumptions and providing a practical performance-gap result without such assumptions. Experimental results with Phi-2 and Mistral-7B demonstrate that $i$REPO effectively achieves self-alignment using soft-label, self-generated responses and the logit of empirical AI annotators. Furthermore, our approach surpasses preference optimization baselines in evaluations using the Language Model Evaluation Harness and Multi-turn benchmarks., Comment: Under Review

In this paper we argue that conventional unitary-invariant measures of recommender system (RS) performance based on measuring differences between predicted ratings and actual user ratings fail to assess fundamental RS properties. More specifically, posing the optimization problem as one of predicting exact user ratings provides only an indirect suboptimal approximation for what RS applications typically need, which is an ability to accurately predict user preferences. We argue that scalar measures such as RMSE and MAE with respect to differences between actual and predicted ratings are only proxies for measuring RS ability to accurately estimate user preferences. We propose what we consider to be a measure that is more fundamentally appropriate for assessing RS performance, rank-preference consistency, which simply counts the number of prediction pairs that are inconsistent with the user's expressed product preferences. For example, if an RS predicts the user will prefer product A over product B, but the user's withheld ratings indicate s/he prefers product B over A, then rank-preference consistency has been violated. Our test results conclusively demonstrate that methods tailored to optimize arbitrary measures such as RMSE are not generally effective at accurately predicting user preferences. Thus, we conclude that conventional methods used for assessing RS performance are arbitrary and misleading.

In recent work, we study certain Cayley graphs associated with a finite commutative ring and their multiplicative subgroups. Among various results that we prove, we provide the necessary and sufficient conditions for such a Cayley graph to be prime. In this paper, we continue this line of research. Specifically, we investigate some basic properties of certain $p$-unitary Cayeley graphs associated with a finite commutative ring. In particular, under some mild conditions, we provide the necessary and sufficient conditions for this graph to be prime., Comment: Comments are welcome!

In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible., Comment: 13 pages

Accurate prediction of climate in the subseasonal-to-seasonal scale is crucial for disaster preparedness and robust decision making amidst climate change. Yet, forecasting beyond the weather timescale is challenging because it deals with problems other than initial condition, including boundary interaction, butterfly effect, and our inherent lack of physical understanding. At present, existing benchmarks tend to have shorter forecasting range of up-to 15 days, do not include a wide range of operational baselines, and lack physics-based constraints for explainability. Thus, we propose ChaosBench, a challenging benchmark to extend the predictability range of data-driven weather emulators to S2S timescale. First, ChaosBench is comprised of variables beyond the typical surface-atmospheric ERA5 to also include ocean, ice, and land reanalysis products that span over 45 years to allow for full Earth system emulation that respects boundary conditions. We also propose physics-based, in addition to deterministic and probabilistic metrics, to ensure a physically-consistent ensemble that accounts for butterfly effect. Furthermore, we evaluate on a diverse set of physics-based forecasts from four national weather agencies as baselines to our data-driven counterpart such as ViT/ClimaX, PanguWeather, GraphCast, and FourCastNetV2. Overall, we find methods originally developed for weather-scale applications fail on S2S task: their performance simply collapse to an unskilled climatology. Nonetheless, we outline and demonstrate several strategies that can extend the predictability range of existing weather emulators, including the use of ensembles, robust control of error propagation, and the use of physics-informed models. Our benchmark, datasets, and instructions are available at https://leap-stc.github.io/ChaosBench., Comment: Accepted as Oral in NeurIPS'24 D&B Track

It was conjectured, independently by two sets of authors, that for all integers $k,d\ge 1$ there exists $\ell>0$, such that if $S,T$ are subsets of vertices of a graph $G$, then either there are $k$ paths between $S,T$, pairwise at distance at least $d$, or there is a set $X\subseteq V(G)$ with $|X|\le k-1$ such that every path between $S,T$ contains a vertex with distance at most $\ell$ from some member of $X$. The result is known for $k\le 2$, but we will show that it is false for all $k\ge 3$, even if $G$ is constrained to have maximum degree at most three. We also give a proof of the result when $k=2$ that is simpler than the previous proofs.

The decomposition of complex networks into smaller, interconnected components is a central challenge in network theory with a wide range of potential applications. In this paper, we utilize tools from group theory and ring theory to study this problem when the network is a Cayley graph. In particular, we answer the following question: Which Cayley graphs are prime?

We confirm a conjecture of Fox, Pach, and Suk, that for every $d>0$, there exists $c>0$ such that every $n$-vertex graph of VC-dimension at most $d$ has a clique or stable set of size at least $n^c$. This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erd\H{o}s-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lov\'asz and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper., Comment: 11 pages, minor revisions

We prove the Erd\H{o}s-Hajnal conjecture for the five-vertex path $P_5$; that is, there exists $c>0$ such that every $n$-vertex graph with no induced $P_5$ has a clique or stable set of size at least $n^c$. This completes the verification of the Erd\H{o}s-Hajnal property of all five-vertex graphs. Indeed, we show a stronger statement, that $P_5$ satisfies the polynomial version of a theorem of R\"odl. To achieve this, we combine simple probabilistic and structural ideas with the iterative sparsification framework introduced in the series., Comment: 15 pages

Recently, research in human-robot interaction began to consider a robot's influence at the group level. Despite the recent growth in research investigating the effects of robots within groups of people, our overall understanding of what happens when robots are placed within groups or teams of people is still limited. This paper investigates several key problems for social robots that manage conversations in a group setting, where the number of participants is more than two. In a group setting, the conversation dynamics are a lot more complicated than the conventional one-to-one conversation, thus, there are more challenges need to be solved., Comment: 5 pages

Weather forecasting is a fundamental problem for anticipating and mitigating the impacts of climate change. Recently, data-driven approaches for weather forecasting based on deep learning have shown great promise, achieving accuracies that are competitive with operational systems. However, those methods often employ complex, customized architectures without sufficient ablation analysis, making it difficult to understand what truly contributes to their success. Here we introduce Stormer, a simple transformer model that achieves state-of-the-art performance on weather forecasting with minimal changes to the standard transformer backbone. We identify the key components of Stormer through careful empirical analyses, including weather-specific embedding, randomized dynamics forecast, and pressure-weighted loss. At the core of Stormer is a randomized forecasting objective that trains the model to forecast the weather dynamics over varying time intervals. During inference, this allows us to produce multiple forecasts for a target lead time and combine them to obtain better forecast accuracy. On WeatherBench 2, Stormer performs competitively at short to medium-range forecasts and outperforms current methods beyond 7 days, while requiring orders-of-magnitude less training data and compute. Additionally, we demonstrate Stormer's favorable scaling properties, showing consistent improvements in forecast accuracy with increases in model size and training tokens. Code and checkpoints will be made publicly available.

We define the finite number ring ${\Bbb Z}_n [\sqrt [m] r]$ where $m,n$ are positive integers and $r$ in an integer akin to the definition of the Gaussian integer ${\Bbb Z}[i]$. This idea is also introduced briefly in [7]. By definition, this finite number ring ${\Bbb Z}_n [\sqrt [m] r]$ is naturally isomorphic to the ring ${\Bbb Z}_n[x]/{\langle x^m-r \rangle}$. From an educational standpoint, this description offers a straightforward and elementary presentation of this finite ring, making it suitable for readers who do not have extensive exposure to abstract algebra. We discuss various arithmetical properties of this ring. In particular, when $n=p$ is a prime number and $\mathbb{Z}_p$ contains a primitive $m$-root of unity, we describe the structure of $\mathbb{Z}_n[\sqrt[m]{r}]$ explicitly., Comment: Expository paper. Comments are welcome!

Experimental design is a fundamental problem in many science and engineering fields. In this problem, sample efficiency is crucial due to the time, money, and safety costs of real-world design evaluations. Existing approaches either rely on active data collection or access to large, labeled datasets of past experiments, making them impractical in many real-world scenarios. In this work, we address the more challenging yet realistic setting of few-shot experimental design, where only a few labeled data points of input designs and their corresponding values are available. We approach this problem as a conditional generation task, where a model conditions on a few labeled examples and the desired output to generate an optimal input design. To this end, we introduce Experiment Pretrained Transformers (ExPT), a foundation model for few-shot experimental design that employs a novel combination of synthetic pretraining with in-context learning. In ExPT, we only assume knowledge of a finite collection of unlabelled data points from the input domain and pretrain a transformer neural network to optimize diverse synthetic functions defined over this domain. Unsupervised pretraining allows ExPT to adapt to any design task at test time in an in-context fashion by conditioning on a few labeled data points from the target task and generating the candidate optima. We evaluate ExPT on few-shot experimental design in challenging domains and demonstrate its superior generality and performance compared to existing methods. The source code is available at https://github.com/tung-nd/ExPT.git., Comment: 2023 Conference on Neural Information Processing Systems (NeurIPS)

Federated Learning (FL) is a prominent distributed learning paradigm facilitating collaboration among nodes within an edge network to co-train a global model without centralizing data. By shifting computation to the network edge, FL offers robust and responsive edge-AI solutions and enhance privacy-preservation. However, deploying deep FL models within edge environments is often hindered by communication bottlenecks, data heterogeneity, and memory limitations. To address these challenges jointly, we introduce FeDEQ, a pioneering FL framework that effectively employs deep equilibrium learning and consensus optimization to exploit a compact shared data representation across edge nodes, allowing the derivation of personalized models specific to each node. We delve into a unique model structure composed of an equilibrium layer followed by traditional neural network layers. Here, the equilibrium layer functions as a global feature representation that edge nodes can adapt to personalize their local layers. Capitalizing on FeDEQ's compactness and representation power, we present a novel distributed algorithm rooted in the alternating direction method of multipliers (ADMM) consensus optimization and theoretically establish its convergence for smooth objectives. Experiments across various benchmarks demonstrate that FeDEQ achieves performance comparable to state-of-the-art personalized methods while employing models of up to 4 times smaller in communication size and 1.5 times lower memory footprint during training.

Given a collection $\{ G_i\}_{i=1}^d$ of finite groups and a ring $R$, we have previously introduced and studied certain foundational properties of the join ring $\mathcal{J}_{G_1, G_2, \ldots, G_d}(R)$. This ring bridges two extreme worlds: matrix rings $M_n(R)$ on one end, and group rings $R[G]$ on the other. The construction of this ring was motivated by various problems in graph theory, network theory, nonlinear dynamics, and neuroscience. In this paper, we continue our investigations of this ring, focusing more on its arithmetic properties. We begin by constructing a generalized augmentation map that gives a structural decomposition of this ring. This decomposition allows us to compute the zeta function of the join of group rings. We show that the join of group rings is a natural home for studying the concept of simultaneous primitive roots for a given set of primes. This concept is related to the order of the unit group of the join of group rings. Finally, we characterize the join of group rings over finite fields with the property that the order of every unit divides a fixed number. Remarkably, Mersenne and Fermat primes unexpectedly emerge within the context of this exploration., Comment: 21 pages

The Erd\H{o}s-Hajnal conjecture says that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $2^{c\log|G|}$ (a graph is ``$H$-free'' if no induced subgraph is isomorphic to $H$). The conjecture is known when $H$ is a path with at most four vertices, but remains open for longer paths. For the five-vertex path, Blanco and Buci\'c recently proved a bound of $2^{c(\log |G|)^{2/3}}$; for longer paths, the best existing bound is $2^{c(\log|G|\log\log|G|)^{1/2}}$. We prove a much stronger result: for any path $P$, every $P$-free graph $G$ has a clique or stable set of size at least $2^{(\log |G|)^{1-o(1)}}$. We strengthen this further, weakening the hypothesis that $G$ is $P$-free by a hypothesis that $G$ does not contain ``many'' copies of $P$, and strengthening the conclusion, replacing the large clique or stable set outcome with a ``near-polynomial'' version of Nikiforov's theorem.

Fekete polynomials associated to quadratic Dirichlet characters have interesting arithmetic properties, and have been studied in many works. In this paper, we study a seemingly simpler yet rich variant: the Fekete polynomial $F_n(x) = \sum_{a=1}^n \chi_n(a) x^a$ associated to a principal Dirichlet character $\chi_n$ of modulus $n$. We investigate the cyclotomic factors of $F_n$ and conjecturally describe all of them. One interesting observation from our computations is that the non-cyclotomic part $f_n$ of $F_n(x)/x$ seems to be always irreducible. We study this factor closely in the special case that $n$ is a product of two odd primes, proving separability in specific cases, and studying its coefficients and special values. Combining these theoretical results with computational evidence lets us identify the Galois group of $f_n$ for small $n$, and raises precise questions in general., Comment: Comments are welcome