Technical Summary: Multi-Label Node Classification with Label Influence Propagation

Problem Definition

The paper addresses Multi-Label Node Classification (MLNC) on graphs, a task where nodes in a graph structure are assigned multiple labels simultaneously (e.g., proteins with multiple functions or users with diverse interests). While existing methods utilize Graph Neural Networks (GNNs) to exploit label co-occurrence or incorporate label embeddings, the authors argue that these approaches fail to account for the intricate influences between labels in non-Euclidean graph data. Specifically, current strategies often underestimate complex correlations, merely assessing label proximity without modeling how one label can positively enhance or negatively harm the prediction of another.

Methodology: Label Influence Propagation (LIP)

The proposed solution, Label Influence Propagation (LIP), is a plug-and-play framework designed to quantify and leverage label influences to dynamically adjust the learning process. The methodology is built on three core pillars:

1. Decomposition of Message Passing

The authors decompose the GNN message passing process into two independent operations to analyze label influences separately:

• Propagation (P) Operation: Aggregates neighbor information (Laplacian smoothing). The paper theoretically demonstrates that influence in this step is independent of node features and parameters, relying instead on the graph structure.
• Transformation (T) Operation: Applies non-linear transformations via model parameters. Here, label influences arise from the interactions of gradients during backpropagation.

2. Quantification of Label Influences

The framework quantifies influences in both operations to construct a comprehensive influence matrix:

• Propagation Influence ($INFP$): Calculated using Personalized PageRank (PPR). The authors distinguish between positive and negative influences based on set theory:
  • Positive Influence: Nodes in label set $Y_a$ that do not share label $Y_b$ but help identify nodes in $Y_b$.
  • Negative Influence: Nodes in $Y_a$ that lack $Y_b$ but hinder the identification of $Y_b$.
  • Overlapping nodes ($Y_a \cap Y_b$) are treated as neutralizing factors.
• Transformation Influence ($INFT$): Calculated based on the gradient conflict between labels during backpropagation. Using the cosine similarity of gradients from the shared backbone, the method measures the angle between loss gradients; smaller angles indicate less negative (or more positive) influence.
• High-Order Influence ($INFMAT$): The final influence matrix is derived by element-wise multiplication of $INFP$ and $INFT$, capturing both structural and optimization-based correlations.

3. Dynamic Learning via Label Graph

To utilize these quantified influences, LIP constructs a Label Influence Graph ($G_{LIP}$):

• The influence matrix is converted into a weighted adjacency matrix using row-wise Softmax, treating negative influences as weak positive influences to preserve high-order connectivity.
• Importance Scoring: The authors apply PageRank on $G_{LIP}$ to calculate an importance score ($R$) for each label.
• Loss Adjustment: The final loss function is a weighted sum of individual binary cross-entropy losses, where the weight for each label is its calculated importance score. This dynamically amplifies labels with positive contributions and mitigates those with negative influence.

Key Contributions

1. Novel Perspective on Correlation: The paper dissects the MLNC pipeline into forward (propagation) and backward (transformation) segments, providing a theoretical and practical framework to analyze and quantify label influence correlations in both phases.
2. LIP Framework: The design of a method that calculates high-order label correlations and propagates influence to dynamically guide the model's learning process, specifically by adjusting loss coefficients based on label importance.
3. Empirical Superiority: Validation across comprehensive benchmarks (including OGB-proteins, DBLP, BlogCat, and biological datasets) demonstrates consistent improvements over State-of-the-Art (SOTA) methods.

Experimental Results

The authors evaluated LIP on six datasets across various domains (social, citation, and biological) under both node split and label split settings.

• Performance Gains: LIP outperformed existing baselines (including ML-GCN, LARN, LANC, and VariMul) by an average of 3.06% in Macro AUC under node split and 3.42% under label split settings.
• Backbone Agnosticism: The method was tested as a "plug-and-play" booster on various GNN backbones (e.g., GCN, GAT, H2GCN). Results indicated that LIP consistently improved performance across different architectures, regardless of whether the underlying graph was homophilic or heterophilic.
• Ablation Studies: Experiments confirmed that combining both propagation ($INFP$) and transformation ($INFT$) influences yields the best results, validating the necessity of analyzing both forward and backward information transmission. Furthermore, the captured influence correlations were shown to align more closely with ground-truth performance differences than traditional co-occurrence or cosine similarity metrics.

Significance and Claims

The paper claims that the primary significance of LIP lies in its ability to explicitly analyze and quantify the complex, bidirectional influences between labels on graphs, a factor previously overlooked or underutilized. By decomposing the message passing mechanism, the authors reveal that graph structure drives influence during propagation, while parameter interactions drive influence during transformation.

The framework addresses the challenge of "entangled" label effects by dynamically adjusting the learning process: it encourages labels that positively influence others and suppresses those that cause negative interference. The authors position LIP not as a replacement for specific GNN architectures, but as a universal enhancement that improves the utilization of multi-label information, leading to more robust and accurate node classification across diverse graph domains.