Multi-Label Node Classification with Label Influence Propagation
Authors: Yifei Sun
Zemin Liu
Bryan Hooi
Yang Yang
Rizal Fathony
Jia Chen
Bingsheng He
Venue: ICLR 2025 Poster (2025)
Keywords: graph neural networks
multi-label
node classification
Primary area: learning on graphs and other geometries & topologies
TL;DR: A novel LIP model is proposed for multi-label node classification on graphs, which analyzes and quantifies label influence correlations.

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 tasks.

Published as a conference paper at ICLR 2025
MULTI-LABEL NODE CLASSIFICATION WITH LABEL INFLUENCE PROPAGATION
Yifei Sun', Zemin Liu', Bryan Hooi', Yang Yang'; Rizal Fathony", Jia Chen', Bingsheng He "Zhejiang University, ?National University of Singapore, CCaital One, *GrabTaxi Holdings Pte. Ltd.
fyifeisun, 1iu. zemin, yangya @ ju edu. en, {bhooi, hebs @comp. nus wws. edu. aodu.sg, sg,
rizal. watphoonoyapitalllmo.ooo com, jia. wwwnegrabncccmmm 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 e-commerce networks exhibiting diverse interests. Tackling multi-label node classification (MLNC) on graphs has led to the development of various ap- proaches. 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 influ- ences between labels in non-Euclidean graph data. To address this issue, de- compose the message passing process in GNNs into two operations: propagation and transformation. We then conduct comprehensive analysis and quantification of the influence correlations between labels in each operation. Building on these insights, we propose novel model, Label Influence Propagation (LIP). Specif- ically, we construct a label influence graph based on the integrated label correla- tions. 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 evaluated on comprehensive benchmark datasets, consistently outperforming SOTA methods across various settings, demonstrating its effectiveness on MLNC task."]
INTRODUCTION
Graphs, as complex data structure, are prevalent across various fields (Jiang et al. 2019 Kipf & &Welling. 2016 Ying al. 2018 Liu et al., 2023 Fang et al., 2024). Among these, graphs with multi-label nodes are common and of great importance. For instance, proteins in ogbn-protein dataset have multiple functions (Hu al. 2020). 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 address this problem. The first strategy is to neglect the multi-label information and predict the labels without mining label cor- relations (Shi et al.] 2020b; Li et al., (023). The second strategy 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 (Gao et al. 2019 Shi et al. 2020a). 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 aggrega- tion and classification processes, thereby improving the utilization of multi-label information (Zhou et al. 2021 Xiao et al. 2022 However, these strategies underestimate the complex label correla-
"Corresponding authors.
'Our code is available at
wnwpunting//1111 MLNNC

---

Published as a conference paper at ICLR 2025
(a) Difference on DBLP
(b) AP Dilferensee on BlugCa
(c)AP Difierence un PCG
(P) Diflerence on HonLoc
0.15
0.
0.10
005
42
0000
00
-44
4.5
-0.00
-0.1
2
Figure 1: Observations showing positive (red) and negative (blue) influence between different labels. Each value in the heat maps represents the performance on the column label when trained together with the row label, minus the result of training the column label individually.
tions 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. D 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 simul- taneously 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, imply- ing that the row label can enhance the column label. Conversely, negative difference suggests a negative influence. As shown in Fig. I most graph datasets exhibit both positive and negative influ- ence 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.
Challenges. However, given the intricate nature of graph, several challenges emerges. First, the in- fluences 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 -uc-Eucli graph data is the first challenge. Second, since any label may exert both positive and negative influ- ences 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 bring positive or negative influences, respectively. Thus, how to leverage the quantified high-order influence correlations enhance the performance of MLNC task is the third challenge.
suppress labels that
Present work. To address the first challenge, we decompose the message passing into propagation and transformation operations (Zhang al.] 2022a). allowing for 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 (Xu al., 2018a; Wann & Leskovec 2020). 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 label influence analysis not only provide a deep insight into multi-label correlations on graph data but also lay solid foundation for improving MLNC on graphs.
model parameters. The above two parts of the
To tackle the second challenge, we construct 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, Label Information Propagation (LIP), which contains the above quantification steps and crafts the training dynam- ies 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 col- lection (Zhao et al. 2023) of MLNC datasets.
2 'These 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 DBI.P) due to space limitations.
2

---

Published as a conference paper at ICLR 2025
Contributions. To summarize, 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 thorough analysis and quantification of the influence correlation between labels.
Building on the quantified pairwise label influence, we design LIP, which calculates high-ordet 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 do- mains, showing improvements (AUC) of 3.06% and 3.42% on average under the node split and label split settings, respectively.
2 RELATED WORK
Multi-label Node Classification (MLNC). To promote research on MLNC, MLGNC (Zhao et al, 2023) provides three biological datasets and performs detailed analysis on both datasets and exist- ing methods. From the methodology perspective, some methods consider using textual embeddings of labels to incorporate label proximity. LARN (Xiao et al. 2022) incorporates the all label em- beddings during the neighbor aggregation process. Similarly, LANC (Zhou et al., 2021)) proposes attention mechanism to aggregates the label embeddings with each node. Another line of work con- struct additional label-label network to use the label co-occurrence correlations. ML-GCN (Gao ett al. 2019) construct both node-centric and label-centric graphs to aggregate information, while MINE (Shi et al.) 2020a) 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 (Akujuobi et al. 2019) leverage label-specific agents to walk on graphs. VariMul (Song et al. 2021) utilizes VGAE to derive node and label embeddings and designs confidence ranking loss to mine pairwise label correlations. Recent work improves MLNC by ad- dressing the ambiguity in multi-label graph structures (Bei et al.] 2024) and the limited expressive power for multi-label tasks (Zhao & Khosla 2024). However, these work do not explicitly analyze and quantify the influences between labels and exploit them to enhance the MLNC task.
Decoupled GNNs. Compared conventional GNNs, decoupled GNNs explicitly isolate the two operations and aggregate all propagation (P) and transformation (T) operations separately for pro- cessing. APPNP Gasteiger et al. (2019) and DAGNN [iu al. (2020) first propose that decoupling the two operations can enable GNNs to go much deeper without causing over-smoothing. Although SGC et al. (219) and lightGCN He al. (2020) do not discuss the decouple paradigm, it demon- strate superior efficiency and performance. PTA Dong al. (202T) further explore the paradigm from the perspective of label propagation. Since the APPNP is more suitable for homophily graphs, GPRGNN Chien al. (2020) improves it by adaptively learning GPR weights. This method not only avoids over-smoothing but also enables adaptive filtering to handle heterophily graphs. NCGNN Chen et al. (2024a) improves model capacity and training efficiency by pre-pri prepropaaatinn node features, then employs CNN-based approach to aggregate the propagated features, adap- tively capturing contextual information to boost the performance. Our work is inspired by above studies that decouple or disentangle Zhang et al. (2022a) 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 performance Gasteiger et al. (2019); Chien et al. 22000); (Sun et al. (2022) or enhance model capacity and scalability Chen et al. (2024a).
PRELIMINARIES
3.1 PROBLEM FORMULATION
Given graph G (V, E) with the adjacency matrix A E Rax= where V and |E| are the total number of nodes and edges. Each node e; E V associated with feature vector x, E R and all these feature vectors constitute the feature matrix X R X2,X2,.... x,," 1 of the graph G. Among all the nodes, n, of n are labeled while the remaining n,, of n are not. For every node v; < n1), , it also contains set of labels y, C Y drawn
in the labeled dataset D, (1v, yi (09)
3

---

Published as a conference paper at ICLR 2025
from the given label space Y {y1, 3/.............. the label sets for the rest of the unlabeled nodes Du = fer ny + I S ny + nuJ are not available. The goal of MLNC on graphs under the semi-supervised learning setting is to learn model h : V - 2 with training data D = Dj U D, by taking both graph structure A and node feature X into consideration. Moreover, denote the nodes with label yj Y (1 S j k), node set Y3 = {U1, U2, Um, J. where my is the number of nodes belong to label y/.
................. 4k
with & possible class labels most. Furthermore,
3.2 DECOMPOSITION OF MLNC PIPELINE
Since MINC is considered as correlated multiple binary classification problems on graphs, each determining the presence or absence of a certain label (Zhang & Zhou 2013). If 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 tg as the backbone to explore both the individual information of multiple labels and their correlation information. The graph encoder Do takes in the graph structure A and the node feature X and generate node embeddings E Rnxd as
Z = Φ (A, X):
where backbone Dg parameterized by 0 can be any existing GNNs, such as GCN (Kipf & Welling 2017), GAT (Velicković al. 2018), GraphSAGE (Hamilton et al. 2017).
Thereafter, the node embeddings Z are further mapped into different label spaces by multiple shal- low classifiers V {1/1, 1/,,.... ... 2'x} with fewer parameters. For each label yy, the objective is to train a classifier bhy that computes the prediction DY R" as
yj (Z).
I ii 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. is specific to the label yj and is utilized privately by the corresponding classifier w 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 Z serving as the central bridge of the two components.
By considering both Eqs. [nd simultaneously we observe that Eq.
Definition 1 (Shared component MLNC). The shared component in MLNC boils down to the GNN backbone, parameterized by 0, which can be denoted as Lo This component is to encode nodes collectively to generate embeddings Z, irrespective of their associated labels.
Definition 2 (Private components in MLNC). The private components in MLNC boils down the classification head for each label yj. denoted th corresponding to the operations W; W,-Yy, This component is tasked with calibrating the node embeddings Z for label-specific prediction.
4 LABEL INFLUENCE PROPAGATION
4.1 OVERVIEW
The core idea of LIP is 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, first need to quantify the relationships of mutual influence between labels. Then, based 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, 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 decom- posed from Sec. 3.2 GNN relies on message passing as its core mechanism, enabling solutions to a wide range of graph applications (Wu et al. 2020). Therefore, we begin by breaking down the mes- sage passing into two independent operations: propagation (P) and transformation (T) (Zhang et al. 2022a). In short, the P step is form of Laplacian smoothing that aggregates the information of neighbors, while the step applies non-lineat transformations to capture the data distribution of the training samples. On the one hand, in Sec. 4.2 theoretical analysis shows that the influence values
4

---

Published as a conference paper at ICLR 2025
Influence in Propagation (P) Operation
Influence in Transformation (T) Operation
(a)
b
Lbi
GNN
La
Importance
Score
Ra
D
LIP
Lancar
*
Rc
Overall Loss
Rd
Ca
Influencc Propagation
INF"
INF
INFMAT
Label
Label
Label
Label D
Construct
GLIP
Figure 2:
The overall framework of LIP: (a) quantify the influence correlations in P operation (Sec. (42) where the arrows with colors represents the mutual influence between labels; (b) quantify the influence correlations
operation (Sec. 4.3) where Laj separately calculates the loss of each label; (c) combine these two influence correlations to get the high-order label influence, and propa- gate through the constructed graph G GLIP to calculate the important score for each label (Sec. 4.4
in P operation are independent of the node embeddings, and therefore unrelated to the parameters of message passing. On the other hand, Sec. 4.. analyzes the influence between labels in T opera- tion which does not affect the topological structure between node sets with different labels, and is thus unrelated to the aggregation message passing. Since the two operations are independent, the quantified influence be further combined the foundation of computing high-order influence correlations and help to improve MLNC task (Sec. 4.4
The overall framework is shown in Fig. F with three main parts: (a) calculating the influence between labels in P operation, (b) calculating the influence between labels in T operation, and (c) propagating the influence the label information propagation graph to form the final learning objective.
4.2 INFLUENCES 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 sets Y. and Y, (1 S a k), which shown in Fig. aa).. 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 pairs Wi and ey- Inspired by previous work (Xu et al. 20T8a; Wang & Leskovec) 2020 /Zhag ct al. 202 the influence from U; to By can be quantified by measuring how alterations in the input feature of i affect the node embedding zj of vy after / iterations of message passing. In particular, for 2 and ny, supposing the message passing of the shared backbone D as (k) A * (Z) where Z ()) = X and Å = D D-1/1 1/2 AD- is the symmetrically normalized adjacency matrix with self- loops, the influence of v; on the final embedding of Uj. i.e., [i,,),, can be defined
(x(
Iii.))
Although the calculation of [(i,j) initially involves node features, inspired by (Xu et al. 201 (a). we
prove that the magnitude of (i.j) is actually independent of the features themselves and is instead proportional in expectation to random walk distribution T quantify and compute this distribution Tim, inspired by (Gasteiger et al. 2019). we find that we can solving the Personalized PageRank (PPR) Tpp instead. By iteratively computing the PPR, we obtain the influence correlations between any two nodes. Thus, we derive the quantification of the influence between any pair of nodes vi ny during the P phase as:
(jx) To further (ji) namely [(i, j) *
5

---

Published as a conference paper at ICLR 2025
INF (w,, == [(i.]) & +(0) "ppr = {a(In - (
(4)
where In R=x" is the identity matrix, one-hot indicator vector, and {-)e, means the vy-th element {.}. Detailed discussion is in App.
(0, 1] is the teleport (or restart) probability, Su, is
Influence between label sets. Having computed the influence correlations magnitude INF (vi, uz)) between any pair of nodes during the phase, represented as an x node influence correlations matrix, the second part involves integrating the influence from all nodes in Y. (with label ya) all nodes in Y, (with label y6) get the label influence correlation between Yo and ye- This part yields k x k label influence relationship matrix INF" (ya. yb). A straightforward way would be di- rectly sum up the node level influence. However, as shown in analysis in Fig. | there are both positive and negative influences between labels.
Label: 1,0
Label: 0,1
Ya
Yo
INF
INF
Therefore, proceed to analyze the combinations of two node sets Y, and Y, with different labels to de- termine which node pairs exert positive influence and which exert negative influence. Specifically, if node o is labeled with yj. can be seen that this node is la- beled as 1 in the binary classification of whether it has the label Vy: conversely, it does not have the label yy, it can seen as being labeled as O. Based on the Laplacian smoothing in the P operation (Zhang et al. (2222a), the information transmitted by source node v, labeled with makes easier for target nodes v, to identified as labeled in the same label space. Note that we break down the discussion of the influence direction between Y, and Y by first analyzing the influence from Y, to Y9. The reverse direction can be inferred by analogy. Thus, first analyze the influence from Y, Y,, where the target is the set of all nodes with label yb. From analysis in Fig. 3, we discuss the source from the following two aspects:
Figure 3: Illustration of the direction of positive and negative influence during step. The nodes with both colors indi- cates the ones with both labels.
the label set Y., the nodes are labeled as [1, 0) (possessing ya). therefore has negative influence on label set Y, ((,, 1)). However, the overlapping nodes labeled [1, 1] where the positive and negative influences to target nodes are neutralized.
Definition 3 (Source of Negative Influence INF
Vneg = Ya \ (Ya n Y.) - Yb,
(5)
where means set difference and O means intersection.
Intuitively, nodes with the label yb, noted as [+, 1), may contribute positive influence to all nodes Yo (those with the label [0, 1J). However, nodes that simultaneously have both yo and yh labels (noted as [1, 1J) neutralize their positive and negative influences on Y,. Therefore, the source of positive influence from Y, to Y, can be defined as follows:
Definition (Source of Positive Influence INFP+).
VpOe Ya Y. UY Yo nY + Yo.
(6)
where means complement and means union.
Thus, by simply substituting INF as the index into Eq. and normalizing by number of nodes, obtain the value of
obtain the value of positive influence from Y, to Yo; similarly, negative influence by substituting INF" Adding the positive and negative influence together yields the complete influence in propagation operation ! between any two labels.
4.3 INFLUENCES 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

---

Published as a conference paper at ICLR 2025
this transformation operation. Moreover, the direction and magnitudes of parameter updates in the shared backbone Po is determined by each label yi, but different labels may require different directions and magnitudes of updates to reach their optimal solutions. Thus, labels influence each other through parameter transformation during back propagation, which through gradient descent. Next, further quantify and analyze the gradient influence exerted by different labels.
Note that we use binary cross-entropy losses as Lsi for each label individually, which can be changed other types of binary classification loss:
M
L M log(S:) + (1 - yz) log(1 - 9;)],,
Σ
where y {0, 1] is binary label indicating whether node possess certain label and M is the number of the training nodes.
Therefore, the binary classification loss Loi of each label exerts specific gradient Vo to the shared component during the transformation operation:
Vbi
(8)
0
These different gradients generated by the losses of different labels may either be mutually bene- ficial or mutually harmful. Therefore. during this transformation operation, any pair of labels will influence each other through their respective gradients as shown in Fig.B(b)
Inspired by the definition of gradients conflicting (Yu al. 2020), 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 transformation step.
Definition (T step Influence INFT). Given two losses La and La (1 S. a, S. k) label ya and yb respectively, the influence in transformation operation is the accumulated differences between the gradients Va and Vu:
(9) where (0) is the gradient of binary loss Lu on shared backbone bg. and ANGLE(-) measure the angle between directions of two gradients. our implementation, we determine the angle between the two gradients by calculating the cosine similarity.
INF (a. (b, - Eo ANGLEEV..00 Vo(O)),
4.4 INFLUENCE PROPAGATION ON LABEL GRAPH
Label graph construction. From the previous work (Zhang et al. 2022a Wu et al.) 2019 Zhang jet al., 2022b) and the above analysis, can seen that the influence between labels during prop- agation 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 INF INFT, INFMAT *
(10)
where means element-wint multiply. Each value in INFMAT reflects the relationship between each pair of labels. However, we still need to analyze the higher-order correlations between labels.
Thus, we propose to build label graph GLIP. Note that INFMAT contains both positive and negative values. Our goal is to enhance the positive influence and suppress the negative influence between labels. Thus, introduce simple method yet can preserve higher-order influence to convert the INFMAT into label graph GI.P:
Definition 6. Given the label influence matrix INFMAT BRkck we define label graph as GLIP (Vy. ALIP), with ALIP SOFTMAX (INEMAT).
(11)
where SOFTMAX represents calculating softmax along the rows which means that we tend treat the negative inftuence weak positive influence in the higher-order view. V, y denotes the label nodes (triangle nodes in Fig. ( which represent a certain label type. ALp h.pp& is the weighted adjacent matrix denoting the overall higher-onder correlations between all the labels.
7

---

Published as a conference paper at ICLR 2025
Overall loss function. Intuitively, if label is detrimental to many other labels, suppressed it by reducing its coefficient of the loss corresponding to this label to lessen its negative impact. Conversely, if label is beneficial to many other labels, 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 graph GLIP. Since the higher-order influence propagation take place the graph LIP,, we turn to the computation of PageRank (Page et al. 1999) for GLIP.
Formally, calculate the importance score [0. 11th of each label node as
(-
R= (I BALIP)
(12)
h
where I, is the identity matrix, B E (0, 1) is the teleport (or restart) probability here, 1 is an h- dimensional vector in which all elements are equal to I.
Incorporating this importance coefficient R, present the overall loss function
CLIP Σj= Ry
(13)
where Lai is from Eq. which can be changed other imbalanced classification loss (Chen al. 2024b Zhuo et al. )
5
EXPERIMENTS
In this section, we evaluate LIP and aim to answer the following research questions:
RQI. How does LIP perform on MINC task with different settings and label ratios?
RQ2. Can LIP serve as plug-and-play booster to be equipped with any backbone?
RQ3. How reliable are the label influence relationships we proposed to capture?
5.1 EXPERIMENTAL SETTINGS
To comprehensively validate our framework, we conduct experiments on 2 classical MLNC datasets (DBLP (Akujuobi al., 2019), BlogCat (Shi al., (020a)). 1 large scale OGB dataset (Ogbn- proteins (Hu et al. 2020), OGB-p in short), and 3 new biological datasets (PCG, HumLoc, Euk-
Loc (Zhao al. (203)) from different domains. The statistics of datasets are in App. D We use three types of basclines for comparison. First, we combine unsupervised embedding and multi-label classifier. We adopt the frequently used unsupervised graph embedding methods 2 (Grover & Leskovec| 2016). the classic multi-label classifiers binary relevance (BR) (Tsoumakas al.) 2010) and classifier chain (CC) (Read et al.) (009). 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 (Kipi & Welling 2017) as main backbone, ML-KNN (Zhang Zhou 2007) and lat- est work PLAÍN (Wang al. 2023) as multi-label methods. The third group is raelean methods which specifically designed for MLNC on graphs. We choose MLGW (Akujuobi et al.) 2019), ML-GGN (Gao et al. 2019), LARN (Xiao al.] (2022), LANC (Zhou al., (021] and the latest work VariMul (Song et al.) 2021). Furthermore, "backhone+Auto" means the coefficients of losses of different labels are learned automatically. More details are App. E.1
5.2 COMPARISON WITH BASELINES
To answer RQ1, we evaluate LIP against various kinds of baselines classic and latest benchmark datasets, ranging from multi-label techniques used on any data form to methods tailored for MILCC on graphs. To fully evaluate the effectiveness against baselines, adopt 2 split settings: node split and label split. Refer to App. [.I to see the details and differences between them. We also evaluate under different training ratio (App. E.2
From Tab. D we can draw several conclusions. First and foremost, LIP is the most effective one most of the time. which verifies the effectiveness of 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 the backbones. Second, we find that while other methods including VariMul,
8

---

Published as a conference paper at ICLR 2025
Table 1: Performance (mean + std. deviation) under node split at 6:2:2 in terms of Maero AUC, AP.
DBLP
BlogCat
OGB-p
Metrics
Macro AUC
AP
Macro AUC
AP
Macro AUC
AP
Node2vec+BB BR
71.22 = 0.31
57.41 = 1.29
53.76 1.08
6,56 + 0.75
50.22 +: 3.01
1.92 0.73
Node2vec+CCC
72.57 0.24
57.13 + 1.88
57.97 1.31
8.93 0.82
51.39 2.14
2.07 0.31
GCN+ML-KNN
90.11 = 1.02
80.01 = 0.77
60.18 = 2.33
9.16 + 0.60
55.07
=
2.02 =0:=00. 0.33
GCN+PLAIN
80.55
73.44
63.95 1.85
10.21 0.56
66.29 3.45
3.26 0.67
MLGW
73.32 1.44
56.03
60.02 2.19
9.81 0.46
50.70 2.54
1.78 0.73
MI-GGON
72.66 + 2.73
56.71
2.59
60.97 2.21
9.68 0.39
60.11 + 2.65
2.19 0.54
LARN
74.29 = 2.53
58.11 = 1.25
63.18 1.84
9.77 + 0.63
68.18 + 1.33
3.08 = 0.16
LANC
91.68 = 0.42
83.50
0.83
67.94 = 3.30
10.35 = 0.82
68.75 0.51
=
VariMul
92.14 1.23
85.30
2.97 68.71
13.74 0.83
70.73
1.67
2.31 0.44
ACt+
92.13 1.57
85.48
1.32
66.05 1.25
12.53
0.51
71.39
1.34
2.11 0.22
GCN+LIP
94.38 1.51
1.28 87.45
70.21 2.02
12.33 0.91
74,82 + 0.34
5.72 0.28
PCG
HumLoc
EukLoc
Metrics
Macro AUC
AP
Macro AUC
AP
Macro AUC
AP
Node2vec+BR
52.66 = 1.73
15.13 = 0.25
54.17 1,58
10.67 = 0.42
51.29 # 1.60
6.00 0.72
Node2vec+CCC
52.92 = 0.62
14.54 = 0.51
54.81 1.29
11.53 = 0.36
52.18 + 1.16
6.55 = 0.59
MCN+ML-KNN
56.11 = 0,50
18.60 = 0.82
57.99 = 0.35
11.76 = 0.77
63.95 + 1.15
9.34 0.77
GCN-PLAIN
59.75 1.70
20.16 = 1.00
60.15 1.28
14.71 1.51
68.02 1.10
11.72 + 0.69
MLGW
55.86
15.59
56.92 1.03
10.54
0.43
51.77
1.41
0.55
ML-GCN
57.24 2.44
19.45
1.13
60.79 1.38
0,46 14.55
54.17
1.88
6.92 0.49
L.RN
57.79 + 0.61
19.09 + 0.38
61.48
1.22
17.89
0.62
$7.79 + 1.28
7.41 0.80
LANC
56.58 = 0.63
19.51 = 0.93
59.63 = 1.21
13,26 1006=0.900 0.98
51.25 1: 0.63
6.11
VariMul
62.77 0.34
21.93
0.52
67.42 2.44
23.34
0.88
71.44 4: 1.66
13.74 1 0.76
GCN+Aute
58.53 0.47
19.11 0.83
66.07 1.17
21.58
1.09
70.25
1.25
13.05 + 0.46
GCN+LIP
65.73 0.52
22.97
1.69
73.22 1.76
25.18
1.16
72.92
1.82
15.26 + 0,56
LARN, and PLAIN achieve good results, methods tailored for MLNC on graph data always outper- form 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-labe 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+ 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 benefi- cial 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.3 COMPARISON WITH DIFFERENT BACKBONES
One of the advantages of LIP is the ability of being plugged into any node embedding methods. Thus, to answer RQ2, we propose to change the backbone to others with different inductive bias. Here compare
method with the "Com", which directly sums the multi-label loss to train the model. We also change backbones on more datasets in App. F.2 Since some of the datasets are heterophily graphs (see Tab. 4. we backbones designed for homophily and heterophily graphs.
Results. We change backbones on BlogCat dataset in Fig. 4a). We can see that LIP constantly achieves large improvement when applied to any backbone, demonstrating the effectiveness of our approach. Although BlogCat is heterophily graph, H2GCN does not perform well comparing to others. Similar results can be found in (Zhao et al. 2023). However, H2GCN perform best on Abnormal as a heterophily graph in App. E.2 We believe there are two reasons for this. First, BlogCat has no node features, so we used Vec as feature for all methods, making the input of backbone actually homogeneous graph from 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

---

Published as a conference paper at ICLR 2025
75.0
100
15
Com
LIP
Only
72.5
90-
Only
Label Co
Macw AUC
70.0
Macro ADC
All
13
Cosine Similarity
67.5
80-
12-
65.0
25
50 Eppachs
100
GraphSoge H2GCN (5) Comparison different backiomess
GCN GAT
EakLoc (b) Ablation label influenees.
DBLP
Comparison of diffferen label correlations.
Figure 4: Model Analysis showing the effectiveness of LIP.
not perform better. An interesting observation is that different backbone models exhibit varying degrees of sensitivity 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.
5.4 DISCUSSION ON LABEL CORRELATIONS
To answer the RQ3, we evaluate the label influence correlation mined by LIP. First, we decom- pose the proposed two parts of influence correlations to evaluate effectiveness of each correlation separately. Then, we compare puting correlations to see which more accurately reflects the influence correlations between labels.
method with other commonly used approaches for explicitly com-
Ablation study on correlations. The "Only P", "Only T" and "All" means using INF", INF" and INFMAT respectively, where GCN is the backbone. As shown in Fig. 4bb), the performance using the whole INFMAT is the best, which prove the utility of the combination of the influence during both forward and backward propagation. Moreover, we find that INF perform better than INF" on EukLoc while the other way around DBLP. We believe the reason is that EukLoc is more heterophilic, making it more dependent global graph structure. Our INF" focuses uncover- ing influence during the propagation process, which emphasizes the structural aspects more during training compared to INF"". More ablation study on normalization is in App. B.2
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. [ which contain positive and negative correlations. Note that cannot this performance differences as the label correlations in the model, as retraining the performance to calculate them possible. Therefore, compare which method 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 (Wang al. (023) and cosine similarity of label embeddings from (Xu et al. 2018b). We calculate the 12-norm difference between the three methods we compare and the influence correlations as epochs increase (with GCN backbone on DBLP). As shown in Fig. c), although INFMAT changes over epochs, the difference between INFMAT and ground truth correlation 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
6 CONCLUSIONS
In this paper, we address the challenges of the valuable but overlooked MLNC task by introduc- ing 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 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 nega- tive ones. Empirical results across comprehensive MLNC datasets demonstrate the effectiveness of LIP, achieving consistent improvements in various metrics.
10

---

Published as a conference paper at ICLR 2025
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 Foun- dation, Singapore under its Singapore Programme (AISG Award No: AISG2-TC-2021-002 Any opinions, findings and conclusions recommendations expressed in this material those of the author(s) and do not reflect the views of National Research Foundation, Singapore and Info- comm Media Development Authority. This work is also supported by NSFC (No. 62322606, No. 62441605), Zhejiang NSF (LR22F020005), and CCF-Zhipu Large Model Fund.
REFERENCES
Uchenna Akujuobi, Han Yufei, Qiannan Zhang, and Xiangliang Zhang. Collaborative graph walk for semi- semi-supervised multi-label node classification. In 2019 IEEE International Conference on Data Mining (ICDM), pp. 1-10, 2019. doi: 10. 200.000...0...00.0..
Yuanchen Bei, Weizhi Chen, Hao Chen, Sheng Zhou, Carl Yang, Jiapei Fan, Longtao Huang, and Jiajun Bu. Correlation-aware graph convolutional networks for multi-label node classification. arXiv preprint arXiv:2411.1553 2024.
Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imbaland learning for semi-supervised node classification. Advances in Neural In- formation Processing Systems, 34:29885-29000 -98977, 2021.
Jinsong Chen, Boyu Li, and Kun He. Neighborhood convolutional graph neural network. Knowledge- Based Systems, 295: 1861, 2024a.
Nan Chen, Zemin Liu, Bryan Hooi, Bingsheng He, Rizal Fathony, Jun Hu, and Jia Chen. Consis- tency training with learnable data augmentation for graph anomaly detection with limited super- vision. In The Twelfth International Conference on Learning Representations, 2024b.
Yao Cheng, Caihua Shan, Yifei Shen, Xiang Li, Siqiang Luo, and Dongsheng Li. Resurrecting label propagation for graphs with heterophily and label noise. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 433-444, 2024.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint wxXv:2006.07798, 2020.
Hande Dong, Jiawei Chen, Fuli Feng, Xiangnan He, Shuxian Bi, Zhaolin Ding, and Peng Cui. On the equivalence of decoupled graph convolution network and label propagation. In Proceedings of the Web Conference 2021, pp. 3651-3662, 2021.
Taoran Fang. Wei Zhou, Yifei Sun, Kaiqiao Han, Lvbin Ma, and Yang Yang. Exploring correlations of self-supervised tasks for graphs. In International Conference on Machine Learning, 2024.
Johannes Fürnkranz, Eyke Hüllermeier, Eneldo Loza Meneía, and Klaus Brinker. Multilabel classi- fication via calibrated label ranking. Machine learning, 73:133-153, 2008
Kaisheng Gao, Jing Zhang, and Cangqi Zhou. Semi-supervised graph embedding for multi-label graph node classification, 2019.
Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. ICLR, 2019.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855 864, 2016.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NIPS, volume 30, pp. 1025-1035, 2017.

---

Published as a conference paper at ICLR 2025
Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgnn: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 639-648, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:221 111112223,,,, 2020.
Qian Huang, Horace He, Abhay Singh. Ser-Nam Lim, and Austin R. Benson. Combining label propagation and simple models out-performs graph neural networks, 2020.
Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning teaniing-oonvolutionaal networks. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 11305-11312, 2019.
Thomas N Kipf and Max Welling, Variational graph auto-encoders. In ArXiv, volume abs/161 1.071.,,70,,, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works, 2017.
John Lafferty, Andrew McCallum, Fernando Pereira, et al. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In leml, volume 1, pp. 3. Williamstown, MA, 2001.
Houyi Li, Zhihong Chen, Zhao Li, Qinkai Zheng, Peng Zhang, and Shuigeng Zhou. Gipa: A general information propagation algorithm for graph learning. In International Conference on Database Systems for Advanced Applications, pp. 465-476. Springer, 2023.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp- 338-348, 2020.
Zemin Liu, Yuan Li, Nan Chen, Qian Wang. Bryan Hooi, and Bingsheng He. A survey of imbalanced learning on graphs: Problems, techniques, and future directions. arXiv preprint arXiv:2308. 13821, 2023.
Radford M Neal and Geoffrey E Hinton. A view of the em algorithm that justifies incremental, sparse, and other variants. In Learning in graphical models, pp. 355-368. Springer, 1998.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation rank- ing Bringing order to the web. In The Web Conference, 1999. URL hhtpps://api.
semant i cschol ar. org/Corpus TD: 1508503
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social represen- tations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge dis- covery and data mining, KDD '14. ACM, August 2014. doi: 10. 10.1145/26233302222777 URL
httt:://xx doi. /tgg /
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. arXiv preprint arXiv:2006.0900 09963, 2020.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In International conference on machine learning, pp. 5241-52551 PMLR, 2019.
Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank. Classifier chains for multi-label classification. In Wray Buntine, Marko Grobelnik, Dunja Mladenié, and John Shawe-Tay Taylor (eds.), Machine Learning and Knowledge Discovery in Databases, pp. 254-269, Berlin, Heidel- berg. 2009. Springer Berlin Heidelberg. ISBN 978-3-642-04174-7.
12

---

Published as a conference paper at ICLR 2025
Min Shi, Yufei Tang, and Xingquan Zhu. Mine: Multi-label network embedding. JEEE Transactions on Neural Networks and Learning Systems, 31(9):3682-360 -3995, 2020a. doi: 10.1109/TNNLS.2015 2945869.
Yunsheng Shi, Zhengjie Huang. Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509 2020b.
Chongjie Si, Yuheng Jia, Ran Wang, Min-Ling Zhang, Yanghe Feng, and Qu Chongxiao. Multi-label classification with high-rank and high-order label correlations. IEEE Transactions on Knowledge and Data Engineering. 2023.
Zixing Song, Ziqiao Meng, Yifei Zhang, and Irwin King. Semi-supervised multi-label learning for graph-structured data. In Proceedings of the 30th ACM International Conference Information
& Knowledge Management, CIKM '21, pp. 1723-1733, New York, NY. USA, 2021. Associa- tion for Computing Machinery. ISBN 9781450384469,
doi: 10.114573459933.34883911 URL
htttps://doi.org htt.g//....11111. 114./ 33513375563333 015.:///0///11113355533333333999 3482391
Yifei Sun, Haoran Deng, Yang Yang, Chunping Wang, Jiarong Xu, Renhong Huang, Linfeng Cao, Yang Wang. and Lei Chen. Beyond homophily: Structure-aware path aggregation graph neural network. In Lud De Raedt (ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22, pp. 2233-2240 International Joint Conferences on Artificial org/
Intelligence Organization, 7 2022. doi: 2/44933/jcaii2222//110 URL httlhhttss////
10. 24.22493/1111 /ttp:////jcai.2///1111133 2022/310
Main Track.
Yifei Sun, Qi Zhu, Yang Yang, Chunping Wang, Tianyu Fan, Jiajun Zhu, and Lei Chen. Fine- tuning graph neural networks by preserving graph generative patterns. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pp. 9053-90611 2024. 2024.
Yifei Sun, Yang Yang, Xiao Feng, Zijun Wang, Haoyang Zhong, Chumping Wang, and Lei Chen. Handling feature heterogeneity with learnable graph patches. In Proceedings of the 31th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2025.
Jianheng Tang, Fengrui Hua, Ziqi Gao, Peilin Zhao, and Jia Li. Gadbench: iting and benchmarking supervised graph anomaly detection. In Advances Neu- ral Information Processing Systems, volume 36, pp. 29628 29653, 2023.
Revis-
URL
httt:s///procedingssneeniii wwtpeeurww.....pppepeeeeeeeeeeee htcpppaapprrreeeaaaaaeeeeeee /atpe////e//e//ppp//2/2//L/L/
pdf
Grigorios Tsoumakas, loannis Manousos Katakis, and Ioannis P. Vlahavas. Mining multi-labo
data. In Data Mining and Knowledge Discovery Handbook, 2010. URL htttps://api.
Petar Velicković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Petar Velicković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Haobo Wang, Shisong Yang, Gengyu Lyu, Weiwei Liu, Tianlei Hu, Ke Chen, Songhe Feng, and Gang Chen. Deep partial multi-label learning with graph disambiguation, 2023.
Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propa- gation. arXiv preprint arXiv:2002.06755, 2020.
Hongwei Wang and Jure Leskovec. Combining graph convolutional neural networks and label prop- agation. ACM Transactions on Information Systems (TOIS), 40(4):1-27, 2021.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning. pp- 6861-6871. PMLR, 2019.
13

---

Published as a conference paper at ICLR 2025
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22)) 24, 2020.
Jun Xia, Haitao Lin, Yongjie Xu, Lirong Wu, Zhangyang Gao, Siyuan Li, and Stan Z Li. Towards robust graph neural networks against label noise. 2021.
Lin Xiao, Pengyu Xu, Liping Jing, Uchenna Akujuobi, and Xiangliang Zhang. Semantic guide for semi-supervised few-shot multi-label node classification. Information Sciences, 591:235- 250, 2022. ISSN 0020-0255.
doi: http://dbi.org//000066.........
130. URL https:
//www. sciencedirect. com/ wttp:///waaacrrrrrara////////2/0
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5463 PMLR, 2018a.
Yuanyuan Xu, Jun Wang, Shuai An, Jinmao Wei, and Jianhua Ruan. Semi-supervised multi-label feature selection by preserving feature-label space consistency. In Proceedings of the 27th ACM international conference on information and knowledge management, pp. 783-792, 2018b.
Yang Yang. Ryan N Lichtenwalter, and Nitesh V Chawla. Evaluating link prediction methods.
Knowledge and Information Systems, 45:751-782, 2015.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In SIGKDD, pp. 974- 983, 2018.
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances in Neural Information Processing Systems, 33:5824-58366 2020.
Min-Ling Zhang and Kun Zhang. Multi-label learning by exploiting label dependency. In Pro- ceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 999-1008, 2010.
Min-Ling Zhang and Hua-Hua Zhou. MI-knn: lazy learning approach to multi-label learning- Pattern Recogn., 40(7))2038- jul 2007. ISSN 0031-3203, doi: ww..10066j..atooo.ooo 12. 019. URL
100.0/.....0011111111/611111 patcog 200.cccoo.200000 2006 5.000...2 12.012
Min-Ling Zhang and Zhi-Hua Zhou. A review on multi-label learning algorithms. IEEE transactions on knowledge and data engineering. 1618):1819-1837, 2013.
Wentao Zhang, Mingyu Yang. Zeang Sheng. Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Node dependent local smoothing for scalable graph learning. Advances in Neural Information Processing Systems, 34:20321-20333 2021a.
Wentao Zhang, Zeang Sheng. Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. Model degradation hinders deep graph neural networks. In Proceedings of the 28th ACM 2022a.
SIGKDD conference on knowledge discovery and data mining, pp.
Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang. and Bin Cui. Graph attention multi-layer perceptron. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. pp. 4560-4570 2022b.
Ximing Zhang, Qian-Wen Zhang, Zhao Yan, Ruifang Liu, and Yunbo Cao. Enhancing label correlation feedback in multi-label text classification via multi-task learning, arXiv preprint arXiv:2106.03103, 2021b.
Tianqi Zhao and Megha Khosla. Gun-multifix: Addressing the pitfalls for gnns for multi-label node classification. arXiv preprint arXiv:2411.14094 2024.
Tianqi Zhao, Thi Ngan Dong, Alan Hanjalic, and Megha Khosla. Multi-label node classification on graph-structured data. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. http.htttps::/pppeeeewe
14

---

Published as a conference paper at ICLR 2025
Cangqi Zhou, Hui Chen, Jing Zhang, Qianmu Li, Dianming Hu, and Victor S. Sheng. Multi- label graph node classification with label attentive neighborhood convolution. Expert Systems with Applications, 180:115063, 2021. ISSN 0957-4174. doi: https///bb.orr//011116....vo 2021.115061 URL https: httpps://wwwwwttt 5095741742100504
www.ww..ic..coo......ooo...o.... sci encedi rect r htt////ccceeee//arrrccl//////
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily m graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
Wei Zhuo, Zemin Liu, Bryan Hooi, Bingsheng He, Guang Tan, Rizal Fathony, and Jia Chen. Par- titioning message passing for graph fraud detection. In The Twelfth International Conference Learning Representations, 2024.
15

---

Published as a conference paper at ICLR 2025
APPENDIX
A DISCUSSIONS ON INFLUENCE FROM PROPAGATION
This section aims supplement See regarding the pair wise influence value from propagation (P operation). Specifically, inspired by previous work (Xu et al. 2018a| Wang & Leskovec 2020). prove the correctness of the calculation method influence value between nodes with different labels in propagation operation.
Theorem (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) (Gasteiger al. 2019
Chen et al. 2027). Namely, the inftuence value between V:. V/ is
INF (vi, Uy), = {a(In - -1-a)) so, he, α I(i.j),
(14)
where In E Ruxn the identity matrix, a E [0, is the teleport (or restart) probability, Su, is one-hot indicator vector and (.re, means the 1y-th element of {-}-
Proof. We use l layers of GCN Kipf & Welling (017)) as backbone bg for analysis. We first prove the the influence value between us by with different labels is equivalent, in expectation, the k-step random walk distribution on graph G starting at node Uz.
From the definition of influence from vs to uy in Eq. 3 we proceed with the detailed calculations:
(k)
Oz 0z)3-1 (k-1)
[(v,, U2) 0zi (0)
diag (1,4))0) WK. Σ
(15)
22 0))
deg(o;)
=EN(v.)
where ((k) is the pre-activated embedding of 2j W stands for the last layer weight matrix of GCN. Furthermore, we use chain rule to calculate any rank I the derivative as
Oz
Oz
ΣII
diag (1 (Lycm>>>)) p=1m=f deg (om²
yrom (0)0)0))
W m:
(16)
0z (0)
Oz (0)
p=1
where À the total number paths of length /+1 from node vy to Gr For certain path p. op is node vs. 2 is node vy and for m = I...(I 1), uhk 1) E N(,,)). More specifically, we can calculate an entry of the derivative
(a,5)
02
R
W
(m) q
(17)
0z
deg (1:3))
I=
where y is the number of paths q from the b in the computation directed acyelic graph (DAG) 0e 3z
For each layer m, wy (m) is the entry of Wm which is used in the q-th path. Rg 0,
of
denote whether the q-th path is active or not as the result of ReLU activation of entries of ((m) on the q-th path. Since the variable R follows a Bernoulli distribution, for all q, Pr(R, = 1) = we have
O211
IE
(m)
(18)
Oz1
(0)
m=i deg (u
Thus, we know that
02 !
E
II Wm m=
(19)
0z (0)
p=1 m=i deg (p)))
On the other hand, k-step random walk probability v; can be calculated by summing up the probability of all paths of length from v; to uj. which is exactly Σソ I deg(
Moreover,
16

---

Published as a conference paper at ICLR 2025
the random walk probability starting v, to the other nodes up to 1. By multiplying and normalizing, the conclusion can be immediately derived.
Moreover, the distribution of random walk with restart x oz (1 a)) Ar (1) in iteration.
We can derive the solution (Gasteiger et al. 2019 as π = a (I (1-og -a) v. which is the same the calculation equation in Eq.
B TIME COMPLEXITY COMPARISON
B. THEORETICAL COMPARISON
We now analyze the time complexity of LIP based vanilla MLNC (Sec. 3.2 of influence in Sec. 4.2 (P step) 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, namely O(n + ed), where f is feature dimension and d is hidden dimension of GNNs, n and are the number of nodes and edges in original graph; (ii) the important score calculation from GLIP costs (t EL.P), where is the number of iterations and ELIP is the number of influence edges in AIIp. Thus, the overall time complexity is On + t -I.P)) since J, d < n.
The calculation
We select several representative baselines and analyzed their time complexities, as shown in the Tab. beloo.
Table 2: The comparison of time complexity between LIP and other baselines.
Method
GCN+ML-KNN
MLGW
LANC
Complexity
O(n logn (+
O e e. f4) O(n th+teu b²
Method
VariMul
GCN+Auto O(n
LIP
Complexity
O(n + 6 logg
O (eeIPP
In the table above, i represents the hyperparameter for the k-nearest neighbors algorithm, / stands for the number of labels, denotes the number of sample neighbors set in LANC, and f refers 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.2 EMPIRICAL. COMPUTATIONAL COST
We add 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.
Cost
ML-KNN
MLGW
LANC
VariMul
GCN+Auto
GCN+LIP
DBLP
Time (slepoch)
0.012
5.710
2.350
1.015
0.003
0.008
BlogCat
Time (s/epoch)
0.100
9.710
3.837
2.082
0.051
0.311
DBLP
GPU mem (MB)
2200
3530
2204
2980
2271
1595
BlogCat
GPU mem (MB)
3010
5036
2800
3572
3073
2369
As observed, our method aligns with the conclusions analyzed in Appendix B, demonstrating rel- atively 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 mag- nitude 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 quantifica- tion influence correlations during the step involves gradient calculations, our method essentially splits the gradient calculation into k smaller steps. This trades off some computation time for duced memory usage, allowing our method to achieve even lower GPU memory consumption than standard GCN.
17

---

Published as a conference paper at ICLR 2025
C EXTENDED RELATED WORK
Multi-label correlation mining. Exploring multi-label correlation in other data forms, e.g. com- puter vision (CV), is also a key challenge. These methods can be divided into three categories: first order, second order and high-order (Zhang & Zhang 2010). First-order methods disregard label correlations, assuming all labels are independent. Binary Relevance (BR) (Tsoumakas et al.] 2010), transforms the problem into separate binary classification tasks. Similarly, MI.-KNN (Zhang & Zhou /hh7) is based on Eenearest-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ürnkranz et al. 2008) 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) (Read et al., 2009) trains chain of binary classifiers, each predicting the current label based on the features and previously predicted labels. LACO (Zhang et al., (021b) introduces two additional losses for label correlation prediction. HOMI (Si et al.) (223) argue that the label matrix is approximately full-rank and use the label correlation to regularize the prediction which is similar to PLAIN (Wang et al. 2023). 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 semanties. For graph data, the topological structure between node sets with different labels makes the analysis more challenging. Moreover, as shown in Fig. [ we find that MINC 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 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 incorpo- rate 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 assist graph models for node classification. GMNN Qu et al. (2019) models the joint distribution of labels with node fea- tures using Conditional Random Fields (CRF) [afferty et al. (2001) and employs variational EM framework Neal & Hinton| (1998) 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 depen- dencies between labels. The M-step is quite similar to LPA, except that it is learnable and nonlinear. C&S Huang et al. (2020) proposes combining shallow models that ignore graph structure with two post-processing methods including error correction (correct) and label propagation (smooth), result- ing in significant performance improvements with a simple model. GCN-LPA Wang & Leskovec (202T) 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 IPA regularization term for GCN. Another line of work uses LPA to cor- rect noisy labels. LPM Xia et al. (202T) utilize the intrinsic graph structure to propagate labels and combines meta-learning to aggregate labels. Furthermore, R2LP et al. (2024) 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 het- erophily 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 three- fold: 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, con- structed 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 com- puted pairwise label influences to high-order label influences. This ultimately encourages labels with positive influence and suppresses those with negative influence.
18

---

Published as a conference paper at ICLR 2025
D DATASETS
To validate the proposed framework, we conduct experiments on 8 datasets, including 3 classical MLNC datasets (Delve-M (Akujuobi et al., 2019), DBLP (Akujuobi et al. 2019). BlogCat (Shi
et al. 2020a)), 1 private dataset (Abnormal), large scale OGB dataset (Ogbn-proteing Hu et al., 2020. OGB-p - in short), new biological datasets (PCG, HumLoc, EukLoc (Zhao al. 2023)) 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 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.
The data lacks inherent node features, feature initialization is required. Although the paper Zhao et al. 2023) uses an identity matrix to initialize node features on BlogCat, their exper- imental results show that DeepWalk (Perozzi et al.) 2014) significantly outperforms other methods using identity matrix initialization. Thus, we use Deep Walk embedding as node feature of BlogCat Tab.[[ and Fig. 4 Moreover, we find that another frequently used feature initialization method on BlogCat is to use structure-bass base embedding (Qiu et al. 2020). Hence we use their seuuture-based initialization method in Tab. aadd Tab.
ClogCat.
Table 4: The statistics of all the MLNC grap datasets.
DBLP
BlogCat
OGB-p
PCG
nodes edges
28, 70,2
10,312
132,534
3,233
68,335
667, 667,966
39,561,252
37,352
labels
39
112
Thome
0.76
0.10
0.15
0.17
Domain
Citation Network
Social Network Blogger Friendship Interests
PPI
PPI Protein Biological associations Phenotypes
Node
Author
Protein
Edge
Co-authorship
Biological associations Functions
Label
Research areas
Huml.oc
Eukl.oc
Delve-M
Abnomal
nodes
3,106
7,766
1,229,280
0.1 ~ 10M 100M
# edges
18,496
13,818
4,322,275
labels
14
22
20
11 0.05 0.20
Thomoo
0.42
0.46
0.65
Domain
PPI
PPI Protein
Wikipidia Network Paper Citation Topics
Anomaly detection User
Node
Protein
Edge
Biological associations Subcellular locations
Biological associations Subcellular locations
Label
Anomaly
E MORE EXPERIMENTS
E. SETTINGS AND DETAILS
Reproducibility Experiments are conducted using 2 NVIDIA 3090 GPUs. Each experiment is replicated five times, utilizing different seeds for each run 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 ensure the faimess of comparison. The implementation settings and details are uploaded in the anonymous repository: https:// github. ccm/ Xtra- Comput ing LII 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 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 (Hu et al. 2020), and it is also used in benchmarks (Tang al. 2023) for highly
imbalanced scenarios. Moreover, as noted in (Zhao et al., 2023 Yang et al. 2015
Sun et al. 2025
2024), AUC can be misleading for highly imbalanced datasets.
(Zhao al. 2023
also reveals that
19

---

Published as a conference paper at ICLR 2025
OGB-p has nearly 90% of unlabeled nodes, indicating extreme imbalance for most labels. Thus, we also report Macro F1 and AP. Macro F1 computes the Fl score for each class independently and then takes the average. AP (Average Precision) is performance metric that summarizes the precision-recall curve by computing the weighted mean of precisions at different thresholds. provides overall measure of model's ability to balance precision and recall, particularly useful in imbalanced datasets. Higher values of these metrics indicates superior performance of LIP.
Note that AP, Fl and AUC can show significant differences due to their focus on different aspects of classification performance. Fl is sensitive to the balance between precision and recall, making it crucial for imbalanced datasets. AUC evaluates the overall ability discriminate between classes across all thresholds. Therefore, 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 well-known classificatiin metric. However, AUPR may overestimate model performance when the number of thresholds or unique prediction values is limited. Hence we omit this metric.
aaapee-prrameter settings. For training process, 100 epochs to train LIP. Moreover, other hyper-parameters are decided using random search strat- egy and the range of paremmeersseteess listed in Tab. [ When comparing with other baselines, we set the same number of layers for the backbone if the same backbone is used.
Adam optimizer with early stopping
Backbones. As shown in the Tab. 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& & Welling 2017), GAT (Velicković et al.) 2017), and GraphSage (Hamilton et al. 2017) are commonly used backbones for homophily graphs, while H2GCN (Zhu et al. 2020) is a popular model for heterophily graphs
Table 5: The hyperparameter setting this paper for all datasets
Hyper-parameter
Range Value
Hidden size
0t8.44,22.256.555
Learning Rate
(le-3 - 5e-1)
Weight decay
Dropout rate
{0- 0.8)
Optimizer Epuch
Adam 1000
Early stopping patience
100
E.2 EVALUATION 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 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 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 inherently mansductive-wher all node features and the graph structure are known- -hhre 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 Tab. [ for node split setting. Here in appendix, we show the performance under label split setting in Tab. 6 and Tab.
Results. In our experiments, employed two different split ratios, specifically, 6 2 and 2 2 6. Under the same split ratio, we repeat the random splitting process with different random seeds five times.
20

---

Published as a conference paper at ICLR 2025
Due to its abundance of labels, better reveals whether the model truly uncovers the rich relationships among labels. From the Tab. [ 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 Fl, macro ROC AUC. The top performance are bolded and second ones are underlined.
DBLP
Delve M
BlogCat
Abnonal
Metries
Macro Fl
Macro AUC
Macro Fl
Macro AUC
Macro Fl
Macro AUC
Macro Fl
Macro AUC
Nede2Ve
75.92=20.34
83.7820.48
1.1342
64.0321.49
$2.01=1.41
60.08-0.97
43.55=11.88
76.59=1.17
Nod22veo+CC
73.61=0.31
80.34=0.32
50.06+t..29
65.47=1444
60.59=1.58 1..22+1.39
45.12+:144 143
19.28=1.44
UCN-ML-KNN
77.64:2.335
86.62-0.41
11.98:1.24
69.451181
53.61:1.14
63.56-2.62
47.22:13.24
80.28=1.81
GCN+PLAIN
82.27=0.34
91 01.28:0.44
1.761=1.74
78.72=1557
56.30:22.99
70.69=1.38
52.16:+3.27
18.23=189
MLGW
79.13.10.66
90.14.10.63
52.25
74.1510.188
$2.97.11.20
68.70_1.14
49.12.12.27
82.14. 1.92
MI.-GCN
78.64+00.4
89.30-0028
51.92-40.34
4-.2140..44
55.29-+0.22
70.64-0.68
51.27-41.30
86.61-1.21
LARN
83.86.10.28
92.77.10.33
$4.31.1 1.29
85.8511155
55.61.11.11
2.14
51.34.11.44
88.611149
LANC
80.37:0.62
89.58=0.49
05.14
86.4810.62
54.48:10.84
70.55=1.04
50,23:10.66
84.02=0.33
VariMul
84.61
93.17.10.38
56.81
86.9110.13
57.88.11.34
71.35.0.49
$2.32.10.50
88.56.0.36
GCN+Com
86,00=#0.24
94.00=00055
56.82:40.28
88.74+0.11 12
17.39++1.75
70.29-2.38
50.86++0.25
87 87.08=0.226
GCN+Auto
85.43-+0.10
14
54.71-10.29
79.08--0.11
53.44 1.50
26.7
52.35-+0.23
90.31-0031
GCN-LIP
86.50=:0.34
93.91+00119
$8.87=1122
10.89+1114
59.02:10.21
7..30=0.36
53.98+0.34
94,91=0.45
Here we show the second setting of training label ratio in Tab. 7 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 underlined.
DBLP
Delve-M
BlogCat
Abnomal
Metrics
Macro Fl
Macro AUC
Macro Fl
Macro AUC
Macro F1
Macro AUC
Macro F1
Macro AUC
BR
72.02.1..15
77.761..14
40.19.1..2
53.42.1.54
48.33
54.08
71.32..2.12 1..5
Node2Nec+CC
71.52:2.11
75.5921.59
42.45:1.03
56.5621144
49.5711.51
55.84=1.00
45.41122.8
71.33=2.32
GCN-ML-KNN
74.43=2.12
79.59=2.1
45.3411.76
$7.49=2.29
11.0811822
59.24=1.22 22
45.8111.72
73.39-0.33
GCN+PLAIN
1..34#1.32
88.67=0.52
49.23 1.25
61.25 L4
55.34+:1.22 1.26
67.35-2.11
48.23+ 1.32
87.11=2.42
MLGW
78.62442.27
85.95+1.11
47, 47.24442.56
57.83++2.15 13
51.82:+0.36
60.48:0.24
45.68++1.15
74.35=1.29
MI.-GCN
78.62:11445
83.63 1.21
49.37 1.12
58.00 1.18
$3.55 1.03
61.77 1.29
4..57-11444
77.24 1.18
LARN
50.71:1 1.8
62.08111 1686
54.1111.66
63.56=1.62
49.35:11.22
80.22-1557
LANC
79.63=20.91
88.43:20.22
49.80E2 1.12
$7.8523.18
54.18:1182
62.18=1.87
49.24:20.88
83.52=141
VariMul
83.23:10.33
91.0611.18
50.39.1 1.18
59.0811.27
57.02-11.23
69.31=1.18
10.54.1..05
88.5112115
Auto
83.96--0.13
91. 11-66+0000 16
47. 17-00.2
64.44++2.69
16.34++1.7
62.64-1.01
48. 14++1.04
85.12=1.51
GCN-LIP
84.05:20.19
92.21=0028
52.56=+1.21
69.33=1134
57.07:10.43
72.40=0.66
51.91+1.188
90.58=0.52
As shown in Tab our method once again achieved the best performance, with greater improvement over the baseline compared to scenarios with richer training samples.
E.3 CHANGING BACKBONE OF LIP
As shown in Fig. 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 method compared to GAT. We think that this may be due to method's '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 serve
plug-and-play enhancement for MLNC.
Moreover, we further conducte a series of experiments by replacing the backbone with more ad- vanced decoupled GNNs: AAPPPP(Gasteigen et al. (2019) and GPRGNN al. (2020). APPNP
21

---

Published as a conference paper at ICLR 2025
Table 8: Changing backbones (AUC) under node split MLNC datasets.
AUC
DBLP
BlogCat
PCG
EukLoc
GCN
92.83 + 1.13
66.14 1.74
59.54 + 0.90
70.53 = 1,97
GCN+LIP
94.38 + 1.51
70.21 = 2.02
65.73 + 0.52
72.92 = 1.82
GIN
93.00 0.46
68.32
0.67
63.44
1.15
73.13 = 1.24
GIN+LIP
94.75 1.29
70.87
0.93
66.10
1.64
75.10 1.29
APPNP
94.17 0.92
70.33
1.10
64.96
1.33
74.67
0.98
APPNP+LIP
95.21 + 1.08
71.82 1.45
65.51
1.74
75.86 = 1.02
GPRGNN
93.09 + 1.12
68.31
1.26
68.02
1 1.17
72.91 = 0.99
GPRGNN+LIP
95.07 1.84
72.36
0.97
68.74 + 1.58
74.88 = 1.06
is classical yet powerful model, while GPRGNN achieve state-of-the-art (SOTA) on both ho- mophily and heterophily graphs. Here, we evaluate the effectiveness our method, LIP, on these advanced decoupled GNNs and present comparison of the results between the original models and LIP-enhanced models on MLNC tasks the Tab.
observe that even for high perfforrfrm decoupled GNN models, LIP con- sistently achieves performance improvements. LIP provides enhancements across different domains and demonstrates exceptional results certain datasets. For example, LIP improved the perfor- mance 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, high- lighting 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 pro- vide additional support by modeling the influence correlation between labels.
From the Tab. g
56
100
Com
RowNorm
L1P
SottMax
54-
95
Macro AtC
Macro AUC
52-
90
50
85
48
80
GCN
GAT
GruphSSge 112GCN
AP
Marro AUC
Comparison of buckhones Abmormal.
(b) Compurison nemmulizationn DBLP.
Figure 5: More model analysis different datasets.
E.4 ABLATION STUDY
Normalization. As shown in Fig. 5jb), the softmax normalization we use is more effective. From empirical analysis, Softmax offers two key advantages compared Row normalization. First, Softmax provides stronger differentiation. In the case the influence matrix, failing to capture dif- ferences 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 smoother model optimization. In contrast, Row normal- ization, 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. 44)) which is shown in the Tab. 9 "None" stands for simply using the backbone model without any quantification of influence correlations between labels.
can observed that in all cases, utilizing the influence correlations from both propagation (P) and transformation (T) steps (noted 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 using them all. This indicates that
22

---

Published as a conference paper at ICLR 2025
Table 9:
Ablation study of label influences (GCN as backbone).
AUC
DBLP
BlogCat
OGB-p
PCG
HumLoc
EukLac
None
92.83 + 1.13
66.14 1.74
71.26 + 1.45
59.54 0.90
66.57 = 0.67
69.27 = 1.97
Only
92.08 1.06
68.27
1.88
73.72 0.63
62.01
1.21
70.17 = 1.42
70.87 1.64
Only
93.94
1.00
67.11 = 1.51
73.58
1.24
63.82 + 1.04
69.30 1.02
69.93 = 1.01
All
94.38 + 1.51
70.21 = 2.02
74.82 + 0.34
65.73 + 0.52
73.22 = 1.76
72.92 = 1.82
leveraging the influence relationships from both the P and steps is crucial for the MLNC task. Additionally, the table reveals that using the influence correlations from either the P step the 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 process, while others may benefit from maximizing positive influence during the T process.
E.5 SENSITIVITY STUDY
Settings. We examine the sensitivity of the model to hyper-parameters by varying the values of and B. We draw inspiration from APPNP's (Gasteiger et al. 2019) experimental setup. When we vary a, fixed 0.28; when we vary B, a fixed 0.15.
The conclusion is that method demonstrates robustness across range of hyper- parameter settings. Specifically, the performance remains stable within reasonable parameter ranges, indicating that the model does not heavily depend fine-tuned hyper-parameters for achieving effective results. Moreover, we find that regardless of the dataset characteristies, the optimal range for is approximately between 0.08 and 0.30, while the optimal range for B approximately between 0.10 and 0.56.
Results.
DBLP
PCG
DBLP
PCG
70
67.5
95.0
65.0
1 92.5
90.0
67.5
85
8
Figure 6: Changing hyper-parameters of a and 33 on datasets DBLP and PCG.
E.6 EVALUATION UNDER INDUCTIVE SETTING
Settings. In this section, perform the inductive train/val/test split (6:2:2) and conducted exper- iments to validate the effectiveness in such setting. We used GraphSage as the backbone because naturally suited for the inductive setting. We also excluded certain baselines that not suitable for the setting, such as VariMul and MLGW.
The results are shown in the Tab. TO 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 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 differ- ent labels, modeling the influence relationships between labels in the T step is also necessary. As result, our method achieves performance surpassing the baselines even under the inductive setting.
Results.
E.7 CHANGING 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 categories At
23

---

Published as a conference paper at ICLR 2025
Table 10: Performance (AUC) comparison under inductive setting.
SAGE+ML-KKN
SAGE+PLAIN
LARN
LANC
SAGE+Auto
SAGE+LIP
DBLP
72.45 E 1.77
74.16 1 0.91
73.87 E 1.79
73.54 1,95
77.11 2,42
79.32 1.96
EukLoc
53.31 + 1.51
55.02 + 1.73
63.39 + 2.01
65.97 + 1.67
62.82 2.19
66.35 2.36
observe that 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 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 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, some extent, an increase the number of labels results in decline in GCN's prediction performance.
Results. From the Tab.
Moreover, with our method, the performance generally improves as the number of labels increases. In contrast, GCN's 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 categories k on HumLoc.
Huml oc (AUC)
2
4
6
8
10
12
14
GCN
70.29 1 1.74
64.44
:
0.92
66.35
1.49
65.14
188
66.52 = 1.22
66.73 1 0.86
68.14 E 188
GCN-LIP
72.17 1,56
65.99
1.02
68.41
68.82
0.97
72.13
1.29
72.22 4 1.76
73.22
1.76
E.8
CASE STUDY
Settings. To better illustrate the positive and negative mutual influences between labels, take a specific node and its surrounding neighbors as an example to demonstrate the mutual influences between labels. We aim show how these influences contribute either improving the prediction performance of the node. We selected a node with degree of 3 from the DBLP dataset, identified as node 197. Its adjacency structure in the original graph is shown in the Fig,
impairing
Analysis. It is worth noting that, discussed in Sec. 4 of the main text, the influence between labels is quite complex. The influence from Y, to Y, is the combined effect group of nodes with label ya group of nodes with label ys during both the P and T processes. Here, attempt to visualize the positive and negative influences, as well as their ultimate effect on performance, using the local structure of single node rather than group of nodes with the same label. This provides a simplified perspective on these interactions.
From the local structure of node 197, observe its connections to nodes O, 18566, and 22, along with their respective node indices and ground truth labels, as shown in the figure. How- ever, when GCN predicts the labels for node 197, the resulting predicted probabilities are shown in the bar chart. Based on the observations from Fig. I(a), we can roughly infer the reasons for this phe- nomenon:
Node id: 0 GT: 10,0,0,0]
Node id: 197 GT: [0,0.00]
Node id: 18566
1.00
Node 197
GT:[0,10.0]
Positive and Negative Influences: From Fig. 1(a), evident that the other three labels generally provide positive support for label 0 and label 2, while they mostly exert negative influence on la- bel 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 label 3.
0.25
Node id: 22
GT: [0,0,000]
8.00
Label Label Label2 2 Labe
Figure 7: Case study on node 197 from dataset DBLP.
24

---

Published as a conference paper at ICLR 2025
Localized Negative Influence: Among the neighboring nodes of node 197, only node 18566 has label 1, which different from its surroundings. Consequently, its negative influence is received by node 197 during the P process, resulting in label I's probability exceeding 0.5.
Impact on label 3: The high predicted probability for label is likely due to the influence other labels during hackpropagation, which affects the GNN parameters. This, in turn, increases the probability of label 3 during the process. conclusion, the combined effects of positive and negative influences ultimately impact the final prediction, As result, Labels 0 and are correctly predicted for node 197, while Labels and 3 are incorrectly predicted.
F LIMITATIONS AND FUTURE WORK
From a scenario perspective, our work currently focuses on the most common case: static and ho- mogeneous 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 analyz- ing and quantifying the influence correlations between labels on graph datasets, without considering potential noise the labels or graph structure. We leave these complex challenges in both aspects for future exploration.
25


Reviews:
[{"review_id": "7hk04amPq9", "reviewer": "Reviewer_d1PZ", "summary": "This paper presents Label Influence Propagation (LIP), a novel approach for multi-label node classification (MLNC) on graphs. The key innovation is analyzing and leveraging the mutual influences between different labels, rather than just label correlations. The authors decompose the message passing process into propagation and transformation operations to quantify label influences, construct a label influence graph, and dynamically adjust the learning process based on positive and negative label interactions.", "questions": "1. What are the limitations of decomposing message passing into propagation and transformation operations? Are there cases where this decomposition might not hold?\n\n2. How sensitive is the method to the initial construction of the label influence graph?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper introduces a new way to analyze label relationships by examining their mutual influences rather than just correlations, supported by empirical observations shown in Figure 1.\n\n2. The work provides a theoretical analysis of how label influences emerge during both propagation and transformation operations in graph neural networks.\n\n3. The proposed LIP framework is plug-and-play compatible with various GNN architectures and shows consistent performance improvements across different datasets and settings.", "weaknesses": "The paper doesn't thoroughly discuss how the method scales with increasing numbers of labels or larger graphs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iW9ZFmNkup", "reviewer": "Reviewer_jPZg", "summary": "The paper proposes a label influence propagation framework for the multi-label node classification task. Specifically, the paper constructs a label influence graph based on the integrated label correlations. Then, the paper propagates high-order influences through this graph and dynamically adjusts the learning process by amplifying labels with positive contributions and mitigating those with negative influence.", "questions": "Please see the above weakness.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Pros:\n1. The paper considers the positive and negative influence of different labels and encourages or suppresses labels that bring positive or negative influences, respectively.\n2. The proposed model is a plug-and-play approach, which can be applied to various GNN backbones. \n3. The paper offers a label correlation analysis by dissecting the pipeline into a forward and backward propagation segment.", "weaknesses": "Cons:\n1. What is the difference between the label propagation methods? (GMNN: Graph Markov Neural Networks, Combining Graph Convolutional Neural Networks and Label Propagation, Resurrecting Label Propagation for Graphs with Heterophily and Label Noise). The paper should cite and compare with them, and highlight the improvement of the model.\n2. Some hyperparameters are important to the model. It is better to give some hyperparameter analysis about the model, such as \\alpha, \\beta. It is suggested to plot the results showing how performance varies with these parameters and report the chosen values.\n3. How does the number of label categories k affect the model? It is recommended to study the effect of the performance.\n4. It is highly recommended to give some examples, i.e., the visualization of the positive and negative influence of different labels in the case studies, showing how certain labels positively or negatively influence others and how this affects the model's predictions.\n5. It is recommended to give other backbones, such as the most commonly used GIN, to show the effectiveness of the model.\n6. It is better to check the label of the axis in the figure. i.e., fig 4c. The label of the x-axis is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2r4SxpqYlA", "reviewer": "Reviewer_SoZZ", "summary": "This paper develops a new method LIP that leverages the propagation strategy to obtain high-order label information in the graph for multi-label node classification . The authors provide the theoretical analysis for the motivation and the proposed method. The extensive experimental results show the effectiveness of LIP on multi-label node classification.", "questions": "My concerns are mainly from two parts: discussions of relation work and designs of experiments.\n\n1.  Actually, decoupled GNNs\\[1,2,3,4,5] have been studied in past a few years. Although the authors are inspired by the theoretical analysis to decouple the propagation module and feature transformation, the previous efforts in decoupled GNNs should be discussed. I have noticed the authors cite APPNP \\[1], one of the representative decoupled GNNs, in Line 263. Here, I suggest the authors open a new subsection in Related Work to comprehensively review recent decoupled GNNs.\n2.  As a plug-and-play, I suggest the authors try more advanced GNNs as backbones for ablation study, such as advanced decoupled GNNs\\[1,3].\n3.  Based on Figure 4(b), I suggest the authors conduct ablation on all other datasets to comprehensively validate the contribution of each module.\n4.  The author claim the efficiency of the proposed method via the time complexity analysis. Maybe the authors can report the computational cost of each methods, including training time cost and GPU memory cost, to strength this contribution.\n\n\n\n[1] Predict then propagate: Graph neural networks meet personalized pagerank, ICLR 2019\n\n[2] On the equivalence of decoupled graph convolution network and label propagation, WWW 2021\n\n[3] Adaptive universal generalized pagerank graph neural network, ICLR 2021\n\n[4] Towards deeper graph neural networks, KDD 2020\n\n[5] Neighborhood Convolutional Graph Neural Network, KBS 2024", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.  This paper is well-written and easy to follow.\n2.  The authors provide the theoretical guarantee for the proposed method.\n3.  LIP shows promising performance on various datasets.", "weaknesses": "1.  The review of related work is not comprehensive.\n2.  The ablation study is inadequate.\n3.  The efficiency study is missing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "DDn6pOEyZo", "reviewer": "Reviewer_SyKm", "summary": "This paper proposes the Label Influence Propagation (LIP) method for multi-label node classification on graph-structured data. The main idea is to model both positive and negative influences between labels by separating the message-passing process into distinct propagation and transformation operations. Additionally, LIP constructs a label influence graph to quantify label-wise importance scores.", "questions": "**Q1.** Could you provide additional explanation of the performance enhancement on heterophilous graphs? It's interesting that LIP consistently enhances performance on these datasets, despite the method appearing to be built upon a homophily assumption.\n\n**Q2.** How does the performance change when varying the $\\beta$ in eq. 12?\n\n**Q3.** Although the authors state that \"multi-label classification on graph data is inherently transductive\" in the Appendix, the inductive setting with partially accessible graph structure is more realistic in many real-world applications. While benchmark datasets are commonly used in a transductive manner, it would be straightforward to modify these datasets for the inductive setting by masking nodes and their corresponding edges in different splits. The authors should consider evaluating LIP under such conditions to verify the practical relevance.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- This paper is well-motivated, emphasizing the importance of multi-label node classification in various domains. The challenge of label correlations and their potential positive and negative influences in non-Euclidean data is clearly explained.\n- The idea of constructing a label graph is interesting.\n- Experimental results demonstrate that LIP achieves notable performance gains across datasets of diverse domains, regardless of the backbone GNNs, highlighting its versatility.", "weaknesses": "**W1.** The writing needs more thorough proofreading. I noticed several grammatical issues, which detract from the overall quality of the paper.\n\nExamples include:\n- \"Illustrate\" should be changed to \"Illustration of\" in Fig. 3 caption.\n- \"contain\" should be \"containing\" in line 300.\n- \"analysis\" should be \"analyze\" in line 313.\n- \"which can be change\" should be \"which can be changed\" in line 320.\n\nAdditionally, table captions should be placed *above* the tables.\n\nSeveral critical errors related to definitions also needs to be revised:\n- \"negative influence\" should be \"positive influence\" in line 301.\n- The eq. 6 seems inconsistent with the textual explanation of positive influence.\n- $\\Omega_j$ may need to be revised to $\\psi_j$ for consistency.\n\n**W2.** The clarity of the paper needs to be improved. For instance:\n- The theoretical justification in Section 4.2 and Appendix A needs more clarity. While the authors assert that the graph structure is a key driver of label influence during propagation, they do not fully clarify how the feature influence $I(i,j)$ and PPR are connected to the proposed label influence metric in the propagation operation. I can infer that positive and negative influences in PPR and feature influence metrics correspond to Equations 6 and 5, respectively, but this connection should be made explicit.\n- Additionally, the augmented form of $\\text{\\textbf A}$ is not clearly defined. Is it a multi-hop adjacency matrix?\n\n**W3.** What are the limitations of the proposed method? The authors didn't include a discussion on the potential limitations of the proposed method.\n\nIf the above concerns and subsequent questions are addressed, I'm willing to raise my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)