Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper makes three contributions: (i) three axioms are specified to characterize the requirements of predictive uncertainty behaviour in homophilic attributed graphs; (ii) a new inference model is proposed and theorems are provided that demonstrate how the model behaves with respect to its characterization of uncertainty; and (iii) via numerical experiments, it is demonstrated that the proposed model achieves better uncertainty estimation performance.
main_review: The paper contains some very interesting ideas and the proposed model is well-constructed. The experiments are thorough, with comparison to multiple baselines across 8 datasets. These experiments demonstrate that the proposed model significantly outperforms existing methods in terms of its uncertainty quantification for the task of node classification. 

On the negative side, the paper is very difficult to read, and there needs to be considerably more care with definitions of terms and explanations of concepts. 

(1) The axioms are imprecisely stated and contain important elements that are not defined. 
The figures used to explain the axioms introduce concepts and variables that are not defined or explained until later in Section 3.2. For example, it is not clear what Dirichlet distribution is being referred to. 

In Axiom 3.1 it is written “A node with features more different from training features should be assigned higher uncertainty”. This sentence raises several questions. How is “different” defined or measured? What does it mean to “assign a node higher uncertainty”? When the axiom is imprecise in this way, it is very difficult to claim that a particular model obeys it. The authors claim that “The first theorem shows that GPN follows Ax. 3.1” but it actually shows something that is much more specific. It only characterizes the behaviour of the prediction as the distance (measured in any way) approaches infinity. It does not establish that for one node with “more different” features than another the uncertainty in the prediction will be higher (for some definition of “different” and some definition of “uncertainty”).  

Axiom 3.2 states that “a node’s prediction… should have higher aleatoric uncertainty”. At this stage of the paper, there is no quantitative definition of aleatoric or epistemic uncertainty. The approaches to quantitatively assess these are only made clear in Section 3.2. 

The text after Axiom 3.2 is confusing: “a node $v$ with confident feature predictions $x^{(v)}$. Above $x^{(v)}$ are specified as node features. Now they are node feature “predictions”?  

In a similar vein, “more conflicting” in Axiom 3.3. is not defined. 
 
Are the axioms supposed to relate to only a predictive model under a specific framework for uncertainty characterization? Or do we need to provide definitions and metrics for of all of these concepts – “uncertainty”, “aleatoric uncertainty”, “epistemic uncertainty”, “different”, “conflicting” – as well as the predictive model?

(2) It is extremely difficult to understand the proposed method and model from Section 3.2 alone. There is too much reliance on material from [14, 15]. While it is fine to refer a reader to other papers for further information and detail, the main method should be clear for a reader without it being essential to refer to other work. For example, phrases like “the epistemic uncertainty can be measured by the pseudo-count $\alpha_0$ of fictitious observations” are very hard to understand when “fictitious observations” have not been defined or introduced.  

Overall, I would like to recommend the paper for acceptance based on its technical content, but I think the axioms and the presentation need major improvement.

***
After author response: I acknowledge that the authors have provided a thorough commentary regarding my criticisms and they can all be addressed by modifying the text (although I view these changes as being important, since I think some of the claims about the theoretical results are not strictly correct as they stand and the axioms are vague). I have raised my overall score.



limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduced a well-grounded framework for uncertainty estimation on interdependent nodes. This paper first proposed explicit and motivated axioms describing desired properties for aleatoric and epistemic uncertainty in the absence or in the presence of network effects. Then it proposed GPN, a GNN for uncertainty estimation which provably follows our axioms. Furthermore, extensive experiments was conducted to evaluate the uncertainty performances of a broad range of baselines for OOD detection and robustness against node features or edge shifts. GPN outperforms all baselines in these experiments.
main_review: This paper is well written and pertinent to the NeurIPS. The related work is extensive and impressive, I like the Axioms style. But I have some concerns about the experiment part.

1. Since GPN was designed based on APPNP and PostNet, it is necessary to do an ablation study to analyze the contribution of each component. 

2. It might be necessary to add one important baseline, PostNet (ignore graph) or PostNet+GCN (simply combine PostNet and GCN), to show the advantage of GPN over PostNet in graph data.

3. For baseline GKD-GCN, it should be evaluated based on vacuity uncertainty, which is naturally designed to detect OOD. Note that GKD-GCN was proposed to improve the estimation of vacuity.

4. It is better to evaluate the proposed method in the misclassification detection task, which is an important task in uncertainty estimation [1] [2]. And this paper also discussed aleatoric uncertainty, which is not appropriate for OOD detection but is suitable for misclassification detection.

5. Why was GPN robust to feature perturbations, especially for accuracy? Which component supports this observation?

Some minor issues:

1. The indexes (1), (2), (3) are missing in Figure 2.
2. Typo in Table 1, “GDK-GCN” → “GKD-GCN”.
3. Typo in Line-358, “Tab. 3” → “Figure 3”

[1] Hendrycks, Dan, and Kevin Gimpel. "A baseline for detecting misclassified and out-of-distribution examples in neural networks." ICLR 2017.

[2] Malinin, Andrey, and Mark Gales. "Predictive uncertainty estimation via prior networks." NeurIPS 2018.
limitations_and_societal_impact: Yes,  the authors adequately addressed the limitations and potential negative societal impact of this work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors proposed a graph posterior network based on the uncertainty theory to enhance the node classification in graph learning. The uncertainty estimation based on the interdependent node inputs instead of assuming i.i.d inputs is interesting. Through theoretical analysis and experiments on 8 data sets, they claim that the proposed framework has advantages in node classification and OOD detection.
main_review: In general, the node classification based on uncertainty is not a new problem. However, the proposed method study the influence of the interdependent inputs on GNN is new. Furthermore, the proposed Graph Posterior Network is a combination of two existing methods. One is APPNP [47], the other is PostNet [14]. It is good to see that the authors discussed the key difference between this paper and the above two papers. The authors provide relatively comprehensive related works from two perspectives (Uncertainty for i.i.d. inputs and Uncertainty for graphs).  

This submission is technically sound. Most claims are well supported by theoretical analysis and experiments. The proposed method theoretically proves the appropriateness of the fusion of the two known methods. Furthermore, the authors also discussed the limitations of their approach, which is good for understanding the applicability of their method in real-world tasks. This work is complete.

The paper is well-written in several sections. However, the Axioms and Theorems in Section 3 seem too dense. I suggest the authors can draw a figure to show the relationships between each Axiom and each theorem. The authors had provided many experiment details in the Appendix to reproduce the results in the main paper.

The results shown in this paper seem important. The researchers or practitioners may like to use the ideas from this paper in their research works. According to the experiment results, this paper advances the state of the art in a demonstrable way. The proposed method is tested on several existing data. There are no unique data, unique theoretical, and unique experimental approaches.

My major comments are as follows,

1. In table 1, why baseline methods do not have values in [Epist w/o Net]? What is the meaning of '_'?

2. It is hard to see the efficiency of the proposed methods compared to the baseline methods. 

My minor comments are as follows,

1. In line 359, Tab.3 should be Figure 3.

2. In line 375, Tab.10 should be Table 2.
limitations_and_societal_impact: The authors discussed the limitations of the proposed method.
review_title: null

Meta-review: This paper first proposes axioms describing desired properties of uncertainty in the absence or in the presence of network effects. It then  introduces a novel framework for uncertainty estimation in the graph setting (graph posterior networks). The problem of uncertainty estimation in the graph setting is interesting and relevant and has received much less attention than more standard supervised learning settings. The approach is technically correct. AN extensive set of the experiments includes the assessment of uncertainty estimation quality for OOD detection as well as the assessment of robustness against shifts in attributed graph properties. The proposed approach shows promising performance in these experiments. Following the author response and discussion, the reviewers were in agreement that the paper should be accepted. One concern raised in several of the reviews was that the paper could benefit from reducing the density of the exposition and the reliance on reader familiarity with results from prior works. The authors have committed to addressing these issues in the revised manuscript. 
Decision: Accept (Poster)