Multi-Label Node Classification with Label Influence Propagation

# Multi-Label Node Classification with Label Influence Propagation
Source: [https://arxiv.org/html/2607.00671](https://arxiv.org/html/2607.00671)
Yifei Sun1, Zemin Liu1, Bryan Hooi2, Yang Yang111footnotemark:1, Rizal Fathony3, Jia Chen4, Bingsheng He211footnotemark:1 1Zhejiang University,2National University of Singapore, 3Capital One,4GrabTaxi Holdings Pte\. Ltd\. \{yifeisun, liu\.zemin, yangya\}@zju\.edu\.cn, \{bhooi, hebs\}@comp\.nus\.edu\.sg, rizal\.fathony@capitalone\.com,jia\.chen@grab\.com

###### Abstract

Graphs are a complex and versatile data structure used across various domains, with possibly multi\-label nodes playing a particularly crucial role\. Examples include proteins in PPI networks with multiple functions and users in social or e\-commerce networks exhibiting diverse interests\. Tackling multi\-label node classification \(MLNC\) on graphs has led to the development of various approaches\. Some methods leverage graph neural networks \(GNNs\) to exploit label co\-occurrence correlations, while others incorporate label embeddings to capture label proximity\. However, these approaches fail to account for the intricate influences between labels in non\-Euclidean graph data\. To address this issue, we decompose the message passing process in GNNs into two operations:*propagation*and*transformation*\. We then conduct a comprehensive analysis and quantification of the influence correlations between labels in each operation\. Building on these insights, we propose a novel model, Label Influence Propagation \(LIP\)\. Specifically, we construct a label influence graph based on the integrated label correlations\. Then, we propagate high\-order influences through this graph, dynamically adjusting the learning process by amplifying labels with positive contributions and mitigating those with negative influence\. Finally, our framework is evaluated on comprehensive benchmark datasets, consistently outperforming SOTA methods across various settings, demonstrating its effectiveness on MLNC tasks111Our code is available at[https://github\.com/Xtra\-Computing/LIP\_MLNC](https://github.com/Xtra-Computing/LIP_MLNC)\.\.

## 1Introduction

Graphs, as a complex data structure, are prevalent across various fields\(Jianget al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib15); Kipf and Welling,[2016](https://arxiv.org/html/2607.00671#bib.bib2); Yinget al\.,[2018](https://arxiv.org/html/2607.00671#bib.bib14); Liuet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib101); Fanget al\.,[2024](https://arxiv.org/html/2607.00671#bib.bib63)\)\. Among these, graphs with multi\-label nodes are common and of great importance\. For instance, proteins in ogbn\-protein dataset have multiple functions\(Huet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib16)\)\. Accurately identifying all the functions can assist with understanding biological processes and advancing biomedical research\. Thus, we focus on this realistic but challenging problem named multi\-label node classification on graphs, which we abbreviate as MLNC in the following paper\.

Prior studies\.Current methods typically adopt three strategies to address this problem\. The*first strategy*is to neglect the multi\-label information and predict the labels without mining label correlations\(Shiet al\.,[2020b](https://arxiv.org/html/2607.00671#bib.bib33); Liet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib32)\)\. The*second strategy*is to explicitly treat labels as a new type of node and incorporate them into the original graph, thereby enhancing task performance through propagation and aggregation information between nodes and label nodes\(Gaoet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib50); Shiet al\.,[2020a](https://arxiv.org/html/2607.00671#bib.bib47)\)\. Since only incomplete connections between nodes and label nodes are available in the training set, the*third strategy*is to integrate label representations into the neighbor aggregation and classification processes, thereby improving the utilization of multi\-label information\(Zhouet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib44); Xiaoet al\.,[2022](https://arxiv.org/html/2607.00671#bib.bib45)\)\. However, these strategies underestimate the complex label correlations in graph data, only assessing label proximity without modeling their influence, thereby failing to fully utilize these correlations to improve MLNC\.

Observations\.Our observations \(Fig\.[3](https://arxiv.org/html/2607.00671#footnote3)\) further show that, for graph data, different labels can mutually enhance or harm each other’s performance\. Specifically, we compare the performance differences when training a graph neural network \(GNN\) using both row and column labels simultaneously versus training with only column labels individually\. A positive difference indicates that jointly training with row and column labels outperforms training with column label alone, implying that the row label can enhance the column label\. Conversely, a negative difference suggests a negative influence\. As shown in Fig\.[3](https://arxiv.org/html/2607.00671#footnote3), most graph datasets exhibit both positive and negative influence between labels\. Therefore, in this paper we aim to analyze and quantify these complex label influences on graphs to enhance or mitigate the positive or negative effects\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/x1.png)Figure 1:Observations showing positive \(red\) and negative \(blue\) influence between different labels\. Each value in the heat maps333These heat maps are asymmetric because each value represents the degree to which the row label helps \(\+\+\) or harms \(−\-\) the column label\. Without loss of generality, we selected the first 10 labels as observation targets \(except for DBLP\) due to space limitations\.represents the performance on the column label when trained together with the row label, minus the result of training the column label individually\.Challenges\.However, given the intricate nature of graph, several challenges emerges\. First, the influences existing not only between labels themselves but between nodes entangled together through graph structure\. Thus,*how to quantify the influences between labels on the complex non\-Euclidean graph data*is the first challenge\. Second, since any label may exert both positive and negative influences on multiple other labels simultaneously, the second challenge is*how to capture the high\-order influence correlations between all labels*\. Finally, our goal is to encourage or suppress labels that bring positive or negative influences, respectively\. Thus,*how to leverage the quantified high\-order influence correlations to enhance the performance of MLNC task*is the third challenge\.

Present work\.To address the*first*challenge, we decompose the message passing into propagation and transformation operations\(Zhanget al\.,[2022a](https://arxiv.org/html/2607.00671#bib.bib85)\), allowing for a detailed analysis of the label influence correlation on graph data\. Moreover, we provide a theoretical analysis, grounded in the inductive biases inherent in graph models\(Xuet al\.,[2018a](https://arxiv.org/html/2607.00671#bib.bib22); Wang and Leskovec,[2020](https://arxiv.org/html/2607.00671#bib.bib19)\), revealing that the graph structure itself is a key driver of label influence during propagation operation\. As for transformation operation, our analysis revealed that the dynamic interactions between labels during training are caused during each back propagation on model parameters\. The above two parts of the label influence analysis not only provide a deep insight into multi\-label correlations on graph data but also lay a solid foundation for improving MLNC on graphs\.

To tackle the*second*challenge, we construct a high\-order label influence propagation graph based on the pair\-wise correlations\. Thus, we can quantify the propagated influence from one label to any other labels on graph data\. For the*third*challenge, we propose a novel method,LabelInformationPropagation \(LIP\), which contains the above quantification steps and crafts the training dynamics among multiple labels to improve the overall performance\. By calculating the importance of each label in this propagation graph, we dynamically adjusted its learning proportion throughout the training process\. This ensures that labels with more positive influence on others are learned more effectively, while minimizing negative interactions between labels, ultimately enhancing the performance of MLNC\. As a plug\-and\-play approach, our method can be applied to various GNN backbones\. We validated its effectiveness using multiple settings on the most comprehensive collection\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)of MLNC datasets\.

Contributions\.To summarize, our contributions are three\-fold\.

- •We offer a novel perspective on label correlation analysis by dissecting the pipeline into forward and backward propagation segments, where we conduct a thorough analysis and quantification of the influence correlation between labels\.
- •Building on the quantified pairwise label influence, we designLIP, which calculates high\-order label correlation and the influence propagation between labels to dynamically guide the learning process of the model\.
- •Empirically, we validate the superiority of our method on MLNC graph data across various domains, showing improvements \(AUC\) of 3\.06% and 3\.42% on average under the node split and label split settings, respectively\.

## 2Related Work

Multi\-label Node Classification \(MLNC\)\.To promote research on MLNC, MLGNC\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)provides three biological datasets and performs a detailed analysis on both datasets and existing methods\. From the methodology perspective, some methods consider using textual embeddings of labels to incorporate label proximity\. LARN\(Xiaoet al\.,[2022](https://arxiv.org/html/2607.00671#bib.bib45)\)incorporates the all label embeddings during the neighbor aggregation process\. Similarly, LANC\(Zhouet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib44)\)proposes attention mechanism to aggregates the label embeddings with each node\. Another line of work construct additional label\-label network to use the label co\-occurrence correlations\. ML\-GCN\(Gaoet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib50)\)construct both node\-centric and label\-centric graphs to aggregate information, while MLNE\(Shiet al\.,[2020a](https://arxiv.org/html/2607.00671#bib.bib47)\)use random walk to get embedding on both label\-label network and original graph\. There are also some methods that modify the approach to modeling graphs from multi\-label perspective\. MLGW\(Akujuobiet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib49)\)leverage label\-specific agents to walk on graphs\. VariMul\(Songet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib46)\)utilizes VGAE to derive node and label embeddings and designs a confidence ranking loss to mine pairwise label correlations\. Recent work improves MLNC by addressing the ambiguity in multi\-label graph structures\(Beiet al\.,[2024](https://arxiv.org/html/2607.00671#bib.bib60)\)and the limited expressive power for multi\-label tasks\(Zhao and Khosla,[2024](https://arxiv.org/html/2607.00671#bib.bib59)\)\. However, these work do not explicitly analyze and quantify the influences between labels and exploit them to enhance the MLNC task\.

Decoupled GNNs\.Compared to conventional GNNs, decoupled GNNs explicitly isolate the two operations and aggregate all propagation \(P\) and transformation \(T\) operations separately for processing\. APPNPGasteigeret al\.\([2019](https://arxiv.org/html/2607.00671#bib.bib23)\)and DAGNNLiuet al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib24)\)first propose that decoupling the two operations can enable GNNs to go much deeper without causing over\-smoothing\. Although SGCWuet al\.\([2019](https://arxiv.org/html/2607.00671#bib.bib36)\)and lightGCNHeet al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib35)\)do not discuss the decouple paradigm, it demonstrate superior efficiency and performance\. PTADonget al\.\([2021](https://arxiv.org/html/2607.00671#bib.bib26)\)further explore the paradigm from the perspective of label propagation\. Since the APPNP is more suitable for homophily graphs, GPRGNNChienet al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib25)\)improves it by adaptively learning GPR weights\. This method not only avoids over\-smoothing but also enables adaptive filtering to handle heterophily graphs\. NCGNNChenet al\.\([2024a](https://arxiv.org/html/2607.00671#bib.bib27)\)improves model capacity and training efficiency by pre\-propagating node features, then employs a CNN\-based approach to aggregate the propagated features, adaptively capturing contextual information to boost the performance\. Our work is inspired by above studies that decouple or disentangleZhanget al\.\([2022a](https://arxiv.org/html/2607.00671#bib.bib85)\)the message passing process\. 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 performanceGasteigeret al\.\([2019](https://arxiv.org/html/2607.00671#bib.bib23)\); Chienet al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib25)\); Sunet al\.\([2022](https://arxiv.org/html/2607.00671#bib.bib61)\)or enhance model capacity and scalabilityChenet al\.\([2024a](https://arxiv.org/html/2607.00671#bib.bib27)\)\.

## 3Preliminaries

### 3\.1Problem Formulation

Given a graphG=\(V,E\)G=\(V,E\)with the adjacency matrix𝐀∈ℝn×n\\mathbf\{A\}\\in\\mathbb\{R\}^\{n\\times n\}, wheren=\|V\|n=\|V\|ande=\|E\|e=\|E\|are the total number of nodes and edges\. Each nodevi∈Vv\_\{i\}\\in Vis associated with a feature vector𝐱i∈ℝf\\mathbf\{x\}\_\{i\}\\in\\mathbb\{R\}^\{f\}, and all these feature vectors constitute the feature matrix𝐗∈ℝn×f=\[𝐱1,𝐱2,…,𝐱n\]T\\mathbf\{X\}\\in\\mathbb\{R\}^\{n\\times f\}=\[\\mathbf\{x\}\_\{1\},\\mathbf\{x\}\_\{2\},\\ldots,\\mathbf\{x\}\_\{n\}\]^\{T\}of the graphGG\. Among all the nodes,nln\_\{l\}ofnnare labeled while the remainingnun\_\{u\}ofnnare not\. For every nodeviv\_\{i\}in the labeled datasetDl=\{\(vi,yiseq\)\|1≤i≤nlD\_\{l\}=\\\{\(v\_\{i\},y^\{\\text\{seq\}\}\_\{i\}\)\\ \|\\ 1\\leq i\\leq n\_\{l\}\}, it also contains a set of labelsyiseq⊆𝐘y^\{\\text\{seq\}\}\_\{i\}\\subseteq\\mathbf\{Y\}drawn from the given label space𝐘=\{y1,y2,…,yk\}\\mathbf\{Y\}=\\\{y\_\{1\},y\_\{2\},\\ldots,y\_\{k\}\\\}withkkpossible class labels at most\. Furthermore, the label sets for the rest of the unlabeled nodesDu=\{vi\|nl\+1≤i≤nl\+nu\}D\_\{u\}=\\\{v\_\{i\}\\ \|\\ n\_\{l\}\+1\\leq i\\leq n\_\{l\}\+n\_\{u\}\\\}are not available\. The goal of MLNC on graphs under the semi\-supervised learning setting is to learn a modelh:V→2𝐘h:V\\rightarrow 2^\{\\mathbf\{Y\}\}with training dataD=Dl∪DuD=D\_\{l\}\\cup D\_\{u\}by taking both graph structure𝐀\\mathbf\{A\}and node feature𝐗\\mathbf\{X\}into consideration\. Moreover, we denote the nodes with labelyj∈𝐘y\_\{j\}\\in\{\\mathbf\{Y\}\}\(1≤j≤k1\\leq j\\leq k\), as a node setYj=\{v1,v2,…,vmj\}Y\_\{j\}=\\\{v\_\{1\},v\_\{2\},\\ldots,v\_\{m\_\{j\}\}\\\}, wheremjm\_\{j\}is the number of nodes belong to labelyjy\_\{j\}\.

### 3\.2Decomposition of MLNC Pipeline

Since MLNC is considered as correlated multiple binary classification problems on graphs, each determining the presence or absence of a certain label\(Zhang and Zhou,[2013](https://arxiv.org/html/2607.00671#bib.bib1)\)\. If a multi\-label task is modeled as unrelated single\-label tasks, it not only wastes the information brought by the other labels but also squanders model parameters\. Therefore, almost all the multi\-label methods adopt a common style which utilize a graph encoderΦθ\\Phi\_\{\\theta\}as the backbone to explore both the individual information of multiple labels and their correlation information\. The graph encoderΦθ\\Phi\_\{\\theta\}takes in the graph structure𝐀\\mathbf\{A\}and the node feature𝐗\\mathbf\{X\}and generate node embeddings𝐙∈ℝn×d\\mathbf\{Z\}\\in\\mathbb\{R\}^\{n\\times d\}as

𝐙=Φθ​\(𝐀,𝐗\),\\mathbf\{Z\}=\\Phi\_\{\\theta\}\(\\mathbf\{A\},\\mathbf\{X\}\),\(1\)where backboneΦθ\\Phi\_\{\\theta\}parameterized byθ\\thetacan be any existing GNNs, such as GCN\(Kipf and Welling,[2017](https://arxiv.org/html/2607.00671#bib.bib65)\), GAT\(Veličkovićet al\.,[2018](https://arxiv.org/html/2607.00671#bib.bib64)\), GraphSAGE\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.00671#bib.bib62)\)\.

Thereafter, the node embeddings𝐙\\mathbf\{Z\}are further mapped into different label spaces by multiple shallow classifiersΨ=\{ψ1,ψ2,…,ψk\}\\Psi=\\\{\\psi\_\{1\},\\psi\_\{2\},\\ldots,\\psi\_\{k\}\\\}with fewer parameters\. For each labelyjy\_\{j\}, the objective is to train a classifierψj\\psi\_\{j\}that computes the prediction𝒚~j∈ℝn\\tilde\{\{\\bm\{y\}\}\}\_\{j\}\\in\\mathbb\{R\}^\{n\}as

𝒚~j=ψj​\(𝐙\)\.\\tilde\{\{\\bm\{y\}\}\}\_\{j\}=\\psi\_\{j\}\(\\mathbf\{Z\}\)\.\(2\)By considering both Eqs\.[1](https://arxiv.org/html/2607.00671#S3.E1)and[2](https://arxiv.org/html/2607.00671#S3.E2)simultaneously, we observe that Eq\.[1](https://arxiv.org/html/2607.00671#S3.E1)is designed to generate node representations that are*shared*across all labels \(*i\.e\.*, all classifiers\) for subsequent tasks such as label prediction\. In contrast, Eq\.[2](https://arxiv.org/html/2607.00671#S3.E2)is specific to the labelyjy\_\{j\}and is utilized*privately*by the corresponding classifierψj\\psi\_\{j\}for label prediction\. Consequently, the architecture of the entire framework can be delineated into two main components: the*shared component*and the*private component*, with𝐙\\mathbf\{Z\}serving as the central bridge of the two components\.

###### Definition 1\(Shared component in MLNC\)\.

The shared component in MLNC boils down to the GNN backbone, parameterized byθ\\theta, which can be denoted asΦθ​\(𝐀,𝐗\)\\Phi\_\{\\theta\}\(\\mathbf\{A\},\\mathbf\{X\}\)\. This component is to encode nodes collectively to generate embeddings𝐙\\mathbf\{Z\}, irrespective of their associated labels\.

###### Definition 2\(Private components in MLNC\)\.

The private components in MLNC boils down to the classification head for each labelyjy\_\{j\}, denoted asψj\\psi\_\{j\}, corresponding to the operations𝐖j−1​𝐘j\{\\mathbf\{W\}\_\{j\}\}^\{\-1\}\\mathbf\{Y\}\_\{j\}\. This component is tasked with calibrating the node embeddings𝐙\\mathbf\{Z\}for label\-specific prediction\.

## 4Label Influence Propagation

![Refer to caption](https://arxiv.org/html/2607.00671v1/x2.png)Figure 2:The overall framework ofLIP: \(a\) quantify the influence correlations inPoperation \(Sec\.[4\.2](https://arxiv.org/html/2607.00671#S4.SS2)\) where the arrows with colors represents the mutual influence between labels; \(b\) quantify the influence correlations inToperation \(Sec\.[4\.3](https://arxiv.org/html/2607.00671#S4.SS3)\) whereℒbi\\mathcal\{L\}\_\{\\text\{bi\}\}separately calculates the loss of each label; \(c\) combine these two influence correlations to get the high\-order label influence, and propagate through the constructed graphGL​I​PG\_\{LIP\}to calculate the important scoreRRfor each label \(Sec\.[4\.4](https://arxiv.org/html/2607.00671#S4.SS4)\)\.### 4\.1Overview

The core idea ofLIPis to capture the influence between labels to guide the training process of model that need to be encouraged or suppressed within the overall set of labels\. To achieve this, we first need to quantify the relationships of mutual influence between labels\. Then, based on this influence relationship, we further capture high\-order relationship between labels and calculate the importance score of loss corresponding to each label during training\. Finally, we combine the losses with their respective importance levels to improve the MLNC tasks\.

The analysis from message passing\.While the graph structure makes analyzing label influence relationships highly challenging, these influences arise through the shared GNN backbone decomposed from Sec\.[3\.2](https://arxiv.org/html/2607.00671#S3.SS2)\. GNN relies on message passing as its core mechanism, enabling solutions to a wide range of graph applications\(Wuet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib30)\)\. Therefore, we begin by breaking down the message passing into two*independent*operations: propagation \(P\) and transformation \(T\)\(Zhanget al\.,[2022a](https://arxiv.org/html/2607.00671#bib.bib85)\)\. In short, thePstep is a form of Laplacian smoothing that aggregates the information of neighbors, while theTstep applies non\-linear transformations to capture the data distribution of the training samples\. On the one hand, in Sec\.[4\.2](https://arxiv.org/html/2607.00671#S4.SS2), theoretical analysis shows that the influence values inPoperation are independent of the node embeddings, and therefore unrelated to the parameters of message passing\. On the other hand, Sec\.[4\.3](https://arxiv.org/html/2607.00671#S4.SS3)analyzes the influence between labels inToperation which does not affect the topological structure between node sets with different labels, and is thus unrelated to the aggregation in message passing\. Since the two operations are independent, the quantified influence can be further combined as the foundation of computing high\-order influence correlations and help to improve MLNC task \(Sec\.[4\.4](https://arxiv.org/html/2607.00671#S4.SS4)\)\.

The overall framework is shown in Fig\.[2](https://arxiv.org/html/2607.00671#S4.F2)with three main parts: \(a\) calculating the influence between labels inPoperation, \(b\) calculating the influence between labels inToperation, and \(c\) propagating the influence on the label information propagation graph to form the final learning objective\.

### 4\.2Influences in Propagation Operation

This*propagation operation*involves aggregating information from their contextual nodes, which may belong to different labels\. Consequently, the intertwined distribution of nodes from various labels facilitates their interactions\. During propagation, the interaction we seek to analyze is between two label setsYaY\_\{a\}andYbY\_\{b\}\(1≤a,b≤k1\\leq a,b\\leq k\), which is shown in Fig\.[2](https://arxiv.org/html/2607.00671#S4.F2)\(a\)\. Specifically, 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”\) and the positive or negative direction of influence between node pairs with different labels \(”Influence between label sets”\)\.

Influence between node pairs\.We start the analysis by investigating the influence between node pairsviv\_\{i\}andvjv\_\{j\}\. Inspired by previous work\(Xuet al\.,[2018a](https://arxiv.org/html/2607.00671#bib.bib22); Wang and Leskovec,[2020](https://arxiv.org/html/2607.00671#bib.bib19); Zhanget al\.,[2021a](https://arxiv.org/html/2607.00671#bib.bib31)\), the influence fromviv\_\{i\}tovjv\_\{j\}can be quantified by measuring how alterations in the input feature𝐱i\\mathbf\{x\}\_\{i\}ofviv\_\{i\}affect the node embedding𝐳j\\mathbf\{z\}\_\{j\}ofvjv\_\{j\}afterlliterations of message passing\. In particular, forviv\_\{i\}andvjv\_\{j\}, supposing the message passing of the shared backboneΦθ\\Phi\_\{\\theta\}as𝐙\(k\)=𝐀^k​𝐙\(0\)​θ\\mathbf\{Z\}^\{\(k\)\}=\\hat\{\\mathbf\{A\}\}^\{k\}\\mathbf\{Z\}^\{\(0\)\}\\thetawhere𝐙\(0\)=𝐗\\mathbf\{Z\}^\{\(0\)\}=\\mathbf\{X\}and𝐀^=𝐃~−1/2​𝐀~​𝐃~−1/2\\hat\{\\mathbf\{A\}\}=\\mathbf\{\{\\tilde\{D\}\}\}^\{\-1/2\}\\mathbf\{\{\\tilde\{A\}\}\}\\mathbf\{\{\\tilde\{D\}\}\}^\{\-1/2\}is the symmetrically normalized adjacency matrix with self\-loops, the influence ofviv\_\{i\}on the final embedding ofvjv\_\{j\},*i\.e\.*,I​\(i,j\)I\(i,j\), can be defined as

I​\(i,j\)=∂𝐳j\(k\)∂𝐳i\(0\)\.\\textstyle I\(i,j\)=\\frac\{\\partial\\mathbf\{z\}^\{\(k\)\}\_\{j\}\}\{\\partial\\mathbf\{z\}^\{\(0\)\}\_\{i\}\}\.\(3\)Although the calculation ofI​\(i,j\)I\(i,j\)initially involves node features, inspired by\(Xuet al\.,[2018a](https://arxiv.org/html/2607.00671#bib.bib22)\), we prove that the magnitude ofI​\(i,j\)I\(i,j\)is actually independent of the features themselves and is instead proportional in expectation to a random walk distributionπlim\(j​i\)\\mathbf\{\\pi\}\_\{\\text\{lim\}\}^\{\(ji\)\}, namelyI​\(i,j\)∝πlim\(j​i\)I\(i,j\)\\propto\\mathbf\{\\pi\}\_\{\\text\{lim\}\}^\{\(ji\)\}\. To further quantify and compute this distributionπlim\\mathbf\{\\pi\}\_\{\\text\{lim\}\}, inspired by\(Gasteigeret al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib23)\), we find that we can solving the Personalized PageRank \(PPR\)π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 nodesvi,vjv\_\{i\},v\_\{j\}during the P phase as:

InfP​\(vi,vj\):=I​\(i,j\)∝πppr\(j​i\)=\{α​\(𝐈n−\(1−α\)​𝐀^\)−1​𝐬vi\}vj,\\textsc\{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\}\},\(4\)where𝐈n∈ℝn×n\\mathbf\{I\}\_\{n\}\\in\\mathbb\{R\}^\{n\\times n\}is the identity matrix,α∈\(0,1\]\\alpha\\in\(0,1\]is the teleport \(or restart\) probability,𝐬vi\\mathbf\{s\}\_\{v\_\{i\}\}is a one\-hot indicator vector, and\{⋅\}vj\\\{\\cdot\\\}\_\{v\_\{j\}\}means thevjv\_\{j\}\-th element of\{⋅\}\\\{\\cdot\\\}\. Detailed discussion is in App\.[A](https://arxiv.org/html/2607.00671#A1)\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/x3.png)Figure 3:Illustration of the direction of positive and negative influence during P step\. The nodes with both colors indicates the ones with both labels\.Influence between label sets\.Having computed the influence correlations magnitudeInfP​\(vi,vj\)\\textsc\{Inf\}^\{P\}\(v\_\{i\},v\_\{j\}\)between any pair of nodes during the P phase, represented as ann×nn\\times nnode influence correlations matrix, the second part involves integrating the influence from all nodes inYaY\_\{a\}\(with labelyay\_\{a\}\) on all nodes inYbY\_\{b\}\(with labelyby\_\{b\}\) to get the label influence correlation betweenyay\_\{a\}andyby\_\{b\}\. This part yields ak×kk\\times klabel influence relationship matrixInfP​\(ya,yb\)\\textsc\{Inf\}^\{P\}\(y\_\{a\},y\_\{b\}\)\. A straightforward way would be to directly sum up the node level influence\. However, as shown in our analysis in Fig\.[3](https://arxiv.org/html/2607.00671#footnote3), there are both positive and negative influences between labels\.

Therefore, we proceed to analyze the combinations of two node setsYaY\_\{a\}andYbY\_\{b\}with different labels to determine which node pairs exert positive influence and which exert negative influence\. Specifically, if a nodeviv\_\{i\}is labeled withyjy\_\{j\}, it can be seen that this node is labeled as 1 in the binary classification of whether it has the labelyjy\_\{j\}; conversely, if it does not have the labelyjy\_\{j\}, it can be seen as being labeled as 0\. Based on the Laplacian smoothing in the P operation\(Zhanget al\.,[2022a](https://arxiv.org/html/2607.00671#bib.bib85)\), the information transmitted by source nodeviv\_\{i\}labeled with 1 makes it easier for target nodesvjv\_\{j\}to be identified as labeled 1 in the same label space\. Note that we break down the discussion of the influence direction betweenYaY\_\{a\}andYbY\_\{b\}by first analyzing the influence fromYaY\_\{a\}toYbY\_\{b\}\. The reverse direction can be inferred by analogy\. Thus, we first analyze the influence fromYaY\_\{a\}toYbY\_\{b\}, where the target is the set of all nodes with labelyby\_\{b\}\. From analysis in Fig\.[3](https://arxiv.org/html/2607.00671#S4.F3), we discuss the source from the following two aspects:

- •In the label setYaY\_\{a\}, the nodes are labeled as\[1,0\]\[1,0\]\(possessingyay\_\{a\}\), it therefore has negative influence on label setYbY\_\{b\}\(\[0,1\]\[0,1\]\)\. However, the overlapping nodes are labeled as\[1,1\]\[1,1\]where the positive and negative influences to target nodes are neutralized\. ###### Definition 3\(Source of Negative InfluenceInfP−\\textsc\{Inf\}^\{P\_\{\-\}\}\)\. Vn​e​g=Ya∖\(Ya∩Yb\)→Yb,V\_\{neg\}=Y\_\{a\}\\setminus\(Y\_\{a\}\\cap Y\_\{b\}\)\\rightarrow Y\_\{b\},\(5\)where∖\\setminusmeans set difference and∩\\capmeans intersection\.
- •Intuitively, nodes with the labelyby\_\{b\}, noted as\[∗,1\]\[\*,1\], may contribute positive influence to all nodes inYbY\_\{b\}\(those with the label\[0,1\]\[0,1\]\)\. However, nodes that simultaneously have bothyay\_\{a\}andyby\_\{b\}labels \(noted as\[1,1\]\[1,1\]\) neutralize their positive and negative influences onYbY\_\{b\}\. Therefore, the source of positive influence fromYaY\_\{a\}toYbY\_\{b\}can be defined as follows: ###### Definition 4\(Source of Positive InfluenceInfP\+\\textsc\{Inf\}^\{P\_\{\+\}\}\)\. Vp​o​s=Ya¯∖Ya∪Yb¯=Ya¯∩Yb→Yb,V\_\{pos\}=\\overline\{Y\_\{a\}\}\\setminus\\overline\{Y\_\{a\}\\cup Y\_\{b\}\}=\\overline\{Y\_\{a\}\}\\cap Y\_\{b\}\\rightarrow Y\_\{b\},\(6\)where⋅¯\\overline\{\\cdot\}means complement and∪\\cupmeans union\.

Thus, by simply substitutingInfP\+\\textsc\{Inf\}^\{P\_\{\+\}\}as the index into Eq\.[4](https://arxiv.org/html/2607.00671#S4.E4)and normalizing by number of nodes, we can obtain the value of positive influence fromYaY\_\{a\}toYbY\_\{b\}; similarly, we can obtain the value of negative influence by substitutingInfP−\\textsc\{Inf\}^\{P\_\{\-\}\}\. Adding the positive and negative influence together yields the complete influence in propagation operationInfP\\textsc\{Inf\}^\{P\}between any two labels\.

### 4\.3Influences in Transformation Operation

In this section, we analyze interactions between label sets in transformation operation from message passing\. The shared GNN backbone learns from the training data through model parameters in this transformation operation\. Moreover, the direction and magnitudes of parameter updates in the shared backboneΦθ\\Phi\_\{\\theta\}is determined by each labelyiy\_\{i\}, but different labels may require different directions and magnitudes of updates to reach their own optimal solutions\. Thus, labels influence each other through parameter transformation during back propagation, which is through gradient descent\. Next, we further quantify and analyze the gradient influence exerted by different labels\.

Note that we use binary cross\-entropy losses asℒbi\\mathcal\{L\}\_\{\\text\{bi\}\}for each label individually, which can be changed to other types of binary classification loss:

ℒbi​\(𝐲,𝐲^\)=−1M​∑i=1M\[𝐲i​log⁡\(𝐲^i\)\+\(1−𝐲i\)​log⁡\(1−𝐲^i\)\],\\mathcal\{L\}\_\{\\text\{bi\}\}\(\\mathbf\{y\},\\hat\{\\mathbf\{y\}\}\)=\-\\frac\{1\}\{M\}\\sum\_\{i=1\}^\{M\}\\left\[\\mathbf\{y\}\_\{i\}\\log\(\\hat\{\\mathbf\{y\}\}\_\{i\}\)\+\(1\-\\mathbf\{y\}\_\{i\}\)\\log\(1\-\\hat\{\\mathbf\{y\}\}\_\{i\}\)\\right\],\(7\)where𝐲∈\{0,1\}\\mathbf\{y\}\\in\\\{0,1\\\}is a binary label indicating whether a node possess a certain label andMMis the number of the training nodes\.

Therefore, the binary classification lossℒbi\\mathcal\{L\}\_\{\\text\{bi\}\}of each label exerts specific gradient∇b​i\\nabla\_\{bi\}to the shared component during the transformation operation:

∇b​i=∂ℒbi∂Φθ\.\\nabla\_\{bi\}=\\frac\{\\partial\\mathcal\{L\}\_\{\\text\{bi\}\}\}\{\\partial\\Phi\_\{\\theta\}\}\.\(8\)These different gradients generated by the losses of different labels may either be mutually beneficial or mutually harmful\. Therefore, during this transformation operation, any pair of labels will influence each other through their respective gradients as shown in Fig\.[2](https://arxiv.org/html/2607.00671#S4.F2)\(b\)\.

Inspired by the definition of gradients conflicting\(Yuet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib17)\), we propose that as the angle between the gradients of two losses increases, the positive influence between the labels becomes less significant\. Conversely, the smaller the angle between the gradients generated by different labels, the smaller the negative influence they have on each other\. Accordingly, here we give a formal definition on measuring the influence in transformationTstep\.

###### Definition 5\(Tstep InfluenceInfT\\textsc\{Inf\}^\{T\}\)\.

Given two lossesLaL\_\{a\}andLbL\_\{b\}\(1≤a,b≤k1\\leq a,b\\leq k\) from labelyay\_\{a\}andyby\_\{b\}respectively, the influence in transformation operation is the accumulated differences between the gradients∇a\\nabla\_\{a\}and∇b\\nabla\_\{b\}:

InfT​\(a,b\)=InfT​\(b,a\)=−∑θAngle​\(∇a\(θ\),∇b\(θ\)\),\\textstyle\\textsc\{Inf\}^\{T\}\(a,b\)=\\textsc\{Inf\}^\{T\}\(b,a\)=\-\\sum\_\{\\theta\}\\textsc\{Angle\}\(\\nabla\_\{a\}\(\\theta\),\\nabla\_\{b\}\(\\theta\)\),\(9\)where∇a\(θ\)\\nabla\_\{a\}\(\\theta\)is the gradient of binary lossℒa\\mathcal\{L\}\_\{a\}on shared backboneΦθ\\Phi\_\{\\theta\}, andAngle​\(⋅\)\\textsc\{Angle\}\(\\cdot\)can measure the angle between directions of two gradients\. In our implementation, we determine the angle between the two gradients by calculating the cosine similarity\.

### 4\.4Influence Propagation on Label Graph

Label graph construction\.From the previous work\(Zhanget al\.,[2022a](https://arxiv.org/html/2607.00671#bib.bib85); Wuet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib36); Zhanget al\.,[2022b](https://arxiv.org/html/2607.00671#bib.bib34)\)and the above analysis, it can be seen that the influence between labels during propagation and transformation operation is independent of each other\. Therefore, the influences from these two parts can be combined through multiplication to obtain the final relationship matrix of label influence:

InfMat=InfP∗InfT,InfMat∈ℝk×k,\\textsc\{InfMat\}=\\textsc\{Inf\}^\{P\}\*\\textsc\{Inf\}^\{T\},\\quad\\textsc\{InfMat\}\\in\\mathbb\{R\}^\{k\\times k\},\(10\)where∗\*means element\-wise multiply\. Each value inInfMatreflects the relationship between each pair of labels\. However, we still need to analyze the higher\-order correlations between labels\.

Thus, we propose to build alabel graphGL​I​PG\_\{LIP\}\. Note thatInfMatcontains both positive and negative values\. Our goal is to enhance the positive influence and suppress the negative influence between labels\. Thus, we introduce a simple method yet can preserve higher\-order influence to convert theInfMatinto label graphGL​I​PG\_\{LIP\}:

###### Definition 6\.

Given the label influence matrixInfMat∈ℝk×k\\textsc\{InfMat\}\\in\\mathbb\{R\}^\{k\\times k\}, we define label graph as

GL​I​P=\(𝐕y,𝐀L​I​P\),with​𝐀L​I​P=SoftMaxrow​\(InfMat\),G\_\{LIP\}=\(\\mathbf\{V\}\_\{y\},\\mathbf\{A\}\_\{LIP\}\),\\quad\\text\{with\}\\ \\mathbf\{A\}\_\{LIP\}=\\textsc\{SoftMax\}\_\{\\text\{row\}\}\(\\textsc\{InfMat\}\),\(11\)whereSoftMaxrow​\(⋅\)\\textsc\{SoftMax\}\_\{\\text\{row\}\}\(\\cdot\)represents calculating softmax along the rows which means that we tend to treat the negative influence as weak positive influence in the higher\-order view\.𝐕y\\mathbf\{V\}\_\{y\}denotes the label nodes \(triangle nodes in Fig\.[2](https://arxiv.org/html/2607.00671#S4.F2)\(c\)\) which represent a certain label type\.𝐀L​I​P\\mathbf\{A\}\_\{LIP\}is the weighted adjacent matrix denoting the overall higher\-order correlations between all the labels\.

Overall loss function\.Intuitively, if a label is detrimental to many other labels, we suppressed it by reducing its coefficient of the loss corresponding to this label to lessen its negative impact\. Conversely, if a label is beneficial to many other labels, we encourage it by increasing the coefficient of the loss to enhance its positive impact\. Thus, we propose to quantify the importance coefficient \(score\) based on the label graphGL​I​PG\_\{LIP\}\. Since the higher\-order influence propagation take place on the graphGL​I​PG\_\{LIP\}, we turn to the computation of PageRank\(Pageet al\.,[1999](https://arxiv.org/html/2607.00671#bib.bib67)\)forGL​I​PG\_\{LIP\}\.

Formally, we calculate the importance scoreR∈\[0,1\]kR\\in\[0,1\]^\{k\}of each label node as

R=\(𝐈h−β​𝐀L​I​P\)−1​\(1−βh\)​𝟏,R=\\left\(\\mathbf\{I\}\_\{h\}\-\\beta\\mathbf\{A\}\_\{LIP\}\\right\)^\{\-1\}\\left\(\\frac\{1\-\\beta\}\{h\}\\right\)\\mathbf\{1\},\(12\)where𝐈h\\mathbf\{I\}\_\{h\}is the identity matrix,β∈\(0,1\)\\beta\\in\(0,1\)is the teleport \(or restart\) probability here,𝟏\\mathbf\{1\}is anhh\-dimensional vector in which all elements are equal to 1\.

Incorporating this importance coefficientRR, we present the overall loss function as

ℒLIP=∑j=0kRj​ℒbi​\(𝐲j^,𝐲j\),\\textstyle\\mathcal\{L\}\_\{\\textbf\{\{LIP\}\}\}=\\sum\_\{j=0\}^\{k\}R\_\{j\}\\mathcal\{L\}\_\{\\text\{bi\}\}\(\\hat\{\\mathbf\{y\}\_\{j\}\},\\mathbf\{y\}\_\{j\}\),\(13\)whereℒbi\\mathcal\{L\}\_\{\\text\{bi\}\}is from Eq\.[7](https://arxiv.org/html/2607.00671#S4.E7)which can be changed to other imbalanced classification loss\(Chenet al\.,[2024b](https://arxiv.org/html/2607.00671#bib.bib98); Zhuoet al\.,[2024](https://arxiv.org/html/2607.00671#bib.bib99)\)\.

## 5Experiments

In this section, we evaluateLIPand aim to answer the following research questions:

- •RQ1\.How doesLIPperform on MLNC task with different settings and label ratios?
- •RQ2\.CanLIPserve as a plug\-and\-play booster to be equipped with any backbone?
- •RQ3\.How reliable are the label influence relationships we proposed to capture?

### 5\.1Experimental Settings

To comprehensively validate our framework, we conduct experiments on 2 classical MLNC datasets \(DBLP\(Akujuobiet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib49)\), BlogCat\(Shiet al\.,[2020a](https://arxiv.org/html/2607.00671#bib.bib47)\)\), 1 large scale OGB dataset \(Ogbn\-proteins\(Huet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib16)\), OGB\-p in short\), and 3 new biological datasets \(PCG, HumLoc, EukLoc\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)\) from different domains\. The statistics of datasets are in App\.[D](https://arxiv.org/html/2607.00671#A4)\. We use three types of baselines for comparison\. First, we combine unsupervised embedding and multi\-label classifier\. We adopt the frequently used unsupervised graph embedding methods Node2Vec\(Grover and Leskovec,[2016](https://arxiv.org/html/2607.00671#bib.bib66)\), the classic multi\-label classifiers binary relevance \(BR\)\(Tsoumakaset al\.,[2010](https://arxiv.org/html/2607.00671#bib.bib53)\)and classifier chain \(CC\)\(Readet al\.,[2009](https://arxiv.org/html/2607.00671#bib.bib55)\)\. Second, we combine semi\-supervised backbone with SOTA multi\-label methods\. We adopt the same backbone for baselines and our own for fairness\. We choose GCN\(Kipf and Welling,[2017](https://arxiv.org/html/2607.00671#bib.bib65)\)as main backbone, ML\-KNN\(Zhang and Zhou,[2007](https://arxiv.org/html/2607.00671#bib.bib56)\)and latest work PLAIN\(Wanget al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib57)\)as multi\-label methods\. The third group is backbone\-relevant methods which specifically designed for MLNC on graphs\. We choose MLGW\(Akujuobiet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib49)\), ML\-GCN\(Gaoet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib50)\), LARN\(Xiaoet al\.,[2022](https://arxiv.org/html/2607.00671#bib.bib45)\), LANC\(Zhouet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib44)\)and the latest work VariMul\(Songet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib46)\)\. Furthermore, “backbone\+Auto” means the coefficients of losses of different labels are learned automatically\. More details are in App\.[E\.1](https://arxiv.org/html/2607.00671#A5.SS1)\.

Table 1:Performance \(mean ± std\. deviation\) under node split at 6:2:2 in terms of Macro AUC, AP\.
### 5\.2Comparison with Baselines

To answerRQ1, we evaluateLIPagainst various kinds of baselines on classic and latest benchmark datasets, ranging from multi\-label techniques used on any data form to methods tailored for MLNC on graphs\. To fully evaluate the effectiveness against baselines, we adopt 2 split settings: node split and label split\. Refer to App\.[E\.1](https://arxiv.org/html/2607.00671#A5.SS1)to see the details and differences between them\. We also evaluate under different training ratio \(App\.[E\.2](https://arxiv.org/html/2607.00671#A5.SS2)\)\.

From Tab\.[1](https://arxiv.org/html/2607.00671#S5.T1), we can draw several conclusions\. First and foremost,LIPis the most effective one most of the time, which verifies the effectiveness of our approach\. Our method outperforms other baselines by 3\.06% on AUC and 2\.54% on AUC on average\. Note that our methods can boost the performance based on the backbones\. Second, we find that while other methods including VariMul, LARN, and PLAIN achieve good results, methods tailored for MLNC on graph data always outperform those designed for all data form\. The reason is that integrating multi\-label processing into the encoding of graph structure and node features makes the node embeddings more informative, while methods that separate node encoding from multi\-label correlation mining struggle to achieve optimal results\. Third, the methods using unsupervised node embedding perform even worse since there is no label information when representing the nodes\. Although methods like “backbone\+Auto”, which automatically learn loss coefficients, appear more flexible, setting these coefficients solely based on the loss is like searching for a needle in a haystack, making it difficult to amplify the loss of beneficial labels during the learning process\. On one hand, our method better explores the relevant impact of the nodes contained by labels from the perspectives of both message passing and gradient update; on the other hand, during the training process, our method is also constantly related to the current state of the model\. This enables our approach to dynamically mine the relationships of nodes with different labels in the process of forward and backward information transmission, thereby making the model more effective\.

### 5\.3Comparison with Different Backbones

One of the advantages ofLIPis the ability of being plugged into any node embedding methods\. Thus, to answerRQ2, we propose to change the backbone to others with different inductive bias\. Here we compare our method with the “Com”, which directly sums the multi\-label loss to train the model\. We also change backbones on more datasets in App\.[E\.2](https://arxiv.org/html/2607.00671#A5.SS2)\. Since some of the datasets are heterophily graphs \(see Tab\.[4](https://arxiv.org/html/2607.00671#A4.T4)\), we use backbones designed for homophily and heterophily graphs\.

Results\.We change backbones on BlogCat dataset in Fig\.[4](https://arxiv.org/html/2607.00671#S5.F4)\(a\)\. We can see thatLIPconstantly achieves large improvement when applied to any backbone, demonstrating the effectiveness of our approach\. Although BlogCat is a heterophily graph, H2GCN does not perform well comparing to others\. Similar results can be found in\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)\. However, H2GCN perform best on Abnormal as a heterophily graph in App\.[E\.2](https://arxiv.org/html/2607.00671#A5.SS2)\. We believe there are two reasons for this\. First, BlogCat has no node features, so we used Node2Vec as feature for all methods, making the input of backbone actually a homogeneous graph from a feature perspective\. However, H2GCN’s strategy of aggregating more neighbor features makes it harder for nodes to learn the labels\. Second, the heterophily here is calculated from multi\-label, but H2GCN is designed for single\-label, so it may not perform better\. An interesting observation is that different backbone models exhibit varying degrees of sensitivity to our method\. For instance, GCN show greater improvements before and after the application of our method compared to GAT\. We think that this may be due to our method’s relation to gradient calculation, with different models having varying sensitivities to labels\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/x4.png)Figure 4:Model Analysis showing the effectiveness ofLIP\.
### 5\.4Discussion on Label Correlations

To answer theRQ3, we evaluate the label influence correlation mined byLIP\. First, we decompose the proposed two parts of influence correlations to evaluate effectiveness of each correlation separately\. Then, we compare our method with other commonly used approaches for explicitly computing correlations to see which more accurately reflects the influence correlations between labels\.

Ablation study on correlations\.The “Only P”, “Only T” and “All” means usingInfP\\textsc\{Inf\}^\{P\},InfT\\textsc\{Inf\}^\{T\}andInfMatrespectively, where GCN is the backbone\. As shown in Fig\.[4](https://arxiv.org/html/2607.00671#S5.F4)\(b\), the performance using the wholeInfMatis the best, which prove the utility of the combination of the influence during both forward and backward propagation\. Moreover, we find thatInfP\\textsc\{Inf\}^\{P\}perform better thanInfT\\textsc\{Inf\}^\{T\}on EukLoc while the other way around on DBLP\. We believe the reason is that EukLoc is more heterophilic, making it more dependent on global graph structure\. OurInfP\\textsc\{Inf\}^\{P\}focuses on uncovering influence during the propagation process, which emphasizes the structural aspects more during training compared toInfT\\textsc\{Inf\}^\{T\}\. More ablation study on normalization is in App\.[E\.2](https://arxiv.org/html/2607.00671#A5.SS2)\.

Compare with other label correlations\.Here, we can verify if our captured label correlation align with expectations\. Specifically, we aim to capture the pairwise label correlations similar as shown in Fig\.[3](https://arxiv.org/html/2607.00671#footnote3), which contain positive and negative correlations\. Note that we cannot use this performance differences as the label correlations in the model, as retraining the performance to calculate them are not possible\. Therefore, we compare which method can obtain the relationship matrix that most closely matches the influence relationships inferred from the results\. Here we collect all methods used for explicitly calculating multi\-label correlations: co\-occurrence from\(Wanget al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib57)\)and cosine similarity of label embeddings from\(Xuet al\.,[2018b](https://arxiv.org/html/2607.00671#bib.bib21)\)\. We calculate thel2\-norm difference between the three methods we compare and the influence correlations as epochs increase \(with GCN backbone on DBLP\)\. As shown in Fig\.[4](https://arxiv.org/html/2607.00671#S5.F4)\(c\), althoughInfMatchanges over epochs, the difference betweenInfMatand ground truth correlation is the closest\. Moreover, it can be observed that the label co\-occurrence measurement is closer compared to the cosine similarity of labels\. Additionally, for a significant portion of epochs, the distance relative to ground truth does not change much, not because the influence we measure is static, but because the influence between different pairs of labels waxes and wanes, yet always remains close to the ground truth\. Due to space limit, we place the results of other experiments in the App\.[E](https://arxiv.org/html/2607.00671#A5)\.

## 6Conclusions

In this paper, we address the challenges of the valuable but overlooked MLNC task by introducing a novel approach to understanding and leveraging label influence correlations on graphs\. By decomposing the influences between labels in message passing mechanism, we provide insights on analyzing and quantifying label influences during the learning process\. Our proposed method,LIP, boosts the MLNC by ensuring that positive label influences are amplified while mitigating the negative ones\. Empirical results across comprehensive MLNC datasets demonstrate the effectiveness ofLIP, achieving consistent improvements in various metrics\.

#### Acknowledgments

This research is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority under its Trust Tech Funding Initiative, and the National Research Foundation, Singapore under its AI Singapore Programme \(AISG Award No: AISG2\-TC\-2021\-002\)\. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author\(s\) and do not reflect the views of National Research Foundation, Singapore and Infocomm Media Development Authority\. This work is also supported by NSFC \(No\. 62322606, No\. 62441605\), Zhejiang NSF \(LR22F020005\), and CCF\-Zhipu Large Model Fund\.

## References

- U\. Akujuobi, H\. Yufei, Q\. Zhang, and X\. Zhang \(2019\)Collaborative graph walk for semi\-supervised multi\-label node classification\.In2019 IEEE International Conference on Data Mining \(ICDM\),Vol\.,pp\. 1–10\.External Links:[Document](https://dx.doi.org/10.1109/ICDM.2019.00010)Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p1.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- Y\. Bei, W\. Chen, H\. Chen, S\. Zhou, C\. Yang, J\. Fan, L\. Huang, and J\. Bu \(2024\)Correlation\-aware graph convolutional networks for multi\-label node classification\.arXiv preprint arXiv:2411\.17350\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p1.1)\.
- D\. Chen, Y\. Lin, G\. Zhao, X\. Ren, P\. Li, J\. Zhou, and X\. Sun \(2021\)Topology\-imbalance learning for semi\-supervised node classification\.Advances in Neural Information Processing Systems34,pp\. 29885–29897\.Cited by:[Theorem 1](https://arxiv.org/html/2607.00671#Thmtheorem1.p1.1.1)\.
- J\. Chen, B\. Li, and K\. He \(2024a\)Neighborhood convolutional graph neural network\.Knowledge\-Based Systems295,pp\. 111861\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- N\. Chen, Z\. Liu, B\. Hooi, B\. He, R\. Fathony, J\. Hu, and J\. Chen \(2024b\)Consistency training with learnable data augmentation for graph anomaly detection with limited supervision\.InThe Twelfth International Conference on Learning Representations,Cited by:[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p5.2)\.
- Y\. Cheng, C\. Shan, Y\. Shen, X\. Li, S\. Luo, and D\. Li \(2024\)Resurrecting label propagation for graphs with heterophily and label noise\.InProceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 433–444\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- E\. Chien, J\. Peng, P\. Li, and O\. Milenkovic \(2020\)Adaptive universal generalized pagerank graph neural network\.arXiv preprint arXiv:2006\.07988\.Cited by:[§E\.3](https://arxiv.org/html/2607.00671#A5.SS3.p2.1),[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- H\. Dong, J\. Chen, F\. Feng, X\. He, S\. Bi, Z\. Ding, and P\. Cui \(2021\)On the equivalence of decoupled graph convolution network and label propagation\.InProceedings of the Web Conference 2021,pp\. 3651–3662\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- T\. Fang, W\. Zhou, Y\. Sun, K\. Han, L\. Ma, and Y\. Yang \(2024\)Exploring correlations of self\-supervised tasks for graphs\.InInternational Conference on Machine Learning,Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p1.1)\.
- J\. Fürnkranz, E\. Hüllermeier, E\. Loza Mencía, and K\. Brinker \(2008\)Multilabel classification via calibrated label ranking\.Machine learning73,pp\. 133–153\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1)\.
- K\. Gao, J\. Zhang, and C\. Zhou \(2019\)Semi\-supervised graph embedding for multi\-label graph node classification\.External Links:1907\.05743Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p2.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- J\. Gasteiger, A\. Bojchevski, and S\. Günnemann \(2019\)Predict then propagate: graph neural networks meet personalized pagerank\.ICLR\.Cited by:[Appendix A](https://arxiv.org/html/2607.00671#A1.3.p3.3),[§E\.3](https://arxiv.org/html/2607.00671#A5.SS3.p2.1),[§E\.5](https://arxiv.org/html/2607.00671#A5.SS5.p1.6),[§2](https://arxiv.org/html/2607.00671#S2.p2.1),[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p2.25),[Theorem 1](https://arxiv.org/html/2607.00671#Thmtheorem1.p1.1.1)\.
- A\. Grover and J\. Leskovec \(2016\)Node2vec: scalable feature learning for networks\.InProceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 855–864\.Cited by:[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- W\. L\. Hamilton, R\. Ying, and J\. Leskovec \(2017\)Inductive representation learning on large graphs\.InNIPS,Vol\.30,pp\. 1025–1035\.Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p5.1),[§3\.2](https://arxiv.org/html/2607.00671#S3.SS2.p1.7)\.
- X\. He, K\. Deng, X\. Wang, Y\. Li, Y\. Zhang, and M\. Wang \(2020\)Lightgcn: simplifying and powering graph convolution network for recommendation\.InProceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval,pp\. 639–648\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec \(2020\)Open graph benchmark: datasets for machine learning on graphs\.Advances in neural information processing systems33,pp\. 22118–22133\.Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p1.1),[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1),[§1](https://arxiv.org/html/2607.00671#S1.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- Q\. Huang, H\. He, A\. Singh, S\. Lim, and A\. R\. Benson \(2020\)Combining label propagation and simple models out\-performs graph neural networks\.External Links:2010\.13993Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- B\. Jiang, Z\. Zhang, D\. Lin, J\. Tang, and B\. Luo \(2019\)Semi\-supervised learning with graph learning\-convolutional networks\.2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\),pp\. 11305–11312\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p1.1)\.
- T\. N\. Kipf and M\. Welling \(2016\)Variational graph auto\-encoders\.InArXiv,Vol\.abs/1611\.07308\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p1.1)\.
- T\. N\. Kipf and M\. Welling \(2017\)Semi\-supervised classification with graph convolutional networks\.External Links:1609\.02907Cited by:[Appendix A](https://arxiv.org/html/2607.00671#A1.1.p1.6),[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p5.1),[§3\.2](https://arxiv.org/html/2607.00671#S3.SS2.p1.7),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- J\. Lafferty, A\. McCallum, F\. Pereira,et al\.\(2001\)Conditional random fields: probabilistic models for segmenting and labeling sequence data\.InIcml,Vol\.1,pp\. 3\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- H\. Li, Z\. Chen, Z\. Li, Q\. Zheng, P\. Zhang, and S\. Zhou \(2023\)GIPA: a general information propagation algorithm for graph learning\.InInternational Conference on Database Systems for Advanced Applications,pp\. 465–476\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p2.1)\.
- M\. Liu, H\. Gao, and S\. Ji \(2020\)Towards deeper graph neural networks\.InProceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining,pp\. 338–348\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- Z\. Liu, Y\. Li, N\. Chen, Q\. Wang, B\. Hooi, and B\. He \(2023\)A survey of imbalanced learning on graphs: problems, techniques, and future directions\.arXiv preprint arXiv:2308\.13821\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p1.1)\.
- R\. M\. Neal and G\. E\. Hinton \(1998\)A view of the em algorithm that justifies incremental, sparse, and other variants\.InLearning in graphical models,pp\. 355–368\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- L\. Page, S\. Brin, R\. Motwani, and T\. Winograd \(1999\)The pagerank citation ranking : bringing order to the web\.InThe Web Conference,External Links:[Link](https://api.semanticscholar.org/CorpusID:1508503)Cited by:[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p3.3)\.
- B\. Perozzi, R\. Al\-Rfou, and S\. Skiena \(2014\)DeepWalk: online learning of social representations\.InProceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,KDD ’14\.External Links:[Link](http://dx.doi.org/10.1145/2623330.2623732),[Document](https://dx.doi.org/10.1145/2623330.2623732)Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p2.1)\.
- J\. Qiu, Q\. Chen, Y\. Dong, J\. Zhang, H\. Yang, M\. Ding, K\. Wang, and J\. Tang \(2020\)GCC: graph contrastive coding for graph neural network pre\-training\.arXiv preprint arXiv:2006\.09963\.Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p2.1)\.
- M\. Qu, Y\. Bengio, and J\. Tang \(2019\)Gmnn: graph markov neural networks\.InInternational conference on machine learning,pp\. 5241–5250\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- J\. Read, B\. Pfahringer, G\. Holmes, and E\. Frank \(2009\)Classifier chains for multi\-label classification\.InMachine Learning and Knowledge Discovery in Databases,W\. Buntine, M\. Grobelnik, D\. Mladenić, and J\. Shawe\-Taylor \(Eds\.\),Berlin, Heidelberg,pp\. 254–269\.External Links:ISBN 978\-3\-642\-04174\-7Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- M\. Shi, Y\. Tang, and X\. Zhu \(2020a\)MLNE: multi\-label network embedding\.IEEE Transactions on Neural Networks and Learning Systems31\(9\),pp\. 3682–3695\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2019.2945869)Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p1.1),[§1](https://arxiv.org/html/2607.00671#S1.p2.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- Y\. Shi, Z\. Huang, S\. Feng, H\. Zhong, W\. Wang, and Y\. Sun \(2020b\)Masked label prediction: unified message passing model for semi\-supervised classification\.arXiv preprint arXiv:2009\.03509\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p2.1)\.
- C\. Si, Y\. Jia, R\. Wang, M\. Zhang, Y\. Feng, and Q\. Chongxiao \(2023\)Multi\-label classification with high\-rank and high\-order label correlations\.IEEE Transactions on Knowledge and Data Engineering\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1)\.
- Z\. Song, Z\. Meng, Y\. Zhang, and I\. King \(2021\)Semi\-supervised multi\-label learning for graph\-structured data\.InProceedings of the 30th ACM International Conference on Information & Knowledge Management,CIKM ’21,New York, NY, USA,pp\. 1723–1733\.External Links:ISBN 9781450384469,[Link](https://doi.org/10.1145/3459637.3482391),[Document](https://dx.doi.org/10.1145/3459637.3482391)Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- Y\. Sun, H\. Deng, Y\. Yang, C\. Wang, J\. Xu, R\. Huang, L\. Cao, Y\. Wang, and L\. Chen \(2022\)Beyond homophily: structure\-aware path aggregation graph neural network\.InProceedings of the Thirty\-First International Joint Conference on Artificial Intelligence, IJCAI\-22,L\. D\. Raedt \(Ed\.\),pp\. 2233–2240\.Note:Main TrackExternal Links:[Document](https://dx.doi.org/10.24963/ijcai.2022/310),[Link](https://doi.org/10.24963/ijcai.2022/310)Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1)\.
- Y\. Sun, Y\. Yang, X\. Feng, Z\. Wang, H\. Zhong, C\. Wang, and L\. Chen \(2025\)Handling feature heterogeneity with learnable graph patches\.InProceedings of the 31th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1)\.
- Y\. Sun, Q\. Zhu, Y\. Yang, C\. Wang, T\. Fan, J\. Zhu, and L\. Chen \(2024\)Fine\-tuning graph neural networks by preserving graph generative patterns\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 9053–9061\.Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1)\.
- J\. Tang, F\. Hua, Z\. Gao, P\. Zhao, and J\. Li \(2023\)GADBench: revisiting and benchmarking supervised graph anomaly detection\.InAdvances in Neural Information Processing Systems,Vol\.36,pp\. 29628–29653\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2023/file/5eaafd67434a4cfb1cf829722c65f184-Paper-Datasets_and_Benchmarks.pdf)Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1)\.
- G\. Tsoumakas, I\. M\. Katakis, and I\. P\. Vlahavas \(2010\)Mining multi\-label data\.InData Mining and Knowledge Discovery Handbook,External Links:[Link](https://api.semanticscholar.org/CorpusID:22998)Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Lio, and Y\. Bengio \(2017\)Graph attention networks\.arXiv preprint arXiv:1710\.10903\.Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p5.1)\.
- P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. Bengio \(2018\)Graph attention networks\.InICLR,Cited by:[§3\.2](https://arxiv.org/html/2607.00671#S3.SS2.p1.7)\.
- H\. Wang, S\. Yang, G\. Lyu, W\. Liu, T\. Hu, K\. Chen, S\. Feng, and G\. Chen \(2023\)Deep partial multi\-label learning with graph disambiguation\.External Links:2305\.05882Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1),[§5\.4](https://arxiv.org/html/2607.00671#S5.SS4.p3.2)\.
- H\. Wang and J\. Leskovec \(2020\)Unifying graph convolutional neural networks and label propagation\.arXiv preprint arXiv:2002\.06755\.Cited by:[Appendix A](https://arxiv.org/html/2607.00671#A1.p1.1),[§1](https://arxiv.org/html/2607.00671#S1.p5.1),[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p2.18)\.
- H\. Wang and J\. Leskovec \(2021\)Combining graph convolutional neural networks and label propagation\.ACM Transactions on Information Systems \(TOIS\)40\(4\),pp\. 1–27\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- F\. Wu, A\. Souza, T\. Zhang, C\. Fifty, T\. Yu, and K\. Weinberger \(2019\)Simplifying graph convolutional networks\.InInternational conference on machine learning,pp\. 6861–6871\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p2.1),[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p1.3)\.
- Z\. Wu, S\. Pan, F\. Chen, G\. Long, C\. Zhang, and S\. Y\. Philip \(2020\)A comprehensive survey on graph neural networks\.IEEE transactions on neural networks and learning systems32\(1\),pp\. 4–24\.Cited by:[§4\.1](https://arxiv.org/html/2607.00671#S4.SS1.p2.1)\.
- J\. Xia, H\. Lin, Y\. Xu, L\. Wu, Z\. Gao, S\. Li, and S\. Z\. Li \(2021\)Towards robust graph neural networks against label noise\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p2.1)\.
- L\. Xiao, P\. Xu, L\. Jing, U\. Akujuobi, and X\. Zhang \(2022\)Semantic guide for semi\-supervised few\-shot multi\-label node classification\.Information Sciences591,pp\. 235–250\.External Links:ISSN 0020\-0255,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.ins.2021.12.130),[Link](https://www.sciencedirect.com/science/article/pii/S0020025522000111)Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p2.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- K\. Xu, C\. Li, Y\. Tian, T\. Sonobe, K\. Kawarabayashi, and S\. Jegelka \(2018a\)Representation learning on graphs with jumping knowledge networks\.InInternational conference on machine learning,pp\. 5453–5462\.Cited by:[Appendix A](https://arxiv.org/html/2607.00671#A1.p1.1),[§1](https://arxiv.org/html/2607.00671#S1.p5.1),[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p2.18),[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p2.25)\.
- Y\. Xu, J\. Wang, S\. An, J\. Wei, and J\. Ruan \(2018b\)Semi\-supervised multi\-label feature selection by preserving feature\-label space consistency\.InProceedings of the 27th ACM international conference on information and knowledge management,pp\. 783–792\.Cited by:[§5\.4](https://arxiv.org/html/2607.00671#S5.SS4.p3.2)\.
- Y\. Yang, R\. N\. Lichtenwalter, and N\. V\. Chawla \(2015\)Evaluating link prediction methods\.Knowledge and Information Systems45,pp\. 751–782\.Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1)\.
- R\. Ying, R\. He, K\. Chen, P\. Eksombatchai, W\. L\. Hamilton, and J\. Leskovec \(2018\)Graph convolutional neural networks for web\-scale recommender systems\.InSIGKDD,pp\. 974–983\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p1.1)\.
- T\. Yu, S\. Kumar, A\. Gupta, S\. Levine, K\. Hausman, and C\. Finn \(2020\)Gradient surgery for multi\-task learning\.Advances in Neural Information Processing Systems33,pp\. 5824–5836\.Cited by:[§4\.3](https://arxiv.org/html/2607.00671#S4.SS3.p4.1)\.
- M\. Zhang and K\. Zhang \(2010\)Multi\-label learning by exploiting label dependency\.InProceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining,pp\. 999–1008\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1)\.
- M\. Zhang and Z\. Zhou \(2007\)ML\-knn: a lazy learning approach to multi\-label learning\.Pattern Recogn\.40\(7\),pp\. 2038–2048\.External Links:ISSN 0031\-3203,[Link](https://doi.org/10.1016/j.patcog.2006.12.019),[Document](https://dx.doi.org/10.1016/j.patcog.2006.12.019)Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- M\. Zhang and Z\. Zhou \(2013\)A review on multi\-label learning algorithms\.IEEE transactions on knowledge and data engineering26\(8\),pp\. 1819–1837\.Cited by:[§3\.2](https://arxiv.org/html/2607.00671#S3.SS2.p1.5)\.
- W\. Zhang, Z\. Sheng, Z\. Yin, Y\. Jiang, Y\. Xia, J\. Gao, Z\. Yang, and B\. Cui \(2022a\)Model degradation hinders deep graph neural networks\.InProceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining,pp\. 2493–2503\.Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p5.1),[§2](https://arxiv.org/html/2607.00671#S2.p2.1),[§4\.1](https://arxiv.org/html/2607.00671#S4.SS1.p2.1),[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p5.15),[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p1.3)\.
- W\. Zhang, M\. Yang, Z\. Sheng, Y\. Li, W\. Ouyang, Y\. Tao, Z\. Yang, and B\. Cui \(2021a\)Node dependent local smoothing for scalable graph learning\.Advances in Neural Information Processing Systems34,pp\. 20321–20332\.Cited by:[§4\.2](https://arxiv.org/html/2607.00671#S4.SS2.p2.18)\.
- W\. Zhang, Z\. Yin, Z\. Sheng, Y\. Li, W\. Ouyang, X\. Li, Y\. Tao, Z\. Yang, and B\. Cui \(2022b\)Graph attention multi\-layer perceptron\.InProceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining,pp\. 4560–4570\.Cited by:[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p1.3)\.
- X\. Zhang, Q\. Zhang, Z\. Yan, R\. Liu, and Y\. Cao \(2021b\)Enhancing label correlation feedback in multi\-label text classification via multi\-task learning\.arXiv preprint arXiv:2106\.03103\.Cited by:[Appendix C](https://arxiv.org/html/2607.00671#A3.p1.1)\.
- T\. Zhao, T\. N\. Dong, A\. Hanjalic, and M\. Khosla \(2023\)Multi\-label node classification on graph\-structured data\.Transactions on Machine Learning Research\.Note:External Links:ISSN 2835\-8856,[Link](https://openreview.net/forum?id=EZhkV2BjDP)Cited by:[Appendix D](https://arxiv.org/html/2607.00671#A4.p1.1),[Appendix D](https://arxiv.org/html/2607.00671#A4.p2.1),[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p2.1),[§1](https://arxiv.org/html/2607.00671#S1.p6.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1),[§5\.3](https://arxiv.org/html/2607.00671#S5.SS3.p2.1)\.
- T\. Zhao and M\. Khosla \(2024\)GNN\-multifix: addressing the pitfalls for gnns for multi\-label node classification\.arXiv preprint arXiv:2411\.14094\.Cited by:[§2](https://arxiv.org/html/2607.00671#S2.p1.1)\.
- C\. Zhou, H\. Chen, J\. Zhang, Q\. Li, D\. Hu, and V\. S\. Sheng \(2021\)Multi\-label graph node classification with label attentive neighborhood convolution\.Expert Systems with Applications180,pp\. 115063\.External Links:ISSN 0957\-4174,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.eswa.2021.115063),[Link](https://www.sciencedirect.com/science/article/pii/S0957417421005042)Cited by:[§1](https://arxiv.org/html/2607.00671#S1.p2.1),[§2](https://arxiv.org/html/2607.00671#S2.p1.1),[§5\.1](https://arxiv.org/html/2607.00671#S5.SS1.p1.1)\.
- J\. Zhu, Y\. Yan, L\. Zhao, M\. Heimann, L\. Akoglu, and D\. Koutra \(2020\)Beyond homophily in graph neural networks: current limitations and effective designs\.Advances in neural information processing systems33,pp\. 7793–7804\.Cited by:[§E\.1](https://arxiv.org/html/2607.00671#A5.SS1.p5.1)\.
- W\. Zhuo, Z\. Liu, B\. Hooi, B\. He, G\. Tan, R\. Fathony, and J\. Chen \(2024\)Partitioning message passing for graph fraud detection\.InThe Twelfth International Conference on Learning Representations,Cited by:[§4\.4](https://arxiv.org/html/2607.00671#S4.SS4.p5.2)\.

## Appendix

## Appendix ADiscussions on Influence from Propagation

This section aims to supplement Sec[4\.2](https://arxiv.org/html/2607.00671#S4.SS2)regarding the pair wise influence value from propagation \(Poperation\)\. Specifically, inspired by previous work\(Xuet al\.,[2018a](https://arxiv.org/html/2607.00671#bib.bib22); Wang and Leskovec,[2020](https://arxiv.org/html/2607.00671#bib.bib19)\), we prove the correctness of the calculation method on influence value between nodes with different labels in propagation operation\.

###### Theorem 1\(Influence Value in Propagation\)\.

During the propagation phase in message passing, the influence value between two nodes with different labels is equivalent, in expectation, to the transition probability between them as calculated by Personalized PageRank \(PPR\)\(Gasteigeret al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib23); Chenet al\.,[2021](https://arxiv.org/html/2607.00671#bib.bib68)\)\. Namely, the influence value betweenvi,vjv\_\{i\},v\_\{j\}is

InfP​\(vi,vj\)=\{α​\(In−\(1−α\)​𝐀^\)−1​svi\}vj∝I​\(i,j\),\\displaystyle\\textsc\{Inf\}^\{P\}\(v\_\{i\},v\_\{j\}\)=\\\{\\alpha\(I\_\{n\}\-\(1\-\\alpha\)\\hat\{\\mathbf\{A\}\}\)^\{\-1\}s\_\{v\_\{i\}\}\\\}\_\{v\_\{j\}\}\\propto I\(i,j\),\(14\)where𝐈n∈ℝn×n\\mathbf\{I\}\_\{n\}\\in\\mathbb\{R\}^\{n\\times n\}is the identity matrix,α∈\(0,1\]\\alpha\\in\(0,1\]is the teleport \(or restart\) probability,𝐬vi\\mathbf\{s\}\_\{v\_\{i\}\}is a one\-hot indicator vector and\{⋅\}vj\\\{\\cdot\\\}\_\{v\_\{j\}\}means thevjv\_\{j\}\-th element of\{⋅\}\\\{\\cdot\\\}\.

###### Proof\.

We usekklayers of GCNKipf and Welling \([2017](https://arxiv.org/html/2607.00671#bib.bib65)\)as backboneΦθ\\Phi\_\{\\theta\}for analysis\. We first prove the the influence value betweenvi,vjv\_\{i\},v\_\{j\}with different labels is equivalent, in expectation, to thekk\-step random walk distribution on graphGGstarting at nodeviv\_\{i\}\.

From the definition of influence fromviv\_\{i\}tovjv\_\{j\}in Eq\.[3](https://arxiv.org/html/2607.00671#S4.E3), we proceed with the detailed calculations:

I​\(vi,vj\)=∂zj\(k\)∂zi\(0\)=1deg⁡\(vi\)~⋅diag⁡\(1fvi\(k\)\>0\)⋅Wk⋅∑z∈N~​\(vi\)∂zj\(k−1\)∂zi\(0\),\\displaystyle\\begin\{aligned\} \\textstyle I\(v\_\{i\},v\_\{j\}\)=&\\frac\{\\partial z\_\{j\}^\{\(k\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}=&\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\(v\_\{i\}\)\}\}\\cdot\\operatorname\{diag\}\\left\(1\_\{f\_\{v\_\{i\}\}^\{\(k\)\}\>0\}\\right\)\\cdot W\_\{k\}\\cdot\\sum\_\{z\\in\\widetilde\{N\}\(v\_\{i\}\)\}\\frac\{\\partial z\_\{j\}^\{\(k\-1\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\},\\end\{aligned\}\(15\)wherefvi\(k\)f\_\{v\_\{i\}\}^\{\(k\)\}is the pre\-activated embedding ofzj\(k\)z\_\{j\}^\{\(k\)\},WkW\_\{k\}stands for the last layer weight matrix of GCN\. Furthermore, we use chain rule to calculate any rankllof the derivative as

∂zj\(l\)∂zi\(0\)=∑p=1λ\[∂zj\(l\)∂zi\(0\)\]p=∑p=1λ∏m=l11deg⁡\(vpm\)~⋅diag⁡\(1fvpm\(m\)\>0\)⋅Wm,\\displaystyle\\begin\{aligned\} \\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}=&\\sum\_\{p=1\}^\{\\lambda\}\\left\[\\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}\\right\]\_\{p\}=&\\sum\_\{p=1\}^\{\\lambda\}\\prod\_\{m=l\}^\{1\}\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\\left\(v\_\{p\}^\{m\}\\right\)\}\}\\cdot\\operatorname\{diag\}\\left\(1\_\{f\_\{v\_\{p\}^\{m\}\}^\{\(m\)\}\>0\}\\right\)\\cdot W\_\{m\},\\end\{aligned\}\(16\)whereλ\\lambdais the total number of paths of lengthl\+1l\+1from nodevjv\_\{j\}toviv\_\{i\}\. For certain pathpp,vpmv\_\{p\}^\{m\}is nodeviv\_\{i\},vp0v\_\{p\}^\{0\}is nodevjv\_\{j\}and form=1​…​\(l−1\)m=1\.\.\.\(l\-1\),vp\(k−1\)∈N~\(vpm\)v\_\{p\}^\{\(\}k\-1\)\\in\\widetilde\{N\}\(v\_\{p\}^\{m\}\)\. More specifically, we can calculate an entry of the derivative as

\[∂zj\(l\)∂zi\(0\)\]p\(a,b\)=∏l=k11deg~​\(vpm\)​∑q=1γRq​∏m=l1wq\(m\),\\displaystyle\\begin\{aligned\} \\left\[\\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}\\right\]\_\{p\}^\{\(a,b\)\}=\\prod\_\{l=k\}^\{1\}\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\}\\left\(v\_\{p\}^\{m\}\\right\)\}\\sum\_\{q=1\}^\{\\gamma\}R\_\{q\}\\prod\_\{m=l\}^\{1\}w\_\{q\}^\{\(m\)\},\\end\{aligned\}\(17\)whereγ\\gammais the number of pathsqqfrom theaatobbin the computation directed acyclic graph \(DAG\) of\[∂zj\(l\)∂zi\(0\)\]p\\left\[\\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}\\right\]\_\{p\}\. For each layermm,wq\(m\)w\_\{q\}^\{\(m\)\}is the entry ofWmW\_\{m\}which is used in theqq\-th path\.Rq∈0,1R\_\{q\}\\in\{0,1\}denote whether theqq\-th path is active or not as the result of ReLU activation of entries offvpm\(m\)f\_\{v\_\{p\}^\{m\}\}^\{\(m\)\}’s on theqq\-th path\. Since the variableRRfollows a Bernoulli distribution, for allqq,P​r​\(Rq=1\)=ρPr\(R\_\{q\}=1\)=\\rho, we have

𝔼​\[\[∂zj\(l\)∂zi\(0\)\]p\]=ρ⋅∏m=l11deg⁡\(vpm\)~⋅wq\(m\)\.\\mathbb\{E\}\\left\[\\left\[\\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}\\right\]\_\{p\}\\right\]=\\rho\\cdot\\prod\_\{m=l\}^\{1\}\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\\left\(v\_\{p\}^\{m\}\\right\)\}\}\\cdot w\_\{q\}^\{\(m\)\}\.\(18\)Thus, we know that

𝔼​\[∂zj\(l\)∂zi\(0\)\]=ρ⋅∏m=l1Wm⋅\(∑p=1λ∏m=l11deg⁡\(vpm\)~\)\.\\mathbb\{E\}\\left\[\\frac\{\\partial z\_\{j\}^\{\(l\)\}\}\{\\partial z\_\{i\}^\{\(0\)\}\}\\right\]=\\rho\\cdot\\prod\_\{m=l\}^\{1\}W\_\{m\}\\cdot\\left\(\\sum\_\{p=1\}^\{\\lambda\}\\prod\_\{m=l\}^\{1\}\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\\left\(v\_\{p\}^\{m\}\\right\)\}\}\\right\)\.\(19\)On the other hand,kk\-step random walk probability atviv\_\{i\}can be calculated by summing up the probability of all paths of lengthkkfromviv\_\{i\}tovjv\_\{j\}, which is exactly∑p=1λ∏m=l11deg⁡\(vpm\)~\\sum\_\{p=1\}^\{\\lambda\}\\prod\_\{m=l\}^\{1\}\\frac\{1\}\{\\widetilde\{\\operatorname\{deg\}\\left\(v\_\{p\}^\{m\}\\right\)\}\}\. Moreover, the random walk probability starting atviv\_\{i\}to the other nodes sum up to 1\. By multiplying and normalizing, the conclusion can be immediately derived\.

Moreover, the distributionπ\\piof random walk with restart isπ\(t\+1\)=α​v\+\(1−α\)​A​π\(t\)\\pi^\{\(t\+1\)\}=\\alpha v\+\(1\-\\alpha\)A\\pi^\{\(t\)\}in iteration\. We can derive the solution\(Gasteigeret al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib23)\)asπ=α​\(I−\(1−α\)​A\)−1​v\\pi=\\alpha\\left\(I\-\(1\-\\alpha\)A\\right\)^\{\-1\}v, which is the same as the calculation equation in Eq\.[4](https://arxiv.org/html/2607.00671#S4.E4)\. ∎

## Appendix BTime Complexity Comparison

### B\.1Theoretical Comparison

We now analyze the time complexity ofLIPbased on vanilla MLNC \(Sec\.[3\.2](https://arxiv.org/html/2607.00671#S3.SS2)\)\. The calculation of influence in Sec\.[4\.2](https://arxiv.org/html/2607.00671#S4.SS2)\(Pstep\) is part of data pre\-processing where we can use fast personalized PageRank algorithms designed for large graphs\. Thus, the additional time includes two parts: \(i\) the influence calculation in transformation operation which is the same as the forward calculation of GNN, namelyO​\(n​f​d\+e​d\)O\(nfd\+ed\), whereffis feature dimension andddis hidden dimension of GNNs,nnandeeare the number of nodes and edges in original graph; \(ii\) the important score calculation fromGL​I​PG\_\{LIP\}costsO​\(t⋅eL​I​P\)O\(t\\cdot e\_\{LIP\}\), wherettis the number of iterations andeL​I​Pe\_\{LIP\}is the number of influence edges in𝐀L​I​P\\mathbf\{A\}\_\{LIP\}\. Thus, the overall time complexity isO​\(n\+e\+t⋅eL​I​P\)O\(n\+e\+t\\cdot e\_\{LIP\}\)sincef,d≪n,ef,d\\ll n,e\.

We select several representative baselines and analyzed their time complexities, as shown in the Tab\.[2](https://arxiv.org/html/2607.00671#A2.T2)below\.

Table 2:The comparison of time complexity betweenLIPand other baselines\.In the table above,kkrepresents the hyperparameter for the k\-nearest neighbors algorithm,llstands for the number of labels,bbdenotes the number of sample neighbors set in LANC, andffrefers to the size of its hidden layer\. The table shows that our method has almost the lowest time complexity, and experiments confirm that it can scale to large graph datasets effectively\.

### B\.2Empirical Computational Cost

We add 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 methods, 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\.

## Appendix CExtended Related Work

Multi\-label correlation mining\.Exploring multi\-label correlation in other data forms, e\.g\. computer vision \(CV\), is also a key challenge\. These methods can be divided into three categories: first order, second order and high\-order\(Zhang and Zhang,[2010](https://arxiv.org/html/2607.00671#bib.bib88)\)\. First\-order methods disregard label correlations, assuming all labels are independent\. Binary Relevance \(BR\)\(Tsoumakaset al\.,[2010](https://arxiv.org/html/2607.00671#bib.bib53)\), transforms the problem into separate binary classification tasks\. Similarly, ML\-KNN\(Zhang and Zhou,[2007](https://arxiv.org/html/2607.00671#bib.bib56)\)is based on k\-nearest\-neighbor classification\. While these methods are highly efficient, their neglect of label correlations leads to reduced performance\. Second\-order methods emphasize pairwise label correlations\. Approaches like calibrated label ranking \(CLR\)\(Fürnkranzet al\.,[2008](https://arxiv.org/html/2607.00671#bib.bib5)\)transform into pairwise ranking problems\. While they are generally more effective than first\-order approaches at exploiting label correlations, label relationships can be highly complex in the real\-world applications\. High\-order methods aim to explore higher\-order label correlations\. Classifier chains \(CC\)\(Readet al\.,[2009](https://arxiv.org/html/2607.00671#bib.bib55)\)trains a chain of binary classifiers, each predicting the current label based on the features and previously predicted labels\. LACO\(Zhanget al\.,[2021b](https://arxiv.org/html/2607.00671#bib.bib86)\)introduces two additional losses for label correlation prediction\. HOMI\(Siet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib89)\)argue that the label matrix is approximately full\-rank and use the label correlation to regularize the prediction which is similar to PLAIN\(Wanget al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib57)\)\. However, these methods do not analyze the complex non\-Euclidean nature of graphs\. For image and text data, where data points are independent, label correlations exist within label semantics\. For graph data, the topological structure between node sets with different labels makes the analysis more challenging\. Moreover, as shown in Fig\.[3](https://arxiv.org/html/2607.00671#footnote3), we find that MLNC on graphs requires uncovering the*influence correlations*rather than the proximity correlations explored in other works\. In other words, there can be both positive and negative influences between labels on graphs, while previous studies could only capture positive label proximity\.

Label Propagation Methods\.The Label Propagation Algorithm \(LPA\) is a classic method whose application extends even beyond graph\-based tasks\. The fundamental assumption of LPA is that labels vary smoothly over the edges of a graph\. As a result, given a graph and the labels of some of its nodes, LPA can infer the labels of the remaining nodes\. However, traditional LPA does not take advantage of node feature information\. This limitation has inspired many efforts to incorporate its principles or combine its ideas with Graph Neural Networks \(GNNs\) to construct powerful models\. Some work leverage the simplicity and effectiveness of the LPA to assist graph models for node classification\. GMNNQuet al\.\([2019](https://arxiv.org/html/2607.00671#bib.bib90)\)models the joint distribution of labels with node features using Conditional Random Fields \(CRF\)Laffertyet al\.\([2001](https://arxiv.org/html/2607.00671#bib.bib91)\)and employs a variational EM frameworkNeal and Hinton \([1998](https://arxiv.org/html/2607.00671#bib.bib95)\)for efficient training\. In the E\-step, a GNN learns representation to approximate the posterior distribution of labels\. In the M\-step, another GNN models the dependencies between labels\. The M\-step is quite similar to LPA, except that it is learnable and nonlinear\. C&SHuanget al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib97)\)proposes combining shallow models that ignore graph structure with two post\-processing methods including error correction \(correct\) and label propagation \(smooth\), resulting in significant performance improvements with a simple model\. GCN\-LPAWang and Leskovec \([2021](https://arxiv.org/html/2607.00671#bib.bib94)\)theoretically analyzes the relationship between GCN and LPA, proving that edge weights that enhance LPA can also improve GCN\. Based on this insight, they proposed the GCN\-LPA model, which incorporates LPA as a regularization term for GCN\. Another line of work uses LPA to correct noisy labels\. LPMXiaet al\.\([2021](https://arxiv.org/html/2607.00671#bib.bib92)\)utilize the intrinsic graph structure to propagate labels and combines meta\-learning to aggregate labels\. Furthermore, R2LPChenget al\.\([2024](https://arxiv.org/html/2607.00671#bib.bib93)\)extends the use of LPA to arbitrary heterophily levels, simultaneously propagating labels to unlabeled nodes and correcting noisy labels\. R2LP 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 threefold: Propagation target: We do not propagate labels; instead, we propagate the influence between labels\. 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\. 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 to high\-order label influences\. This ultimately encourages labels with positive influence and suppresses those with negative influence\.

## Appendix DDatasets

To validate the proposed framework, we conduct experiments on 8 datasets, including 3 classical MLNC datasets \(Delve\-M\(Akujuobiet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib49)\), DBLP\(Akujuobiet al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib49)\), BlogCat\(Shiet al\.,[2020a](https://arxiv.org/html/2607.00671#bib.bib47)\)\), 1 private dataset \(Abnormal\), 1 large scale OGB dataset \(Ogbn\-proteins\(Huet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib16)\), OGB\-p in short\), 3 new biological datasets \(PCG, HumLoc, EukLoc\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)\) from different domains\. The private one is a real\-world anonymous graph multi\-label anomaly detection dataset under the premise of ensuring data privacy\. At present, the data Abnormal is not yet publicly available, but it may be released in the form of benchmarks in the future\. The statistics of these datasets are in following Tab\.[4](https://arxiv.org/html/2607.00671#A4.T4)\.

BlogCat\.The data lacks inherent node features, so feature initialization is required\. Although the paper\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)uses an identity matrix to initialize node features on BlogCat, their experimental results show that DeepWalk\(Perozziet al\.,[2014](https://arxiv.org/html/2607.00671#bib.bib81)\)significantly outperforms other methods using identity matrix initialization\. Thus, we use DeepWalk embedding as node feature of BlogCat in Tab\.[1](https://arxiv.org/html/2607.00671#S5.T1)and Fig\.[4](https://arxiv.org/html/2607.00671#S5.F4)\. Moreover, we find that another frequently used feature initialization method on BlogCat is to use structure\-base embedding\(Qiuet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib29)\)\. Hence we use their structure\-based initialization method in Tab\.[6](https://arxiv.org/html/2607.00671#A5.T6)and Tab\.[7](https://arxiv.org/html/2607.00671#A5.T7)\.

Table 4:The statistics of all the MLNC graph datasets\.
## Appendix EMore Experiments

### E\.1Settings and Details

ReproducibilityExperiments are conducted using 2 NVIDIA 3090 GPUs\. Each experiment is replicated five times, utilizing different seeds for each run to ensure robustness and reproducibility\. We reproduce the baselines by the released code or corresponding description in their paper\. And we follow the hyper\-parameter setting suggested in their papers to ensure the fairness of comparison\. The implementation settings and details are uploaded in the anonymous repository:[https://github\.com/Xtra\-Computing/LIP\_MLNC](https://github.com/Xtra-Computing/LIP_MLNC)\.

Evaluation metrics\.Macro AUC and AP are commonly used non\-parametric metrics in prior works\. Macro AUC is the area under the ROC curve, and it provides an aggregate measure of performance across all possible classification thresholds, reflecting the model’s ability to distinguish between positive and negative classes\. AUC is the official metric provided for comparison on the OGB leaderboard\(Huet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib16)\), and it is also used in benchmarks\(Tanget al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib11)\)for highly imbalanced scenarios\. Moreover, as noted in\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6); Yanget al\.,[2015](https://arxiv.org/html/2607.00671#bib.bib12); Sunet al\.,[2025](https://arxiv.org/html/2607.00671#bib.bib8);[2024](https://arxiv.org/html/2607.00671#bib.bib7)\), AUC can be misleading for highly imbalanced datasets\.\(Zhaoet al\.,[2023](https://arxiv.org/html/2607.00671#bib.bib6)\)also reveals that OGB\-p has a nearly 90% of unlabeled nodes, indicating extreme imbalance for most labels\. Thus, we also report Macro F1 and AP\. Macro F1 computes the F1 score for each class independently and then takes the average\. AP \(Average Precision\) is a performance metric that summarizes the precision\-recall curve by computing the weighted mean of precisions at different thresholds\. It provides an overall measure of a model’s ability to balance precision and recall, particularly useful in imbalanced datasets\. Higher values of these metrics indicates superior performance ofLIP\.

Note that AP, F1 and AUC can show significant differences due to their focus on different aspects of classification performance\. F1 is sensitive to the balance between precision and recall, making it crucial for imbalanced datasets\. AUC evaluates the overall ability to discriminate between classes across all thresholds\. Therefore, a model might have a high AUC but a lower F1 if it struggles with precision or recall for the positive class\. Moreover, AUPR \(Area Under the Precision\-Recall Curve\) is also a well\-known classification metric\. However, AUPR may overestimate model performance when the number of thresholds or unique prediction values is limited\. Hence we omit this metric\.

Hyper\-parameter settings\.For training process, we use Adam optimizer with early stopping at 100 epochs to trainLIP\. Moreover, other hyper\-parameters are decided using random search strategy and the range of hyper\-parameters are listed in Tab\.[5](https://arxiv.org/html/2607.00671#A5.T5)\. When comparing with other baselines, we set the same number of layers for the backbone if the same backbone is used\.

Backbones\.As shown in the Tab\.[4](https://arxiv.org/html/2607.00671#A4.T4), our datasets include both homophily and heterophily datasets, so we used four different backbones to validate the effectiveness of our method\. Among them, GCN\(Kipf and Welling,[2017](https://arxiv.org/html/2607.00671#bib.bib65)\), GAT\(Veličkovićet al\.,[2017](https://arxiv.org/html/2607.00671#bib.bib10)\), and GraphSage\(Hamiltonet al\.,[2017](https://arxiv.org/html/2607.00671#bib.bib62)\)are commonly used backbones for homophily graphs, while H2GCN\(Zhuet al\.,[2020](https://arxiv.org/html/2607.00671#bib.bib28)\)is a popular model for heterophily graphs\.

Table 5:The hyperparameter setting in this paper for all datasets
### E\.2Evaluation under Label Split

Two split settings\.We employ two types of split settings to show the robustness of our method on MLNC task\. The first setting is node split, where the dataset is divided into training, validation, and test sets based on nodes, meaning that every node in the training set has full label information\. This corresponds to the common single\-label split method\. However, in real\-world scenarios, labels often come from different sources\. For instance, in biological PPI networks, a protein may not have all its functions or phenotypes collected, or different phenotypes might be annotated by different teams, meaning not every node in a batch has all labels\. Thus, the second setting, label split, was introduced: each label is assigned to the same number of nodes\. Since multi\-label classification on graph data is inherently transductive—where all node features and the graph structure are known—there is no risk of data leakage\. This setting better reflects real\-world scenarios\. Note that split setting is not split ratio setting which means different proportions of training samples\. Please refer to Tab\.[1](https://arxiv.org/html/2607.00671#S5.T1)for node split setting\. Here in appendix, we show the performance under label split setting in Tab\.[6](https://arxiv.org/html/2607.00671#A5.T6)and Tab\.[7](https://arxiv.org/html/2607.00671#A5.T7)\.

Results\.In our experiments, we employed two different split ratios, specifically,6:2:26:2:2and2:2:62:2:6\. Under the same split ratio, we repeat the random splitting process with different random seeds five times\.

Due to its abundance of labels, better reveals whether the model truly uncovers the rich relationships among labels\. From the Tab\.[6](https://arxiv.org/html/2607.00671#A5.T6), we can draw several conclusions\. First and foremost, our method is the most effective one most of the time, which verifies the effectiveness of our approach\.

Table 6:Performance under*label split*setting with the split of 6:2:2 \(mean ± std\. deviation\) in terms of macro F1 , macro ROC\_AUC\. The top performance are bolded and second ones are underlined\.Here we show the second setting of training label ratio in Tab\.[7](https://arxiv.org/html/2607.00671#A5.T7)\. We simulated a scenario with sparse training samples, as often seen in real\-world applications\. In this setting, the limited training labels make it more challenging to capture label relationships\. Methods that introduce labels as new nodes and construct a new graph with label\-node edges are more affected, as fewer training labels result in fewer connections between the new label nodes and the original nodes, potentially leading to poorer performance\.

Table 7:Performance under*label split*setting with the split of 2:2:6 \(mean ± std\. deviation\) in terms of macro F1, macro ROC\_AUC\. The top performance are bolded and second ones are underlined\.As shown in Tab\.[7](https://arxiv.org/html/2607.00671#A5.T7), our method once again achieved the best performance, with greater improvement over the baseline compared to scenarios with richer training samples\.

### E\.3Changing Backbone ofLIP

As shown in Fig\.[5](https://arxiv.org/html/2607.00671#A5.F5)\(a\), our model consistantly achieves improvement when applied to any backbone, demonstrating the effectiveness of our approach\. The difference in performance among backbones not using our method depends entirely on the inductive bias inherent in the graph data itself\. An interesting observation is that different backbone models exhibit varying degrees of sensitivity to our method\. For instance, GCN show greater improvements before and after the application of our method compared to GAT\. We think that this may be due to our method’s relation to gradient calculation, with different models having varying sensitivities to labels\. Possibly, during training, GAT’s gradient changes more rapidly, leading to quicker changes in label correlation\. Moreover, since our method can be flexibly applied to any backbone capable of obtaining node embeddings, it allows our approach to serve as a plug\-and\-play enhancement for MLNC\.

Table 8:Changing backbones \(AUC\) under node split on MLNC datasets\.Moreover, we further conducte a series of experiments by replacing the backbone with more advanced decoupled GNNs: APPNPGasteigeret al\.\([2019](https://arxiv.org/html/2607.00671#bib.bib23)\)and GPRGNNChienet al\.\([2020](https://arxiv.org/html/2607.00671#bib.bib25)\)\. APPNP is a classical yet powerful model, while GPRGNN achieve state\-of\-the\-art \(SOTA\) on both homophily and heterophily graphs\. 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 Tab\.[8](https://arxiv.org/html/2607.00671#A5.T8)\.

From the Tab\.[8](https://arxiv.org/html/2607.00671#A5.T8), 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\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/x5.png)Figure 5:More model analysis on different datasets\.
### E\.4Ablation study

Normalization\.As shown in Fig\.[5](https://arxiv.org/html/2607.00671#A5.F5)\(b\), the softmax normalization we use is more effective\. From our empirical analysis, Softmax offers two key advantages compared to Row normalization\. First, Softmax provides stronger differentiation\. In the case of the influence matrix, failing to capture differences in influence may result in similar learning weights for labels that either negatively impact or provide only minimal positive impact, potentially leading to a vicious cycle\. Second, Softmax provides stable gradients, contributing to smoother model optimization\. In contrast, Row normalization, being a simple normalization operation, may gradually flatten the differences in influence relationships over successive iterations\.

Influence Correlations in P and T steps\.We supplement the ablation study across all datasets \(the full version of Fig\.[4](https://arxiv.org/html/2607.00671#S5.F4)b\), which is shown in the Tab\.[9](https://arxiv.org/html/2607.00671#A5.T9)\. ”None” stands for simply using the backbone model without any quantification of influence correlations between labels\.

Table 9:Ablation study of label influences \(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\.

### E\.5Sensitivity Study

Settings\.We examine the sensitivity of the model to hyper\-parameters by varying the values ofα\\alphaandβ\\beta\. We draw inspiration from APPNP’s\(Gasteigeret al\.,[2019](https://arxiv.org/html/2607.00671#bib.bib23)\)experimental setup\. When we varyα\\alpha,β\\betais fixed at 0\.28; when we varyβ\\beta,α\\alphais fixed at 0\.15\.

Results\.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α\\alphais approximately between 0\.08 and 0\.30, while the optimal range forβ\\betais approximately between 0\.10 and 0\.56\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/figs/hyper1.png)Figure 6:Changing hyper\-parameters ofα\\alphaandβ\\betaon datasets DBLP and PCG\.
### E\.6Evaluation under Inductive Setting

Settings\.In this section, we perform the inductive train/val/test split \(6:2:2\) and conducted experiments to validate the effectiveness in such setting\. 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\.

Results\.The results are shown in the Tab\.[10](https://arxiv.org/html/2607.00671#A5.T10)\. 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 correlation during the 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\.

Table 10:Performance \(AUC\) comparison under inductive setting\.
### E\.7Changing Number of Labels

Settings\.We used GCN as the backbone to compare and analyze the performance of our method across different label number of label categorieskk\.

Results\.From the Tab\.[11](https://arxiv.org/html/2607.00671#A5.T11), 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\.

Table 11:Performance \(AUC\) when changing the number of label categorieskkon HumLoc\.
### E\.8Case Study

Settings\.To better illustrate the positive and negative mutual influences between labels, we take a specific node and its surrounding neighbors as an example to demonstrate the mutual influences between labels\. We aim to show how these influences contribute to either improving or impairing the prediction performance of the node\. We selected a node with a degree of 3 from the DBLP dataset, identified as node 197\. Its adjacency structure in the original graph is shown in the Fig\.[7](https://arxiv.org/html/2607.00671#A5.F7)\.

Analysis\.It is worth noting that, as discussed in Sec\.[4](https://arxiv.org/html/2607.00671#S4)of the main text, the influence between labels is quite complex\. The influence fromYaY\_\{a\}toYbY\_\{b\}is the combined effect of a group of nodes with labelyay\_\{a\}on a group of nodes with labelyby\_\{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\. This provides a simplified perspective on these interactions\.

![Refer to caption](https://arxiv.org/html/2607.00671v1/x6.png)Figure 7:Case study on node 197 from dataset DBLP\.From the local structure of node 197, we can observe its connections to nodes 0, 18566, and 22, along with their respective node indices and ground truth labels, as shown in the figure\. However, when GCN predicts the labels for node 197, the resulting predicted probabilities are shown in the bar chart\. Based on the observations from Fig\. 1\(a\), we can roughly infer the reasons for this phenomenon:

Positive and Negative Influences: From Fig\. 1\(a\), it is evident that the other three labels generally provide positive support for label 0 and label 2, while they mostly exert negative influence on label 1 and label 3\. This implies that the influence from other labels makes it easier for node 197 to be correctly identified as label 0 or label 2, but not necessarily for label 1 or label 3\.

Localized Negative Influence: Among the neighboring nodes of node 197, only node 18566 has label 1, which is different from its surroundings\. Consequently, its negative influence is received by node 197 during the P process, resulting in label 1’s probability exceeding 0\.5\.

Impact on label 3: The high predicted probability for label 3 is likely due to the influence of other labels during backpropagation, which affects the GNN parameters\. This, in turn, increases the probability of label 3 during the T process\. In conclusion, the combined effects of positive and negative influences ultimately impact the final prediction\. As a result, Labels 0 and 2 are correctly predicted for node 197, while Labels 1 and 3 are incorrectly predicted\.

## Appendix FLimitations and Future Work

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 by 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\.