The paper introduces linear‑time randomized algorithms for unbiased approximation of general random walk kernels (RWKs) on sparse graphs, covering both labelled and unlabelled cases. By sampling dependent random walks and constructing novel graph embeddings in ρ^d, the method avoids building the direct product graph, enabling scaling to massive datasets that cannot fit on a single machine. The authors provide exponential concentration bounds for the estimator’s sharpness and demonstrate up to 27× speed‑ups and 128× larger graph handling compared to previous cubic‑time approaches.
By Krzysztof Choromanski, Isaac Reid, Arijit Sehanobish, Avinava Dubey
arXiv:2510. 07716v2 Announce Type: replace Abstract: We propose refined GRFs (GRFs++), a new class of Graph Random Features (GRFs) for efficient and accurate computations involving kernels defined on the nodes of a graph.
By Krzysztof Choromanski, Avinava Dubey, Arijit Sehanobish, Isaac Reid
arXiv:2510.17714v3 Announce Type: replace-cross
Abstract: Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partit...
By Atticus McWhorter, Daryl DeFord
The paper introduces a scalable subgraph sampling method that uses resistance curvature to guide the selection of nodes and edges for graph neural network training. It builds on ERC‑LG, a curvature approximation technique that employs Johnson‑Lindenstrauss projections and regularized multi‑GPU batched conjugate gradient solvers, thereby avoiding costly Laplacian pseudoinverse calculations and large embedding storage. Experiments demonstrate that ERC‑LG‑based sampling matches pseudoinverse‑based curvature numerically, runs faster than conjugate‑gradient‑only approaches, and achieves the best mean accuracy on six of seven real‑world node‑classification datasets.
By Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li
The paper introduces a data‑driven method for learning Random Geometric Graphs (RGGs) in probabilistic metric spaces. It defines a distance function based on the cumulative distribution of a disparity variable that captures differences in vertex connectivity and correlation of attached random variables, enabling edges to exist with a specified probability. The approach includes a rejection‑sampling technique for edge probability estimation and a closed‑form posterior for learning the inter‑observable correlation matrix, and it is demonstrated on highly multivariate real datasets.
By Dalia Chakrabarty, Kangrui Wang, Chuqiao Zhang, Ye Liu
arXiv:2604. 12211v2 Announce Type: replace Abstract: Ollivier-Ricci curvature (ORC), defined via the Wasserstein distance that captures rich geometric information, has received growing attention in both theory and applications.
By Xiang Gu, Huichun Zhang, Jian Sun
arXiv:2506.02825v3 Announce Type: replace-cross
Abstract: We present the OmniMatch algorithm for seeded multiple graph matching. In the setting of $d$-dimensional Random Dot Product Graphs (RDPG), we...
By Tong Qi, Vera Andersson, Peter Viechnicki, Vince Lyzinski
The paper investigates methods for estimating average distances in large static graphs, comparing a graph sampling approach (Random Walk) with landmark-based techniques such as the Size Estimation Framework (SEF) and the Eppstein‑Wang (EW) algorithm. Random Walk proved unreliable for small samples and costly for larger ones, while landmark methods using HyperLogLog were more efficient. Experiments on undirected, unweighted graphs showed that the EW algorithm achieves very low error (≈0.02%) and can use a subset of only 100 nodes for accurate estimation, outperforming SEF in accuracy and speed.
By Kartikey Ahlawat
arXiv:2402. 11736v3 Announce Type: replace Abstract: Kernel herding belongs to a family of deterministic quadratures that seek to minimize the maximum mean discrepancy (MMD), that is, the worst-case integration error over a reproducing kernel Hilbert space (RKHS).
By Martin Rouault, R\'emi Bardenet, Myl\`ene Ma\"ida
The paper revisits the Boykov‑Kolmogorov (BK) algorithm for computing minimum s‑t cuts in graphs, improving its theoretical time complexity to O(mn|C|). It introduces a faster variant, the fast BK (fBK) algorithm, with complexity O(m|C|), and proposes a compact graph representation enabling the algorithms to handle graphs with up to 10^9 vertices and 10^10 edges on a 128 GB machine. Experiments show that the compact BK implementation (cBK) outperforms other BK variants, underscoring the value of memory‑efficient designs.
By Christian M{\o}ller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille, Vedrana Andersen Dahl, Inge Li G{\o}rtz
arXiv:2608. 10523v1 Announce Type: cross Abstract: \texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$.
By Amit Sharma, Mohammad Azhar Khan, Rameshwar Pratap, Keegan Kang
\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$.