Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper is to improve GCN by considering different hops relationship of the network. It starts with the observation that for networks with complete homophily, complete heterophily and randomness, 1-hop network, 1-hop neighbors, 2-hop neighbors and k-nearest neighbor (kNN) are more suitable as neighborhoods for information propagation for GCN, respectively. Therefore it proposed a new algorithm: U-GCN, which first individually propagates node information under different hops of graphs and then combine their results using discriminative aggregation. It compares with traditional GCN methods in small scale datasets.
main_review: The paper is well written and easy to understand. I think it is quite meaningful to study the information propagation under different types of graph. However I still have several concerns and suggestions as below:

1) Lots of GCN methods are using skip connections, so in theory it will consider 1 hop, 2 hops, and N hops relationships. So what is the main different between the proposed method and skip connection strategy. Any comparison with it?

2) the computation issue. I think the proposed method is quite expensive in terms of computation. As 1: it needs to for KNN graph using node features, which is known to be very expensive. 2: it needs to compute three separate GCN and then combine them together. In terms of memory and computation time, it would be at least 3 times larger/slower than GCN. Is this the reason why only small scale datasets (with # of nodes less than 20k) are tested?

3) The fair comparison is to compare different methods under the same number of parameters, as U-GCN will introduce more parameters (at least 3x more parameters) than other GCN based methods.

4) the performance of the proposed method is still far from SOTA. For example in Cora dataset, SOTA can achieve 90%+ accuracy (https://paperswithcode.com/sota/node-classification-on-cora), while the proposed method is only 84%. And the compared methods are all traditional methods with no comparison with SOTA methods.
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes Universal GCN, an architecture built on top of GCN that utilizes 3 different neighborhoods per node to generate 3 node vectors that are then fused together via an attention mechanism. The 3 different neighborhoods are:
1. 1-hop neighborhood of the node
2. 2-hop neighborhood of the node
3. kNN based neighborhood of the node where proximity is calculated based on cosine similarity of node attributes

To motivate the need for this architecture, the authors first elaborate on phenomena like homophily, heterophily, and presence of random connections in real-world graphs to highlight that GNNs that solely rely on homophily may not perform well on real-world graphs.
main_review: Overall, this paper is an interesting one. I like the motivation presented by the authors for their work. Indeed homophily is not the only phenomenon in graphs, and graph neural networks should be able to capture other phenomena like heterophily or some any other neighborhood pattern present in a given graph. To be able to do so, we do need GNNs that have higher discriminative power than vanilla GCNs. The authors demonstrate this empirically on artificially generated graphs by comparing the attention values given to neighborhood representations generated from 1-hop, 2-hop and kNN based neighbors which show that they respectively do well on homophilic, heterophilic, and random graphs.

That said, there are several weaknesses in the paper that lie mainly in the experimentation section:
1. In table 2, are the GCN, GAT, GraphSAGE results from 2 layer networks or 1 layer network? In my opinion, we should have results from both 1 layer and 2 layers for each of those networks.
2. In lines 213-217, the authors describe a procedure to sample the graph for applying a 2-layer GCN. But why is this sampling needed in the first place because the propagation rule complexity remains the same anyway? Also, if 2-hop neighbors are directly used, why is a 2-layer GCN applied and not a 1-layer?
3. No significance testing is performed on the results to show the statistical significance of the improvements made by U-GCN over other architectures.
4. There are GNN architectures like Graph Isomorphism Networks (GIN) that have high discriminative power; but U-GCN hasn’t been compared to those.
5. Wouldn’t a better way to measure homophily be to take the average of ratio of neighbors per node within k-hops of the node that have the same label? That way, the homophily metric can be calculated for or unto any number of hops.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This manuscript rethinks the propagation mechanism of networks with different structural properties, and presents a novel and universal GCN model, i.e., U-GCN, for general network data. In this work, they first conduct experiments to analyze the propagation mechanism of GCNs in networks with different structural properties, and discover that there are actually segmentation rules for the propagation mechanism. They then accordingly develop a new universal GCN framework, which first introduces a multi-type convolution to extract information from different type of neighbors simultaneously, and designs a discriminative aggregation to sufficiently fuse them aiming to given learning objectives. Extensive experiments on a series of benchmark datasets demonstrate the superiority of U-GCN over some state-of-the-arts. Overall, this paper is well written, easy to follow, and of high quality.
main_review: This paper first investigates whether different networks should adopt a unified or different propagation mechanisms using several intuitive cases, and accordingly proposes a universal GCN model, namely U-GCN, for general network data. 

Pros:
1. This paper is well motivated. Considering most GCNs based on the homophily assumption of networks may fail on the situations of heterophily or randomness, the authors perform motivating experiments to analyze whether different networks should adopt different propagation mechanisms.
2. The design of a universal propagation mechanism independent of the network structural assumption is a quite highlight part of this paper, which can be easily generalized to other GNNs. That is, the methods of considering the information from nodes of 1-hop network neighbors, 2-hop neighbors and kNN simultaneously, and meanwhile adaptively learning their corresponding importance for the given learning objectives can be considered as universal models.  

Suggestions & Questions:
1. The author needs to modify some grammatical errors. For example: 
On the 15th line: an universal -> a universal; 
One the 142th line: increases -> increase, etc. 
2. The authors are expected to provide some intuitive examples to demonstrate that the network dominated by a certain kind of structural properties (e.g., homophily) may contain a small amount of other structural properties (e.g., randomness), which can help the readers better understand their idea.  
3. In the discriminative aggregation part, I wonder if using other aggregation operation such as concatenation instead of summation will have similar performance, what is the difference between them? 
4. 2-hop neighbors or kNN may bring some technical challenges (e.g., high variance) when one attempts to scale the proposed method to large-scale graphs via selecting node pairs connected by at least two different paths for each node to set edges or constructing similarity matrix.  
To sum up, the authors have made an insightful understanding in networks with different structural properties from the perspective of propagation mechanisms, and the writing is also very clear.

limitations_and_societal_impact: Yes, the authors demonstrate that like many other GCNs, the proposed method U-GCN provides limited explanation to its prediction.
review_title: null

Meta-review: The work is motivated by the fact that GCNs are hinged on the homophily assumption, yet the real-world networks may contain heterogeneous structural properties, which requires different propagation mechanisms. As a result, the paper proposes an approach to combine 1-hop network neighbors, 2-hop neighbors and k-nearest neighbor, by using each mechanism independently and then fuse them via discriminative aggregation. The reviewers all commended the authors for studying the important topic, and at the same time had several concerns, which are mostly addressed in the rebuttal. In particular, Reviewer v9av and Reviewer TX8J are concerned with the computational complexity specifically with respect to kNN, and Reviewer TX8J also made an insightful point about whether "heterophily and randomness can't be captured by just having deeper discriminative GNNs". The authors's rebuttals addressed some of these points, although Reviewer v9av is still concerned with the computation complexity of the method on large datasets. The authors should address these further in the revision of the paper.
Decision: Accept (Poster)