Multi-Label Node Classification with Label Influence Propagation

Q3. How is the performance under specific inductive setting?

Thank you for your practical suggestions regarding the inductive setting.

Following your advice, we perform the inductive train/val/test split (6:2:2) and conducted experiments, which we have added in Appendix E.6. Due to time constraints, we have supplemented the results with comparisons on two datasets from different domains. We used GraphSage as the backbone because it is naturally suited for the inductive setting. We also excluded certain baselines that are not suitable for the setting, such as VariMul and MLGW. The results are shown in the table below.

Table 1. Performance (AUC) comparison under inductive setting.

It shows that our method also achieves satisfactory performance under the inductive setting. Although the model cannot observe the complete graph in the inductive setting, the subgraph containing the nodes whose labels need to be predicted is visible. Therefore, our model’s quantification of influence correlations during P step remains meaningful and effective. Since inductive training also involves mutual interactions between gradients of different labels, modeling the influence relationships between labels in the T step is also necessary. As a result, our method achieves performance surpassing the baselines even under the inductive setting.

[1] Representation Learning on Graphs with Jumping Knowledge Networks (JKNet).

[2] Predict then propagate: Graph neural networks meet personalized pagerank (APPNP).

[3] Semi-supervised classification with graph convolutional networks (GCN).

[4] Model Degradation Hinders Deep Graph Neural Networks.

[5] Deeper insights into graph convolutional networks for semi-supervised learning.

[6] The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges.

Q1. Provide additional explanation of the performance enhancement on heterophilous graphs.

Sorry for the misleading expressions. We have polished the paper accordingly.

Actually, our analysis is based on the Laplacian smoothing effect inherent in the propagation (P) step rather than homophily.

That is, as the number of propagation or aggregation layers in the message passing increases, the representations and predicted labels of neighboring nodes tend to become increasingly similar. In simple terms, the negative influence during the P step, originates from nodes in $Y\_a$ and $Y\_b$ (excluding their intersection) that are supposed to have different labels but become similar during the P step. Conversely, the positive influence comes from nodes with the same labels, such as nodes in $Y\_b$ without the intersection, which become more similar during the P process, making it easier to achieve correct label predictions.

In fact, the design of our method is independent of whether the graph follows the homophily assumption.

As long as the backbone model includes a propagation or aggregation step, the influence during these processes can be analyzed as described above (more detailed in Sec 4.2). We mentioned homophily mainly because, as noted in [1], the smoothing of propagation step significantly aids homophily graphs. However, homophily is not a necessary condition for the P step. Existing graph models specifically designed for heterophily graphs also include propagation steps [6].

Therefore, our conclusion that the method achieves performance improvement on both homophily and heterophily graphs is based on the following:

1. Our quantification of label influence correlations during the P step is grounded in the Laplacian smoothing, which is present in the P step from the models designed for both homophily and heterophily graphs.
2. We also quantify the label influence correlations during the T step and construct a label influence graph to capture higher-order influence correlations. This allows us to enhance/suppress the positive/negative label influences, which is independent of whether the graph is homophilic or heterophilic.
3. Our method is designed independent of the backbone model. For heterophily graphs, we can use graph models specifically designed for heterophily graphs as backbone to achieve further performance improvements.

Q2. How does the performance change when varying the $\beta$?

We have added a hyper-parameter sensitivity study in Appendix E.5, especially $\beta$.

The conclusion is that our method demonstrates robustness across a range of hyper-parameter settings. Specifically, the performance remains stable within reasonable parameter ranges, indicating that the model does not heavily depend on fine-tuned hyper-parameters for achieving effective results. Moreover, we find that regardless of the dataset characteristics, the optimal range for $\beta$ is approximately between 0.10 and 0.56.

Dear reviewer SyKm,
Thank you for your insightful comments. Please, see below our answer to the raised comments/questions.

W1. Several grammatical issues need proofreading.

Thank you very much for your thorough review and detailed suggestions.

We have made the corresponding revisions in the revised pdf and highlighted the revisions in blue. We will continue to polish the paper to further enhance its readability. Moreover, we rewrite the explanation preceding Def. 4 to provide a detailed explanation of the positive influence.

W2.1 How the influence $I(i, j)$ and PPR are connected to the proposed label influence metric in the propagation operation?

We have revised the motivation and analysis in Sec 4.2 and Appendix A to better clarify the relationship between the influence among labels during the propagation (P) step and $I(i, j)$, PPR.

Overall, we decompose the computation of influence correlations among labels during the P step into two parts: the magnitude of influence between all pairs of nodes ("Influence between node pairs" at line 247) and the positive or negative direction of influence between node pairs with different labels ("Influence between label sets" at line 268).

For the first part, our analysis shows that the magnitude of influence between any pair of nodes during the P phase can be defined as $I(i, j)$. Although the calculation of $I(i, j)$ initially involves node features, inspired by [1], we prove that the magnitude of $I(i, j)$ is actually independent of the features themselves and is instead proportional in expectation to a random walk distribution $\mathbf{\pi}\_{\text{lim}}^{(ji)}$, namely $I(i, j) \propto \mathbf{\pi}\_{\text{lim}}^{(ji)}$. To further quantify and compute this distribution $\mathbf{\pi}\_{\text{lim}}$, inspired by [2], we find that we can solving the PPR $\mathbf{\pi}\_{\text{ppr}}$ instead. By iteratively computing the PPR, we can obtain the influence correlations between any two nodes. Thus, we derive the quantification of the influence between any pair of nodes $v_i, v_j$ during the P phase as: $\mathbf{INF}^{P}(v_i, v_j) := I(i, j) \propto \mathbf{\pi}\_{\text{ppr}}^{(ji)} = \{ \alpha (\mathbf{I}\_n - (1 - \alpha)\hat{\mathbf{A}})^{-1} \mathbf{s}_{v_i} \}\_{v_j}$

Having computed the influence correlations magnitude $\mathbf{INF}^{P}(v_i, v_j)$ between any pair of nodes during the P phase, represented as an  $n\times n$ node influence correlation matrix, the second part involves integrating the influence from all nodes in  $Y_a$  (with label $y_a$) on all nodes in  $Y_b$ (with label $y_b$) to get the label influence correlation between $y_a$ and $y_b$. This part yields a $k \times k$ label influence correlation matrix $\mathbf{INF}^{P}(y_a,y_b)$. Through our analysis, we find that the influence from $Y_a$ to $Y_b$ has both positive and negative directions. Based on the analysis in Fig. 3, we identified the node sets contributing to the positive (Eq. 6) and negative influences (Eq. 5) for any pair of labels. By incorporating these signs and integrating the pairwise influences between nodes $\mathbf{INF}^{P}(v_i, v_j)$, we can ultimately compute the influence correlations between labels $\mathbf{INF}^{P}(y_a,y_b)$.

In short, the label influence correlation $\mathbf{INF}^{P}$ in the P operation is defined as $I(i, j)$, which can be directly computed using PPR.

W2.2 What is the augmented form of $A$?

We have added a more detailed description in line 252 of revised version. Specifically, the augmented form of $\mathbf{A}$ that we use is $\hat{\mathbf{A}} = \mathbf{{\tilde{D}}}^{-1/2} \mathbf{{\tilde{A}}} \mathbf{{\tilde{D}}}^{-1/2}$ [2]. Namely, $\hat{\mathbf{A}}$ is the symmetrically normalized adjacency matrix with self-loops, where $\mathbf{\tilde{A}}= \mathbf{A} + \mathbf{I}\_n$ is the adjacency matrix with added self-loops, $\mathbf{{\tilde{D}}}\_{ij} = \delta\_{ij} \sum\_k \mathbf{{\tilde{A}}}\_{ik}$ is the diagonal degree matrix [3], $\delta_{ij}$ is the Kronecker delta function indicating the edge between $i$ and $j$.

W3. What are the limitations of the method?

We have added a paragraph of "limitation and future work" in the Appendix.

From a scenario perspective, our work currently focuses on the most common case: static and homogeneous graphs. That is, the nodes, edges, and labels do not change over time, and all nodes in the dataset are of the same type, with all edges sharing the same physical meaning. From a goal perspective, our work is currently focused on improving the performance of MLNC tasks analyzing and quantifying the influence correlations between labels on graph datasets, without considering potential noise in the labels or graph structure. We leave these complex challenges in both aspects for future exploration.

Q3. Conduct ablation study of Fig. 4b on all other datasets.

We supplement the ablation study across all datasets (the full version of Fig. 4b), which is shown in the table below. "None" stands for simply using the backbone model without any quantification of influence correlations between labels.

Table 2. Ablation study of label influences on all datasets (GCN as backbone).

It can be observed that in all cases, utilizing the influence correlations from both propagation (P) and transformation (T) steps (noted as All in the table) achieves the best performance than using the influence from either phase alone. Moreover, individually quantifying and utilizing either type of influence correlations yields better performance than not using them at all. This indicates that leveraging the influence relationships from both the P and T steps is crucial for the MLNC task. Additionally, the table reveals that using the influence correlations from either the P step or the T step alone can achieve better results on different datasets. We hypothesize that this is due to the varying demands of different datasets for the P and T processes. Some datasets may require minimizing negative influence during the P process, while others may benefit from maximizing positive influence during the T process.

Q4.  Report the computational cost of each method, including training time and GPU memory.

We have added a table below showing the average per-epoch training time and GPU memory usage of various methods on graph data from two different domains.

Table 3. Computational cost of each method, including time and space during training.

As observed, our method aligns with the conclusions analyzed in Appendix B, demonstrating relatively shorter training times and especially lower GPU memory usage. This indicates that our method has better scalability. Specifically, our training time is roughly on the same order of magnitude as a standard GCN but takes a few times bigger. However, compared to other baselines, our method typically requires one order of magnitude less time. On the other hand, since the quantification of influence correlations during the T step involves gradient calculations, our method essentially splits the gradient calculation into k smaller steps. This trades off some computation time for reduced memory usage, allowing our method to achieve even lower GPU memory consumption than a standard GCN.

Dear reviewer SoZZ,
Thank you for your insightful comments. Please, see below our answer to the raised comments/questions.

Q1. Discussion about decoupled GNNs.

Thank you for your valuable suggestions. We have added a paragraph in Sec. 2 of the paper as suggested. For a detailed discussion on decoupled GNN-related works, please refer to the additional paragraph in the revised paper. Here, we focus on discussing the relationship between our work and decoupled GNNs.

Our work is inspired by these studies that disentangle [1] or decouple [2,3,4] the message passing process into propagation (P) and transformation (T) operations. We focus more on analyzing the influence correlations between labels during the P and T operations, rather than designing specific P and T operations to increase model performance [2,3] or enhance model capacity and scalability [4]. Moreover, as shown in the backbone replacement experiments in the response to the next question, our method achieves performance improvement regardless of whether the backbone is a decoupled or non-decoupled GNN.

Q2. Try more advanced decoupled GNNs as backbones.

We have conducted a series of experiments by replacing the backbone with more advanced decoupled GNNs: APPNP [2] and GPRGNN [3]. APPNP is a classical yet powerful model, while GPRGNN achieve state-of-the-art (SOTA) on both homophily and heterophily graphs. We have also added experiments with other alternative backbones in Appendix E.4 of the revised pdf. Here, we evaluate the effectiveness of our method, LIP, on these advanced decoupled GNNs and present a comparison of the results between the original models and the LIP-enhanced models on MLNC tasks in the table below.

Table 1. Changing backbones (AUC) under node split on MLNC datasets.

From the table above, we can observe that even for high-performance decoupled GNN models, LIP consistently achieves performance improvements. LIP provides enhancements across different domains and demonstrates exceptional results on certain datasets. For example, LIP improved the performance of GPRGNN by approximately 4% on the BlogCat dataset. In many cases, the performance improvement brought by LIP exceeds the performance differences between different models, highlighting the value of incorporating LIP. This is because these backbones primarily focus on modeling the input graph structure and node features. Regardless of the type of GNNs used, our LIP can provide additional support by modeling the influence correlation between labels.

[1] Model Degradation Hinders Deep Graph Neural Networks.

[2] Predict then propagate: Graph neural networks meet personalized pagerank (APPNP).

[3] Adaptive universal generalized pagerank graph neural network (GPRGNN).

[4] Neighborhood Convolutional Graph Neural Network (NCGNN).

Dear reviewer jPZg,
Thank you for your insightful comments. Please, see below our answer to the raised comments/questions.

W1. What is the difference between the label propagation methods?

Thank you very much for your suggestion. We have added a paragraph for label propagation algorithm (LPA) related work in Appendix C. Please refer to it for the complete version of the discussion.

LPA is a classic and insightful algorithm that has inspired a series of related GNN works. In GMNN [1], the M-step models label dependencies using a GNN. GCN-LPA [2] not only theoretically analyzed the relationship between GCN and LPA but also incorporated LPA as a regularization term for GCN, improving the performance of single-label node classification. R2LP [3] not only generalizes LPA to more realistic scenarios involving heterophily graphs and varying noise levels but also provides a theoretical analysis of its effectiveness on label denoising.

The differences between our Label Influence Propagation (LIP) and the LPA-related works are mainly threefold:

1. Propagation target: We do not propagate labels; instead, we propagate the influence between labels.
2. Propagation medium: In LPA, the propagation medium is typically the graph structure that connects nodes. In contrast, the propagation medium in LIP is the label propagation graph, constructed by quantified pairwise label influences. In this graph, nodes are labels, and edges are the influence correlations between labels.
3. Purpose of propagation: The purpose of propagating label influence is not to infer unknown labels or denoise existing labels, but rather to extend the computed pairwise label influences on high-order label influences. This ultimately encourages labels with positive influence and suppresses those with negative influence.

W2. How does the performance change when varying the $\alpha, \beta$?

We have added a hyper-parameter sensitivity study on $\alpha, \beta$ in Appendix E.5.
The conclusion is that our method demonstrates robustness across a range of hyper-parameter settings. Specifically, the performance remains stable within reasonable parameter ranges, indicating that the model does not heavily depend on fine-tuned hyper-parameters for achieving effective results. Moreover, we find that regardless of the dataset characteristics, the optimal range for $\alpha$ is approximately between 0.08 and 0.30, while the optimal range for $\beta$ is approximately between 0.10 and 0.56. We choose 0.15 and 0.28 respectively for $\alpha, \beta$.

W3. How does the number of label categories $k$ affect the model?

Thank you for this insightful question. Due to time constraints, we only tested the performance of different label quantities on a single dataset, HumLoc. We used GCN as the backbone to compare and analyze the performance of our method across different label number of label categories $k$.

Table 1. Performance (AUC) when changing the number of label categories $k$ on HumLoc.

From the table above, we can observe that our method consistently achieves performance boosting regardless of the number of labels. We also identified some interesting phenomena from the experiments. First, for GCN, the performance is actually the best when the number of labels is 2. This phenomenon can be understood from two perspectives: On one hand, statistical analysis shows that label 2 is the category with the highest number of training nodes across all training datasets. Therefore, when the total number of labels is 2, the contribution of label 2 leads to a higher average performance. On the other hand, this also indicates that, to some extent, an increase in the number of labels results in a decline in GCN’s prediction performance.

Moreover, with our method, the performance generally improves as the number of labels increases. In contrast, GCN’s performance fluctuates as the number of labels increases, sometimes improving and sometimes deteriorating. This indirectly indicates that our method reduces the negative influence between labels while enhancing the positive influence.

W4. Give some examples to show the positive and negative influences between labels and how these influences affect the model’s predictions.

Thank you very much for your suggestion. We have added a case study in Appendix E.8 to better illustrate the positive and negative mutual influences between labels. In this study, we take a specific node and its surrounding neighbors as an example to demonstrate the influences between labels and how these influences contribute to either improving or impairing the prediction of the node.

It is worth noting that, as discussed in Sec. 4, the influence between labels is quite complex. The influence from $Y_a$ to $Y_b$ is the combined effect of a group of nodes with label $y_a$ on a group of nodes with label $y_b$ during both the P and T processes. Here, we attempt to visualize the positive and negative influences, as well as their ultimate effect on performance, using the local structure of a single node rather than a group of nodes with the same label. The case study provides a simplified perspective on these interactions.

W5. Try more backbones, such as GIN.

We have conducted a series of experiments by replacing the backbone with other commonly used GNNs: GIN[4] and APPNP[5]. GIN is a GNN model with theoretical proof of high expressive power. APPNP is a classical yet powerful model. We have also added experiments with other alternative backbones in Appendix E.4 of the revised pdf. Here, we evaluate the effectiveness of our method, LIP, on these GNNs and present a comparison of the results between the original models and the LIP-enhanced models on MLNC tasks in the table below.

Table 2. Changing backbones (AUC) under node split on MLNC datasets.

From the table above, we can observe that even for high-performance GNNs, LIP consistently achieves performance improvements. LIP provides enhancements across different domains and demonstrates exceptional results on certain datasets. For example, LIP improved the performance of GIN by approximately 3% on the PCG dataset. In many cases, the performance improvement brought by LIP exceeds the performance differences between different models, highlighting the value of incorporating LIP. This is because these backbones primarily focus on modeling the input graph structure and node features. Regardless of the type of GNNs used, our LIP can provide additional support by modeling the influence correlation between labels.

W6. The label of the x-axis of Fig.4c is missing.

Thank you for your careful and detailed review. As stated in the original paper on lines 522-523, the horizontal axis of this figure represents the number of epochs. Additionally, we have added have added labels (number of epochs) to the horizontal axis of in Fig. 4c in the revised version.

[1] GMNN: Graph Markov Neural Networks.

[2] Combining Graph Convolutional Neural Networks and Label Propagation (GCN-LPA).

[3] Resurrecting Label Propagation for Graphs with Heterophily and Label Noise (R2LP).

[4] How Powerful are Graph Neural Networks? (GIN)

[5] Predict then propagate: Graph neural networks meet personalized pagerank (APPNP).

Dear reviewer jPZg,

Thank you for the time and effort you have dedicated to reviewing our submission.

We sincerely appreciate your positive rating and hope that our responses to your review comments have addressed your concerns. As the discussion phase is coming to an end, we would like to know if you have any additional questions or suggestions.

Thank you once again.

Dear reviewer d1PZ,
Thank you for your insightful comments. Please, see below our answer to the raised comments/questions.

W1. How does the model scale with an increasing number of label categories $k$ or nodes $n$?

Thank you for this insightful question.

• Scales with increasing number of label categories $k$.

Due to time constraints, we only tested the performance of different label quantities on a single dataset, HumLoc.

Table 1. Performance (AUC) when changing the number of label categories $k$ on HumLoc.

From the table above, we can observe that our method consistently achieves performance boosting regardless of the number of labels. Moreover, the performance generally improves as the number of labels increases. In contrast, GCN’s performance fluctuates as the number of labels increases, sometimes improving and sometimes deteriorating. This indirectly indicates that our method reduces the negative influence between labels while enhancing the positive influence.

• Scales with increasing number of nodes $n$.

In the MLNC task setting, the total number of nodes in the graph is fixed, meaning that the model can access all nodes during training. Therefore, it is not feasible to vary the number of nodes while keeping the number of labels constant. However, as shown in Table 4 of the paper, our method has been evaluated on datasets ranging from graphs with a few thousand nodes to graphs with millions of nodes. The results indicate that our method consistently achieves improvements across these datasets. Furthermore, regarding the training cost, theoretical complexity analysis and empirical statistics on runtime and memory consumption are provided in Appendix C.

In conclusion, our method not only achieves satisfactory results but also demonstrates considerable scalability in terms of both $k$ and $n$.

Q1. What are the limitations of decomposing message passing into the propagation (P) and transformation (T) operations? Are there cases where this decomposition might not hold?

Thank you for your insightful question. In essence, both P and T are operations inherently present in the message passing process. Some decomposing or decoupling GNN models separate P and T to allow independent adjustment of their layers and positions, enabling deeper models to maintain better performance. However, existing work [1] has shown through extensive experiments that good performance can be achieved regardless of whether P and T are decomposed. Furthermore, improper design of the layer configuration for P and T after decomposing can lead to performance degradation.

Specifically, as discussed in Appendix A.1 of [1], non-decomposing methods such as ResGCN and DenseGCN can still achieve strong performance when the model depth increases (e.g., Figure 4(b) in [1]). This suggests that decomposing is not the only way to achieve good results. On the other hand, for some decomposing methods like DAGNN [2], increasing both the P and T layers simultaneously can result in a significant performance drop as the depth increases (e.g., Figure 9(a) in [1]). However, with a slight modification—fixing the number of T layers to 2 while only increasing the P layers—relatively stable performance can be maintained. This demonstrates that even when using a decomposing approach, specific designs are required to ensure the method’s effectiveness.

In the context of our work, we focus on analyzing the influence correlations between labels during the P and T operations, rather than designing how P and T should be combined or adjusted to increase model depth. As shown in the backbone replacement experiments in our Appendix E.3, our method achieves performance improvement regardless of whether the backbone is a decomposed or non-decomposed GNNs.

[1] Model Degradation Hinders Deep Graph Neural Networks.

[2] Towards deeper graph neural networks (DAGNN).

Q2. How sensitive is the method to the initial construction of the label influence graph?

Actually, our method does not involve any specific initialization for the label influence graph  $G_{LIP}$ . In fact,  $G_{LIP}$  is computed using Equations 4, 9, 10, and 11 from Section 4, directly after the backbone model performs its first predictions. In other words, our method does not manually set an initial state or randomly initialize the structure of  $G_{LIP}$.