Noise Robust Graph Learning under Feature-Dependent Graph-Noise

We sincerely appreciate your valuable feedback on our work and for recognizing the contributions made by our research! We have diligently addressed the typos in the manuscript to enhance its quality. The revised content is distinctly highlighted in orange.

(W1) Additional real-world evidences of FDGN

Upon the reviewer’s request for additional application examples of FDGN, we provide additional examples of real-world applications:

Biological networks

A cell-cell graph is widely used in computational biology [1,2,3]. In the cell-cell graph, a node denotes a cell, each node is associated with features that represent gene expression values, and each node is labeled with the cell type. As the graph structural information is missing by nature, a cell-cell graph is usually constructed based on the node feature similarity [1,2,3]. However, gene expression values (i.e., cell-gene count matrix) often contain noise due to dropout phenomenon and batch effect, and such noise may entail noisy cell-cell graph structures, which can be referred to as FDGN. Furthermore, since the cell type (i.e., node label) is annotated by using transcripted marker genes (i.e., important features), noisy node features may lead to noisy node labels, which can be referred to as FDGN.

[1] scGNN is a novel graph neural network framework for single-cell RNA-Seq analyses. Nature communications 2021

[2] scGCL: an imputation method for scRNA-seq data based on graph contrastive learning. Bioinformatics 2023

[3] Single-cell RNA-seq data imputation using Feature Propagation. ICML 2023 Workshop on Computational Biology

Recommender systems in many domains

In recommender systems of various domains (e.g., e-commerce, news, movie, etc), user-item interaction graphs are common, where node feature represents the information of users/items, and the user-item interaction represents the graph structures. Besides, users’ communities (interests) and items’ categories denote node labels. In this situation, if a user creates a fake or incomplete profile due to various reasons (e.g., privacy), node features would become noisy. Due to such noisy node features, items that are irrelevant to the user’s genuine interest can be exposed to users, which would make them interact with irrelevant items, resulting in noisy user-item interaction graph structures. This is an example of FDGN. Furthermore, such noisy information of users and noisy user-item interactions may also eventually change the users’ communities (i.e., noisy node labels), which can be referred to as FDGN.

We appreciate the feedback and have included these examples in Appendix H. We believe it effectively addresses the concern.

(W2) Why not directly learn a clean latent $Z_X$

In the data generation process (DGP) we introduce, latent variable $Z_Y$ is a cause of $X$, as node features are generated based on the node label, similar to the approach in [1]. However, there might be some cases in which $Z_Y$ can not determine $X$. In such cases, we are open to exploring the reviewer's suggestion of positing a causal relationship $X ← Z_X$, where $Z_X$ represents the latent clean node features, rather than $X ← Z_Y$. However, the direct inference of $Z_X$ presents some challenges, as it would require parameterizing the clean node feature matrix $X \in R^{N \times F}$, which could be computationally intensive when dealing with large $N$ and $F$. Nevertheless, we appreciate the reviewer's suggestion and leave it as a future work. Exploring this idea further could potentially enhance the applicability of our proposed method.

[1] Instance-Dependent Label-Noise Learning under Structural Causal Models, NeurIPS 2021

(W3) Technical contribution is neutral

We acknowledge the reviewer's perspective on the technical contribution of our work in model derivation. However, we would like to emphasize that our primary contribution lies in proposing the DGP of FDGN, which is a more realistic scenario in graph learning. Additionally, we effectively adapt existing techniques, such as variational inference, to address our problem of interest. It is important to note that even after deriving the objective using variational inference, how to implement each term in the derived objective was also non-trivial and challenging, which is another technical contribution. We specified the challenges in instantiating each term in here compared to [1] that also takes a similar approach to our work. Moreover, to the best of our knowledge, our proposed method successfully tackles a novel and crucial problem for the first time: handling noise scenarios where node features, graph structures, and node labels all simultaneously contain noise.

We appreciate the reviewer for bringing up this important concern. We believe that it effectively addresses the concerns raised by the reviewer.

[1] Instance-Dependent Label-Noise Learning under Structural Causal Models, NeurIPS 2021

(W2) A lot of GNN with label noise works are missed

We agree with the reviewer’s comment about the missing baselines. Hence, we further compare PRINGLE with the widely used label noise baselines: Co-teaching+ [1], CP [2], D-GNN [3], and CGNN [4].

[1] How does disagreement help generalization against label corruption? ICML 2019

[2] Adversarial Label-Flipping Attack and Defense for Graph Neural Networks. ICDM 2020.

[3] Learning graph neural networks with noisy labels. ICLR LLD Workshop 2019

[4] Learning on Graphs under Label Noise. ICASSP 2023

From the below table, we clearly see that the proposed method, PRINGLE, outperforms all the baselines in terms of the node classification accuracy. We argue that these baseline methods are designed to tackle the noisy node labels while assuming that both node features and graph structures are noise-free. However, the proposed FDGN introduces a more realistic noise scenario, wherein node features, graph structures, and node labels simultaneously contain noise. As a consequence, the performance of these existing methods is considerably more constrained compared to PRINGLE.

We acknowledge and appreciate the feedback provided, and as a response, we have incorporated the corresponding results in Appendix I. We are confident that this inclusion effectively addresses the raised concerns.

(W3) The abstract cannot summarize the methodology.

We apologize for the oversight in the abstract. We have revised the abstract to include a more comprehensive summary of the proposed method and have uploaded the revised manuscript. The revised content is distinctly highlighted in orange.

(W4) Why the last three losses share the same weights in Eq. 4?

In our experiments, we observed that the last three loss terms, namely $L_{rec-feat}$, $L_{cls-dec}$, and $L_{p}$, have a relatively minor impact on the model's performance compared to the others. As a result, we have made a strategic decision to simplify the hyperparameter search process and improve the practicality of PRINGLE by sharing the weights $\lambda_3$ among these last three loss terms.

We appreciate the reviewer's feedback and have addressed this concern by including a detailed explanation in the implementation details section in Appendix D.5. The revised content is distinctly highlighted in orange.

(W5) Why the generative methods can release the label noise?

We acknowledge that deep generative models typically do not address label noise as a primary focus. However, in the context of our proposed FDGN, the DGP accounts for label noise that is generated in a feature-dependent manner. Hence, directly modeling the DGP of FDGN is beneficial for the model to recognize the way that the label noise is generated. Consequently, our modeling approach effectively mitigates the impact of the label noise.

(W1-1) FDGN is a combination of structure noise and label noise.

We would like to emphasize that our proposed FDGN is not a naive combination of independent node label noise and graph structure noise (which is referred to [1] by the reviewer). In this work, we introduce a more realistic noise scenario, where noisy node features may entail both structure and label noise, which we call feature-dependent graph-noise (FDGN). In other words, we assume that there exist "causal relationships" among node feature noise, graph structure noise, and node label noise, rather than assuming that these noise occur independently, lacking any causal connections between them. We argue that the proposed FDGN is more comprehensive and applicable in various real-world scenarios compared to the naive combination, because such causal relationships are evident in a range of real-world applications (as will be described below).

(W1-2) More application examples in the real-world of FDGN

Upon the reviewer’s request for additional application examples of FDGN, we provide additional examples of real-world applications:

Biological networks

A cell-cell graph is widely used in computational biology [1,2,3]. In the cell-cell graph, a node denotes a cell, each node is associated with features that represent gene expression values, and each node is labeled with the cell type. As the graph structural information is missing by nature, a cell-cell graph is usually constructed based on the node feature similarity [1,2,3]. However, gene expression values (i.e., cell-gene count matrix) often contain noise due to dropout phenomenon and batch effect, and such noise may entail noisy cell-cell graph structures, which can be referred to as FDGN. Furthermore, since the cell type (i.e., node label) is annotated by using transcripted marker genes (i.e., important features), noisy node features may lead to noisy node labels, which can be referred to as FDGN.

[1] scGNN is a novel graph neural network framework for single-cell RNA-Seq analyses. Nature communications 2021

[2] scGCL: an imputation method for scRNA-seq data based on graph contrastive learning. Bioinformatics 2023

[3] Single-cell RNA-seq data imputation using Feature Propagation. ICML 2023 Workshop on Computational Biology

Recommender systems in many domains

In recommender systems of various domains (e.g., e-commerce, news, movie, etc), user-item interaction graphs are common, where node feature represents the information of users/items, and the user-item interaction represents the graph structures. Besides, users’ communities (interests) and items’ categories denote node labels. In this situation, if a user creates a fake or incomplete profile due to various reasons (e.g., privacy), node features would become noisy. Due to such noisy node features, items that are irrelevant to the user’s genuine interest can be exposed to users, which would make them interact with irrelevant items, resulting in noisy user-item interaction graph structures. This is an example of FDGN. Furthermore, such noisy information of users and noisy user-item interactions may also eventually change the users’ communities (i.e., noisy node labels), which can be referred to as FDGN.

We appreciate the feedback and have included these examples in Appendix H. We believe it effectively addresses the concern.

We kindly request the reviewer to refer to our response addressing the concerns related to the plausibility of FDGN, missing baselines, and so on. If the reviewer have any additional concerns, please don’t hesitate to bring them to our attention. We are eager to address any further concerns or questions the reviewer may have.

Thanks for your efforts in the rebuttal. I have read all the reviews and responses. The authors added some missing baselines and revised the abstract, which improved the quality of the paper. However, the limited novelty of the proposed setting and techniques in this paper is still the main concern, which I haven't been persuaded. It makes the paper not achieve the requirements for ICLR. I would nonetheless take these comments into consideration in the reviewers' discussion and in the final score.

We thank the reviewer for carefully reviewing our rebuttal and other reviews. Finally, we would like to briefly underscore our contributions and respectfully request the reviewer to take them into consideration during the upcoming reviewers' discussion phase:

1. Our primary contribution lies in proposing the DGP of FDGN, which is well justified through a range of real-world application examples. Furthermore, the proposed FDGN is a new and novel concept in graph learning, which is a pivotal technical contribution.
2. We properly derive the ELBO objective and carefully instantiate each term in the objective while addressing various intricate challenges.
3. For rigorous evaluation, we newly introduce two real-world graph noise benchmark datasets, Auto and Garden, which is expected to foster practical research in noise-robust graph learning.

We sincerely thank the reviewer for thoughtful and constructive feedback on our paper. However, we kindly request the reviewer to provide clarification regarding the specific citation details for [1] mentioned in Weakness 1, which appears to be missing. This information would be invaluable for us to address the concern effectively.

Dear authors, I apologize for this oversight, and thank your prompt identification of the issue. The article I'm referring to is CausalNL proposal by Yao et al., which is in my view very similar in terms of scope and approach to this work. Notably, both studies explore the application of a causal perspective to address the challenge of learning in the presence of noise. Furthermore, both works leverage variational auto-encoders to introduce an additional reconstruction loss to model latent variables.

Yao, Yu, et al. "Instance-dependent label-noise learning under a structural causal model." Advances in Neural Information Processing Systems 34 (2021): 4409-4420.

(W2) The derivation on ELBO are well-known results, and the authors are only re-stating them here.

We acknowledge that the derivation of the Evidence Lower Bound (ELBO) is based on well-known results. However, we would like to emphasize that our primary contribution lies in proposing the DGP of FDGN, which is a more realistic scenario in graph learning, not in the derivation of ELBO. In other words, considering that the ELBO of our objective has been derived by following the well-known derivation procedure, our main focus was on how to implement each term in the derived ELBO, which is non-trivial. Please refer to our response to W1 for more detail on how each term is implemented. We fully agree with the reviewer’s opinion that the re-stating of the ELBO derivation may seem redundant as they are well-known, and we are willing to remove them from the paper.

(W3) An efficiency analysis is needed.

We thank the reviewer for pointing out the potential high computational complexity of our proposed method.

Hence, we compare the training time of PRINGLE with the baselines to analyze the computational complexity of PRINGLE. In the below table, we report the total training time and training time per epoch on Cora with FDGN 50% for all models. Note that since STABLE is a 2-stage method, we did not report the training time per epoch. The results show that PRINGLE requires significantly less total training time and training time per epoch compared with WSGNN, ProGNN, RSGNN, STABLE, NRGNN, and RTGNN. This suggests that PRINGLE can be efficiently trained, while still achieving substantial performance improvements.

Although AirGNN and EvenNet require much less training time than PRINGLE, their node classification accuracy is notably worse than other methods, including PRINGLE. This indicates that, despite their fast training time, they may not be suitable for real-world scenarios. In summary, PRINGLE demonstrates superior performance compared to the baselines while maintaining acceptable training time.

We appreciate the feedback and have incorporated these experimental results into Appendix J. We believe it effectively addresses the concerns related to computational complexity.

Loss term $E_{Z_Y \sim q_{\phi_3}}[kl(q_{\phi_2}(\epsilon | X,A,Z_Y) || p(\epsilon))]$

This term is decomposed into $kl(q_{\phi_{21}}(\epsilon_X | X, Z_Y) || p(\epsilon_X))$ and $kl(q_{\phi_{22}}(\epsilon_A | X,A)||p(\epsilon_A))$. The first term is calculated in a similar manner to [1]. Specifically, a Gaussian distribution is employed as the prior $p(\epsilon_X)$. However, the second term is unique to our problem, and its computation necessitates prior information about $\epsilon_A$. As $\epsilon_A$ indicates the likelihood of each observed edge being noisy or not, it is not appropriate to simply assume $p(\epsilon_A)$ as a Gaussian distribution as done in [1]. This aspect makes the problem more challenging. To address this challenge, we introduce a new assumption that the inferred $\epsilon_A$ follows an unknown distribution with high variance, while our prior knowledge suggests that $p(\epsilon_A)$ follows the same distribution but with low variance. Additionally, we employ an Exponential Moving Average (EMA) technique to reduce the uncertainty of the inferred $\epsilon_A$. This challenge represent non-trivial aspects of our approach and is absent in [1].

We appreciate the reviewer for bringing up this important concern. We have taken the feedback into consideration and have included an explanation in the Appendix G to further clarify this aspect of our work. We believe that it effectively addresses the concerns raised by the reviewer.

[1] Instance-dependent Label-noise Learning under a Structural Causal Model, NeurIPS 2021

(W1) This paper only incrementally adapts CausalNL [1] on the graph.

We agree with the reviewer's opinion that our work may appear to lack technical novelty in comparison to [1]. However, it is important to note that we tackle additional, more challenging aspects unique to our specific problem that do not exist in [1]. Specifically, when additionally introducing $A$, we handle four more causal relationships: $\epsilon → A, X → A, A → Y, Z_A → A$, each of which is non-trivial to consider. We would like to specify the challenges in instantiations caused by their additional introduction.

Inference of $\epsilon$

In contrast to [1], which assumes that $\epsilon$ is a cause of $X$, our proposed FDGN consider that $\epsilon$ is a cause of both $X$ and $A$. In other words, the DGP of FDGN contains the causal relationships $\epsilon → X$ and $\epsilon → A$, as real-world applications often exhibit graph structure noise originating from arbitrary sources (i.e., $\epsilon$) in addition to the feature-dependent noise. Therefore, this scenario is a unique characteristic of our problem and not addressed in [1]. To deal with this, we decompose $q_{\phi_2}(\epsilon |X,A,Z_Y)$ into $q_{\phi_{21}}(\epsilon_X | X, Z_Y)$ and $q_{\phi_{22}}(\epsilon_A|X,A)$. While the instantiation of $q_{\phi_{21}}(\epsilon_X | X, Z_Y)$ is similar to [1], that of $q_{\phi_{22}}(\epsilon_A|X,A)$ is non-trivial and is absent in [1]. In our approach, we regard $\epsilon_A$ as a set of scores indicating the likelihood of each observed edge being noisy or not. Moreover, we leverage the concept of early-learning phenomenon to infer $\epsilon_A$. It is worth emphasizing once again that the instantiation of this scenario is novel and not a straightforward extension of [1].

Loss term $kl(q_{\phi_1}(Z_A|X,A)||p(Z_A))$

To compute this loss term, we encounter two primary challenges:

1. Designing an appropriate prior for the latent graph structure $p(Z_A)$
2. Addressing the complexity associated with calculating the KL divergence between the two matrices sampled from Bernoulli distributions.

In response to the first challenge, we employ the $\gamma$-hop subgraph similarity as a metric to identify assortative edges. Regarding the second challenge, we introduce a predefined candidate graph, which includes the observed edge set along with a $k$-NN graph based on the $\gamma$-hop subgraph similarity. Both of these challenges represent non-trivial aspects of our approach and are absent in [1].

Loss term $kl(q_{\phi_3}(Z_Y|X,A)||p(Z_Y))$

To compute this loss term, [1] employs a uniform distribution as the prior $p(Z_Y)$. In contrast, we introduce the concept of class homophily to effectively regularize the inference of latent clean node label $Z_Y$. Specifically, we encourage $Z_Y$ to align with our prior knowledge, i.e., $p(Z_Y)$, that the two end nodes on the accurately inferred latent graph structure $Z_A$ are expected to have identical latent labels. Therefore, using this prior helps alleviate the noisy node label issues.

It is essential to highlight that this instantiation effectively utilizes the property unique to the graph domain, which is not present in [1]. It is worth emphasizing once again that such an instantiation is novel and not a straightforward extension of [1].

To be continued in the following post

We kindly request the reviewer to refer to our response addressing the concerns related to the limited technical novelty and high complexity. If the reviewer have any additional concerns, please don’t hesitate to bring them to our attention. We are eager to address any further concerns or questions the reviewer may have.