We analyze the renormalization trick in GCNs beyond its established spectral smoothing effect.We prove that self-loops can increase the rank of the propagation matrix by resolving local symmetries that otherwise induce linear dependencies, providing a rigorous explanation for the trick's effectiveness: through Oono and Suzuki's framework, the rank increment counteracts the loss of expressive power.From a spectral point of view, the addition of self-loops in GCNs ensures that some information located in the normalized adjacency's kernel is preserved and propagated rather than discarded.

Many Graph Neural Networks (GNNs) in the literature are based on message-passing, which introduces a strong learning bias that may fail to capture critical relational information encoded in the edges of the graph, particularly in tasks where the structural role of edges is as significant as that of nodes, such as in chemical molecular analysis or social network dynamics.We propose a novel architecture inspired by line graph theory that explicitly models edge adjacencies, iteratively transforming a graph into its corresponding line graph.Differently from message-passing, the iterative application of this transformation enables the exchange of information among non-adjacent nodes, allowing for the capture of complex topological dependencies, which standard GNNs overlook.Experiments on standard benchmarks show promising results.

Abstract This work introduces a novel graph-based approach to candidate-job matching using Graph Neural Networks (GNNs). We analyzed data from 62 real-world selection processes encompassing 8360 unique candidates and 9532 applications, characterized by extreme class imbalance (95% rejection rate). Our methodology constructs purpose-built bipartite graphs for each candidate-job pair, with 14 nodes representing candidates, jobs, and their respective attributes extracted using Large Language Models. Each graph contains a minimum of 15 edges representing semantic relationships between entities, with edge weights derived from embedding similarity measures. We empirically evaluated five GNN architectures (GCN, MIGNN, GIN, GAT, GraphConv) against standard neural networks across binary and ordinal classification tasks. In binary classification, graph-based approaches consistently outperformed non-graph baselines, with GCN achieving 65.4% balanced accuracy compared to 55.0% for the MLP baseline. GNN models also demonstrated superior minority class detection, with GCN correctly identifying 48.9% of qualified candidates versus only 8.5% for MLP. Statistical analysis revealed that higher recruitment stages correlate with increased graph connectivity, validating our graph construction methodology. While all models struggled with ordinal classification, the explicit modeling of semantic relationships through graph structures enabled effective binary discrimination for candidate screening, offering a promising direction for augmenting human decision-making in recruitment processes while maintaining interpretability.

In recent years, there has been a growing interest in using generative models for de novo drug design. State-of-the-Art methods typically focus on either 2D structures or 3D structures, also known as conformers. Designing 3D structures is more challenging because it involves predicting spatial coordinates, necessitating the use of SE(3) equivariant architectures to ensure consistency under coordinate transformations like rotations and translations. This study presents D4, a novel Distance and Discrete Denoising Diffusion model that utilizes the distance matrix of molecular atoms to predict a molecule’s 3D coordinates, which are naturally unaffected by such transformations. This method effectively sidesteps the difficulties encountered with traditional coordinate-based training done by State-of-the-Art methods and allows explicit conditioning of bond types on distances. The experiments performed on three well-established datasets — QM9, GDB13, and ZINC250K — of varying challenges show that this approach significantly surpasses the performance of MiDi, a State-of-the-Art approach for generating 3D molecular structures. Additionally, an ablation study confirms the significance of adopting a novel regularization loss, which addresses errors in distance predictions and bounds the triangle inequality, validating the use of distance matrices in molecular generative models. • Generation of 3D molecules through distance and discrete denoising diffusion • SE(3) equivariance is built into the model by the use of distances • A loss on eigenvalues leads to better generation of Euclidean Distance Matrices in 3D • D4 surpasses State-of-the-Art model in the generation of realistic dis- tances in QM9, ZINC, and GDB13 • KDEs offer additional qualitative insights, showing improved distribu- tion learning

Abstract The framework of Backpropagation-Free Graph Neural Networks (BF-GNNs) enables local learning at the neuron level in GNNs. While BF-GNNs can match the performance of their backpropagation-based counterparts, they may develop redundant internal representations that limit further gains. To address this issue, we propose an innovative architecture dubbed Boosting-based Backpropagation-Free GNN (B 3 F-GNN), where each network module contains multiple backpropagation-free neurons trained locally and combined as a classifier. Within each layer, later modules exploit error signals from earlier trained modules to refine predictions by diversifying internal representations. We implement this approach with two complementary boosting strategies: sample reweighting, in the spirit of AdaBoost, and error-guided prototype selection for gating, which concentrates non-linearities where previous modules struggled. The modular design also enables any-time incremental training by adding more modules on demand within resource constraints. An ablation study and in-depth experimental analysis show that both strategies reduce redundancy and increase specialization, leading to statistically significant accuracy improvements over backpropagation-based counterparts on standard node-classification benchmarks.

Functional Magnetic Resonance Imaging (fMRI) provides spatio-temporal maps of brain activity; however, extracting the rich information they contain is challenging. Traditional approaches use only summary statistics, losing details that might be hidden in the complex temporal dynamics. Deep neural networks are emerging as an apt solution in this context, given their ability to handle vast amounts of structured data. In this paper, we consider two widely studied fMRI datasets: the Human Connectome Project for connectome fingerprinting, and ABIDE for autism classification. We aim to understand how handling the temporal and spatial dimensions could influence the performance of the models and their interpretability. Specifically, we compare neural network models with architectural biases toward temporal, spatial, or combined spatio-temporal features. The results of our analysis show that existing methods exploiting the spatial dimension, or spatio-temporal hybrids, are not competitive with simpler ones considering the temporal dimension only, such as LSTM. Additionally, we propose a contrastive learning approach for connectome fingerprinting, enabling robust individual identification without requiring access to all subjects during training. Our findings suggest that explicit graph modeling of the interaction between brain regions introduces complexity without improving performance, thereby challenging current trends.

Recent years have witnessed an increase in interest in leveraging generative models for de novo molecular design in drug discovery.Many State-of-the-Art (SotA) models incorporate the 3D structural information of the molecule, particularly atomic spatial coordinates.However, such approaches face challenges integrating SE(3) equivariance when trained on coordinates.This work explores the use of the distance matrix for molecular structures, natively SE(3) invariant, avoiding whatever the issue.Experimental evaluation shows that our proposed approach significantly improves upon MiDi, a SotA 3D molecule generator.

Albeit the ubiquitous use of Graph Neural Networks (GNNs) in machine learning (ML) prediction tasks involving graph-structured data, their interpretability remains challenging. In explainable artificial intelligence (XAI), the Shapley Value (SV) is the predominant method to quantify contributions of individual features to a ML model’s output. Addressing the limitations of SVs in complex prediction models, Shapley Interactions (SIs) extend the SV to groups of features. In this work, we explain single graph predictions of GNNs with SIs that quantify node contributions and interactions among multiple nodes. By exploiting the GNN architecture, we show that the structure of interactions in node embeddings are preserved for graph prediction. As a result, the exponential complexity of SIs depends only on the receptive fields, i.e. the message-passing ranges determined by the connectivity of the graph and the number of convolutional layers. Based on our theoretical results, we introduce GraphSHAP-IQ, an efficient approach to compute any-order SIs exactly. GraphSHAP-IQ is applicable to popular message passing techniques in conjunction with a linear global pooling and output layer. We showcase that GraphSHAP-IQ substantially reduces the exponential complexity of computing exact SIs on multiple benchmark datasets. Beyond exact computation, we evaluate GraphSHAP-IQ’s approximation of SIs on popular GNN architectures and compare with existing baselines. Lastly, we visualize SIs of real-world water distribution networks and molecule structures using a SI-Graph.

Shell and tube heat exchangers are essential for many industries, as they allow to control of temperatures in industrial processes. Designing shell and tube heat exchangers is a complex task as they are governed by differential equations and influenced by numerous variables. Calculating the performance of a heat exchanger, based on variables such as the shape, number, and length of tubes, requires solving time-consuming differential equations or using simplified estimates requiring specialist expertise. This paper introduces a novel approach using deep neural networks to predict the required shell and tube heat exchanger variables based on the customer’s required capacities and pressures. This is achieved through two sequential phases: a pre-training on estimated values and, subsequently, a fine-tuning on a smaller dataset comprising measurements collected from real-world products. This method eliminates the need for iterative processes and complex equations, offering faster and accurate predictions. In addition, the paper highlights the phenomenon of "double descent" in neural networks, as it was crucial for optimizing performance. This approach enables companies to customize reliable exchangers efficiently, reducing time and specialist efforts.

Abstract Identifying molecules that exhibit some pre-specified properties is a difficult problem to solve. In the last few years, deep generative models have been used for molecule generation. Deep Graph Variational Autoencoders are among the most powerful machine learning tools with which it is possible to address this problem. However, existing methods struggle to capture the true data distribution and tend to be computationally expensive. In this work, we propose RGCVAE, an efficient and effective Graph Variational Autoencoder based on: (i) an encoding network exploiting a new powerful Relational Graph Isomorphism Network; (ii) a novel probabilistic decoding component. Compared to several State-of-the-Art VAE methods on two widely adopted datasets, RGCVAE shows State-of-the-Art molecule generation performance while being significantly faster to train. The Python code implementing RGCVAE is openly accessible for download at: https://github.com/drigoni/RGCVAE .

Large Language Models (LLMs) have revolutionized the field of Natural Language Processing thanks to their ability to reuse knowledge acquired on massive text corpora on a wide variety of downstream tasks, with minimal (if any) tuning steps. At the same time, it has been repeatedly shown that LLMs lack systematic generalization, which allows to extrapolate the learned statistical regularities outside the training distribution. In this work, we offer a systematic benchmarking of GPT-4, one of the most advanced LLMs available, on three algorithmic tasks characterized by the possibility to control the problem difficulty with two parameters. We compare the performance of GPT-4 with that of its predecessor (GPT-3.5) and with a variant of the Transformer-Encoder architecture recently introduced to solve similar tasks, the Neural Data Router. We find that the deployment of advanced prompting techniques allows GPT-4 to reach superior accuracy on all tasks, demonstrating that state-of-the-art LLMs constitute a very strong baseline also in challenging tasks that require systematic generalization.

Graph generative models can be classified into two prominent families: one-shot models, which generate a graph in one go, and sequential models, which generate a graph by successive additions of nodes and edges. Ideally, between these two extreme models lies a continuous range of models that adopt different levels of sequentiality. This paper proposes a graph generative model, called Insert-Fill-Halt (IFH), that supports the specification of a sequentiality degree. IFH is based upon the theory of Denoising Diffusion Probabilistic Models (DDPM), designing a node removal process that gradually destroys a graph. An insertion process learns to reverse this removal process by inserting arcs and nodes according to the specified sequentiality degree. We evaluate the performance of IFH in terms of quality, run time, and memory, depending on different sequentiality degrees. We also show that using DiGress, a diffusion-based one-shot model, as a generative step in IFH leads to improvement to the model itself, and is competitive with the current state-of-the-art.

Modern neural network architectures still struggle to learn algorithmic procedures that require to systematically apply compositional rules to solve out-of-distribution problem instances. In this work, we focus on formula simplification problems, a class of synthetic benchmarks used to study the systematic generalization capabilities of neural architectures. We propose a modular architecture designed to learn a general procedure for solving nested mathematical formulas by only relying on a minimal set of training examples. Inspired by rewriting systems, a classic framework in symbolic artificial intelligence, we include in the architecture three specialized and interacting modules: the Selector, trained to identify solvable sub-expressions; the Solver, mapping sub-expressions to their values; and the Combiner, replacing sub-expressions in the original formula with the solution provided by the Solver. We benchmark our system against the Neural Data Router, a recent model specialized for systematic generalization, and a state-of-the-art large language model (GPT-4) probed with advanced prompting strategies. We demonstrate that our approach achieves a higher degree of out-of-distribution generalization compared to these alternative approaches on three different types of formula simplification problems, and we discuss its limitations by analyzing its failures.

Named Entity Recognition is a crucial task in Natural Language Processing (NLP) which aims to identify the entities in text. Given an adequate amount of annotated data, Large Language Models (LLMs) have been shown to be effective in this task when fine-tuned. However, the performance of LLMs is severely affected when annotated datasets are limited. To alleviate this problem, adding synthetic data via Data Augmentation (DA) techniques is a viable approach. Even so, DA for token-level tasks suffers from two main limitations: (i) token-label misalignment problem; and (ii) quality of generated synthetic data. In this paper, we propose a novel prompt-based DA approach using contrastive learning. The proposed method can generate high-quality synthetic data while preserving the token-label correspondences. Experimental results demonstrate that the proposed approach, when compared against multiple baselines on well-known Named Entity Recognition (NER) datasets, achieves State-of-the-Art performance.

Backpropagation-Free Graph Convolutional Networks (BF-GCN) are backpropagation-free neural models dealing with graph data based on Gated Linear Networks.Each neuron in a BF-GCN is defined as a set of graph convolution filters (weight vectors) and a gating mechanism that, given a node's context, selects the weight vector to use for processing the node's attributes based on its distance from a set of prototypes.Given the higher expressivity BF-GNN's neurons compared to the standard graph convolutional neural networks' ones, they show bigger memory footprint.In this paper, we explore how reducing the size of node contexts through randomization can reduce the memory occupancy of the method, enabling its application to huge datasets.We empirically show how working with very low dimensional contexts does not impact the resulting predictive performances.* We acknowledge the support of the projects: "Future AI Research (FAIR) -Spoke 2 Integrative AI -Symbolic conditioning of Graph Generative Models (SymboliG)" funded by the European Union under the National Recovery and Resilience Plan (NRRP), Mission 4 Component 2 Investment 1.3 -Call for tender No. 341 of March 15, 2022 of Italian Ministry of University and Research -NextGenerationEU, Code PE0000013, Concession Decree No. 1555 of October 11, 2022 CUP C63C22000770006; "iNEST: Interconnected Nord-Est Innovation Ecosystem" funded under the NRRP, Mission 4 Component 2 Investment 1.5 -Call for tender No. 3277 of 30 December 2021 of Italian Ministry of University and Research -NextGenerationEU, Code ECS00000043, Concession Decree No. 1058 of June 23, 2022, CUP C43C22000340006; the PON R&I 2014-2020 project Smart Waste Treatment founded by the FSE REAC-EU; the project "Lifelong Learning on large-scale and structured data"

The recent outbreak of COVID-19 has spurred global collaborative research efforts to model and forecast the disease to improve preparation and control. Epidemiological models integrate experimental data and expert opinions to understand infection dynamics and control measures. Classical Machine Learning techniques often face challenges such as high data requirements, lack of interpretability, and difficulty integrating domain knowledge. A potential solution is to leverage Physically-Informed Machine Learning (PIML) models, which enhance models by incorporating known physical properties of viral spread. Additionally, epidemiological datasets are best represented as graphs, facilitating the modelling of interactions between individuals. In this paper, we propose a novel, interpretable graph-based PIML technique called SINDy-Graph to model infectious disease dynamics. Our approach is a Graph Cellular Automata architecture that combines the ability to identify dynamics for discovering the differential equations governing the physical phenomena under study using graphs modelling relationships between nodes (individuals). The experimental results demonstrate that integrating domain knowledge ensures better physical plausibility. In addition, our proposed model is easier to train and achieves a lower generalisation error compared to other baseline methods.

In this paper, we investigate neural models based on graph random features for classification tasks. First, we aim to understand when over parameterization, namely generating more features than the ones necessary to interpolate, may be beneficial for the generalization abilities of the resulting models. We employ two measures: one from the algorithmic stability framework and another one based on information theory. We provide empirical evidence from several commonly adopted graph datasets showing that the considered measures, even without considering task labels, can be effective for this purpose. Additionally, we investigate whether these measures can aid in the process of hyperparameters selection. The results of our empirical analysis show that the considered measures have good correlations with the estimated generalization performance of the models with different hyperparameter configurations. Moreover, they can be used to identify good hyperparameters, achieving results comparable to the ones obtained with a classic grid search.

Abstract We propose a framework for the definition of neural models for graphs that do not rely on backpropagation for training, thus making learning more biologically plausible and amenable to parallel implementation. Our proposed framework is inspired by Gated Linear Networks and allows the adoption of multiple graph convolutions. Specifically, each neuron is defined as a set of graph convolution filters (weight vectors) and a gating mechanism that, given a node and its topological context, generates the weight vector to use for processing the node’s attributes. Two different graph processing schemes are studied, i.e., a message-passing aggregation scheme where the gating mechanism is embedded directly into the graph convolution, and a multi-resolution one where neighboring nodes at different topological distances are jointly processed by a single graph convolution layer. We also compare the effectiveness of different alternatives for defining the context function of a node, i.e., based on hyperplanes or on prototypes, and using a soft or hard-gating mechanism. We propose a unified theoretical framework allowing us to theoretically characterize the proposed models’ expressiveness. We experimentally evaluate our backpropagation-free graph convolutional neural models on commonly adopted node classification datasets and show competitive performances compared to the backpropagation-based counterparts.

Abstract Object detectors are used for searching all objects belonging to a pre-defined set of categories contained in a given picture. However, users are often not interested in finding all objects, but only those that pertain to a small set of categories or concepts. Nowadays, the standard approach to solve this task involves initially employing an object detector to identify all objects within the image, followed by refining the outcomes to retain only the ones of interest. Nevertheless, the object detector does not take advantage of the user’s prior intent that, when used, can potentially improve the detection performance of the model. This work presents a method to condition an existing object detector with the user’s intent, encoded as one or more concepts from the WordNet graph, to find just those objects of interest. The proposed approach takes advantage of existing datasets for object detection without the need for new annotations, and it allows to adapt the already existing object detector models with minor changes. The evaluation, performed on the COCO and the Visual Genome datasets considering several object detector architectures, shows that conditioning the search on concepts is actually beneficial. The code and the pre-trained model weights are released at: https://github.com/drigoni/Concept-Conditioned-Object-Detector .

Many neural networks for graphs are based on the graph convolution (GC) operator, proposed more than a decade ago. Since then, many alternative definitions have been proposed, which tend to add complexity (and nonlinearity) to the model. Recently, however, a simplified GC operator, dubbed simple graph convolution (SGC), which aims to remove nonlinearities was proposed. Motivated by the good results reached by this simpler model, in this article we propose, analyze, and compare simple graph convolution operators of increasing complexity that rely on linear transformations or controlled nonlinearities, and that can be implemented in single-layer graph convolutional networks (GCNs). Their computational expressiveness is characterized as well. We show that the predictive performance of the proposed GC operators is competitive with the ones of other widely adopted models on the considered node classification benchmark datasets.

In Local Field Potential (LFP) recordings it is hard to distinguish Evoked Potentials (EPs) from spontaneous activity.Automatic real-time detection of all EPs in a recording would enable the deployment of neuromorphic prostheses.In this paper, we present a case study involving EPs induced by stimulation of a whisker in rats.We compare the detection performance of three deep learning models: a Temporal Convolutional Network, a Recurrent Neural Network, and a Mixed model.A data augmentation technique for LFP data and a technique to learn the delay of causal models are proposed.Experimental results show that the three deep learning models are capable of detecting most EPs with few false positives, a delay of less than 100ms, and for a pruned TCN, using only 1,282 parameters.

In this paper, we investigate neural models based on graph random features.In particular, we aim to understand when over-parameterization, namely generating more features than the ones necessary to interpolate, may be beneficial for the generalization of the resulting models.Exploiting the algorithmic stability framework and based on empirical evidences from several commonly adopted graph datasets, we will shed some light on this issue.

Graph Neural Networks (GNNs) are nowadays widely used in many real-world applications.Nonetheless, the data relationships can be a source of biases based on sensitive attributes (e.g., gender or ethnicity).Several methods have been proposed to learn fair graph node representations.In this work we extend NIFTY, an approach that exploits additional terms in the loss function based on perturbing the input data to enforce the fairness of the GNNs.In particular, we exploit a biased perturbation of the adjacency matrix of the graph able to reduce the edge homophily.We show the effectiveness of our approach in four real-world graph datasets.

We propose a class of neural models for graphs that do not rely on backpropagation for training, thus making learning more biologically plausible and amenable to parallel implementation in hardware. The base component of our architecture is a generalization of Gated Linear Networks which allows the adoption of multiple graph convolutions. Specifically, each neuron is defined as a set of graph convolution filters (weight vectors) and a gating mechanism that, given a node and its topological context, selects the weight vector to use for processing the node’s attributes. Two different graph processing schemes are studied, i.e., a message-passing aggregation scheme where the gating mechanism is embedded directly into the graph convolution, and a multi-resolution one where neighbouring nodes at different topological distances are jointly processed by a single graph convolution layer. We also compare the effectiveness of different alternatives for defining the context function of a node, i.e., based on hyper-planes or on prototypes. A theoretical result on the expressiveness of the proposed models is also reported. We experimented our backpropagation-free graph convolutional neural architectures on commonly adopted node classification datasets, and show competitive performances compared to the backpropagation-based counterparts.

Abstract Graph property prediction is becoming more and more popular due to the increasing availability of scientific and social data naturally represented in a graph form. Because of that, many researchers are focusing on the development of improved graph neural network models. One of the main components of a graph neural network is the aggregation operator, needed to generate a graph-level representation from a set of node-level embeddings. The aggregation operator is critical since it should, in principle, provide a representation of the graph that is isomorphism invariant, i.e. the graph representation should be a function of graph nodes treated as a set. DeepSets (in: Advances in neural information processing systems, pp 3391–3401, 2017) provides a framework to construct a set-aggregation operator with universal approximation properties. In this paper, we propose a DeepSets aggregation operator, based on Self-Organizing Maps (SOM), to transform a set of node-level representations into a single graph-level one. The adoption of SOMs allows to compute node representations that embed the information about their mutual similarity. Experimental results on several real-world datasets show that our proposed approach achieves improved predictive performance compared to the commonly adopted sum aggregation and many state-of-the-art graph neural network architectures in the literature.

Graph neural networks are receiving increasing attention as state-of-the-art methods to process graph-structured data. However, similar to other neural networks, they tend to suffer from a high computational cost to perform training. Reservoir computing (RC) is an effective way to define neural networks that are very efficient to train, often obtaining comparable predictive performance with respect to the fully trained counterparts. Different proposals of reservoir graph neural networks have been proposed in the literature. However, their predictive performances are still slightly below the ones of fully trained graph neural networks on many benchmark datasets, arguably because of the oversmoothing problem that arises when iterating over the graph structure in the reservoir computation. In this work, we aim to reduce this gap defining a multiresolution reservoir graph neural network (MRGNN) inspired by graph spectral filtering. Instead of iterating on the nonlinearity in the reservoir and using a shallow readout function, we aim to generate an explicit k -hop unsupervised graph representation amenable for further, possibly nonlinear, processing. Experiments on several datasets from various application areas show that our approach is extremely fast and it achieves in most of the cases comparable or even higher results with respect to state-of-the-art approaches.

Machine Learning (ML) achievements enabled automatic extraction of actionable information from data in a wide range of decisionmaking scenarios.This demands for improving both ML technical aspects (e.g., design and automation) and human-related metrics (e.g., fairness, robustness, privacy, and explainability), with performance guarantees at both levels.The aforementioned scenario posed three main challenges: (i) Learning from Complex Data (i.e., sequence, tree, and graph data), (ii) Learning Trustworthily, and (iii) Learning Automatically with Guarantees.The focus of this special session is on addressing one or more of these challenges with the final goal of Learning Trustworthily, Automatically, and with Guarantees from Complex Data.

Most Graph Convolutions (GCs) proposed in the Graph Neural Networks (GNNs) literature share the principle of computing topologically enriched node representations based on the ones of their neighbors.In this paper, we propose a novel GNN named Tangent Graph Convolutional Network (TGCN) that, in addition to the traditional GC approach, exploits a novel GC that computes node embeddings based on the differences between the attributes of a vertex and the attributes of its neighbors.This allows the GC to characterize each node's neighbor by computing its tangent space representation with respect to the considered vertex.* This research was supported by the Department of Mathematics, University of Padua with the SID/BIRD 2020 project "Deep Graph Memory Networks" and with the provision of the necessary HPC resources.

In open set recognition, a classifier has to detect unknown classes that are not known at training time. In order to recognize new categories, the classifier has to project the input samples of known classes in very compact and separated regions of the features space for discriminating samples of unknown classes. Recently proposed Capsule Networks have shown to outperform alternatives in many fields, particularly in image recognition, however they have not been fully applied yet to open-set recognition. In capsule networks, scalar neurons are replaced by capsule vectors or matrices, whose entries represent different proper-ties of objects. In our proposal, during training, capsules features of the same known class are encouraged to match a pre-defined gaussian, one for each class. To this end, we use the variational autoencoder framework, with a set of gaussian priors as the approximation for the posterior distribution. In this way, we are able to control the compactness of the features of the same class around the center of the gaussians, thus controlling the ability of the classifier in detecting samples from unknown classes. We conducted several experiments and ablation of our model, obtaining state of the art results on different datasets in the open set recognition and unknown detection tasks.

"A picture is worth a thousand words", the adage reads. However, pictures cannot replace words in terms of their ability to efficiently convey clear (mostly) unambiguous and concise knowledge. Images and text, indeed, reveal different and complementary information that, if combined, result in more information than the sum of that contained in the single media. The combination of visual and textual information can be obtained by linking the entities mentioned in the text with those shown in the pictures. To further integrate this with agent background knowledge, an additional step is necessary. That is, either finding the entities in the agent knowledge base that correspond to those mentioned in the text or shown in the picture or, extending the knowledge base with the newly discovered entities. We call this complex task Visual-Textual-Knowledge Entity Linking (VTKEL). In this paper, we precisely define the VTKEL task and present two datasets composed of 1k and 30k pictures, annotated with visual and textual entities and linked to the YAGO ontology. Successively, we develop the first unsupervised algorithm for the solution of VTKEL task. The evaluation of the algorithm shows promising results on both 1k and 30k VTKEL datasets.

We investigate whether Graph Convolutional Neural Networks (GCNNs) may benefit from incorporating information conveyed by a state-of-the-art graph kernel in the learning process. We propose a GCNN architecture and a training procedure based on multi-task learning, where we provide supervision not only from the graph labels, but also from the kernel to each layer of the network, achieving state-of-the-art performances on many real-world datasets. We conduct an ablation study to analyze the impact on the predictive performances of each part of our proposal, including a simplified version of our multi-task learning formulation that can, in principle, be applied with a broad family of graph embeddings. Finally, we study how to improve the performance of a model considering graphs coming from related datasets into the training procedure in a semi-supervised learning fashion.

In recent years, several techniques have been made available to automatically discover declarative process models from event logs. These techniques are useful to provide a comprehensible picture of the process as opposed to full specifications of process behavior provided by procedural modeling languages. Since many modern systems produce "big data" from business process executions, in previous work, a framework for the discovery of LTL-based declarative process models from streaming event data has been proposed. This framework can be used to process events online, as they occur, as a way to deal with large and complex collections of datasets that are impossible to store and process altogether. However, the proposed framework does not take into account data attributes associated with events in the log, which can otherwise provide valuable insights into the rules that govern the process. This paper makes the first proposal to close this gap by presenting a technique for discovering declarative process models from event streams that incorporates both control-flow dependencies and data conditions. Specifically, we use Hoeffding trees to incrementally discover data-aware declarative process models, which are represented as conjunctions of first-order temporal logic expressions. The proposed technique has been validated on a synthetic event log, and on a real-life log of a cancer treatment process.

MOTIVATION: The identification of disease-gene associations is a task of fundamental importance in human health research. A typical approach consists in first encoding large gene/protein relational datasets as networks due to the natural and intuitive property of graphs for representing objects' relationships and then utilizing graph-based techniques to prioritize genes for successive low-throughput validation assays. Since different types of interactions between genes yield distinct gene networks, there is the need to integrate different heterogeneous sources to improve the reliability of prioritization systems. RESULTS: We propose an approach based on three phases: first, we merge all sources in a single network, then we partition the integrated network according to edge density introducing a notion of edge type to distinguish the parts and finally, we employ a novel node kernel suitable for graphs with typed edges. We show how the node kernel can generate a large number of discriminative features that can be efficiently processed by linear regularized machine learning classifiers. We report state-of-the-art results on 12 disease-gene associations and on a time-stamped benchmark containing 42 newly discovered associations. AVAILABILITY AND IMPLEMENTATION: Source code: https://github.com/dinhinfotech/DiGI.git. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Several machine learning problems can be naturally defined over graph data. Recently, many researchers have been focusing on the definition of neural networks for graphs. The core idea is to learn a hidden representation for the graph vertices, with a convolutive or recurrent mechanism. When considering discriminative tasks on graphs, such as classification or regression, one critical component to design is the readout function, i.e. the mapping from the set of vertex representations to a fixed-size vector (or the output). Different approaches have been presented in literature, but recent approaches tend to be complex, making the training of the whole network harder. In this paper, we frame the problem in the setting of learning over sets. Adopting recently proposed theorems over functions defined on sets, we propose a simple but powerful formulation for a readout layer that can encode or approximate arbitrarily well any continuous permutation-invariant function over sets. Experimental results on real-world graph datasets show that, compared to other approaches, the proposed readout architecture can improve the predictive performance of Graph Neural Networks while being computationally more efficient.

Learning with limited resources (processing power and memory) on a stream of data is a challenging problem. When dealing with structured data, in particular with graphs, state-of- the-art graph kernels coupled with budget-aware online learning algorithms provide an efficient and effective solution. They map the input graph in a feature space that can be represented explicitly in sparse format. In this paper, we propose a method to enhance existing graph kernels in a streaming scenario with strict memory constraints. Specifically, we combine state-of-the-art online kernel methods with the power and flexibility of the feature representation of Extreme Learning Machines (ELM). Although being in principle a simple idea, our proposal, applied to several real-world datasets, outperformed state-of-the-art algorithms on streams of graphs with respect to predictive performance.

BACKGROUND: The uncovering of genes linked to human diseases is a pressing challenge in molecular biology and precision medicine. This task is often hindered by the large number of candidate genes and by the heterogeneity of the available information. Computational methods for the prioritization of candidate genes can help to cope with these problems. In particular, kernel-based methods are a powerful resource for the integration of heterogeneous biological knowledge, however, their practical implementation is often precluded by their limited scalability. RESULTS: We propose Scuba, a scalable kernel-based method for gene prioritization. It implements a novel multiple kernel learning approach, based on a semi-supervised perspective and on the optimization of the margin distribution. Scuba is optimized to cope with strongly unbalanced settings where known disease genes are few and large scale predictions are required. Importantly, it is able to efficiently deal both with a large amount of candidate genes and with an arbitrary number of data sources. As a direct consequence of scalability, Scuba integrates also a new efficient strategy to select optimal kernel parameters for each data source. We performed cross-validation experiments and simulated a realistic usage setting, showing that Scuba outperforms a wide range of state-of-the-art methods. CONCLUSIONS: Scuba achieves state-of-the-art performance and has enhanced scalability compared to existing kernel-based approaches for genomic data. This method can be useful to prioritize candidate genes, particularly when their number is large or when input data is highly heterogeneous. The code is freely available at https://github.com/gzampieri/Scuba .

This paper presents a family of methods for the design of adaptive kernels for tree-structured data that exploits the summarization properties of hidden states of hidden Markov models for trees. We introduce a compact and discriminative feature space based on the concept of hidden states multisets and we discuss different approaches to estimate such hidden state encoding. We show how it can be used to build an efficient and general tree kernel based on Jaccard similarity. Furthermore, we derive an unsupervised convolutional generative kernel using a topology induced on the Markov states by a tree topographic mapping. This paper provides an extensive empirical assessment on a variety of structured data learning tasks, comparing the predictive accuracy and computational efficiency of state-of-the-art generative, adaptive, and syntactical tree kernels. The results show that the proposed generative approach has a good tradeoff between computational complexity and predictive performance, in particular when considering the soft matching introduced by the topographic mapping.

The availability of graph data with node attributes that can be either discrete or real-valued is constantly increasing. While existing Kernel methods are effective techniques for dealing with graphs having discrete node labels, their adaptation to nondiscrete or continuous node attributes has been limited, mainly for computational issues. Recently, a few kernels especially tailored for this domain, and that trade predictive performance for computational efficiency, have been proposed. In this brief, we propose a graph kernel for complex and continuous nodes' attributes, whose features are tree structures extracted from specific graph visits. The kernel manages to keep the same complexity of the state-of-the-art kernels while implicitly using a larger feature space. We further present an approximated variant of the kernel, which reduces its complexity significantly. Experimental results obtained on six real-world data sets show that the kernel is the best performing one on most of them. Moreover, in most cases, the approximated version reaches comparable performances to the current state-of-the-art kernels in terms of classification accuracy while greatly shortening the running times.

When dealing with kernel methods, one has to decide which kernel and which values for the hyperparameters to use. Resampling techniques can address this issue but these procedures are time-consuming. This problem is particularly challenging when dealing with structured data, in particular with graphs, since several kernels for graph data have been proposed in literature, but no clear relationship among them in terms of learning properties is defined. In these cases, exhaustive search seems to be the only reasonable approach. Recently, the global Rademacher complexity (RC) and local Rademacher complexity (LRC), two powerful measures of the complexity of a hypothesis space, have shown to be suited for studying kernels properties. In particular, the LRC is able to bound the generalization error of an hypothesis chosen in a space by disregarding those ones which will not be taken into account by any learning procedure because of their high error. In this paper, we show a new approach to efficiently bound the RC of the space induced by a kernel, since its exact computation is an NP-Hard problem. Then we show for the first time that RC can be used to estimate the accuracy and expressivity of different graph kernels under different parameter configurations. The authors' claims are supported by experimental results on several real-world graph data sets.

Modern mining approaches should be able to properly deal with the increased availability of structured data. Here we focus on the problem of processing streams of trees. Specifically, we cope with classification tasks. We show that by adopting a double concept drifting reaction mechanism in the context of a kernel-based ensemble of classifiers, it is actually possible to have an effective and efficient system to process streams of trees. The original contribution consists into the introduction of a local concept drifting mechanism, specifically designed for structured data, and used to compute the ensemble score function in such a way to focus only on reliable (sub)trees belonging to the classification models which constitute the ensemble. Experimental results seem to support the relevance and usefulness of this local component for concept drifting management.

Nowadays, developing effective techniques able to deal with data coming from structured domains is becoming crucial. In this context kernel methods are the state-of-the-art tool widely adopted in real-world applications that involve learning on structured data. Contrarily, when one has to deal with unstructured domains, deep learning methods represent a competitive, or even better, choice. In this paper we propose a new family of kernels for graphs which exploits a deep representation of the information. Our proposal exploits the advantages of the two worlds. From one side we exploit the potentiality of the state-of-the-art graph kernels. From the other side we develop a deep architecture through a series of stacked kernel pre-image estimators trained in an unsupervised fashion via convex optimization. The hidden layers of the proposed framework are trained in a forward manner and this allows us to avoid the greedy layerwise training of classical deep learning. Results on real world graph datasets confirm the quality of the proposal.

The aim of the paper is to explore how models based on a linear dynamic can be used in order to perform a prediction task in sequential domains. In the literature, it has already been shown that Linear Dynamical Systems (LDSs) can be quite useful when dealing with sequence learning tasks. Our aim is to study whether it is possible to use LDSs as building blocks for constructing more complex and powerful models. Specifically, we propose a model dubbed Linear System Network, that exploits several LDSs in order to compute a nonlinear projection of the input. Moreover, we explore whether is it possible to apply a co-learning technique in order to improve the performance of LDSs for the considered prediction task.

Tree kernels proposed in the literature rarely use information about the relative location of the substructures within a tree. As this type of information is orthogonal to the one commonly exploited by tree kernels, the two can be combined to enhance state-of-the-art accuracy of tree kernels. In this brief, our attention is focused on subtree kernels. We describe an efficient algorithm for injecting positional information into a tree kernel and present ways to enlarge its feature space without affecting its worst case complexity. The experimental results on several benchmark datasets are presented showing that our method is able to reach state-of-the-art performances, obtaining in some cases better performance than computationally more demanding tree kernels.

Today's business processes are often controlled and supported by information systems. These systems record real-time information about business processes during their executions. This enables the analysis at runtime of the process behavior. However, many modern systems produce “big data”, i.e., collections of data sets so large and complex that it becomes impossible to store and process all of them. Moreover, few processes are in steady-state but, due to changing circumstances, they evolve and systems need to adapt continuously. In this paper, we present a novel framework for the discovery of LTL-based declarative process models from streaming event data in settings where it is impossible to store all events over an extended period of time or where processes evolve while being analyzed. The framework continuously updates a set of valid business constraints based on the events occurred in the event stream. In addition, our approach is able to provide meaningful information about the most significant concept drifts, i.e., changes occurring in a process during its execution. We report about experimental results obtained using synthetic logs and a real-life event log pertaining to the treatment of patients diagnosed with cancer in a large Dutch academic hospital.

Process Mining represents an important research field that connects Business Process Modeling and Data Mining. One of the most prominent task of Process Mining is the discovery of a control-flow starting from event logs. This paper focuses on the important problem of control-flow discovery starting from a stream of event data. We propose to adapt Heuristics Miner, one of the most effective control-flow discovery algorithms, to the treatment of streams of event data. Two adaptations, based on Lossy Counting and Lossy Counting with Budget, as well as a sliding window based version of Heuristics Miner, are proposed and experimentally compared against both artificial and real streams. Experimental results show the effectiveness of control-flow discovery algorithms for streams on artificial and real datasets.

In community detection, the theme of correctly identifying overlapping nodes, i.e. nodes which belong to more than one community, is important as it is related to role detection and to the improvement of the quality of clustering: proper detection of overlapping nodes gives a better understanding of the community structure. In this paper, we introduce a novel measure, called cuttability, that we show being useful for reliable detection of overlaps among communities and for improving the quality of the clustering, measured via modularity. The proposed algorithm shows better behaviour than existing techniques on the considered datasets (IRC logs and Enron e-mail log). The best behaviour is caught when a network is split between micro-communities. In that case, the algorithm manages to get a better description of the community structure.

Context is essential to evaluate an atomic piece of information composing an articulated structured sample. A particular context captures different structural information with respect to an alternative context. The paper introduces a generative kernel that easily and effectively combines the structural information captured by generative tree models characterized by different contextual capabilities. The proposed approach exploits the idea of hidden states multisets to realize a tree encoding that takes into account both the summarized information on the path leading to a node (i.e. a top-down context) as well as the information on how substructures are composed to create a subtree rooted on a node (bottom-up context). An thorough experimental analysis is provided, showing that the bi-directional approach incorporating top-down and bottom-up contexts yields to superior performances with respect to the unidirectional contexts alone, achieving state of the art results on challenging tree classification benchmarks.

Accurate prediction of the completion time of a business process instance would constitute a valuable tool when managing processes under service level agreement constraints. Such prediction, however, is a very challenging task. A wide variety of factors could influence the trend of a process instance, and hence just using time statistics of historical cases cannot be sufficient to get accurate predictions. Here we propose a new approach where, in order to improve the prediction quality, both the control and the data flow perspectives are jointly used. To achieve this goal, our approach builds a process model which is augmented by time and data information in order to enable remaining time prediction. The remaining time prediction of a running case is calculated combining two factors: (a) the likelihood of all the following activities, given the data collected so far; and (b) the remaining time estimation given by a regression model built upon the data.

Control flow discovery algorithms are able to reconstruct the workflow of a business process from a log of performed activities. These algorithms, however, do not pay attention to the reconstruction of roles, i.e. they do not group activities according to the skills required to perform them. Information about roles in business processes is commonly considered important and explicitly integrated into the process representation, e.g. as swimlanes in BPMN diagrams. This work proposes an approach to enhance a business process model with information on roles. Specifically, the identification of roles is based on the detection of handover of roles. On the basis of candidates for roles handover, the set of activities is first partitioned and then subsets of activities which are performed by the same originators are merged, so to obtain roles. All significant partitions of activities are automatically generated. Experimental results on several logs show that the set of generated roles is not too large and it always contains the correct definition of roles. We also propose an entropy based measure to rank the candidate roles which returns promising experimental results.

We introduce GTM-SD (Generative Topographic Mapping for Structured Data), which is the first compositional generative model for topographic mapping of tree-structured data. GTM-SD exploits a scalable bottom-up hidden-tree Markov model that was introduced in Part I of this paper to achieve a recursive topographic mapping of hierarchical information. The proposed model allows efficient exploitation of contextual information from shared substructures by a recursive upward propagation on the tree structure which distributes substructure information across the topographic map. Compared to its noncompositional generative counterpart, GTM-SD is shown to allow the topographic mapping of the full sample tree, which includes a projection onto the lattice of all the distinct subtrees rooted in each of its nodes. Experimental results show that the continuous projection space generated by the smooth topographic mapping of GTM-SD yields a finer grained discrimination of the sample structures with respect to the state-of-the-art recursive neural network approach.

The increasing availability of event data recorded by information systems, electronic devices, web services and sensor networks provides detailed information about the actual processes in systems and organizations. Process mining techniques can use such event data to discover processes and check the conformance of process models. For conformance checking, we need to analyze whether the observed behavior matches the modeled behavior. In such settings, it is often desirable to specify the expected behavior in terms of a declarative process model rather than of a detailed procedural model. However, declarative models do not have an explicit notion of state, thus making it more difficult to pinpoint deviations and to explain and quantify discrepancies. This paper focuses on providing high-quality and understandable diagnostics. The notion of activation plays a key role in determining the effect of individual events on a given constraint. Using this notion, we are able to show cause-and-effect relations and measure the healthiness of the process.

In this paper, we show how learning models generated by a recently introduced state-of-the-art kernel for graphs can be optimized from the point of view of memory occupancy. After a brief description of the kernel, we introduce a novel representation of the explicit feature space of the kernel based on an hash function which allows to reduce the amount of memory needed both during the training phase and to represent the final learned model. Subsequently, we study the application of a feature selection strategy based on the F-score to further reduce the number of features in the final model. On two representative datasets involving binary classification of chemical graphs, we show that it is actually possible to sensibly reduce memory occupancy (up to one order of magnitude) for the final model with a moderate loss in classification performance.

This paper proposes a new tree-based kernel for graphs. Graphs are decomposed into multisets of ordered Directed Acyclic Graphs (DAGs) and a family of kernels computed by application of tree kernels extended to the DAG domain. We focus our attention on the efficient development of one member of this family. A technique for speeding up the computation is given, as well as theoretical bounds and practical evidence of its feasibility. State of the art results on various benchmark datasets prove the effectiveness of our approach.

We introduce a novel compositional (recursive) probabilistic model for trees that defines an approximated bottom-up generative process from the leaves to the root of a tree. The proposed model defines contextual state transitions from the joint configuration of the children to the parent nodes. We argue that the bottom-up context postulates different probabilistic assumptions with respect to a top-down approach, leading to different representational capabilities. We discuss classes of applications that are best suited to a bottom-up approach. In particular, the bottom-up context is shown to better correlate and model the co-occurrence of substructures among the child subtrees of internal nodes. A mixed memory approximation is introduced to factorize the joint children-to-parent state transition matrix as a mixture of pairwise transitions. The proposed approach is the first practical bottom-up generative model for tree-structured data that maintains the same computational class of its top-down counterpart. Comparative experimental analyses exploiting synthetic and real-world datasets show that the proposed model can deal with deep structures better than a top-down generative model. The model is also shown to better capture structural information from real-world data comprising trees with a large out-degree. The proposed bottom-up model can be used as a fundamental building block for the development of other new powerful models.

Learning from streaming data represents an important and challenging task. Maintaining an accurate model, while the stream goes by, requires a smart way for tracking data changes through time, originating concept drift. One way to treat this kind of problem is to resort to ensemble-based techniques. In this context, the advent of new technologies related to web and ubiquitous services call for the need of new learning approaches able to deal with structured-complex information, such as trees. Kernel methods enable the modeling of structured data in learning algorithms, however they are computationally demanding. The contribute of this work is to show how an effective ensemble-based approach can be deviced for streams of trees by optimizing the kernel-based model representation. Both efficacy and efficiency of the proposed approach are assessed for different models by using data sets exhibiting different levels and types of concept drift.

Learning the kernel function from data is a challenging open issue in structured data processing. In the paper, we propose a novel adaptive kernel, defined over a generative learning model, that exploits a novel multinomial extension of the Generative Topographic Mapping for Structured Data (GTM-SD). We show how the proposed kernel effectively exploits the GTM-SD continuity and smoothness properties to provide dense kernels characterized by an high discriminative power even with small topographic maps. Experimental evaluations on challenging structured XML document repositories show the effectiveness of the proposed approach against state-of-the-art syntactic and adaptive convolutional kernels.

The choice of parameters' values for noise-tolerant Process Mining algorithms is not trivial, especially for users that are not expert in Process Mining. Exhaustive exploration of all possible set of values is not feasible, since several parameters are real-valued. Selecting the “right” values, however, is important, since otherwise the control-flow network returned by the mining can be quite far from the correct one. Here we face this problem for a specific Process Mining algorithm, i.e. Heuristics Miner++. We recognize that the domain of real-valued parameters can be actually partitioned into a finite number of equivalence classes and we suggest exploring the parameters space by a local search strategy driven by a Minimum Description Length principle. We believe that the proposed approach is sufficiently general to be used for other Process Mining algorithms. Experimental results on a set of randomly generated process models show promising results.

We introduce a compositional generative model for topographic mapping of tree-structured data. It exploits a scalable bottom-up hidden tree Markov model to achieve a recursive topographic mapping of hierarchical information. The model allows for an efficient exploitation of contextual information from shared substructures by recursive upward propagation on the tree structure and by allowing it to distribute across the map. Experimental results show that the model yields to a topographically ordered mapping of the substructures in the input data.

In many applicative settings there is the interest in ranking a list of items arriving from a data stream. In a human resource application, for example, to help selecting people for a given job role, the person in charge of the selection may want to get a list of candidates sorted according to their profiles and how much they are suited for the target job role. Historical data about past decisions can be analyzed to try to discover rules to help in defining such ranking. Moreover, samples have a temporal dynamics. To exploit this possibly useful information, here we propose a method that incrementally builds a committee of classifiers (experts), each one trained on the newer chunks of samples. The prediction of the committee is obtained as a combination of the rankings proposed by the experts which are ldquocloserrdquo to the data to rank. The experts of the committee are generated using the preference learning model, a recent method which can directly exploit supervision in the form of preferences (partial orders between instances) and thus particularly suitable for rankings. We test our approach on a large dataset coming from many years of human resource selections in a bank.

Almost all tree kernels proposed in the literature match substructures without taking into account their relative positioning with respect to one another. In this paper, we propose a novel family of kernels which explicitly focus on this type of information. Specifically, after defining a family of tree kernels based on routes between nodes, we present an efficient implementation for a member of this family. Experimental results on four different datasets show that our method is able to reach state of the art performances, obtaining in some cases performances better than computationally more demanding tree kernels.

The development of neural network (NN) models able to encode structured input, and the more recent definition of kernels for structures, makes it possible to directly apply machine learning approaches to generic structured data. However, the effectiveness of a kernel can depend on its sparsity with respect to a specific data set. In fact, the accuracy of a kernel method typically reduces as the kernel sparsity increases. The sparsity problem is particularly common in structured domains involving discrete variables which may take on many different values. In this paper, we explore this issue on two well-known kernels for trees, and propose to face it by recurring to self-organizing maps (SOMs) for structures. Specifically, we show that a suitable combination of the two approaches, obtained by defining a new class of kernels based on the activation map of a SOM for structures, can be effective in avoiding the sparsity problem and results in a system that can be significantly more accurate for categorization tasks on structured data. The effectiveness of the proposed approach is demonstrated experimentally on two relatively large corpora of XML formatted data and a data set of user sessions extracted from website logs.

Kernel methods are effective approaches to the modeling of structured objects in learning algorithms. Their major drawback is the typically high computational complexity of kernel functions. This prevents the application of computational demanding algorithms, e.g. support vector machines, on large datasets. Consequently, on-line learning approaches are required. Moreover, to facilitate the application of kernel methods on structured data, additional efficiency optimization should be carried out. In this paper, we propose direct acyclic graphs to reduce the computational burden and storage requirements by representing common structures and feature vectors. We show the benefit of our approach for the perceptron algorithm using tree and polynomial kernels. The experiments on a quite extensive dataset of about one million of instances show that our model makes the use of kernels for trees practical. From the accuracy point of view, the possibility of using large amount of data has allowed us to reach the state-of-the-art on the automatic detection of semantic role labeling as defined in the conference on natural language learning shared task

Category Ranking is a variant of the multi-label classification problem, in which, rather than performing a (hard) assignment to an object of categories from a predefined set, we rank all categories according to their estimated "degree of suitability" to the object. Category ranking has many applications, all pertaining to "interactive" classification contexts in which the system, rather than taking a final categorization decision, is simply required to support a human expert who is in charge of taking this decision. Despite its high applicative potential in information retrieval applications, and in text categorization in particular, category ranking has mainly been tackled by standard text categorization methods. In this paper, we take a radically different stand to category ranking, i.e. one in which supervision is provided to the learner not in the standard form of labels attached to training documents, but in the form of preferences of type "category c\ is to be preferred to category c2 for document d". We apply to this problem a recently proposed, very general model for preferential learning, and show, through experiments performed on the standard Reuters-21578 benchmark, that this largely outperforms support vector machines, the learning method which has up to now proved the best-performing one in text categorization comparative experiments.

Kernel methods have been shown to be very effective for applications requiring the modeling of structured objects. However kernels for structures usually are too computational demanding to be applied to complex learning algorithms, e.g. Support Vector Machines. Consequently, in order to apply kernels to large amount of structured data, we need fast on-line algorithms along with an efficiency optimization of kernel-based computations. In this paper, we optimize this computation by representing set of trees by minimal Direct Acyclic Graphs (DAGs) allowing us i) to reduce the storage requirements and ii) to speed up the evaluation on large number of trees as it can be done 'one-shot' by computing kernels over DAGs. The experiments on predicate argument subtrees from PropBank data show that substantial computational savings can be obtained for the perceptron algorithm.

The number of XML documents produced and available on the Internet is steadily increasing. It is thus important to devise automatic procedures to extract useful information from them with little or no intervention by a human operator. In this paper, we investigate the efficacy of an unsupervised learning approach, namely self-organising maps (SOMs), for the automatic clustering of XML documents. Specifically, we consider a relatively large corpus of XML formatted data from the INEX initiative and evaluate it using two different self-organising map models. The first model is the classical SOM model, and it requires the XML documents to be represented by real-valued vectors, obtained using a "bag of words" (or better a "bag of tags") approach. The other model is the SOM for structured data (SOM-SD) approach which is able to cluster structured data, and it is possible to feed the model with tree structured representations of the XML documents, thus explicitly preserving the structural information in the documents. The experimental results show that the SOM model exhibits quite a poor performance on this problem domain which requires the ability to encode structural properties of the data. The SOM-SD model, on the other hand, is able to produce a good clustering and generalization performance.

Winner-take-all multiclass classifiers are built on the top of a set of prototypes each representing one of the available classes. A pattern is then classified with the label associated to the most 'similar' prototype. Recent proposal of SVM extensions to multiclass can be considered instances of the same strategy with one prototype per class. The multi-prototype SVM proposed in this paper extends multiclass SVM to multiple prototypes per class. It allows to combine several vectors in a principled way to obtain large margin decision functions. For this problem, we give a compact constrained quadratic formulation and we propose a greedy optimization algorithm able to find locally optimal solutions for the non convex objective function. This algorithm proceeds by reducing the overall problem into a series of simpler convex problems. For the solution of these reduced problems an efficient optimization algorithm is proposed. A number of pattern selection strategies are then discussed to speed-up the optimization process. In addition, given the combinatorial nature of the overall problem, stochastic search strategies are suggested to escape from local minima which are not globally optimal. Finally, we report experiments on a number of datasets. The performance obtained using few simple linear prototypes is comparable to that obtained by state-of-the-art kernel-based methods but with a significant reduction (of one or two orders) in response time.

Cascade correlation (CC) constitutes a training method for neural networks that determines the weights as well as the neural architecture during training. Various extensions of CC to structured data have been proposed: recurrent cascade correlation (RCC) for sequences, recursive cascade correlation (RecCC) for tree structures with limited fan-out, and contextual recursive cascade correlation (CRecCC) for rooted directed positional acyclic graphs (DPAGs) with limited fan-in and fan-out. We show that these models possess the universal approximation property in the following sense: given a probability measure P on the input set, every measurable function from sequences into a real vector space can be approximated by a sigmoidal RCC up to any desired degree of accuracy up to inputs of arbitrary small probability. Every measurable function from tree structures with limited fan-out into a real vector space can be approximated by a sigmoidal RecCC with multiplicative neurons up to any desired degree of accuracy up to inputs of arbitrary small probability. For sigmoidal CRecCC networks with multiplicative neurons, we show the universal approximation capability for functions on an important subset of all DPAGs with limited fan-in and fan-out for which a specific linear representation yields unique codes. We give one sufficient structural condition for the latter property, which can easily be tested: the enumeration of ingoing and outgoing edges should becom patible. This property can be fulfilled for every DPAG with fan-in and fan-out two via reenumeration of children and parents, and for larger fan-in and fan-out via an expansion of the fan-in and fan-out and reenumeration of children and parents. In addition, the result can be generalized to the case of input-output isomorphic transductions of structures. Thus, CRecCC networks consti-tute the first neural models for which the universal approximation ca-pability of functions involving fairly general acyclic graph structures is proved.

Many interesting multiclass problems can be cast in the general frame- work of label ranking defined on a given set of classes. The evaluation for such a ranking is generally given in terms of the number of violated order constraints between classes. In this paper, we propose the Prefer- ence Learning Model as a unifying framework to model and solve a large class of multiclass problems in a large margin perspective. In addition, an original kernel-based method is proposed and evaluated on a ranking dataset with state-of-the-art results.

This paper propose a first approach to deal with contextual information in structured domains by recursive neural networks. The proposed model, i.e., contextual recursive cascade correlation (CRCC), a generalization of the recursive cascade correlation (RCC) model, is able to partially remove the causality assumption by exploiting contextual information stored in frozen units. We formally characterize the properties of CRCC showing that it is able to compute contextual transductions and also some causal supersource transductions that RCC cannot compute. Experimental results on controlled sequences and on a real-world task involving chemical structures confirm the computational limitations of RCC, while assessing the efficiency and efficacy of CRCC in dealing both with pure causal and contextual prediction tasks. Moreover, results obtained for the real-world task show the superiority of the proposed approach versus RCC when exploring a task for which it is not known whether the structural causality assumption holds.

Recent developments in the area of neural networks produced models capable of dealing with structured data. Here, we propose the first fully unsupervised model, namely an extension of traditional self-organizing maps (SOMs), for the processing of labeled directed acyclic graphs (DAGs). The extension is obtained by using the unfolding procedure adopted in recurrent and recursive neural networks, with the replicated neurons in the unfolded network comprising of a full SOM. This approach enables the discovery of similarities among objects including vectors consisting of numerical data. The capabilities of the model are analyzed in detail by utilizing a relatively large data set taken from an artificial benchmark problem involving visual patterns encoded as labeled DAGs. The experimental results demonstrate clearly that the proposed model is capable of exploiting both information conveyed in the labels attached to each node of the input DAGs and information encoded in the DAG topology.

We consider a popular approach to multicategory classification tasks: a two-stage system based on a first classifier with rejection followed by a nearest-neighbor classifier. Patterns which are not rejected by the first classifier are classified according to its output. Rejected patterns are passed to the nearest-neighbor classifier together with the top-h ranking classes returned by the first classifier. The nearest-neighbor classifier, looking at patterns in the top-h classes, classifies the rejected pattern. An editing strategy for the nearest-neighbor reference database, controlled by the first classifier, is also considered. We analyze this system. Moreover, we formally relate the response time of the system to the rejection rate of the first classifier and to the other system parameters. The error-response time trade-off is also discussed. Finally, we experimentally study two instances of the system applied to the recognition of handwritten digits. In one system, the first classifier is a fuzzy basis functions network, while in the second system it is a feed-forward neural network. Classification results as well as response times for different settings of the system parameters are reported for both systems.

A number of reasoning problems involving the manipulation of temporal information can naturally be viewed as implicitly inducing an ordering of potential local decisions involving time (specifically, associated with durations or orderings of events) on the basis of preferences. For example, a pair of events might be constrained to occur in a certain order and, in addition, it might be preferable that the delay between the start times of each of them be as large, or as small, as possible. Sometimes, however, it is more natural to view preferences as something initially ascribed to complete solutions to temporal reasoning problems, rather than to local decisions. For example, in classical scheduling problems, the preference for solutions which minimize makespan is a global, rather than a local, condition. In such cases, it might be useful to learn the local preferences that contribute to globally preferred solutions. This information could be used in heuristics to guide the solver to more promising solutions. To address the potential requirement for information about local preferences, we propose to apply learning techniques to infer local preferences from global ones. The preliminary work proposes an approach based on the notion of learning a set of soft temporal constraints, given a training set of solutions to a Temporal CSP, and an objective function for evaluating each solution in the set.

Guest Editors' Introduction to the Special Section on Connectionist Models for Learning in Structured Domains

We describe AdaBoost.MH , an improved boosting al- gorithm, and its application to text categorization. Boosting is a method for supervised learning which has successfully been applied to many different domains, and that has proven one of the best performers in text categorization exercises so far. Boosting is based on the idea of relying on the collec- tive judgment of a committee of classifiers that are trained sequentially. In training the i-th classifier special emphasis is placed on the correct categorization of the training docu- ments which have proven harder for the previously trained classifiers. AdaBoost.MHKR is based on the idea to build, at every iteration of the learning phase, not a single classi- fier but a sub-committee of the K classifiers which, at that iteration, look the most promising. We report the results of systematic experimentation of this method performed on the standard Reuters-21578 benchmark. These experiments have shown that AdaBoost.MHKR is both more efficient to train and more effective than the original AdaBoost.MHR algorithm.

Recurrent neural networks fail to deal with prediction tasks which do not satisfy the causality assumption. We propose to exploit bi-causality to extend the recurrent cascade correlation model in order to deal with contextual prediction tasks. Preliminary results on artificial data show the ability of the model to preserve the prediction capability of recurrent cascade correlation on strict causal tasks, while extending this capability also to prediction tasks involving the future.

To overcome the problem of invariant pattern recognition, Simard, LeCun, and Denker (1993) proposed a successful nearest-neighbor approach based on tangent distance, attaining state-of-the-art accuracy. Since this approach needs great computational and memory effort, Hastie, Simard, and Säckinger (1995) proposed an algorithm (HSS) based on singular value decomposition (SVD), for the generation of nondiscriminant tangent models. In this article we propose a different approach, based on a gradient-descent constructive algorithm, called TD-Neuron, that develops discriminant models. We present as well comparative results of our constructive algorithm versus HSS and learning vector quantization (LVQ) algorithms. Specifically, we tested the HSS algorithm using both the original version based on the two-sided tangent distance and a new version based on the one-sided tangent distance. Empirical results over the NIST-3 database show that the TD-Neuron is superior to both SVD- and LVQ-based algorithms, since it reaches a better trade-off between error and rejection.

In this paper we explore the node complexity of recursive neural network implementations of frontier-to-root tree automata (FRA). Specifically, we show that an FRAO (Mealy version) with m states, l input-output labels, and maximum rank N can be implemented by a recursive neural network with O(radical(log l+log m)lm(N)/log l+N log m) units and four computational layers, i.e., without counting the input layer. A lower bound is derived which is tight when no restrictions are placed on the number of layers. Moreover, we present a construction with three computational layers having node complexity of O((log l + log m)radical lmN) and O((log l + log m) lmN) connections. A construction with two computational layers is given that implements any given FRAO with a node complexity of O(lmN) and O((log l+N log m)lmN) connections. As a corollary we also get a new upper bound for the implementation of finite-state automata (FSA) into recurrent neural networks with three computational layers.

. Usually, not all the solutions of a finite domain constraint satisfaction problem (CSP) are equally desirable: some of them may be preferred to others. However, classical CSPs do not allow for this more informative kind of knowledge representation. On the other hand, semiring-based CSPs (SCSPs), where a value is associated with each tuple in each constraint, generate solutions with a corresponding value attached that can be interpreted as the level of preference of that solution. Sometimes, however, even standard SCSPs are not enough, since one may know preferences over some of the solutions but have no idea on how to code this knowledge into the SCSP. In this paper we consider this situationand propose to address it by first defining a classical CSP and giving some examples of solution preferences, and then learning the corresponding SCSP that behaves as the initial CSP (that is, it has the same solutions) and matches the preferences specified in the examples. In other words, we use the examples as the training set, and we employ a learning scheme to adjust the values to be attached to the constraint tuples, such that the resulting solution preferences coincide with the examples. In this way, we make the SCSP framework more flexible, since it can be used also when it is difficult to assign values to tuples and instead it is easier to rate some of the solutions.

A structured organization of information is typically required by symbolic processing. On the other hand, most connectionist models assume that data are organized according to relatively poor structures, like arrays or sequences. The framework described in this paper is an attempt to unify adaptive models like artificial neural nets and belief nets for the problem of processing structured information. In particular, relations between data variables are expressed by directed acyclic graphs, where both numerical and categorical values coexist. The general framework proposed in this paper can be regarded as an extension of both recurrent neural networks and hidden Markov models to the case of acyclic graphs. In particular we study the supervised learning problem as the problem of learning transductions from an input structured space to an output structured space, where transductions are assumed to admit a recursive hidden statespace representation. We introduce a graphical formalism for representing this class of adaptive transductions by means of recursive networks, i.e., cyclic graphs where nodes are labeled by variables and edges are labeled by generalized delay elements. This representation makes it possible to incorporate the symbolic and subsymbolic nature of data. Structures are processed by unfolding the recursive network into an acyclic graph called encoding network. In so doing, inference and learning algorithms can be easily inherited from the corresponding algorithms for artificial neural networks or probabilistic graphical model.

Standard neural networks and statistical methods are usually believed to be inadequate when dealing with complex structures because of their feature-based approach. In fact, feature-based approaches usually fail to give satisfactory solutions because of the sensitivity of the approach to the a priori selection of the features, and the incapacity to represent any specific information on the relationships among the components of the structures. However, we show that neural networks can, in fact, represent and classify structured patterns. The key idea underpinning our approach is the use of the so called "generalized recursive neuron", which is essentially a generalization to structures of a recurrent neuron. By using generalized recursive neurons, all the supervised networks developed for the classification of sequences, such as backpropagation through time networks, real-time recurrent networks, simple recurrent networks, recurrent cascade correlation networks, and neural trees can, on the whole, be generalized to structures. The results obtained by some of the above networks (with generalized recursive neurons) on the classification of logic terms are presented.

Labeling recursive auto-associative memory (LRAAM) is an extension of the RAAM model by Pollack (1990) to obtain distributed reduced representations of labeled directed graphs. In this paper some mathematical properties of LRAAM are discussed. Specifically, sufficient conditions on the asymptotical stability of the decoding process along a cycle of the encoded structure are given. LRAAM can be transformed into an analog Hopfield network with hidden units and an asymmetric connections matrix by connecting the output units with the input units. In this architecture encoded data can be accessed by content and different access procedures can be defined depending on the access key. Each access procedure corresponds to a particular constrained version of the recurrent network. The authors give sufficient conditions under which the property of asymptotical stability of a fixed point in one particular constrained version of the recurrent network can be extended to related fixed points in different constrained versions of the network. An example of encoding of a labeled directed graph on which the theoretical results are applied is given and discussed.

We present a graph-based method for rapid, accurate search through prototypes for transformation-invariant pattern classifica(cid:173) tion. Our method has in theory the same recognition accuracy as other recent methods based on ''tangent distance" [Simard et al., 1994], since it uses the same categorization rule. Nevertheless ours is significantly faster during classification because far fewer tan(cid:173) gent distances need be computed. Crucial to the success of our system are 1) a novel graph architecture in which transformation constraints and geometric relationships among prototypes are en(cid:173) coded during learning, and 2) an improved graph search criterion, used during classification. These architectural insights are applica(cid:173) ble to a wide range of problem domains. Here we demonstrate that on a handwriting recognition task, a basic implementation of our system requires less than half the computation of the Euclidean sorting method.

In this paper, we propose an extension to the recursive auto-associative memory (RAAM) by Pollack. This extension, the labelling RAAM (LRAAM), can encode labelled graphs with cycles by representing pointers explicitly. Some technical problems encountered in the RAAM, such as the termination problem in the learning and decoding processes, are solved more naturally in the LRAAM framework. The representations developed for the pointers seem to be robust to recurrent decoding along a cycle. Theoretical and experimental results show that the performances of the proposed learning scheme depend on the way the graphs are represented in the training set. Critical features for the representation are cycles and confluent pointers. Data encoded in a LRAAM can be accessed by a pointer as well as by content. Direct access by content can be achieved by transforming the encoder network of the LRAAM into a particular bidirectional associative memory (BAM). Statistics performed on different instances of LRAAM show a strict connection between the associated BAM and a standard BAM. Different access procedures can be defined depending on the access key. The access procedures are not wholly reliable; however, they seem to have a good success rate. The generalization test for the RAAM is no longer complete for the LRAAM. Some suggestions on how to solve this problem are given. Some results on modular LRAAM, stability and application to neural dynamics control are summarized.