Repelling Random Walks
Authors: Isaac Reid
Eli Berger
Krzysztof Marcin Choromanski
Adrian Weller
Venue: ICLR 2024 poster (2024)
Keywords: Graphs
random walkers
quasi-Monte Carlo
kernel
PageRank
graphlets
scalable
mixing
Primary area: learning on graphs and other geometries & topologies
TL;DR: A novel mechanism to correlate the trajectories of random walkers on graphs, improving the concentration properties of estimators whilst leaving them unbiased

Abstract: We present a novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. By inducing correlations between the trajectories of an interacting ensemble such that their marginal transition probabilities are unmodified, we are able  to explore the graph more efficiently, improving the concentration of statistical estimators whilst leaving them unbiased. The mechanism has a trivial drop-in implementation. We showcase the effectiveness of repelling random walks in a range of settings including estimation of graph kernels, the PageRank vector and graphlet concentrations. We provide detailed experimental evaluation and robust theoretical guarantees. To our knowledge, repelling random walks constitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on a graph, inviting new research in this exciting nascent domain.

Published as a conference paper at ICLR 2024
REPELLING RANDOM WALKS
Isaac Reid", Eli Berger Krzysztof Choromanski Adrian Weller University of Cambridge, University of Haifa, *Google DeepMind, 'Columbia University, AAlan Turing Institute ir3370cam ac. uk, kchoro@google.com
ABSTRACT
We present novel quasi-Monte Carlo mechanism to improve graph-based sampling, coined repelling random walks. By inducing correlations between the trajectories of an interacting ensemble such that their marginal transi- tion probabilities are unmodified, we are able to explore the graph more effi- ciently, improving the concentration of statistical estimators whilst lcaving them unbiased. The mechanism has trivial drop-in implementation. We showcase the effectiveness of repelling random walks in range of setlings including estimation of graph kernels, the PageRank vector and graphlet concentrations. We provide detailed experimental evaluation and robust theoretical guarantees. To our knowledge, repelling random walks con- stitute the first rigorously studied quasi-Monte Carlo scheme correlating the directions of walkers on graph, inviting new rescarch in this exciting nascent domain
INTRODUCTION AND RELATED WORK
Quasi-Monte Carlo (QMC) sampling is well-sstablised as universal tool to improve the convergence MC methods, improving the concentration properties of estimators by using low-discrepancy samples to reduce integration error (Dick et al. 2013). They replace iid. samples with a correlated ensemble, carefully constructed to be more 'diverse' and hence improve approximation quality.
Such methods have been widely adopted in the Euclidean setting. For example, when sam- pling from isotropic distributions, one popular approach is to condition that samples are orthogonal: a trick that has proved successful in applications including dimensionality re- duction (Choromanski
al. 2017). evolution strategy methods in reinforcement learning [Choromanski et al.] 2018 Rowland et al. 2018) and estimating sliced Wasserstein dis- tances (Rowland et a 2019; Orthogonal Monte Carlo' has also been used to improve the convergence of random feature maps for kernel approximation (Yu et al.] 2016), including recently in attention approximation for scalable Transformers (Choromanski
al. (020).
Intuitively, conditioning that samples are ort orthogonal prevents them from clustering together and ensures that they 'explore' Rd better. In specific applications it sometimes possible to derive rigorous theoretical guarantees (Reid et al. 2023b).
Less clear is how these powerful ideas generalise to discrete space. Of particular interest are random walks on graphs, which sample sequence of nodes connected by edges with some stopping criterion. Random walks are ubiquitous in machine learning and statistics (Xia et al. 2019), providing a simple mechanism for unbiased graph sampling that can be implemented in a distributed way. However, slow diffusion times (especially for challenging graph topologies) can lead to poor convergence and downstream performance.
Our key contribution the first (to our knowledge) quasi-Monte Carlo scheme that corre- lates the directions of an ensemble of graph random walkers to improve estimator accuracy. By conditioning that walkers 'repel' in a particular way that leaves the marginal walk prob- abilities unmodified, we are able to provably suppress the variance of various estimators
"Senior lead.
Cooee available at http:r//ihhhibcoom/mmaccrrrrplpp random walks

---

Published as a conference paper at ICLR 2024
whilst preserving their unbiasedness. We derive strong theoretical guarantees and observe large performance gains for algorithms estimating three disparate quantities: graph ker- nels [Choromanski, 2023), the PageRank vector [Avrachenkov et al. 2007 and graphlet concentrations (Chen et al. 2016).
Related work: The poor mixing of random walkers on graphs is well-doeumented and varions schemes exist to try to improve estimator convergence. Most directly modify the base Markov chain by changing the transition probabilities, but without altering the walker's stationary distribution and therefore leaving asymplolic estimators (e.g. based on empirical node occupations) unmodified. The canonical example of such a scheme is non-backtracking walks which do not permit walkers to return to their most recently visited node (Alon et al.
2007 Diaconis al.) 2000; Lee et al. 2012)- More involved schemes allow walkers interact with their entire history (Zhou et al. 2015 Doshi et al. 2023). Many of these strategies provide theoretical guarantees that the asymptotic variance estimators is reduced, but crucially the marginal probabilities of sampling different walks are modified they cannot be applied to non-asymptotic estimators that rely on particular known marginal transition probabilities. Conversely, our QMC scheme leaves marginal walk probabilities unmodifed. Research has also predominantly been restricted to the behaviour of a single self-interacting walker rather than an ensemble, and when multiple walkers are considered analytic results are generally restricted to simple structures, e-g. complete graphs (Rosales et al. 2022 Chen
2014). This research exists within the broader literature of reinforced random walks, where nonlinear Markov kernels are used so that walkers are less (or more) likely to transition to nodes that have been visited in the past (Pemantle) 2007]. However, the analytic focus has predominantly been on properties like recurrence times, escape times from sets, cover times
and localisation results for simple topologies (Amit et al. 1983 Tóth 1995 Tarrès 2004). rather than the behaviour of associated statistical estimators general graphs. The lalter of more direct interest in machine learning.
The remainder of the manuscript is organised as follows. In Sec. we introduce the requisite mathematics and present our novel QMC repelling random walk mechanism. In Secs 3 we use it to approximate three quantities of interest in machine learning: graph node kernels (Sec. 3), the PageRank vector (Sec. 4), and graphlet statistics (Sec. 5). Repelling random walks empirically found to outperform the i.i.d. variant in every case and we are often able to provide concrete thcoretical guarantees.
REPELLING RANDOM WALKS
Consider undirected, connected graph G E) where N == {1,..., N) denotes the set of nodes and & denotes the set of edges, with (i,J) E if there is an edge between nodes i, E N. Write the graph's (weighted) adjacency matrix A == [aiglksen, where dij A if (1,5) E E and 0 otherwise. Let d4 == EjeN [[( E E) denote the node degree, which is the number of neighbours of a particular node, and let M(2i) = (j E (i,,)) E} denote the set of neighbours of node i. The transition matrix P PoykJEN of simple random walk is given by
if (
P de 0 otherwise
(1)
such that at every timestep the walker selects one of its neighbours with uniform probability. This can be viewed as finite and reversilee Markov chain with state space A.
Supposing we have m such walkers on the graph simultaneously, we can define an augmented Markov chain with state space N consisting of the possible node positions of all the walkers. If the walkers are independent, the joint transition matrix Q E R N" x is given a Kronecker product of the marginal transition matrices p(O)
Q
(())
(2)
where the index i = 1.... m enumerates the walkers present. Our key contribution now to induce correlations between the walkers' paths such that the joint transition matrix Q is modified but each marginal transition matrix (and hence the unbiasedness of any estimator relying it) is unchanged. The correlations are designed to improve estimator convergence.
2

---

Published as a conference paper at ICLR 2024
1i.d.
000
000
repelling
Figure 1: Schematic for behaviour of repelling random walkers at particular timestep. By sampling from each 'block' (blue and green rectangles) without replacement get more even distribution over neighbours, without changing the marginal probabilities.
Definition 2.1 (Repelling random walks). A repelling ensemble has the following behaviour.
Let D(()) denote the set of walkers at node at timestep t, and N₂ = [ the size of this set. Randomly divide these walkers inlo N /d subsels of size d and one 'remainder' subset of size N₁ N10% < d (where // and denole truncating inleger division and the remainder, respectively). Among each subset, assign the wolkers to neighbour from the set N uniformly without replacement.
This is in contrast to ii.d. walkers where Da are assigned to the neighbours Mii) uniformly with replacement. We provide schematic in Fig. [ In the repelling scheme, each walker still has marginal transition probability P.j = (1/d; if (i,j) E, 0 otherwise), but now they are forced to take different edges and heuristically 'cxplore' the graph more effectively. The sample of walks is more 'diverse'. Since the marginal transition probabilities p() are unmodified, any estimators that are unbiased with i.i.d. walkers are also automatically wnbiased with repelling walkers, including in the non-asymplolic regime. However, as shall see, their concentration properties are often substantially better.
Computational cost and implementation: Repelling random walks have trivial drop- in implementation. The only difference is whether walkers are assigned to neighbours with without replacement. Moreover, the transitions in the augmented state space N remain Markovian (memorylcss): there are no extra space complexity costs because we only need access the current positions of all the walkers.
Physical interpretation and entanglement: Under repulsive interactions, the joint transition matrix Q can no longer be written Kronecker product. Consider transitions of 2 walkers in the same 'block' from iz) to (21,
We have:
[ 8r (1 81.52)
(1-8
if d # if d; =
QNE tig,N Pr(Ji,22h,, Piyj Pinja
with 8, the delta function. This does not generically factorise into (11. and (i2,J2) dependent parts. In quantum mechanics (QM), an interacting Hamillonian which cannol be written as Kronecker sum gives rise to a time-evolution operator U = e that cannot be written as Kronecker product, which in turn generically gives rise to quantum entanglement between particles. Just as the von-Neumann entropy (a measure of bipartite quantum entanglement (Amico et al. 2008)) increases under such interactions, in our QMC scheme the Shannon mutual information initially increases from O: during the first timestep, Note that the analogy is not exact because in QM the time- evolution operator acts on (complex) wavefunctions whereas here the transition matrix acts on the (real positive) probabilities of being in different states of Markov chain encoding graph. It is just intended to help build intuition for the reader.
AT, = 6, log( (og(2_=) - 2
the positions of walkers
will be convenient to define one further class of interacting random walk.
3

---

Published as a conference paper at ICLR 2024
Definition 2.2 (Transient repelling random walks). An ensemble of random walks is de- scribed as transient repelling the walkers repel (according to Def. 2.1 at the first timestep, and are independent thereafter.
Such an ensemble will capture the repelling behaviour at early times but eventually relax to independence. Whilst less practical than the full repelling scheme, we will see that sometimes it makes theoretical analysis tractable.
We now apply our repelling random walks mechanism to three disparate applications: ap- proximation of graph kernels (Sec. 3 approximation of the PageRank vector (Sec. 4 and approximation of graphlet concentrations (Sec.
3 APPLICATION 1: APPROXIMATING GRAPH KERNELS
We begin by demonstrating the effectiveness of repelling random walks for estimating graph kernels Kg : - x N + I. defined on the nodes N of graph G. Such kernels capture the structure of G, letting practitioners repurpose theoretically grounded and empirically successful algorithms like support vector machines, kernelised principal component analysis and Gaussian processes to the discrete domain (Smola and Kondor 2003 Applications include in bioinformaties (Borgwardt. et. al., 2005), community detection (Kloster and Gle- ich 2014], generative modelling (Zhou et al.j 2020) and solving shortesl-path problems CCane et al., 2017), Chief examples of Kg are the d-regularised Laplacian and diffusion lap = -II+ +[)) and Kaift = exp(-or respectively. Here, o² is lengthscale parameter and L is the normalised graph Laplacian, defined by L = I- W W with W = [asp///l (d,d,, / a normalised weighted adjaceney matrix (d, = E, ag is the weighted node degree and Gzy is the weight of the original edge). L is the analogue of the fa- U in discrete space, describing diffusion 0² +...+
kernels, given by K id)
~
R.j=1
miliar Laplacian operator 22 8²
on G (Chung and Yau 1999
Chung
1997
lap exactly can be prohibitively expensive due to the O(N3) time complexity of matrix inversion. This motivated the recently-introducel class of Graph Random Features ( (GRFs) [Choromanski 2023). which provide a discrete analogue to Random Fourier Features [Rahimi and Recht, 2007]. These N-dimensional vectors o(i) e RN are constructed for every node i E A such that their Euclidean dot product is equal to the kernel evaluation in expectation,
For large graphs, computing e.g.
K(d
lap = E (()))
(4)
In their paper, Choromanski (2023) provides an elegant algorithm for constructing obi): one simulates m E N random walks out of each node that terminate with probability p at every timestep, depositing a 'load' at every node they visit to build up a randomised projection of the local environment in G. They show that this gives an unbiased estimate of K (22) "ap'
which can be used to construct KLp for d E N or an asymptotically unbiased approximation of Kait- Since the unbiasedness of the estimator depends on the marginal probabilities of sampling different finite-lnnghh random walks being unmodified (c.f. just its stationary distribution), it is a natural setting to test our new quasi-Monte Carlo scheme.
Remarkably, under mild conditions, we are able to derive an analytic closed form for the difference in kernel estimator mean squared error (MSE) between the i.i.d. and transient- repelling mechanisms for general graphs (deferred to Eq. 32 in App. A. for brevity). This enables us to make the following statement for some specific graphs, proved in App. A.
Theorem 3.1 (Superiority of repelling random walks for kernel estimation). Consider graph nodes indezed (i.j) separated by at least 2 edges. In the limit a + O, provided the number of walkers in the transient repelling ensemble is smaller than or equal to the node degrees d(is) and the edge-weights of W are equal,
Var(Te (2)
tapti repeltin)) S Varl Var( (2) plosid)
for both i) trees and i) 2- 2-dimensional grids.
Though we have made some restrictions for analytic tractability, we will empirically observe that the full repelling QMC scheme is effective in much broader settings. In particular,
4

---

Published as a conference paper at ICLR 2024
ER (N = 20, p 0.2)
ER (N = 100, -0000=00000
Binary tree (N 127)
d-regular = 100, d=
3.02
3.000
SeaGRifs Q-F-GRFs
emer
5,032
5,00-
0.000
0.030
5.032
Rob. 1em
0.00
C-An-GMP
2,000
0.00
2.000
0.00
5,009
2.006
000m
5.004
Ronc4
2002
5.000
15
random walks
No. random walks
random wals
walks
Karate IN 34)
Dolphins 62)
Football IN 1151
Eurosis IN 1272)
0.014
0.034
0.04
2.024
hro mom enro
3.02
5,032
3.010
2.000-
0.00
0000
000
Fob.
5,004
2.004-
o0ce
0006
3.006
5,002
0602
No. random walks
No. random walks
No. random wals
No. random walks
Figure 2: Relative Frobenius norm of estimates of the 2-regularised Laplace kernel (lower better) number of random walks for: vanilla GRFs; ii) GRFs with antithetic termination (Reid et al. 2023a) ('q-a-GRFs') iii) GRFss with repelling walks ('q-r-GREss); iv) GIREs with both antithetic termination and repelling walks ("q-ar-GREs'.. Using both QMC schemes together gives the best results for all graphs considered and the gains are large (somctimes factor of > 2). N gives the number of nodes, p the gege-generation probability for the Erdös- Rényi graphs, and d is the d-regular node degree. One standard deviation on the mean error is shaded but is loo small to easily see.
substantially suppresses kernel estimator variance with many walkers, arbitrary a and arbitrary graphs. Extending the proof to these general cases is exciting open problem.
We also note that our scheme fully compatible with the recemtly-introduuced QMC scheme known andithelic lermination (Reid et al. 2023a), which anticorrelates the lengths of random walkers (by coupling their terminations) but does not modify their trajectories. Both schemes be applied simultaneously, inducing negative correlations between both the walk directions and lengths.
3.1 POINTWISE KERNEL. ESTIMATION
We now empirically test Eq. for general graphs by comparing the variance of [K[ 201 under different schemes. In what follows, 'GRFs' refers to graph random features constructed using i.i.d. walkers, whilst 'q-(a,r,r)-GRRR where walkers exhibit antithetic termination ('a') (Reid et al.) 2023ab, repel ('r',, or both ('ar'). We use these different flavours of GR-) to generate unbiased estimates Kapp then compute the relative Frobenius norm |K[]]
denotes the efficient quasi-Monte Carlo variants
[ between the true and approximated Gram matrices. Fig. 2 presents the results for various graphs: small Erdös- Rényi, larger Erdös- Mendss-Révi,,.. binary tree, a d-regular graph, and four standard real-world examples from ([vashkin, 2023) (karate, dolphins, football and eurosis). These differ substantially in both size and structure. We take 100 repeats compute the variance of 0.1 and termination probability p = 0.5. The gains provided by the repelling QMC scheme (green) are much greater than those from antithetic termination (orange), but the lowest variance is achieved when both are used together (red). Note that the gains provided by repelling random walks continue to accrue as the size of the ensemble grows; with 16 walkers the error is often halved.
1 |p/ - -
lap
the kernel approximation error, using regulariser
3.2 DOWNSTREAM APPLICATIONS: KERNEL REGRESSION FOR NODE ATTRIBUTE PREDICTION
We have both proved (Theorem 3.1 and empirically confirmed (Fig. 2 that using repelling random walks substantially improves the quality of estimation of the 2-regularised Laplacian
5

---

Published as a conference paper at ICLR 2024
kernel using GRFs. Naturally, this permits better performance in downstream applications that depend on the approximation. As an example, we follow Reid et al. (2023a) and consider kernel regression on triangular mesh graphs (Dawson- Haggerty 2023
Consider graph where each node is associated with normal vector w(9) The task is to predict the directions of a random set of missing 'test' vectors (a 5% split) from the remaining 'train' vectors. We compute our (unnormalised) predictions ((1) as T(() = Σ3 K (),)), where sums over the training vertices and K jap (i,5) is constructed using the GRF and q- (-(a.r,,r)-GRR mechanisms described in Sec. 3.1 We compute the average angular error 1-cos & between the prediction g(+) and groundtruth w(() across the test set. We use 16 random walks with a termination probability = 0.5 and regulariser o = 0.1, taking 1000 repeats for stalistics. Table [ reports the results. Higher-quality kernel approxinations with repelling random walks give more accurate downstream predictions for all graphs, with the biggest gains appearing when our repelling scheme is introduced ('r' and 'ar'). The difference is remarkably big when the number of nodes N is big: on torus, the error is reduced by factor of almost 3. Accurate approximation is especially helpful for these large graphs as exact methods become increasingly expensive.
Table 1: Angular error 1 - cos f between true and predicted node vectors when approx- imating the Gram matrix with GRFs and (afarr,ar-GGRFs (lower better). Brackets give one standard deviation. Both schemes combination works best.
Graph
Pred error, 1 - cos
GRFs
q-a-GRF's
q-r-GRFs
FFF
cylinder
210
0.0650(7)
0.0611(7)
0.0166(3)
0.0459 (2)
teapot
480
0.0331(2)
0.0322(2)
0.0224(1)
0.0215(1)
idler-riser
782
0.0528(3)
0.0521(3)
0.0408(2)
0.0408(2)
busted
1941
0.00463(2)
0.00456(2)
0.003833
0.003817(6)
torus
4350
0.000506(1)
0.000482(1)
0.000180(1)
0.000181
Though for concreteness we have considered one particular downstream application, stress that improving the kernel estimate can be expected to boost performance any
algorithm that uses it, e.g. for graph node clustering (Dhillon et al.] 2004), shortest-path prediction (Crane et al.] 2017) or simulation of graph dillusion (Reid el. al. 2023a
4 APPLICATION 2: APPROXIMATING PAGERANK
As a second application, we use repelling random walks to improve numerical estimates of the PageRank vector: popular measure of node importance in a graph originally proposed by Page al. (1988) to rank websites search engine results. The PageRank vector defined as the stationary distribution of Markov chain whose state space is the set of all graph nodes N, with a transition matrix
P= P1 PE N
(6) Here, e (0, 1) a scalar, N is the number of nodes, is defined in Eq, I and E [e] is matrix whose entries all ones. This encodes the behaviour of "surfer" who at every timestep either teleports to a random node with probability or moves to one of its neighbours chosen uniformly at random. Since P is stochastic, aperiodic and irreducible, we can define the unique PageRank vector π E B.N:
(7) where normalised the sum of vector entries to 1. Physically, π, is the stationary prob- ability that a surfer at node j. π is very expensive compute for large graphs and the form of P invites MC estimation with random walkers. Fogaras et al. (0055) suggest the following algorithm.
π TPp π -1==1

---

Published as a conference paper at ICLR 2024
Algorithm 4.1 (Random walks for PageRank estimation). Fogaras et al. 2005) Simulate m E runs of a simple random walk with transition probability matrir P out of every node i E N, terménating with probability p at each timestep. Evaluate the estimator т the fraction of walks terminating at node j, f3
EN Ex=
II (walker terminates at j)-
It is straightforward show that रे is an unbiased estimator of π (see App. A.2 This is a natural setting to test an ensemble of repelling random walks. We are able to make the following surprisingly strong statement.
Theorem 4.2 (Superiority of repelling random walks for PageRank estimation). For transient repelling ensemble,
Var(fi)))pplliin S Var(Ft))ss.d
(8)
for any graph.
We defer full proof to App. A.2 but provide a brief sketch below.
Proof sketch: Supposing that the number of walkers is smaller than the minimum node degree, the behaviours of a transient repelling and i.i.d. ensemble only differ at the first timestep. In the former scheme walkers are forced to diverge whercas in the latter they are independent. The expectation values the estimators associated with each walker are conditionally independent given their node positions at t = and are identical in both schemes by definition; denote it by f(V==1). With the i.i.d. ensemble the variance depends on 100 (f( (f((1)) where the node positions of pair of walkers v(2.2) are inde- pendent. Meanwhile, for repelling walkers it depends on gee (f where we condition that v(1.2) cannot be equal. Simple algebra reveals that the latter is smaller. It straightforward to then generalise to when the number of walkers exceeds the minimum node degree.
remarkable that Theorem 4.2 holds for arbitrary G. Table 2 shows the PageRank estimator error with 2 walkers that are either i) ii.d. ii) repelling out of every node. already excellent with just a single pair. The termination
The quality approximation probability is p 0.3 and we take 1000 trials to compute the standard deviations (10000 for eurosis since it is larger). As per the theoretical guarantees, repelling random walks consistently perform better.
Mean L2-norm of the difference between the true and approximated PageRank vectors Ter == || f||2, using i.idd and repelling pairs of random walkers. Lower is better. Repelling random walks consistently outperform i.id. random walks. Paren- theses give one standard deviation on the mean error.
Table 2:
Graph
N
PageRank error, Terr repelling
i.i.d.
Small
0.0208(2)
0.0196(2)
Larger ER
100
0.00420(2)
0.00406(2)
Binary tree
127
0.00290(1)
0.00270(1)
d-regular
100
0.00434(2)
0.00422(2)
karate
0.0124(1)
0.0115(1)
dolphins
62
0.00686(4)
0.00651
football
115
0.00385(2)
0.00376(2)
eurosis
1272
0.000341(2)
0.000335(2)
In the PageRank setting, RRWs are closely related to the algorithm presented by Luo 2019 which was introduced to reduce edge bandwidth. The scheme takes d, walks out of every node i and permutes them randomly among the neighbours at every timestep. Note that sampling without replacement is identical to permutation the number of walkers is equal to the number of neighbours to which they must be assigned.
As a brief addendum for the interested reader: îं is actually a member of a broader class of functions coined step-by-slep linear, defined as follows.

---

Published as a conference paper at ICLR 2024
Definition 4.3 (Step-by-sten linear functions). Let Ωr denote the set of all infinite-length walks starting at node r, 2, == {(u)) Vo = 7, Us E N,, (0,, Ut41) E E}. We refer to func- tion y 22 + I step-by-step linear if it takes the form:
v(w) = Σ flu..) II 20.
where f :: x (O)) + R and g:N
X X
x (N U (0}) - R.
These functions have the property that the variance of the corresponding Monte Carlo estimator is guarantoed be suppressed by conditioning that the ensemble of random walks {w) is transient repelling. Concretely, the following is true.
Theorem 4.4 (Variance of step-by-step lincar functions is reduced by transient repulsion). Consider the estimator Y = --= y(w)) where {wi enumerates m (infinite) walks on and y: Ω2 + R step-by-step linear function. Suppose that the sets of walks {wx]== mm are either i) i.i.d. or ti) transient repelling (Def. 2.2 We have that:
Var(Y reepYtntin)))
< Var(Yia..).
(10)
Interostingly, the step-by-step linear family also includes Φ(t)x, the kth component of the GRF corresponding to the ith node of G, though of course this alone is insufficient to guarantee suppression of variance of the kernel estimator d(i)T(()) (()).
We provide a proof and further discussion in Sec. A.3
APPLICATION 3: APPROXIMATING GRAPHLET CONCENTRATIONS
Finally, we use repelling random walks to esti- mate the relative frequencies of graphlets: in- duced subgraph patterns within a graph g. For- mally, k-node induced subgraph G& = (V,, &k) satisfies V4 C V, [Val = k and & = ((u,v) u E V& A (u, E E}: that is, subset of k connnected nodes together with any edges bo- tween them. For example, for &s 3 the possible graphlets are a triangle and & wedge (see Fig. 3
triangle
wedgo
Figure 3: Graphlets for k 3
Computing graph's 's graphlet concentrations the proportions of different k-node graphlets is
task of broad interest in biology (Pržuljj 2007 Milenković and Pržulj 2008 and network
science (Becchetti et al. 2008 Ugander et al. 2013 since it characterises the local structure
of G (Milo et al.) 2002 J. Such concentrations even permit construction of graphlet kernels
K : G x IR to compare different graphs (Shervashidze et al. 2009).
For large graphs, exact computation by exhaustive counting is unfeasible because of the combinatorial explosion in the number of graphlets with N. This motivates random walk Markov Chain Monte Carlo approaches. Such crawling- wrawling-based algorithms also benefit from not requiring access to the entire graph simultaneously:
typical restriction for online social networks where the graph is only available via API calls to retrieve a particular node's neighbours (e.g. user's friends). These algorithms are also easily distributed across machines.
Chen et al. (0016) propose general algorithm for asymptotically unbiased, efficient timation of graphlet concentrations using random walks. We summarise one particular instantiation of it for l: 3 below.
Algorithm 5.1 (Graphlet concentration estimation using random walks). (Chen et al, 2016) Simulate a simple random walk of length L E N (the sampling budget) out of a randomly selected node. Consider x(3) an augmented Markoe Chain whose state space is the ordered 3-tuples of consecutively-ott visited nodes. Discard all such states where X; Xi+2 (where the walker backtrackss) and for the
X1,,X,1,, with 1 sis - 2, the states of
8

---

Published as a conference paper at ICLR 2024
(V = p 0.2)
(W
100, 0.04]
deregular = =000, d=
Palboeks (N 105)
6037
Mid
5.0200
0.0045
1.000
3,030
repelling
5,037
0.0000mm
5,033
0.00:5
5.025
Grsphler
Graphie
Graphige
5.0050
1003
2.0043
12
10
Karate IN - 34)
Dolphins (N 62)
Football IN 115)
Eurosis (N 12721
Graphuet cone aut armer
0L012-
Graphiet conc, eror
00200
Graphiet cone. est.
5.177
6.0.5-
0.011
0.005
2.003
50150
-0122
0009
2.00L3
00100
No. random walks
No. random walks
No. random walks
No. random walks
Figure 4: Mean square error on estimates of k = 3 graphlet concentrations with different numbers of random walks different graphs. Lower better. Using the repelling scheme consistently improves the quality of the estimate compared to independent walks.
remaining n classify the graphlets g, to get the weighted counts Cwed == EI=I wedge) dit1 and Ceri = Em= [( triangle) d=1
(where d:-1 is the degree of the i gives unbiased estimator of the
1th node). In the limit of large L, ((3) Cies Cwed
concentration of triangle graphlets.
The weightings in the computation of C twed,ttr) are included to correct for two sources of bias: d++1 accounts for the fact that the stationary distribution of the expanded Markov chain is inversely proportional to the degree of the middle node, T (x{²)) (2( and the combinatorial factors adjust for the fact that 6 states x correspond to the triangle graphlet (twice the number of Hamiltonian paths) but only 2 correspond to the wedge.
We implement Alg. 5.1 with both i) i.i.d. walkers and ii) a repelling ensemble. rigorous theoretical analysis of concentration properties is very challenging and is deferred impor- lant future work; for now, our study is empirical. Fig. | plots the fractional error of the estimator of triangle graphlet concentration 2(3) against the number of walkers. We use the same graphs as in Sec. [ but replace the binary tree with polbooks since for the former 0 trivially. We impose a restricted sampling budget with walks of length J. 16 to highlight the benefits of repelling random walks in the transient regime, and take 2500 repeats over all starting nodes for statisties. Repelling random walks consistently perform better, providing more accurate estimates of the triangle graphlet concentration, and for some graphs the improvement is large. Alg. [5. can be generalised to estimate the concen- trations larger graphlets with k > 3; we anticipate that repelling random walks will still prove effective.
CONCLUSION
We have presented new quasi-Monte Carlo scheme called repelling random walks that induces correlations between the directions of random walkers on a graph. Estimators con- structed using this interacting ensemble guaranteed to remain unbiased but their concen- tration properties are often substantially improved. We test our algorithm on applications as diverse as estimating graph kernels, the PageRank vector and graphlet concentrations. In every case the experimental performance is very strong and often we are able to pro- vide concrete thcoretical guarantocs. We hope this work will motivate further rescarch on developing quasi-Monte Carlo methods to improve sampling on graphs

---

Published as a conference paper at ICLR 2024
7 ETHICS AND REPRODUCIBILITY
Our work is foundational with no immediate ethical concerns apparent to us. How- ever, increases in scalability provided by quasi-Monte Carlo algorithms could exacerbate existing and incipient risks of graph-based machine learning, from bad actors or unin- lended consequences.
Ethics:
Every effort has been made to guarantee the work's reproducibility. The core algorithm is clearly presented in Def. 2.1 Accompanying theoretical results are proved and discussed in the Appendices A..1 1AA.3 including any assumptions where appro- priate. Source code is available at lhtpps:/ buttps://itthb..e. /gtttut.ttcom/////m issaa-roid/repelling crooeeling_rrnddmm walks All datasets used correspond to standard graphs and are freely available online; give links to suitable repositories in every instance. Results are reported with uncertainties to facilitate comparison.
Reproducibility:
8 RELATIVE CONTRIBUTIONS AND ACKNOWLEDGEMENTS
IR. conceived and implemented the repelling random walks mechanism, derived the the- orctical results and prepared the manuscript. KC was crucially involved the project throughout, acting as the senior research lead. EB proposed the class of step-by-step linear functions and made important theoretical contributions. AW provided helpful discussions and guidance.
TR acknowledges support from a Trinity College External Studentship. AW acknowledges support from Turing Al fellowship under grant EP via CFL.
and the Leverhulme Trust
We thank Kenza Tazi and Austin Tripp for their careful readings of the manuscript, and Yashar Ahmadian for interesting discussions about the relationship with quantum entangle- ment. Richard Turner provided valuable suggestions and support throughout the project.
REFERENCES
Noga Alon, Itai Benjamini, Fyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster. Communiccations in Contemporary Mathematics, 9044):585 603, 2007. URL
Luigi Amico, Rosario Fazio, Andreas Osterloh, and Vlatko Vedral. Entanglement in many- body systems. Reviews of modern physics, 80(2):517, 2008. URL
1103/RevModPhya .0.880.111
Daniel J Amit, Giorgio Parisi, and Luca Peliti. Asymptotic behavior of the' true" self- avoiding walk. Physical Review B, 27(3):1635, 1983. URL https://doi.org: org. 1103/
PhysRevB.27 27.1635
Konstantin Avrachenkov, Nelly Litvak, Danil Nemirovsky, and Natalia Osipova. Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM Journal Numerical Analysis, (5(2):890 904, 2007. URL hattps://dl. acm..acmm...mmmmmmmmmmmm.mmm.... acm. wtg/doi///..1330333333 1137/
(050643799)
Luca Becchetti, Paolo Boldi, Carlos Castillo, and Aristides Gionis. Efficient semi-streaming algorithms for local triangle counting in massive graphs. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data måning, pages 16-24, 2008. URL https::/dddt
acm. http:///d..acc.oooo//////./oo 1145//401891 1401898
Karsten Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinfor- matics, 2 2005. URL https: //doi. arg/10. 10t.1//ioiofffrmaicccc.
bti1007
10

---

Published as a conference paper at ICLR 2024
Jun Chen. Two particles' repelling random walks on the complete graph. Electronic Journal of Probability, 19 (nnne): 17, 2014. doi: org/10. 1214/.121./JJ..... -19-vv1iv-000 2669
URL https://doi.
Xiaowei Chen, Yongkun Li, Pinghui Wang, and John Lui. A general framework for esti- mating graphlet statistics via random walk. arXiv preprint rrXii:1603.07500 2016. URL
https://doi.. org/org/// 10. 48550/ arrivv/ 1603. 07504
Krzysztof Choromanski, Mark Rowland, Vikas Sindhwani, Richard Turner, and Adrian Weller. Structured evolution with compact architectures for scalable policy optimization. In International Conference on Machine Learning, pages 970-978. PMLR, 2018. URL
https://doi. http:///oooorr////// 11111000/05////1111/ 16003000000
Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009.1479. 2020. URL
httts:://di.. wwt.ooo.g/..//..... 18550/arXivy 2009. 14794
Krzysztof M Choromanski, Mark Rowland, and Adrian Weller. The unreasonable effec- liveness of structured random orthogonal embeddings. Advances in neural in information processing systems, 30, 2017. URL https:://di..rgg:
48550/ aar5vv.rrxi...... 1703. 00864
Krzysztof Marcin Choromanski. Taming graph kernels with random features. In In- ternational Conference on Machine Learning, pages 5964-5977. PMLR, 2023. URL https://doi. org/10 10. 48550/arXiv 2305. 00156
Fan R. K. Chung and Shing- Tung Yau. Coverings, heat kernels and spanning trees. Electron. J. Comb., 6, 1999. doi: 10.37236/144 1444. URL https:://do..rg/// 371.///4443366/444444
Fan RK Chung. Spectral graph theory, volume 92. American Mathematical Soc., 1997.
Keenan Cranc, Clarisse Weischedel, and Max Wardetzky. The heat method for distance computation. Communications of the ACM, 60(11):90 99, 2017. URL https://dl. acm. http//////o.1115//133333
Michael Dawson-Haageery, Trimesh repository, 2023. URL https://ggithhb..cmmmkkkeee/eeee trimesh
Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the lenth ACM SIGKDD international conference on Knowledge discovery and dala mining, pages 551 551-556,
2004. URL httpps:/ddl acm.
org/doi/100 1111//111111111111 1014118
Persi Diaconis, Susan Holmes, and Radford M Neal. Analysis of a nonreversible markov chain sampler. Annals of Applied Probability, pages 726 226-752, 2000. URL https://doi.
org/10. 1000..114//00
Josef Dick, Frances Y Kuo, and Ian H Sloan. High-dimensional integration: the quasi- monte carlo way. Acta Numerica, 22:133-28 288, 2013. URL htdps:://ol...o 1rt./0..0/0001111111111 1017/
50962492913000044
Vishwaraj Doshi, Jie Hu, and Do Young Eun. Self-repellent random walks on general graphs achieving minimal sampling variance via nonlinear markov chains. arxiv preprint urXio:2305. 05097, 2023. URL https://doi.
48550/arXiv. 2305.05099
Dániel Fogaras, Balázs Rácz, Károly Csalogány, and Tamás Sarlós. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internel Mathemal- ics, 2(3) 358, 2005. URL https:://oi.orggr
1007 http:///000000000000000000000000
Vladimir Ivashkin. Community graphs repository, 2023. plivashkkin/commuittt.
URL http::://gtttub..oo com/
11

---

Published as a conference paper at ICLR 2024
Kyle Kloster and David F Gleich. Heat kernel based community detection. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 1386-1395, 2014. URL https:///oi.
(66500/axXiv 1403 1408.3148
Chul-Ho Lee, Xin Xu, and Do Young Eun. Beyond random walk and metropolli-hastingg samplers: why you should not backtrack for unbiased graph sampling. ACM SIGMET- RICS Performance evaluation review, 40(1):319 330, 2012. URL https://al. acm. org/
////10..144/2218887 2254795
Siqiang Luo. Distributed pagerank computation: An improved theoretical study. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4496-4503, 2019. URL httpss://oi. org/ 10. 1609/ aaai. v33101 v33101.33014496 33014496
Tijana Milenković and Nataša Pržulj- Uncovering biological network function via graphlet degree signatures. Cancer informatics, 6:CIN S680, 2008. URL https://doi.orr
48550/arXiv 0802.0556
Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. Network motifs: simple building blocks of complex networks. Science, 298 5594)): 824 827, 2002. URL httpp:///wat wwwpwwecieece.eem wwtp:///eoo////////oooo///////.. http://....1//////./
science 298. 824
Lawrence Page, Sergey Brin, Rajeov Motwani, and Terry Winograd. The pagerank cita- tion ranking: Bring order to the web. Technical report, Tochnical report, stanford Uni- versity, 1998. URL htthhhtpt:///tt wwwpwwww....o..w/..oo/wwwt...... upenn. edu/ http://mmeeetteeecccccc/c///eeee pagerank. pdf
Robin Pemantle. A survey of random processos with reinforcement. Probability Surveys, (none):1 - 79, 2007. doi: 10.1214/07-P5094
1214/07-5044
Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioin-
formatics, 23 2007. URL http::///doarrrgooo.//////////om bt1301
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. Advances in newral information processing systems, 20, 2007. URL https://dl.acn oow.cooorg/oo/.....
5555/2981562.2998 2981710
Isaac Reid, Krzysutof Choromanski, and Adrian Weller. Quasi-monte carlo graph random features. arXiv preprint arXin:2305.12477 2023a. URL. http:::://ooi.rr//1....
arXiv. 2305 2305.12470
Isaac Reid, Krzysztof Marcin Choromanski, Valerii Likhosherstor, and Adrian Weller. Sim- plex random features. In International Conference on Machine Learning, pages 28864- 28888. PMLR, 2023b.
48550/ arxiv. 2301. 13856
Rafacl A Rosales, Fernando PA Prado, and Benito Pires. Vertex reinforced random walks with exponential interaction on complete graphs. Stochastic Processes and their Applica- lions, 148:353-3733 2022. URL
orw..o...11.... 1016/ (00016/..sp. spa. wpp.p022...................... 2...203.2220.0000
Mark Rowland, Krzysztof M Choromanski, François Chalus, Aldo Pacchiano, Tamas Sarlos, Richard Turner, and Adrian Weller. Geometrically coupled monte carlo sampling. Advances in Neural Information Processing Systems, 31, 2018. URL https://dd acm. org/ brg/doi//dff /10. 00..5555/333333 3326962)
Mark Rowland, Jiri Hron, Yunhao Tang, Krzysztof Choromanski, Tamas Sarlos, and Adrian Weller. Orthogonal estimation of wasserstein distances. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 186-195. PMLR, 2019. URL https://doi. org/10 10. 48550/ atto0//rXivv.. 1903. 03784
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mchlhorn, and Karsten Borg- wardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009. URL attps://app) http::://pp....mmmmmoooo.oooooo semanticscholarr oorg///oarrrrr//
Cor5usID:11557614
12

---

Published as a conference paper at ICLR 2024
Alexander J Smola and Risi Kondor. Kernels and regularization graphs. In Learning The- ory and Kernel Machines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop, COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceed- ings, pages 144-158. Springer, 2003. URL. htttps:/peoppe.... www.pple.cs.uccccag..e..e..
Saperrs/SmolaKondor..
Pierre Tarrès. Vertex-reinforcel random walk on z eventually gets stuck on five points. The Annals of Probobility, 32(3))2650- 2701, 2004. ISSN 00911798. URL http://www: jstor.
org/stable/34811
Bálint Tóth. The" true' self-avoiding walk with bond repulsion on z: Limit theorems. The Annols of Probability, pages 1523-1556, 1995. URL https://doi.oom org/ 1214/ 1214/aop/
1176987798
Johan Ugander, Lars Backstrom, and Jon Kleinberg. Subgraph frequencies: Mapping the empirical and extremal geography of large graph collections. In Proceedings of the 22nd international conference on World Wide Web, pages 1307-1318, 2013. URL https://
doi. doi.org/ org/10. 10-4445550/KK50 1304. 1548
Feng Xia, Jiaying Liu, Hansong Nie, Yonghao Fu, Liangtian Wan, and Xiangjie Kong. Random walks: A review of algorithms and applications. IEEE Transactions on Emerging Topics in Computational Intelligence, 4(2):95-107, 2019. URL https://doi. org/ 10g/10. 10.
1109/TETON 2952998
Felix Xinnan X Yu, Ananda Theertha Suresh, Krzysztof M Choromanski, Daniel N Holtmann-Rice, and Sanjiv Kumar. Orthogonal random features. Advances in newral in- formation processing systems, 29, 2016. URL pattps://dot org/10. arg/10.48550//rr// 48550/arXiv..610 09072.
Yufan Zhou, Changyou Chen, and Jinhui Xu. Learning manifold implicitly via explicit heat- kernel learning. Advances in Neural Information Processing Systems, 33:477-44 487, 2020.
URL https://doi. otg//0../000 48550/ arXiv 2010.017611
Zhuojic Zhou, Nan Zhang, and Gautam Das. Leveraging history for faster sampling of online social networks. arXiv preprint arXiv: 1ee:1505.0000 00079, 2015. URL //ttps://dii.oo/ 10. 00.48550/ariiv 00079
13

---

Published as a conference paper at ICLR 2024
A APPENDICES
A.1 PROOF OF THEOREM 3.1 (SUPERIORITY OF REPELLING RANDOM WALKS FOR KERNEL ESTIMATION
In this appendix, we prove Theorem 3.1 namely, that using transient repelling random walks reduces the mean square error of graph random feature (GRF) estimates of the 2- regularised Laplacian kernel, defined by:
K lap ij = (I- - -(+0)))
o² 1 ( W
(1
I
(11)
where L is the Laplacian, is regulariser and W is normalised weighted adjacency matrix with elements w ( 4,j=1 (with d; - -, aij the degree of the ith node and dij the weight of the edge before normalisation). Ignoring the overall normalisation constant and absorbing the factor of o2/(11+ + o²) into W, wlg we will now consider estimation of
Rij (I wW
(12)
where W [usy] juyyly-r
Directly from the definition of the GRF vector (see e.g. Choromanski 2023 2023a ) we have that
(Reid et al.
x(wiz) إميياق) N (wise N (Wjzz
Kyy = =00 o(j)
Σ Σ
Σ
(13)
m TEN wis
p(wi)) p(wja)
El wyx EQ
where
(ww+)= I E 41).
(14)
Here: m E N is the number of random walkers simulated out of each node; Daz is the set of all walks on the graph between the nodes indexed and æ; wis is a member of this set; ((w) is a function that returns the product of weights of edges traversed by graph random walk w; and p(w) is a function that returns the marginal probability
random walk (equal to ((1 -P)/d) len(w) - with < < 1 a finite termination probability, d the node degree and (w) the walk length in the case of a d-regular graph). Ω denotes the (th walk out of node such that N(wzz) counts the empirical number of walkers completing a particular prefix subwalk Win, discrete random variable between 0 and m. Since E ((iz)) mp(wsz), it straightforward to see that
B(o(i) o()) = Σ Σ
BWwi (Wija))
FEN Elt wg
(15)
Σ (len(wi))) + 1)w(w;)) = (--W)-
which confirms that the estimator is unbiased. Our task is now determine how the variance of Kiy depends on whether the ensemble m walkers from each node is i) independent or ii) repelling. We will see that, under some conditions, it is guaranteed to be smaller in the latter case.
The following is true:
((مما)) ((wاا) B(N(win ((Ww))) plwsze p(w3y
E
m
(16)
x(wلz) xموواق E(N (w (
Σ
p(wjz) p(wjy)
14

---

Published as a conference paper at ICLR 2024
This makes clear that the object of central importance will be
E (N
(17)
where 2, E N. We will now consider how this depends on the pair of subwalks (wiss wiy and ii) the presence or absence of repulsion.
To avoid notational clutter, will write expressions if the graph is d-regular with the undcrstanding that it is trivial to relax this without changing any conclusions, making the replacement: den(wwe)) + I (on(urr))1 dç.
i.i.d. walkers: Begin with the simpler i..dd case. First consider the case that Win * ways Wir é wiy and Way & wast namely, that the walks are distinct and neither is a (strict) subwalk of the other. It follows that single walker cannot take both subwalks simultaneously. We also assume that both walks are of length len (wi(z.))) 2 1. Then we have that
E (WWWl E
Σ
Ilwia E Pt, )a(wey Sunl))
(18)
1 1- len(wra) (lem(rr))
=m(m- 1)
What about wis E way? is straightforward convince oneself that
len(wss +len(way)
1- len(wsy)
(1-P)
E [[N(we)) = m(m-
+ m
(19)
where the extra second correlation term comes from a single walker completing both sub- walks. Lastly, suppose that len(wiz) = (i.e. one of the subwalks has zero length). Then we have that
len(wey)
E (N((a))) m² (1-2)
(20)
Now we move onto the repelling case, which is substantially more difficult.
Repelling walkers: For tractability, we will consider the transient repulsion scheme de- scribed in Def. [2.2] Suppose that we have N2 walkers at some node indexed a * i, with the set of neighbouring nodes including nodes labelled 3 and (i.e. 8, E (aa)). An important quantity
B(NgN,IN
(21)
From Def. 2.1 we have that
N3 No//d +11,
N₂ = No/
(22)
where // denotes truncating integer division 61,2 are anticorrelated binary random vari- ables. The reason they are anticorrelated is that walker that transitions to B cannot also transition to 7, With a little work, one can convince oncself that
No 2
R
R-1 R d). d
R
I(N
(23)
where R= N/. %dd the remainder after the the walkers have been partitioned into blocks of that will be concerned with the statistics of N in
size d. From this form, particular how E(N."² (2) behaves. Understanding this is our next task.
Let N₂ be a random variable denoting the number walkers at node a of some particular walk the graph. Then let N2 denote the number of walkers surviving the 'p-step', where each walker terminates independently with probability Let N₃ denote the number of walkers that subsequently hop to node 3 the walk. It is clear that N₂ = N//d++ e, with
15

---

Published as a conference paper at ICLR 2024
random variable that takes value of with probability & and 0 with probability - R It is simple to show that
B(N 3 1
R
R d
B(N
+ E
-
(1
(24)
d2
It is also trivially the case that IE( o
= E(N, (1 - p)² + B(N, (1 pp) (law of iterated
expectations). The second term in Eq. 24 is generically difficult to describe analytically, but it is simple in the special case that No < d so R = Na. In particular, here we have that len(
B(N2) = =B(N.) ( = m
P d
(25)
whereupon, referring back to Eq. 23
B(N&N,ING) O.
(26)
It is trivial to see why this must be the case: supposing we begin with fewer than d walkers at node i, in the transient repelling scheme they all diverge at the first timestep. Any subsequent node its da neighbours at random, so value of NgN, (product of occupations its child nodes) always vanishes. It is encouraging that algebraic approach reproduces this intuitive result. It follows immediately that, for walks diverging at some node not equal to the starting node i, IE
some walk is occupied by most walker which chooses one of
0. 0.
What about if the walkers instead diverge at i? Here the result is different because E(N,) = m, the initial number of particles, and Var(m) since the total number of walkers fixed hyperparameter. After just little work,
(1 - p) B(NgN7) = d(d 1)
m(m 1)
(27)
and therefore
lon (nn (en((w))))
E ((xi)) d - m(m 1) (1-P) d
(28)
This is also intuitive: the repelling scheme shifts probability mass onto walks that diverge at i, enhancing this correlation term.
The subwalk case also straightforward. Supposing Win E Wigs we can use Eq. 25 to show that
len(wry)
E (N(wx)
(29)
d
because if the walkers immediately diverge then we can only sample both why and Wir E Wiy a single walk traverses both. Lastly, if len(wix) = 0, we still have that
len(wi))
= m² (²a²)
E (N
(30)
which is natural because one (or both) of the walks of zero length then the repulsion scheme cannot modify the correlation term.
We summarise these observations Table 3 denoting c= 1-p and Wir as shorthand for len(w))) for compactness.
Table 3
Class
E ((N()))NN(
i.idd
transient repelling
Same walk, Wiz Wig Subwalk, Wir E way Different walks, diverge Different walks, diverge at d o Jen(wi.)
me m(m 1) me + m(m 1) tatt
m m
m(m 1)0 twyy
mmm (m 1)
m(m 1) m 2
0
16

---

Published as a conference paper at ICLR 2024
More explicitly, we write
m(m - 1) 1) twiy
twiy T(both > 0)
+l (ssubwalks, both 0)
if.d.
+m² Chaoeer I(len 0)
((N (wig))
(31)
di d
m(m- 1) + I(both 0, div at
if repelling
+ocehonge Ussubwalks, both 0)
+m² chooger I(len 0)
where only the first term differs. Here, I(both > 0) means both walks traverse at least one edge, I(len 0) means one of the walks is of length I(subwalks) means Wis Wiy (or vice versa), and Wlonger denotes the length of the longer walk. We will now insert these expressions into Eq. 16 to compute the difference in variance of Kiz with the two possible coupling schemes.
After tedious but straightforward algebra, we arrive at the following closed form:
Var
Rey
Var
([Rs))
L.a.
repelling
(m 1)²
W
m²
w)2
(a)
d:d,
(m 1)²
Σ
Σ
War W
(d. ()
m
W)
(1
w)²
MENU ""M(G
MeNU PEENGY
+ d;
m
((win) )
[B(x,]) - -C(,,)))
m
((wax)
I Wix
d3
(w
[B(r, 1) - C(
(b)
dj
m²
p(wjjz)
m 1
d, (B(j,) c(i.
d: (B
C(i,)))
m
d
(32)
where
B(x,1)= Σ
wif
1
1
Wiy
(33)
(1 w
w)2
(EN(()
and
2
W
W
C(r,i)= = Σ
Σ (EE(()
Wiy
(34)
W)
ae d,
PEN())
Note that both B and C are always positive by Jensen's inequality. It is remarkable that such a simple expression exists for the difference in kernel estimator variance between the ii.dd and transient repelling schemes.
Showing the class of graphs for which this is guaranteed to be positive a challenging open problem, but we are able to make progress in some tractable special cases.
For instance, consider the limit w with all the graph weights equal, W WA. In this case, when computing matrix elements we can just retain terms corresponding to the shortest path. For example,
=[1+ 2wA + 3wFA² ..]G, M(4))( + 1) + O(w
(35)
(1 [A=
17

---

Published as a conference paper at ICLR 2024
where 45 denotes the length of the shortest path between nodes i and and M(4y) denotes its maltiplicity: the number of such unique paths that exist in G. To give examples, for a tree M (4gg = 1 and for a square grid M (4g) = (u+h),, where a the difference in x-coordinates of nodes i and j and 6 is the difference in y coordinates.
When will (a) be positive? Provided that nodes and j are separated by at least edges, the following is true:
2
(m 1)²
2
A
(m 1)²
M(h,)
1) 2(;tt))))
(36)
m2
WAy
m²
and
d.d,
(m 1)2
Σ
Σ
(d. [)(d, -
m²
wA ve'' 115"
WA
(CMG))
d,dj
{m - 1)2
Σ
Σ S'ENG)
to (lag + 1)(ggr + 1)
(d. - 1](d, -1
m²
JENG MENOW
J'NON"
+w
(37)
Note that, since i' (i)) and j' ()))), it is trivially the case that 4ij - 10 S lig + 2. In Eq. 37 only terms where by Lorg bi - 2 will give contributions of the same order as the leading term O(w2ly) in Eq. 36 The condition that Eq. 36 is greater at the leading order is then:
d,dj
M(L)2 (d: -
E SNNW '2g1=lergr
M(kr)) (38)
(dd) (dd,--11) 1)
where we remind the reader that M (4:) denotes the degeneracy (number) of shortest paths (of length 4y) between nodes i and This encodes the topological constraint that is sufficient for variance reduction with repelling random walkers on an equal-weights graph as - O. Heuristically, the set of nodes Miii cannot be too connected to the nodes Mj)..
A cursory numerical check suggests that Eq. 38 is not generically satisfied for every pair of nodes (i.j) on arbitrary graphs, but it does seem to very often be true. We can, however, identify some particular examples where it is guaranteed to hold. For example, it is trivially true for trees for which M(1,,) 1 but the RHS is 0. To wit: for trees there is a unique shortest path between nodes i and and it is only the case that by = Li - 2 if both i' and j' lie on this path. Then conditioning that i" + and j" A j' means that we cannot fulfil 1yrg" = 45- - 2. whereupon the sum is over the empty set so evaluates to O. It is also true for the two dimensional square grid. Without loss of generality, locate node at coordinates (0, 0) and node j at (a, b). If a = 0 or 6 = 0 there is a unique shortest path so the inequality follows trivially. If 1 then M (4,,)
6 + 1 whereas the RHS evaluates to 2 (d/(d- 1))² which is smaller for 6 2 and d 4. Finally, if a, 1, then M(4y) (*+h)) (a walker on a shortest path between nodes i and j must take steps in one direction and steps in the other, but we are free to permute their order). Mcanwhile, the sum on the RHS of Eq. 38 evaluates to:
2 aa (1 ?)
aa (a+b-2) 2) b b-2 9) + a (a+b- 2) 2)
(a+b-2)²
- )
8-1
2.
(39)
whereupon the ratio RHS/LHS is:
2 ala 1)b(b 1) + 1212
d
((a + () b
1))² 1
(40)
2ab
a(a - 1) b(b b(b- 1)
d
(a b)²
(a - (a-1)(b-11-
18

---

Published as a conference paper at ICLR 2024
The expression in square brackets is greater than 1 so its inverse is smaller than 1. Hence, is sufficient that
(a + b)
(a b) +22
(41)
2ab
2ab
d
which is trivially always true for d 4. The inequality in Eq. 38
then holds in all cases
where nodes and j are separated by at least 2 edges, so terms on two-dimensional square grid.
will indeed be positive
Having asserted that the terms labelled (a) in Eq. 32 will sum to positive value under cortain conditions (namely: graphs characterised by Eq. 38 with equal edge weights w + 0, considering nodes and j separated by at least 2 edges), we now proceed to consider the terms labelled (b).
When will (b) be positive? Now we consider the remaining terms involving c.g. B(z, i) C(r, i) where z, i E N. These demand little more care because the sum over x E W means that we need to account for terms where even when considering off-diagonal terms of the kernel estimate i j. Note that
B(r, i) Varrev)) [(1 (1)
(42)
the empirical variance of the matrix elements Kep among the set of vertices i' that neighbour
Denote by ini the smallest walk length for which the variance of the number of walks from x to the set of nodes (t)) is nonzero,
Tx = min ((l VarreN(o) (A * #0))
(43)
IEN
This might well correspond to the shortest path between I and E -ii,,, but this not necessarily the (i.e. if all the neighbours i' have equal number of equally short paths to x so the variance on this quantity vanishes). Then we have that
B(x, du Varvento [(1 wA) " =d(zzi + 1 2he VarveNto and
(wolbrrt) (44)
A
C(x, d, VarveNi [WA(1 =A) = 22 Varveni A + O(w (45)
where VarveN()) in - - and VarreN()
denotes this first nonvanishing variance. For trees with o # i,
d-1 dz
To lcading order in w, it trivial see that B(x, > C(x, Insorting back into Eq. 32 and noting the positivity of the prefactor a(w:.) p(wia,, the positivity of (2) follows. Note that in this section we have not assumed anything about the structure of G beyond equal weights and w + 0. The topological constraints originate solely from the terms in (a).
Combining the above arguments, conclude that the using the transient repelling scheme is indeed guaranteed to suppress the variance of kernel estimators K, for nodes and separated by at least edges under certain conditions: namcly, that we have an equally- weighted graph with the case for e.g. trees and two-dimensional grids). D
0, and that the topological condition in Eq. 38 is truc (which is
We stress that, in practice, the scheme performs very well even for much more general classes of graphs and in the non-asymptotic w limit. We defer extending the proof above to include these cases as future work.
A.2 PROOF OF THEOREM 4.2 PAGERANK ESTIMATION
(SUPERIORITY OF REPELLING RANDOM WALKS FOR
In this appendix, show how random walks can be used to estimate the PageRank vector and prove that using a transient repelling ensemble reduces the estimator mean square error (Theorem 4.2
19

---

Published as a conference paper at ICLR 2024
Our intention is to estimate the vector n,, defined as the stationary distribution of the transition matrix P defined in Eq. 6 and reproduced below:
p= (1 p) P
E
(46)
N
The reader should refer back to Eq.
6 for all symbol definitions. We then require that
π π
π I =111.
(47)
Rearranging and Taylor expanding that the solution is given by
2, it is straightforward to convince oneself (1- P1) -,
P T. N JEN k=
P)
(48)
This is nothing other than sum over all walks w/ from each of the graph nodes j to node i, each weighted by factor of (zze)* k p (with d generalising to the product of node degrees along wiss if the graph is not d-regular) and normalised by the number of vertices N. Equivalently, supposing we simulate a random walk out of a random node on the graph j. it is the probability that it terminates at node i. This invites the algorithm proposed by We construct the unbiased estimator
Fogaras et al. (2055) and shown in Alg, 4.1
EE JEN
terminates at node i]
(49)
where 225)
denotes the /th walk (out of a total of m E NN simulated from node j.
Our task is now to consider the variance properties of the estimator â when ensembles of walkers out of each node are either i) independent or ii) repelling according to our QMC scheme defined in Def. 2.1 Evidently,
m7
Σ
ΣE
(TO terminates at node i T[O terminates node }1}
22
JEJIEN 111==1
(50)
By construction, only walkers out of the same node are correlated: we simulate repelling
ensembles out of every vertex but a pair of walkers coming from different vertices remain independent. throughout. Therefore, is sufficient to consider the behaviour of terms ji = jz. In particular, we we need to determine whether the value of
T1o terminates at node i T[2 terminates at node }1}
(51)
suppressed with repelling random walks for fixed arbitrary j E N. We will refer this as the corvelation term.
First consider the special case f so all walks are of length least 1. We also consider transient repulsion (sce Def. 2.2 so that walkers only repel at the first timestep: the full- repelling scheme is empirically effective but difficult to reason about analytically.
For i.idd. walkers, the correlation term in Eq.
51 evaluates to
p² (1 2)²
P 1-
p
Σ
Σ
P
1-
1 (1
P)
J'ENG))"ENT))
j"l
(52)
At the first timestep, a pair of repelling walkers are either assigned to the same 'block' (see Fig. [1 different 'blocks' with probability that depends the number of walkers and the degree the first node dy. The correlation term in Eq. 51 depends on its evaluations conditioned each of these two events, weighted by their respective probabilities.
the pair are assigned to different blocks their dynamics are i.idd. so the correlation term is unmodified. Meanwhile, if they assigned to the same block (which happens almost.
20

---

Published as a conference paper at ICLR 2024
surely if m 1 dj), then the equivalent term evaluates to
p² ((77))
dj
E E P1PP1
1
(53)
p)P
J'ENG)J"NNNN
j's
This differs from Eq. 52 in that i) the variable j" in the sum over the neighbours of j can no longer be equal to since the walks repel, and ii) there is an extra factor of - to account for the increase the conditional probability of choosing j" given that j' becomes excluded when the first walker picks it ('without replacement').
Denote the matrix element i(i, = 1-(1-)PP Then the difference between the terms in Eqs
52 and
53
is equal to
p²
((T))
ΣΣ S0'"00"'
dj
Iído not share first edge)
(54)
dj
dj
This can be rewritten
p²
p
d
Σ E
f(',))
[(share first edge)
dj
dj
- 1
dg.
j'mj j"mnj
(55)
1
_ 0
p² (1
p)
f('
dj
dg
where we used Jensen's inequality.
To complete the proof, we also consider the subcase i j. For L.dd. walkers, the correlation term evaluates to
2
(1 - p)P
=p
(1 - P
1- (1 P
(56)
P
2
=p² 1+ 11+2(1-2)
+ 2)
1 (1-
1-
For repelling walkers in the same block, we need to consider contributions from i) both walkers terminating immediately, ii) one terminating and one leaving then returning to and iii) both walkers leaving (to different neighbours (i' * i") then returning to i. Enumerating these possibilities, we get:
P
p²
2 p)
(1
P
(57)
(1-P) dj
2
d
E
Σ
Σ
1 (1 (1- P
d,
I- (1 P)P
(EN()) PENOW
Only the final term differs compared to Eq. 56 It is of precisely the same form considered above with = j, so we immediately deduce that it is smaller with repelling walkers the same block. It follows that when j repelling random walkers also yield lower variance estimators セ/-
We have now considered the cases where the pair of walkers are in either different blocks or the same block, including the sub-cases i * and i i= and proved that the variance of the estimator a is the
reduced in both cases. The proof is complete. O
A.3 PROOF OF THEOREM 4.4 REDUCED BY TRANSIENT REPULSION)
(VARIANCE OF STEP-BY-STEP LINEAR FUNCTIONS IS
In this section, supplement the discussion at the end of identifying general class of functions whose variance is suppressed by conditioning that random walks exhibit transient repulsion.
21

---

Published as a conference paper at ICLR 2024
Following Def.
let 2r denote the set of all infinite-lnngth walks starting at node r, U0 T, U, E N, (o,, U441) E E}. Recall that we refer to a function y 22 - R as step-by-step linear if it takes the form:
4.3
Or == {0
v(w)= - Σ ((v,, I(
(58)
An example of such a function provided by Φ())). the k-th component of the graph random feature corresponding to node i, for which (V,,, T(u = k) and 9(1)-1, V.,
-yy-,,,,---114 > p)- Here, Way 1. is the weight of the edge (1z-1, E, duy is the degree of the node fj-1 and tj ~ Unif(O, 1) is a termination random variable which controls whether the walk ends at the jth timestep. Another example is provided by the kth component of the PageRank vector estimator Ty. in which case f(u;, 2) = I[u = k)I(t, > p) and ((1)-1,9..... 1) I(tz-1 < p), ensuring that y(w) evaluates to if the walker terminates at node & and is zero otheeeise.
1-p
In Theorem 4.4
asserted that, for the estimator Y Ei y(us) (where {ux) enu- merates m (ifinite) walks on 9 and y: Ω - R is a step-by-step lincar function),
reppolig)) S Var(Vi....) This is proved as follows. Begin by writing
(59)
00
)(w(())= f(vo. 0) Σ (k)
flu
II F=1
(K) (1) 1..-- - 1)= f(vo. 0) + (10 ) 1u ..j
(60)
with k- = [1, Note that we took %/ up node, and introduced the function to simplify notation.
since the walkers begin at the same
As in Sec. A.2 pair of walks may be either assigned to the same block or different blocks (see Fig. Lp. We focus on the former case since in the latter they are i.i.d. and the variance of the estimator is trivially unchanged. This means that our walkers diverge at the first timestep, "1
(1) o of2). It follows from the definition of transient repulsion that the random
variables h(((;; (k) )2=))) are conditionally independent given (1) (2) since at this point the walkers stop repelling. Moreover, since in both cases the marginal distribution over is identical, for Var(Y) to be reduced by repulsion we just require that
Eri.a.
[n
((r(2) ((())=a)]] Erop [n
((f)))
(61)
In the i.i.d. scheme, Ui and v/ are independent and are uniformly distributed among the set of neighbours NVvo,, each with probability 1/do- Meanwhile, in the repelling scheme, (u) (2)) is uniformly distributed among the set {(v,, 1y)) 2, E eN(ep), & 1j} i.e. all
do 1) possible pairs of distinct neighbours of node vo. Then Eq. 61 evaluates to
1
Σ
Σ MeNeo (PEENT
E(h ( (((ee))))))) 2
(62)
do(do - 1)
( EANo)
where we used that (1.2) are conditionally independent given of (1.2) Rearranging, this expression is nothing other Ihan
Var (e (E(hlo1)) 20
(63)
dg
where the variance is being computed over the dg nodes that neighbour Vo- Eq. holds, confirming that Var(Yrepelling) < Var(Yi.a.) O
63
trivially
Note that Theorem 4.4 does not obviate the long proof in Sec. A. suppressing the variance of the GRF coordinate Φ(t),, i, k E N is not sufficient to conclude that the variance of the dot product K, d(i) T(j) is also reduced since now we need to consider correlations between @i)),, and o()),, with k # k2- On the other hand, it does subsume Theorem 4.2 as special case, though we keep this section in the manuscript for clarity of presentation.
22


Reviews:
[{"review_id": "OtROSlBWkL", "reviewer": "Reviewer_1jyG", "summary": "In this paper, the authors present repelling random walks to sample from a graph. In some examples, theoretical results about the improvement on the concentration of estimators and numerical experiments about efficiency in sampling are given. Both theoretical and numerical results look sound.", "questions": "Q1. Is it possible to give a more explicit relationship comparing the variances of estimators between the classical and the new method?\n\nQ2. Ideally I would like to see some basic properties or results concerning the repelling random walk in Section 2 before diving into the applications.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. A novel quasi-Monte Carlo algorithm called repelling random walks is given. \n\nS2. Results on typical examples are given to illustrate the new algorithm.", "weaknesses": "W1. Theoretical results only show that the new variance of estimator is less than classical method, but the author can give a more explicit quantitative analysis of how small it can be.\n\nW2. As to the efficiency in sampling, only numerical results are given, which weaken the solidity of the improvement brought by the new algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kjBLNn9Mnp", "reviewer": "Reviewer_KSvf", "summary": "This paper presents a novel quasi-Monte Carlo mechanism called repelling random walks. The authors demonstrate that the marginal transition probabilities of repelling random walks remain unchanged compared to standard random walks. In particular, the paper proves that the variance of approximate random walk probabilities is suppressed by simulating repelling random walks. The paper showcases the effectiveness of repelling random walks by applying them to three distinct tasks.", "questions": "Q1. The experimental setups presented in Table 2 lack clarity. The paper indicates that 1000 trials are conducted on each graph, with more than two repelling random walks simulated during each trial. Could you specify the exact number of standard and repelling random walks simulated for each graph?\n\nQ2. In Table 2, could you please indicate the minimum node degree for each graph?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "S1. The paper introduces a novel quasi-Monte Carlo mechanism, repelling random walks, aimed at enhancing graph-based sampling. This approach could potentially inspire further research in this field.\n\nS2. The marginal transition probabilities of repelling random walks remain unchanged, while the variance of these walks is reduced.", "weaknesses": "W1. The advantage of using repelling random walks over standard random walks appears to be marginal. For instance, the reduction in approximation errors when estimating PageRank using both standard and repelling random walks as shown in Table 2 is relatively minor.\n\nW2.  The validity of certain arguments is heavily dependent on specific assumptions. Take Theorem 4.2, for example: its accuracy hinges on the assumption that the count of random walks is less than the minimum node degree in the provided graph. Nonetheless, in a variety of real-world network structures, the minimum node degree stands at one, rendering repelling random walks virtually indistinguishable from standard random walks. \n\nW3. The paper's presentation needs improvements. The current manuscript contains ambiguous sentences and unclear notations. For instance: \n- Page 2: the notation $P^{(i)}$ requires clarification, as the paper defines $P$ but not $P^{(i)}$. \n- Page 3: the notation $i_1$ and $\\delta_{i_1}$ require clarifications. \n- In the appendix on Page 20: the reasoning behind the statement \"only walkers originating from the same node are correlated\" requires additional explanation.\n\n--- \nDuring the rebuttal phase, the authors and I engaged in detailed discussions regarding the novelty and contributions of the paper. I appreciate that the authors have effectively addressed the issue related to the minimum node degree assumption (i.e., W2). We also had a thorough discussion about the fundamental differences between Repelling Random Walk and Radar Push, a closely related work. The authors' responses were not only prompt but also convincing. Consequently, I have decided to revise my initial score from 5 to 6.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CIs8wFajQL", "reviewer": "Reviewer_vsCv", "summary": "This work introduced a repelling mechanism among walkers in a graph when doing MC simulation. The proposed sampling mechanism is easy to understand. And intuitively it makes more sense than iid sampling by considering the graph topological property. Experiments are conducted on three graph-related tasks. Results also verified its better performance than the iid baseline", "questions": "Overall, this is a good paper with both solid theoretical analyses and experiments on various tasks. However, some concerns are: \n\nC1. Random walk is one of the important research topic in graph, the fundamental research is worthy of applause. Random walk related approaches have also be applied in downstream tasks in the real-world applications, such as graph embedding and community detection. However, the focus of this paper seems to be more fundamental. Random walk theoretical research usually fits better in venues like graph theory (lean more on mathematics) and computing theory (e.g., STOC). So I have concern on audience interest for ICLR. \n\nC2. More real-world related applications are expected. The authors applied the proposed random walk mechanism in three applications. But the three seem to be more abstract than those driven by real-world applications or hot topics in the current research community. For example, graph kernel approximation covers one major category of approaches for graph embedding. PageRank vector approximation is also one of the fundamental problems for graph embedding and community detection. Graphlet detection is used in subgraph representation. Compared to the three in this paper, graph embedding, subgraph representation, and community detection may be closer to real-world scenario. In recent 10 years, deep learning approaches attract more attentions in almost every research field. If the fundamental research like this paper can show enhancement against recent so-called advanced methods or benefit the recent popular approaches, that would be more exciting.\n\n=================\n\nAfter reading the authors response where more examples were involved. The response address some of my concerns. But more real-world related applications are expected (C2 in my review) in this paper. \n\nAs a result, I increased my score.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. A more vivid random walk mechanism with considering graph topological property\n\nS2. experiments on three graph tasks to show the advantage of the proposed\n\nS3. Solid theoretical analyses", "weaknesses": "W1. concern on the audience interest\n\nW2. more interesting downstream applications are expected", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)