Project in Computer Science 1 - Machine Learning Algorithms and Applications

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: 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

Through the emergence of powerful LLMs we have now a utility that allows for automated reading and understanding of a large text corpus. We want to investigate how we can utilize LLMs to extract graph data with context from suitable text sources. We could ask, for example, under which conditions can an LLM extract correct graph representations and what is a suitable grammar for the output. A possible area of application is the extraction of chemical reaction counter-examples, commonly modeled as labeled graphs, from scientific literature. Data on chemical reactions that can not happen in practice is almost nonexistent, however, these types of reactions are well documented in scientific literature.\

Advisor: Klaus Weinbauer ( klaus.weinbauer@tuwien.ac.at )

Context: Recent work has characterized the logical formulas expressible by Graph Neural Networks. Based on this work our recent paper proposes a methodology to distill GNNs into interpretable logically expressed classifiers, called Iterated Decision Trees. This project asks the student to reimplement the Iterated Decision Tree (IDT) distillation algorithm from the KR 2024 paper on logical distillation of GNNs, reproduce a subset of its graph-classification results, and run a focused ablation study on two design choices: the leaf-set clustering procedure and the EMLC% operators used to approximate GNN aggregation. The expected outcome is a reproducible Python/PyTorch implementation that trains a teacher GNN, distills an IDT from intermediate node representations, and evaluates how clustering and operator choices affect accuracy, macro-F1, fidelity to the teacher, runtime, and rule complexity.

Suggested approach:

1. Read the core paper carefully and extract the exact components to implement: the layer-wise IDT learning loop, the per-layer decision-tree learner, the leaf-set construction by hierarchical clustering of leaf predictions, the practical operator restrictions, and the EMLC% extension with relative thresholds.
2. Build the experimental pipeline in Python using PyTorch or PyTorch Geometric for the teacher GNNs and scikit-learn for decision trees and clustering. Use fixed random seeds and configuration files so every experiment is reproducible.
3. Prepare datasets from the synthetic datasets from the paper. If time permits, add BAMultiShapes as an optional extra benchmark.
4. Train at least one teacher GNN from the paper, preferably both GCN+GraphNorm and GIN+GraphNorm. Save intermediate node representations from every message-passing layer and the final graph-level outputs, because these are the supervision targets used by the distillation algorithm.
5. Reimplement the IDT algorithm exactly once in its paper version: for each layer, construct the feature table induced by modal operators and current node predicates, train a decision tree to predict the next GNN layer representation, convert selected leaf sets into new Boolean node features, append them to the feature matrix, and continue iteratively until the final graph-level layer. Start with the practical setting from the paper: use (I), (A), and (I{+}A) in intermediate layers, use (1) in the final layer, cap intermediate tree depth at 2, and prune the final tree.

6. Implement two logical variants of the feature generator: (a) EMLC only, with absolute counting thresholds (S\phi > n), and (b) EMLC%, with both absolute thresholds and relative thresholds (S\phi > p). In code, compute the relative operator by dividing the count of satisfying nodes in (\varepsilon_S(v)) by (

   \varepsilon_S(v)

   ), then compare against a threshold (p\in(0,1)).

7. Run a clustering ablation centered on the leaf-set construction step. Compare at least four variants: the paper’s agglomerative hierarchical clustering over leaf predictions, no clustering beyond singleton leaves, agglomerative clustering with different linkage rules, and a simple threshold-based merge rule on leaf prediction distance. For each variant, measure test accuracy, macro-F1, fidelity to the teacher GNN, number of induced formulas, average tree depth, and total distillation time.
8. Run an operator and aggregator ablation. Compare EMLC against EMLC%, compare modal-operator sets ({I,A}), ({I,A,I{+}A}), and the full set from the paper’s modal language, and compare final-layer settings using only (1) versus allowing additional operators. A good hypothesis to test is that relative operators help more for GCN-like teachers and on synthetic tasks whose labels explicitly depend on proportions.
9. Include at least two baselines: the teacher GNN itself and an IDT(True) model trained directly from the dataset labels instead of GNN representations. If both GCN and GIN are implemented, also compare distillation from the two teachers.
10. Perform a short qualitative analysis of the learned formulas. For a few distilled rules, simplify the corresponding logical conditions, report whether they recover the planted synthetic rule or a simple dataset heuristic, and discuss at least two clear failure cases.
11. Final deliverables should include: the full source code, at least one of the aforementioned ablations EMLC% operators or the clustering algorithms and the main empirical conclusions.

Related work:

• Alexander Pluska, Pascal Welke, Thomas Gärtner, and Sagar Malhotra. Logical Distillation of Graph Neural Networks. KR 2024.
• Pablo Barceló, Egor V. Kostylev, Mikaël Monet, Jorge Pérez, Juan L. Reutter, and Juan Pablo Silva. The Logical Expressiveness of Graph Neural Networks. ICLR 2020.

Advisor: Sagar

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: Theory + lightweight implementation of WL tests and a 2-WL-inspired GNN

Question: Which graph structures are indistinguishable for 1-WL (and standard message-passing GNNs), and how much do we gain with 2-WL / 2-GNN on graph classification?

Suggested Approach: Standard message-passing GNNs match the discriminative power of 1-WL, hence they inherit blind spots on highly symmetric graphs. In this project, you will implement both 1-WL and 2-WL color refinement algorithms (operating on nodes and node pairs, respectively) and build a failure suite of graphs where 1-WL cannot distinguish structures but 2-WL can. You will then implement a simple 2-GNN model inspired by 2-WL logic and benchmark it against GIN and GCN on graph classification tasks, comparing expressivity and scaling behavior on datasets like CSL (where 1-WL provably fails) and a real-world benchmark.

Related Work:

• Christopher Morris et al. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks.
• Christopher Morris et al. Weisfeiler and Leman go Machine Learning: The Story so far (survey).
• Towards Better Evaluation of GNN Expressiveness with BREC Dataset.

Advisor: Flaviano

Type: Implementing and benchmarking two WL-inspired GNN families (Loopy-WL vs PAIN) in PyTorch (Geometric)

Question: How do Loopy-WL (r-ℓMPNN) and Path-WL (PAIN / d-PATH-WL) compare in practical expressivity on the BREC benchmark, and do the empirical results match the theoretical separations suggested by the papers?

Suggested Approach: Implement the two models proposed in recent works and evaluate their expressivity on the BREC benchmark:

• Weisfeiler and Leman Go Loopy (r-ℓWL / r-ℓMPNN): Targets enhanced counting and discrimination via “loopy” refinements
• Path-WL (d-PATH-WL / PAIN): Aggregates information over paths up to length ℓ (optionally with distance tags) and is provably stronger than 1-WL for ℓ>1

Evaluate both models on BREC (pairwise non-isomorphic graphs designed for fine-grained expressivity testing) using a consistent training protocol, reporting success rate/accuracy across BREC categories and computing memory cost. Optionally, theoretically analyze how each model’s hyperparameters relate to each other and which BREC category each method should handle better.

Related Work:

• Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Neural Networks. NeurIPS 2024.
• Caterina Graziani et al. The Expressive Power of Path-Based Graph Neural Networks.International Conference on Machine Learning, 2024.
• Towards Better Evaluation of GNN Expressiveness with BREC Dataset.

Advisor: Flaviano

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: Implementing topology informed GNN with Pythorch (Geometric)

Question: Can we leverage information arising from higher-order interaction for social networks predicion tasks?

Suggested Approach: The concept of filtration (of a set) has been employed in the context of graph learning to enrich message passing with topological information arising from higher order interactions in various ways. In this project, we aim to combine (and eventually extend) existing approaches and evaluate their effectiveness on prediction tasks over social network datasets.

Related Work:

• Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference on Learning Representations, 2022.
• Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. International Conference on Machine Learning, 2019.
• Davide Buffelli, Farzin Soleymani, and Bastian Rieck. Cliqueph: Higher-order information for graph neural networks through persistent homology on clique graphs. arXiv preprint arXiv, 2024.

Advisor: Flaviano