Projects

Recent ideas [1,2] have considered how the behavior of different activation functions may depend upon their 'topological' properties, e.g., homeomorphism vs continuity. The work of Naitzat et al [1] seems to suggest that ReLU activations exhibit a stronger effect upon the topology, collapsing it in earlier layers and more quickly than homeomorphic activations such as Tanh or Leaky ReLU.

On the other hand, auto-encoders are neural networks which minimize the distance between a reconstruction and the original data, producing both an 'encoder' and 'decoder'.  The stability theorem of persistent homology suggests that if an autoencoder is trained to reconstruct the data within epsilon, the resulting persistence diagrams (a proxy for the topology) are also within distance epsilon.  This would seem to suggest that the topology cannot be changed by much, even with the use of ReLU and a deep autoencoder.  The goal of this project is to investigate and understand how these two observations can be reconciled; and once properly understood, to determine whether these observations can be used to design topologically-faithful dimensionality reduction techniques.  

[1] Naitzat, G., Zhitnikov, A., & Lim, L. H. (2020). Topology of deep neural networks. Journal of Machine Learning Research, 21(184), 1-40.
[2] C.  Olah.   Neural  networks,  manifolds,  and  topology.http://colah.github.io/posts/2014-03-NN-Manifolds-Topology/, 2014.

Project timezone: C

Text-based adventure games, such as Zork, use natural language to describe their setup, receive actions from the player, and describe the effects of such actions. However, they typically also have a clear underlying geometric structure, which links different states ("rooms") with each other as a result of taking actions (e.g. "moving"). This also endows them with a set of symmetries (e.g. it is often the case that going west, then going east, has the outcome of not changing the state). Hence, text adventures represent a fantastic test-bed for benchmarking agents on real-world noisy language data, while still grounding that data in a simplified underlying "world model".

Neural algorithmic reasoning (see Cappart et al., IJCAI'21; Section 3.3.) represents an emerging area of (graph) representation learning that seeks to emulate operations of classical algorithms and data structures within a high-dimensional latent space---allowing us to more directly execute classical algorithms over noisy data. A classical collection of algorithms shown to be efficiently learnable in this way are path-finding routines (such as the Bellman-Ford algorithm). Quickly solving text adventures typically involves (implicitly) constructing a map of the environment, determining the current and goal states in this map, then searching for a (shortest) path from the current state to the goal.

All of these components are tricky to do in a generic text adventure setting. To simplify, we will assume that the map is given to us. It is still non-trivial to map current and previous state descriptions to a particular current and goal state, and through the use of neural algorithmic reasoning, we will attempt to directly feed such natural language descriptions to an algorithm, and then use the output representations of that algorithm to find shortest paths to the required goal state.

The work will be based on the TextWorld environment, specifically the subset of coin-collecting environments proposed by Yuan, Côté et al. (EWRL'18), for which code and example agents are already available. While our focus will not necessarily be reinforcement learning, I anticipate that this will provide an excellent starting point. Neural path-finders will be trained by using the methodology proposed by Veličković et al. (ICLR'20) and deployed in the style of XLVIN (Deac et al., NeurIPS DeepRL'20).

Project timezone: C

Real-world applications often require sequential decision making, and, in order to reason over longer time horizons, planning. One way of doing planning is by estimating the effects of actions and the values of the states. Then a plan can be constructed consisting of the actions which lead to overall highest possible value.

Fortunately, there is a known dynamic programming algorithm, Value Iteration (VI), which can find the optimal value function of a known Markov Decision Process (MDP). Even more, we know that the VI update is taking an expectation over the neighbouring states’ values, which is something a CNN can do in a grid, or, more generally, a graph neural network (GNN) in a graph. The GNN can then be used as part of the policy network. This has been directly validated in recent work, where GNNs have been successfully used to execute dynamic programming algorithms.

In this project, we will focus on the recently proposed eXecuted Latent Value Iteration Network (XLVIN) model [1], which provides us with one way to apply VI-style reasoning even if the underlying state graph is not known. While the XLVIN agent holds promise, it leaves several design decisions which have not been fully explored—perhaps the most interesting of which is generalising beyond discrete action spaces. By using a simple continuous control environment (such as LunarLander), we will first construct an XLVIN agent relying on simple MLP-based encoders. Then, we will take it one step further and bin the environment’s continuous action space, allowing for more fine-grained control.

Eventually, the number of bins may expand the computational budget of our planner (which normally applies an exhaustive breadth-first search strategy), so we will attempt various forms of exploratory planning. Ultimately, this can lead us to fully continuous action spaces, specified using, for example, a Gaussian distribution over various torque actions.

[1] Deac A., Velickovic P., Milinkovic O., Bacon P., Tang J. et. al. 2020. “XLVIN: EXecuted Latent Value Iteration Nets.” http://arxiv.org/abs/2010.13146

Project timezone: A

A particularly successful and instructive special case of group equivariant neural networks is when the input consists of images painted on a sphere and the transformation to which we desire invariance are 3D rotations, leading to work on spherical CNNs. Approaches to the design of spherical CNNs include combined real and harmonic space methods (such as [1] and [2]) and fully Fourier space approaches (such as [3]). The former exploit efficient sampling theorems which ensure that the underlying 3D rotational symmetry is captured properly. However, they also lead to a somewhat unconventional architecture composed of repeated forward and backward Fourier transforms since the non-linearity is still applied pointwise in "real space". However applications of the non-linearity in this manner also lead to errors which break strict rotational equivariance. On the other hand, fully Fourier approaches, which maintain a harmonic space representation of the input to the end, afford strict rotational equivariance, but are prohibitively expensive. In this project we will explore methods for speeding up such a harmonic space approach while still maintaining exact rotational equivariance. In particular, we will examine the channel structure of the approach of [3] building further off the approach of [4] to produce more efficient implementations.

[1] Taco Cohen, Mario Geiger, Jonas Kohler, and Max Welling. Spherical CNNs. International Conference on Learning Representations, 2018.

[2] Carlos Esteves, Christine Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis. Learning SO(3) Equivariant Representations with Spherical CNNs. European Conference on Computer Vision, 2018.

[3] Risi Kondor, Zhen Lin and Shubhendu Trivedi, Clebsch-Gordan Nets: A Fully Fourier Space Spherical Convolutional Neural Network. IAdvances in Neural Information Processing Systems, 2018.

[4] Oliver J. Cobb, Christopher G. R. Wallis, Augustine N. Mavor-Parker, Augustin Marignier, Matthew A. Price, Mayeul d'Avezac, Jason D. McEwen, Efficient Generalized Spherical CNNs, International Conference on Learning Representations, 2021.

Project timezone: A

Optimal transport generalizes sorting to spaces of dimension D>1. It induces the Wasserstein metric (aka. Earth Mover’s Distance) between probability distributions, which allows us to work with unlabelled point clouds using a simple and intuitive particle-based model.

In this project, we will build upon the fast numerical routines of the GeomLoss library (https://www.kernel-operations.io/geomloss/) to explore the use of the Wasserstein metric in geometric data analysis. We will first start with a short lecture on the definition and main properties of optimal transport. Then, we will rely on simple experiments with Wasserstein barycenters and gradient flows to get an intuitive understanding of the optimal transport distance. Finally, we will study the impact of this metric on several standard tasks, from 3D shape registration to the UMAP visualization of a dataset of histograms.

This project will allow you to get a hands-on experience of optimal transport tools in realistic application scenarios. Notably, we will highlight both the strengths and the limitations of this theory in data sciences: by the end of the week, you should have a clear picture of what optimal transport can (and cannot) bring to your own research work.

Project timezone: C

Graph Neural Networks (GNN) have been achieving state-of-the-art performance in various graph related tasks, being the first adopted solution especially when graphs have node and edge features.  However, GNNs have several difficulties [4], such as capturing long-range graph interactions (due to the oversquashing effect) or differentiating locally isomorphic nodes [5] (e.g. based on the WL test). Moreover, GNNs haven't yet been reconciled or combined with positional independent node embedding (PINE) approaches such as Node2Vec [1] or distortion based embeddings (e.g. Poincare embeddings [2]). The latter are known to capture well long-range graph interactions, can be trained fully unsupervised, but are not uniquely defined as they can be arbitrarily transformed with a shared invertible matrix while keeping the loss value unchanged. In this project, we propose to explore combining GNNs and PINEs in a joint end-to-end supervised trainable method by leveraging the power of implicit differentiation (ID) [3] traditionally used in meta-learning approaches. Given an input graph, we will create an implicit layer that learns PINEs based on an unsupervised objective (e.g. distortion loss), and these will in turn become node features that will be the input of a GNN. Importantly, using ID, we can backpropagate through the PINE training procedure and, thus, obtain meaningful PINE features for the downstream task at hand.  This would allow us to obtain globally (at graph level) correlated node features for GNNs, to differentiate non-isomorphic graphs otherwise indistinguishable by the WL test, and to reflect on other (unsupervised) inductive biases useful for specific downstream graph problems.


[1] Node2Vec: https://snap.stanford.edu/node2vec/
[2] Poincare Embeddings: https://arxiv.org/pdf/1705.08039.pdf
[3] ID Neurips 2020 tutorial: https://www.youtube.com/watch?v=MX1RJELWONc
[4] GNN difficulties: https://arxiv.org/pdf/2006.05205.pdf , https://arxiv.org/abs/2006.13318, rb.gy/quo3n6

[5] https://www.mit.edu/~vgarg/GNNs_FinalVersion.pdf

Project timezone: A

Existing learning-based methods for mesh reconstruction from fixed point clouds mostly generate triangles individually, making it hard to create consistent manifold meshes. In this project, we will build a novel method aimed at estimating local surfaces from point clouds and constructing high quality meshes. We are interested in leveraging the properties of 2D Delaunay triangulations to construct a mesh from small manifold surface elements. The method first learns local logarithmic maps around estimated geodesic neighborhoods centered at each point, from which we can compute manifold Delaunay triangulation. The local 2D projections are then synchronized to maximize the manifoldness of the global reconstructed mesh.

During this week, we will first build a robust learning-based pipeline to mesh point clouds. Throughout this process, you will gain significant familiarity with or get a deeper understanding of basic concepts in geometry for representing 3D shapes as well as existing tools for machine learning on point clouds such as PointNet or FoldingNet. In the second stage of this project, we will explore novel directions to improve the proposed method and build tools for both meshing and analysis of 3D surfaces.

Project timezone: C

Optimization over smooth manifolds or manifold optimization involves minimizing an objective function over a smooth constrained set. Many such sets have usually a manifold structure. Some particularly useful manifolds include the set of orthogonal matrices, the set of symmetric positive definite matrices, the set of subspaces, the set of fixed-rank matrices/tensors, and the set of doubly stochastic matrices (optimal transport plans), to name a few [1]. Consequently, there has been a development of a number of manifold optimization toolboxes [2].

In this project, we make use of these wonderful tools to solve a few machine learning problems with manifold optimization. The aim would be to get a hands-on experience of manifold optimization.

[1] Boumal, N., 2020. An introduction to optimization on smooth manifolds. Web: http://sma.epfl.ch/~nboumal/book/index.html.

[2] Manopt, pymanopt, Manopt.jl, McTorch, Geomstats, ROPTLIB, and so on. The links to many of these toolboxes are available on https://www.manopt.org/about.html.

Project timezone: B

Recent work [1] on neuroimaging has demonstrated significant benefits of using population graphs to capture non-imaging information in the prediction of neurodegenerative and neurodevelopmental disorders. These non-imaging attributes may contain demographic information about the individuals, e.g. age or sex, but also the acquisition site, as imaging protocols and hardware might significantly differ across sites in large-scale studies. The effect of the latter is particularly prevalent in functional connectomics studies, where it’s unclear how to sufficiently homogenise fMRI signals across the different sites. A recent study [2] has highlighted the need to investigate potential biases in the classifiers devised using large-scale datasets, which might be imbalanced in terms of one or more sensitive attributes (like gender and race). This can be exacerbated when employing these attributes in a population graph and lead to disparate predictive performance across sub-populations. This project aims to uncover any potential biases of a semi-supervised classifier that relies on a population graph and explores methods to mitigate such biases to produce fairer predictions across the population.

[1] *Parisot, S., *Ktena, S. I., Ferrante, E., Lee, M., Moreno, R. G., Glocker, B., & Rueckert, D. Disease Prediction using Graph Convolutional Networks: Application to Autism Spectrum Disorder and Alzheimer’s Disease. Medical Image Analysis, 2018

[2] Larrazabal, Agostina J., et al. "Gender imbalance in medical imaging datasets produces biased classifiers for computer-aided diagnosis." Proceedings of the National Academy of Sciences, 2020.

Project timezone: C

Omnidirectional signals occur in a wide variety of domains, from climate and weather science to astronomy and omnidirectional computer vision. Neural networks for omnidirectional data should respect the topological and geometric structure and symmetries of the signal domains (typically a sphere-like manifold). Many kinds of spherical CNNs have been developed, but typically these involve non-standard and costly operations that may be hard to implement. By contrast, the gauge equivariant Icosahedral CNN (1) is implemented by performing a standard conv2d over a collection of local charts concatenated into a feature map. One downside of the method is that it requires projecting the spherical signal to the icosahedron. On the other hand, the method is very efficient, and exactly equivariant to the rotational symmetries of the icosahedron.

Project timezone: C

One of the holy grails of modern theoretical physics is the unification of Quantum Mechanics with Einstein’s relativity. String theory is the only known consistent theory of quantum gravity, and arguably the most promising candidate for a unified theory of physics. Since its inception in the late 1960s, it has provided tremendous insights into our understanding of the physical world, and has overseen many interesting developments in various branches of pure mathematics and theoretical physics. Despite string theory’s many successes, a string model that explains all observed data from cosmology and particle physics experiments, has eluded discovery. This is owing to the particularly large landscape of valid string theory solutions, estimated to be of the size 10^{270,000}. Most of these solutions are thought to lead to descriptions of universes that do not resemble ours in detail. 

String theory posits extra-dimensions of space. These are often described by complex geometries called Calabi—Yau manifolds. A class of string theory solutions (or vacua) is characterised by Complete Intersection Calabi--Yau manifolds, and bundles over them. The data corresponding to these are encoded as bipartite graphs and integer matrices, whose size is governed by the (topological) properties of the bundles and Calabi--Yau geometries. The resulting dataset is of size tens of thousands. The objective of this project is to characterise these different solutions (Universes) using Machine Learning. More concretely, the aim is to obtain a suitable metric on this space of solutions that 'scores' stringy solutions based on their closeness to reality, i.e., observations from particle accelerators like the LHC. Such a metric could be approximated by a sufficiently deep neural network. Insights from such a metric will allow the construction of even more realistic string solutions, ESP on geometries that have been out of current computational reach. 

The project will allow the participant(s) to delve into fundamentals of complex geometry, learn about effective representations of geometric data in Machine Learning, and develop an empirical understanding of the ML tools that are effective in such geometric problems.

References:

[1] Calabi-Yau Spaces in the String Landscape -- Yang-Hui He, https://arxiv.org/abs/2006.16623

[2] Calabi-Yau manifolds, Discrete Symmetries, and String theory -- Challenger Misha, https://ora.ox.ac.uk/objects/uuid:4a174981-085e-4e81-8f27-b48533f08315

[3] Heterotic Line Bundle Standard Models -- Lara B. Anderson, James Gray, Andre Lukas, Eran Palti

https://arxiv.org/abs/1202.1757

Project timezone: C

In this project, we will take a closer look into surface reconstruction from point clouds. This project is a hands-on project in PyTorch. You will gain familiarity with 3D surface reconstruction and applying deep neural networks to meshes. The project is mainly focused on the Point2Mesh [1] technique, which optimizes the weights of a CNN to deform some initial mesh to shrink-wrap the input point cloud. You will apply this technique to scans and a wider variety of data in order to explore the current strengths and limitations of such a technique, and how it can be further improved. One interesting direction is to learn which edge to split, thereby defining where to add additional mesh connectivity. By the end of the project, you should better understand these topics from a theoretical and practical perspective, and gain insights with respect to how to incorporate similar concepts into your own research.

[1] Point2Mesh: A Self-Prior for Deformable Meshes. Rana Hanocka, Gal Metzer, Raja Giryes, and Daniel Cohen-Or. SIGGRAPH 2020.

Project timezone: to be decided

Many real-world applications require us to study large-scale graphs which are computationally expensive to process and difficult to understand intuitively.

To solve this issue, graph coarsening (or, sometimes, "pooling") techniques allow us to reduce the size of a graph while preserving its overall characteristics. Many works have been proposed recently to tackle this problem, especially in the field of graph neural networks, but it remains a challenging and open research direction.

Most techniques for graph coarsening assume that the input graph is assortative, that is, a graph in which neighboring nodes are likely to be similar. Conversely, many real-world graphs are disassortative graphs in which connections are heterophilous.
For example, scale-free graphs (in which nodes with small degree are likely to be connected to nodes with a high degree) are very frequent in nature and technology.

In this project, we will attempt to develop a coarsening algorithm for strongly disassortative graphs. This will require us to discard many assumptions that are usually exploited in the design of coarsening algorithms, and chiefly the assumption that clusters of nodes can be identified in densely connected communities.

First, we will study the effect of typical coarsening algorithms when applied to disassortative graphs. Then, we will formulate our coarsening problem as an optimization to obtain a desired degree of disassortativity in the coarse graph. Finally, we will identify one or more solutions to the problem, either through procedural techniques or end-to-end learning.

Project timezone: C

Geodesic distortion minimization has been demonstrated as an effective approach for self-supervised non-rigid correspondence; see "Unsupervised learning of dense shape correspondence‏" (CVPR 2019).

There, shape descriptors were represented by a deep network, and the network was optimized to minimize the geodesic distortion criteria of the correspondence, resulting through the Functional Maps pipeline.

A novel method to differentiate the geodesic distortion with respect to the deformation field was introduced later in the paper "Limp: Learning latent shape representations with metric preservation priors" (ECCV 2020).

The proposed project aims at combining the observations in both mentioned publications. The goal is to represent the deformation field using a deep network and to optimize it to admit the following requirements:

1) Geodesic distance preservation of the deformation field 

2) Overlapping between the deformed source shape and the target shape.

Project timezone: C

Latent variable models, such as the variational autoencoder, suffer from the identifiability problem: there is no unique configuration of the latent variables. This is problematic as latent variables are often inspected, e.g. through visualization, to gain insights into the data generating process. The lack of identifiability then raise the risk of
misinterpreting the data as conclusions may be drawn from arbitrary latent instantiations.

In this project you will investigate a geometric solution to the
identifiability problem that amounts to endowing the latent space with a particular Riemannian metric. You will learn latent representations and compute geodesics accordingly.

References:
(*) Latent Space Oddity: on the Curvature of Deep Generative Models Georgios Arvanitidis, Lars Kai Hansen and Søren Hauberg. In International Conference on Learning Representations (ICLR), 2018.
(*) Only Bayes should learn a manifold (on the estimation of
differential geometric structure from data)
Søren Hauberg.

Project timezone: C

Graph deep learning has recently emerged as a powerful technique especially in the medical domain. Graph-based methods have shown promising results on a broad spectrum of applications ranging from social science, biomedicine, and particle physics to computer vision, graphics, and chemistry. One of the current problems with most of the GCN based methods is the requirement of a pre-computed graph. However, in many scenarios, especially in the medical and healthcare domain, the graph may not be given. 

In this project, we will explore how such a graph can be learned mainly for medical applications. Given the population of individuals, we focus on predicting the age and gender of each based on brain MRI features. The method is inspired by our recent work on the differentiable graph module [1, 2] which can be further extended to any problem where the graph is unknown and can be inferred from the input features. With this project, you get to learn how to define a graph learning problem in the non-/ medical domain and further collaboration with a brain mesh analysis project.

[1] Kazi, A., Cosmo, L., Navab, N. and Bronstein, M., 2020. Differentiable graph module (dgm) graph convolutional networks. arXiv preprint arXiv:2002.04999.

[2] Cosmo, L., Kazi, A., Ahmadi, S.A., Navab, N. and Bronstein, M., 2020, October. Latent-Graph Learning for Disease Prediction. In International Conference on Medical Image Computing and Computer-Assisted Intervention (pp. 643-653). Springer, Cham.

Project timezone: C

In this project, we deal with manifold-valued images, which occur, e.g., in DT-MRI (values are symmetric positive definite matrices) or material science (EBSD data describing grain orientation in materials). As the potential applications are becoming more and more, many classical imaging problems have also been investigated for the manifold setting. While some problems are easy to generalize, others require more attention. One specific issue popping up is that the values at each pixel are not rotation invariant anymore (rotating a point by 90 degrees changes nothing, rotating an arrow pointing in some direction by 90 degrees also changes its direction). Hence, some applications can not be tackled with the straight-forward extension of Euclidean transformation models. Originally, we have proposed a metamorphosis (or morphing) model for manifold-valued images which does note take this observation into account. Extending the model and deriving similar theoretical results as for the original one incorporating this observation will be the main goal of this project. Part of the project is devoted to the numerical implementation of the model. There is some Matlab Code available for the original version, but we can clearly also start from scratch in Python if you prefer. Being already a bit familiar with one of the available manifold toolboxes is definitely beneficial for the project.

Project timezone: C

Owing to their scalability and simplicity, message-passing neural networks (MPNNS) are currently the leading architecture for deep learning on graph-structured data. However,  [1,2] recently showed that these architectures have limited expressive power. The most famous example is that MPNNs cannot distinguish a graph that consists of two triangles and a graph that consists of a single cycle of length 6 (see attached figure). This limitation raises a fundamental question: is it possible to make MPNNs more expressive? Several recent works  [3,4,5] suggested architectures that aim to address this problem.

In this project, we will develop a novel approach that tackles this problem. The key to our solution is the observation that while two graphs may not be distinguishable by an MPNN, it might be easy to find distinguishable subgraphs. Following that observation, we suggest treating each graph as a set of subgraphs generated according to some predefined rule, e.g., all graphs that can be obtained by removing one edge from the original graph. We propose to process this set using the DSS framework [6], which allows processing sets of symmetric elements. To deal with the possible computational burden, we will also consider efficient random sampling schemes to improve time complexity. We will study this new model’s theoretical properties, e.g., is it provably more expressive than other MPNNS? and evaluate its practical performance.

[1] Morris, Christopher, et al. "Weisfeiler and leman go neural: Higher-order graph neural networks." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. 2019.

[2] Xu, Keyulu, et al. "How powerful are graph neural networks?." arXiv preprint arXiv:1810.00826 (2018).

[3] Abboud, Ralph, et al. "The Surprising Power of Graph Neural Networks with Random Node Initialization." arXiv preprint arXiv:2010.01179 (2020).

[4] Vignac, Clément, Andreas Loukas, and Pascal Frossard. "Building powerful and equivariant graph neural networks with structural message-passing." arXiv e-prints (2020): arXiv-2006.

[5] Bouritsas, Giorgos, et al. "Improving graph neural network expressivity via subgraph isomorphism counting." arXiv preprint arXiv:2006.09252 (2020).

[6] Maron, Haggai, et al. "On learning sets of symmetric elements." International Conference on Machine Learning. PMLR, 2020.

Project timezone: A

Molecular property prediction is an important task in cheminformatics. Current property prediction methods are based on graph neural networks and require a large amount of training data to achieve state-of-the-art performance. Unfortunately, most datasets in cheminformatic domains are small (e.g., less than 1000). On the other hand, pretraining methods have achieved great success in computer vision and natural language processing. In this project, we seek to investigate how to pretrain graph neural networks on a large collection of unlabeled molecules using ELECTRA (Clark et al., 2020). The goal is to learn a masked language model to generate corrupted molecules and train a discriminator to distinguish the real molecules from the fake molecules. The method will be evaluated on MoleculeNet benchmark (Wu et al., 2017) to test its empirical performance.

Project timezone: A

Geometric integration plays a central role in many applications. In this project, we will discuss its applications to sampling and optimisation.
For sampling, we will uncover the canonical geometry of measures and apply it construct diffusions and dynamics preserving measures, symmetries and constraints. We will then discuss general strategies to construct Hamiltonian-based geometric integrators maintaining some critical properties, in particular volume preservation and conservation of a shadow energy, and hence obtain the family of Hamiltonian Monte Carlo samplers on vector spaces and manifolds. 

We will then apply similar techniques to optimization in order to obtain rate-matching integrators that preserve the decay rate of dissipative dynamics.

Project timezone: C