Approximate nearest neighbor search (ANNS) is a fundamental task in data science with widespread applications. In this talk, we present several techniques for scaling ANNS to large datasets. First, we introduce a new algorithm for building ANNS indices that achieves an order of magnitude speedup over earlier approaches. Furthermore, we present a general technique for decomposing a large ANNS problem into a collection of smaller problems, enabling ANNS on datasets that exceed single-machine capacity.

Modeling complex, multi-way interactions with hypergraphs presents a fundamental tradeoff between mathematical expressivity and computational scalability. In this talk, we demonstrate how implicit approaches and randomized algorithms serve as critical tools for mitigating this bottleneck. Specifically, we highlight recurring challenges in scaling hypergraph matrix and tensor methods for large datasets. For hypergraph matrices and Laplacians, we identify prohibitive density as a primary barrier to downstream analysis. We show how random sampling accurately predicts this density, and how subsequent implicit approaches enable efficient hypergraph matrix sparsification, construction, and spectral analysis. Moving to hypergraph tensors, we address the dual challenges of hyperedge nonuniformity and high-dimensionality. We introduce an implicit algorithm for executing a core primitive — tensor-times-same-vector (TTSV) — on a nonuniform hypergraph adjacency tensor without ever requiring its explicit formation. Through concrete examples, we illustrate how these scalable tensor methods capture structural nuances that remain invisible to matrix-based approaches. We will conclude with a discussion of open problems and future directions.

Data that records groups of interacting entities, or groups of entities that share a common property, especially over time, is quite common in a variety of domains. These data can be modeled mathematically as a hypergraph with vertices representing the entities and hyperedges representing the groups. Understanding how the hypergraphs evolve over time, or how multiple groupings (hypergraphs) on the same entities differ, can be crucial to identifying trends and anomalies. For example, in computer networks each user has its own pattern of how they use various programs and files which can be summarized in a user-centric hypergraph. Tracking the structural difference between multiple user's behaviors can group users into categories, help spot anomalous users, which might be malicious, or help identify when two usernames correspond to the same person (i.e., entity disambiguation). One method of tracking changes in hypergraph structure is hypergraph edit distance, a generalization of the well-known graph edit distance. Both are known to be NP-hard to compute exactly but there are approximation algorithms or special cases where computation is possible. This talk will introduce two formulations of hypergraph edit distance, survey some theoretical results on how they relate to graph edit distance, and discuss a hypergraph neural network approach to approximating hypergraph edit distance. We then show applications to cyber anomaly detection and author disambiguation. This work is a collaboration with Audun Myers and Cliff Joslyn.

The rich spectral information of the graph Laplacian has been instrumental in graph theory, machine learning, and graph signal processing for a diverse range of applications. Arguably this is due to the fact that the Laplacian spectrum encodes important topological and combinatorial properties. In this talk we will argue that these ideas can be naturally generalised to discrete Hodge-Laplacian matrices, whose eigenvectors and eigenvalues provide additional information. Specifically, the eigenvectors and eigenvectors of the Hodge-Laplacians provide us with vectorial representations that encode topological information such as homology. We illustrate how these insights can be used in a range of applications, including clustering or the signal processing of flows on discrete spaces.

Decision trees are powerful supervised machine learning tools for classification and regression that attract many academic researchers and industry professionals. In particular, decision trees provide interpretability, which is often preferred over other higher-accuracy methods that are relatively uninterpretable. In this talk, we explore discrete optimization techniques to derive classification trees. In particular, we consider binary classification trees where we introduce mixed-integer linear optimization (MILO) formulations that offer theoretical improvements on the strongest flow-based MILO formulation currently in the literature and conduct experiments on publicly available data sets to demonstrate our models’ ability to scale, strength against traditional branch-and-bound approaches, and robustness in out-of-sample test performance.

Lack of trust is a major barrier for the adoption of AI in national-security applications. We introduce a way to use learning-augmented algorithms to provide some provable confidence in the quality of AI used for real-time combinatorial optimization. Our exemplar is monitoring the performance of an AI-based (re-)scheduler orchestrating satellites to track fast-moving maneuverable objects.

Today’s scientific discovery increasingly relies on the ability to analyze datasets of unprecedented scale and complexity. In genomics, studies that once examined a few thousand individuals now aim to analyze millions. Computing systems capable of handling this scale exist, but using them effectively requires expertise in parallel programming and modern accelerator architectures, which most scientists lack, especially since these applications are often irregular, memory intensive, and difficult to parallelize. As a result, important scientific questions remain unanswered because computations would take weeks or months to complete on single-processor CPU architectures. This highlights the need for an abstraction layer that provides programming flexibility and productivity while ensuring high system performance on modern accelerator architectures. In this talk, I will discuss how sparse linear algebra can deliver performance and scalability on modern accelerators and large-scale systems while maintaining productivity for emerging data-intensive scientific challenges. In particular, I will draw examples from data analysis and computational biology, such as clustering and population genetics.

Graph Neural Networks (GNNs) now power high-stakes applications from drug discovery to fraud detection, making it essential to understand why a model makes a given prediction. Among the many GNN explanation techniques proposed, methods based on Shapley values stand out for their theoretical rigor and consistently superior fidelity. Their adoption, however, has been limited by cost: Shapley values are exponential to compute exactly, and even sampling-based approximations require hundreds of thousands of GNN inferences, leaving Shapley-based explainers an order of magnitude slower than competing methods. In this talk, I will present two systems that close this gap. GNNShap (WWW 2024) redesigns Shapley sampling across all coalition sizes, parallelizes sampling on a single GPU, and batches GNN inference to deliver both higher fidelity and faster runtimes than prior work. DistShap (VLDB 2026) extends these ideas to distributed memory by partitioning subgraph sampling across processes, running GNN inference in parallel across GPUs, and solving the underlying weighted least-squares problem in a distributed fashion. Together, these results show that the Shapley value—long established as a principled tool in game theory and a workhorse of modern ML explainability—can now extend its success to graph neural networks at scale.

Metric Forest Completion is a learning augmented algorithm for metric minimum spanning trees. This talk will cover the basics of the algorithm as well as work being done towards achieving a fast distributed memory parallel version of the algorithm.

A fundamental goal of genetics is to understand how variation in biological sequences gives rise to differences in measurable characteristics called phenotypes. The mapping from genotype (DNA, RNA or protein sequence) to phenotype can be difficult to model and interpret because the space of possible sequences is enormous and combinations of mutations interact in complex ways. We describe how to use Gaussian process regression to learn genotype-phenotype maps, which to a mathematician are real-valued functions over a discrete space of sequences with a fixed length and alphabet. Using a kernel trick, we derive tractable analytic expressions for a large class of statistics of genotype-phenotype maps and their uncertainties. We leverage this kernel trick to design algorithms that (i) identify and describe distinct regions of sequence space that are well-approximated by different simple functions and (ii) navigate to regions of sequence space with predicted high-fitness. Our methods form a practical toolkit for extracting biological insight from the rapidly growing collection of high-throughput genotype-phenotype datasets.

Many real-world graphs support multiple predictive tasks over the same underlying structure, creating an opportunity to reuse supervision across node classification (NC) and link prediction (LP). However, existing evaluations often rely on incompatible splits, observed-graph assumptions, and negative sampling rules, making conclusions about same-graph cross-task transfer unreliable. We formalize same-graph NC–LP transfer and propose a leakage-free protocol that fixes node and edge splits, uses a shared message-passing graph that excludes evaluated edges, and employs fixed negatives for LP. Across three backbones (GCN, GraphSAGE, GPS), we find transfer is strongly directional and predictable: NC -> LP is consistently beneficial on homophilic graphs, while LP -> NC is fragile and can even degrade accuracy under naive representation reuse. LP -> NC becomes reliably positive mainly in a structure-dominant regime where LP is easy but NC is unsaturated, suggesting LP acts as structural pretraining. Finally, we introduce CoTask Score (CTS) to summarize joint NC+LP utility when a shared encoder must serve both tasks, and show that simple dataset statistics, especially homophily, can guide mechanism choice and help avoid negative transfer.

Probabilistic graphs are graphs in which each edge fails independently with a certain probability. Equivalently, each edge is only ""active"" with a certain probability. These objects are a useful model of randomized propagation in graphs, capturing so-called ""independent cascades"" of information in social networks, the spread of disease in epidemiology, and random communication loss in the study of network robustness. We study edge augmentation, or link recommendation, in this setting. Informally, the goal is to add a budgeted number of (probabilistic) edges to a probabilistic graph, such that the ability of information to spread throughout the network is improved. We design approximation algorithms and complementary lower bounds. Our arguments combine classic ideas from the edge augmentation literature with new structural insights and powerful analytical tools from percolation theory. Based on joint work with Bhaskara, Jain, Mazumder, Sullivan, and Yalamanchili.

In a dynamic graph problem, the vertices of the graph G are known ahead of time and the edges are revealed over time. The goal is to efficiently maintain some property (such as connectivity or shortest path) of the graph throughout. Machine-learned predictions about future inserts in such problems help interpolate smoothly between the fully online and fully offline settings. This lightning talk will mention recent results that use a technique (recursive decomposition) to design learning-augmented algorithms for faster graph algorithms for dynamic shortest paths and strong connectivity.

Reconfigurable optical circuit switches revolutionize datacenter networks by allowing to adjust the physical topology in a dynamic and demand-aware manner. These switches directly match currently frequently communicating racks, reducing bandwidth tax and hence improving throughput. The underlying optimization problem is essentially the NP-hard Weighted 𝑘-Disjoint Matchings problem. Existing efficient solutions to this problem require a centralized controller, which constitutes a scalability bottleneck. This paper introduces the first distributed approach. Our main contributions are four new algorithms and a new approach to trade solution quality for running time via a parameter 𝜀 ∈ [0, 1]. Our best algorithm guarantees a 1/3 -approximation. We provide an extensive empirical evaluation on 87 real-world and synthetic workloads with billions of edges showing scalability and a speedup over state- of-art algorithms up to 1-2 orders of magnitude on most instances while retaining high-quality solutions.

HDBSCAN (Hierarchical Density-Based Spatial Clustering of Applications with Noise) is a clustering algorithm suitable for arbitrary distance metrics and capable of identify clusters of varying density with few parameters to tune. We present a novel, parallel, distributed-memory method that generalizes HDBSCAN. We start with the PANDORA method by Sao, Prokopenko, and Lebrun-Grandie to construct the single-linkage dendrogram in parallel. We then develop a novel, distributed method to extract the cluster hierarchy and optimal flat clusters from the dendrogram. On the Deep1B data set consisting of 1 billion points, we find a 10x speed up moving from the serial HDBSCAN method on 1 process to our method on 224 processes distributed across 4 nodes compute nodes on LLNL's Dane cluster.

Graph retrieval-augmented generation (GraphRAG) provides deep domain-specific reasoning over complex systems through knowledge-graph representations, capturing higher-order relationships missed by traditional RAG systems. Despite the depth, these systems fall short in real-time scenarios, where large-scale data workloads coupled with static, sequential processing methods bottleneck performance. To address this, we propose a streaming GraphRAG workflow built on dynamic process knowledge graphs and live telemetry for edge agentic decision support in cybersecurity applications. Towards this, we augment GraphRAG indexing and community detection with multithreaded data chunking and graph sketching, respectively, for improved performance and memory efficiency. Preliminary evaluations demonstrate the viability of this dynamic approach over traditional pipelines, establishing a scalable framework for real-world agentic deployment.

Simple neuron models are powerful: networks built out of perceptrons, model neurons which sum up their input and produce an output when input is above threshold, are the building blocks for modern artificial intelligence. However, biological neurons are more complicated than perceptrons. In this talk, we take one example of this complexity -- the presence of synaptic nonlinearities, combined with multiple synapses between a pair of neurons -- and use discrete math to explore how it increases the computational power of a neuron.

We consider a generalization of the densest subhypergraph problem where nonnegative rewards are given for including partial hyperedges in a dense subhypergraph. Prior work addressed this problem only in cases where reward functions are convex, in which case the problem is poly-time solvable. We consider a broader setting where rewards are monotonic but otherwise arbitrary. We first prove hardness results for a wide class of non-convex rewards, then design a $1/k$-approximation by projecting to the nearest set of convex rewards, where $k$ is the maximum hyperedge size. We also design another $1/k$-approximation using a faster peeling algorithm, which (somewhat surprisingly) differs from the standard greedy peeling algorithm used to approximate other variants of the densest subgraph problem. We then develop approximation algorithms for constrained variants of the problem, including variants with a minimum size requirement and variants that incorporate fairness constraints. Our results include an empirical analysis of our algorithm across several real-world hypergraphs along with a case study on the NYC rapid-transit network that demonstrates an application of a constrained variant of the problem.

We develop an algorithm that finds the consensus among many different clustering solutions of a graph. We formulate the problem as a median set partitioning problem and propose a greedy optimization technique. Unlike other approaches that find median set partitions, our algorithm takes graph structure into account and finds a comparable quality solution much faster than the other approaches. For graphs with known communities, our consensus partition captures the actual community structure more accurately than alternative approaches. To make it applicable to large graphs, we remove sequential dependencies from our algorithm and design a parallel algorithm. Our parallel algorithm achieves 35x speedup when utilizing 64 processing cores for large real-world graphs representing mass cytometry data from single-cell experiments.

ParEVO moves from evaluation to synthesis, introducing an agentic evolutionary framework for generating high-performance parallel algorithms over irregular data structures such as sparse graphs. It combines curated instruction data, specialized models, and iterative feedback from performance tests to optimize generated programs. LLMs help us shift from static benchmark performance toward expert-grounded feedback loops: systems that can be rigorously judged, corrected using domain-specific signals, and improved in settings where correctness, reasoning, and efficiency are all non-negotiable.

Semi-supervised learning aims to infer class labels using only a small fraction of labeled data. In graph-based semi-supervised learning, this is typically achieved through label propagation to predict labels of unlabeled nodes. However, in real-world applications, new data often arrives in batches, and stale data often becomes irrelevant. Each time a new batch appears, reapplying the traditional label propagation algorithm to recompute all labels is redundant, computationally intensive, and inefficient. In this lightning talk, I will present a novel GPU-centric Dynamic Batched Parallel Label Propagation algorithm that performs only the necessary updates, propagating changes to the relevant subgraph without requiring full recalculation. By exploiting GPU architectural optimizations, our algorithm achieves on average 13x and up to 102x speedups on large-scale datasets compared to state-of-the-art approaches. This talk is based on our recent ACM ICS accepted paper.

While automatic differentiation itself is used to compute derivative matrices and vectors used primarily for solving continuous optimization problems in scientific computing and machine learning, the implementation and application of automatic differentiation algorithms involves many combinatorial problems. We survey some of these problems.

An important characteristic of temporal graphs is how the directed arrow of time influences their causal topology, i.e., which nodes can possibly influence each other causally via time-respecting paths. The resulting patterns are often neglected by temporal graph neural networks (TGNNs). To formally analyze the expressive power of TGNNs, we lack a generalization of graph isomorphism to temporal graphs that captures their causal topology. Addressing this gap, we introduce consistent event graph isomorphism, which utilizes a time-unfolded representation of time-respecting paths in temporal graphs. We compare this definition with existing notions of temporal graph isomorphisms and show that its expressive power is equivalent to a temporal generalization of the Weisfeiler-Leman graph isomorphism test. Building on this theoretical foundation, we derive a message passing scheme for TGNNs that operates on the event graph representation of temporal graphs and experimentally evaluate it in a temporal graph classification setting.

The maximum independent set problem can be solved exactly on many large sparse graphs in practice by applying data reductions to shrink the input to a smaller equivalent instance. However, when an instance is too large to be solved exactly, we often turn to a combination of fast (ideally, linear time) data reductions and heuristic search to produce high quality solution quickly in practice. In this talk we present a new generalized data reduction that subsumes many existing vertex removal reductions, and can be applied in linear time. However, while many traditional reductions remove a limited number of vertices, the quality of this reduction depends on the structure of a given independent set and clique cover. We formulate this data reduction as an optimization problem, enabling us to compute the maximum reduction possible with an ideal independent set and clique cover, and we empirically test existing linear- and near-linear time heuristics to see how effective they are at enabling data reduction in practice. Of particular interest for future work is using more advanced heuristic methods (including evolutionary algorithms or GNNs) to enable efficient data reduction that is close to optimal in practice. Such data reductions could enable the exact solving of larger instances or finding higher quality solutions faster. (This is joint work with Hank Elsesser and Garrett Rhoads.)

​A team of agents moves around a graph by stepping vertex-to-vertex along its edges. They can only communicate when they are on the same vertex at the same time. The adversary removes different edges at every time step. How many agents are needed to defeat the adversary on which types of graphs? Intuitively this seems related to edge connectivity, but it is provably not! I’ll discuss a few approaches and results, and describe open questions.

Mathematics is as much of a human language as English, French, or Hindi. While the world races towards human language programming of computing systems, the mathematically inclined have a profound advantage. Fundamentally computers are big calculators. More recently the improvements in computers have been concentrated around the domain of mixed-precision matrix mathematics, enabling those literate in such mathematics to instruct computers directly in the language of linear algebra. Recent developments in sparse, hypersparse, and associative (token) array mathematics enables arbitrary programs to be expressed using small amounts of mathematics to produce programs with outstanding horizontal scaling (across compute nodes), vertical scaling (within a compute node), and longitudinal scaling (across hardware generations). In the future AI will start producing such codes to reduce the scaling, security, and maintenance challenges associated with the voluminous code bases that are now emerging from AI programming systems.

Training data is central to machine learning, yet it remains challenging to efficiently appraise dataset value for a learning process. Neural scaling laws appraise data through dataset size, while the recently proposed Vendi Score uses Von Neumann (quantum) entropy to measure dataset value. In this paper, we show both that common neural-scaling-law objectives and the Vendi Score are submodular. We further show that the Vendi Score is a special case of a broader class of submodular objectives that we call matrix spectral functions. This class also includes determinantal (DPP) objectives, which are known to be log-submodular, as well as many others, including neural-scaling-law-inspired matrix spectral hybrids. We also introduce weakly matrix monotone functions and show how they lead to weakly submodular matrix spectral functions, yielding a broad family of practical objectives for data selection and appraisal. A key challenge is scale. We thus develop secular-equation-based updates that avoid repeated eigendecompositions during greedy optimization, reducing marginal-gain evaluation for m-dimensional embeddings by an O(m) factor relative to oracle queries. In our implementation, this yields an average empirical speedup of ≈ 35,000×, making direct optimization of the Vendi Score feasible on ImageNet-1K-scale datasets. Thus enabled, we compare how well several objectives predict the value of training subsets for heldout test performance under fixed-size, class-balanced, and fixed training-budget regimes, including the Vendi Score, DPPs, facility location, and three new matrix spectral variants. Across multiple datasets, facility location performs the best. Direct optimization also reveals that, while the Vendi Score is predictive over moderate score ranges, pushing the objective to higher values can make it a poor downstream performance proxy. Other matrix spectral variants, including weakly submodular ones, perform better, though still below facility location. We also find that uniformly at random fixed-size subsets, both unconstrained and class-balanced, are remarkably concentrated in both appraisal scores and held-out performance, indicating that random sampling fails to expose much variety. Finally, we show that size, class balance, and training budget do not alone determine data value: even when controlling for these factors, performance ranges smoothly from good to bad.

We highlight three recent examples where the toolbox of computational discrete algorithms was crucial to the design and efficient implementation of our methods for inference in different settings involving protein-protein or genetic interaction networks. First we describe Approximate IsoRank, an approximation of the famous IsoRank method for global alignment of two protein-protein interaction networks across species. Our new IsoRank approximation exploits the mathematical properties of IsoRank’s linear system to solve the problem in quadratic time with respect to the maximum size of the two PPI networks. In experiments on synthetic and real PPI networks with various proposed metrics to measure alignment quality, we find the results of our approximate IsoRank are nearly as accurate as the original IsoRank. And for functional enrichment-based measures of global network alignment quality we find our approximation performs better than exact IsoRank, doubtless because it is more robust to the noise of missing or incorrect edges. Second, we describe our new ILP-based method named GIDEON to search for a diverse collection of Between-Pathway Models (BPMs) in the Yeast genetic interaction network, where the genetic interaction network is a weighted signed graph representation of a series of high-throughput pairwise epistasis experiments. More specifically: the vertices of the genetic interaction network represent non-essential genes, and two genes are connected with a positive (or negative) weighted edge when the yeast strain of the double knockout is more healthy (or sicker) than would be expected by examining the sickness of its component single knockout strains. In this network, BPMs are a graph motif signature that indicates potential compensatory pathways. We discuss both the novel ILP formulation as well as potential biological applications. Finally, D-SCRIPT is a powerful lightweight deep learning method designed for high-throughput inference of protein–protein interactions (PPIs) using a pre-trained protein language model, but it is expensive in time and memory to infer all PPIs for network-/proteome-level analyses. We introduce D-SCRIPT with blocked multi-GPU parallel inference, which substantially reduces memory usage across tasks and computational systems ( for a representative large proteome) and enables multi-GPU parallelism.

The graph coloring problem asks for an assignment of the minimum number of distinct colors to vertices in an undirected graph with the constraint that no pair of adjacent vertices share the same color. The problem is a thoroughly studied NP-hard combinatorial problem with several real-world applications. As such, a number of greedy heuristics have been suggested that strike a good balance between coloring quality, execution time, and also parallel scalability. In this work, we introduce a graph neural network (GNN) based ordering heuristic and demonstrate that it outperforms existing greedy ordering heuristics both on quality and performance. Previous results have demonstrated that GNNs can produce high-quality colorings but at the expense of excessive running time. The current paper is the first that brings the execution time down to compete with existing greedy heuristics. Our GNN model is trained using both supervised and unsupervised techniques. The experimental results show that a 2-layer GNN model can achieve execution times between the largest degree first (LF) and smallest degree last (SL) ordering heuristics while outperforming both on coloring quality. Increasing the number of layers improves the coloring quality further, and it is only at four layers that SL becomes faster than the GNN. Finally, our GNN-based coloring heuristic achieves superior scaling in the parallel setting compared to both SL and LF.

Traditional exact solvers and purely end-to-end machine learning (ML) models often face steep bottlenecks in scalability, data efficiency, and generalization. We present a unifying hybrid ML–algorithmic framework rooted in the Learning to Prune (LTP) paradigm. Instead of relying on black-box networks to output solutions directly, our framework leverages lightweight, highly interpretable ML models to predict and prune components by fixing variables, thereby isolating the difficult core of a problem instance to be processed by the state-of-the-art exact and heuristic solvers. We showcase the versatility and theoretical grounding of this framework across three distinct problem domains: k-median and Facility Location: We illustrate how quantities derived from classical approximation algorithms can serve as highly effective features for the k-median, facility location, and set cover problems. Remarkably, these features generalize across problem variants, allowing classifiers to identify the core of the problem while training on minimal data. Routing and Matheuristics: We extend LTP to complex electric vehicle routing problems with non-linear charging functions. We demonstrate how the framework operates as a variable sparsification tool integrated within an exact branch-and-bound matheuristic, even when exact training labels are unavailable. Independent Set and Vertex Cover Variants: We demonstrate how adapting the multiplicative weights method yields fast, high-quality surrogate features for problems like maximum independent set and minimum vertex cover variants. Collectively, these results highlight a powerful blueprint for the future of discrete algorithms: combining domain-specific algorithmic insights with data-driven pruning to achieve drastic runtime reductions while maintaining robust solution quality.

Classical graph algorithms and machine learning on graphs are often studied in isolation, yet each has much to offer the other. This talk explores the interplay from three angles. First, it shows how Graph Neural Networks can accelerate exact data reduction rules for the Maximum Weight Independent Set problem, allowing expensive reductions to be applied selectively and at scale, and yielding state-of-the-art solver performance on real-world instances. Second, the relationship is turned around: streaming graph partitioning is used to speed up distributed GNN training itself, balancing both vertices and edges to reduce communication overhead across workers. Finally, the talk presents a systematic experimental survey of modularity-based community detection, jointly evaluating classical heuristic, multilevel, metaheuristic, and exact methods alongside recent neural approaches within a unified benchmarking framework. Together, these results highlight where learning-based methods complement well-engineered combinatorial algorithms, where they fall short, and where the most promising opportunities for hybrid approaches lie.

Graph learning is an umbrella term for machine learning methods applied to graph-structured data, including tasks such as graph- and node-level prediction as well as link prediction. In recent years, graph neural networks, and in particular message-passing neural networks (MPNNs), have emerged as the dominant research paradigm in this area. We provide an introduction to MPNNs and the relationship between their expressive power and the classical graph isomorphism heuristic known as color refinement or the Weisfeiler-Leman method. We discuss the main architectural components of MPNNs, including sparse neighborhood aggregation and dense feature transformations, as well as their realization on modern hardware architectures. Building on these foundations, we present recent results on quantization and pruning methods for MPNNs, connecting the lottery ticket hypothesis to sparse subnetworks in MPNNs. Our findings suggest that expressive power is a key factor in identifying randomly initialized subnetworks that achieve performance comparable to their dense counterparts while reducing computational and memory requirements.

Graph Neural Networks (GNNs) are now a fundamental building block in many systems, but how can we trust them? We begin by discussing conformal prediction, a framework that equips unreliable black-box models with strong statistical guarantees and quantifies their uncertainty. We then extend these guarantees to worst-case adversarial settings, addressing robustness. Finally, we look inside the black box to identify how nodes shape the model and its predictions.