5 papers
Accelerating the Local Push Primitive for PageRank Computation
Guanyu Cui, Zhewei Wei, Mingji Yang
We propose a local algorithm that computes an -approximate PageRank vector in the sense of Andersen, Chung, and Lang (ACL; Internet Math. 2007) with teleportation para…
Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management
Guanyu Cui, Zhewei Wei, Kun He
Many works make the eye-catching claim that Transformers are Turing-complete. However, the literature often conflates two distinct settings: (i) a fixed Transformer system setting,…
Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method
Guanyu Cui, Hanzhi Wang, Zhewei Wei
We study the problem of efficiently approximating the \textit{effective resistance} (ER) on undirected graphs, where ER is a widely used node proximity measure with applications in…
How Hard Is It for Message-Passing GNNs to Simulate One Weisfeiler-Lehman Color-Refinement Step?
Guanyu Cui, Yuhe Guo, Zhewei Wei +1
Message-passing graph neural networks (MPGNNs) are commonly compared with the Weisfeiler-Lehman (WL) color-refinement procedure, but this comparison does not quantify the resource…
MGNN: Graph Neural Networks Inspired by Distance Geometry Problem
Guanyu Cui, Zhewei Wei
Graph Neural Networks (GNNs) have emerged as a prominent research topic in the field of machine learning. Existing GNN models are commonly categorized into two types: spectral GNNs…