Generative modeling of graphs with spatial structure is essential across many applications from computer graphics to spatial genomics. Recent flow-based generative models have achieved impressive results by gradually adding and then learning to remove noise from these graphs. Existing models, however, use graph neural network architectures that are independent of the noise level, limiting their expressiveness. To address this issue, we introduce *Noise-Conditioned Graph Networks* (NCGNs), a class of graph neural networks that dynamically modify their architecture according to the noise level during generation. Our theoretical and empirical analysis reveals that as noise increases, (1) graphs require information from increasingly distant neighbors and (2) graphs can be effectively represented at lower resolutions. Based on these insights, we develop Dynamic Message Passing (DMP), a specific instantiation of NCGNs that adapts both the range and resolution of message passing to the noise level. DMP consistently outperforms noise independent architectures on a variety of domains including $3$D point clouds, spatiotemporal transcriptomics, and images.

Effective resistance is a distance between vertices of a graph that is both theoretically interesting and useful in applications. We study a variant of effective resistance called the biharmonic distance. While the effective resistance measures how well-connected two vertices are, we prove several theoretical results supporting the idea that the biharmonic distance measures how important an edge is to the global topology of the graph. Our theoretical results connect the biharmonic distance to well-known measures of connectivity of a graph like its total resistance and sparsity. Based on these results, we introduce two clustering algorithms using the biharmonic distance. Finally, we introduce a further generalization of the biharmonic distance that we call the $k$-harmonic distance. We empirically study the utility of biharmonic and $k$-harmonic distance for edge centrality and graph clustering.

The distinguishing power of graph transformers is tied to the choice of positional encoding: features used to augment the base transformer with information about the graph. There are two primary types of positional encoding: absolute positional encodings (APEs) and relative positional encodings (RPEs). APEs assign features to each node and are given as input to the transformer. RPEs instead assign a feature to each pair of nodes, e.g., shortest-path distance, and are used to augment the attention block. A priori, it is unclear which method is better for maximizing the power of the resulting graph transformer. In this paper, we aim to understand the relationship between these different types of positional encodings. Interestingly, we show that graph transformers using APEs and RPEs are equivalent in their ability to distinguish non-isomorphic graphs. In particular, we demonstrate how to interchange APEs and RPEs while maintaining their distinguishing power in terms of graph transformers. However, in the case of graphs with node features, we show that RPEs may have an advantage over APEs. Based on our theoretical results, we provide a study of different APEs and RPEs—including the shortest-path and resistance distance and the recently introduced stable and expressive positional encoding (SPE)—and compare their distinguishing power in terms of transformers. We believe our work will help navigate the vast number of positional encoding choices and provide guidance on the future design of positional encodings for graph transformers.

Message passing graph neural networks (GNNs) are a popular learning architectures for graph-structured data. However, one problem GNNs experience is oversquashing, where a GNN has difficulty sending information between distant nodes. Understanding and mitigating oversquashing has recently received significant attention from the research community. In this paper, we continue this line of work by analyzing oversquashing through the lens of the *effective resistance* between nodes in the input graph. Effective resistance intuitively captures the ``strength'' of connection between two nodes by paths in the graph, and has a rich literature spanning many areas of graph theory. We propose to use *total effective resistance* as a bound of the total amount of oversquashing in a graph and provide theoretical justification for its use. We further develop an algorithm to identify edges to be added to an input graph to minimize the total effective resistance, thereby alleviating oversquashing. We provide empirical evidence of the effectiveness of our total effective resistance based rewiring strategies for improving the performance of GNNs.

Given a simplicial complex with $n$ simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth $k$ of the Hasse diagram that run in $2^{O(k \log k)}n^{O(1)}$ time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

We describe a nearly-linear time algorithm to solve the linear system $L_1x = b$ parameterized by the first Betti number of the complex, where $L_1$ is the 1-Laplacian of a simplicial complex $K$ that is a subcomplex of a collapsible complex $X$ linearly embedded in $\mathbb{R}^{3}$. Our algorithm generalizes the work of Black et al.~[SODA2022] that solved the same problem but required that $K$ have trivial first homology. Our algorithm works for complexes $K$ with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of $K$ in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex $K$ embedded in $\mathbb{R}^{3}$, as $K$ can always be expanded to a collapsible embedded complex of quadratic complexity.

We consider a variety of topology problems on a d-dimensional simplicial complex K given that K ∪ X for X a collapsible simplicial complex embedded in ℝd+1 with known collapsing sequence. Our first result is a solver for the linear system L1x = b, where L1 is the 1-Laplacian of a simplicial complex K with dimH1(K) = 0 and K ∪ X for X a collapsible simplicial complex embedded in ℝ3 with a known collapsing sequence. Our algorithm runs in O(n log2 (nκ/∊)) time, where n is the total number of vertices, edges, and triangles in X, κ is the largest condition number of the two parts of the Laplacian, and ∊ quantifies the approximation quality. This result is a generalization of Cohen et al. [SODA 2014]. The new technical piece of our Laplacian solver, in addition to the machinery described by Cohen et al., is an algorithm to compute a bounding chain of a 1-cycle within k. In addition, we describe faster algorithms for testing null-homology of (d–1)-cycles and null-cohomology of d-cocycles. Our algorithm runs in O(nd) time, where nd is the number of d-simplices in X. Finally, we describe an algorithm to compute a (d–1)-cohomology basis from a given (d–1)-homology basis for a d-simplicial complex K in O(βd–1nd) time; βd–1 is the rank of the (d–1)st homology group of k. In particular, we can obtain a cohomology basis for subcomplexes of a collapsible complex X embedded in ℝ3 in O(nd log nd + βd–1 n) time using a homology basis computed by the algorithm of Dey [SODA 2019]. For all of the problems above, if K ∪ ℝ3 and the collapsible supercomplex X is not provided, we can expand K into a convex ball of possibly quadratic complexity, which is known to be collapsible, resulting in nearly quadratic time algorithms.

This paper clarifies a recurrent structural confusion in advanced computation: the tendency to equate Quantum Mechanical (QM) computation and Cognitional Mechanics (CM) solely because both employ non-commutative structures. While the mathematical resemblance is real, the two frameworks operate at fundamentally different ontological layers and therefore govern distinct domains. Quantum computation represents extreme peak performance. Its advantage appears only after a problem has been fully formalized within a closed mathematical system, such as a fixed Hilbert space with well-defined operators and observables. Algorithms like Shor’s and Grover’s demonstrate that, under these conditions, QM can invalidate classical hardness assumptions or achieve dramatic speedups. However, QM neither generates nor reinterprets problems; it presupposes that all semantic uncertainty has already been resolved. Cognitional Mechanics governs the peripheral domain in which problems are formed, redefined, and semantically stabilized. CM models intelligence as a system of non-commutative semantic operations acting on meaning states within an open and evolving semantic manifold. Its non-commutativity is semantic rather than physical: the order of interpretive operations determines which meaning stabilizes, and this process is intrinsically irreversible. Through the example of RSA cryptanalysis, this paper shows that QM and CM are not competing frameworks. QM dominates isolated computational peaks, while CM governs the surrounding periphery that makes such peaks identifiable as problems at all. Recognizing this structural division is necessary to avoid category errors that conflate physical computational power with intelligence itself.