Multi-Label Node Classification with Label Influence Propagation
Abstract Overview
This paper studies multi-label node classification on graphs by focusing on how labels influence one another, rather than only modeling label co-occurrence or label proximity. The authors decompose GNN message passing into propagation and transformation operations, then analyze label influence in each part separately: propagation influence is tied to graph structure via node-to-node influence and Personalized PageRank, while transformation influence is quantified through interactions among label-specific gradients. Based on these pairwise influences, they build a label influence graph and propagate higher-order influence over it to compute label importance scores. These scores are used to reweight per-label losses during training in the proposed Label Influence Propagation (LIP) framework, which is designed as a plug-and-play module for different GNN backbones.
Novelty
The main novelty is an explicit treatment of label influence on graphs as potentially positive or negative, rather than relying only on co-occurrence statistics or label embeddings. Methodologically, the paper introduces a decomposition of GNN message passing into propagation and transformation for influence analysis, then combines the two into a label influence graph whose PageRank-style scores dynamically guide multi-label training.
Results
Across six benchmark datasets from different domains, LIP is reported to consistently outperform prior MLNC baselines under multiple evaluation settings. The paper states average Macro AUC gains of 3.06% under node-split evaluation and 3.42% under label-split evaluation, and also shows that LIP improves several different GNN backbones rather than only a single architecture.
Key Points
- LIP quantifies label interactions in two separate parts of GNN learning: graph-structure-driven propagation influence and gradient-driven transformation influence.
- The method constructs a higher-order label influence graph from the combined pairwise influences and uses PageRank-style importance scores to upweight helpful labels and downweight harmful ones in the loss.
- Experiments and ablations indicate that combining both influence components performs better than using either alone, and the approach acts as a plug-in booster across multiple graph backbones.