Pooling layers play a critical role in Convolutional Neural Networks by reducing spatial dimensions and enhancing translation invariance.While conventional methods like max pooling and average pooling are effective, they can respectively amplify noise or dilute important features.Stochastic pooling introduces probabilistic sampling to improve generalization but is susceptible to biases from outliers, often mimicking max pooling in such cases.To address these limitations, we propose a generalization of stochastic pooling that introduces a tunable parameter to control the balance between uniform sampling, stochastic pooling, and max pooling.Experiments on multiple datasets demonstrate that uniform sampling outperforms the biased one, achieving a favorable trade-off between regularization and performance.

Convolution, a fundamental operation in deep learning for structured grid data like images, cannot be directly applied to point clouds due to their irregular and unordered nature.Many approaches in literature that perform convolution on point clouds achieve this by designing a convolutional operator from scratch, often with little resemblance to the one used on images.We present two point cloud convolutions that naturally follow from the convolution in its standard definition popular with images.We do so by relaxing the indexing of the kernel weights with a "soft" dictionary that resembles the attention mechanism of the transformers.Finally, experimental results demonstrate the effectiveness of the proposed relaxations on two benchmark point cloud classification tasks. Generalizing Convolution to Point CloudsGiven the tensors

The structure learning problem consists of fitting data generated by a Directed Acyclic Graph (DAG) to correctly reconstruct its arcs. In this context, differentiable approaches constrain or regularize an optimization problem with a continuous relaxation of the acyclicity property. The computational cost of evaluating graph acyclicity is cubic on the number of nodes and significantly affects scalability. In this paper, we introduce COSMO, a constraint-free continuous optimization scheme for acyclic structure learning. At the core of our method lies a novel differentiable approximation of an orientation matrix parameterized by a single priority vector. Differently from previous works, our parameterization fits a smooth orientation matrix and the resulting acyclic adjacency matrix without evaluating acyclicity at any step. Despite this absence, we prove that COSMO always converges to an acyclic solution. In addition to being asymptotically faster, our empirical analysis highlights how COSMO performance on graph reconstruction compares favorably with competing structure learning methods.

Downsampling produces coarsened, multi-resolution representations of data and it is used, for example, to produce lossy compression and visualization of large images, reduce computational costs, and boost deep neural representation learning. Unfortunately, due to their lack of a regular structure, there is still no consensus on how downsampling should apply to graphs and linked data. Indeed reductions in graph data are still needed for the goals described above, but reduction mechanisms do not have the same focus on preserving topological structures and properties, while allowing for resolution-tuning, as is the case in regular data downsampling. In this paper, we take a step in this direction, introducing a unifying interpretation of downsampling in regular and graph data. In particular, we define a graph coarsening mechanism which is a graph-structured counterpart of controllable equispaced coarsening mechanisms in regular data. We prove theoretical guarantees for distortion bounds on path lengths, as well as the ability to preserve key topological properties in the coarsened graphs. We leverage these concepts to define a graph pooling mechanism that we empirically assess in graph classification tasks, providing a greedy algorithm that allows efficient parallel implementation on GPUs, and showing that it compares favorably against pooling methods in literature.

Learning dynamic programming algorithms with Graph Neural Networks (GNNs) is a research direction which is increasingly gaining popularity.Prior work has demonstrated that in order to learn such algorithms, it is necessary to have an "alignment" between the neural architecture and the dynamics of the target algorithms, and that GNNs align, in fact, with dynamic programming.Here, we provide a different view of this alignment, studying it through the lens of tropical algebra.We show that GNNs can approximate dynamic programming algorithms up to arbitrary precision, provided that their input and output are appropriately pre-and post-processed.

Sparse pooling methods for graph neural networks typically perform graph reduction by keeping only the top-k vertices according to an adaptive scoring function.Although fast and scalable, these methods destroy the relational information of the graph and possibly make it disconnected.EdgePool is one of the few sparse alternatives that preserve the connectivity of the input graph by performing a series of edge contractions according to an adaptive scoring of the edges, but it has the drawback of being sequential and not scalable on large scale graphs.In this paper we show that EdgePool can be efficiently computed adapting a well-known parallel algorithm from literature, and we also propose a novel, parallel alternative that leverages on an adaptive scoring function of the nodes.We test both methods on standard benchmark datasets, showing that they generally outperform other sparse pooling methods from the literature. * I would like to thank Davide Bacciu and Alessio Conte

Abstract Graph pooling methods provide mechanisms for structure reduction that are intended to ease the diffusion of context between nodes further in the graph, and that typically leverage community discovery mechanisms or node and edge pruning heuristics. In this paper, we introduce a novel pooling technique which borrows from classical results in graph theory that is non-parametric and generalizes well to graphs of different nature and connectivity patterns. Our pooling method, namedKPlexPool, builds on the concepts of graph covers andk-plexes, i.e. pseudo-cliques where each node can miss up toklinks. The experimental evaluation on benchmarks on molecular and social graph classification shows thatKPlexPoolachieves state of the art performances against both parametric and non-parametric pooling methods in the literature, despite generating pooled graphs based solely on topological information.