Project in Computer Science 1 - Machine Learning Algorithms and Applications

Type: Develop and validate a deep learning model.

Recommended Skills: Experience with machine learning using Python. Ideally: experience with implementing and training neural networks with a deep learning framework (like PyTorch).

Task: Develop and validate a deep learning model to automatically segment intraocular lens (IOL) axis in toric IOLs.

Context: In cataract surgery, patients with higher astigmatism require toric IOL implantation for improvement in vision-related quality of life (spectacle independence). Rotational stability of the IOL is crucial. Thus, we want to develop a deep learning model to automatically detect IOL rotation based on clinically recorded images, to validate safety and efficacy of new toric IOLs.

Suggested approach: Implement a deep learning model and evaluate its performance with the standardized and well-tried method of Schartmüller et al.. The work will be conducted in adherence to the tenets of the Declaration of Helsinki and a positive ethics approval.

Related work: Schartmüller et al., Rotational Stability of Intraocular Lenses: A Standardized Method for More Accurate Measurements in Future Studies. Am J Ophthalmol. 2021 Nov;231:200-207. doi: 10.1016/j.ajo.2021.06.006. Epub 2021 Jun 8. PMID: 34116009.

Contact person:
Marcus Lisy
Department of Ophthalmology and Optometry
Medical University of Viennamarcus.lisy@meduniwien.ac.at
Tel.: 01/40400-79450

Type: Reading and report-writing project on the constructive proof of Chernoff bounds and its implications in probability theory.

Recommended Skills:

• Probability theory
• Mathematical maturity

Task: Chernoff bounds are crucial in probability theory because they provide exponentially tight bounds on the tail probabilities of sums of independent random variables. This allows us to quantify the likelihood that the sum deviates significantly from its expected value. They are widely used in areas like randomized algorithms, machine learning, and complexity theory, where controlling the probability of large deviations is essential for guaranteeing performance and reliability.

This project focuses on gaining a deep understanding of a recent constructive proof of Chernoff bounds, as presented by Impagliazzo and Kabanets. The proof is a combinatorial approach that allows not only for bounding the probability of large deviations but also for identifying the subsets (witnesses) responsible for these deviations. Students will review the proof in detail, compare it to the standard (non-constructive) proof, and explore its potential applications in areas such as distribution testing and complexity theory.

Objectives:

1. Understand Chernoff bounds: Learn the classical non-constructive proof of Chernoff bounds, which uses moment-generating functions to bound tail probabilities.
2. Study the constructive proof: Analyze how the constructive proof by Impagliazzo and Kabanets identifies witnesses for large deviations and its use of combinatorial counting arguments.
3. Explore implications: Investigate the implications of the constructive approach in probabilistic algorithms, including applications in complexity theory, uniformity testing, and algorithmic error detection.

Suggested Approach:

• Read foundational papers: Start by reading the paper by Impagliazzo and Kabanets on the constructive proof of Chernoff bounds [1]. Focus on understanding the steps of the proof and how it differs from the classical Chernoff bound.
• Compare and analyze: Compare the constructive proof to the standard method, highlighting differences in technique, results, and implications for real-world applications.
• Applications: Investigate how the constructive Chernoff bound can be applied to areas like testing non-uniform distributions, error detection in coding theory, and probabilistic algorithms.
• Write a report: Summarize the key findings and insights from the reading, providing a comparison of the two approaches and discussing the potential broader impact of the constructive method.

References:

1. Impagliazzo, R., & Kabanets, V. Constructive Proof of Concentration Bounds. 2009.
2. One hour long lecture by Valentine Kabanets at the Institute of Advanced Studies, Princeton.

Advisor: Sagar Malhotra

Type: Implementing and training GNNs with PyTorch (Geometric)

Recommended Skills: (Some) experience with machine learning in Python.

Task: Train two GNN variants using contrastive learning and compare their performance

Context: The expressivity of GNNs is usually described in terms of graph isomorphism testing, i.e., whether GNNs are able to map isomorphic graphs to the same point in the embedding space and non-isomorphic graphs to different points. Formally, they are only as good in distinguishing isomorphic graphs as the Weisfeiler-Leman graph isomorphism test (WL). However, for some real-world graph datasets, we might actually be interested in a slightly different inductive bias: Similar graphs should be embedded close to each other, while dissimilar graphs should be embedded distant from each other in the embedding space. One possible way to achieve these kinds of embeddings is through contrastive learning, where learning is done by comparing positive (i.e., similar graphs) and negative (i.e., dissimilar graphs) pairs of graphs.

Now, if distances between representations are all that are relevant, we can also look at methods that more directly (some might say: more interpretably) implement distances on graphs. One such approach are Wasserstein distances on Multisets of Weisfeiler-Leman (WL) Labels (Negishi 2024, Beaumont, 2022).
This measure can be efficiently computed (see Remark 2.30 in Peyre and Cuturi, 2018; Le et al., 2019) and is differentiable wrt. some parameter vector. Hence, we can, instead of a siamese network to compute a fixed distance between learned GNN embeddings compute a learned distance between fixed Multisets of WL labels.

I wonder how well that performs, if we the number of trainable parameters in GNN and our alternative approach is roughly equal.

Suggested approach:

• Choose a suitable contrastive learning task.
• Alternatively/additionally: Use graph classification datasets in a contrastive training regime (TripletLoss or so)
• Choose one to three GNN architecture(s) (e.g. GIN, GCN, GAT)
• Implement the training method for WILTs proposed by Masahiro Negishi et al.
• Compare the performance of GNN and WILT

Related work: Masahiro Negishi, Pascal Welke, and Thomas Gärtner (2024): WILTing Trees: Interpreting the Distance Between MPNN Embeddings. Under Review Samuele D’Avenia (2024) - Contrastive Learning Ideas for Graph Embedding. Project Report, TU Wien Fabrice Beaumont (2022) - Learning Graph Similarities Using The Weisfeiler-Leman Label Hierarchy. Master Thesis, University of Bonn Gabriel Peyré and Marco Cuturi (2018) - Computational Optimal Transport. ArXiv:1803.00567 Tam Le, Makoto Yamada, Kenji Fukumizu, Marco Cuturi (2019) - Tree-Sliced Variants of Wasserstein Distances. NeurIPS

Advisor: Pascal

Question: Do node labelled real-world graphs have (almost) geodesically convex classes?

Suggested approach: Check for node-labelled graphs in benchmark datasets (e.g., http://snap.stanford.edu/data/), whether the classes (vertex sets corresponding with same node label) are convex. Try to find a more realisitic notion of convexity which, for example, allows outliers and disconnected regions.

Related work:

• Ignacio M. Pelayo “Geodesic Convexity in Graphs” (Springer 2013) (chapter 1, 2.1, 2.2, and 2.10) (Researchgate link)
• Eike Stadtländer, Tamás Horváth, and Stefan Wrobel. “Learning weakly convex sets in metric spaces.” (ECMLPKDD 2021)
• Florian Seiffarth, Tamás Horváth, and Stefan Wrobel “Maximal Closed Set and Half-Space Separations in Finite Closure Systems.” (ECMLPKDD 2019)
• Maximilian Thiessen and Thomas Gärtner. “Active Learning of Convex Halfspaces on Graphs.” (NeurIPS 2021).

Context: While classical notions of convexity in Euclidean space are largely studied and used by the machine learning community, related notions in discrete spaces (e.g., graphs) have been mostly overlooked. A vertex set S is in a graph is geodesically convex, if all shortest paths joining two vertices in S stay in S. Recently, we (and other groups) have started to use the notion of convexity in graphs to achieve guarantees for machine learning problems on graphs. Currently, these results are mainly of theoretical interest, but the next step is to evaluate and test the developed methods on real-world graphs. For that, we have to find reasonable datasets and application areas that fit our convexity-based assumptions. Your goal is to identify graphs where the labelled subgraphs are (close to) convex.

Advisor: Max

Type: Mostly implementing and training GNNs with PyTorch (Geometric), some going through related work and collecting interesting generalization bounds

Recommended Skills: (Some) experience with machine learning in Python. Familiarity with mathematical proofs is helpful to understand the related work, but not strictly required for this project

Question: How (empirically) tight are generalization bounds for graph neural networks?

Context: In machine learning theory, we are interested in giving formal guarantees about the behavior of machine learning algorithms. One type of guarantee is about generalization, where we may want to provide an (upper) bound on the generalization error, i.e., how well does a model generalize to yet unseen data? Recently, there has been a number of theoretical contributions for generalization bounds for graph neural networks. It would be interesting to assess (1) how practically useful they are, and (2) how they compare to each other.

Suggested approach: Consult related work and choose two to three different generalization bounds for graph neural networks (this can be done in discussion with your supervisor). Assess them empirically on a number of graph benchmark datasets for at least one GNN architecture.

Related work:

• Garg, Vikas, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. International Conference on Machine Learning. PMLR, 2020.
• Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. In International Conference on Learning Representations (2021).

Advisor: Tamara

Type: Implementation and training of GNNs with PyTorch.

Question: Is there a privacy risk of data leakage from information contained in gradients computed during the training of a GNN?

Suggested Approach: Definition and evaluation of an attack strategy using information contained in the gradients computed during training and/or inference, adapting the approach of Zhu et al. (2019) to the graph setting.

Related Work:

• Zhang, He, et al. “Trustworthy graph neural networks: Aspects, methods and trends.” arXiv preprint arXiv:2205.07424 (2022).
• Zhu, Ligeng, Zhijian Liu, and Song Han. “Deep leakage from gradients.” Advances in neural information processing systems 32 (2019).
• Yin, Hongxu, et al. “See through gradients: Image batch recovery via gradinversion.” Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. (2021).

Context: Information contained in the gradients computed to train a neural network can be used to infer private information on training data (Zhu et al., 2019). This risk is under-investigated in the GNN context (Zhang et al., 2022), where focus is usually put on the privacy risks of the final, trained model. It is thus interesting to investigate gradient inversion attacks (Yin et al., 2021) for GNN models and evaluate their efficacy and the possible protections offered by, e.g., differential privacy.

Advisor: Patrick

Type: Implementation and training of GNNs with PyTorch.

Question: Are GNNs which are robust against adversarial attacks less private? Are private GNNs less robust?

Suggested Approach: Implementation/adaptation of robust GNNs and evaluation of the privacy/utility trade-off on benchmark datasets against a number of privacy attacks. A possible focus can be on private/adversarial perturbations on the edges of the graphs: how does the accuracy of an adversarially attacked GNN compare to that of a private one?

Related Work:

• Song, Liwei, Reza Shokri, and Prateek Mittal. “Privacy risks of securing machine learning models against adversarial examples.” Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019.
• Ghazi, Badih, et al. “Robust and private learning of halfspaces.” International Conference on Artificial Intelligence and Statistics. PMLR, 2021.
• Dai, Enyan, et al. “A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability.” arXiv (2022).

Context: A tension between differential privacy and robustness (against adversarial examples) has been empirically observed [Song et al., 2019] and theoretically shown [Ghazi et al., 2021]. Do these result extend to structured data? Focusing on a centralised setting and possibly on perturbations of the graph structure: are more robust algorithms less private (or vice versa)?

Advisor: Patrick

Type: Implement and experiment with GNNs

Recommended Skills: Experience with deep learning using PyTorch

Task: Testing Zero-One laws on Graph Neural Networks on distributions beyond Erdos-Reyni

Context: Zero-One laws state that the probability of any first order logic sentence on a random graph approaches zero or one, as larger and larger graphs are sampled [1]. Recent results [2] have shown that GNNs also exhibit zero-one laws on Erdos-Reyni random graphs. In this project our goal would be to empirically test this behavior of GNNs beyond the Erdos-Reyni random graph model. We will be interested in checking this behavior on graphons — a very general random graph model, and on random graph models, where edge probability depends on the number of nodes in the graph. Especially, we would be interested in testing distributions where zero-one laws for first order logic do not hold.

Suggested approach: Create synthetic dataset by randomly generating graphs w.r.t the above mentioned distributions, and label the graphs with a first order logic rule of your choice — 1 if the fol rule is true on the graph and 0 otherwise. Learn a GNN on those graphs. Now, check the probability of the randomly generated graph being classified as 1, as the graph size increases, both with the GNN and with the first order logic formula.

Related work:
[1] Spencer. Strange Logic of Random Graphs. Springer-Verlag 2001 [2] Adam Day et al. Zero-One Laws of Graph Neural Networks. NeurIPS 2023

Advisor: Sagar Malhotra

Type: Understanding a theory focused paper and implementing a graph algorithm

Recommended Skills: A good understanding of graph algorithms and some experience with theoretical computer science. Experience with implementing graph algorithms.

Task: Implement an algorithm to find pairs of non-isomorphic that cannot be distinguished by message passing graph neural networks or the Weisfeiler-Leman graph isormoprhism test

Context: It is known that message passing graph neural networks (MPNNs) have limitations in the kind of functions they can express. Formally, they are only as good in distinguish isomorphic graphs as the Weisfeiler-Leman graph isomorphism test (WL). Thus, any pair of graphs that cannot be distinguished by WL cannot be distinguished by any MPNN i.e., any MPNN will return the same output for the two graphs. Arvind et al. propose an efficient algorithm to determine whether a given graph can be distinguished from all other graphs by WL. Such graphs are called amenable. We propose using this algorithm to generate a dataset of pairs of graphs that are indistinguishable by WL and MPNNs. This dataset could serve as a benchmark to evaluate graph neural networks that are more expressive than the MPNN in distinguishing graphs.

Suggested approach: Implement the algorithm from Corollary 11 of Arvind et al.. This algorithm allows us to search for non-amenable graphs i.e., graphs for which a non-isomorphic graph exists that cannot be distinguished via WL. Implement a brute-force algorithm to find this non-isomorphic graph or (optionally) design a more efficient algorithm to find these graphs.

Related work:

• Arvind et al., On the Power of Color Refinement, International Symposium on Fundamentals of Computation Theory, 2015
• Xu et al., How Powerful are Graph Neural Networks?, ICLR, 2019

Advisor: Fabian

Type: Implementation and training of GNNs with PyTorch.

Question: What is the privacy protection performance of differentially private GNNs against various privacy attacks?

Suggested Approach: Implementation/adaptation of existing differentially private GNNs and evaluation of the privacy/utility trade-off on benchmark datasets against a number of privacy attacks.

Related Work:

• Dai, Enyan, et al. “A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability.” arXiv (2022).
• Sajadmanesh, Sina, and Daniel Gatica-Perez. “Locally private graph neural networks.” Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021.

Context: Similarly to deep learning algorithms trained on images and text, GNNs rely on large amounts of (possibly sensitive) data. Differential privacy is one of the possible approaches to protect sensitive data, which is of particular importance when the models are trained in a centralised way. In particular, there exist differentially private techniques that aim at preserving the privacy of features, labels, or edges of the graph, mainly focusing on protection against membership inference attacks. Nevertheless, privacy protection performance against various other privacy attacks if under-investigated.

Advisor: Patrick

Type:

Coding and evaluation in python, likely using sklearn [4] and grakel [5].

Question:

How well do SVMs and graph kernels still do on large scale problems?

Context: Recent large scale graph level learning problems give you a few million training graphs and a learning problem such as molecule property prediction. In recent years, such tasks are typically solved by large (message passing) graph neural networks (GNN) with millions of parameters [1]. In fact, most top scoring competitors in recent challenges are in fact ensembles of GNNs. These methods require expensive hardware (e.g. 4 NVIDIA A100 for 10k€ a piece) to train in reasonable time.

One argument that is often mentioned as a drawback of SVM/SVR learning is its typical at-least-quadratic scaling behavior with the number of training examples. In particular, kernel methods are assumed to require a full Gram matrix of the input data, which is infeasible for datasets with millions of graphs.

However, multiple graph kernels have been proposed that capture different graph properties that have been shown to achieve good predictive performance on small to medium sized graph datasets see e.g. [3] [4].

Suggested approach:

If ensembling of models is an integral part of recent practical approaches using GNNs, why don’t we allow it for kernel methods, as well?

1. Split the training data in reasonable size chunks (e.g. 2000 graphs each) on which kernel methods are empirically fast
2. Train SVM/SVR on each chunk independently, using multiple graph kernels.
3. Ensemble the trained models using a voting scheme or a simple model such as linear regression to obtain a global model.
4. Optimize the approach such that a leaderboard position can be achieved, where you can write ‘Hardware: My Laptop’

Related work:

[1] https://ogb.stanford.edu/docs/lsc/pcqm4mv2
[2] Nils M. Kriege, Fredrik D. Johansson, Christopher Morris: A survey on graph kernels. Appl. Netw. Sci. 5(1): 6 (2020)
[3] Karsten M. Borgwardt, M. Elisabetta Ghisu, Felipe Llinares-López, Leslie O’Bray, Bastian Rieck: Graph Kernels: State-of-the-Art and Future Challenges. Found. Trends Mach. Learn. 13(5-6) (2020)
[4] https://scikit-learn.org/
[5] https://ysig.github.io/GraKeL/

Advisor: Pascal

Type: Implement and train deep neural networks, use off-the-shelf logical rule learners

Recommended Skills: Experience with deep learning using PyTorch

Task: Zero-One Laws of Graph Neural Network

Context: Message Passing Graph Neural Networks(GNNs) expressivity is known to be bounded above by the one dimensional Weisfeiler-Leman test [1] — an algorithm that iteratively colors graph nodes, with the goal of creating different coloring for two non-isomorphic graphs (although not necessarily succeeding). Hence, if two graphs have the same WL coloring then a GNN will have the same labels for these two graphs. This implies that whatever function a GNN learns can be expressed as a function on 1-WL colors. This equivalence can be further extended to the fragment of first order logic with two variables and counting quantifiers (C2) i.e. two graphs which agree on all C2 properties have the same WL colors, and hence are assigned the same label by a GNN. The research question in this project is “Can we learn/approximate the function represented by a GNN in an explainable logical language?” If successful, such an algorithm can provide explanations for GNNs predictions, and can potentially serve as an explainable alternative to the GNN itself.

Suggested approach: Create synthetic dataset, by fixing an a-priori a logical rule, and labelling randomly generated graphs with that rule. Learn a GNN on those graphs. Now, run WL on the previously generated graphs, which will give you set of colors for your examples, use the GNN generated graph label as the label for the corresponding multiset of WL-colors of the graph. Now, we can use off-the-shelf logical rule learners (like [2]) to learn succinct rules expressing the association between WL colors (as propositions) and GNN labels. Finally, we can check if the learned logical rule is indeed equivalent to the original logical rule.

Related work:
[1] Martin Grohe. The Logic of Graph Neural Networks. 2022. LICS 2022 [2] Ghosh et al. Efficient Learning of Interpretable Classification Rules. JAIR 2022 [3] Azzolin et al. Global Explainability of GNNs via Logic Combination of Learned Concepts. ICLR 2023

Advisor: Sagar and Pascal

Type: Learn theory on symmetries and parameter sharing in Neural Networks. Implementation and experimentation with symmetry-driven parameter sharing in a toy neuro-symbolic model.

Recommended Skills:

• Mathematical maturity
• PyTorch or TensorFlow

Task: This project aims to explore how symmetries in constraints for NeuroSymbolic (NeSy) models can be leveraged to induce parameter sharing. The goal is to reduce the number of independent parameters, enhance generalization, and improving computational efficiency. Students will design and implement neural networks that enforce symmetry-driven parameter sharing[1], focusing on toy tasks such as the MNIST Sum Task [2] and (optionally) extending to more complex domains where symmetries in data can be exploited [3].

Objectives:

1. Understand symmetries in NeSy models: Identify symmetries (e.g., permutation invariance) in NeSy constraints [2,3] and learn how they can simplify neural network architectures [1].
2. Test parameter sharing for NeSy systems: Test a toy case of parameter sharing for a NeSy task using the techniques proposed in [1].

Suggested Approach:

• Understand the principles that model symmetries in the input-output space using parameter sharing in NNs [1].
• Begin with implementing the parameter-sharing strategy for toy NeSy tasks with obvious symmetries, e.g., MNIST Sum [2,3], that has clear permutation symmetry due to commutativity.
• [Optional] Move to more complex logical constraints, develop a module that identifies symmetries in these constraints, and encode them in NNs using parameter sharing.

Related Work:

1. Ravanbakhsh et al. Equivariance Through Parameter-Sharing. ICML 2017.
2. Robin Manhaeve et al. DeepProbLog: Neural Probabilistic Logic Programming. NeurIPS 2018.
3. Daniele et al. Deep Symbolic Learning IJCAI 2023.

Advisor: Sagar Malhotra

Type: Solving a regression task using pretrained language models.

Recommended Skills: Experience with machine learning using Python. Ideally: experience with a deep learning framework (PyTorch, TensorFlow, …).

Task: Use a pretrained language model to encode the DNA of viruses and predict how well they fight a given bacterium.

Context: Phages are viruses that infect bacteria. Hence, they can be used to fight diseases. However, phages only infect specific bacteria, and their effectiveness in fighting the targeted bacteria varies. Since it is very costly to determine the effectiveness in a lab, ML models may help to reduce this effort. In recent years, some LLMs specialized in (phage) DNA have been published. The goal is to investigate whether these models help predict phage effectiveness with only a few tested phages.

Suggested Approach: Use a pretrained language model (e.g. [1]) to embed the phage DNA and use these embeddings to predict the effectiveness with a regressor.

Related Work:

Bin Shao, A Long-context Language Model for Deciphering and Generating Bacteriophage Genomes

Advisor: Christoph Sandrock

Type: Research methods for debiasing (graph-based) models, implement and train GNNs, apply and evaluate debiasing methods

Recommended Skills: Experience with deep learning framework such as PyTorch (Geometric)

Task: Conduct an initial research related to debiasing methods for deep neural networks (and graph-based models) and experiment in translating them to graph-based models.

Context: Bias in ML models is a very important part of ML research which tries to identify and reduce implicit biases such as gender or racial bias. While there has been a plethora of different algorithms and methods to debias deep neural networks (e.g., debiasing Recommender Systems, Large Language Models), there is still plenty of room to explore, especially for graph-based models such as GNNs. With the rising popularity of using GNNs for a variety of different tasks, we want to investige methods suitable to debias those models.

Suggested approach: Find suitable data sets, i.e., data sets with additional meta information such as gender or age that can be represented as a graph (e.g., Knowledge Graphs of recommendation tasks such as MovieLens, LFM2b); implement and train a GNN; evaluate performance of the task and metrics related to bias; apply debiasing methods and evaluate (e.g., adversarial training)

Related work:

• Chen et al., Bias and Debias in Recommender System: A Survey and Future Directions, ACM Transactions on Information Systems, Vol. 41, No. 3
• Fan et al., Debiasing Graph Neural Networks via Learning Disentangled Causal Substructure, NeurIPS 2022
• Ganhör et al., Unlearning Protected User Attributes in Recommendations with Adversarial Training, SIGIR 2022
• RecBole as a framework for Recommender Systems and related data sets [https://recbole.io/]

Advisor: David

Type: Implement and train deep neural networks

Recommended Skills: Experience with deep learning using PyTorch

Task: Extend research on debiasing recommender systems (see Ganhör et al. below) by experimenting with the use of Information Theory

Context: Bias in ML models is a very important part of ML research which tries to identify and reduce implicit biases such as gender or racial bias. While there has been a plethora of different algorithms and methods to debias deep neural networks (e.g., debiasing Recommender Systems, Large Language Models), many of those algorithms require changes and/or additions to the architecture. Using Fisher/Mutual Information as regression term, we hope for a method that is easy to tune and does not require changes to the existing architecture.

Suggested approach: Implement recommender systems based on VAE architectures and different data sets including additional meta information such as gender (e.g. LFM2b, MovieLens), implement and adapt an approximation algorithm for Fisher/Mutual Information (see related work), train and evaluate the influence of the regression term.

Related work:

• Chen et al., Bias and Debias in Recommender System: A Survey and Future Directions, ACM Transactions on Information Systems, Vol. 41, No. 3
• Ganhör et al., Unlearning Protected User Attributes in Recommendations with Adversarial Training, SIGIR 2022
• Adilova et al., Information Plane Analysis for Dropout Neural Networks, ICLR 2023
• RecBole as a framework for Recommender Systems and related data sets [https://recbole.io/]

Advisor: David

Type: Implement and train deep neural networks

Recommended Skills: Experience with deep learning using PyTorch

Task: Extend research on debiasing recommender systems (see Ganhör et al. below) by experimenting with the use of Siamese Neural Networks

Context: Bias in ML models is a very important part of ML research which tries to identify and reduce implicit biases such as gender or racial bias. Recent research has shown good results using a variety of different approaches (e.g., adversarial training). However, many of those approaches are difficult to fine tune and come with a loss in performance. Using a simpler training loop using Siamese Neural Networks, we hope for a method that is easy to tune and preserves the models performance.

Suggested approach: Implement recommender systems based on VAE architectures and different data sets including additional meta information such as gender (e.g. LFM2b, MovieLens), extend the implementation to a Siamese Neural Network architecture,

Related work:

• Ganhör et al., Unlearning Protected User Attributes in Recommendations with Adversarial Training, SIGIR 2022
• Koch et al., Siamese neural networks for one-shot image recognition, ICML deep learning workshop 2015

Advisor: David

Type: Implement and train different algorithms designed to compute disentangled representations (PyTorch)

Recommended Skills: Experience with deep learning using PyTorch

Task: Implement different state-of-the-art algorithms for computing disentangled representations and benchmark them on a variety of different data sets, preferrably (including) data sets outside the Computer Vision domain.

Context: Many state-of-the-art deep learning models in various domains such as Language Models and Recommender Systems thrive on semantincally rich hidden representations. Those representations, however, are most of the time highly entangled, i.e., a change of a single factor such as gender, colour, shape, age, … will change all the dimensions of the representation. Disentangling individual dimensions or vectors from eachother might offer benefits such as better explainability of the predictions, new insights in what the network is learning, controllability over what information flows through the network, …

Suggested approach: Find suitable data sets, i.e., data sets that come with additional meta information such as gender and age (e.g., LFM2b, MovieLens, BIOS); implement and train a variety of different algorithms suitable for the given task (e.g., beta-VAE, FactorVAE); evaluate performance of the task and metrics related to disentanglement

Related work:

• Zhang and Sugiyama, A Category-theoretical Meta-analysis of Definitions of Disentanglement, PMLR 2023
• Eastwood and Williams, A Framework for the Quantitative Evaluation of Disentangled Representations, ICLR 2018
• Kim and Mnih, Disentangling by Factorising, PMLR 2018
• Burgess et al., Understanding disentangling in beta-VAE

Advisor: David

Type: Experimentation with different existing neural network implementations.

Recommended Skills: Knowledge about graphs. Experience with machine learning using Python. Ideally: experience with a deep learning framework (PyTorch, TensorFlow, …).

Task: Analyze different implementation and figure out which design choices lead to strong performance and which do not.

Context: It is known that deep learning models require highly tuned architectural choices to achieve strong performance. However, these choices are often not communicated publicly. In this project, we want to identify which architectural choices are relevant for graph neural networks (GNNs). There exists a variety of expressive GNNs that differ in both their expressivity and other design choices not related to expressivity. In this project we are interested in design choices that are not related to expressivity. For example, architectures might differ in when they feed their internal representation into MLPs/linear layers or where they use batchnorms. The goal of this project is to dissect existing GNN implementations and figure out which parts of the archticture are crucial to performance and whether this can be used to improve existing implementations.

Suggested approach: Select at least 2 expressive GNNs (+ their implementation) from the literature and find some datasets for which they achieve strong results. Analyze existing implementation to figure out which design choices are (not) shared across architectures. Experiment with removing (or adding) these operations from the architectures and measure how this influences downstream task performance.

Related work:

An introduction to GNNs:

• Sanchez-Lengeling, et al., A Gentle Introduction to Graph Neural Networks, Distill 2021
• Daigavane, et al., Understanding Convolutions on Graphs, Distill 2021

Some expressive GNN architectures:

• Bevilacqua et al., Equivariant Subgraph Aggregation Network, ICLR 2022
• Frasca et al., Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries, NeurIPS 2022

These two papers both propose similar GNNs (local 2-GNNs with the same expressivity) but vary strongly in performance:

• Morris et al., Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings, NeurIPS 2022
• Zhang et al., Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness, ICLR 2024

Advisor: Fabian

Type: Experimental

Recommended Skills: Some programming experience, ideally some experience with standard machine learning libraries such as PyTorch.

Task: Reproduce the results of a machine learning paper.

Context: Reproducibility, i.e., obtaining similar output using the same data, is a critical quality in research. Unfortunately, this is often not the case.

Suggested approach: Choose a paper from one of the following venues: NeurIPS, ICML, ICLR, ECML, JMLR, MLJ. Please do no just re-use existing code! (i.e., re-implement in a different programming language/library, or implement methods from multiple papers to perform a comparison.)

Related work:

• NeurIPS reproducibility program (Pineau, Joelle, et al. “Improving reproducibility in machine learning research (a report from the NeurIPS 2019 reproducibility program).” JMLR, 2021)
• quantifying reproducibility (Raff. “A step toward quantifying independently reproducible machine learning research.” NeurIPS 2019)
• https://reproducedpapers.org/

Advisor: Depends on paper

Question: How can we find robust hypotheses that attackers cannot easily manipulate?

Suggested Approach: Approximate Tukey center of hypotheses via iterated Radon points.

Related Works:

• Michael Kamp, Mario Boley, Olana Missura, and Thomas Gärtner. Effective Parallelisation for Machine Learning. Accepted for publication in Advances in Neural Information Processing Systems 30, 2017.
• Ran Gilad-Bachrach, Amir Navot, and Naftali Tishby. Bayes and Tukey Meet at the Center Point. COLT 2004: Learning Theory.

Context: The more (distributed) machine learning algorithms and/or the models learned by them are to be applied in critical applications where lives depend on predictions, the more trustworthy they need to be. For that, (distributed) learning algorithms need to be robust to manipulation of (training) data and communication channels. They also need to guarantee that their models have well-calibrated confidence. The Tukey center is a high-dimensional generalisation of the median and shares similar stability properties that will be exploited in this project.

Question: How can constraints be incorporated into meaningful low-dimensional embeddings of large data sets?

Suggested Approach: Approximate knowledge-constrained PCA via the power method.

Related Works:

• Dino Oglic, Daniel Paurat, and Thomas Gärtner. Interactive Knowledge-Based Kernel PCA. Proceedings of ECML PKDD, 2014. Springer.
• Daniel Paurat and Thomas Gärtner. InVis: A Tool for Interactive Visual Data Analysis. Proceedings of ECML PKDD, 2013. Springer.

Context: Traditionally, embedding techniques focus on finding one fixed embedding, which depends on some technical parameters and emphasises a singular aspects of the data. In contrast, interactive data exploration aims at allowing the user to explore the structure of a dataset by observing a projection dynamically controlled by the user in an intuitive way. Ultimately it provides a way to search and find an embedding, emphasising aspects that the user desires to highlight. Current approaches often do not allow for real-time manipulation of large data sets.

Type: Coding and evaluation in python, likely using pytorch (maybe pytorch geometric)

Question: Can we accurately predict shortest path distances in a large graph in sublinear time and space using a specialized neural network?

Context: Shortest path distance computation is an important primitive in network analysis and practical applications such as suggesting new contacts and content to users of a social network.

Let $G=(V,E)$ be an undirected graph. The shortest path distance $d(s,t)$ can be computed with Dijkstras algorithm in $O(|E|+\log(|V|))$ time for any pair of vertices $s,t \in V$. Running this algorithm in a live system for thousands of queries per second in a very large graph with millions or billions of nodes and edges is intractable. Precomputing and storing the distances of all pairs of vertices, on the other hand is intractable due to its quadratic space requirement. As a result, one tends to work with estimates of $d(s,t)$ that can be computed more efficiently.

One way of arriving at such estimates is to select landmarks or anchors, which are some vertices for which we precompute the shortest path distances to all other vertices in $G$. Let $l \in V$ be such a landmark, then – using the triangle inequality – we can bound \(d(s,t) \leq d(l,s) + d(l,t)\) \(d(s,t) \geq |d(l,s) - d(l,t)|\) for all pairs $s,t \in V$. Note that we only use distances from $l$ to other vertices for these bounds.

We can use the bounds directly to give estimates of the form \(d(s,t) \simeq d(l,s) + d(l,t),\) \(d(s,t) \simeq |d(l,s) - d(l,t)|,\) or \(d(s,t) \simeq \frac{(d(l,s) + d(l,t) - |d(l,s) - d(l,t)|)}{2} + |d(l,s) - d(l,t)|.\) But can we do better?

Suggested approach: We consider the distance estimation problem as a supervised learning task. Given a pair $(s,t)$ of vertices, predict $d(s,t)$. As features, we will use the lower and upper bounds that we obtain from several landmarks, at training time, we can allow a certain number of shortest path distance computations to obtain ground truth distances $d(s,t)$. This problem has already been formulated and addressed, e.g. in [1].

Your tasks include

• literature review of other more recent methods for this learning problem
• implementation of an efficient sampling scheme for ground truth distance computation for training
• implementation of several baselines for distance estimation using landmarks
• evaluation and extension of a novel model architecture for this regression task (proof of concept code exists in pytorch)

Related work: [1] Maria Christoforaki, Torsten Suel: Estimating pairwise distances in large graphs. IEEE BigData 2014: 335-344

Advisor: Pascal

Type: Theory of reinforcement learning (multiple topics)

Recommended skills: Course on reinforcement learning. Strong mathematical/theoretical background.

Task: Show convergence results for algorithms in RL. Show lower bounds on the performance of RL algorithms, i.e. PAC (probably approximately correct) estimates. Based on the PAC estimates, show computational complexity.

Context: In safety critical applications, convergence results and performance estimates are of utmost importance for reliable/safe/robust learning.

Suggested approach: Use fixed-point arguments and concentration inequalities.

Related work: Markus Böck and Clemens Heitzinger. Speedy categorical distributional reinforcement learning and complexity analysis. SIAM Journal on Mathematics of Data Science, 4(2):675–693, 2022. Markus Böck, Julien Malle, Daniel Pasterk, Hrvoje Kukina, Ramin Hasani, andClemens Heitzinger. Superhuman performance on sepsis MIMIC-III data by distributional reinforcement learning. PLOS ONE, 17(11):e0275358/1–18, 2022.

Advisor: Prof. Clemens Heitzinger

Type: Safety-critical applications of reinforcement learning (multiple topics)

Recommended skills: Course on reinforcement learning. Strong programming skills (Python and/or Julia) for applications.

Task: Implement and test modern RL algorithms and devise new algorithms.

Context: In safety critical applications, distributional RL makes it possible to quantify risk. In real-world applications, deep RL makes it possible to treat large state spaces. We have experience in medical applications and want to learn more optimal strategies on recent datasets.

Suggested approach: Distributional RL, deep RL.

Related work: Markus Böck, Julien Malle, Daniel Pasterk, Hrvoje Kukina, Ramin Hasani, and Clemens Heitzinger. Superhuman performance on sepsis MIMIC-III data by distributional reinforcement learning. PLOS ONE, 17(11):e0275358/1–18, 2022. Pierrick Lorang, Horvath Helmut, Tobias Kietreiber, Patrik Zips, Clemens Heitzinger, Matthias Scheutz. Adapting to the ``open world’’: the utility of hybrid hierarchical reinforcement learning and symbolic planning. Proc. 2024 IEEE International Conference on Robotics and Automation (ICRA 2024), 13–17 May 2024, accepted for publication.

Advisor: Prof. Clemens Heitzinger