Graph Traversal with Tensor Functionals: A Meta-Algorithm for Scalable Learning
Authors: Elan Sopher Markowitz
Keshav Balasubramanian
Mehrnoosh Mirtaheri
Sami Abu-El-Haija
Bryan Perozzi
Greg Ver Steeg
Aram Galstyan
Venue: ICLR 2021 Poster (2021)
Keywords: Graph
Learning
Algorithm
Scale
Message Passing
Node Embeddings

Abstract: Graph Representation Learning (GRL) methods have impacted fields from chemistry to social science. However, their algorithmic implementations are specialized to specific use-cases e.g. "message passing" methods are run differently from "node embedding" ones. Despite their apparent differences, all these methods utilize the graph structure,  and therefore, their learning can be approximated with stochastic graph traversals.  We propose Graph Traversal via Tensor Functionals (GTTF), a unifying meta-algorithm framework for easing the implementation of diverse graph algorithms and enabling transparent and efficient scaling to large graphs.  GTTF is founded upon a data structure (stored as a sparse tensor) and a stochastic graph traversal algorithm (described using tensor operations). The algorithm is a functional that accept two functions, and can be specialized to obtain a variety of GRL models and objectives, simply by changing those two functions. We show for a wide class of methods, our algorithm learns in an unbiased fashion and, in expectation, approximates the learning as if the specialized implementations were run directly.
With these capabilities, we scale otherwise non-scalable methods to set state-of-the-art on large graph datasets while being more efficient than existing GRL libraries -- with only a handful of lines of code for each method specialization.

Published as a conference paper at ICLR 2021
GRAPH TRAVERSAL WITH TENSOR FUNCTIONALS: A META AEGORALGO FOR SCALABLE LEARNING
Elan Markowitz :12, Keshav Balasubramanian Mehrnoosh Mirtaheri .1,2 Sami Abu-El-Haija 1.122
"Equal Contribution
'University of Southern Californi,, PUSC Information Sciences Institute
Bryan Perozzi
Google Research
Greg Ver Steeg! Aram Galstyan
ABSTRACT
Graph Representation Learning (GRL) methods have impacted fields from chem- istry to social science. However, their algorithmic implementations are special- ized to specific use-cases e.g. message passing methods are run differently from node embedding ones. Despite their apparent differences, all these methods uti- lize the graph structure, and therefore, their learning can be approximated with stochastic graph traversals. We propose Graph Traversal via Tensor Functionals (GTTF), unifying meta-algorithm framework for easing the implementation of diverse graph algorithms and enabling transparent and efficient scaling to large graphs. GTTF is founded upon data structure (stored as sparse tensor) and a stochastic graph traversal algorithm (described using tensor operations). The algorithm is functional that accept two functions, and can be specialized obtain a variety of GRL models and objectives, simply by changing those two functions. We show for a wide class of methods, our algorithm learns in an unbi- ased fashion and, in expectation, approximates the learning as the specialized implementations were directly. With these capabilities, non-scalable methods to set state-of-the-art on large graph datasets while being more efficient than existing GRL libraries with only a handful of lines of code for each method specialization. GTTF and its various GRL implementations are on: ltttps://
scale otherwise
INTRODUCTION
Graph representation learning (GRL.) has become an invaluable approach for a variety of tasks, such
as node classification (e.g., biological and citation networks; Veličković et al. (2018); Kipf & WWlling 2017);; Hamilton et al. (017);; Xu et al. (2018)), edge classification (c.g.. link prediction for social and protein networks; Perozzi et al. (2014); Grover & Leskoved (2016)). entire graph classification (e.g., for chemistry and drug discovery Gilmer et al. (2017): Chen et al. 2018a)) etc.
In this work, we propose an algorithmic unification of various GRL methods that allows us to ce-implement existing GRL methods and introduce new ones, in merely handful of code lines per method. Our algorithm (abbreviated GTTF, Section 3.2). receives graphs as input, traverses them using efficient tenso ooperations and invokes specializable functions during the traversal. We show function specializations for recovering popular GRL methods (Section 3.3). Moreover, since GTTF is stochastic, these specializations automatically scale to arbitrarily large graphs, without careful derivation per method. Importantly, such specializations, in expectation, recover unbiased gradient estimates of the objective w.r.t. model parameters.
'To disambiguate: by tensors, we refer to multi- multi-dimensional arrays, as used in Deep Learning literature; and by operations, refer routines such matrix multiplication, advanced indexing, etc.

---

Published as a conference paper at ICLR 2021
1
0
2
3
1
1
1
4
2
3
1
1 3
[2]
(a) Example graph G
(b) Adjacency matrix for graph G
(c) CompactAdj for with sparse A z and dense Z We store IDs of adjacent nodes A
Walk Forest. GTTF in- vokes AcCUME T. TRFN once per (green) instance.
Figure 1: (c)&(d) Depict our data structure & traversal algorithm toy graph in (a)((b).
GTTF uses a data structure À (Compact Adjacency. Section 3.1 a sparse encoding of the adjacency matrix. Node e contains its neighbors row A[v] & Ag, notably, in the first degree(v) columns of A[u]. This encoding allows stochastic graph traversals using standard tensor operations. GTTF a functional, as it accepts functions ACCUMULATEE? and BIASFN, respectively, to provided by each GRL specialization to accumulate necessary information for computing the objective, and optionally to parametrize sampling procedure p(v's neighbors v). The traversal internally constructs walk forest part of the computation graph. Figure deppicss the data structure and the computation. From a generalization perspective, GTTF shares similarities with Dropout (Srivastava et al. 2014).
Our contributions are: (i) A stochastic graph traversal algorithm (GTTF) based on tensor operations that inherits the benefits of vectorized computation and libraries such as PyTorch and Tensorflow. (ii) We list specialization functions, allowing GTTF approximately recover the learning of a broad class of popular GRL methods. (iii) We prove that this learning unbiased, with controllable variance. Wor this class of methods, (iv) show that GTTF scale previously-unscalee setting the state-of-the tate-oof-hhe-at on a range of datasets. Finally, (v) we open-source GTTF along with new stochastic traversal versions of several algorithms, to aid practitioners from various fields in applying and designing state-of-the-ard GRL methods for large graphs.
GRL algorithms,
RELATED WORK
We take a broad standpoint in summarizing related work to motivate our contribution.
Models for GRL have been proposed, including message passing (MP) algorithms, such as Graph Convolutional Net- work (GCN) (Kipf & Welling 2017), Graph Attention (GAT)
Learning
Family
Scale
(Veličković et al. 2018); as as node embedding (NE) algo- rithms, including node2vec (Grover & Leskovec) (016). WYS
Method
Models
(Abu-El-Haija et al. 2018);; among many others (Xu et al. 2018 Wu et al. 2019 Perozzi et al. 2014). The full-batch GCN of
GCN, GAT
MP
X
exact
node2vec
NE
approx
Kipf & Welling (017)) which drew recent attention and has mo- tivated many MP algorithms, was not initially scalable to large graphs, as it processes all graph nodes at every training step. To scale MP methods to large graphs, researchers proposed Stochastic Sampling Methods that, at each training step, as- semble batch constituting subgraph(s) of the (large) input graph. Some of these sampling methods yield unbiased gradi- ent estimates (with some variance) including SAGE (Hamilton) et al. 2017). FastGCN (Chen et al. 2018b) LADIES (Zuu et al. 2019). and GraphSAINT (Zeng et al. 2020). On the other hand. ClusterGCN (Chiang et al.) 2019) is heuristic in the sense that, despite its good performance, it provides no guarantee of unbiased gradient estimates of the full-batch learning. Gilmer et al.) (2017) and CCamii et al. (202I) generalized many GRL models into Message Passing and Auto-Encoder frameworks.
WYS
NE
x
exact
Stochastic Sampling Methods
SAGE
MP
approx
FastGCN
MP
approx
LADIES
MP
approx
GraphSAINT
MP
approx
CluterGCN
MP
heuristic
Software Frameworks
PyG
Both inherits re-
DGL
Both implements
Algorithmic Abstraction (ours)
GTTF
Both V/ approx
2

---

Published as a conference paper at ICLR 2021
These frameworks prompt bundling of GRL methods under Software Libraries, like PyG (Fey & Lenssen 2019) and DGL (Wang et al. 2019). offering consistent interfaces on data formats.
We now position contribution relative to the above. Unlike generalized m passing (Gilmer ct al. 2017). rather than abstracting the model computation, we abstract the learning algorithm. As a result, GTTF can be specialized to recover the learning of MP well as NE methods. Morever, unlike Software Frameworks, which are re-implementations of many algorithms and therefore inherit the scale and learning of the copied algorithms, we re-write the algorithms themselves, giving them new properties (memory and computation complexity), while maintaining (in expectation) the original algorithm outcomes. Further, while the listed Stochastic Sampling Methods target MP algorithms (such as GCN, GAT, alike), as their initial construction could not scale to large graphs, our learning algorithm applies to wider class GRI. methods, additionally encapsulating NE methods. Finally, while some NE methods such as node2vec (Grover & Leskovec 2016) and DeepWalk (Perozzi et al., 2014) are scalable their original form, their scalability stems from their multi-step process: sample many (short) random walks, save them to desk, and then learn node embeddings using positional embedding methods (e.g., word2vee, Mikoloo et al. (003)) - they are sub-optimal in the sense that their first step (walk sampling) takes considerable time (before training starts) and also places an artificial limit on the number of training samples (number of simulated walks), whereas our algorithm conducts walks on-the-fly whilst training.
GRAPH TRAVERSAL VIA TENSOR FUNCTIONALS (GTTF)
At its core, GTTF is stochastic algorithm that recursively conducts graph traversals to build representations of the graph. We describe the data structure and traversal algorithm below, using the following notation. G (V, E) is an unweighted graph with = [V nodes and m = E edges, described as a sparse adjacency matrix A E {0, 1|mxx. Without loss generality, let the nodes be zero-based numbered i.e. V {0, ..... n 1}. We denote the out-degree vector ò g
can be
calculated by summing over rows of A as 6n = Evey Alu, uj. We assume 8, > 0 for all u E V: pre- pre-processing can add cof-connections to orphan nodes. B denotes a batch of nodes.
3.1 DATA STRUCTURE
Internally, GTTF relies on reformulation of the adjacency matrix, which we term CompactAdj (for "Compact Adjacency", Figure Tcp. It consists of two tensors:
1. 8 2", a dense out-degree vector (figure Ic right)
2. Ā E Zax", sparse edge-list matrix in which the row u contains left-aligned 8,, non-zero values. The consecutive entries (Alu, 0j, A(u, 1)..... Alu, 8,. 1}} contain IDs of nodes receiving an edge from node u. The remaining [V] 6, are left unset, therefore, À only occupies (()) memory when stored as a sparse matrix (Figure Ic left).
CompactAdj allows us to concisely describe stochastic traversals using standard tensor operations. To uniformly sample neighbor to node u E V, one can draw ~ (6. 1)), then get the neighbor ID with À Alu, r). In vectorized form, given node batch B and access continuous 24 (0, 1), we sample neighbors for each node B as: ~ (0, 1)², where b = |B], then B' A[B, R o 8[B]J] is b-sized vector, with B", containing neighbor of B,, floor operation [.] is applied element- and is Hadamard product.
3.2 STOCHASTIC TRAVERSAL FUNCTIONAL ALGORITHM
Our traversal algorithm starts from batch of nodes. It expands from each into tree, resulting in a walk forest rooted at the nodes in the batch, as depicted in Figure [d] In particular, given node batch B, the algorithm instantiates [B] seed walkers, placing one at every node in B. Iteratively, each walker first replicates itself a fanour (f) number of times. Each replica then samples and transitions to neighbor. This process repeats depth (h) number of times. Therefore, each seed walker becomes the ancestor of a f-ary tree with height h. Setting f = 1 recovers traditional random walk. In practice, provide flexibility by allowing custom fanout value per depth.
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: Stochastic Traverse Functional, parametrized by ACCUMOLATEFI and BIASFN.
input: (current node); + [] (path leading to u, starts empty); (list of fanouts); ACCUMOLATEFN (function: with side-effects and no return. It is model-specific and records information for computing model and/or objective, see text);
BIASFN f (function mapping to distribution on u's neighbors, defaults to uniform)
def Traverse(T, u, F, ACCUMULATTEE BIASFN):
F fsize () 0 then return # Base case. Traversed up-to requested depth f F. pop # fanout duplication factor (i.e. breadth) at this depth.
sample_bias + BIASFN (T, w) if
then return Special case. No sampling from zero sample_bias + sample biiss / sample_bias, bias. sum () # valid distribution
K + Sample A [u, :6,]] sttple_bias.aaa1 Sample f nodes from u's neighbors for k 4 to
do
The <- concatenate [u]
ACCOMULATEFM/ FFN nes. K [M).))
11
Traverse(Tnow nex: K ACCUMOLTTTEP,,BASST # Recursion
12
13 def Sample(N, W, f):
14
tf. Cft..cuusum(W Cumulative sum. Last entry must = 1. coin_flips t random. uni (orm((
15
16
indices + tf..f.. ttt.tt.f..saaeee..e wewrrchhrtteeeC.... coin_flips) return [indices
Functional Traverse is listed in Algorithm| accepts: a batch of node list of fanout values F (e.g. to F' [3, 5] samples neighbors per E B, then 5 neighbors for each of those); and more notably, two functions: ACCUMULATEFN and BIAST SNN. These functions will be called by the functional every node visited along the traversal, and will be passed relevant information (e.g, the path taken from root seed node). Custom settings of these functions allow recovering wide classes of graph learning methods. At high-level, functional can be used in the following manner:
1. Construct model & initialize parameters (e.g. to random). Define ACCOMULATER and BIASFN.
2. Repeat (many rounds):
Reset accumulation information (from previous round) and then sample batch C C.
i. Invoke Traverse (B, ACCUMULA TENN, BIASA AFN),, which invokes the FN's s, allowing the first to accumulate information sufficient for rumning the model and estimating an objective. iii. Use accumulated information to: run model, estimate objective, apply learning rule (e.g. SGD).
Ac ACCUMULATED a function that is used track necessary information for computing the model and the objective function. For instance, an implementation of DeepWalk (Perozzi et al. 2014) on top of GTTF, specializes ACCUMUT 1.A TEEN n to measure an estimate of the sampled softmax likelihood of nodes' positional distribution, modeled as dot-prodet of node embeddings. On the other hand, GCN Kipf & Welling 2017) on top of GTTF uses it to accumulate a sampled adjacency matrix, which passes to the underlying model (e.g. 2-layer GCN) as if this were the full adjacency matrix.
BIASEN a function that customizes the sampling procedure for the stochastic transitions. nodes, given the current node and the path that
provided, it must yield a probability distribution lead to it. If not provided, it defaults to 24, transitioning to any neighbor with equal probability. It can be defined to read edge weights, if they denote importance, a second order Markov Chain (Grover & Leskovec, 2016), or use neighborhood attention to guide sampling (Veličković et al. 2018), as discussed in the Appendix.
intricately, used to parameterize
*Our pseudo-cod code displays the traversal starting from one node rather than a batch only for clarity, our actual implementation is vectorized e.g. would he vector of nodes, T would be a 2D matrix with each row containing transition path preceeding the corresponding entry u, ... Refer to Appendix and code.
4

---

Published as a conference paper at ICLR 2021
3.3 SOME SPECIALIZATIONS OF ACCUMULATEFN & BIASFN
3.3. MESSAGE PASSING: GRAPH CONVOLUTIONAL VARIANTS
These methods, including Kipf & Welling 2017 Hamilton et al. 2017 Wu et al. 2019 Abu-El El
Haija et al. 2019; Xu al. 2018) can be approximated by by initializing A to empty sparse matrix, then invoking Traverse (Algorithm 1) with u B: to list fanouts with size h; Thus
ACCUMULATEFN and BIASPN become:
def RetRoEEDADDAcc(T, u. f): Alu, T-1)
def NOREVISITBIAS u): return [A[u]]sumO = 0] 18_ 8
(2)
where I, is an n-dimensional all-ones vector, and negative indexing T-x the h last entry of T. If a node has been visited through the stochastic traversal, then it already has fanout number of neighbors and NCREVIS TSIAS ensures does not get revisited for efficiency, per line 5 of Algorithm 1. Afterwards, the accumulated stochastic will be fed into the underlying model e.g. for 2-layer GCN of Kipf & Welling (0177:
with À D2 -' GCN(Á,X; Wi, W2) softmax ReLu (eLu(AX
trick
(3)
D' = diag(6'); 8' 8 A'; A' = Taxn + A
Lastly, h should be set to the receptive field required by the model for obtaining output dz- dimenssioo features at the labeled node batch. In particular, to the number of GC layers multiplied by the number of hops each layers access. E.g. hops=1 for GCN but customizable for MixHop and SimpleGCN.
3.3.2 NODE EMBEDDINGS
Given batch of nodes B C V, Deep can be implemented in GTTF by first initializing loss L to the contrastive term estimating the partition function of log-softmax:
C
Σ BEB
log
E PNPP
[exp( Zo))1
(4)
where (...) is dot-product notation, Z E Ra is the trainable embedding matrix with Z, E Rd is d-dimensional embedding for node V. In our experiments, estimate the expectation by taking
5 samples and we set the negative distribution (V = v) o following Mikolov et al. 2013).
The functional is invoked with no BIASFN and ACCUMULATEFN
C5 def DeErFWLLKAA u. C C- Zi, Σ M (C-ktl ZT_
D 1l
(5)
where hyperparameter C' indicates maximum window size (inherited from word2vec, Mikolov et al. 2013), the summation on does not access invalid entries of T as Cr & min(C. T .ssze), the scalar fraction (-b+1) is inherited from context sampling of word2vec (Section 3.1 in Levy et al. 2015 and rederived for graph context by AAbu-El-Haij a al. (2018), and 7/[1] stores a scalar per node the traversal Walk Forest, which defaults to for non-mittaalied entries, and is used as a correction straight line) whereas our walk tree has
term. DeepWalk conducts random walks (visualized branching factor of f- Setting fanout f = recovers DeepWalk's 's simulation, though we found f /> outperforms within fewer iterations e.g. f 5, within I epoch, outperforms DeepWalk's 's published implementation. Learning can be performed using the accumulated L as: Z + Z - -e
4 THEORETICAL ANALYSIS
Due to space limitations, we include the full proofs all propositions the appendix.
1 Beforr feeding the batch to model, in practice, we find nodes not reached by traversal and remove their corresponding rows (and also columns) from X (and A). *We present more methods in the Appendix.
5

---

Published as a conference paper at ICLR 2021
4.1 ESTIMATING TTT POWER OF TRANSITION MATRIX
We show that it is possible with GTTF to accumulate an estimate of transition T matrix to power k. Let Ω denote the walk forest generated by GTTF, Quu, k, i) as the jt node in the vector of nodes at depth & of the walk tree rooted at u E B, and 2.. as the indicator random variable 1 [[((u, k, i) u]. Let the estimate of the hthh power of the transition matrix be denoted 7 Entry Tr, should be an unbiased estimate of T for B, with controllable variance. We define:
4 fue. u,U
Eisr fk
(6)
The fraction in Equation 6 counts the number of times the walker starting at visits v in Ω divided by the total number of nodes visited at the 1hth step from u.
Proposition (UnBIASEDTK) Tu, as defined in Equation 6 an unbiased estimator of T
1 4
Proposition 2. (VARTANCETK) Variance of our estimate is upper-bounded: Var[Ta,, u.ul S
Naive computation of 1:th powers of the transition matrix can be efficiently computed via repeated sparse matrix- multiplication. Specifically, each column of T can be computed in (m,)) where m is the number of edges the graph. Thus, computing T in its entirety can be accomplished in (nmmk). However, this can still become prohibitively expensive if the graph grows beyond certain size. GTTF on the other hand can estimate T time complexity independent of the size of the graph, (Prop. 8). with low variance. Transition matrix powers are useful for many GRL methods. QQu et al. 2018
4.2 UNBIASED LEARNING
As consequence of Propositions and GTTF enables unbiased learning with variance control for classes of node embedding methods, and provides a convergence guarantee for graph convolution models under certain simplifying assumptions.
We start by analyzing node embedding methods. Specifically, we cover two general types. The first is based on matrix factorization of the power-series of transition matrix. and the second is based on cross-entropy objectives, c.g., like DeepWalk (Perozzi et al., 2014), node2vec (Grover & Leskoved 2016), These are shown in Proposations andd
Suppose C= -- -IULREEGG Tx i.e. factoriza- tion objective that can be optimized by gradient descent by calculating VI,CC, where ex 'ss are scalar coefficients. Let its estimate C 2 Ex 1h where T obtained by GTTF according to
Proposition
Equation 6 Then LVVn, V.,C..
Proposition 4. (UNBIASEDLEARNNE) Learning node embeddings Z E Raad with objective function C, decomposable as L(Z) Euev Lz(Z,u) Σu.eev Σx L2(Th, u, L, where La is linear over Th then using Th yields an unbiased estimate of V ZzC.
Generally, Li (and L3) score the similarity between disconnected (and connected) nodes and V. The above form of covers a family of contrastive learning objectives that use cross-entropy loss and assume logistic (sampled-)softmax )softmax distributions. We provide, in the Appendix, the decompositions for the objectives of DeepWalk (Perozzi et al. 2014), node2vec (Grover & Leskoved 2016) and WYS (Abu-El-Haija al. (0188).
Proposition 5. (UNBIASEDMP) Given input activations, H(-1),, graph comv layer (1) can use rooted udjucency À accumulated by RooTEDAJJACe 4)) to provide unbiased pre-activation output, Lee. (011) (D' (D'-1/2 -12)" ((-1))() with A' and D' defined in 33
Proposition 6. (UNBIASEDLEARNMP If objective to a graph convolution model is convex and Lipschitz continous, with minimizer 0*, then utilizing GTTF for graph convolution converges 0*

---

Published as a conference paper at ICLR 2021
4.3 COMPLEXITY ANALYSIS
Proposition 7. STORAGE complexity of GTTF is O(m n..
Proposition 8. TIME complexity of GTTF is (b)th)
) for batch size b, fanout f, and depth h.
Proposition X iimplies the speed of computation is irrespective of graph size. Methods implemented in GTTF inherit this advantage. For instance, the node embedding algorithm WYS (Abu-EI-Haija et al. 2018 is (nn"), however, we apply its GTTF implementation on large graphs
5
EXPERIMENTS
We conduct experiments on 10 different graph datasets, listed in in Table [ We experimentally demonstrate the following. (I) Re-implementing baseline method using GTTF maintains performance. methods, can be made scalable when implemented in GTTF (3) GTTF achieves good empirical performance when compared to other sampling-basee approaches hand- designed for Message Passing. (4) GTTF consumes less memory and trains faster than other popular Software Frameworks for GRL. To replicate
(2) Previously-unscalabe
experimental results, for each cell of the table in code repository, we provide one shell script to produce the metric, except when we indicate that the metric copied from another paper. Unless otherwise stated, we used fanout factor of 3 for GTTF implementations. Learning rates and model hyperparameters are included in the Appendix.
5.1 NODE EMBEDDINGS FOR LINK PREDICTION
In link prediction tasks, graph is partially obstructed by hiding a portion of its edges. The task is to recover the hidden edges. We follow popular approach to tackle this task: first learn node embedding Z E TR from the observed graph, then predict the link between nodes u and v with score Z,, Z.. We use two ranking metrics for evaluations: ROC-AUC, which is ranking objective: how well do methods rank the hidden edges above randomly-sampled negative edges and Mean Rank.
We re-implement Node Embedding methods, DeepWalk (Perozzi et al. 2014) and WYS (Abu-El Haija et al. 2018). into GTTF (abbreviated F). Table 2 summarizes link prediction test performance.
LiveJournal and Reddit are large datasets, where original implementation of WYS is unable to scale to. However, scalable F(WYS) sets new state-of-the-ar on these datasets. For PPI and HepTh datasets, we copy accuracy numbers for Walk and WYS from (Abu-EI-Haija et al. 2218). 8). For LiveJourna,, we copy accuracy numbers for Deep Walk and PBG from (Lerer et al. [019)] note that well-engineered approach (PBG, (Lerer et al.) 2019) ) using mapreduce- like framework, is under-performing compared to F(WYS), which is a few lines specialization of GTTF.
5.2 MESSAGE PASSING FOR NODE CLASSIFICATION
We implement in GTTF the message passing models: GCN Kipf & Welling 2017). GraphSAGE (Hamilton et al., 2017), MixHop (Abu --u-El-Be Hajja et al. 2019), SimpleGCN (Wu et al. 2019). as their computation is ttaight-forwant For GAT (Veličković 2018) and GCNII (Chen et 2020). as they are more intricate, we download the authors' codes, and wrap them as-is with our functional.
We show that we are able to run these models in Table (left and middle), and that GTTF implemen- tations matches the baselines performance. For the left table, we copy numbers from the published papers. However, we update GAT to work with TensorFlow 2.0 and we use our updated code (GAT*).
5.3 EXPERIMENTS COMPARING AGAINST SAMPLING METHODS FOR MESSAGE PASSING
We now compare models trained with GTTF (where samples are walk forests) against sampling methods that are especially designed for Message Passing algorithms (GraphSAINT and ClusterGCN), especially since their sampling strategies do not match ours.
Table 3 (right) shows test performance on node classification accuracy on a large dataset: Products. We calculate the accuracy for F(SAGE) but copy from (Hu et al. 2020 the accuracy for the baselines: GraphSAINT (Zeng et al. 2020) and ClusterGCN (Chiang et al. 2019) (both are message passing methods); and also 2ode2vec (Grover & Leskovec 2016) (node embedding method).
7

---

Published as a conference paper at ICLR 2021
Table Dataset summary. Tasks are LP, SSC, FSC, for link prediction, semi- and fully-supervised classification. Split indicates the train/validate/test paritioning, with (a) = (Abu-El-Haija et al. 2018
(b) to be released, (c) (Hamilton et 2017). (d) Yang al. 2016): (e) (Hu al. 2020
Dataset
Split
# Nodes
Edges
# Classes
Nodes
Edges interaction
Tasks
PPI
(a)
3,852
20,881
N/A
proteins
LP
Ca-HepTT
(a)
80,638
24.827
N/A
researchers
co-authorship
LP
ca-AstroPh
(a)
17,903
197,031
N/A
researchers
co-authorship
LP
LiveJournal
(b)
4.85M
68.99M
N/A
users
friendship
LP
Reddit
(c) 233,965
11.60M
41
posts
user co-comment
LP/FSC
Amazon
(b) 2.6M
48.33M
31
products
co-purchased
FSC
Cora
(d)
2,708
5,429
articles
citation
SSC
CiteSeer (d)
3,327
4,732
articles
citation
SSC
PubMed
(d)
19,717
44,338
3
articles
citation
SSC
Products
(c)
2.45M
61.86M
47
products
co-purchased
SSC
Table 2: Results of node embeddings Link Prediction. Left: Test ROC-AUC scores. Right: Mean
Rank on the right for consistency with Lerer et al. (201)). *OOM Out of Memory.
PPI
HepTh
Reddit
LiveJournal
DeepWalk
70.6
91.8
93.5
DeepWalk
234.6
F(DeepWalk)
87.9
89.9
95.5
PBG
245.9
WYS
89.8
93.6
OOM
WYS
OOM*
F(WYS)
90.5
93.5
98.6
F(WYS)
185.6
Table 3: Node classification tasks. Left: test accuracy scores on semi-supervised classification (SSC) of citation networks. Middle: test micro-F1 scores for large hully-supervised classification. Right: test accuracy on an SSC task, showing only scalable baselines. We bold the highest value per column.
Cora
Citeseer
Pubmeb
GCN
81.5
70.3
79.0
F(GCN)
81.9
69.8
79.4
Reddit
Amazon
Products
MixHop
81.9
71.4
80.8
SAGE
95.0
88.3
node2vee
72.1
F(MixHop)
83.1
71.8
80.9
F(SAGE)
95.9
88.5
ClusterGCN
75.2
GAT*
83.2
72.4
77.7
SimpGCN
94.9
83.4
GraphSAINT
77.3
F(GAT)
83.3
72.5
77.8
F(SimpGCN)
94.8
83.8
F(SAGE)
77.0
GCNII
85,5
73.4
80.3
F(GCNII)
85.3
74.4
80.2
Table 4: Performance of GTTF against frameworks DGL and PyG. Left: Speed is the per epoch time in seconds when training GraphSAGE, Memory is the memory in GB used when training GCN. All experiments conducted using an AMD Ryzen 3 120 Quad-Core CPU and an Nvidia GTX 1080Ti
GPU. Right: Training curve for GTTF and PyG implementations of Node2Vec.
Speed (s)
Memory (GB)
ROC-AUC
0.0-
framework
Reddit
Products
Reddit
Citeseer
Pubmed
0.7
P'node2vecl
DGL
17.3
13.4
OOM
1.1
1.1
1.1
PyG(nade2vec)
PyG
5.8
9.2
OOM
1.2
1.3
1.6
GTTF
1.8
1.4
2.44
0.32
0.40
0.43
250
500
750
Time (s)
5.4 RUNTIME AND MEMORY COMPARISON AGAINST OPTIMIZED SOFTWARE FRAMEWORKS
In addition to the accuracy metrics discussed above, we also care about computational performance. We compare against software frameworks DGL (Wang et al. 2019) and PyG (Fey & Lensseni 2019). These software frameworks offer implementations of many methods. Jummarries the following. First (left), show time-per-epoch large graphs of their implementation of
8

---

Published as a conference paper at ICLR 2021
GraphSAGE, compared with GTTF's, where make all hyper parameters to be the same (of model architecture, and number of neighbors at message passing layers). Second (middle), we run their GCN implementation small datasets (Cora, Citeseer, Pubmed) to show peak memory usage. The run times between GTTF, PyG and DGL. are similar for these datasets. The comparison can be found in the Appendix. While the aforementioned two comparisons on popular message passing methods, the third (right) chart shows popular node embedding method: node2vec's link prediction test ROC-AUC in relation to its training runtime.
CONCLUSION
We present new algorithm, Graph Traversal via Tensor Functionals (GTTF) that can be specialized re-implement the algorithms of various Graph Representation Learning methods. The specialization takes little effort per method, making straight-forwee forward port existing methods or introduce new ones. Methods implemented in GTTF run efficiently as GTTF uses tensor operations to traverse graphs. In addition, the traversal is stochastic and therefore automatically makes the implementations scalable to large graphs. We theoretically show that the learning outcome due to the stochastic traversal is in expectation equivalent to the baseline when the graph is observed at-once, for popular GRL methods analyze. Our thorough experimental evaluation confirms that methods implemented GTTF maintain their empirical performance, and can be trained faster and using less memory even compared to software frameworks that have been thoroughly optimized.
7
ACKNOWI.DDGEMENTS
We acknowledge support from the Defense Advanced Research Projects Agency (DARPA) under award FA8750-17-C-0106.
REFERENCES
Sami Abu-El-Haal El-Haija, Bryan Perozzi, Rami AI-Rfou, and Alexander Alemi. Watch your step: Learning node embeddings via graph attention. In Advances in Neural Information Processing Systems, 2018.
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional archi- tectures via sparsified neighborhood mixing. In International Conference on Machine Learning. 2019.
Pierre Baldi and Peter Sadowski. The dropout learning algorithm. In Artificial Intelligence, 2014.
Leon Bottou, Online algorithms and stochastic approximations. In Online Learning and Neural Networks, 1998.
Leon Bottou. Stochastic learning. In Advanced Lectures on Machine Learning, Lecture Notes in Artificial Intelligence, vol. 3176, Springer Verlag, 2004.
Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. Machine learning graphs: A model and comprehensive taxonomy, 2021.
Hongming Chen, Ola Engkvist, Yinhai Wang, Marcus Olivecrona, and Thomas Blaschke. The rise of deep learning in drug discovery. In Drug discovery today, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representation, 2018b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference Knowledge Discovery & Data Mining, 2019.

---

Published as a conference paper at ICLR 2021
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016.
William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In arXiv, 2020.
Thomas Kipf' and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. Pytorch-biggraph: A large-scale graph embedding system. In The Conference Systems and Machine Learning, 2019.
Omer Levy, Yoav Goldberg, and Ido Dagan. Improving distributional similarity with lessons learned from word embeddings. In Transactions of the Association for Computational Linguistics, 2015.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado. and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, 2013.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social represen- tations. In ACM SIGKDD international conference on Knowledge discovery & Data Mining, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, ptc, and node2vec. In ACM International Conference on Web Search and Data Mining, 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting In Journal of Machine Learning Research, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018
Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference Learning Representations, 2019.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang Deep graph library: A graph-centric, preprint Xiv: 1909.0/395 2019.
package for graph neural networks. arXiv
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In International Conference on Machine Learning, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, In International Conference on Machine Learning, 2018.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning, 2016.
10

---

Published as a conference paper at ICLR 2021
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Few-shot repre- sentation learning for out-of-vocabulary words. In Advances in Neural Information Processing Systems, 2019.
APPENDIX
A HYPERPARAMETERS
For the general link prediction tasks we used a |B| = [V], f 3, 10 negative samples per edge, Adam optimizer with a learning rate of 0.5, multiplied by a factor of 0.2, every 50 steps, for 200 total iterations. The differences are listed below.
The Reddit dataset was trained using starting learning rate of 2.0, decaying 50% every 10 iterations.
The LiveJournal task was trained using fixed learning rate of 0.001, |B] 5000, f = 2, and 50 negative samples per edge.
For the node classifications tasks:
For F(SimpleGCN) on Amazon, we use f [15, 15), a batch size of 1024, and learning rate of 0.02, decaying by factor Of 0.2 after and 6 epochs for total of 25 epochs. On Reddit, it is the same except f = [25, 25]
For F(SAGE) on Amazon we use f = [20, 10), two layer model, batch size of 256, and fixed learning rates 0.001 and 0.002 respectively. On reddit we use f = [25, 20), a fixed learning rate of 0.001, hidden dimension of 256 and batch size of 1024. On the Products dataset, we used f [15, 10). a fixed learning learning rate of 0.001 and a batch size of 1024, hidden dimension of 256 and fixed learning rate of 0.003.
For GAT (baseline), we follow the authors code and hyperparameters: for Cora and Citeseer, we use Adam with learning rate of 0.005, L2 regularization of 0.0005, 8 attention heads the first layer and I attention head on the output layer. For Pubmed, we use Adam with learning rate of 0.01, 1.2 regularization of 0.01, 8 attention heads the first layer and 8 attention heads the output layer. For F(GAT), we use the same aforementioned hyperparameters, a fanout of 3 and traversal depth of 2 (to cover two layers) i.c. F 3, 3). For F(GCN), we use the authors' recommended hyperparameters. Learning rate of 0,005, 0.001 L2 regularization, and F = [3, 3]. for all datasets. For both methods, we apply "patience" and stop the training if validation loss does not improve for 100 consecutive epochs, reporting the test accuracy at the best validation loss. For F FoMi we wrap the authors' script and use their hyperparameters. For F(GCNII), we use F [5. 5, 5, 5), as their models are deep (64 layers for Cora). Otherwise, we inherit their network hyperparameters (latent dimensions, number of layers, dropout factor, and their introduced coefficients), as they have tuned them per dataset, but change the learning rate to 0.005 (half of what they use) and extend the patience from 100 to 1000, and extend the maximum number of epochs from 1500 to 5000 this is because down the learning per epoch, which similar to the practice when someone applies Dropout to neural networks. We re-run their shell scripts, with their code modified to use the Rooted Adjacency rather than the real adjacency, which is sampled at every epoch.
presenting subgraph each epoch, and therefore
intuitively want to slow
MLP was trained with layer and learning rate of 0.01.

---

Published as a conference paper at ICLR 2021
B PROOFS
B.1 PROOF OF PROPOSITION 1
k
Σ Plu
=
Σ
u.e
Proof. E[TT,, E
T
fk
fk
fk
B.2 PROOF OF PROPOSITION
2
Varl
fkTTk,
-To
u,0 (1 - Toh.
Proof. Var(Tu;
110
f2h
f2k
fk
Since 0 - ue I 1, then T1. Taly)) is maximized with Tuk
Hence Var Var
2'
4
B.3 PROOF OF PROPOSITION
Proof. Consider d-dimensional factorization E. C Th where oj are scalar coefficients:
C 2
LR Σ cx
(7)
parametrized by I., R E RRaxd The gradients of L w.r.t. parameters are:
V LR - E C -a
R and = LR - Σ Tx
(8)
k
Given estimate objective L (replacing 7 with using GTTF-estimated 7):
E
LR
Σ
ck
7
(9)
2
d
F
It follows that:
E
V
E
LR Σ
Ck T
R
k
E
LR Σ
Cx 7
R
Scaling property of expectation
LRT Σ C+LE [T
R.
Linearity of expectation
LR Σ
Tx
R
Proof of Proposition 1
VLL
The above steps can similarly be used to show E VRL
R
B.4 PROOF OF PROPOSITION 4
Proof. We want to show that F. V 2)]
VzL(T>, 2). Since the terms of L1 are unaf-
fected by T, they are excluded w.l.g. from C in the proof.
E/V .)) = F[V2( Σ
Σ
u,)
M.VVV kE
12

---

Published as a conference paper at ICLR 2021
(by linearity of expectation)
- Σ
Σ
(2( u1, ,,, (,,,))c(Z,uu))
u,vEV (E(1...)
(by Prop 1) Z Σ a (E(1..C)
Σ
C2 u, L3 -V
Vz2(TH
The following table gives the decomposition for DeepWalk, node2vec, and Watch Your Step. Node2vec also introduces biased sampling procedure based on hyperparameters (they name p and g) instead of uniform transition probabilities. We can equivalently bias the transitions in GTTF to match node2vec's. This would then show up change in 7 in the objective. This effect can also be included in the objective by multiplying (w Zu) by the probability of such transition in L3. In this format, the and g variables appear in the objective and can be included in the optimization. For WYS, Qk are also trainable parameters.
Method
L
L2
L3
C
k
+
DeepWalk
Th
log( (Zu( Zo))
C
C
+1
Node2Vec
log
Evev exp( Zo)))
T
(Zui Zu}
C
Watch Your Step
log(1 o(LL, R.)))
QKT
log(or((Lgg) RB)))
Table 5: Decomposition of graph embedding methods to demonstrate unbiased learning. For WYS,
Zu concatenate Lu, R.,).
For methods in which the transition distribution is uniform, such as node2vec, there two options for incorporating this distribution in the loss. The obvious choice is to sample from a biased transition matrix, Tu W.,, where W is the transition weights. Alternatively, the transition bias can be used as weight on the objective itself. This approach is still unbiased as
E W.
W. [C(e, u)] = Evev P. P.w. [u][(u, u) = Evev W W., C,,,C(o,
B.5 PROOF OF PROPOSITION 5
Proof. Let A be the neighborhood patch returned by GTTF, and let indicate measurement based on the sampled graph, À, such the degree vector, 8, or diagonal degree matrix, D. For the remainder of this proof, let all notation for adjacency matrices, or A, and diagonal degree matrices, D) or D, and degree vector, 8, refer to the corresponding measure on the graph with self loops e.g. A +- A Inxe- We now show that the expectation the layer output unbiased.
E
Å ((111))
E
(1-1w()) implies that E (0 is unbiased if
A (D-1// AD
1D-AAD-122 1/2)
E A =E
D1/2 (5-IA) D 1/2 -1/2E (ō-1a)) D-1/2
Let pu.ek be the set of all walks ap (u, .. 1k uk-1, v)(e, VJ. and let pJA indicate that the path p exists in the graph given by and let t be the probability of a random walker traversing the graph along path
A. Let ga,nk be the transition probability from u to v in & steps.
IF. (D
E
1u.0
Pr Frank = 1] 1]= Σ Pr|p 1/p
u.v
pEP
13

---

Published as a conference paper at ICLR 2021
R (f+1)= E
E
IA P++1] =1] 11
I[ Pi+1] = 1]8[p:]
8lpi] 1=1
pEPuo,t t=l
PEPu. t=1
Pr(t = =1 Pritureity
= - (
PC P
Thus, F. [((
1/-11/2 and E. (( AD-1/2 H(-1)
For writing, we assumed nodes have degree, 6a 2 S. though the proof still holds that is not the case as the probability of an outgoing edge being present from becomes 1 and the transition probability becomes 8, i.c. the same as no estimate at all.
B.6 PROOF OF PROPOSITION 6
GTTF can be seen as a way of applying dropout (Srivastava et al. 2014), and our proof is contingent on the convergence of dropout, which is shown in Baldi & Sadowski (2014). Our dropout is on the adjacency, rather than the features. Denote the output of a graph convolution network with H:
H = GCNx (A; W) = TXW
We restrict our analysis to GCNs with linear activations. We are interested in quantifying the change of as changes, and therefore the fixed (always visible) features X placed on the subscript. Let denote adjacency accumulated by GTTF's ROOTEDADJACC (Eq.
He GCNN x
Let A= (Ae) denote the (countable) analysis, assume the graph is a-regular: the assumption eases the notation though it is not needed. Therefore, degree 8, for all u V. Our analysis depend on - Σλeu A A. i.c. the average realizable matrix by GTTF is proportional (entry-wise) to the full adjacency. This is can be shown when considering one-row at a time: given node u with 6, = a outgoing neighbors, each of its neighbors has the same appearance probability = J. Summing over all combinations
all adjacency matrices realizable by GTTF. For the
(7)) makes
each edge appear the same frequency = x, [AA,, noting that |A| evenly divides (or) for all u E V.
We define a dropout module:
|A them
M A
1 LA
Σ Ac with 2 ~ Categorical
(10)
[A] [A|
where z, acts as Multinoulli selector over the elements of A, with one of its entries set to 1 and all others to zero. With this definitions, GCNs can be seen in the droupout framework as: H GCNx (Å). Nonetheless, in order to inherit the analysis of (Baldi Sadowski 2014, see their equations 140 & 141), we need to satisfy two conditions which their analysis is founded upon:
(i) x|GCNx = GCNx (A): in the usual (feature-wise) dropout, such condition is easily verified.
(ii) Backpropagated error signal does not vary too much around around the mean, across all realizations of Á.
Condition (i) is satisfied due to proof of Proposition To analyze the error signal, i.e. the gradient of the enror w.r.t. the network, assume loss function L H)). outputs scalar loss, is X-Lipschitz continuous.
'The following definition averages the node features (uses non-symmetric normalization) and appears in multiple GCN's including Hamilton el al. (2017).
II not a-regular, it would be AeAA D- A
14

---

Published as a conference paper at ICLR 2021
The Liptchitz continuity allows us bound the difference in error signal between L(H) and L(H):
V - V C(M)
V =C(H) -
(1-1)
(11)
V (
VnC(Hlle 11H -H1l2
(12)
21 d
A V VnC(H)]2 W X QU
(13)
XQ
] - V=
(14)
2
XQ
11 (H VnL(Hl S
2/T ||W]| I
(15)
where (a) is by Lipschitz continuity, (b) is by Cauchy-Schwarz inequality, "w.p." means with probability and uses Chebyshev's inequality, with the following equality because the variance of T is shown element-wise in proof for Prop. 2 Finally, we get the last line by dividing both sides over the common term. This shows that one can make the error signal for the different realizations arbitrarily small, for example, by choosing larger fanout value putting (convex) norm constraints on W and X e.g. through batchnorm and/or weightnorm. Since we can have VHC(H) (HH,
V C(H2) x se (H((H))) with high probability, then the analysis of Baldi & Sadowski (2014) applies. Effectively, algorithm where the elements of A are the stochastic training examples and analyzed per (Bottou 1998 2004), as explained by Baldi & Sadowski (2014) D.
be thought of as online learning
B.7 PROOF OF PROPOSITION 7
The storage complexity of CompactAdj is O(sizeo](o) + sizeos
O( m))
Moreover, for extemely large graphs, the adjacncy can be row-wise partitioned across multiple machines and therefore admitting linear scaling. However, we acknolwedge that choosing which rows to partition which machines can drastically affect the performance. Balanced partitioning ideal. It is an NP-hard problem, but many approximations have been proposed. Nonetheless, reducing inter-communication, when distributing the data structure across machines, is outside our scope.
B.8 PROOF OF PROPOSITION
For each step of GTTF, the computational complexity is O(bh). This follows trivially from the GTTF functional: each nodes in batch (6 of them) builds tree with depth and fanout f i.c. with hf tree nodes. This calculation assumes random number generation, AcCUMULA LATEULLAAES and BIASFN take constant time. The searchsort ed function is linear, as it is called on a sorted list: cumulative sum of probabilities.
C ADDITIONAL GTTF IMPLEMENTATIONS
C.1 MESSAGE PASSING IMPLEMENTATIONS
C.1.1 GRAPH ATTENTION NETWORKS (GAT, VELIĆKOVIĆ ET AL.. 2018)
One can implement GAT by following the previous subsection, utilizing ACCUMULATEFX and BIASEN defined in (1] and (2) but just replacing the model by GAT's:
W2) = softmax ((An Å) ReLu((A o AjxW;)Wa):
(16)
where is hadamard product and A is n. x matrix placing a positive scalar (an attention value) on each edge, parametrized by multi-heades attention described in (Veličković et al.] 2018). However, for some high-degree nodes that put most of the attention weight sampling uniformly (with B S N= vIv ITBIAs) aS) might mostly sample neighbors with entries in A with value z 0, and could require more epochs for convergence. However, flexible functional
small subset of their neighbors,
15

---

Published as a conference paper at ICLR 2021
allows us propose sample-efficient alternative, that is in expectation, equivalent to the above:
GAT(A, A, W2): voftmax((vA) A) ReLu((VA W)x))))Ws);
(17)
def GATBIAS(T) u): return NoREviSI1Bras(7 Alu, A[u]];
(18)
C.1.2 DEEP GRAPH INFOMAX (DGI. VELIĆKOVIĆ ET AL. 2019)
DGI implementation on GTTF can use ACCOMUIATEFFFRROTTEBBAA create the positive graph: and utilize the accumulated adjacency Å for running: GCN xB) and GCN(A, (A, X Xpemuee) where the second run randomly permutes the order of nodes in X. Finally, the output of those GCNs can then fed into a readout function which outputs to descriminator trying classify if the readout latent vector correspond to the real, or the permuted features.
defined in T To sample some nodes B V. It would pass GTTF's Traverse B,
C.2 NODE EMBEDDING IMPLEMENTATIONS
C.2.1 NODE2VEC (GROVER LESKOVEC 2016)
simple implementation follows from above: N2VACC A DEEPWALKACC; but override BIASFN=
def N2vBIAs u): return =il -l [[A[[[)))))]]
(19)
where denotes indicator function, p.q
hyperparameters of node2vec assigning (un- normalized) probabilities for transitioning back to the previous node or to node connected to it. (A[T-22), (u]} counts mutual neighbors between considered node and previous T-2
An alternative implementation is to not override BIASFN but rather fold it into ACCUMOLATSFN,
def' N2vAce(T, u, f): DEEPWALXAcc(T; f); V/o + Mu] N2VBIAs u);
(20)
Both alternatives are equivalent in expectation. However, the latter directly exposes the parameters p and the objective L: allowing them to be differentiable w.r.t. L and therefore trainable via gradient descent, rather than by grid-search. Nonetheless, parameterizing & q is beyond our scope.
C.2.2 WATCH YOUR STEP (WYS, ABU-EL-HAUA ET AL. 2018)
First, embedding dictionaries R, E R can be initialized random. Then repeatedly over batches B C V, the loss L can be initialized to estimate the negative part of the objective:
L+
Σ log a (ngg((EveuV)) [(R,, L.) + (Ro, Lu)l),
WEB
Then call GTTF's traverse passing the following ACCUMULATEFN
def (xsAcc(T,uj) u):
T.sizel # Q.size(): return;
< T(O): U T(1 [M];
ctx etx_weighted_ L Eo,Lu, ctx_weighted R Oj
- L- (-C--looo((Rt.tttt_.eieeeeee (L,, weighttedd
D MISCELLANEOUS
D. SENSITIVITY
The following figures show the sensitivity of fanout and walk depth for WYS the Reddit dataset.
16

---

Published as a conference paper at ICLR 2021
0.0
59.00
$0.90
Figure 3: Test AUC score when changing the fanout (left) and random walk length (right)
dataset
citeseer
Accuracy
pubmed
framework
PyG
0.5
1.5
Time (s)
Figure 4: Runtime of GTTF versus PyG for training GCN on citation network datasets. Each line averages 10 runs on an Nvidia GTX 1080Ti GPU.
D.2 RUNTIME GCN ON CITATION NETWORKS
Citation networks (Cora, Citeseer, Pubmed) have been popularized by Kipf & Welling (2017). and for completeness, we report in Figure 4 the runtime versus test accuracy of GCN on these networks. We compare against PyG, which is optimized for GCN. We find that the methods are somewhat comparable terms of training time.
17


Reviews:
[{"review_id": "qSfQeDT7Mj9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new graph traversal method by introducing a compact adjacency matrix and applying stochastic methods to sample nodes.  The proposed graph traversal can be applied in conjunction with graph neural networks such as GCN, Deepwalk,..etc, and ideas proposed in the paper would interest and influence other researchers in the community. An advantage is that the proposed method shows improvements in speed and memory usage. Overall, The paper is well written with both theoretical and experimental evaluations. \n\nPros:\na.) The proposed method well-developed and supported with theoretical analysis \n\nb.) The proposed sampling method can be combined with other existing methods. The authors discuss the applicability of the proposed method with existing methods.\n\nCons:\na.) One limitation is that experiments are not very convincing since there are only a few baseline methods that are compared with the proposed method.  For instance, It would be better to show performances of methods like GraphSAGE, cluster GCN, and other methods (at least method in the table in Section 2) applied to all datasets. Showing different selections of baseline methods make it hard to understand the true performances of the proposed method. Can the authors provide more detailed comparisons with different baseline methods?  \n\nb.) The performances (e.g. semisupervised node-classification) shown are not as competitive as performances achieved by other recent methods (e.g. GCNII). Can the authors add more experimental results to the paper?\n\nI raise my rating based on the additional experimental results given.", "extra_scores": {}, "extra_text": {}}, {"review_id": "k3XjexqdjnC", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Pros:\n1)\tThe graph traversal via tensor functionals is proposed with stochastic graph traversal algorithm based on tensor optimization that inherits benefits of vectorized computation and libraries. \n2)\tIt can be specialized for many existing models and make them scalable for large graph.\n3)\tAuthors proved the learning is unbiased, with controllable variance.\n4)\tExperimental results on both node classification and link prediction verify the efficiency and effectiveness of the proposed unified meta-algorithm framework. \n\nCons:\n1)\tAs shown in the experiments, the implementation of existing methods under GTTE can be more efficient and less memory requirement. It might be better to conduct complexity analysis on the proposed meta-algorithm to show these advantages.\n2)\tThe algorithmic comparisons between the existing stochastic sampling methods and GTTE can be helpful to understand the differences and their pros and cons.  \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "gheznvXq6WD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Quality\n\nThis paper, as far as I can tell, is technically solid.\nThe authors present an algorithm, show how it can be specialized to a variety of other methods, then prove the conditions under which it estimates loss functions, gradients, and powers of transition matrices without bias.\nThey then demonstrate how their method can be used to approximate graph representation learning techniques over a variety of datasets, as well as enabling the application of non-scalable techniques to large graphs.\n\n# Clarity\n\nThis paper is mostly well-written, with a few issues throughout.\n\nOne issue I took was with the authors' use of the term \"tensor:\" they claim that their method allows for efficient implementation via standard tensor operations.\nThis was deceiving when first reading the paper: I expected this approach to involve tensors in the sense of a multilinear operator, and for operations to be understood in terms of that operator.\nThe approach in this paper doesn't resemble tensor methods in that way: it would be better described as graph representation learning with sparse edge lists.\n\nThere is also some ambiguity in Algorithm 1: it is unclear what AccumulateFn *does*.\nWithout thoroughly looking at the specific applications, it is not easy to tell what effect line 10 in Algorithm 1 has.\nIt would significantly improve readability to be specific about side-effects, return values, etc. of AccumulateFn in general.\n\n# Originality\n\nThis paper is somewhat original.\nThe authors do not formulate anything particularly new: rather, they unify a variety of algorithms for graph representation learning under a common approach, parameterized by two functions (Accumulate and Bias).\nThe algorithm in this paper takes very similar form to that written in the most popular GRL papers, so I would not evaluate it as being a particularly novel contribution.\n\nHowever, there is novel value in the analysis of the meta-algorithm as an unbiased estimator of loss functions dependent on powers of a transition matrix.\nThis is similar in spirit to the cited paper [Qui et al., 2018], where a link is made between these methods and matrix factorization techniques.\nHere, the authors have made a link between many methods and a general framework, from which they can form computationally efficient approximations.\n\n# Significance\n\nOne contribution of this work to the community is a \"unified look\" at a wide array of node embedding methods.\nThe authors have identified common features of approaches such as node2vec, DeepWalk, GCN, etc., and formulated a stochastic approach that is flexible enough to reflect each of these algorithms.\nI wouldn't characterize this formulation as inherently significant, since the form of all of these algorithms is written in a similar way.\n\nA more concrete contribution of this work is the analysis of this formulation as a computationally efficient (Propositions 6 and 7) approximator for powers of a transition matrix (Propositions 1 and 2), which has applications in many representation learning tasks.\nIt is established that using the proposed estimator of the transition matrix yields unbiased estimates and gradients for a class of loss functions (Propositions 3, 4, and 5).\n\nThis yields the most significant contribution of this paper: if a practitioner can write the loss function in the form provided in Proposition 3, the formulation of the authors can be justified as a good, computationally efficient approximant for their case.\nThis impact is demonstrated in the experiments using WYS, where the authors' form is shown to perform similarly to WYS on graphs of small scale, and then shown to be feasible on graphs of large scale, while the original form of WYS does not scale.\nThat is, the proposed framework appears to be a reasonable way to approximate methods that are not scalable, showing potential in bridging theory and practice.\n\nBeyond the special case where a method's loss function can be written in terms of a transition matrix raised to some power, though, this paper falls short.\nIt would be useful to understand the behavior of this approach when used to approximate methods that cannot be written in the form of Proposition 3.\nBecause of this, the scope of analysis in this paper is somewhat limited: the authors should more directly discuss cases where this is not true, beyond the brief mention of node2vec in the appendix.\n\n# Overall review\n\nThis paper takes a broad view of graph representation learning problems, proposing a generic algorithm that they show can recover many popular approaches.\nAlthough there are a few missing pieces, the proposed approach is useful in scaling approaches that were previously not scalable, and thus warrants being accepted into ICLR 2021.", "extra_scores": {}, "extra_text": {}}, {"review_id": "YDVV6nZ84Bh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe authors propose a \"meta-algorithm\" for approximating various graph representation learning schemes: generate batches of random trees with fixed fanout (and possibly biased probabilities of selecting different edges), and use them to accumulate information to approximate operations on the graph.  The idea is beautifully simple, and generalizes running independent random walkers, an approach that is used in deriving many related algorithms.  The biasing and accumulation functions are user provided, and the authors show how different choices of these functions can be used to approximate a number of graph representation learning schemes.  The authors also provide a software framework, though it was inaccessible at review due to anonymization.  Experiments show the approach is much more scalable than competing approaches (though, to be fair, some of the competition was not targeting scalability).\n\n### Minor points\n\n- The \"CompactAdj\" format seems equivalent to compressed sparse row (or compressed sparse column) storage for the adjacency.  Is there any difference?\n- It might be worth commenting (possibly in appendices) on the data structures used for accumulation in the different concrete instances that are presented.  For example, the sparse matrix data structure used in 3.3.1 is presumably a neighbor list or equivalent, and not the CompactAdj format (since rebuilding the latter at every step seems needlessly expensive).\n- The claim at the end of section 4.1 that \"although naive calculation of $T^k$ is cubic, GTTF can estimate it in time complexity independent of the number of nodes\" is imprecise to the point of being misleading.  One can exactly compute a single row of $T^k$ for arbitrary $T$ via repeated sparse matrix-vector products time time proportional to the graph size times $k$, and one can do an approximate  computation of a row of $T^k$ even more cheaply using the method sketched here.  One can also get efficient estimates of various properties of matrix powers.  But actually getting estimates of all elements of the matrix $T^k$ in general is going to depend on the size of the graph, particularly when $k$ gets to the order of the graph diameter.\n\n### Typos\n\n- In the related work section, the table lists \"DGI\" -- I believe this is referring to DGL.\n- For the paper, I recommend writing out \"without loss of generality\" rather than using the abbreviation at the start of section 3 (unless it leads to going over space)\n- Add \"the\" before \"node embedding WYS\" at the start of 4.3.\n\n### Update\n\nThanks to the authors for their clarifications (and to the other reviewers).  I am more comfortable with my accept recommendation now, and have updated my confidence accordingly.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Summary: The authors propose to approximate operations on graphs, roughly
speaking by approximating the graph locally around a collection of
vertices by a collection of trees. The method is presented as a
meta-algorithm that can be applied to a range of problems in the
context of learning graph representations.

Discussion: The reviews are overall positive, though they point out a
number of weaknesses. One was unconvincing experimental
validation. Another, more conceptual one was that this is a 'unifying
framework' rather than a novel method. Additionally, there were a number of
minor points that were not clear. However, the authors have provided
additional experiments that the reviewers consider convincing, and
were able to provide sufficient clarification.

Recommendation:
The reviewer's verdict post-discussion favors publication, and I
agree. The authors have convincingly addressed the main concerns in discussion, and novelty is not a necessity: Unifying frameworks often seem an end in themselves, but this one is
potentially useful and compellingly simple.

Decision: Accept (Poster)