论文检索

Optimization · Convex

Ji Qi, Mingxiao Liu, VIET THUC, Yuzhe Li, Zhuoshi Pan, Gene Cheung, Hong Zhao

To forecast traffic with both spatial and temporal dimensions, we unroll a mixed-graph-based optimization algorithm into a lightweight and interpretable transformer-like neural net. Specifically, we construct two graphs: an undirected graph $\mathcal{G}^u$ capturing spatial correlations across geography, and a directed graph $\mathcal{G}^d$ capturing sequential relationships over time. We formulate a prediction problem for the future samples of signal $\mathbf{x}$, assuming it is ``smooth'' with respect to both $\mathcal{G}^u$ and $\mathbf{G}^d$, where we design new $\ell_2$ and $\ell_1$-norm variational terms to quantify and promote signal smoothness (low-frequency reconstruction) on a directed graph. We construct an iterative algorithm based on alternating direction method of multipliers (ADMM), and unroll it into a feed-forward network for data-driven parameter learning. We periodically insert graph learning modules for $\mathcal{G}^u$ and $\mathcal{G}^d$, which are akin to the self-attention mechanism in classical transformers. Experiments show that our unrolled networks achieve competitive traffic forecast performance as state-of-the-art prediction schemes, while reducing parameter counts drastically.

Social Aspects · Accountability, Transparency, and Interpretability

Viet-Hung Tran, Zichi Zhang, Ngoc Doan, Xuan Hoang Nguyen, Phi Nguyen, Yimeng An, Peixin Li, Hans Vandierendonck, Ira Assent, Thai Son Mai

Deep Neural Networks (DNNs) achieve outstanding performance in Time Series Classification (TSC) yet remain opaque "black boxes", hindering their adoption in sensitive domains. While Explainable AI (XAI) aims to bridge this gap, existing TSC XAI methods rely on a single perspective and incur significant computational costs, making them difficult to integrate into real-time applications. To overcome these challenges, we propose a framework, containing two key techniques called Instance-level Multi-Expert Knowledge Distillation (IMEKD) and Semi-Amortized Optimization Explanation (SAOE). Unlike static methods, our IMEKD approach bridges the gap between explanation methods by dynamically selecting the best attribution map from a pool of "XAI experts" for each instance. We then distill this instance-optimal knowledge into a DNN using our SAOE framework, a dual-stage process that learns a global attribution via distillation and refines it using faithfulness and robustness losses, aligning the optimization with objectives of human evaluation. To the best of our knowledge, this is the first work to unify multi-expert selection with semi-amortized optimization for TSC XAI. Also, we introduce a Faithfulness-Preserving Segmentation (FPS) mechanism that converts point-wise maps into interpretable segments without sacrificing fidelity to align explanations with human intuition. Comprehensive experiments on four synthetic datasets, a ECG dataset with human-verified ground truth, and 11 multivariate UEA benchmarks across three DNN architectures show that our framework significantly outperforms the current state-of-the-art (SOTA) in terms of faithfulness, robustness, and computational efficiency.

Deep Learning · Graph Neural Networks

Nicolas Keriven

Oversmoothing has long been identified as a major limitation of Graph Neural Networks (GNNs): input node features are smoothed at each layer and converge to a constant non-informative representation, *if the weights of the GNN are sufficiently bounded*. This assumption is crucial: if, on the contrary, the weights are sufficiently large, then oversmoothing may be compensated. Theoretically, GNN could thus *learn* to not oversmooth. However, this does not really happen in practice, which prompts us to examine oversmoothing from an *optimization* point of view. In this paper, we analyze *backward oversmoothing*, that is, the notion that backpropagated errors are also subject to oversmoothing from output to input. With non-linearities, we outline the key role of the *interaction* between forward and backward smoothing. Moreover, we show that, due to backward oversmoothing, GNNs provably exhibit many *spurious stationary points*: as soon as the *last* layer is trained, the *whole* GNN is at a stationary point. As a result, we can exhibit regions where gradients are near-zero while the loss stays high. Additionally, we prove that this is *specific* to GNNs, and does not necessarily hold for Multi-Layer Perceptrons. This paper is a step toward a more complete comprehension of the optimization landscape of GNNs.

Applications · Neuroscience, Cognitive Science

Jea Kwon, Dong-Kyum Kim, Jiwon Kim, Yonghyun Kim, Woong Kook, MEEYOUNG CHA

Memory formation is fundamental to intelligence, yet whether deep neural networks preserve identifiable memory traces—analogous to biological memory units—remains an open question. This work introduces a geometric framework to identify such "AI engrams," by formalizing the neuroscientific criteria of specificity, reactivation, sufficiency, and necessity into a constrained inverse problem. We derive a closed-form estimator that isolates individual memory traces from globally entangled parameters. Theoretical analysis reveals that this biologically-derived solution corresponds to a natural gradient update on the parameter manifold. AI engrams enable surgical manipulation of learned knowledge: any subset of memories can be composed or erased through linear arithmetic, without iterative optimization. Experiments ranging from simple MLPs to LLMs demonstrate the causal validity and substantial scalability of AI engrams. Together, these results bridge theories of biological memory and artificial representation learning, offering geometric insight into how deep networks simultaneously support functional specificity within distributed storage.

Applications · Neuroscience, Cognitive Science

Jea Kwon, Dong-Kyum Kim, Jiwon Kim, Yonghyun Kim, Woong Kook, MEEYOUNG CHA

Memory formation is fundamental to intelligence, yet whether deep neural networks preserve identifiable memory traces—analogous to biological memory units—remains an open question. This work introduces a geometric framework to identify such "AI engrams," by formalizing the neuroscientific criteria of specificity, reactivation, sufficiency, and necessity into a constrained inverse problem. We derive a closed-form estimator that isolates individual memory traces from globally entangled parameters. Theoretical analysis reveals that this biologically-derived solution corresponds to a natural gradient update on the parameter manifold. AI engrams enable surgical manipulation of learned knowledge: any subset of memories can be composed or erased through linear arithmetic, without iterative optimization. Experiments ranging from simple MLPs to LLMs demonstrate the causal validity and substantial scalability of AI engrams. Together, these results bridge theories of biological memory and artificial representation learning, offering geometric insight into how deep networks simultaneously support functional specificity within distributed storage.

Deep Learning · Graph Neural Networks

Lorenz Kummer, Samir Moustafa, Anatol Ehrlich, Franka Bause, Marco Nennstiel, Przemysław Wałęga, Nils M. Kriege

Graph neural networks (GNNs) are widely used, but how parameter sparsity affects the expressivity of relational (RGNNs) and temporal (TGNNs) variants is poorly understood. The Strong Expressive Lottery Ticket Hypothesis (SELTH) posits the existence of sparse GNNs that preserve Weisfeiler-Leman (WL) expressivity on static graphs. We generalize this existence result to a probabilistic statement for multi-relational and temporal domains via the relational WL (RWL). We prove that sufficiently parameterized RGNNs contain sparse subnetworks that maintain 1-RWL expressivity and derive a lower bound on the probability that a random pruning yields such a subnetwork. We show that common TGNNs and cross-graph message passing schemes admit RGNN reformulations such that they inherit these guarantees and, moreover, that the expressivity of a sparse RGNN is connected to its optimization behavior under common update regimes. Experiments instantiate the bound, compare it to empirical probabilities on synthetic data, and study how pre-training expressivity relates to optimization and prediction quality metrics on temporal and molecular benchmarks.

Optimization · Everything Else

Haoming Meng, Anton Sugolov, Vardan Papyan

Deep neural networks with repeated blocks, such as transformers and ResNets, often exhibit closely related representational structure across layers that emerges with training. Motivated by this observation, we introduce *Gradient Smoothing*, a general training paradigm that couples gradient updates across blocks and admits a natural interpretation as a preconditioning method. Our framework applies structured smoothing operators to layer-wise updates, such as weighted averages and exponential moving averages, with minimal computational overhead. We evaluate Gradient Smoothing across a range of architectures and training regimes, including RL post-training of LLMs on reasoning tasks, as well as diffusion and classification with Vision Transformers. Across these settings, Gradient Smoothing consistently improves generalization performance, in addition to promoting structured representation evolution across layers. These results suggest that gradient smoothing is a simple and broadly applicable technique for improving training in modern deep networks.

Deep Learning · Graph Neural Networks

Kunal Mukherjee, Zulfikar Alom, Tran Gia Bao Ngo, Cuneyt Akcora, Murat Kantarcioglu

The rise of bot accounts on social media poses significant risks to public discourse. To address this threat, modern bot detectors increasingly rely on Graph Neural Networks (GNNs). However, the effectiveness of these GNN-based detectors in real-world settings remains poorly understood. In practice, attackers continuously adapt their strategies as well as must operate under domain-specific and temporal constraints, which can fundamentally limit the applicability of existing attack methods. As a result, there is a critical need for robust GNN-based bot detection methods under realistic, constraint-aware attack scenarios. To address this gap, we introduce BOCLOAK to systematically evaluate the robustness of GNN-based social bot detection via both edge editing and node injection adversarial attacks under realistic constraints. BOCLOAK constructs a probability measure over spatio-temporal neighbor features and learns an optimal transport geometry that separates human and bot behaviors. It then decodes transport plans into sparse, plausible edge edits that evade detection while obeying real-world constraints. We evaluate BOCLOAK across three social bot datasets, five state-of-the-art bot detectors, three adversarial defenses, and compare it against four leading graph adversarial attack baselines. BOCLOAK achieves up to 80.13% higher attack success rates while using 99.80% less GPU memory under realistic real-world constraints. Most importantly, BOCLOAK shows that optimal transport provides a lightweight, principled framework for bridging adversarial attacks and real-world bot detection

Deep Learning · Graph Neural Networks

Guolei Zeng, Hezhe Qiao, Guoguo Ai, Jinsong Guo, Guansong Pang

Semi-supervised graph anomaly detection (GAD), which assumes a subset of annotated normal nodes available during training, is among the most widely explored applications. However, the normality learned by existing semi-supervised GAD methods is limited to the labeled normal nodes, often inclining to overfitting the given patterns, thereby leading to high detection errors, such as high false positives. To overcome this limitation, we propose $GraphNC$, a graph normality calibration framework that leverages both labeled and unlabeled data to calibrate the normality from a teacher (a pre-trained semi-supervised GAD model) jointly in anomaly score and representation spaces. GraphNC includes two main components, anomaly score distribution alignment ($ScoreDA$) and perturbation-based normality regularization ($NormReg$). ScoreDA optimizes the anomaly scores of our model by aligning them with the score distribution yielded by the teacher. Due to accurate scores in most of the normal nodes and part of the anomaly nodes in the teacher, the alignment effectively pulls the anomaly scores of the two classes toward the two ends, resulting in more separable anomaly scores. To mitigate the misleading by inaccurate scores from the teacher, NormReg is designed to regularize the normality in representation space, making the representations of normal nodes more compact by minimizing a perturbation-guided consistency loss solely on the labeled nodes. Comprehensive experiments on six benchmarks demonstrate that GraphNC (1) consistently and substantially enhances the performance of teacher models from different GAD methods (2) achieves new state-of-the-art performance.

Deep Learning · Graph Neural Networks

Yali Fink, Ido Ben-Yair, Lars Ruthotto, Eran Treister

The scalable solution of large sparse linear systems is a bottleneck in scientific computing and graph analysis. While algebraic multigrid (AMG) offers optimal linear scaling, its performance is severely constrained by the trade-off between the sparsity and convergence quality of coarse-grid operators. Classical AMG heuristics struggle to balance these objectives, often sacrificing stability for sparsity. We propose RAPNet, a graph neural network (GNN) framework that resolves this trade-off by learning to generate sparse, robust coarse operators directly from the sparse algebraic system. Key to our approach is a level-wise training strategy that enables learning from small subgraphs and generalization to million-node domains, bypassing the bottlenecks of prior neural AMG attempts. RAPNet executes exclusively during the solver setup phase, ensuring that the solve phase retains its favorable computational properties. We show that our method outperforms classical non-Galerkin baselines on diverse PDE discretizations and graph Laplacians, making it particularly effective for multi-query tasks such as eigenproblems, time-dependent simulations, and inverse or design problems.

Optimization · Everything Else

Peixin Huang, Yaoxin Wu, Yining Ma, Cathy Wu, Wen Song, Wei Zhang

Mixed-integer linear programming (MILP) is a foundational framework for combinatorial optimization across science and engineering, but remains hard to solve at scale due to NP-hardness.Recent learning-based methods typically model MILP instances as variable–constraint bipartite graphs and use Graph Neural Networks (GNNs) for representation learning, yet their locality limits representation power.We propose an attention-driven neural backbone that adopts an element-centric view of variables and constraints, with dual attention performing parallel intra-type self-attention and inter-type cross-attention.Across three representative tasks at the instance, element, and solving-state levels, our model consistently outperforms conventional GNN-based architectures, highlighting attention-based, element-centric modeling as a powerful foundation for learning-enhanced combinatorial optimization.

Shishang Wu, Bingjing Tang, Vinayak A Rao

Generative models such as diffusion models and transformers are powerful tools for learning complex data distributions and generating new samples. However, their black-box nature limits interpretability, and the learned distributions may violate side knowledge arising from domain expertise. We represent such side knowledge as probability distributions over noisy functions of the modeled objects and seek to minimally adjust the generative model to satisfy such constraints. Our approach is to optimize the dual of the corresponding constrained optimization problem, encoding the infinite-dimensional dual variable using a neural network. We introduce a simple and efficient score-based method for fitting the parameters of this neural network, and for simulating from the resulting adjusted distribution. We evaluate our approach on a number of synthetic tasks, as well on two real-world problems: a regularized nonparametric maximum likelihood estimation problem, and the incorporation of class-level fairness constraints into image diffusion models.

Optimization · Stochastic

Dimitris Oikonomou, Nicolas Loizou

The stochastic Polyak step size (SPS) has proven to be a promising choice for stochastic gradient descent (SGD), delivering competitive performance relative to state-of-the-art methods on smooth convex and non-convex optimization problems, including deep neural network training. However, extensions of this approach to non-smooth settings remain in their early stages, often relying on interpolation assumptions or requiring knowledge of the optimal solution. In this work, we propose a novel SPS variant, Safeguarded SPS (SPS$_{safe}$), for the stochastic subgradient method, and provide rigorous convergence guarantees for non-smooth convex optimization with no need for strong assumptions. We further incorporate momentum into the update rule, yielding equally tight theoretical results. Comprehensive experiments on convex benchmarks and deep neural networks corroborate our theory: the proposed step size achieves competitive performance to existing adaptive baselines and exhibits stable behavior across a wide range of problem settings. Finally, in the context of deep neural network training, the gradient norms under our step size do not collapse to (near) zero, indicating robustness to vanishing gradients.

Optimization · Discrete and Combinatorial Optimization

Wenzheng Pan, Jiale Ma, Nuoyan Chen, Yang Li, Junchi Yan

Despite the fast progress of Neural Combinatorial Optimization (NCO) on graphs, existing solvers mainly learn a narrow task (e.g., uniform TSP) at a time and hardly handle instances over diverse distributions. This paper proposes M$^2$GenCO, a Multi-task learning framework that pioneers the instantiation of the Meta-learning mechanism with diffusion-based Generative solving for CO Problems (COPs) on graphs, first formulating "tasks" in meta-learning as distinct problem types instead of instances of the same problem. With a tailored lightweight graph neural network, our framework performs effective joint pre-training on a variety of problem types and efficient fine-tuning to adapt for out-of-distribution scenarios. Further, we establish a benchmark comprising 5 classic graph COPs with varying scales and multiple distributions, forming 38 distinct test datasets that facilitate standard evaluation of generalizability and adaptability for NCO solvers. Empirically, M$^2$GenCO with greedy decoder yields an overall 9.16% performance gain with an average 95.6$\times$ acceleration for inference, and achieves concrete state-of-the-arts on all test sets with simple local searchers, maintaining superior solving time against previous neural methods. The computational resource and time consumption for training are saved by up to 82% and 91%, respectively.

Deep Learning · Attention Mechanisms

Tobias Schröder, Lester Mackey

We introduce WildCat, a high-accuracy, low-cost approach to compressing the attention mechanism in neural networks. While attention is a staple of modern network architectures, it is also notoriously expensive to deploy due to resource requirements that scale quadratically with the input sequence length $n$. WildCat avoids these quadratic costs by only attending over a small weighted coreset. Crucially, we select the coreset using a fast but spectrally-accurate subsampling algorithm -- randomly pivoted Cholesky -- and weight the elements optimally to minimise reconstruction error. Remarkably, given bounded inputs, WildCat approximates exact attention with super-polynomial $O(n^{-\sqrt{\log(\log(n))}})$ error decay while running in near-linear $O(n^{1+o(1)})$ time. In contrast, prior practical approximations either lack error guarantees or require quadratic runtime to guarantee such high fidelity. We couple this advance with a GPU-optimized PyTorch implementation and a suite of benchmark experiments demonstrating the benefits of WildCat for image generation, image classification, and language model KV cache compression.

General Machine Learning · Transfer, Multitask and Meta-learning

Fabian Morelli, Stephan Eckstein

Ensembles of neural networks typically outperform individual networks but incur large computational costs, whereas weight aggregation produces less costly, yet also less accurate, aggregate models. We introduce partial fusion of networks, which interpolates between ensembles and weight aggregation and thus allows for a flexible tradeoff between computational cost and performance. A direct way to achieve this is to extend existing weight aggregation methods based on neuron-level similarity between different networks, where partial fusion then only aggregates weights of neurons which are most similar. We showcase one particular method to jointly identify which neurons are most similar and match them via partial optimal transport. Further, we consider the more general perspective of weight aggregation and partial fusion as generalized pruning of ensemble models, where neurons cannot just be deleted, but also linearly combined. Finally, we show that generalized pruning applied to a single network yields similar benefits as partial fusion by allowing for a tradeoff between isolating, deleting, and linearly combining neurons based on similarity.

Deep Learning · Theory

Yuri Kinoshita, Naoki Nishikawa, Taro Toyoizumi

Dataset distillation, a training-aware data compression technique, has recently attracted increasing attention as an effective tool for mitigating costs of optimization and data storage. However, progress remains largely empirical. Mechanisms underlying the extraction of task-relevant information from the training process and the efficient encoding of such information into synthetic data points remain elusive. In this paper, we theoretically analyze practical algorithms of dataset distillation applied to the gradient-based training of two-layer neural networks with width $L$. By focusing on a non-linear task structure called multi-index model, we prove that the low-dimensional structure of the problem is efficiently encoded into the resulting distilled data. This dataset reproduces a model with high generalization ability for a required memory complexity of $\Theta(r^2d+L)$, where $d$ and $r$ are the input and intrinsic dimensions of the task. To the best of our knowledge, this is one of the first theoretical works that include a specific task structure, leverage its intrinsic dimensionality to quantify the compression rate and study dataset distillation implemented solely via gradient-based algorithms.

General Machine Learning · Evaluation

Yuanzhe Hu, Xiaopeng Wang, Yuxin Wang, Xiaokun Zhong, Haiquan Lu, Tianyu Pang, Michael Mahoney, Yujun Yan, Pu Ren, Yaoqing Yang

Neural networks (NNs) trained under different hyperparameters can fall into distinct training ``regimes'', with models in the same regime showing homogeneous properties and models across regimes differing qualitatively. In this paper, we analyze multi-regime patterns in scientific machine learning (SciML) models by characterizing these regimes and the transitions between them. We show how different regimes affect trainability and generalization, and we demonstrate that loss-landscape analysis enables regime-based diagnostics to understand, evaluate, and improve SciML model training. Our analysis yields three key insights: (1) compared with computer vision (CV) tasks, SciML models exhibit significantly more pathological loss landscapes; (2) optimization methods are regime-specific -- different optimization strategies help in different regimes, but none is uniformly effective; and (3) SciML models exhibit fine-grained failure modes that challenge conventional interpretations of standard loss-landscape metrics. Using this study, we aim to unify our understanding of seemingly different failure modes across SciML tasks and obtain task-oblivious insights and methodologies for addressing these failures. We validate these findings across widely used SciML models, including physics-informed neural networks (PINNs), Fourier neural operators (FNOs), and Neural Ordinary Differential Equations (NeuralODEs), on benchmarks spanning representative ordinary and partial differential equations.

Deep Learning · Graph Neural Networks

Hangyuan Du, Rong Wang, Weihong Zhang, Lu Bai, Liang Bai, Yu Xie, Wenjian Wang

Graph neural networks (GNNs) excel in graph analyzing tasks but often suffer from poor generalization under Out-of-Distribution (OOD) environments. Although this problem has attracted increasing attention, most solutions primarily rely on empirical designs, lacking effective mechanisms to characterize and quantify invariance for graph representation learning. To address these limitations, we propose DIGL, a novel graph learning method that improves the OOD generalization of GNNs. Our work makes an initial attempt to geometrize invariance for graphs by introducing computational optimal transport (OT) theory to characterize invariance principle. Specifically, we formulate the underlying invariant prototype shared by graphs across different environments as a distribution barycenter, and consider graph representations in each specific environment as distortions of the prototype. Building on this idea, we establish an invariant learning framework to promote the model to learn purely invariant graph representations for downstream tasks. Moreover, we derive a unified optimization objective for model implementation and provide theoretical analysis to justify our method. Extensive experiments on a broad range of benchmark datasets demonstrate the superior generalization ability of our method compared with baseline methods under various OOD settings.

Probabilistic Methods · Bayesian Models and Methods

Mame Diarra Toure, David A Stephens

Bayesian neural networks promise calibrated uncertainty but require $O(mn)$ parameters for standard mean-field Gaussian posteriors. We argue this cost is often unnecessary, particularly when weight matrices exhibit fast singular value decay. By parameterizing weights as $W = AB^{\top}$ with $A \in \mathbb{R}^{m \times r}$, $B \in \mathbb{R}^{n \times r}$, we induce a posterior that is singular with respect to the Lebesgue measure, concentrating on the rank-$r$ manifold. This singularity captures structured weight correlations through shared latent factors, geometrically distinct from mean-field's independence assumption. We derive PAC-Bayes generalization bounds whose complexity term scales as $\sqrt{r(m+n)}$ instead of $\sqrt{m n}$, and prove loss bounds that decompose the error into optimization and rank-induced bias using the Eckart-Young-Mirsky theorem. We further adapt recent Gaussian complexity bounds for low-rank deterministic networks to Bayesian predictive means by exploiting their stability under convex combinations. Empirically, across MLPs, LSTMs, and Transformers on standard benchmarks, our method achieves predictive performance competitive with 5-member Deep Ensembles while using up to $15\times$ fewer parameters. Furthermore, it substantially improves OOD detection and often improves calibration relative to mean-field and perturbation baselines.