Amir Nayyeri

ICML Conference 2024 Conference Paper

Biharmonic Distance of Graphs and its Higher-Order Variants: Theoretical Properties with Applications to Centrality and Clustering

• Mitchell Black 0002
• Lucy Lin
• Weng-Keen Wong
• Amir Nayyeri

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.

ICML Conference 2024 Conference Paper

Comparing Graph Transformers via Positional Encodings

• Mitchell Black 0002
• Zhengchao Wan
• Gal Mishne
• Amir Nayyeri
• Yusu Wang 0001

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.

ICML Conference 2023 Conference Paper

Understanding Oversquashing in GNNs through the Lens of Effective Resistance

• Mitchell Black 0002
• Zhengchao Wan
• Amir Nayyeri
• Yusu Wang 0001

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.

SODA Conference 2022 Conference Paper

Computational Topology in a Collapsing Universe: Laplacians, Homology, Cohomology

• Mitchell Black 0002
• William Maxwell
• Amir Nayyeri
• Eli Winkelman

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 L 1 x = b, where L 1 is the 1-Laplacian of a simplicial complex K with dim H 1 ( 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 log 2 ( 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(n d ) time, where n d 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 –1 n d ) 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(n d log n d + β 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.

SODA Conference 2019 Conference Paper

Viewing the Rings of a Tree: Minimum Distortion Embeddings into Trees

• Amir Nayyeri
• Benjamin Adam Raichel

We describe a (1 + ε ) approximation algorithm for finding the minimum distortion embedding of an n -point metric space, ( X, d X ), into a tree with vertex set X. The running time of our algorithm is n 2 · (Δ/ ε ) ( O ( δopt / ε ))2λ+1 parameterized with respect to the spread of X, denoted by Δ, the minimum possible distortion for embedding X into any tree, denoted by δ opt, and the doubling dimension of X, denoted by λ. Hence we obtain a PTAS, provided δ opt is a constant and X is a finite doubling metric space with polynomially bounded spread, for example, a point set with polynomially bounded spread in constant dimensional Euclidean space. Our algorithm implies a constant factor approximation with the same running time when Steiner vertices are allowed. Moreover, we describe a similar (1 + ε ) approximation algorithm for finding a tree spanner of ( X, d X ) that minimizes the maximum stretch. The running time of our algorithm stays the same, except that δ opt must be interpreted as the minimum stretch of any spanning tree of X. Finally, we generalize our tree spanner algorithm to a (1 + ε ) approximation algorithm for computing a minimum stretch tree spanner of a weighted graph, where the running time is parameterized with respect to the maximum degree, in addition to the other parameters above. In particular, we obtain a PTAS for computing minimum stretch tree spanners of weighted graphs, with polynomially bounded spread, constant doubling dimension, and constant maximum degree, when a tree spanner with constant stretch exists.

SODA Conference 2018 Conference Paper

On the Decidability of the Fréchet Distance between Surfaces

• Amir Nayyeri
• Hanzhong Xu

We show that the Fréchet distance between two piecewise linear surfaces can be decided in finite time, hence, the problem is decidable. For the special case that one of the surfaces is a triangle, we show that the problem is in PSPACE. In both cases, our computational model is a Turing Machine, and our algorithms rely on Canny's result [STOC 1988] that the existential theory of the real numbers is decidable in PSPACE.

SODA Conference 2017 Conference Paper

A Treehouse with Custom Windows: Minimum Distortion Embeddings into Bounded Treewidth Graphs

• Amir Nayyeri
• Benjamin Adam Raichel

We describe a (1 + ∊)-approximation algorithm for finding the minimum distortion embedding of an n -point metric space X into the shortest path metric space of a weighted graph G with m vertices. The running time of our algorithm is parametrized by the values of the minimum distortion, δ opt, the spread, Δ, of the points of X, the treewidth, ω, of G, and the doubling dimension, λ, of G. In particular, our result implies a PTAS provided an X with polynomial spread, and the doubling dimension of G, the treewidth of G, and δ opt, are all constant. For example, if X has a polynomial spread and δ opt is a constant, we obtain PTAS's for embedding X into the following spaces: the line, a cycle, a tree of bounded doubling dimension, and a k -outer planar graph of bounded doubling dimension (for a constant k ).

FOCS Conference 2015 Conference Paper

Reality Distortion: Exact and Approximate Algorithms for Embedding into the Line

• Amir Nayyeri
• Benjamin Adam Raichel

We describe algorithms for the problem of minimum distortion embeddings of finite metric spaces into the real line (or a finite subset of the line). The time complexities of our algorithms are parametrized by the values of the minimum distortion, δ, and the spread, Δ, of the point set we are embedding. We consider the problem of finding the minimum distortion bijection between two finite subsets of IR. This problem was known to have an exact polynomial time solution when δ is below a specific small constant, and hard to approximate within a factor of δ 1-E, when δ is polynomially large. Let D be the largest adjacent pair distance, a value potentially much smaller than Δ. Then we provide a δ O(δ 2 log 2 D) nO (1) time exact algorithm for this problem, which in particular yields a quasipolynomial running time for constant δ, and polynomial D. For the more general problem of embedding any finite metric space (X, dX) into a finite subset of the line, Y, we provide a Δ O(δ 2 ) (mn) O(1) time O(1)-approximation algorithm (where X = n and Y = m), which runs in polynomial time provided δ is a constant and Δ is polynomial. This in turn allows us to get a Δ O(δ 2 ) (n)O (1) time O(1)-approximation algorithm for embedding (X, dX) into the continuous real line.

SODA Conference 2014 Conference Paper

Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball

• Michael B. Cohen
• Brittany Terese Fasy
• Gary L. Miller
• Amir Nayyeri
• Richard Peng
• Noel Walkington

We present an efficient algorithm for solving a linear system arising from the 1-Laplacian corresponding to a collapsible simplicial complex with a known collapsing sequence. When combined with a result of Chillingworth, our algorithm is applicable to convex simplicial complexes embedded in ℝ 3. The running time of our algorithm is nearly-linear in the size of the complex and is logarithmic on its numerical properties. Our algorithm is based on projection operators and combinatorial steps for transferring between them. The former relies on decomposing flows into circulations and potential flows using fast solvers for graph Laplacians, and the latter relates Gaussian elimination to topological properties of simplicial complexes.

SODA Conference 2014 Conference Paper

Testing Surface Area

• Pravesh K. Kothari
• Amir Nayyeri
• Ryan O'Donnell
• Chenggang Wu 0003

We consider the problem of estimating the surface area of an unknown n -dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and ∊, satisfies: if surf( F ) ≤ A then the algorithm accepts (whp); if F is not ∊-close to some set G with surf ( G ) ≤ κA, then the algorithm rejects (whp). We call κ ≥ 1 the “approximation factor” of the testing algorithm. The n = 1 case (in which “surf( F ) = 2 m ” means F is a disjoint union of m intervals) was introduced by Kearns and Ron [KR98], who solved the problem with κ = 1/∊ and O (1/∊) oracle queries. Later, Balcan et al. [BBBY12] solved it with with κ = 1 and O (1/∊ 4 ) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the “curse of dimensionality”: for any n and any κ > we give a test that uses O (1/∊) queries. For small n we have improved bounds. For n = 1 we can achieve κ = 1 with O (1/∊ 3. 5 ) queries (slightly improving [BBBY12]), or any κ > 1 with O (1/∊) queries (improving [KR98]). For n = 2, 3 we obtain κ ≈ 1. 08, 1. 125 respectively, with O (1/∊) queries. Getting an arbitrary κ > 1 for n > 1 remains an open problem.

SODA Conference 2012 Conference Paper

Global minimum cuts in surface embedded graphs

• Jeff Erickson 0001
• Kyle Fox
• Amir Nayyeri

SODA Conference 2011 Conference Paper

Computing Replacement Paths in Surface Embedded Graphs

• Jeff Erickson 0001
• Amir Nayyeri

SODA Conference 2011 Conference Paper

Minimum Cuts and Shortest Non-Separating Cycles via Homology Covers

• Jeff Erickson 0001
• Amir Nayyeri

Let G be a directed graph with weighted edges, embedded on a surface of genus g. We describe an algorithm to compute a shortest directed cycle in G in any given ℤ 2 -homology class in 2 O ( g ) n log n time; this problem is NP-hard even for undirected graphs. We also present two applications of our algorithm. The first is an algorithm to compute a shortest non-separating directed cycle in G in 2 O ( g ) n log n time, improving the recent algorithm of Cabello et al. [SOCG 2010] for all g = o (log n ). The second is a combinatorial algorithm to compute minimum ( s, t )-cuts in undirected surface graphs in 2 O (g) n log n time, improving on previous combinatorial algorithms, and in particular the recent of Chambers et al. [SOCG 2009], for all g = o (log n ). Unlike earlier algorithms for surface graphs that construct and search finite portions of the universal cover, our algorithms use another canonical covering space, called the ℤ 2 - homology cover.

SODA Conference 2011 Conference Paper

Shortest Non-Crossing Walks in the Plane

• Jeff Erickson 0001
• Amir Nayyeri

Let G be an n -vertex plane graph with non-negative edge weights, and let k terminal pairs be specified on h face boundaries. We present an algorithm to find k non-crossing walks in G of minimum total length that connect all terminal pairs, if any such walks exist, in 2 O ( h 2 ) n log k time. The computed walks may overlap but may not cross each other or themselves. Our algorithm generalizes a result of Takahashi, Suzuki, and Nishizeki [ Algorithmica 1996] for the special case h ≤ 2. We also describe an algorithm for the corresponding geometric problem, where the terminal points lie on the boundary of h polygonal obstacles of total complexity n, again in 2 O ( h 2 ) n time, generalizing an algorithm of Papadopoulou [ Int. J. Comput. Geom. Appl. 1999] for the special case h ≤ 2. In both settings, shortest non-crossing walks can have complexity exponential in h. We also describe algorithms to determine in O ( n ) time whether the terminal pairs can be connected by any non-crossing walks.

STOC Conference 2009 Conference Paper

Homology flows, cohomology cuts

• Erin W. Chambers
• Jeff Erickson 0001
• Amir Nayyeri

We describe the first algorithms to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given an undirected graph embedded on an orientable surface of genus g, with two specified vertices s and t, we can compute a maximum (s,t)-flow in O(g 7 n log 2 n log 2 C) time for integer capacities that sum to C, or in (g log n) O(g) n time for real capacities. Except for the special case of planar graphs, for which an O(n log n)-time algorithm has been known for 20 years, the best previous time bounds for maximum flows in surface-embedded graphs follow from algorithms for general sparse graphs. Our key insight is to optimize the relative homology class of the flow, rather than directly optimizing the flow itself. A dual formulation of our algorithm computes the minimum-cost cycle or circulation in a given (real or integer) homology class.