Graph neural networks (GNNs) have shown promise on combinatorial problems such as Max-Clique, yet it remains unclear what algorithmic principles they actually learn. This paper introduces a concept-driven framework for evaluating and interpreting GNNs on such tasks. We begin with a principled benchmark based on synthetic graphs with known difficulty levels—easy, medium, and hard—derived from theoretical thresholds for planted cliques. Using this setup, we show that GNNs reliably learn a simple yet powerful concept: degree-based ranking. This insight motivates a new decoder, Least-Probable Removal (LPR), which significantly outperforms the common top-k strategy, especially on harder and real-world instances. Our analysis pipeline connects latent representations to classical heuristics, improving both interpretability and performance. Finally, we demonstrate cross-domain generalization to sparse PCA, showing that the same GNN architecture and decoding strategy succeed in recovering sparse principal components, revealing a shared underlying principle across domains.

Explainable AI and model transparency methods primarily focus on classification tasks, identifying salient input features or abstract concepts that are directly tied to the data. In contrast, algorithmic problems such as SAT solving present a deeper challenge: here, meaningful concepts depend not only on the input but also on the model’s evolving internal state; hence, such settings remain underexplored. We study concept learning in an existing model named NeuroSAT , a Graph Neural Network (GNN) trained to predict satisfiability, and uncover internal algorithmic structures, most notably the notion of support , that align with classical SAT heuristics. We then construct a significantly simplified GNN trained via a teacher–student approach: instead of learning from SAT/UNSAT labels, the student is trained to mimic NeuroSAT ’s latent representations—i.e., the concepts themselves—and achieves comparable performance using 91 % fewer parameters. For this simplified architecture, we provide a rigorous theoretical analysis that demonstrates, under certain assumptions on the input distribution and network weights, the emergence of the concept of support and its governing role in the network’s dynamics. This work bridges explainability and algorithmic reasoning by showing that classical SAT-solving strategies emerge naturally in GNNs—and can be used to simplify, compress, and formally analyze their internal dynamics. • We propose a framework for discovering algorithmic concepts learned by GNNs and showcase it on the problem of satisfiability using NeuroSAT by Selsam et al. (2018). • Key abstractions, such as variable assignment confidence-level, emerge spontaneously when the GNN is trained to predict SAT/UNSAT using only single-bit supervision and standard cross-entropy loss. • The discovered concepts enable both theoretical analysis and compression via a compact student network trained on internal representations. • Our insights guide principled modifications to the classical WalkSAT algorithm, yielding new variants that converge faster.

We study the following version of cut sparsification. Given a large edge-weighted network $G$ with $k$ terminal vertices, compress it into a smaller network $H$ with the same terminals, such that every minimum terminal cut in $H$ approximates the corresponding one in $G$, up to a factor $q\geq 1$ that is called the quality. (The case $q=1$ is known also as a mimicking network.) We provide new insights about the structure of minimum terminal cuts, leading to new results for cut sparsifiers of planar graphs. Our first contribution identifies a subset of the minimum terminal cuts, which we call elementary, that generates all the others. Consequently, $H$ is a cut sparsifier if and only if it preserves all the elementary terminal cuts (up to this factor $q$). Our second and main contribution is to refine the known bounds in terms of $\gamma=\gamma(G)$, which is defined as the minimum number of faces that are incident to all the terminals in a planar graph $G$. We prove that the number of elementary terminal cuts is $O((2k/\gamma)^{2\gamma})$ (compared to $O(2^k)$ terminal cuts) and furthermore obtain a mimicking network of size $O(\gamma 2^{2\gamma} k^4)$, which is near-optimal as a function of $\gamma$. Our third contribution is a duality between cut sparsification and distance sparsification for certain planar graphs, when the sparsifier $H$ is required to be a minor of $G$. This duality connects problems that were previously studied separately, implying new results, new proofs of known results, and equivalences between open gaps.

The relationship between the sparsest cut and the maximum concurrent multi-flow in graphs has been studied extensively. For general graphs, the worst-case gap between these two quantities is now settled: When there are k terminal pairs, the flow-cut gap is O(log k), and this is tight. But when topological restrictions are placed on the flow network, the situation is far less clear. In particular, it has been conjectured that the flow-cut gap in planar networks is O(1), while the known bounds place the gap somewhere between 2 (Lee and Raghavendra, 2003) and (Rao, 1999). A seminal result of Okamura and Seymour (1981) shows that when all the terminals of a planar network lie on a single face, the flow-cut gap is exactly 1. This setting can be generalized by considering planar networks where the terminals lie on one of γ > 1 faces in some fixed planar drawing. Lee and Sidiropoulos (2009) proved that the flow-cut gap is bounded by a function of γ, and Chekuri, Shepherd, and Weibel (2013) showed that the gap is at most 3γ. We significantly improve these asymptotics by establishing that the flow-cut gap is O(log γ). This is achieved by showing that the edge-weighted shortest-path metric induced on the terminals admits a stochastic embedding into trees with distortion O(log γ). The latter result is tight, e.g., for a square planar lattice on Θ(γ) vertices. The preceding results refer to the setting of edge-capacitated networks. For vertex-capacitated networks, it can be significantly more challenging to control flow-cut gaps. While there is no exact vertex-capacitated version of the Okamura-Seymour Theorem, an approximate version holds; Lee, Mendel, and Moharrami (2015) showed that the vertex-capacitated flow-cut gap is O(1) on planar networks whose terminals lie on a single face. We prove that the flow-cut gap is O(γ) for vertex-capacitated instances when the terminals lie on at most γ faces. In fact, this result holds in the more general setting of submodular vertex capacities.

Given a large edge-weighted network G with k terminal vertices, we wish to compress it and store, using little memory, the value of the minimum cut (or equivalently, maximum flow) between every bipartition of terminals. One appealing methodology to implement a compression of G is to construct a mimicking network: a small network G′ with the same k terminals, in which the minimum cut value between every bipartition of terminals is the same as in G. This notion was introduced by Hagerup, Katajainen, Nishimura, and Ragde [JCSS 98], who proved that such G′ of size at most always exists. Obviously, by having access to the smaller network G′, certain computations involving cuts can be carried out much more efficiently. We provide several new bounds, which together narrow the previously known gap from doubly-exponential to only singly-exponential, both for planar and for general graphs. Our first and main result is that every k-terminal planar network admits a mimicking network G′ of size O(k222k), which is moreover a minor of G. On the other hand, some planar networks G require |E(G′)| ≥ Ω(k2). For general networks, we show that certain bipartite graphs only admit mimicking networks of size |V(G′)| ≥ 2Ω(k), and moreover, every data structure that stores the minimum cut value between all bipartitions of the terminals must use 2Ω(k) machine words.