Scalable Graph Neural Networks for Heterogeneous Graphs
Authors: Lingfan Yu
Jiajun Shen
Jinyang Li
Adam Lerer
Venue:  (2021)
Keywords: Graph Neural Networks
Large Graphs
Heterogeneous Graphs

Abstract: Graph neural networks (GNNs) are a popular class of parametric model for learning over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on benchmark tasks by simply operating on graph-smoothed node features, rather than using end-to-end learned feature hierarchies that are challenging to scale to large graphs. In this work, we ask whether these results can be extended to heterogeneous graphs, which encode multiple types of relationship between different entities. We propose Neighbor Averaging over Relation Subgraphs (NARS), which trains a classifier on neighbor-averaged features for randomly-sampled subgraphs of the ‘metagraph‘ of relations. We describe optimizations to allow these sets of node features to be computed in a memory-efficient way, both at training and inference time. NARS achieves a new state of the art accuracy on several benchmark datasets, outperforming more expensive GNN-based methods.

Under review as a conference paper at ICLR 2021
SCALABLE GRAPH NEURAL NETWORKS FOR HETEROGENEOUS GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) a popular class of parametric model for learn- ing over graph-structured data. Recent work has argued that GNNs primarily use the graph for feature smoothing, and have shown competitive results on bench- mark tasks by simply operating on graph- smoothed node features, rather than us- ing end-to-end learned feature hierarchies that are challenging to scale to large graphs. In this work, we ask whether these results can be extended to heteroge- neous graphs, which encode multiple types of relationship between different en- tities. We propose Neighbor Averaging over Relation Subgraphs (NARS), which subgraphs
trains a classifier on neighbor-averaged features for randomly-sampae of the "metagraph" of relations. We describe optimizations to allow these sets of node features to be computed a memory- memory-efficient way, both at training and in- ference time. NARS achieves new state of the art accuracy several benchmark datasets, outperforming more expensive GNN-based methods.
INTRODUCTION
In recent years, deep learning on graphs has attracted great deal of interest, with new applications ranging from social networks and recommender systems, to biomedicine, scene understanding, and modeling of physics (Wu al. 2020). One popular branch of graph learning based on the idea of stacking learned "graph convolutional" layers that perform feature transformation and neighbor aggregation (Kipf & Welling 2017), and has led to an explosion of variants collectively referred to Graph Neural Networks (GNNs) (Hamilton et al., 2017, Xu et al.) 2018, Velickovic et al.) 2018). Most benchmarks for learning on graphs focus on very small graphs, but the relevance of such models to large-scale social network and e-commerce datasets was quickly recognized (Ying) ctt al. 2018). Since the computational cost of training and inference on GNNs scales poorly to large graphs, number of sampling approaches have been proposed that improve the time and memory cost of GNNs by operating on subsets of graph nodes or edges (Hamilton et al. 2017 Chen et al. 2017
Zou et al. 2019 Zeng et al.] 2019 Chiang al. 2019).
Recently several papers have argued that on a range of benchmark tasks - social network and e-commerce tasks in particular GNNs primarily derive their benefits from performing feature smoothing over graph neighborhoods rather than learning non-linear hierarchics of features as im- plied by the analogy CNNs (Wu al. 2019 NT & Machara 2019 Chen et al. 2019 Rossi al., 2020). Surprisingly, Rossi et al. (2020) demonstrate that one-layer MLP operating on concatenated N-hop averaged features, which they call Scalable Inception Graph Network (SIGN), performs com- petitively with state-of- of-teof-the-an art GNNs on large web datasets while being more scalable and simpler to use than sampling approaches. Neighbor-averaged features can be precomputed, reducing GNN training and inference to standard classification task.
However, in practice the large graphs used web-scale classification problems are often heteroge- neous, encoding many types of relationship between different entities (Lerer et al.) 2019). While GNNs extend naturally to these multi-relation graphs (Schlichtkrull et al. (018)) and specialized methods further improve the clear how to extend beighbor-averrginn approaches like SIGN to these graphs.
them (Hu et al.) [022bb] |aan al. 2019b), it is not
In this work, we investigate whether neighbor-averee graphs (HGs). We propose Neighbor Averaging over Relation Subgraphs (NARS), which computes neighbor averaged features for random subsets of relation types, and combines them into a single
approaches can be applied to heterogeneous

---

Under review as a conference paper at ICLR 2021
Heterogeneous Graph
Sample Relation Subeel R; R
Build Relation Subgraph 6,
Compute Neighbor- Avereged Feelurre
Aggragate 40
MLP Classiir
Oo
R3
[P P)
0
f
Re- LA p)
Gx-1
St p-
A P
02
P- P
Figure 1: Neighbor Averaging over Relation Subgraphs on heterogeneous graph G. G has three node types: Paper (P), Author (A), and Field (F), and three relation types: Paper cites Paper (P-> P), Paper belongs-to Field (P-+F), Author writes Paper (A-P).
set of features for a classifier using 1D) convolution. We find that this scalable approach exceeds the accuracy of state-of-the-ar GNN methods for heterogeneous graphs on tasks in three benchmark datasets.
One downside of NARS is that requires a large amount of memory to store node features for many random subgraphs. We describe approximate version that fixes the memory scaling issue, and show that does not degrade accuracy on benchmark tasks.
2
BACKGROUND
Graph Neural Networks are type of neural model for graph data that uses graph structure to trans- form input node features into more predictive representation for supervised task.
popular flavor of graph neural network consists of stacked layers of operators composed of learned transformations and neighbor aggregation. These "messsae-passingg" GNNs were inspired by spec- tral notions of graph convolution (Bruna et al. [0144 [Dffterrard et al. 2016 Kipf Welling 2017). Consider a graph G' with n vertices and adjacency matrix A E RT A graph convolution *
of node features x by a filter g is defined as multiplication by g in the graph Fourier basis, just as standard convolution is multiplication in Fourier space. The Fourier basis for graph is defined as the eigenvectors U the normalized Laplacian, and can be thought of as a basis of functions of varying smoothness over the graph. g * x = UgU*x
Any convolution g can be approximated by series of k-th order polynomials in the Laplacian, which depend on neighbors within a h-hop radius (Hammond et al. 2011). By limiting this approximation to k 1, Kipf & Welling (207)) arrive an operation that consists of multiplying node features by the normalized adjacency matrix, i.e. averaging each node's neighbor features. Such an operation can be viewed as a graph convolution by particular smoothing kernel. A Graph Convolutional Network (GCN) is constructed by stacking multiple layers, each with a neighbor averaging step followed by a linear transformation. Many variants of this approach of stacked message-passing layers have since been proposed with different aggregation functions and for different applications (Velickovic et al. 2018 Xu et al.) 22088) Hamilton et al.) 2017, Schlichtkrull al. 2018).
Early GNN work focused on tasks with small graphs (thousands of nodes), and it's not straight- forward to scale these methods to large-scale graphs. Applying neighbor aggregation by directly multiplying node features by the sparse adjacency matrix at each training step is computationally expensive and does not permit minibatch training. On the other hand, applying a GCN for a mini- batch of labeled nodes requires aggregation over receptive field (neighborhood) of diameter d equal to the GCN depth, which can grow exponentially in d. Recent work in scaling GNNs to very large graphs have focused on training the GNN sampled subsets of neighbors or subgraphs to allevate the computation and memory cost (Hamilton et al. 2017 Chen et al. 2007 Zou et al. 2019 Zeng et al. 2019 Chiang et al. 2019).
2

---

Under review as a conference paper at ICLR 2021
Rossi al. 20200) proposed different approach to scaling GCNs, called SIGN: As shown in Fig- ure 2 by eliding all learned parameters from intermediate layers, the GNN graph aggregation steps can be pre-computed as iterated neighbor feature averages, and model training consists of training an MI.P on these neighbor-averaged features. On benchmark tasks on large graphs, they observed that SIGN achieved similar accuracy state-of-the-art GNNs. The success of SIGN suggests that GNNs are primarily using the graph to "smooth" node features over local neighborhoods rather than learning non-linear feature hierarchies. Similar hypotheses have been argued in several other recent
works (Wu et al. 2019 NT & Maehara 2019 Chen et al. 2019 T
Standard GCNs extend naturally to heterogeneous (aka relational) graphs by applying relation-specifi learned transformations (Schlichtkrull et al. 2018). There have also been number of GNN variants specialized to het- erogeneous graphs. HetGNN (Zhang al.] (019a) per- forms fixed-size random walk on the graph and encodes heterogeneous content with RNNs. Heterogeneous At- tention Network (Wang et al. 2019b) generalizes neigh- borhood of nodes based on semantic patterns (called metapaths) and extends GAT (Velickovic al., 2018) with a semantic attention mechanism. The Heteroge- neous Graph Transformer (Hu et al., 2020b) uses an atten- tion mechanism that conditions on node and edge types, and introduces relative temporal encoding to handle dy- namic graphs. These models inherit the scaling limitation of GNN and are expensive to train on large graphs. Therefore, it is of practical importance to generalize the computationally much sim- pler SIGN model to heterogeneous graphs
9
e, a
Ω
$
02
Figure 2: SIGN Model. A is the 1-th power of adjacency matrix A. @ and ? are transformation parameters in MLP, and o and are non-lincar operators.
3 NEIGHBOR AVERAGING OVER RELATION SUBGRAPHS FOR HETEROGENEOUS GRAPHS
The challenge with adapting SIGN to heterogeneous graphs how to incorporate the information about different node and edge types. Relational GNNs like R-GCN naturally handle heterogeneous graphs by learning different transformations for each relation type (Schlichtkruil et al. 2018), , but SIGN elides these learned transformations. While one can naively apply SIGN to heterogeneous graphs by ignoring entity and relation types, doing so results in poor task performance (Table 4
In this section, we propose Neighbor Averaging over Relation Subgraphs (NARS). The key idea of NARS is to utilize entity and relation information by repeatedly sampling subsets of relation types and building subgraphs consisting only of edges of these types, which we call relation subgraphs. We then perform neighbor averaging on these relation subgraphs and aggregate features with a learned I-D convolution. The resulting features are then used to train an MLP, as in SIGN.
We take inspiration from the notion of "metapaths" proposed in Dong et al. (2017) and used by several recent heterogeneous GNN approaches (Wang et al.. 2019b). metapath sequence of relation types that describes a semantic relationship among different types of nodes; for example, one metapath in an academic graph might be "venue- paper- - author". which could represent "venues of papers with the same author as the target paper node". Information passed and aggregated along a metapath is expected to be semantically meaningful. In previous work like HAN (Wang et al., 2019b), features from different metapaths are later aggregated to capture different neighborhood information for each node.
In prior work, relevant metapaths were manually specified as input (Dong et al. 2017 Wang et al.) 2019b), but we hypothesized that the same information could be captured by randomly sampling metapaths. However, sampling individual metapaths doesn't 't scale well to graphs with many edge
'SIGN primarily differs from these other proposed methods by concatenating from different numbers of hops of feature aggregation. This addresses the need to balance the benefits of feature smoothing from large neighborhoods with the risk of "oversmoothing" the features and losing local neighborhood information when GNNs are too deep (Li et al. 2018), allowing the classifier to learn a halance hetween features from different GNN depths.
aggreggtee features
3

---

Under review as a conference paper at ICLR 2021
types: for graph with M edge types, would require (M) metapaths to sample each edge type in a single metapath. As a result, one might need to sample a large set of metapaths to obtain good prediction results, and in practice we obtained poor task performance by sampling metapaths.
We observe that metapaths are an instance of a more general class aggregation procedures: those that aggregate at each GNN layer over subset of relation types rather than a single relation type. We consider a different procedure in that class: sampling a subset of relation types (uniformly from the power of relation types), and using this subset for all aggregation layers. This procedure amounts to randomly selecting K relation subgraphs each specified by a subset of relations, and performing L-hop neighbor aggregation across each of these subgraphs. We found that this strategy led to strong task performance ( (55), but it's possible that other aggregation strategies could perform even better.
Given heterogeneous graph G' and its edge relation type set R. our proposed method first samples K unique subsets from R. Then for each sampled subset R, S RR we generate relation subgraph
G from G' in which only edges whose type belongs to RG are kept. We treat G; as a homogeneous graph, and perform neighbor aggregation to generate L-hop neighbor features for each node.
Let Ho.0 be the input features (of dimension D) for node v. For each subgraph Gi, the 1-th hop features H n
are computed
Σ uEN,(v) [N((w]]
H -
where (i(1) is the set of neighbors of node in Gi,
3.1 AGGREGATING SIGN FEATURES FROM SAMPLED SUBGRAPHS
For each layer 1, we let the model adaptively learn which relation- elation--ubgraph features to use by aggre- gating features from different subgraphs G2 with a learnable 1-D convolution. The aggregated (-hop features across all subgraphs are calculated as
H
Σ au H
(3)
where H is the neighbor averaging features on sub- graph G, and a, is a learned vector of length equal to the feature dimension D. In total, a is a tensor of learned coefficients of size K
Model
# parameters DL DKLK D2L DLK
SIGN
NARS (concat)
We use a 1D convolution to reduce the number of input parameters the subsequent SIGN classifier, avoiding multiplicative increase in the number of model pa- rameters by a factor of K, as shown in Table Having fewer parameters reduces the cost of computation and memory and less prone to overfitting.
NARS (ID conv)
Number of parameters (equivalently, FLOPs per prediction) in vanilla SIGN and NARS. If features are concatenated in NARS, the number of parameters grows multiplica- tively, but this resolved by using 1D convolu- tion to reduce input dimension to classifier.
Table 1:
A classifier is then trained on the aggregated node fea- tures to predict task labels, using the MLP architecture described in SIGN (Rossi al. 2020)
3.2 NODE TYPES WITHOUT INPUT FEATURES
One consideration for learning heterogeneous graphs is that input features are not always pro- vided for all node types. Take the OAG academic graph as an example: in prior work, paper nodes were featurized with language embeddings for the paper title using a pretrained XLNet model (Yang et al. 2019). But for other node types like author, field, venue, node features were not provided, so any features must be inferred from the graph.
There are different ways to handle these "featureless" node types, and the best approach might be dependent the dataset and task. On the tasks we examined, we found it helpful to use relational
4

---

Under review as a conference paper at ICLR 2021
Node Tynes
Edge Types
Dataset
#P
#AA
41
#V
#PA
FFT
UPP
BA.1
WP.V
ACM
4,025
17,431
73
13,407
4,025
OGB MAG
736,389
1,134,649
59,965
8,740
7.145,660
7,505,078
5,416,271 5,597,606
1,043,998
OAG (CS)
5,597,605
5,985,759
27,433
16,931
15,571.614
47,462,559
7,190,480
31,441,552
Table 2: Statistics of three academic graph datasets. Institute (I) and Venue (V)
The node types are: Paper (P), Author (A). Field (F),
graph embeddings (Bordes et al. 2013) trained on the heterogeneous graph as the initial features for nodes without provided input features. Note that these graph embeddings do not make use of the input features provided for the papers.
We compare the effectiveness of using different types of features for nodes that don't 't have intrinsic (i.e. content) features in Section 5.4
MEMORY FOOTPRINT OPTIMIZATION
NARS allows trainable aggregation of features from sampled subgraphs. However, even though the model is trained in minibatch fashion on GPU, we have to precompute and store all the subgraph- aggregated features in CPU memory. The amount of memory required to store these pre-computed features is O(LLDK) which is K times more than SIGN. So for large heterogeneous graphs with many edge types, there tradeoff between sampling more subgraphs in order capture semantically meaningful relations, and limiting the number of subgraphs to conserve memory during training.
To address this issue, we propose to divide the training into multiple stages. In each stage which lasts several epochs, we train the model with subset of the sampled subgraphs. Concretely speaking, approximate Equation (3) with the following equation:
H
Σ G,EStNCS
bu.1 Hi aH
(4)
In this equation, 5(0) is the randomly sampled subset of the K subgraphs used in stage 4, and H is the approximation of H at stage t.
Equation is equivalent to setting dgl = b,. + aa!i
(t-1) for G2 E s(t) and (++1) = aat? for a.t
G E ((*) in Equation (3), so the values of can be updated after each stage. The approximated H(t) used as the input the classifier during end-to-end training across all stages. The detailed training process is shown in Algorithm 2 in the Appendix.
Our sub-sampling approach reduces memory usage during training to O(NLD)S() ), and in prac- tice, we found that even |(t)| = produces decent results and outperforms the accuracy of current SOTA models (see (5.5). One thing worth pointing out is that even though this memory optimization requires regenerating features for [s())] subgraphs every few epochs, the generation can be done on CPU and can completely overlap with GPU training, and hence does not slow down training.
For inference, since all model parameters in Equation memory optimization method, we simply generate features for each sampled subgraph and compute the aggregation in place. The memory overhead for inference is therefore also only OLD...
fixed, instead of using proposed
EVALUATION
In this section, we evaluate NARS several popular heterogeneous graph datasets and compare with state-of-the--rt models. We also investigate the effect of different ways to featurize nodes without input features, and how the memory optimization described in 44fffect prediction accuracy.
5.1 EXPERIMENTAL SETUP
We evaluate our model using node prediction on three popular academic graph datasets: ACM (Wang al. 2019b), OGB-MAG (Hu al. 2020a), and OAG (Sinha et al., 2015
Datasets & Tasks
5

---

Under review as a conference paper at ICLR 2021
Hyper-parament parameters
# Model Parameters
Dataset
hidden
layers (L)
# subgraphs (K)
TransE size
NARS (Ours)
SIGN
R-GCN
HAN
HGT
ACM
2
128
0.40M
0.39M
0.14M
0.25M
0.26M
OGB-MAG
512
5
256
4.13M
4.12M
9.18M
26.88M
OAG-Venue
256
3
2.21M
40.60M
8.26M
OAG-LI-Field
256
3
400
1.41M
1.3M
1164M
7.43M
Table 3: Training hypee-parameters & number of parameters for each model. For hyper-parameterss # hidden # layers, we adopt values from HAN for ACM, and values from HGT for OGB-MAG and OAG. subgraphs sampled for NARS is picked to be small while producing good and stable results. TransE size is selected based on the size of the graph.
Dataset Metric
ACM
OGB-MAG
OAG- Venue
DAG-LI-Field
Accuracy
Accuracy
NDCG
MRR
NDCG
MRR
R-GCN
.930+-000
+500+.0011
.481+.004
.32+H.055
852+-0002
843+F.002
HAN
.922+-002
H
.919+.003
498:t.001
.49:+.014
.322#.014
888
.899+.003
SIGN
.919t.001
.811:.001
.506::001
.327#0001
.839=.001
.836+.003
NARS (Ours)
.931+.004
.521
.520::.03
.342+.003
.608
.857+.003
Table Performance of NARS vs. baseline models on different datasets and tasks. All numbers are average and standard deviation over 5 runs. Bold numbers indicate best model(s).
Tang et al. 2008 Zhang et al. 2019b). The tasks involve predicting paper's category, its publishing venue, or its research field on these three datasets. We summarize the statistics of the datasets in Table 2 and put the details of each dataset in Appendix A.3
Baselines & Metries We compare NARS with four baseline models: R-GCN (Schlichtkrull al., 2018). HAN (Wang et al. 2019b), HGT (Hu et al. (020b). and SIGN (Rossi et al. (020). The first three models are designed for heterogeneous scenarios and be naturally applied on all datasets. The vanilla SIGN model, however, is for the homogencous graph setting. Therefore, we ignore the node types and edge types when training SIGN. We use the best implementation we can find for each baseline model: for HGT, we use the authors' (original implementation, For SSGN and HAN we use the implementation by Deep Graph Library (Wang et al. 2019a). For R-GCN implementation by Py PoTcch Geometric (eyy &
we use the
We report test accuracy (micro-Fl) for the ACM and OGB-MAG datasets and NDCG and MRR for the OAG dataset, using the model from the epoch that performs best on the validation set. For each experiment, we run five replicates and report the average and standard deviation across replicates.
Training GNN baselines the OGB-MAG and OAG datasets is intractable due memory usage, unless sampling is used. We adopt neighbor sampling (Hamilton et al. (017]) for R-GCN and HGT's custom sampling method, but were unable evaluate HAN on these datasets, since is unclear how to train this model with sampling while following metapath constraints.
Training settings We train NARS with learning rate 0.001, dropout rate 0.5 and the Adam op- timizer. For nodes that don't 't have input features, al. 2013) as input. During the preprocessing phase, we sample K subgraphs and pre-compute the aggregated features of I. hop neighbors for each node. Table shows shows the training parameparseeters for our model, as well as a comparison of model sizes (in terms of the number of parameters) across ours and various baseline models. Though we try use the same hyper-parameters for all models, we note that our extension to SIGN results in simple model and in most cases has significantly fewer training parameters.
pre-trained TransE embeddings (Bordes)
Detailed implementation and configuration can be found in our open-sourced GitHub repository?
5.2
RESULTS
"To be relcased
We improved the reported performance of HGT by 5% by sampling 10 times for target nodes and using the average of predictions, to reduce sampling variance.

---

Under review as a conference paper at ICLR 2021
0.55
I 0.5208
0.5235
0.51118
0.50
T T0.5032
Test Accuracy
Test Accuracy
0.45
0.48
0.40
NARS (CPU Features! Features)
0.46
0.35
SIGN
0.44
0.4409
HGT
R-GCN
R-GCN
0.42
NARS
0.30
10
20
30
40
50
100
200
300
1
3
5
11
Training Time (min)
Relation Subgraph Sampled
Figure 3: Training speed of NARS (sampling 8 subgraphs) and baseline models on the OGB-MAG dataset. NARS leads to higher final accuracy less training time. NARS training is much faster when features be stored GPU (dashed line).
Figure 4: Accuracy of sampling different bers of relation subgraphs on the OGB-MAG dataset. Sampling more relation subgraphs improves test ac- curacy while reducing variance across replicates.
Table summarizes the performance of NARS and baseline models on different datasets and tasks. NARS outperforms all baseline methods all datasets and node prediction tasks that we evaluated. In particular, NARS improves test performance by up to 4% compared to the current state-of-the-ar model (HGT) large datasets like OAG and MAG. Compared naively applying SIGN by treat- ing the graph as homogeneous, NARS improves performance by to 8%. It is quite surprising that NARS exceeds the performance of existing tfatcof-the-aa GNN methods since NARS computa- tionally much simpler than the baselines; like SIGN, it does not learn any feature hierarchies over graph neighborhoods, but merely learns a classifier on graph-smoothn features.
Figure 3 compares the training speed of NARS and public implementations of baseline methods on OGB-MAG dataset. We did not include the time for pre-training TransE embeddings (40 min) since all models benefit from using them (5.4). In Figure the solid blue line labelled NARS (CPU features) refers to an implementation that stores all compued features on the CPU and transfers them to the GPU demand during each mini-batch training. This NARS implementation not only achieves superior accuracy. but also is substantially faster train than competing approaches. We further improve NARS training speed by storing pre-computed features the GPU if space permits, as shown by the dotted blue line labeled NARS (GPU features).
5.3 EFFECT OF NUMBER OF SUBGRAPHS SAMPLED
We have shown in Table that sampling relation subgraphs produces better results than treating the graph as homogeneous. Now we use the OGB-MAG dataset to perform an ablation study on how the number of sampled subgraphs affects the performance.
OGB-MAG dataset has edge relation types, hence the edge relation set has in total 15 non-empty subsets. Among the 15 subsets, only 11 are valid (others don't 't touch paper nodes for prediction or are disconnected). In Figure 4 we randomly sample subsets of size 1, 3, 5, from which contains the 11 valid subgraphs. For each point in the figure, randomly sample different subsets and report the average and standard deviation.
As shown in Figure 4 the average accuracy improves while the variance decreases the number of sampled subgraphs increases, which expected since sampling more reduces sampling variance and increase the chance cover relation subgraphs that more semantically meaningful. On the OGB-MAG dataset, sampling 2 5 subgraphs always outperforms current state-of-the-art models like HGT (green line) and R-GCN (red line).
5.4 EFFECT OF DIFFERENT STRATEGIES TO HANDDE FEATURELESS NODES
In this section, we compare how different ways of featurizing nodes that don't 't have input features affect the performance of NARS OGB-MAG dataset. In the dataset, only paper nodes have input language features generated using word2vec, and all other node types are not associated with any input features.

---

Under review as a conference paper at ICLR 2021
Padding Zeros
Average Neighbors
Metapath2vec Embs
TransE: Embs
NARS
44622.0022
.4227.00018
.5187=00011
52144.0016
SIGN
.4007+-0010
.4028 .021
.4685 1011
.881011.0099
HGT
.597=.00227
.8891=00021
.4962=.0026
.4982:1.013
R-GCN
4811=100028
.777
.5013:t.0019
550111.0005
Table 5; Comparison of different ways to featurize nodes with no input features on the OGB-MAG datasct. All models achieve their best performance with pre-trained TransE: graph embedding features, Featurization is especially important for neighborraverrging approaches (SIGN and NARS).
We tried four different ways to generate features for the featureless nodes: 1) padding zero; 2) taking the average of features from neighboring papers nodes; 3) using pre-trained Metapath2vec embedding: 4) using pre-trained TransH relational graph emheddings with I.2 norm. We followed the same sepeerparaaeter listed in Table
As shown in Table 5 unsupervised graph embedding methods greatly improve model accuracy, especially for SIGN and NARS. We use TransE embeddings in the rest of this section because it achieves the best accuracy, and because metapath2vec embeddings require manually specifying metapaths, which we seek to avoid.
5.5 EFFECT OF TRAINING WITH SUBSET OF SAMPLED SUBGRAPHS
In section 4 we proposed to train with a sub- sampled set from all K sampled relation sub- graphs to reduce CPU memory usage. Fig- S we vary the number of relation subgraphs in the randomly sampled subset in each stage on OGB-MAG dataset to see how this approach af- fects accuracy. The blue dashed line at the top of the figure is the accuracy for training with all 11 valid relation subgraphs. The blue point with error bar represents the average and stan- dard deviation for sampling a certain number of subgraphs from the 11 valid relation subgraphs in each stage. Performance improves when more subgraphs are sampled in each stage, but sampling a single subgraph in each stage leads to good performance with small variance, out- performing existing models.
0.52
0.5162
I 0.5191
0.5205
0.5208
I 0.170
Test Accuracy
0.51
0.50
HGT
R-GCN
NARS (all)
NARS (sample)
2 4
# Relation Subgraph Trained
Figure 5: Training with different numbers of sub- graphs each stage 44 on OGB-MAG dataset, to improve memory efficiency. Good test accuracy is achieved with even single subgraph sampled per train- ing stage.
CONCLUSION
Simplified GNNs like SIGN that do not require learned aggregation promising new class of models for graph learning due to their simplicity, scalability, and interpretability. We present Neigh- bor Averaging over Relation Subgraphs. a novel GNN architecture for heterogeneous graphs that learns a classifier based on a combination of neighbor-averaged features for random subgraphs specified by a subset of relation types. NARS beats ofate-of-the-ar task performance on several benchmarks despite its simpler and more scalable approach.
This work provides further evidence that current GNNs might not learn meaningful feature hier- archies on benchmark datasets, but are primarily functioning by graph feature smoothing. Future advances in GNN modeling may realize the benefits of "deep" learning for these tasks, or may be that this modeling is not necessary for many important graph learning tasks.
One remaining limitation NARS is that it doesn't explicitly handle heterogeneous feature types, averaging together features of different types (e.g. language features graph features). While this performs adequately on benchmark datasets, it is an unsatisfying approach for industry graph datasets with potentially dozens hundreds of distinct entity types, each with their own distinct features. In these situations, existing GNNs (c.g. R-GCN) may be more appropriate, and neighbor averaging approaches suitable for this situation are area for future work.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances neural information processing systems, pp. 2787-2795, 2013.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann Lecun. Spectral networks and lo- cally connected networks on graphs. International Conference on Learning Representations (ICLR2014), CBLS, April 2014, pp. http-openreview, 2014.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv: 2017.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection on 2019.
graph classification. arXiv preprint
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. -3522, 2016.
Yuxiao Dong, Nitesh Chawla, and Ananthram Swami. metapath2vec: Scalable representation learning for heterogeneous networks. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 135-144, 2017.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. NIPS, 2017.
David Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 3022):129-150, 2011.
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. arXiv preprint arXiv:2005.006: 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. Heterogeneous graph transformer. In Proceedings of The Web Conference 2020, pp. 2704-2710, 2020b.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich. ahtorch-biggraph. A large-scale graph embedding system. arXiv preprint arXiv:1903.12887, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. arXiv preprint arXiv:1801.07606 2018.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters.
arXiv preprint arXiv: wwX.v::905.095500 2019.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Fed- crico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004.11199 2020.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.

---

Under review as a conference paper at ICLR 2021
Arnab Sinha, Zhihong Shen, Yang Song, Hao Ma, Darrin Eide, Bo-June Hsu, and Kuansan Wang. An overview of microsoft academic service (mas) and applications. In Proceedings of the 24th international conference world wide web, pp.
2015.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Ametminer: extraction and mining of academic social networks. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 990-998, 2008.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
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-centrie, highly-performant package for graph neural networks. arXiv preprint arviv (etiv:1900) 0e0.9999910911 2019a.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip S Yu. Heterogeneous graph attention network. The World Wide Web Conference, pp. 2022-2032, 2019b.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv:1902.07135 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. Xlnet: Generalized autoregressive pretraining for language understanding. Advances in neural information processing systems, pp.
2019.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. wwXiv:/907.049331 2019.
Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heteroge- neous graph neural network. Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 793 803, 2019a.
Fanjin Zhang, Xiao Liu, Jie Tang, Yuxiao Dong, Peiran Yao, Jie Zhang, Xiaotao Gu, Yan Wang, Bin Shao, Rui Li, et al. Oag: Toward linking large-scale heterogeneous entity graphs. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 2019b.
pp.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, 2019.
10

---

Under review as a conference paper at ICLR 2021
A
APPENDIX
A.1 ALGORITIMM TO TRAIN NARS
demonstrates the detailed training algorithm for Neighbor Averaging Relation Subgraphs.
Algorithm
Algorithm 1: Neighbor Averaging over Relation Subgraphs
Input: G heterogeneous graph
Input: R the set of relations in G
Input: K number of relation subgraphs sample
Input: L number of layers in MLP model
Input: Hinput node input features
/* Generate mult --hp nei neighoorhood-average features
def GenNeighhorFeatureCC::
// Build adjacency matrix for G regardless of edge types
+ BbulddttjacencyMatrri((f
// Divide nonzeros in each row by node in in-degree
W + Row
Ho < Himput:
for +- to do
Hi W
return Ho, HI...., Hrs
Sample K unique relation subgraphs from G and R def SampleReeationSuugrrphiii. K):
P + GetP Net < Sample ithout Replacement(P. K); E < Set
for R4 do
E, + 0;
for E do
if e.pp R, then
E, - +
G;
return Gb, G...,...
Prepreocssing S + CempleeleeationSSuuggqppll K);
for G; S do
L Hi Hf...., Hi,
/* Training
// Any MLP classfier, SIGN model for example model + MLPMMdeel);
for epoch
MAX_EPOCI do
// Compute Equation 3 for to L do
11 Eatll
loss model.forwardd (HHi)); loss.back loss.backword() model);
11

---

Under review as a conference paper at ICLR 2021
A.2 ALGORITHM TO TRAIN WITH REDUCED MEMORY USAGE
Algorithm 2 demonstrates details about how to further sub-sample subgraphs in each stage from the set of relation subgraph S and use Equation (4) train the model. In Algorithm 2 we omit the layer number to make it more concise.
A.3 DATASETS
ACM We use the ACM dataset from Heterogeneous Graph Attention Network (Wang et al, 2019b), which is an academic graph extracted from papers published in ACM conferences (KDD, SIGMOD, SIGCOMM, MobiCOMM, and VLDB). The HAN author-provided version removed the field and author node types. Therefore,
used the version re-constructed by DGL (Wang et al. 2019a). this dataset, only paper nodes have Bag-of-Worde features. Papers are divided into three classes and the task is predict the class for each paper.
OGB-MAG Open Graph Benchmark (Hu et al., 2020a) is an effort to build standard, large and challenging benchmark for graph learning, which contains a large collection of datasets that cover important tasks on graphs and wide range of domains. Leaderboards are set up for each dataset and performance of state-of-the-ane models listed with open-sourced implementation reproduce results. We evaluate our approach the MAG benchmark from OGB node prediction category, which is a heterogeneous network extracted from Microsoft Academic Graph (MAG). The papers published 349 different venues and they come with Word2 features. The task here is to predict the publishing venue for each paper.
OAG Open Academic Graph (Sinha et 2015 Tang al. 2008 Zhang al.) 2019b) is the largest public academic graph with more than 178 million nodes and 2 billion edges. We use the pre-processed CS domain c provided by the authors of Heterogeneous Graph Transformer (HGT) (Hu et al. 2020b) in order to have a fair comparison with HGT. Field nodes are further divided into 6 levels (LO L5) and a result, the graph comes with 15 edge types, adding rich edge relation information to the graph. Each paper is featurized with a language embedding generated by pre-trained XI.Net on its title. Following HGT, we evaluate two tasks on paper nodes: predicting publishing venues and predicting LI field (multi-label), One potential issue with OAG dataset is indirect information leakage since target nodes have edges connecting to ground truth label nodes in OAG graph. To address this issue, for each task, we remove all edges between paper nodes and corresponding label nodes we are to predict. For example, if the task is predicting venues of papers, remove all edges between paper nodes and venue nodes.
'HGT authors only shared the CS component. Also they performed filter step make the graph denser.
After the filtering, there 544244 papers, 45717 fields, 510189 authors, 9079 institutes, and 6933 venues left.
12

---

Under review as a conference paper at ICLR 2021
Algorithm 2: Train with subset sampled subgraph
Input: S a set of K sampled subgraphs
Input: T number of epochs in each stage
Input: p number of subgraphs used for training in each stage
model f MLLMModelO
Randona (niidddodoo__i((aa)))) [nit((an));
// Initialize history of aggregated features using Equation
( + 0:
for G; E do
H' t Cen.Neighbor
( (10) a.H":
Sample subset 5(0) from
((0) + SumpleSuusee(SSpp)
for G, E ((0) do
// Generate neighbor feature for each sampled G, E S())
H' + www.NeiighooFeatuee(e
// Initialize to
6; 4 0;
// Initialize to 1
1=
// Initialize stage t to
1;
for epoch +- 1 to EPOCH do
// Compute approximated aggregation following Equation
(1 + (H!;+
for G, E (()) do
L H + (*)) + b;
loss ()
loss. bossbbckwward); grodient- wuw.rettduuuaaeemmdeleeee. (b;),a);
epoch % = then
// Update history of aggregation H(O) <- (H(11));
for G, E (() do (1() +- (+t) b;
// Update a;
for G; s(t) do
a; b, -0;;
for G, d s() do
aa;;
// Increment stage
(- 1;
Re sample ((t) from
5(0) + SampleSubsel
for G, E 8(t) do
// Generate neighbor feature for newly sampled G, S(t)
H' +
// Re-initialize b, to 0
b; + 0;
// Re iriiiiiaaiize a to 1
13


Reviews:
[{"review_id": "zXybr9FEmON", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 extends from SIGN (https://arxiv.org/abs/2004.11198) model to heterogeneous graphs.\n\nThe SIGN model argues that simply applying MLP on graph-smoothed node features (concatenating k-th hop neighbor features, k $\\in$ [1-L]) can achieve similar results compared with learnable aggregation applied in GNNs. To extend to the heterogeneous graph, this paper proposes to sample relation graphs, by:\n(1) sample several subsets $R_i$ of relations; \n(2) sample relation subgraphs whose edges belong to $R_i$; \n(3) treat each subgraph as homogeneous graphs and perform neighbor aggregation (simply average). \n(4) Apply MLP on each node for node classification.\n\nI have several questions about the proposed approaches:\n\n(1) The difficulty of heterogeneous graphs is that each node might have different types of features. For example, in a social network, nodes can be associated with image, text, or some discrete profiles. Thus, the neighborhood smoothing only works when the input features are both 1) already very informative, and don't need too much transformation; 2) features from different node types are projected to the same space. Therefore, I'm afraid the authors' proposed aggregation might not generalize to more complicated heterogeneous graphs. (It seems that during experiments, the authors utilize TransE to pre-train embeddings for all the nodes, so that they are naturally within the same space, making the problem simpler. One evidence is that when using other feature initialization strategies, such as simple average, the performance of this model drops significantly)\n\n(2) Also, it's confusing to me why can we fuse all the subgraphs with different subgraph schema. Intuitively, with different relation set, the semantic of the relation subgraph should be very different, but the authors seem to treat them equally. It would be better if the authors can provide some analysis on this, for example, for a given node, what is the variance of final node embeddings calculated with subgraphs of different relation sets.\n\n(3) How to get the inference results for large graphs? It seems that the proposed method should get a different predictions for each node with a different relation set. So which set the authors to use? Complete set or average over random sampling? (If it's random, the reported variance, which is close to 0, seems to be very strange).\n\nAlso, though the authors show superior experimental results, I have several concerns about experiment settings:\n\n(1) About feature initialization. From Table 5, we can see that the proposed NARS method highly relies on the TransE\n embedding initialization. When using a standard feature initialization method (such as average neighbors), the results are much lower than HGT and R-GCN. However, the authors didn't provide implementation details about how to train such TransE embedding (normally it's weird to use TransE for heterogeneous graph, as the node number can be much larger than the knowledge graph and we don't have that much relation type. For example, two papers published by the same author and on the same venue might have exactly the same TransE embedding, if we don't consider text input. So it's confusing to me why the results with TransE embedding is better). The authors should better elaborate on this part or release the code for clarity.\n\n(2) About baseline results. Since the utilization of TransE embedding, the experimental settings of the baseline are different from the original papers. But there's still some confusing part. For example, the HGT model's implementation on OGB-MAG uses neighbor average strategy, and the accuracy result is 0.5, while the result reported in table 5 is 0.489. Also, the model parameter is not matched with the reported number. \n\n(3) About inference time. As discussed above, I'm not sure how the proposed method can efficiently get accurate inferences for all the nodes in the test set. If the authors want to claim their method is more scalable, it would be better to include the inference time comparison.\n\n\nOverall, I think the simplified procedure (direct neighbor average) over heterogeneous graph limits the usage of this model, and there's also some unclear part in experimental settings.", "extra_scores": {}, "extra_text": {}}, {"review_id": "WJVB599S8lG", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 studied heterogeneous graph embedding with graph neural networks. The authors proposed an approach which samples multiple different subgraphs containing a subset of relations and then aggregate the node representations from different subgraphs with attentions. Experimental results on some big data sets prove the effectiveness and efficiency of the proposed approach. \n\nOverall, heterogenous graph embedding with graph neural network is a very important and interesting problem with a variety of applications. However, the novelty of the proposed approach seems to be quite marginal, and I am not quite convinced by the proposed approach. Why are we able to get better results by first sampling a subset of relations to get the subgraph and then aggregating the node representations from different subgraphs? It seems weird to be as a randomly selected subset of relations do not convey any specific semantic meanings as traditional metapath based approaches. I am also surprised by the very small standard deviation in Table 4, which is not consistent with results reported in existing literature on the tasks of node classification. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "3PImdhRId5K", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The authors propose a method to broaden the scope of SIGN, a technique recently introduced for single-relational graphs. The method allows SIGN to also be applied to multi-relational graphs (often called heterogeneous or knowledge graphs in different communities). In SIGN, various powers of the Laplacian are precomputed. For each power, the features of the nodes of a node’s neighborhood are averaged and (e.g., with an MLP) projected into a node vector representation. This is then used to classify the node. \n\nOne way to apply SIGN to multi-relational graphs would be to conflate all relation types into a single relation type. The authors show that this doesn’t work well. \n\nThe authors then propose the following: take the set of all relation types R and sample a subset R’ from it. Construct the subgraph induced by R’ by only keeping edges of relation types in R’. Then treat all of these relation types as one (turn into a single-relational subgraph) and apply (essentially) SIGN to this subgraph. Do this several times, that is, sample subsets of R several times. Finally aggregate the representations coming from each of the application of SIGN to the sampled subgraphs.\n\nThe authors then also discuss what to do if the nodes do not have attributes (features) and ways to improve the memory efficiency of the approach. \n\nThe authors then proceed to empirically evaluate their method. They compare to existing approaches (such as R-GCNs) and show that NARS (the name of their approach) is competitive with these existing methods. Often it is significantly better. They also perform several types of ablation studies, analyzing the impact of choices such as the number of subgraphs sampled. Generally, I would say that the experiments are well done and look at various different important questions. \n\nIn summary, I don’t have much to criticise. The only shortcoming is that the method is more or less an adaptation of SIGN to the multi-relational setting. I want to be careful to lament a “lack of novelty” here, because it is still a good contribution to broaden the scope of an existing method to a larger class of problems. However, one thing I’m missing is a more thorough analysis of the sampling strategies one could use. What is analyzed is the number of subgraphs sampled. But this is based on one way of sampling subgraphs (based on first sampling relation types and inducing the graph based on this). What I’m missing are: sampling subgraphs from the Gaifman graph; and sampling multi-relational graphs and applying R-GCN on each of those and aggregating. The latter is probably less efficient, but I would conjecture also much better than running one R-GCN. Again, see related work below. It has been shown before that sampling multi-relational subgraphs can add robustness of the model to overfitting. Overall, I would tend towards accepting the paper but I would really like to see more analysis on different sampling strategies. \n\nI would encourage the authors to consider as related work a paper from 2017 which is one of the first to propose neighborhood sampling for GNNs (much earlier than most papers you mention in this context) and which is one of the first ones who simply average (learned) features but with an unsupervised objective:\n\nGarcia-Duran and Niepert, Learning Graph Representations with Embedding Propagation, NeurIPS 2017\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1tWiuOT9FQi", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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 aims to propose a new GNN for heterogeneous graphs, which is scalable to large-scale graphs. The proposed idea is to leverage an existing model called SIGN, which simplifies GCN by dropping the non-linear transformation from intermediate layers, and extend it to heterogeneous graphs. The results on several benchmark datasets show the proposed approach is better and faster than baselines.\n\nAlthough the proposed idea seems interesting, there are several concerns about the paper.\n\n1.\tThe description of the methodology is very vague. For example, Fig. 1 is presented without detailed explanation. It is unclear how the features computed by different subgraphs can be aggregated, especially consider nodes only appear in a subset of those subgraphs. The formula in Eq. (2) and (3) do not help due to their simplicity.\n2.\tThe novelty of the paper is also limited, consider it is extending an existing algorithm SIGN to heterogeneous version.\n3.\tI am not fully convinced the simplified GNN works better than some other GNNs designed for heterogeneous networks, such as HAN and HGT, which contains attention scheme and carefully models the message type in the GNN framework. According to other simplified GNN paper, their performance is just comparable to their counterpart but not better, and usually the results are worse than the attention-based one.\n4.\tIt seems the numbers in Table 4 is higher than the ones in the original paper, such as HGT. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposed an extension of the SIGN model as an efficient and scalable solution to handle prediction problems on heterogeneous graphs with multiple edge types.  The approach is quite simple: (1) sample subsets of edge types, then construct graphs with these subsets of edge types and (2) compute node features on each such graph as if they have only a single edge type, (3) then aggregate the representations from multiple graphs into one using an attention mechanism, and (4) train MLPs on node representations as in SIGN.  Results show that such a simple method can produce quite good results, and is very efficient and scalable.

The reviewers of this paper put it on the borderline, with 3 out of 4 leaning toward rejection.  The most common criticism is the lack of novelty.  Indeed this paper is an extension of prior work SIGN, and the proposed approach is simple.  However, I personally think the simplicity and the great empirical results is rather the strength of this paper.

The authors also did a good job addressing reviewers’ comments and concerns in the discussions, but a few reviewers unfortunately didn’t actively engage in the process.

I'd really encourage the authors to improve and highlight the strength of this paper more and submit to the next venue.
Decision: Reject