ICML 2026 Papers

Relational prediction tasks are fundamental in many real-world applications, where data are naturally stored in relational databases (RDBs). Relational Deep Learning (RDL) addresses this problem by modeling RDBs as graphs and applying graph neural networks (GNNs) for end-to-end learning. However, the full-resolution property is commonly adopted as a design principle in graph construction for RDBs to preserve relational semantics, which leads most existing methods to rely on fixed graph structures. In this paper, we propose **FROG**, a *F*ull-*R*esolution and *O*ptimizable *G*raph Structure Learning framework for RDL that formulates relational structure learning as a learnable table role modeling problem, allowing tables to contribute as nodes and edges in message passing. We further design role-driven message passing mechanisms to capture relational semantics, enabling joint optimization of graph structure and GNN representations. To ensure semantic consistency, we introduce functional dependency constraints that regularize representations across table and entity levels. Extensive experiments demonstrate that our method outperforms existing approaches and reveal how table roles impact downstream tasks, offering new insights into graph construction for RDL.

The community is increasingly exploring linear RNNs (LRNNs) as language models, motivated by their expressive power and parallelizability. While prior work establishes the expressivity benefits of LRNNs over transformers, it is unclear what makes LRNNs---but not traditional, *nonlinear* RNNs---as easy to parallelize in practice as transformers. We answer this question by providing a tight connection between types of RNNs and standard complexity classes. We show that LRNNs can be viewed as log-depth (bounded fan-in) arithmetic circuits, which represents only a slight depth overhead relative to log-depth boolean circuits that transformers admit. Furthermore, we show that nonlinear RNNs can solve $\mathsf L$-complete problems (and even $\mathsf P$-complete ones, under polynomial precision), revealing a fundamental barrier to parallelizing them as efficiently as transformers. Our theory also identifies fine-grained expressivity differences between recent popular LRNN variants: permutation-diagonal LRNNs are $\mathsf{NC}^1$-complete whereas diagonal-plus-low-rank LRNNs are more expressive ($\mathsf{PNC}^1$-complete). We provide further insight by associating each type of RNN with a corresponding automata-theoretic model that it can simulate. Together, our results reveal fundamental tradeoffs between nonlinear RNNs and different variants of LRNNs, providing a foundation for designing LLM architectures that achieve an optimal balance between expressivity and parallelism.

We present a novel framework for embedding hard constraint satisfaction into neural network (NN) architectures, specifically feedforward neural networks and transformers, with input-dependent affine constraints of arbitrary cardinality. Traditional constraint enforcement approaches either rely on penalty-based soft constraints, which offer no guarantee of satisfaction, or on post-processing methods that enforce constraints after the NN is trained, which may lead to suboptimality. We introduce a trainable constraint-affine (CAffine) layer into NNs, yielding CAffNet, which goes beyond enforcing affine constraints via fixed orthogonal or parallel projections and enables joint optimization with network parameters. Moreover, we impose no restrictions on the constraint space dimensions and establish that our construction preserves the universal approximation properties of NNs, while providing provable guarantees on constraint adherence for all inputs. Experimental validation demonstrates robust performance across diverse domains requiring guaranteed constraint satisfaction.

Federated Graph Learning (FGL) is a distributed machine learning paradigm based on graph neural networks, enabling secure and collaborative modeling of local graph data among clients. However, label noise in graph data can degrade the generalization performance of the global model. Existing federated label noise learning methods, primarily focused on computer vision tasks, often yield suboptimal results when directly applied to FGL. To address this issue, we propose a robust federated graph learning method with label noise, termed **FedRGL**. Specifically, FedRGL leverages the globally aggregated model and local subgraph structural information to implement a dual-perspective consistency noise-node filtering mechanism under class-aware dynamic thresholds. The resulting *class-aware dual-consistency filtering (CADF)* can also serve as a plug-and-play module, enhancing noise robustness across various subgraph federated learning frameworks. To better exploit the supervisory information from filtered noisy nodes, we employ the natural augmentation techniques from graph contrastive learning to assign high-confidence pseudo-labels to the noise nodes. Additionally, we measure model quality via the average predictive entropy of unlabeled nodes, enabling adaptive robust aggregation on the server side. Extensive experiments on real-world graph datasets show that FedRGL consistently outperforms existing methods under different noise rates, noise types, and client scales, achieving on average **5--8\%** higher accuracy and up to **30\%** improvement over the weakest baselines under noisy conditions. The source code is available at https://github.com/LDer66/FEDRGL-ICML26.

Likelihood-based training is the dominant paradigm in survival prediction. Under independent censoring, we can factorize the likelihood and optimize only the terms related to event modeling, effectively treating the censoring mechanism as incidental. This is justified when censoring is *non-informative*, i.e., when the censoring process shares no parameters with the event-time model. However, this may not hold in practice, and ignoring censoring contributions may discard useful signals for learning representations that can help to effectively estimate event distributions. Motivated by this, we argue that explicitly modeling censoring can improve representation learning and time-to-event estimation, particularly when event and censoring processes are coupled. We introduce a latent decomposition view in which observed covariates are mapped to latent components corresponding to event-specific, censoring-specific, confounding, and irrelevant information. We then learn decomposed representations for the first three categories to guide a better estimation of the event distribution. We instantiate our method on 4 popular deep-learning survival models and evaluate on 10 datasets (2 semi-synthetic and 8 real-world), showing consistent gains over strong baselines and multiple SOTA methods.

Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.

Molecular representation learning has achieved remarkable progress in molecular property prediction, yet out-of-distribution (OOD) generalization remains challenging. In practice, training data typically cover only a limited portion of the chemical space, causing models to rely on environment-dependent factors that fail to transfer when scaffold structures or functional compositions shift. To address this issue, we propose MoSIR, a framework for learning molecular semantic invariant representation with prototype constraint, which projects entangled molecular embeddings into a learnable semantic prototype space to extract semantic invariant representation while isolating environment-sensitive variations. Building upon this decomposition, we optimize a bi-level min-max objective that introduces representation perturbations to simulate plausible environment shifts and enforce semantic stability. We further provide theoretical guarantees for MoSIR by deriving an OOD generalization bound under distribution shifts. Extensive experiments on multiple molecular OOD benchmarks demonstrate that MoSIR consistently outperforms strong baselines across diverse shift settings, and qualitative analyses confirm that the learned prototypes capture meaningful chemical semantics.