Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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.

Although the proposed idea seems interesting, there are several concerns about the paper.

1.	The 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.
2.	The novelty of the paper is also limited, consider it is extending an existing algorithm SIGN to heterogeneous version.
3.	I 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.
4.	It seems the numbers in Table 4 is higher than the ones in the original paper, such as HGT. 

review_title: 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.

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper extends from SIGN (https://arxiv.org/abs/2004.11198) model to heterogeneous graphs.

The 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:
(1) sample several subsets $R_i$ of relations; 
(2) sample relation subgraphs whose edges belong to $R_i$; 
(3) treat each subgraph as homogeneous graphs and perform neighbor aggregation (simply average). 
(4) Apply MLP on each node for node classification.

I have several questions about the proposed approaches:

(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)

(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.

(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).

Also, though the authors show superior experimental results, I have several concerns about experiment settings:

(1) About feature initialization. From Table 5, we can see that the proposed NARS method highly relies on the TransE
 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.

(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. 

(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.


Overall, 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.
review_title: Review #3

final_score: rating: 3: Clear rejection
review_content: 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. 

Overall, 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. 
review_title: Interesting Problem, but the novelty of the technical depth is marginal

final_score: rating: 6: Marginally above acceptance threshold
review_content: 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. 

One 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. 

The 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.

The 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. 

The 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. 

In 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. 

I 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:

Garcia-Duran and Niepert, Learning Graph Representations with Embedding Propagation, NeurIPS 2017

review_title: Broadening the scope of SIGN to multi-relational graphs

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