5 citations · 5 across the 7 of their papers we have counts for
10 papers
The Expressive Power of Random-Feature MPNNs Across Graph Sizes
Robert R. Nerem, Mitchell Black, Antonis Vasileiou +2
Continuous random node features increase the expressivity of message-passing neural networks (MPNNs), but existing theoretical analyses are not fine-grained enough to capture their…
Understanding Truncated Positional Encodings for Graph Neural Networks
James Flora, Mitchell Black, Weng-Keen Wong +1
Positional encodings (PEs) enhance the power of graph neural networks (GNNs), both theoretically and empirically. Two of the most popular families of PEs - spectral (e.g., Laplacia…
Graph Inference with Effective Resistance Queries
Huck Bennett, Mitchell Black, Amir Nayyeri +1
The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. Graph reconstruct…
Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering
Mitchell Black, Lucy Lin, Amir Nayyeri +1
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…
Comparing Graph Transformers via Positional Encodings
Mitchell Black, Zhengchao Wan, Gal Mishne +2
The distinguishing power of graph transformers is closely tied to the choice of positional encoding: features used to augment the base transformer with information about the graph.…
An Incremental Span-Program-Based Algorithm and the Fine Print of Quantum Topological Data Analysis
Mitchell Black, William Maxwell, Amir Nayyeri
We introduce a new quantum algorithm for computing the Betti numbers of a simplicial complex. In contrast to previous quantum algorithms that work by estimating the eigenvalues of…
Understanding Oversquashing in GNNs through the Lens of Effective Resistance
Mitchell Black, Zhengchao Wan, Amir Nayyeri +1
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…
Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes
Mitchell Black, Amir Nayyeri
We describe a nearly-linear time algorithm to solve the linear system parameterized by the first Betti number of the complex, where is the 1-Laplacian of a simplic…
ETH-tight algorithms for finding surfaces in simplicial complexes of bounded treewidth
Mitchell Black, Nello Blaser, Amir Nayyeri +1
Given a simplicial complex with simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected sur…
Finding minimum bounded and homologous chains in simplicial complexes with bounded-treewidth 1-skeleton
Mitchell Black, Amir Nayyeri
We consider two problems on simplicial complexes: the Optimal Bounded Chain Problem and the Optimal Homologous Chain Problem. The Optimal Bounded Chain Problem asks to find the min…