Search

Graph Neural Networks (GNN) exhibit superior performance in graph representation learning, but their inference cost can be high, due to an aggregation operation that can require a memory fetch for a very large number of nodes. This inference cost is the major obstacle to deploying GNN models with \emph{online prediction} to reflect the potentially dynamic node features. To address this, we propose an approach to reduce the number of nodes that are included during aggregation. We achieve this through a sparse decomposition, learning to approximate node representations using a weighted sum of linearly transformed features of a carefully selected subset of nodes within the extended neighbourhood. The approach achieves linear complexity with respect to the average node degree and the number of layers in the graph neural network. We introduce an algorithm to compute the optimal parameters for the sparse decomposition, ensuring an accurate approximation of the original GNN model, and present effective strategies to reduce the training time and improve the learning process. We demonstrate via extensive experiments that our method outperforms other baselines designed for inference speedup, achieving significant accuracy gains with comparable inference times for both node classification and spatio-temporal forecasting tasks.

Efficiently determining the satisfiability of a boolean equation -- known as the SAT problem for brevity -- is crucial in various industrial problems. Recently, the advent of deep learning methods has introduced significant potential for enhancing SAT solving. However, a major barrier to the advancement of this field has been the scarcity of large, realistic datasets. The majority of current public datasets are either randomly generated or extremely limited, containing only a few examples from unrelated problem families. These datasets are inadequate for meaningful training of deep learning methods. In light of this, researchers have started exploring generative techniques to create data that more accurately reflect SAT problems encountered in practical situations. These methods have so far suffered from either the inability to produce challenging SAT problems or time-scalability obstacles. In this paper we address both by identifying and manipulating the key contributors to a problem's ``hardness'', known as cores. Although some previous work has addressed cores, the time costs are unacceptably high due to the expense of traditional heuristic core detection techniques. We introduce a fast core detection procedure that uses a graph neural network. Our empirical results demonstrate that we can efficiently generate problems that remain hard to solve and retain key attributes of the original example problems. We show via experiment that the generated synthetic SAT problems can be used in a data augmentation setting to provide improved prediction of solver runtimes.

Despite recent advances in training and prompting strategies for Large Language Models (LLMs), these models continue to face challenges with complex logical reasoning tasks that involve long reasoning chains. In this work, we explore the potential and limitations of using graph-based synthetic reasoning data as training signals to enhance LLMs' reasoning capabilities. Our extensive experiments, conducted on two established natural language reasoning tasks -- inductive reasoning and spatial reasoning -- demonstrate that supervised fine-tuning (SFT) with synthetic graph-based reasoning data effectively enhances LLMs' reasoning performance without compromising their effectiveness on other standard evaluation benchmarks.

Transit is essential for urban transportation and achieving net-zero targets. In urban areas like the Chicago Metropolitan Region, transit enhances mobility and connects people, fostering a dynamic economy. To quantify the mobility and selected economic impacts of transit, we use a novel agent-based simulation model POLARIS to compare baseline service against a scenario in which transit is completely removed. The transit-removal scenario assumes higher car ownership and results in higher traffic congestion, numerous activity cancellations, and economic decline. In this scenario, average travel times increase by 14.2% regionally and 34.7% within the City of Chicago. The resulting congestion causes significant activity cancellations despite increased car ownership: 11.8% of non-work and 2.8% of work/school activities regionally, totaling an 8.6% overall cancellation rate. In the city, non-work cancellations would reach 26.9%, and work/school cancellations 7.3%, leading to a 19.9% overall cancellation rate. The impact varies between groups. Women and lower-income individuals are more likely to cancel activities than men and higher-income groups. Women account for 53.7% of non-work and 53.0% of total cancellations. The lowest 40% income group experiences 50.2% of non-work and 48.0% of overall cancellations. Combined, activity cancellations, travel time losses, and increased car ownership cost the region $35.4 billion. With annual public transit funding at $2.7 billion, the ratio is 13 to 1, underscoring transit's critical role in mobility, equity, and economic health.

This paper concerns pairs of models of the theory of the differential field of logarithmic-exponential transseries that are tame as a pair of real closed fields. That is, the smaller model is bounded inside the larger model and there exists a standard part map. This covers for instance the differential fields of hyperseries or surreal numbers or maximal Hardy fields equipped with suitable enlargements of the differential field of transseries. The theory of such pairs is complete and model complete in a natural language and it has quantifier elimination in the same language expanded by two predicates and a standard part map. Additionally, the smaller model is purely stably embedded in the pair, and hence so is the constant field. More generally, we study differential-Hensel-Liouville closed pre-$H$-fields, i.e., pre-$H$-fields that are differential-henselian, real closed, and closed under exponential integration, equipped with lifts of their differential residue fields, and establish similar results in that setting relative to the differential residue field., Comment: 24 pages

Inspired by transformation optics and photonic crystals, this paper presents a computational investigation into the interaction between water surface waves and array waveguides of cylinders with multiple previously unexplored lattice geometries, including, for the first time, quasiperiodic geometries. Extending beyond conventional square and hexagonal periodic arrays, transformation optics has opened up entirely new opportunities to investigate water wave propagation through arrays based on quasiperiodic lattices, and quasiperiodically arranged vacancy defects. Using the linear potential flow open-source code Capytaine, missing element and $\tau$-scaled Fibonacci square lattices, the Penrose lattice, hexagonal $H_{00}$ lattice and Amman-Beenker lattice are investigated. The existence of band gaps for all arrays is observed. An hexagonal lattice with vacancy defects transmits the least energy. Bragg diffraction consistent with rotational symmetry is observed from all arrays. Waves will distort significantly to achieve resonance with arrays, supporting transformation-based waveguides. The possible uses include adaptation to more versatile waveguides with applications such as offshore renewable energy and coastal defence., Comment: 23 pages, 6 figures

In this article we show that a large class of infinite measure preserving dynamical systems that do not admit physical measures nevertheless exhibit strong statistical properties. In particular, we give sufficient conditions for existence of a distinguished natural measure $\nu$ such that the pushforwards of any absolutely continuous probability measure converge to $\nu$. Moreover, we obtain a distributional limit law for empirical measures. We also extend existing results on the characterisation of the set of almost sure limit points for empirical measures. Our results apply to various intermittent maps with multiple neutral fixed points preserving an infinite $\sigma$-finite absolutely continuous measure.

Machine learning models can solve complex tasks but often require significant computational resources during inference. This has led to the development of various post-training computation reduction methods that tackle this issue in different ways, such as quantization which reduces the precision of weights and arithmetic operations, and dynamic networks which adapt computation to the sample at hand. In this work, we propose a more general dynamic network that can combine both quantization and early exit dynamic network: QuEE. Our algorithm can be seen as a form of soft early exiting or input-dependent compression. Rather than a binary decision between exiting or continuing, we introduce the possibility of continuing with reduced computation. This complicates the traditionally considered early exiting problem, which we solve through a principled formulation. The crucial factor of our approach is accurate prediction of the potential accuracy improvement achievable through further computation. We demonstrate the effectiveness of our method through empirical evaluation, as well as exploring the conditions for its success on 4 classification datasets.

The transition-metal dicyanides M(CN)$_2$ (M = Zn, Cd) are amongst the most important negative thermal expansion (NTE) materials known, favoured for the magnitude, isotropy, and thermal persistence of the NTE behaviour they show. The conventional picture of the NTE mechanism in this family is one of correlated rotations and translations of M(C/N)$_4$ polyhedra acting to draw the diamondoid network of M--CN--M linkages in on itself. An implication of this mechanism is increased transverse vibrational motion of C and N atoms relative to the isotropic displacements of M atoms, which act as anchors. Here, we use a combination of neutron total scattering measurements and \emph{ab initio} calculations to reassess the vibrational behaviour of the M(CN)$_2$ family. We find that M, C, and N atoms all exhibit similar degrees of local thermal motion, such that the cyanide linkages behave as pseudo-springs connecting M$\ldots$M pairs. This interpretation leads us to uncover a `hidden' dispersion in the M(CN)$_2$ phonon dispersions, closely related to that of diamond and silicon themselves. By virtue of this mapping, a simple geometric model based on the competing energy scales of network stretching and flexing -- long applied to interpret NTE modes in C and Si -- turns out to capture the key NTE physics of M(CN)$_2$, especially at low temperatures. Our study highlights the potential insight gained by coarse-graining the complex lattice dynamics of framework materials in terms of what we call `framework modes' -- the correlated distortions of the underlying network structure itself.

In terms of accuracy, Graph Neural Networks (GNNs) are the best architectural choice for the node classification task. Their drawback in real-world deployment is the latency that emerges from the neighbourhood processing operation. One solution to the latency issue is to perform knowledge distillation from a trained GNN to a Multi-Layer Perceptron (MLP), where the MLP processes only the features of the node being classified (and possibly some pre-computed structural information). However, the performance of such MLPs in both transductive and inductive settings remains inconsistent for existing knowledge distillation techniques. We propose to address the performance concerns by using a specially-designed student model instead of an MLP. Our model, named Routing-by-Memory (RbM), is a form of Mixture-of-Experts (MoE), with a design that enforces expert specialization. By encouraging each expert to specialize on a certain region on the hidden representation space, we demonstrate experimentally that it is possible to derive considerably more consistent performance across multiple datasets.

The van der Heijde modification of the Sharp (SvdH) score is a widely used radiographic scoring method to quantify damage in Rheumatoid Arthritis (RA) in clinical trials. However, its complexity with a necessity to score each individual joint, and the expertise required limit its application in clinical practice, especially in disease progression measurement. In this work, we addressed this limitation by developing a bespoke, automated pipeline that is capable of predicting the SvdH score and RA severity from hand radiographs without the need to localise the joints first. Using hand radiographs from RA and suspected RA patients, we first investigated the performance of the state-of-the-art architectures in predicting the total SvdH score for hands and wrists and its corresponding severity class. Secondly, we leveraged publicly available data sets to perform transfer learning with different finetuning schemes and ensemble learning, which resulted in substantial improvement in model performance being on par with an experienced human reader. The best model for RA scoring achieved a Pearson's correlation coefficient (PCC) of 0.925 and root mean squared error (RMSE) of 18.02, while the best model for RA severity classification achieved an accuracy of 0.358 and PCC of 0.859. Our score prediction model attained almost comparable accuracy with experienced radiologists (PCC = 0.97, RMSE = 18.75). Finally, using Grad-CAM, we showed that our models could focus on the anatomical structures in hands and wrists which clinicians deemed as relevant to RA progression in the majority of cases., Comment: 16 pages, 5 figures, accepted by MIUA 2024

Online deep learning solves the problem of learning from streams of data, reconciling two opposing objectives: learn fast and learn deep. Existing work focuses almost exclusively on exploring pure deep learning solutions, which are much better suited to handle the "deep" than the "fast" part of the online learning equation. In our work, we propose a different paradigm, based on a hybrid multilearner approach. First, we develop a fast online logistic regression learner. This learner does not rely on backpropagation. Instead, it uses closed form recursive updates of model parameters, handling the fast learning part of the online learning problem. We then analyze the existing online deep learning theory and show that the widespread ODL approach, currently operating at complexity $O(L^2)$ in terms of the number of layers $L$, can be equivalently implemented in $O(L)$ complexity. This further leads us to the cascaded multilearner design, in which multiple shallow and deep learners are co-trained to solve the online learning problem in a cooperative, synergistic fashion. We show that this approach achieves state-of-the-art results on common online learning datasets, while also being able to handle missing features gracefully. Our code is publicly available at https://github.com/AntonValk/MODL.

Boolean satisfiability (SAT) problems are routinely solved by SAT solvers in real-life applications, yet solving time can vary drastically between solvers for the same instance. This has motivated research into machine learning models that can predict, for a given SAT instance, which solver to select among several options. Existing SAT solver selection methods all rely on some hand-picked instance features, which are costly to compute and ignore the structural information in SAT graphs. In this paper we present GraSS, a novel approach for automatic SAT solver selection based on tripartite graph representations of instances and a heterogeneous graph neural network (GNN) model. While GNNs have been previously adopted in other SAT-related tasks, they do not incorporate any domain-specific knowledge and ignore the runtime variation introduced by different clause orders. We enrich the graph representation with domain-specific decisions, such as novel node feature design, positional encodings for clauses in the graph, a GNN architecture tailored to our tripartite graphs and a runtime-sensitive loss function. Through extensive experiments, we demonstrate that this combination of raw representations and domain-specific choices leads to improvements in runtime for a pool of seven state-of-the-art solvers on both an industrial circuit design benchmark, and on instances from the 20-year Anniversary Track of the 2022 SAT Competition., Comment: Accepted by KDD 2024

Fractals and quasiperiodic structures share self-similarity as a structural property. Motivated by the link between Fibonacci fractals and quasicrystals which are scaled by the golden mean ratio $\frac{1+\sqrt{5}}{2}$, we introduce and characterize a family of metallic-mean ratio fractals. We calculate the spatial properties of this generalized family, including their boundaries, which are also fractal. We then demonstrate how these fractals can be related to aperiodic tilings, and show how we can decorate them to produce new, fractal tilings., Comment: 12 (+5) pages, 12 (+4) figures. Submitted for community feedback

The existing definitions of graph convolution, either from spatial or spectral perspectives, are inflexible and not unified. Defining a general convolution operator in the graph domain is challenging due to the lack of canonical coordinates, the presence of irregular structures, and the properties of graph symmetries. In this work, we propose a novel and general graph convolution framework by parameterizing the kernels as continuous functions of pseudo-coordinates derived via graph positional encoding. We name this Continuous Kernel Graph Convolution (CKGConv). Theoretically, we demonstrate that CKGConv is flexible and expressive. CKGConv encompasses many existing graph convolutions, and exhibits a stronger expressiveness, as powerful as graph transformers in terms of distinguishing non-isomorphic graphs. Empirically, we show that CKGConv-based Networks outperform existing graph convolutional networks and perform comparably to the best graph transformers across a variety of graph datasets. The code and models are publicly available at https://github.com/networkslab/CKGConv., Comment: On International Conference on Machine Learning (ICML) 2024

Symmetry sharing facilitates coherent interfaces which can transition from periodic to quasiperiodic structures. Motivated by the design and construction of such systems, we present hexagonal quasiperiodic tilings with a single edge-length which can be considered as decorations of a periodic lattice. We introduce these tilings by modifying an existing family of golden-mean trigonal and hexagonal tilings, and discuss their properties in terms of this wider family. Then, we show how the vertices of these new systems can be considered as decorations or sublattice sets of a periodic triangular lattice. We conclude by simulating a simple Ising model on one of these decorations, and compare this system to a triangular lattice with random defects., Comment: 11 (+7) pages, 7 (+8) figures. Submitted for community feedback

Recommender systems have become an integral part of online platforms. Every day the volume of training data is expanding and the number of user interactions is constantly increasing. The exploration of larger and more expressive models has become a necessary pursuit to improve user experience. However, this progression carries with it an increased computational burden. In commercial settings, once a recommendation system model has been trained and deployed it typically needs to be updated frequently as new client data arrive. Cumulatively, the mounting volume of data is guaranteed to eventually make full batch retraining of the model from scratch computationally infeasible. Naively fine-tuning solely on the new data runs into the well-documented problem of catastrophic forgetting. Despite the fact that negative sampling is a crucial part of training with implicit feedback, no specialized technique exists that is tailored to the incremental learning framework. In this work, we take the first step to propose, a personalized negative reservoir strategy which is used to obtain negative samples for the standard triplet loss. This technique balances alleviation of forgetting with plasticity by encouraging the model to remember stable user preferences and selectively forget when user interests change. We derive the mathematical formulation of a negative sampler to populate and update the reservoir. We integrate our design in three SOTA and commonly used incremental recommendation models. We show that these concrete realizations of our negative reservoir framework achieve state-of-the-art results in standard benchmarks, on multiple standard top-k evaluation metrics.

The utilization of technology in second language learning and teaching has become ubiquitous. For the assessment of writing specifically, automated writing evaluation (AWE) and grammatical error correction (GEC) have become immensely popular and effective methods for enhancing writing proficiency and delivering instant and individualized feedback to learners. By leveraging the power of natural language processing (NLP) and machine learning algorithms, AWE and GEC systems have been developed separately to provide language learners with automated corrective feedback and more accurate and unbiased scoring that would otherwise be subject to examiners. In this paper, we propose an integrated system for automated writing evaluation with corrective feedback as a means of bridging the gap between AWE and GEC results for second language learners. This system enables language learners to simulate the essay writing tests: a student writes and submits an essay, and the system returns the assessment of the writing along with suggested grammatical error corrections. Given that automated scoring and grammatical correction are more efficient and cost-effective than human grading, this integrated system would also alleviate the burden of manually correcting innumerable essays., Comment: Supported by the SoTL Seed Program at UBC

We present our optical photometric observations of the 2022 eruption of the recurrent nova U Scorpii (U Sco) using 49,152 data points over 70 d following the optical peak. We have also analyzed its soft X-ray (0.3--1 keV) light curve by the Neil Gehrels Swift Observatory. During the 2022 eruption, the optical plateau stage started 13.8--15.0 d and ended 23.8--25.0 d after the optical peak. The soft X-ray stage started 14.6--15.3 d and ended 38.7--39.5 d after the optical peak. Both stages started later and had shorter durations, and the soft X-ray light curve peaked earlier and was less luminous compared to those during the U Sco 2010 eruption. These points suggest that there were differences in the envelope mass between the different cycles of the nova eruption. Furthermore, we have analyzed the optical eclipses during the 2022 eruption. The primary eclipse was first observed 10.4--11.6 d after the optical peak, earlier than the beginning of the optical plateau stage. This sequence of events can be explained by the receding ejecta photosphere associated with the expanding nova ejecta. We have determined the ingress and egress phases of the primary eclipses and estimated the outer radius of the optical light source centered at the white dwarf (WD). During the optical plateau stage, the source radius remained $\sim$1.2 times larger than the Roche volume radius of the primary WD, being close to the L1 point. When the optical plateau stage ended, the source radius drastically shrank to the tidal truncation radius within a few orbital periods. This previously unresolved phenomenon can be interpreted as a structural change in U Sco where the temporarily expanded accretion disk due to the nova wind returned to a steady state., Comment: 16 pages, 7 figures, 7 tables, accepted for publication in PASJ; doi:10.1093/pasj/psae010

This paper quantitatively analysed orchestral conducting patterns, and detected variations as a result of extraneous body movement during conducting, in the first experiment of its kind. A novel live conducting system featuring data capture, processing, and analysis was developed. Reliable data of an expert conductor's movements was collected, processed, and used to calculate average trajectories for different conducting techniques with various extraneous body movements; variations between extraneous body movement techniques and controlled technique were definitively determined in a novel quantitative analysis. A portable and affordable mechatronic system was created to capture and process live baton tip data, and was found to be accurate through calibration against a reliable reference. Experimental conducting field data was captured through the mechatronic system, and analysed against previously calculated average trajectories; the extraneous movement used during the field data capture was successfully identified by the system., Comment: 10 pages, 10 figures, accepted by ACRA2023

Adaptive importance sampling (AIS) methods provide a useful alternative to Markov Chain Monte Carlo (MCMC) algorithms for performing inference of intractable distributions. Population Monte Carlo (PMC) algorithms constitute a family of AIS approaches which adapt the proposal distributions iteratively to improve the approximation of the target distribution. Recent work in this area primarily focuses on ameliorating the proposal adaptation procedure for high-dimensional applications. However, most of the AIS algorithms use simple proposal distributions for sampling, which might be inadequate in exploring target distributions with intricate geometries. In this work, we construct expressive proposal distributions in the AIS framework using normalizing flow, an appealing approach for modeling complex distributions. We use an iterative parameter update rule to enhance the approximation of the target distribution. Numerical experiments show that in high-dimensional settings, the proposed algorithm offers significantly improved performance compared to the existing techniques.

Multiple news sources over the years have reported on the problematic effects of Digital Rights Management, yet there are no reforms for DRM development, simply removal. The issues are well-known to the public, frequently repeated even when addressed: impact on the software and to the devices that run them. Yet few, if any, have discussed it in recent years, especially with the intent of eliminating the shown issues. This study reviews Digital Rights Management as a general topic, including the various forms it can take, the current laws that affect DRM, and the current public reception and responses. This study describes the different types of DRM in general terms and then lists both positive and negative examples., Comment: 16 pages, 2 figures

The performance of transformers for time-series forecasting has improved significantly. Recent architectures learn complex temporal patterns by segmenting a time-series into patches and using the patches as tokens. The patch size controls the ability of transformers to learn the temporal patterns at different frequencies: shorter patches are effective for learning localized, high-frequency patterns, whereas mining long-term seasonalities and trends requires longer patches. Inspired by this observation, we propose a novel framework, Multi-resolution Time-Series Transformer (MTST), which consists of a multi-branch architecture for simultaneous modeling of diverse temporal patterns at different resolutions. In contrast to many existing time-series transformers, we employ relative positional encoding, which is better suited for extracting periodic components at different scales. Extensive experiments on several real-world datasets demonstrate the effectiveness of MTST in comparison to state-of-the-art forecasting techniques.

Algebraic varieties are the geometric shapes defined by systems of polynomial equations; they are ubiquitous across mathematics and science. Amongst these algebraic varieties are Q-Fano varieties: positively curved shapes which have Q-factorial terminal singularities. Q-Fano varieties are of fundamental importance in geometry as they are "atomic pieces" of more complex shapes - the process of breaking a shape into simpler pieces in this sense is called the Minimal Model Programme. Despite their importance, the classification of Q-Fano varieties remains unknown. In this paper we demonstrate that machine learning can be used to understand this classification. We focus on 8-dimensional positively-curved algebraic varieties that have toric symmetry and Picard rank 2, and develop a neural network classifier that predicts with 95% accuracy whether or not such an algebraic variety is Q-Fano. We use this to give a first sketch of the landscape of Q-Fanos in dimension 8. How the neural network is able to detect Q-Fano varieties with such accuracy remains mysterious, and hints at some deep mathematical theory waiting to be uncovered. Furthermore, when visualised using the quantum period, an invariant that has played an important role in recent theoretical developments, we observe that the classification as revealed by ML appears to fall within a bounded region, and is stratified by the Fano index. This suggests that it may be possible to state and prove conjectures on completeness in the future. Inspired by the ML analysis, we formulate and prove a new global combinatorial criterion for a positively curved toric variety of Picard rank 2 to have terminal singularities. Together with the first sketch of the landscape of Q-Fanos in higher dimensions, this gives new evidence that machine learning can be an essential tool in developing mathematical conjectures and accelerating theoretical discovery., Comment: 20 pages, 11 figures, 3 tables

Neural Temporal Point Processes (TPPs) have emerged as the primary framework for predicting sequences of events that occur at irregular time intervals, but their sequential nature can hamper performance for long-horizon forecasts. To address this, we introduce a novel approach that incorporates a diffusion generative model. The model facilitates sequence-to-sequence prediction, allowing multi-step predictions based on historical event sequences. In contrast to previous approaches, our model directly learns the joint probability distribution of types and inter-arrival times for multiple events. This allows us to fully leverage the high dimensional modeling capability of modern generative models. Our model is composed of two diffusion processes, one for the time intervals and one for the event types. These processes interact through their respective denoising functions, which can take as input intermediate representations from both processes, allowing the model to learn complex interactions. We demonstrate that our proposal outperforms state-of-the-art baselines for long-horizon forecasting of TPP., Comment: camera ready version for ICML

Large pretrained models, coupled with fine-tuning, are slowly becoming established as the dominant architecture in machine learning. Even though these models offer impressive performance, their practical application is often limited by the prohibitive amount of resources required for every inference. Early-exiting dynamic neural networks (EDNN) circumvent this issue by allowing a model to make some of its predictions from intermediate layers (i.e., early-exit). Training an EDNN architecture is challenging as it consists of two intertwined components: the gating mechanism (GM) that controls early-exiting decisions and the intermediate inference modules (IMs) that perform inference from intermediate representations. As a result, most existing approaches rely on thresholding confidence metrics for the gating mechanism and strive to improve the underlying backbone network and the inference modules. Although successful, this approach has two fundamental shortcomings: 1) the GMs and the IMs are decoupled during training, leading to a train-test mismatch; and 2) the thresholding gating mechanism introduces a positive bias into the predictive probabilities, making it difficult to readily extract uncertainty information. We propose a novel architecture that connects these two modules. This leads to significant performance improvements on classification datasets and enables better uncertainty characterization capabilities.