Singapore

We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, &quot;non-uniform&quot;, sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space.
Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.

AAAI 2026

Repetition Makes Perfect: Recurrent Graph Neural Networks Match Message Passing Limit

expresivity

theory of machine learning

theory of deep learning

recurrent graph neural networks

complexity

[![](https://assets.underline.io/uploads/markdown_image/1/image/9a88ae95fbde06e80f4bcf6d4f7d133a.png)](https://certificateaixia.paperform.co/)
The certificate will be provided by December 17. 
In case you need it urgently please contact: francesca.gasparini@unimib.it. 

 

The 20th International Conference of the Italian Association for Artificial Intelligence (**AIxIA 2021**) is organized by AIxIA (Associazione Italiana per l’Intelligenza Artificiale), which is a non-profit scientific society founded in 1988 and devoted to the promotion of Artificial Intelligence. The society aims to increase the public awareness of AI, encourage the teaching of it and promote research in the field.

 
 



**General Chair**

Stefania Bandini, University of Milano-Bicocca, Italyand RCAST - The University of Tokyo, Japan


**Program Chairs**

Viviana Mascardi, University of Genova, Italy; Matteo Palmonari, University of Milano-Bicocca, Italy; Giuseppe Vizzari, University of Milano-Bicocca, Italy

**Organizing Committee**

Francesca Gasparini, University of Milano-Bicocca, Italy (**Chair**); Stefano Ferilli, University of Bari, Italy; Marta Giltri, University of Milano-Bicocca, Italy; Daniela Briola, University of Insubria, Italy


**Publicity and Communication Committee**

Elisabetta Fersini, University of Milano-Bicocca, Italy (**Chair**); Angelo Ferrando, University of Genova, Italy; Francesca Alessandra Lisi, University of Bari, Italy; Giovanni Stilo, University of L'Aquila, Italy; Marco Viviani, University of Milano-Bicocca, Italy


**Workshop Chairs**

Gabriella Cortellessa, ISTC-CNR, Rome, Italy; Silvia Rossi, University of Naples Federico II, Italy; Fabio Stella, University of Milano-Bicocca, Italy


**PC Members**

Fulvio Mastrogiovanni, University of Genova, Italy; Roberto Basili, University of Rome Tor Vergata, Italy; Nicola Gatti, Polytechnic University of Milan, Italy; Stefano Bistarelli, University of Perugia, Italy; Piero Poccianti, Consorzio Operativo Gruppo MPS, Italy; Francesco Scarcello, University of Calabria, Italy; Flavio S. Correa Da Silva, University of São Paulo, Brazil; Elena Cabrio, Université Côte d'Azur, CNRS, Inria, I3S, France; Antonio Lieto, University of Turin, Italy; Diego Calvanese, Free University of Bozen-Bolzano, Italy; Alessio Micheli, University of Pisa, Italy; Francesca A. Lisi University of Bari Aldo Moro, Italy; Mauro Vallati, University of Huddersfield, United Kingdom; Bernardo Magnini, Fondazione Bruno Kessler (FBK), Italy; Luigia C. Aiello, Sapienza University of Rome, Italy; Rafael H. Bordini, Pontifical Catholic University of Rio Grande do Sul, Brazil; Chiara Ghidini, Fondazione Bruno Kessler (FBK), Italy; Federico Bergenti, University of Parma, Italy; Francesco Ricca, University of Calabria, Italy; Andrea Burattin, Technical University of Denmark, Denmark; Angelo Oddi, ISTC-CNR, Italian National Research Council, Italy; Farshad Badie, Aalborg University, Denmark; Emanuel Sallinger, University of Oxford, United Kingdom; Marin Lujak, University Rey Juan Carlos, Spain; Giancarlo Fortino, University of Calabria, Italy; Salvatore Gaglio, University of Palermo, Italy; Johannes K. Fichte, TU Dresden, Germany; Matteo Baldoni, University of Turin, Italy; Fabrizio Riguzzi, Univeristy of Ferrara, Italy; Ivana Dusparic, Trinity College Dublin, Ireland; Serena Villata, CNRS - Laboratoire d'Informatique, Signaux et Systèmes de Sophia-Antipolis, France; Paolo Rosso, Technical University of Valencia, Spain; Ana L. C. Bazzan, Federal University of Rio Grande do Sul, Brazil; Gianluigi Greco, University of Calabria, Italy; Stefano Cagnoni, University of Parma, Italy; Gian Luca Pozzato, University of Turin, Italy; Salvatore Ruggieri, University of Turin, Italy; Claudio Di Ciccio, Sapienza University of Rome, Italy; Eloisa Vargiu, Cetaqua, Water Technology Center, Spain; Marco Maratea, University of Genova, Italy; Andrea Roli, University of Bologna, Italy; Viviana Patti, University of Turin, Italy; Stefania Costantini, University of L'Aquila, Italy; Antonius Weinzierl, Vienna University of Technology, Austria; Silvia Rossi, University of Naples Federico II, Italy; Giovanni Semeraro, University of Bari, Italy; Luciano Serafini, Fondazione Bruno Kessler (FBK), Italy; Laura Giordano, University of Eastern Piedmont, Italy; Ernesto Jimenez-Ruiz, City, University of London, United Kingdom; Marco Gavanelli, University of Ferrara, Italy; Federico Chesani, University of Bologna, Italy

Please register with AIxIA to be able to enter the conference on Underline.io. If you have already registered, please login to Underline.io to be able to see full conference content. In case you do not have an Underline account, please create one. Thank you

Please login to your Underline account

AIxIA 2021

The 20th International Conference of the Italian Association for Artificial Intelligence (AIxIA 2021) is organized by AIxIA (Associazione Italiana per l’Intelligenza Artificiale), which is a non-profit scientific society founded in 1988 and devoted to the promotion of Artificial Intelligence. The society aims to increase the public awareness of AI, encourage the teaching of it and promote research in the field.

We precisely characterize the expressivity of computable Recurrent Graph Neural Networks (recurrent GNNs). We prove that recurrent GNNs with finite-precision parameters, sum aggregation, and ReLU activation, can compute any graph algorithm that respects the natural message-passing invariance induced by the Color Refinement (or Weisfeiler-Leman) algorithm. While it is well known that the expressive power of GNNs is limited by this invariance [Morris et al., AAAI 2019; Xu et al., ICLR 2019], we establish that recurrent GNNs can actually match this limit. This is in contrast to non-recurrent GNNs, which have the power of Weisfeiler-Leman only in a very weak, "non-uniform", sense where each graph size requires a different GNN to compute with. Our construction introduces only a polynomial overhead in both time and space.
Furthermore, we show that by incorporating random initialization, for connected graphs recurrent GNNs can express all graph algorithms. In particular, any polynomial-time graph algorithm can be emulated on connected graphs in polynomial time by a recurrent GNN with random initialization.

technical paper

We are pleased to announce the Fortieth AAAI Conference on Artificial Intelligence (AAAI-26), which will be held in Singapore EXPO from January 20 to January 27, 2026.

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-26 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and a range of other activities to be announced.

To access this event page, you need to log in with the **email address you registered with**. Access credentials will be sent to your email from Underline - subject line "Welcome to AAAI 2026". Please be sure to check your spam email folder if you do not see an email confirmation right away.

Please log in

To access this event page, you are required to register.
Please complete your registration to continue.

We recommend reading [**the registration information**](https://aaai.org/conference/aaai/aaai-26/registration/) first.

**Online Registration Form**: https://aaai.getregistered.net/conference-2026 

Registration Required

We are pleased to announce the Fortieth AAAI Conference on Artificial Intelligence (AAAI-26), which will be held in Singapore EXPO from January 20 to January 27, 2026.

Multimodal Malicious Content Detection (MMCD) is crucial for online ecosystems. Existing methods assume identical distributions between training (source) and inference (target) data. However, malicious content often evolves into irregular and ambiguous forms to evade censorship, resulting in substantial semantic drift and rendering previously trained models ineffective. Test-Time Adaptation (TTA) offers a solution by adapting models during inference to narrow the cross-domain gap, while conventional TTA methods target mild distribution shifts and struggle with the severe semantic drift in MMCD. To tackle these challenges, we propose SCANNER, the first TTA framework tailored for MMCD. Motivated by the insight that, despite the evolving nature of malicious manifestations, their underlying cores remain largely invariant (i.e., targeting is still based on characteristics like gender, race, etc), we leverage these stable cores as a bridge to connect the source and target domains. Specifically, SCANNER initially reveals the stable cores from the ambiguous layout in evolving malicious content via a principled centroid-guided alignment mechanism. To alleviate the impact of outlier-like samples that are weakly correlated with centroids during the alignment process, SCANNER enhances the prior by incorporating a sample-level adaptive centroid alignment strategy, promoting more stable adaptation. Furthermore, to mitigate semantic collapse from overly uniform outputs within clusters, SCANNER introduces an intra-cluster diversity regularization that encourages the cluster-wise semantic richness. Experiments show that SCANNER outperforms all baselines, with an average gain of 6.26% in Macro-F1 over the best.

Shedding the Facades, Connecting the Domains: Detecting Shifting Multimodal Hate Video with Test-Time Adaptation

Local search is an important class of incomplete algorithms for solving Distributed Constraint Optimization Problems (DCOPs) but it often converges to poor local optima. While GDBA provides a comprehensive rule set to escape premature convergence, its empirical benefits remain marginal on general-valued problems. In this work, we systematically examine GDBA and identify three factors that potentially lead to its inferior performance, i.e., over-aggressive constraint violation conditions, unbounded penalty accumulation, and uncoordinated penalty updates. To address these issues, we propose Distributed Guided Local Search (DGLS), a novel GLS framework for DCOPs that incorporates an adaptive violation condition to selectively penalize constraints with high cost, a penalty evaporation mechanism to control the magnitude of penalization, and a synchronization scheme for coordinated penalty updates. We theoretically show that the penalty values are bounded, and agents play a potential game in our DGLS. Our extensive empirical results on various standard benchmarks demonstrate the great superiority of DGLS over state-of-the-art baselines. Particularly, compared to Damped Max-sum with high damping factors (e.g., 0.7 or 0.9), our DGLS achieves competitive performance on general-valued problems, and outperforms it by significant margins (\textbf{3.77\%--66.3\%}) on structured problems in terms of anytime results.

GDBA Revisited: Unleashing the Power of Guided Local Search for Distributed Constraint Optimization

In the context of the Classification and Regression Trees (CART) algorithm, the efficient splitting of categorical features using standard criteria like GINI and Entropy is well-established. However, using the Mean Absolute Error (MAE) criterion for categorical features has traditionally relied on various numerical encoding methods. This paper demonstrates that unsupervised numerical encoding methods are not viable for MAE criteria. Furthermore, we present a novel and efficient splitting algorithm that addresses the challenges of handling categorical features with the MAE criterion. Our findings underscore the limitations of existing approaches and offer a promising solution to enhance the handling of categorical data in CART algorithms.

Binary Split Categorical Feature with Mean Absolute Error Criteria in CART

Large Language Models show promise in emotion understanding, social reasoning, and empathy, yet they struggle with psychologically grounded tasks that require inferring implicit mental states in context-rich, ambiguous settings. These limitations arise from the absence of theory-aligned supervision and the difficulty of capturing nuanced mental processes in real-world narratives. To address this gap, we leverage expert-labeled, psychologically rich scenarios and propose a trajectory-aware reinforcement learning framework that explicitly imitates expert psychological thought patterns. By integrating real-world stimuli with structured reasoning guidance, our approach enables compact models to internalize social-cognitive principles, perform nuanced psychological inference, and support continual self-improvement. Comprehensive experiments across multiple benchmarks further demonstrate that our models achieve expert-level interpretive capabilities, exhibiting strong out-of-distribution generalization and robust continual learning across diverse, challenging, and psychologically grounded tasks.

From Stimuli to Minds: Enhancing Psychological Reasoning in LLMs via Bilateral Reinforcement Learning

Accurate detection of cancer tissue regions (CTR) enables deeper analysis of the tumor microenvironment and offers crucial insights into treatment response. Traditional CTR detection methods, which typically rely on the rich cellular morphology in histology images, are susceptible to a high rate of false positives due to morphological similarities across different tissue regions. The groundbreaking advances in spatial transcriptomics (ST) provide detailed cellular phenotypes and spatial localization information, offering new opportunities for more accurate cancer region detection. However, current methods are unable to effectively integrate histology images with ST data, especially in the context of cross-sample and cross-platform/batch settings for accomplishing the CTR detection. To address this challenge, we propose SpaCRD, a transfer learning-based method that deeply integrates histology images and ST data to enable reliable CTR detection across diverse samples, platforms, and batches. Once trained on source data, SpaCRD can be readily generalized to accurately detect cancerous regions across samples from different platforms and batches. The core of SpaCRD is a category-regularized variational reconstruction-guided bidirectional cross-attention fusion network, which enables the model to adaptively capture latent co-expression patterns between histological features and gene expression from multiple perspectives. Extensive benchmark analysis on 23 matched histology-ST datasets spanning various disease types, platforms, and batches demonstrates that SpaCRD consistently outperforms existing eight state-of-the-art methods in CTR detection. Code availability and reproducibility details are in the Supplementary Materials.

SpaCRD: Multimodal Deep Fusion of Histology and Spatial Transcriptomics for Cancer Region Detection

Accurately determining the shape of deformable objects and
the location of their internal structures is crucial for
medical tasks that require precise targeting, such as
robotic biopsies.
We introduce LUDO, a method for accurate low-latency
understanding of deformable objects.
LUDO reconstructs objects in their deformed state,
including their internal structures, from a single-view
point cloud observation in under 30 ms using occupancy
networks.
LUDO provides uncertainty estimates for its predictions.
Additionally, it provides explainability by highlighting
key features in its input observations.
Both uncertainty and explainability are important for
safety-critical applications such as surgery.
We evaluate LUDO in real-world robotic experiments,
achieving a success rate of 98.9% for puncturing various
regions of interest (ROIs) inside deformable objects.
We compare LUDO to a popular baseline and show its superior
ROI localization accuracy, training time, and memory
requirements.
LUDO demonstrates the potential to interact with deformable
objects without the need for deformable registration
methods.

LUDO: Low-latency understanding of deformable objects using
point cloud occupancy functions

The rapid advancements in artificial intelligence (AI) have primarily focused on the process of learning from data to acquire knowledgeable learning systems. As these systems are increasingly deployed in critical areas, ensuring their privacy and alignment with human values is paramount. Recently, selective forgetting (also known as machine unlearning) has shown promise for privacy and data removal tasks, and has emerged as a transformative paradigm shift in the field of AI. It refers to the ability of a model to selectively erase the influence of previously seen data, which is especially important for compliance with modern data protection regulations and for aligning models with human values. Despite its promise, selective forgetting raises significant privacy concerns, especially when the data involved come from sensitive domains. While new unlearning-induced privacy attacks are continuously proposed, each is shown to outperform its predecessors using different experimental settings, which can lead to overly optimistic and potentially unfair assessments that may disproportionately favor one particular attack over the others. In this work, we present the first comprehensive benchmark for evaluating privacy vulnerabilities in selective forgetting. We extensively investigate privacy vulnerabilities of machine unlearning techniques and benchmark privacy leakage across a wide range of victim data, state-of-the-art unlearning privacy attacks, unlearning methods, and model architectures. We systematically evaluate and identify critical factors related to unlearning-induced privacy leakage. With our organized codebase and novel insights, we aim to provide a standardized tool for practitioners seeking to deploy customized unlearning applications with faithful privacy assessments.

Towards Benchmarking Privacy Vulnerabilities in Selective Forgetting with Large Language Models

Novel object synthesis by integrating distinct textual concepts from diverse categories remains a significant challenge in Text-to-Image (T2I) generation. Existing methods often suffer from insufficient concept mixing, lack of rigorous evaluation, and suboptimal outputs—manifesting as conceptual imbalance, superficial combinations, or mere juxtapositions. To address these limitations, we propose \textbf{Reinforcement Mixing Learning (RMLer)}, a framework that formulates cross-category concept fusion as a reinforcement learning problem: mixed features serve as states, mixing strategies as actions, and visual outcomes as rewards. Specifically, we design an MLP-policy network to predict dynamic coefficients for blending cross-category text embeddings. We further introduce visual rewards based on (1) semantic similarity and (2) compositional balance between the fused object and its constituent concepts, optimizing the policy via proximal policy optimization. At inference, a selection strategy leverages these rewards to curate the highest-quality fused objects. Extensive experiments demonstrate RMLer’s superiority in synthesizing coherent, high-fidelity objects from diverse categories, outperforming existing methods. Our work provides a robust framework for generating novel visual concepts, with promising applications in film, gaming, and design.

RMLer: Synthesizing Novel Objects Across Diverse Categories via Reinforcement Mixing Learning

Sketch person re-identification aims to match hand-drawn sketches with RGB surveillance images, yet remains challenging due to severe modality discrepancies and limited labeled data. To address this, we propose KTCAA, a theoretically grounded and interpretable framework for few-shot cross-modal transfer learning. From the perspective of generalization bounds, we identify two key controllable factors essential to minimizing target domain error: (1) domain discrepancy, which reflects the difficulty of aligning source and target distributions in the feature space; and (2) perturbation invariance, which measures the model’s robustness to cross-modal variations. To address these challenges, we design two corresponding modules: (1) Alignment Augmentation (AA), which applies localized sketch-style transformations to simulate target modality distributions, introducing slight but meaningful feature shifts that guide gradual distribution alignment during training; and (2) Knowledge Transfer Catalyst (KTC), which enhances perturbation invariance by generating worst-case adversarial modality perturbations and enforcing output consistency under such perturbations. These modules are jointly optimized within a meta-learning framework that transfers alignment knowledge from RGB-rich domains to sketch scenarios. Experiments on multiple benchmarks demonstrate that KTCAA achieves state-of-the-art performance, particularly under limited data and cross-domain transfer settings.

A Theory-Inspired Framework for Few-Shot Cross-Modal Sketch Person Re-Identification

The Aperiodic Tiling Complements Problem (ATCP) involves finding the full set of possible aperiodic complements of a given pattern.
This has become a classic problem in music theory, with some recent attempts to model it using Integer Linear Programming (ILP) and Boolean Satisfiability (SAT) frameworks.
In this paper, we propose and compare different models of ATCP encoded in Constraint Programming (CP).
The most effective approach admits two phases: a first one that allows us to merge (join) several subsets of linear constraints under the form of tables with large arity, and a second one that advantageously exploits the generated tables to discard periodic tiling complements.
Our experimental results show that our approach significantly outperforms the state-of-the-art, solving every instance of a classical benchmark (standard Vuza rhythms for canons
with period set to 420 and 900) in a time within 5 seconds to 2 minutes (except the largest instance being solved in 18 minutes).

Downloads

Next from AAAI 2026

Shedding the Facades, Connecting the Domains: Detecting Shifting Multimodal Hate Video with Test-Time Adaptation

Similar lecture

The expressive power of Graph Neural Networks: a unifying point of view