Edge Importance Inference Towards Neighborhood Aware GNNs

We thank Reviewer MmuU for the constructive feedback.

"No Introduction to the Comparison Method": Most of the baseline methods including the state-of-the-art are discussed in Section 1 Introduction and Section 2 Related Works. We will add the discussion about the missing ones: GCNII and JKNet in the camera-ready version.

"Experiment with a recent method": We have experimented with a most recent method named PSNR-GNN [1]. The resulted reported in table below demonstrate that our method achieves better predictive accuracy across the benchmark datasets.

We will add the additional results and discussions in the camera-ready version.

"Experiments other than node classification": Although the main focus of our work is on node classification, intuitively we can extend it to solve other graph-related problems, such as graph classification. Since our method adaptively sample edge during learning which may reduce the number of link examples, its extension to link prediction might be a little problematic. This is a part of our future work.

Heterophilic graph experiments: As the reviewer suggested, we conduct additional experiments on heterophilic graphs. We hypothesize that one main reason why our method doesn’t perform ideally on these datasets is because of the random edge sampling during training. The dropped edges may lead to information loss about the connections between nodes with different labels. This information loss can cause significant impact due to the small sizes of the heterophilic datasets. We have the results in the table below for reference.

More visualization Results on Neighborhood modeling: We have added an analysis on neighborhood scope inference in this link and also in Appendix B.3 in the updated version. We use two synthetic datasets, BA-Shapes and Tree-Cycles, used in GNN explanation studies[2]. Analyzing their ground-truth explanations in the form of motifs, we conclude that inferred neighborhood scope highlights the optimal range for extracting meaningful information during training, with second-order neighborhoods being sufficient for BA-Shapes and third-order neighborhoods required for the ring-like motifs in Tree-Cycles.

[1] Jingbo Zhou, Yixuan Du, Ruqiong Zhang, Jun Xia, Zhizhi Yu, Zelin Zang, Di Jin, Carl Yang, Rui Zhang, & Stan Z. Li (2024). Deep Graph Neural Networks via Posteriori-Sampling-based Node-Adaptative Residual Module. In The Thirty-eighth Annual Conference on Neural Information Processing Systems.

[2]​​ Ying, Z., Bourgeois, D., You, J., Zitnik, M., & Leskovec, J. (2019). Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32.

We thank the reviewer for the constructive feedback and would like to respectfully remind the reviewer that the deadline for the discussion period is approaching. if the reviewer has any other questions, we would be glad to address them. Thank you again for your time and thoughtful review!

"Experiments other than node classification": As Reviewer MmuU suggested, we extend our method for a graph classification task by incorporating a global pooling layer after the GNN layers to aggregate node features into a single graph representation for classification. We evaluate our method on Proteins [1] dataset, and the results [2] are shown in the table below.

Our proposed work primarily focuses on node classification. While our method's performance on graph classification is not particularly outstanding, the experiments demonstrate that our approach can be extended to address other graph-related problems.

[1] Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., & Neumann, M. (2020). Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663. [2] Michel, G., Nikolentzos, G., Lutzeyer, J. F., & Vazirgiannis, M. (2023, July). Path neural networks: Expressive and accurate graph neural networks. In International Conference on Machine Learning (pp. 24737-24755). PMLR.

We have made every effort to address all the concerns and questions raised. As the discussion period is nearing its end, we kindly request a consideration from Reviewer MmuU for an updated score. If there are any further questions or matters to discuss, please don’t hesitate to let us know.

We thank Reviewer qxoW for the constructive feedback.

"Citation Formatting and Inconsistent Figure Text Size Issues": We fix the problems, pointed out by the reviewer, in the revised version. We will include the changes in the camera-ready version.

"Consistency across Baselines": We conduct additional experiments to include the larger datasets, such as ogbn-proteins and ogbn-products in tables 3, 4, 5 and 6, for comprehensive comparison. These additions strengthen the validation of our approach and demonstrate its effectiveness across a broader range of dataset scales. And, for reference, we have included a portion of these experiments on these larger datasets in the table below.

We have further added ablation study with larger datasets, which is shown below.

Also, we have added time complexity for larger dataset (ogb-Mag) in table 5, which is shown below (italic typeface used to represent added results).

"Capturing Edge Importance using $\mathbf{Z}$ and $\boldsymbol{\nu}$": $\mathbf{Z}$ and $\boldsymbol{\nu}$ adaptively sample important edges within the neighborhood. Meanwhile, we jointly learn the kernel functions to evaluate the importance level of these edges, as described in section 3.6. We will clarify these in the camera-ready version.

We are quite grateful to Reviewer qxoW for raising the score. Since you mentioned that we have addressed all your concerns and questions, we wonder if it would be possible for you to kindly increase the score further.

If there are any further questions or matters to discuss, please don’t hesitate to let us know.

We thank Reviewer g91e for the thorough and constructive review.

Although both papers utilize Beta and Bernoulli processes for the inference in GNN models, there are significant differences between the two works.

Methodological Difference: Our method proposes to apply the stochastic processes directly to the graph for identifying important edges, whereas Paper 3881 applies the stochastic processes to regularize the GNN structures. This is elaborated in the equations as follows:

• Our method: $\mathbf{H}\_{l} = \sigma \left((\widehat{\mathbf{A}}\odot \mathbf{Z}\_{l})\mathbf{H}\_{l - 1}\mathbf{W}\_{l} \right) + \mathbf{H}\_{l - 1}$

• Paper 3881: $\mathbf{H}\_{l} = \sigma(\hat{\mathbf{A}} \mathbf{H}\_{l-1} \mathbf{W}\_{l}) \odot \mathbf{z}\_{l} + \mathbf{H}\_{l-1}$

Note that our method applies the Bernoulli mask samples $\mathbf{Z}_{l}$ on the adjacency matrix. In contrast, Paper 3881 uses the mask on GNN feature activations. This leads to distinct working mechanisms for the two method. Specifically, Paper 3881 prunes neurons in each GNN layer, whereas our method samples graph edges.

Besides edge sampling, we propose to capture the importance of edges using kernel function that updates the drop-edge probability based on the similarity between the node features. However, Paper 3881 assigns equal activation probabilities to all the neurons in the same layer.

Difference in the Experimental Design: Regarding the experiments, we focus on examining the effectiveness of kernels for important edge identification and how the subgraphs provide robustness to over-smoothing and over-fitting, whereas Paper 3881 focuses on verifying the theoretical claims it posits.

Similar figures and phrases: Although the demonstration figures look similar, they are based on fundamental different methodological ideas. For example, Figure 3 is visualized using the same plotting tool, but it demonstrates different results on different datasets. We will edit the similar phrases in the camera-ready version, as suggested by the reviewer.

"Weak Literature Review": We mainly discussed the common limitations of the related works in Section 1 Introduction. With respect to our proposed method, these methods are not capable of inferring the number of neighboring hops automatically and require expensive hyper-parameter tuning. The non-Bayesian GNN methods cannot quantify uncertainty in their predictions. Most of the methods in Section 2.3 randomly drop graph edges, which leads to unstable performance. We will clarify the above points and discuss them in both related works and experiments section.

"No Comparison with Bayesian Methods": We actually compared our method against the most relevant Bayesian GNN method, BBGDC in Figures 4 and 5 and Table 6. We discussed the method in related work section and called the method "DropConnect (Hasanzadeh, et. al, 2020). In our experiment section, we referred the method with different names, such as "Graph DropConnect" in Figure 4 and "BBGCN" and "BBGDC" in Figure 5. To highlight the advantages of Bayesian methods, such as better calibration and reliable uncertainty quantification, we further benchmarked our method against BBGDC in Table 6, focusing specifically on uncertainty quantification. We will clarify this and use a consistent name in the camera-ready version.

"The Choice of Beta Process Prior": Beta process is a complete random measure over integers, allowing the activation probability of the edges in each neighboring hop to go from 0 to 1. This flexible property makes it a better choice compared to other stochastic processes such as Dirichlet process who constraints that all activation probabilities sum to 1.

The monotonically decreasing $\pi_l$ across neighboring hops is due to the stick-breaking construction of the beta process. It reduces the activation probabilities of the edges in longer-range neighborhood scope. However, we can mitigate the effects by setting mild hyper-parameters for the beta process, encouraging smooth decrease. As long as the graph data provide strong support for the edge activations through the GNN likelihood, the settings of beta process wouldn't affect the prediction in any significant way.

Mechanism of $\pi_l$: $\pi_l$ is a variable about the activation probability of the edges that are exactly $l$-hops away, not up to $l$-hops. It is not defined on node features. This is why the dimensionality of $Z_l$ is consistent, corresponding to the number of edges in the graph.

"Advantage of using a conjugate Bernoulli-process": We use variational inference to approximate the marginal likelihood is because of the nonlinearity of the GNN weights and the number of hops going to infinity. We think it's reasonable to extend our Bayesian inference to DropMessage-style message-passing by sampling Bernoulli variables to mask the message matrix.

"The change in Figure 4 w/o residual connection": The results of our ablation study in Table 4 shows the performance of our method without residual connections.

"The model setting of ours in Table 2": Our method is equipped with the RBF kernel and the architecture is described in Eqn. 1.

We will clarify the above points in the camera-ready version. We will also add the dimension for the matrices and vectors, bold the degree matrix notatio, and reflect the changes made for the mentioned issues in the camera-ready version.

"Empirical Evidence for Neighborhood Scope Determination": We have added an analysis on neighborhood scope inference in this figure and also in Appendix B.3 in the updated version. We use two synthetic datasets: BA-Shapes and Tree-Cycles in GNN explanation studies [1], and analyze their ground-truth explanations in the form of motifs. The linked figure shows that inferred neighborhood scope highlights the optimal range for extracting meaningful information during training, with second-order neighborhoods being sufficient for BA-Shapes and third-order neighborhoods required for the ring-like motifs in Tree-Cycles.

[1]​​ Ying, Z., Bourgeois, D., You, J., Zitnik, M., & Leskovec, J. (2019). Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32.

Note that our method applies the Bernoulli mask samples on the adjacency matrix. In contrast, Paper 3881 uses the mask on GNN feature activations.

This does not make the two works significantly different, but only marginally. The model is exactly the same except for this work employing a DropEdge-like mechanism, while the other employing a Dropout-like mechanism. The motivation for the work is exactly the same, the proposed solutions are very similar, and the choice of the prior distribution is exactly the same.

For example, Figure 3 is visualized using the same plotting tool, but it demonstrates different results on different datasets. We will edit the similar phrases in the camera-ready version, as suggested by the reviewer.

I didn't raise any concerns about Figure 3. I am more interested in the similarities between Figures 1 of the two works, as well as between Figure 2 of this work and Figure 3 of the other work. They are exactly the same, except for slightly different color choices.

Most of the methods in Section 2.3 randomly drop graph edges, which leads to unstable performance.

I only see DropEdge and DropEdge++ in the current version of the manuscript. Dropout is also discussed but it has nothing to do with dropping along edges. Rather, more relevant works include DropNode, DropAgg, DropGNN, etc. which are missing from the related works section; although, I do agree that their limitations are similar to DropEdge in that they dropping is performed identically. The most relevant work I am aware of is Graph DropConnect, which has a Bayesian interpretation involving learning of dropping probability along each edge $\times$ feature pair. This addresses the problem this work highlights, is more general and flexible than the dropping algorithms mentioned above, and performs competitively in practice.

The monotonically decreasing $\pi_l$ across neighboring hops is due to the stick-breaking construction of the beta process.

I understand. I meant that this intuition/motivation should be highlighted in the manuscript so that a reader unfamiliar with the beta process model can infer its relevance to learning via message-passing.

$\pi_l$ is a variable about the activation probability of the edges that are exactly $l$-hops away, not up to $l$-hops.

I fail to see that since in Section 3.1, there is an addition of self-loops before edge-weights are computed. Wouldn't that imply that masking the edges in the $l$-th step masks information from nodes reachable in $l$-hops, which includes all nodes up to $l$-hops away?

It is not defined on node features. This is why the dimensionality of $\mathbf{Z}_l$ is consistent, corresponding to the number of edges in the graph.

I apologize, but I don't see what concern is being addressed here.

We think it's reasonable to extend our Bayesian inference to DropMessage-style message-passing by sampling Bernoulli variables to mask the message matrix.

My concern is that the manuscript says, "The beta process induces hopwise activation probabilities and its conjugate Bernoulli process enables us to adaptively sample the edges in the neighborhood." This suggests that there is an inherent advantage in using the conjugate prior, when there doesn't seem to be one. Also, if not implemented in this work, I would appreciate a remark about the possible extension of this method to DropMessage-like dropping.

The results of our ablation study in Table 4 shows the performance of our method without residual connections.

Fair enough, that is my bad. My apologies.

We use two synthetic datasets: BA-Shapes and Tree-Cycles in GNN explanation studies

My apologies, but I am not completely sure why the inferred scope for BA-trees and for Tree-cycles should be 2 and 3, respectively. I understand that the model predicts the scopes to be 2 and 3, but since I am not sure what should be the correct scope, I can't conclude whether the model is correct or not.

Note: Updated my rating, but I think the writing is still not sound. Importantly, the ethical concern remains.

We thank Reviewer g91e for raising the score and providing additional valuable comments.

"This does not make the two works significantly different, but only marginally. The model is exactly the same except for this work employing a DropEdge-like mechanism, while the other employing a Dropout-like mechanism."

We thank the reviewer pointed out the different mechanisms of the two proposed approaches to address the similar problem. Meanwhile, to the best of our knowledge, we are the first propose the notion of adaptively sampling edges and integrate kernel methods into the Bayesian GNNs to evaluate edge importance.

"I am more interested in the similarities between Figures 1 of the two works, as well as between Figure 2 of this work and Figure 3 of the other work. They are exactly the same, except for slightly different color choices."

The two papers make use of a similar visualization tool for the beta processes figure 1 and figure 2 in our paper with that of figure 1 and figure 3 of 3881. However, considering figure 1(a), we show that our model learns edge importance by using different intensity of color within the neighborhood, which is not present in 3881’s figure. Figure 2 in our paper is generated on different dataset from different methods.

" The most relevant work I am aware of is Graph DropConnect, which has a Bayesian interpretation involving learning of dropping probability along each edge feature pair. This addresses the problem this work highlights, is more general and flexible than the dropping algorithms mentioned above, and performs competitively in practice."

We actually compared our method against Graph DropConnet in Figures 4 and 5, and Table 6. We discussed the method in related work section and called the method "DropConnect (Hasanzadeh, et. al, 2020). In our experiment section, we referred the method with different names, such as "Graph DropConnect" in Figure 4 and "BBGCN" and "BBGDC" in Figure 5. To highlight the advantages of the Bayesian GNNs, such as better calibration and reliable uncertainty quantification, we further benchmarked our method against Graph DropConnect in Table 6, focusing specifically on uncertainty quantification. We will clarify this and use a consistent name for DropConnet in the camera-ready version.

"there is an addition of self-loops before edge-weights are computed. Wouldn't that imply that masking the edges in the -th step masks information from nodes reachable in $l$-hops, which includes all nodes up to $l$-hops away?"

The reviewer is correct that the addition of self-loops before computing edge weights implies that masking the edges in the $l$-th step affects information from nodes reachable in up to $l$-hops, not exactly $l$-hops. This means that $\pi\_l$​ should be interpreted as the activation probability of edges up to $l$-hops away.

Also, if not implemented in this work, I would appreciate a remark about the possible extension of this method to DropMessage-like dropping.

DropMessage is a quite interesting method. A possible way to extend our method to it is through a hierarchical beta process prior. Specifically, we define a hyper-prior beta process at the global level to adaptively sample a sub-graph when spanning a neighborhood (i.e., corresponding to the size of the Message Matrix) and a local beta-Bernoulli process prior locally on each sampled edge within the neighborhood to regularize the edge-specific message's feature dimension. We will cite and discuss the DropMessage paper and clarify the possible extension as a part of our future work in the camera-ready version.

"I am not completely sure why the inferred scope for BA-trees and for Tree-cycles should be 2 and 3, respectively. I understand that the model predicts the scopes to be 2 and 3, but since I am not sure what should be the correct scope, I can't conclude whether the model is correct or not."

As shown in this link, the motif of BA-shapes is a sub-graph, where each node requires 2-hop neighborhood to aggregate features from every other node. And, for tree-cycles, the motif is a ring structure, where every node requires at least 3-hop neighborhood scope to accumulate features from the remaining nodes. These motifs can be gold-standard as the optimal neighborhood scopes for these synthetic graphs. We will clarify this in our camera-ready version.

We will add the clarifications as suggested by the reviewer in the camera-ready version.

We actually compared our method against Graph DropConnet in Figures 4 and 5, and Table 6.

Oh sorry, that's my bad for not noticing! That concern is resolved.

As shown in this link, the motif of BA-shapes is a sub-graph, where each node requires 2-hop neighborhood to aggregate features from every other node. And, for tree-cycles, the motif is a ring structure, where every node requires at least 3-hop neighborhood scope to accumulate features from the remaining nodes.

Mm okay, I am not confident, but I guess that's not a concern anymore.

I still think that the ethical concerns remain. The rest of my concerns are resolved, and I'll update my rating to a 6.

We appreciate the reviewer’s constructive comments on our work which are valuable for our future research.

"More experiments on Larger-scale Datasets": To address the reviewer's concern, we conduct additional experiments on OGB datasets, including ogb-proteins and ogb-products. Although they are listed as medium-scale ones, they have a larger number of edges and nodes in comparison with OGB-mag we presented in the submission. We reported a portion of these experiments on these larger datasets in the tables below.

Table 3: Test accuracy (%) comparisons with larger datasets on semi-supervised node classification task

The experiments highlight our method’s scalability when it comes to larger-scale datasets. We have also included the results of these experiments in the updated version of the manuscript.

Extensive Experiments on Larger-Scale Datasets: We have revised our manuscript to reflect the scale of datasets as pointed out by the reviewer. We have further extended our experiments to incorporate the comparison on the medium scale datasets. The added results are summarized in the tables below. Additionally, the updated results in tables 3, 4, 5 and 6 reflect the extensions made in the paper's updated version.

Table 4: Ablation study of different modules' effectiveness in our model

Table 5: Semi-supervised node classification training time comparison

Table 6: Evaluating the uncertainty estimation of models with ECE metric

Dirichlet Energy Experiment: We report the experimental results using Dirichlet Energy as a metric for over-smoothing analysis in this link and also added the result in Figure 7 in the updated version. We achieve larger Dirichlet energy between the node features across the truncation level compared to the baseline methods. This result is consistent with what we reported using total variation.

Comparison with PathNN-based GNN: We will add the discussion about PathNN-based GNNs [1] in the related work in the camera-ready version. PathNN-based GNN focuses on graph classification, whereas our experiments primarily target node classification. Extending our work for graph classification will be a part of our future research.

Effectiveness of Edge Importance on Larger Datasets: We evaluate the effectiveness of our method on larger datasets: ogb-Arxiv and ogb-Mag through an ablation study presented in table 4, which are in the table below. The results demonstrate that without edge importance the method performs significantly worse compared to with edge importance. This highlights the effectiveness of inferring edge importance on larger datasets.

We have fixed grammatical issues in line 142 in the revised version. We will include the changes in the camera-ready version.

[1] Michel, G., Nikolentzos, G., Lutzeyer, J., & Vazirgiannis, M. (2023). Path neural networks: expressive and accurate graph neural networks. In Proceedings of the 40th International Conference on Machine Learning.

We thank the reviewer for the constructive feedback and would like to respectfully remind the reviewer that the deadline for the discussion period is approaching. if the reviewer has any other questions, we would be glad to address them. Thank you again for your time and thoughtful review!

As the discussion period is nearing its conclusion, we sincerely thank the reviewer for the valuable feedback. We have made every effort to address all concerns and questions raised. If the reviewer feels our revisions meet the expectations, we kindly request consideration for an updated rating. If there are any further questions or matters to discuss, please don’t hesitate to let us know.