PRISM: Partial-label Relational Inference with Spatial and Spectral Cues
Authors: Yiyang Gu
Wenrui Wu
Yifang Qin
Taian Guo
Tao Zhe
Jiaru Tang
Zhiping Xiao
Weizhi Zhang
Ziyue Qiao
Wei Ju
Dongjie Wang
Xiao Luo
Philip S. Yu
Ming Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Weak Supervised Learning
Graph Neural Networks
Relational Inference
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning

Abstract: In many real-world scenarios, acquiring precise labels for graph-structured data is expensive or even infeasible, as reliable annotation often requires substantial expert knowledge or computational resources. As a result, graph labels are often noisy and ambiguous. This challenge motivates partial-label graph learning, where each graph is weakly annotated with a candidate label set containing the true label. However, such ambiguous supervision makes it hard to extract reliable graph semantics and increases the risk of overfitting to noisy candidate labels. To address these challenges, we propose a unified framework named PRISM that performs relational inference with spatial and spectral cues to alleviate the impact of label ambiguity. On the one hand, PRISM captures discriminative spatial cues by aligning prototype-guided substructures across graphs. On the other hand, it decomposes graph signals into multiple frequency bands and extracts global spectral cues with an attention mechanism, which preserve frequency-specific semantics. We integrate these complementary views into a hybrid relational graph and perform an iterative label propagation under candidate constraints. Extensive experiments on a range of well-known datasets demonstrate that PRISM consistently outperforms strong baselines under various noise settings.

Published as a conference paper at ICLR 2026
PRISM: PARTIAL-LABEL RELATIONAL INFERENCE WITH SPATIAL AND SPECTRAL CUES
Yiyang Gu' Wenrui W Yifang Qin', Taian Guo', Tao Zhe?, Jiaru Tang", Zhiping Xiao
Weizhi Zhang", Ziyue Qiao", Wei Ju', Dongjee Wang', Xiao Luo²t, Philip S. Yu², Ming Zhang"t
1 State Key Laboratory for Multimedia Information Processing,
School Computer Science, PKU-Anker LLM Lab, Peking University
2 School of Mathematical Sciences, Peking University
3 Department of Electrical Engineering and Computer Science, University of Kansas
School of Psychological and Cognitive Sciences, Peking University
5 Paul G. Allen School of Computer Science and Engineering, University of Washington
6 Department of Computer Science, University of Illinois Chicago
7 School of Computing and Information Technology. Great Bay University
8 Department of Statistics, University of Wisconsin-Maddion
yi yiyanggu@pku. edu. en, wenzuiwu@stu pku. edu. cn, patxiacQuu. edu, xiaoluo@wisc edu, mzhang es@pku. edu. en
ABSTRACT
In many real-world scenarios, acquiring precise labels for graph-structured data is expensive even infeasible, as reliable annotation often requires substantial expert knowledge or computational resources. As a result, graph labels are of- ten noisy and ambiguous. This challenge motivates partial-label graph learning, where each graph is weakly annotated with a candidate label set containing the label. However, such ambiguous supervision makes it hard extract reliable graph semantics and increases the risk of overfitting to noisy candidate labels. To address these challenges, we propose a unified framework named PRISM that per- forms relational inference with spatial and spectral cues to alleviate the impact of label ambiguity. On the one hand, PRISM captures discriminative spatial cues by aligning mototype-guided substructures across graphs. On the other hand, it de- composes graph signals into multiple frequency bands and extracts global spectral cues with an attention mechanism, which preserve frequency- rrquuecc--ppecffic semanties. We integrate these complementary views into a hybrid relational graph and per- form iterative label propagation under candidate constraints. Extensive exper- iments on a range of well-known datasets demonstrate that PRISM consistently outperforms strong baselines under various noise settings.
INTRODUCTION
Graph-structured data is pervasive across diverse domains such drug discovery, molecular prop- erty prediction, social network analysis. and recommendation systems (Fang et al., 2022; Zhang al., 2021b; Wang al., 2021). To handle such complex structures, Graph Neural Networks (GNNs) (Welling & Kipf, 2016; Hamilton et al., 2017; Xu et al., 2018; Zhang et al., 2021a; Yang al., 2025) have emerged as powerful tools for learning expressive graph representations. GNNs typically operate by recursively aggregating information from node neighborhoods and summarizing node embeddings via global pooling (Gao & Ji, 2019; Lee et al., 2021), They have achieved state-of- the-art results in a wide range of applications, including biomedical classification (Wu et al., 2022; Li et al., 2022a). cross modal retrieval (Chen et al., 2022), and event understanding (Liu et al., 2023).
Despite these advances, existing graph classification frameworks still highly data hungry: they require accurate labeled samples to learn a discriminative classifier (Li et al., 2022b; Rousseau al.,
Equal contribution.
Corresponding authors.

---

Published as a conference paper at ICLR 2026
2015). However, in many practical scenarios, acquiring ground-truth labels is expensive techni- cally infeasible. For instance, identifying the properties of chemical compounds often depends on density functional theory (DFT) simulations (Becke, 2014), which can be expensive and time- consuming. To alleviate this problem, some automated tools are often employed to assist with the annotation process. However, this approach can introduce label ambiguity, as different tools may lead to inconsistent annotations. These noisy labels can pose significant challenges to the training of graph classifiers. Although self-supervised graph learning methods such as GraphCL (You al., 2020) have alleviated the reliance on labels by using contrastive objectives to learn graph representa- tions during pre-training, they still depend on accurate labels train a classifier during downstream classification stages. Their performance tends to degrade significantly under label ambiguity.
In this paper, we focus on a practical yet underexplored setting: Partial-label Graph Learning (PLGL). Each graph is annotated with a candidate label set that contains the true class label, but the exact ground-truth is unknown. This situation commonly arises when labels are generated from automated tools or coarse taxonomy (Ge et al., 2022; Gu et al., 2024). While partial label learning has been explored in computer vision (Feng & An, 2019; Lyu et al., 2020), PLGL presents unique challenges due to the structural complexity and non-Euclidean nature of graphs. First, ambiguous supervision introduces semantic uncertainty, making it difficult to capture dlass-iisrimminttvee sub- structures. Second, GNNs tend overfit noisy signals, particularly when candidate sets contain semantically similar labels. Third, graphs exhibit patterns at multiple structural resolutions, from local motifs global topology, which cannot be effectively captured by global pooling. Recent works have explored weakly supervised graph classification using pseudo-labeling (Ju et al., 2023b; Gu et al., 2025b) or contrastive learning (Yue et al., 2022; Luo et al., 2023), but they face two limita- tions: (i) reliance on overconfident predictions, leading to error accumulation under label ambiguity; and (ii) lack of explicit use of structural and spectral diversity to distinguish candidate labels.
To bridge this gap. we introduce a unified framework PRISM for Partial-labe Relational Inference with Spatial and Spectral Modeling. PRISM alleviates the impact of label ambiguity through three mechanisms. First, it aligns prototype-guided substructures across graphs to extract spatial cues, which can uncover class diisssddirrimiaaiiee local patterns against the label ambiguity. Second, it decom- poses graph signals into multiple frequency bands to encode spectral cues. We propose multi-band attention mechanism that preserves rrequency-speciffe semantics critical for global structural under- standing. Third, hybrid relational graph is constructed to integrate both spatial and spectral cues. We then employ a label propagation mechanism to refine supervision signals iteratively. We fur- ther utilize momentum- update of soft label confidence matrix under candidate constraints, which suppresses noise accumulation and facilitates robust optimization.
The contributions of this paper can be summarized in three points: (1) Understudied Problem. We study an understudied problem of partial-label graph learning, which has extensive practical appli- cations in various domains. (2) Novel Framework. We propose novel relational inference frame- work named PRISM. It leverages relational propagation to integrate spatial and spectral cues for label disambiguation.
(3) Extensive experiments. We validate PRISM across diverse benchmarks and demonstrate its superiority over existing weakly supervised and graph learning approaches.
2 BACKGROUND
Problem Definition, Let 9 = (G, = (V;, &,, X.)) denote a collection of N graphs, where each graph G; consists of a node set V,, edge set E,, and node features X, E [xd We denote by A, E {0, 1]llIII the adjacency matrix of & For each graph G,, we are given a candidate label set S C V. where y = {1.2.... C} is the complete label space. The candidate set S, includes the true label yf but does not reveal which one is correct. Our objective is to learn a graph classifier ((.;;) that predicts the ground-truth label y for each graph in the test set, by training only on ambiguous candidate sets without access to ground-truth supervision.
Graph Neural Networks. Graph Neural Networks (GNNs) are widely used to encode graph struc- tures by recursively aggregating information from node neighborhoods. At each layer I, the repre- sentation of node is updated by combining its own embedding with messages from its neighbors:
(1) = 1000 (n!-1), 1,000 ((bl-")Jeevee
(1)
2

---

Published as a conference paper at ICLR 2026
(A)
Subetrocture
Chass-aware
Y(1) E ER
GNN
Prototype Attention
:sspa
A Aspe
Prototype Bank
Query
Subarmeture Similarity
(B)
[u Ug.
UN
Mulki-band Similarity
p(
p(22)
Relational Inference
p(AT)
(A1; An, AN}
OOOOO
y(++1)
Constmint Mask
p(Ax)
Figure 1: Overview of PRISM. Our framework jointly models spatial substructures (A) and spectral frequency patterns (B) to disambiguate partial labels. Prototype-guided -updddd attention and multi-band spectral encoding form relational graph for iterative label refinement under candidate constraints.
where w(()) and (( are the aggregation function and the combination function, respectively, and (Nv) denotes the neighbor set of node v. After L layers, node embeddings (hl (h(")) heev are aggre- gated into graph-level representation using readout function:
g READOUT (InS))) )nvv)
where READOUT can be sum, mean, or pooling methods. These graph representations provide the basis for downstream tasks such as graph-level classification.
3 METHODOLOGGY
This paper introduces a novel framework PRISM for partial-label graph learning that integrates lo- cal substructural cues and global spectral cues to resolve candidate label ambiguities. Each graph encoded through two complementary pathways: a spatial encoder captures discriminative spatial cues by aligning prototype-guidee poses graph signals into distinct fireuuency bands, capturing both smooth and non-smooth structural patterns. These dual pathways induce relational graph with types of edges: encoding prototype-basel substructure similarity, the other reflecting spectral affinity across graphs. We then perform iterative propagation which enables the model to distill consistent label cues from noisy candidates and refine the super- vision signals. The overview of PRISM illustrated in Figure
substructures across graphs, while spectral encoder decom-
this graph fuse information from both relational types,
3.1 SPATIAL CUES VIA SUBSTRUCTURE MATCHING
In partial-label graph learning, the true label of each instance is hidden within a noisy candidate set, where multiple labels may be semantically correlated. Relying solely on global graph repre- sentations may blur these distinctions, since graphs with overlapping candidate labels can exhibit similar overall topology. In contrast, local substructures frequently encode the most discriminative evidence for class separation. Motivated by this observation, design a structure-aware disam- biguation module that aligns prototype-guice substructures across related instances, which helps uncover consistent label semantics under ambiguity.
To incorporate class-level semantic priors, we maintain a comnentum-updatee prototype bank {pe e R RF) Joyy, where each prototype Pe tracks the aggregated global representation of graphs associated with candidate label c. At training step j. we update each prototype as:
1
( p (-11) (1 m)
gi
(3)
B.
i
3

---

Published as a conference paper at ICLR 2026
where 9i denotes the global embedding of graph G2, E (0, 1) is the momentum coefficient, and Be is the set of current-batch graphs containing label e in their candidate set. Based on the prototype bank, apply a protorype-guide attention mechanism to extract C substructure embeddings per graph, where each embedding is aligned with a candidate class. Given the node embeddings from the final GNN layer (he heen and the full prototype set {pele attention weights are computed to obtain class-aware aware latent components:
exp(h
(L)T Pc)
Σ Qee h( where Ove DEV;
(4)
Ev exp(h (L) Pc)
The resulting embeddings (r[") stream comparison. We then construct relational graph over graph pairs that share at least one candidate label. Let {(G,, Gý) S, S * 0, + j} denote the set of such graph pairs. For each pair (Ge, Gý) E P, we define prototype-ave awarre substructure similarity:
Je=1 serve interpretable and class-specific substructures for down-
(c)
(c)
2po 83
max COS cES,rS,
(()) COS
rr
Pe
(S)
spa scores to form a sparse rela- For each graph, we retain its top-ka neighbors with the highest sú tional graph with a normalized adjacency matrix A that encodes substructure-level agreement under label semantics. This spatial reasoning module provides fine-grained structural information, thereby enhancing label disambiguation by promoting relational consistency among structurally aligned graph instances.
3.2 SPECTRAL CUES MULTI-BAND FREQUENCY ATTENTION
While the spatial disambiguation module focuses on extracting local spatial cues, graph spectra offer complementary global perspective by capturing both low-frequency smoothness and high- frequency irregularities. However, many existing spectral methods combine spectral components through linear aggregation across eigenmodes (Yang et al., 2022; Bo et al., 2023). Such aggregation mixes signals from different frequencies into single representation, which may blur structurally diverse signals and obscure frequency-specte speciifc patterns that are crucial for graph understanding. We thus propose
Frequency Attention module, which not only synthesizes spectral infor- mation into a unified form but also retains frequency-specinf characteristics by explicitly modeling bands. Specifically, our method: (1) preserves the resolution of each frequency band by constructing explicit band-wise representations, and (2) provides fine-grained cross-graph reasoning from band- level similarity comparison. This architecture allows for frequency- aware graph embeddings. which concentrate on informative spectral patterns while suppressing the noise of less crucial bands.
Given graph G with normalized Laplacian cigenvalues {A1,A2, ......, Av) and corresponding eigen- vectors [u, u2,..., uN). harmonic expansion:
we first project scalar spectral values into learnable signal space using
((A = (sin(k)), cos(())) W.
(6)
where W, E R2Kxd is a shared learnable projection matrix, and K is the number of periods. For efficiency, only consider the T smallest eigenvectors, therefore producing T distinct frequency embeddings, where each embedding serves filtered spectral descriptor of the graph. To construct band-specific node representations, we modulate the p-th eigenvector up E E. with its associated harmonic encoding p()p) to form:
( up p(pp) E Rxd.
where @ denotes the outer product broadcast across all nodes. We then apply a multi-layer neural network fahared, shared across frequency bands, to each (p) to extract spectral signals. For each band E {1,.... (I....,T) T),, we compute the corresponding graph-level embedding as:
(p)
READOUT (fanrred X x(1)))
(
where READOUT denotes a readout function that integrates node embeddings. This yields set of band-level embeddings (1) ...., 2(T) that capture spectrally filtered representations of the graph
4

---

Published as a conference paper at ICLR 2026
across multiple frequency perspectives. To synthesize multi-scale spectral signals, employ a soft attention mechanism across bands:
T
(r)))()) where (0) exp (a LaTooWas (Wz(1)))
2
ΣS exp (a o (W
pm
Here, W and a are learnable parameters, and (-)) denotes nonlinear activation function. For cross-graph spectral reasoning, we compute band-wise similarity between graphs. Let G, and Gj denote two graphs with band embeddings { p= and {z) (2))) defined as:
(2
J==1 respectively, Their similarity
(2(()) 1 .2 (p)
spe Ej
COS Pe (1.....)
max
(10)
To ensure label-aware alignment, we restrict edges to graph pairs with overlapping candidate sets, i... S n S * 0. Each graph links to its top-ke most similar neighbors, forming relational graph with normalized adjacency matrix A spe that supports label disambiguation from the spectral perspective.
We theoretically establish that both T and A she contribute to label disambiguation, Intuitively, the distribution of hidden node embeddings should be determined by the prototype of the true label to a certain degree. Building on this observation, we present the following theorem with proof provided in Appendix A:
Theorem 1. Assume E [n =c] Pe: Vo E V. Tik = P (A: (j, = 1) is random variable
whose distribution can be determined by vl. and mimgggNN 2 (0) 2 6 for some
5 > 0. Then, we have for any i.j E (1.2,...,N7 N}:
PAA = 1/y? = =vī) +
(11)
and
P (A = 1,y² = v3)) +
(12)
as [Vi, 1131 + cc.
Theorem 1 suggests that graph and j shares the same true label, the probabilities of A and A 3j
sm being will both converge to 1, which works on the subsequent label propagation with disam-
biguation from noisy candidate sets.
3.3 LABEL DISAMBIGUATION VIA RELATIONAL INFERENCE
Based on the relational graph constructed in previous modules, which encodes spatial proximity and spectral correlation distinct relational types, we develop iterative label propagation framework to enhance supervision under partially labeled settings where ground-truth labels are inaccessible. This framework integrates complementary structural and spectral signals refine soft supervision progressively, while rigorously enforcing candidate label constraints throughout the entire refine- ment process to ensure both semantic validity and training stability.
Specifically, denote the initial label matrix by (0) E N At each iteration e, the label matrix is updated using two normalized adjacency matrices, i.e., A and Aspe, The propagation rule is:
(e+1) μ ( + 11) W (A (e)
A (1)))
(13)
where μ E (0, 1) controls the update momentum, and N((-) denotes row-wise & normalization. We further apply a binary mask M E {0, NJ to constrain label assignments to valid candidate classes, where Mie- 1 and only if E S, and Mic otherwise:
( N (ÿlet)) o M).
(14)
where 2 denotes element- wise multiplication. After E iterations, the refined label matrix ( cap- tures relatinnll consistency while remaining faithful to partial supervision, enabling effective disambiguation of noisy candidate labels.
5

---

Published as a conference paper at ICLR 2026
We further maintain soft label confidence matrix Q E RN to stabilize optimization, which is uniformly initialized on the candidate label set. We utilize the soft labels Y(E) inferred from relational propagation to update Q gradually. The update follows an exponential moving average (EMA) scheme:
Q: - N ( B- Q: ()-))------)))0))))( B)
(15)
where 3 E (0.1) is the momentum coefficient. This mechanism promotes stable refinement of the supervision signals during training.
3.4 UNIFIED TRAINING OBJECTIVE
We adopt unified objective that couples the soft confidence target with the candidate constraint train our framework effectively. Specifically, we first apply an MLP-based classifier to the spatial- view embeddings g to obtain the final predictions pspa E RNNxC In parallel, we employ distinct classifier that projects the spectral-vies embeddings & to Pspe E R NxC The training loss for the spatial (spectral) view defined as the negative marginal oogliikelhoodd over the candidate label set:
B Σ log Σ 1=1
sup = B
1 te
Qies
o E (spa, spe),
(16)
rES,
where S; is the candidate label set for sample and B is the batch size. This formulation encourages the model align predictions with the soft label confidence within the candidate label set. We then optimize the spatial and spectral objectives jointly to capture complementary graph characteristics:
C = Cape + suup
(17)
This dual-view supervision facilitates robust label disambiguation. We further offer a theoretical analysis of the proposed method, particularly focusing the convergence of the label confidence matrix and training loss under certain conditions. To begin with, let Y [ {0, 1 NxC be the matrix consisting of ground-trute one-hot label vector. Denote the classifier as felassi which produces the label prediction matrix P, the final predicted label confidence vector of graph G; is P. = felassifies füer (g:). If the classifier is well-trained, it should recover label from P. since p. is the prototype of label c. Based on this, we have the following results with the proof in Appendix B:
Theorem 2. Under the assumption of Theorem I, further assume fclossifier (pe) lc. Ve y where Le E {0, 13 denotes one-hot vector whose e-th component is while the rest are 0, we have:
0.3.
(18)
as [Vd, E - 00. And
E (.sup) + 0
(19)
as [il, E - oc.
Theorem 2 indicates that if each graph has enough node information and we conduct enough iter- ations, the soft label confidence matrix updated by EMA will converge to the ground-truth and the training loss will tend to zero, which further implies our framework can resolve label ambiguity by aligning prototype-guit gugddd substructures across graphs. The condition [V]] by B, N + oo to a certain degree, since graphs with the same label and candidate label set can be regarded as whole, and the whole number of nodes tends to infinity when B,N -> 00.
can be replaced
3.5 COMPUTATIONAL EFFICIENCY ANALYSIS
Let [V] be the number of nodes, |8] the number of edges, d the feature dimension, I the number of GNN layers, and T the number of spectral bands. In preprocessing, we compute the T smallest eigenvectors and their spectral encodings, which are reused throughout training. During training, the spatial view performs message passing with complexity O(L (d), while the spectral view operates on pre-computed features across T bands and applies shared MLP, resulting in total cost of OTT)(d) (d). Since L and T are small constants, the overall training complexity is ([E)d), which is linear in the number of edges and consistent with standard GNN-based methods.

---

Published as a conference paper at ICLR 2026
Table I: The compared accuracy (mean%- on different graph classification datasets. The best results are highlighted in boldface and the second best results are underlined, PT E Y Y # y) reflecting the level of label ambiguity.
Datasets
ENZYMES
Litt
COIL-DEL
CIFARIO
COLORS-3
Mothods
y=
4=
0.5
0.3
0.3
== 0.05
9= 0.1
q 0.3
4=055
q= 0.3
q= 0.5
GCN
48
40.22gam
44.00
35.94
is 50.43gun
41.63gi0
43.68
41.35
74.87
60.67
GAT
49.11=25s
34.67
61.33ss4
53.04
59.77aum
46.63s134
52.93
48.54
71.83smm
62.56
GIN
47.11=4m
34.22etm
50.43aus
35.59a11s
46.23suum
37.29
43.91=ae
41.24
48.17:s
41.00
GraphSAGE
47.33
39.33g
70.96.1
60.35g
58.91gie
49,23gmm
47.44
71.24
56.63g94
TopKPooo
44
36.00
55.25
43.83g5
44.83
34.63
48
42.87am
26.69
SACiPool
46.67-125
37.11
14.71
39.30as.
30.17 44.89
50.01 ca.
45.16
54,91
24.62
EdgePool
51.11
33.33
64. 17a74
55,36g11
56.74
45.892131
50.
45.90
76.96
ASAP
44.44.33s
31.56
65.04
52.75
46.20
34,94,342
50.10
44.8
62.47
Graph Transplant
51.78.239
43.78
14.84
66.78
66.57
57.11
53.79
48.95
34.66.130
62.72
PICO
46.88:179
35.78
73.562131
64. 24.63
76.25
63.09
23,47
46.042mm
23.99
34.74amm
TGNN
53.33
42.22
59.83g 70.43400
62.28g
50,20g
00M
00M
75.84
63.95
GraphCL
54,22:334
39.78
72,00
62.49
69.94
60.17:225
:3.57
48. 18.10
52.89
61.55
GraphACL
54,44:235
44789.4m
69. 19.80
57. =1s
71.40suu
60.29
53.25
47. 17.8
73,84
63,57
DEFR
58.22:a>
47
80. 12
72.29
79.94
68.03a1
-7.08
52.48
PRISM (Ours)
63.11
g1.33
82.55
78.32g
85.69g
19,48.144
58.29_au
91,93
80.57g3w
4 EXPERIMENTS
4.1
EXPERIMENTAL SETUP
Datasets. To comprehensively assess the performance of PRISM, we conduct experiments on five established graph classification benchmarks spanning the bioinformatics and vision domains: EN- ZYMES (Schomburg et al., 2004), Letter-High High (Riesen & Bunke, 2008), COIL-DEL (Riesen & Bunke, 2008), CIFARIO (Dwivedi et al., 2020), and COLORS-3 (Knyazev et al., 2019). Fol- lowing (Gu et al., 2024), we randomly inject false positive labels into the candidate set to gen- erate partial-label data. Specifically, each incorrect label 7 # y" is included with probability q = P E S T A y*), controlling the level of label ambiguity. A higher q indicates noisier candi- date supervision. We vary E {0.1, 0.3, 0.5} for the majority of datasets, and q E {0.02, 0.05, 0.1} for COIL-DEL to account for its larger label space.
Baselines. We compare the proposed PRISM with comprehensive set of baselines across multi- ple paradigms: (a) Graph neural networks: GCN (Welling & Kipf, 2016), GAT (Veličković et al., 2017), GIN (Xu et al., 2018), and GraphSAGE (Hamilton et al., 2017); (b) Hierarchical graph pool- ing methods: TopKPool (Gao & Ji, 2019), SAGPool (Lee et al., 2019), EdgePool (Dichl, 2019), and ASAP (Ranjan al., 2020), all using GraphSAGE
the backbone; (c) Graph augmenta- tion method: Graph Transplant (Park et al., 2022); (d) Unsupervised contrastive graph learning: GraphCL (You et al., 2020) and GraphACL (Luo et al., 2023); (e) Semi-supervised graph learning: TGNN (Ju et al., 2023b); (f) Partial label learning in vision: PiCO (Wang et al., 2022), adapted to the graph setting with a GraphSAGE encoder for fair comparison; (g) Partial label learning for graphs: DEER (Gu et al., 2024). Further details on the baselines are provided in the Appendix E.
Implementation and Evaluation Protocol. All experiments are implemented using PyTorch with the PyG backend. We use a two-layer GraphSAGE with 512 hidden units as the shared encoder across all methods. Training performed using the Adam optimizer (Kingma & Ba, 2014) with an initial learning rate of 0.001 and batch size of 128. All these results are averaged over five independent runs with individual seeds, each reporting mean accuracy and standard deviation. More details about the implementation are provided in the Appendix F.
4.2 PERFORMANCE COMPARISON
We report the quantitative results of our PRISM against competitive baselines under various am- biguity levels in Table 1. According to the results, make the following observations: (1) Our PRISM consistently achieves superior performance across all datasets and various ambiguity set- tings. It surpasses all baselines by considerable margin. For example, ENZYMES, our method
7

---

Published as a conference paper at ICLR 2026
Table 2: Ablation study on ENZYMES, Lether-High, and CIFARIO.
Datasets
ENZYMES
Letter High
CIFARIO
Variants
q = 0.3
q 0.5
0.5
q 0.3
4 = 0.5
q q= 0.3
q= 0.5
PRISM w/o Sub
61.78-206
49,56=35s
80.70+1.0
76.11-21
56.65#1
53.30
PRISM w/o Spa
60.89_>.
19.65 48.
5 74.72.0m
1
51.72
PRISM w/o Spe
61.55
48.89
80.17104s
76.46
55.7220m:
52.65114z
PRISM w/o Rel. Infer
57.78=2.1
45.11
78.43+1.8
71.24=218
53,61
49.79
PRISM (Full Model)
:3.11:
82.55 :3.
78.32:1.1
a8.29:.a3
55.10
30.0
01.0
30.0
08.0
ACAP
60.0
K200
Ougarn
Flysing Probubiliyy
Ausrage Sizw of Candidate Sets
(a) CIFARIO
(b) Lett
(c) ENZYMES
(d) Letter-Higg
Figure 2: (a) Performance comparison in scenarios with hierarchical label noise. (b) Performance comparison in scenarios with competitive label noise. (c)(d Performance w.r.f. top-ki and top-k. on ENZYMES and Ligh.r-High.
outperforms the second-best by 8.3% under 0.3, confirming its robustness and generalization under weak supervision. (2) On fine-graing the-grained datasets such as COIL-DEL, where class granularity and semantic ambiguity are pronounced, PRISM retains strong advantage over baseline methods. On COIL-DEL with q = 0.1, it attains 79.48% accuracy, exceeding the prior best (DEER, 68.03%) by 16.8%, showing effective candidate label disambiguation via complementary spatial and spectral cues. (3) Compared to the previous partial label learning methods, our framework consistently im- proves performance across all graph datasets. Although PiCO with GraphSAGE encoders is adapted to graphs, it still performs poorly, demonstrating the limits of directly transferring CV-based meth- ods and the necessity of graph-specific modeling. (4) As label ambiguity q increases, most baselines degrade sharply, whereas our PRISM exhibits a much slower decline. This robustness stems from integrating spectral and substructural reasoning, with an iterative label propagation mitigating noisy and misleading supervision. More results under 0.1 are provided in Appendix D.
Semantically Correlated Label Noise. In many real-world scenarios, labels are not independent but semantically correlated, leading to candidate sets that contain noisy labels with stronger affin- ity to the ground-truth than unrelated classes, thereby introducing additional challenges for robust learning. An important question is whether PRISM can reliably address such semantically entan- gled label ambiguity. To evaluate this, we design two experimental protocols: (1) Hierarchical label noise. We exploit the coarse-to-fine taxonomy of CIFARIO (i.c., vehicles vs. animals) and introduce noise by flipping negative labels within the same super-class as the true label with probability q, thereby forming semantically plausible candidates. (2) Competitive label noise. Following (Yan & Guo, 2023), we pretrain graph neural network (GNN) on clean data to capture inter-class semantic dependencies. We then randomly select noisy candidates from the Top-K predictions of this GNN, with K = 6 for Letter-High, High, and vary the candidate set size by adjusting sampling ratios. The results presented in Figure 2 (a)(b). We can that our PRISM consistently outperforms all baselines under both noise schemes across different ambiguity levels, thereby highlighting its robustness to semantically correlated label noise.
4.3 ABLATION STUDY
To assess the contribution of each core component in PRISM, we conduct ablation experiments on ENZYMES, Letter-High, and CIFARI0 under noise levels = 0.3 and 0.5, with results in Table 2. Removing substructure alignment (PRISM w/o Sub) and replacing class-speciffe matching with holistic graph embeddings causes clear performance drops, especially under high ambiguity, showing that discriminative substructure cues outperform coarse comparisons. Excluding the spatial branch (PRISM w/o Spa) further reduces accuracy, as the absence of neighborhood-awaal signals
8

---

Published as a conference paper at ICLR 2026
Class
conii 2
Class
Class-specific attention maps reveal consistent focus on discriminative substructures across graph instances within different categories.
Figure 3:
weakens the capture of fine-grained topology critical for resolving label ambiguity, particularly in CIFARIO. Discarding the spectral attention module (PRISM w/o Spe) also adversely impacts per- formance, since multi-band decomposition can capture global spectral characteristies, which com- plement local structure. Furthermore, removing the relational inference module (PRISM w/o Rel. Infer) yields the sharpest degradation, indicating that graph-of-graphe modeling and label propaga- tion are indispensable for alleviating the impact of label noise.
4.4 SENSITIVITY ANALYSIS
We analyze the effect of the number of neighbors retained in the spatial and spectral relational graphs, i.e., hi and kic. The results are shown in Figure 2 (c) We can see that accuracy generally increases as k2 and k grow from 1 moderate values, then saturates or slightly declines. Maybe the reason is that adding structurally spectrally aligned instances improves cross-graph consistency by enhancing the density reliable signals. However, overly dense connectivity introduces noisy or weakly correlated neighbors, potentially causing label propagation drift. Our model achieves stable performance under broad range values, reflecting its robustness to hyperparameter choices in relational graph construction.
4.5 VISUALIZATION OF CLASS-SPECINI ATTENTION
We visualize class-specific attention maps from the ENZYMES dataset in Figure Each sub- graph represents different graph instance, and the color of each node indicates its attention weight relative to the corresponding class prototype. Warmer colors signify a higher contribution to the class-specific substructure reasoning. Although the graph structures vary, nodes with high attention consistently correspond to meaningful substructures such as motifs, central connectors, or functional cores, while irrelevant or peripheral nodes receive lower attention. This consistent focus within each class highlights the model's 's ability to identify semantically aligned substructures across diverse graphs and yield human-intesn interppitterreeablle views of functionally significant topological regions.
5 CONCLUSION
In this paper, we study the problem partial-lahel graph learning, where every graph is associated with noisy candidate label set. We propose relational inference framework named PRISM to ad- dress the challenges semantic uncertainty and structural complexity in this problem. PRISM first integrates spatial substructure alignment and spectral frequency modeling via relational graph. We then leverage an iterative label propagation mechanism with candidate constraints to disambiguate supervision signals. Extensive experiments tiveness and robustness our PRISM under various ambiguity levels, highlighting its potential as principled solution for learning from weakly supervised graph data.
range of widely- datasets validate the effec-

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
Ming Zhang and Yiyang Gu are supported by grants from the National Key Research and Devel- opment Program of China with Grant No. 2023YFC3341203 and the National Natural Science Foundation of China (NSFC Grant Number 62276002).
REFERENCES
Axel D Becke. Perspective: Fifty years of Censity-functionn theory in chemical physics. The Journal of chemical physics, 140(18):1A331, 2014.
Deyu Bo, Yuan Fang, Yang Liu, and Chuan Shi. Graph contrastive learning with stable and scalable spectral encoding. Advances Neural Information Processing Systems, 36:45516-45532, 2023,
Dapeng Chen, Min Wang, Haobin Chen, Lin Wu, Jing Qin, and Wei Peng. Cross-modal retrieval with heterogeneous graph embedding. In Proceedings of the 30th ACM International Conference on Multimedia, pp. 3291-3300, 2022.
Timothee Cour, Ben Sapp, and Ben Taskar. Learning from partial labels. The Journal of Machine Learning Research, 12:1501-1536, 2011.
Frederik Diehl.
Edge contraction pooling for graph neural networks. arXiv:1905. 10990, 2019.
arXiv preprint
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Xiaomin Fang, Lihang Liu, Jieqiong Lei, Donglong He, Shanzhuo Zhang, Jingho Zhou, Fan Wang, Hua Wu, and Haifeng Wang. Geometry-eehanced molecular representation learning for property prediction. Nature Machine Intelligence, 4(2):127-133 2022.
Lei Feng and Bo An. Partial label learning by semantic difference maximization. In IJCAI, pp- 2294-2300, 2019.
Hang Gao, Jiaguo Yuan, Jiangmeng Li, Peng Qiao, Fengge Wu, Changwen Zheng, and Huaping Liu. Graph partial label learning with potential cause discovering. arXiv preprint arXiv:2403.114 2024.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In international conference on machine learning, pp. 2083-2092. PMLR, 2019.
Lingchi Ge, Min Fang, Haikun Li, and Bo Chen. Label correlation for partial label learning. Journal of Systems Engineering and Electronics, 3343: 2022.
Yiyang Gu, Zihao Chen, Yifang Qin, Zhengyang Mao, Zhiping Xiao, Wei Ju, Chong Chen, Xian- Sheng Hua, Yifan Wang, Xiao Luo, et al. Deer: Distribution divergence-bass graph contrast for partial label learning graphs. IEEE Transactions Multimedia, 2024.
Yiyang Gu, Binqi Chen, Zihao Chen, Ziyue Qiao, Xiao Luo, Junyu Luo, Zhiping Xiao, Wei Ju, and Ming Zhang. Mate: Masked optimal transport with dynamic selection for partial label graph learning. Artificial Intelligence, pp. 104396, 2025a.
Yiyang Gu, Taian Guo, Hang Zhou, Zihao Chen, Zhiping Xiao, Yifang Qin, Xiao Luo, Wei Ju, Yifan Wang, and Ming Zhang. Code: Towards partial label graph learning via coupled dual separation. In Proceedings of the 33rd ACM International Conference on Multimedia, pp. 9949,8958, 2025b.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Eyke Hüllermeier and Jürgen Beringer. Learning from ambiguously labeled examples. In Advances in Intelligent Data Analysis VI: 6th International Symposium on Intelligent Data Analysis, IDA 2005, Madrid, Spain, September 8- 10, 2005. Proceedings 6. pp. 168-179. Springer, 2005.
10

---

Published as a conference paper at ICLR 2026
Wei Ju, Yiyang Gu, Xiao Luo, Yifan Wang, Haochen Yuan, Huasong Zhong, and Ming Zhang. Unsupervised graph-level representation learning with hierarchical contrasts. Neural Networks, 158:359-368, 2023a.
Wei Ju, Xiao Luo, Meng Qu, Yifan Wang, Chong Chen, Minghua Deng, Xian-Sheng Hua, and Ming Zhang. Tgnn: joint semi semi-supervised framework for graph-level classification. arXiv preprint arXiv:2304. 1688, 2023b.
Wei Ju, Zheng Fang, Yiyang Gu, Zequn Liu, Qingqing Long, Ziyue Qiao, Yifang Qin, Jianhao Shen, Fang Sun, Zhiping Xiao, et al. A comprehensive survey on deep graph representation learning. Neural Networks, 173: 106207, 2024.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1rXiv:1412.69800 2014.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. Advances in neural information processing systems, 32, 2019.
Dongha Lee, Su Kim, Seonghyeon Lee, Chanyoung Park, and Hwanjo Yu. Learnable structural semantic readout for graph classification. In 2021 IEEE International Conference on Data Mining (ICDM), pp. 1180-1185 IEEE, 2021.
Junhyun Lee. Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International confer- ence on machine learming, pp. 3734-3743, PMLR, 2019.
Michelle M Li, Kexin Huang, and Marinka Zitiik. Graph representation learning in biomedicine and healthcare. Nature biomedical engineering, 6(12): 2022a.
Sihang Li, Xiang Wang, An Zhang, Yingxin Wu, Xiangnan He, and Tat-Seng Chua. Let invariant rationale discovery inspire graph contrastive learning. In International conference on machine learning, pp. 13052-13065 PMLR, 2022b.
Meng Liu, Ke Liang, Dayu Hu, Hao Yu, Yue Liu, Lingyuan Meng, Wenxuan Tu, Sihang Zhou, and Xinwang Liu. Tmac: Temporal
graph learning for acoustic event classification. In Proceedings of the 31 ACM International Conference on Multimedia, pp. 3365-336777 2023.
Xiao Luo, Wei Ju, Meng Qu, Yiyang Gu, Chong Chen, Minghua Deng, Xian-Sheng Hua, and Ming Zhang. Clear: Cluster-enhanced contrast for self-supervised graph representation learning. IEEE Transactions on Neural Networks and Learning Systems, 35(1):899 912, 2022.
Xiao Luo, Wei Ju, Yiyang Gu, Zhengyang Mao, Luchen Liu, Yuhui Yuan, and Ming Zhang. Self- supervised graph-level representation learning with adversarial contrastive learning. ACM Trans- actions Knowledge Discovery from Data, 18(2):1-23, 2023.
Gengyu Lyu, Songhe Feng, Tao Wang, and Congyan Lang. self-paced regularization framework for partial-label learning. IEEE Transactions on Cybernetics, 52(2):899-911, 2020.
Mourad Oudghiri. Weyl's theorem and perturbations. Integral Equations and Operator Theory, 53 (4):535-545, 2005.
Joonhyung Park, Hajin Shim, and Eunho Yang. Graph transplant: Node saliency-guided graph mixup with local structure preservation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 7966-7974, 2022.
Ekagra Ranjan, Soumya Sanyal, and Partha Talukdar. Asap: Adaptive structure aware pooling for learning hierarchical graph representations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 5470-5477, 2020.
Kaspar Riesen and Horst Bunke. lam graph database repository for graph based pattern recognition and machine learning. In Joint IAPR International Workshops Statistical Techniques in Pat- tern Recognition (SPR) and Structural and Syntactic Pattern Recognition (SSPR), pp. 287-297. Springer, 2008
11

---

Published as a conference paper at ICLR 2026
François Rousseau, Emmanouil Kiagias, and Michalis Vazirgiannis. Text categorization graph classification problem. In Proceedings of the 53rd Annual Meeting of the Association for Compu- national Linguisties and the 7th International Joint Conference on Natural Language Processing (Volume I: Long Papers), pp. 1702-1712, 2015.
Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 22(suppl.),D431--445 2004.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lhmman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
Vinesh Solanki, Patrick Rubin-Delanchy, and lan Gallagher. Persistent homology of graph embed- dings, 2021. URL httpt: org/
wtw./aa/////aaa.aaae...../..aaee abs
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Haobo Wang, Ruixuan Xiao, Yixuan Li, Lei Feng, Gang Niu, Gang Chen, and Junbo Zhao. Pico: Contrastive label disambiguation for partial label learning. In Proceedings of the International Conference on Learning Representations, 2022.
Qifan Wang, Yinwei Wei, Jianhua Yin, Jianlong Wu, Xuemeng Song, and Liqiang Nie. Dualgon: Dual graph neural network for multimedia recommendation. IEEE Transactions on Multimedia, 25:1074-1084, 2021.
Wei Wang and Min-Ling Zhang. Partial label learning with discrimination augmentation. In Pro- ceedings of the International ACM SIGKDD Conference on Knowledge Discovery & Data Min- ing, pp. 1920-1928, 2022.
Max Welling and Thomas N Kipf. Semi-supervised classification with graph convolutional net- works. In J. International Conference on Learning Representations (ICLR 2017), 2016.
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling, In International conference on machine learning, pp. 24017-24030. PMLR, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
Yan Yan and Yuhong Guo. Mutual partial label learning with competitive label noise. In The Eleventh International Conference on Learning Representations, 2023.
Junwei Yang, Yiyang Gu, Yifang Qin, Xiao Luo, Zhiping Xiao, Kangjie Zheng, Wei Ju, Xian-Sheng Hua, and Ming Zhang. Towerdna: Fast and accurate graph retrieval with dividing, contrasting and alignment. IEEE Transactions on Knowledge and Data Engineering, 2025.
Mingqi Yang. Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin. A new perspective on the effects of spectrum graph neural networks. International Conference on Machine PMLR, 2022.
Learning. pp.
Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. In Advances in Neural Information Processing Systems, 2020.
Yi Yu. Tengyao Wang, and Richard Samworth. A useful variant of the davis- theorem for statisticians. Biometrika, 102(2):315-323, 2015.
Han Yue, Chunhui Zhang, Chuxu Zhang, and Hongfu Liu. Label-invariant augmentation for semi- supervised graph classification. Advances in Neural Information Processing Systems, 35:29350- 29361, 2022.
Tong Zhang, Yun Wang, Zhen Cui, Chuanwei Zhou, Baoliang Cui, Haikuan Huang, and Jian Yang. Deep wasserstein graph discriminant learning for graph classification. In Proceedings of the AAA! Conference on Artificial Intelligence, volume 35, pp. 10922, 2021a.
12

---

Published as a conference paper at ICLR 2026
Zaixi Zhang, Qi Liu, Hao Wang. Chengqiang Lu, and Chee- Kong Lee. Motif-based graph self- supervised learning for molecular property prediction. Advances in Neural Information Process- ing Systems, 34:15870-15882, 2021b.
13

---

Published as a conference paper at ICLR 2026
A PROOF OF THEOREM
To begin with, we denote adjacent matrix of graph i as A for the sake of convenience, take READOUT function as the mean in (2) that yi [Vi Evev, he Since Pe is the prototype of label assume the latent representations of nodes satisfy
E 1 10 = =c] Pe. Au E V,
(20)
where of is the ground-truth label of graph i. Assume the latent representations of nodes in one graph are identically distributed, it follows from (20) and the law of large number that for any graph i with true label y
0.s E b
9:
Pc
DEV.
V.I + co, which is account for (3) certain degree. As for the adjacent matrix, we refer (Gu et al., 2024) to consider the generalized random dot product graph, which can date back to (Solanki al., 2021) that for graph i:
P (A jk 110) an2 Er
where ④ = (f1,...,En) ~ F(O) -r--- = diag (4r, -.)). We assume the distribution F()) is deter- mined by the global graph feature 9: that there exist continuous matrix function M such that
A (gi), Vi E NJ.
(21)
Take coefficients avé |& and denote 2 up as the p-th eigenvalue, eigenvector for graph for the sake of simplicity. First we consider if of = c, Vj = c' then by (20) and the continuity theorem
(9)
cos (1,,5)) r1 ()))()==
Σ
1 5) a r'c'' cos (0 n
VEV.
Σ DEV,
Σ
16))
ane cos (PesPe'
= cos
V
[V
N'EVs
as [V: [V51 + oo, and
cos (r!0) (r!)),p) .P))
Σ
a cos
(1(9)p.) [1 Pc.)
cos
Σ
h10
Pr.
a. cos (pe, Pc) 1,
14
DEV;
DEV;
as [ - x0, which further implies
C
P
(A.pa spa 1/
= 1 = - PP (A spa 1lyf Vう = c) (vt 0/ =cl. = v3)
2
spa
= 11y5 = 2 = c) P (yx = Vī = clyit = =,ブ)
r: + (c)
(c)
008
ri :1g [10)) cos
(c)
Pe
1
vī = IP (vt = 1) =clut = v²3
2
o=l
P y Vi clsi - 1,
as |Vd, 1211 + xc, where the second and third line follow from the definitions of A and stj0 As for (12), observe that (21) indicates the adjacent matrix of graph given yf = c satisfies
(
A
M
a.s. M (po)
BEV.
14

---

Published as a conference paper at ICLR 2026
[ + oo, which implies || - A F - 0 given y/ Vj Further by Weyl's
Perturbation Theorem in (Oudghiri, 2005) we have
1 X - ||4(1) 10 0.9. 0,
while by a variant of Davis-Kahan Theorem, Theorem 2 in (Yu et al., 2015) and nin
(() pt1 ( 2 5 we have
|1 - u- S 11 1 - 0
4
for S Therefore by (8) and the continuity theorem we have
|| (p) 2//011 a.a. 0
for 1 E p S T, which leads to
|| 11 112 + 11 (p) 112 1|, - 2) 11
|| (P) ||2 + 11 112
1 z cos
2 (p) (p)
a.s.
2 1.
2 11
2112 ( 1112 10
Then by the definitions of Aee and 8/ obtain
P (A = 1/1 -3 = Σ
P (A ape 11y1 y = IP (v1 - y3 =clys = v/
c=
C
P (5 -1ylt リه = c) P (ut = Uو = clys = vî)
P c08 (1(0)) ( 1, 1,..., Tly  c) P (vī 13 cly. v3))
+ Σ (yt = yi cly = v) =
[V11 1V,1 oc, which completes the proof.
B PROOF OF THEOREM 2
Recall that we assume the classifier is well-trained such that felossifier (pc) Ie,, Vc V,
(22)
where Te E 13 denotes one-hot vector whose e-th component and the rest are 0. By Theorem 1 and (13) we have
y(E) a.s.
as Vil, E + xo, which further implies Qi and (22) we have
a.s.
Y according to (15). By the continuity theorem
P = Sclassifier (g:) Sciassifier
Σ
1 1..
M
Sclaesifier (Pyt) = I,, Y
(23)
WEV.
M + 0o. Denote [V| minigisN Vel. by dominated convergence theorem and (16) obtain
1
lim E-
E [Coupl
lim E log
Softmax (P.). Que
B
i=1
rES;
1
lim log
Σ
Softmax (P.). Qie + (P.),y: Qr.5
B
i=1
CP
B
E log [0 + [0+1]= 1]=0
B
where the last line follows from (18) and (23).
15

---

Published as a conference paper at ICLR 2026
C RELATED WORK
C.I GRAPH CLASSIFICATION
Graph classification has been widely applied in fields such as molecular property prediction, protein interaction analysis, and social network modeling (Fang al., 2022; Wang al., 2021; Ju et al., 2024). Traditional graph kernel methods (Shervashidze et al., 2011) measure structural similarity through subgraph comparisons, but scale poorly to large graphs. Recent advances in Graph Neu- ral Networks (GNNs) (Welling & Kipf, 2016; Hamilton et al., 2017; Veličković et al., 2017; Xu al., 2018) have shown superior performance by aggregating local neighborhood information and generating graph-level representations via pooling operators (Lee et al., 2019; Gao & Ji, 2019; Lee et al., 2021). Spectral approaches like EigenMLP (Bo et al., 2023) provide an alternative by encod- ing global graph structure through Fourier-like like eigenvalue embeddings. Despite their success, these methods heavily rely on abundant clean labels, which are often unavailable in real-world scenarios due to annotation cost inherent uncertainty. While self-supervised graph learning methods (You et al., 2020: Luo et al., 2022: Ju et al., 2023a) avoid labels during pre-training, they still require accurate annotations for downstream classification and tend to degrade significantly under label am- biguity. this paper, we study the problem of partial label graph learning and utilize relational inference with spatial and spectral cues to address the challenge of label noise.
C.2 PARTIAL LABEL LEARNING
Partial label learning (PLL) considers a weak supervision setting where each training instance is annotated with a candidate label set containing only one correct label (Hüllermeier & Beringer, 2005; Cour al., 2011; Wang et al., 2022; Yan & Guo, 2023). Early approaches treat all candi- dates equally by averaging losses, but such uniform assumptions often fail under high label ambigu- ity. Later works focus on label disambiguation, estimating true labels through confidence-ber -based or similarity-driver refinement (Feng & An, 2019; Wang & Zhang, 2022). Recent advances introduce contrastive learning to PLL (Wang et al., 2022), where prototype-insaance alignment helps separate correct labels from distractors. However, these methods are mostly designed for Euclidean data such as images or texts. On graph-structure data, PLL remains underexplored Gu et al. (2024); Gao et al. (2024); Gu et al. (2025a). DEER (Gu et al., 2024) is of the few attempts. It measures semantic distribution divergence between graph views for contrastive learning and leverages posterior-gus guided soft label correction. Nonetheless, DEER relies semantic distribution matching and lacks fine- grained structural modeling. GPCD (Gao et al., 2024) introduces graph potential cause discovery estimate causal subsets for supervision, but suffers from high training complexity and overlooks global spectral cues. In contrast, our proposed PRISM integrates spatial substructure information and spectral characteristies into a unified relational inference framework, enabling more reliable and stable label disambiguation under complex graph structures.
D MORE EXPERIMENTAL RESULTS
We provide more results under the low ambiguity level (g = 0.1, 0.02) Table 3. Our PRISM consistently achieves the best performance on all datasets, demonstrating its superiority under mild label noise. It may owe to both spatial and spectral cues captured by our PRISM, which play a pivotal role in resolving semantic ambiguities. These results complement the main findings in Section 4.2, and additionally explain the advantage of our framework for keeping strong generalization under different noise regimes.
E DETAILS OF BASELINES
We compare our proposed PRISM against a broad spectrum of baseline models categorized into seven distinct groups: (a) Graph neural networks: GCN (Welling & Kipf, 2016), GAT (Veličković et al., 2017), GIN (Xu et al., 2018), 8), and GraphSAGE (Hamilton et al., 2017); (b) Hierarchical graph pooling: TooLPool (Gao & Ji. 2019), SAGPool (Lee al., 2019), EdgePool (Diehl, 2019), and ASAP (Ranjan et al., 2020) (all using GraphSAGE as the encoder backbone); (c) Graph augmen- Iation method: Graph Transplant (Park et al., 2022); (d) Unsupervised contrastive graph learning:
16

---

Published as a conference paper at ICLR 2026
Table The compared accuracy stdd%) on different graph classification datasets. The best results are highlighted in boldface and the second best results are underlined, P E Y # y) reflecting the level label ambiguity.
Dataset
ENZYMES
Letter-High
COIL-DEL
CIFARIO COLORS-3
Methods
9 0.1
g= 0.1
q 0.02
Q q= 0.1
g 0.1
GCN
61.33
50.09
60.77
47.18
90.34saos
GAT
58.224308
73.39
69.11
57.5620es
89.33214:
GIN
59.78
55.83
55.94
47.29
63.01
GraphSAGE
60.89
78.20=1.17
71.40
57.22:007
91.70+2
TopKPool
53. 1:412
67.07
35.80
55,2610s
82.35
SAGPool
56.891537
67.42.1191
52.94
54.23 10:3
76,99 1.339
EdgePool
28.671227
70.49
68.74 18
55.09
87.47
ASAP
60.89
71.25
59.03
54.5620m
77.84.1.2
Graph Transplant
61.56+286
80.75
80.09
56,87
85,48
PiCO
61.082667
81.27
84.88
57.70g08:
65.68
TGNN
62.44
78.55
70.4920077
OOM
93. 13.161185
GraphCI.
61.78&1.51
78.4320.85
78.83
57.62.106
92.71:11:
GraphACI.
58.22
81.0421.01
80.6620-41
27.652021
92.05
DEER
67.11
83.48
87.86=141
61.45 40
96.23
PRISM (Ours)
68,00
84.87
89.29
61.73
98.36
GraphCL. (You al., 2020) and GraphACI (Luo al., 2023); (e) Semi-supervised graph learning: TGNN (Ju et al., 2023b); (f) Partial label learning in vision: PiCO (Wang et al., 2022), adapted with
GraphSAGE encoder; (g) Partial label learning for graphs: DEER (Gu al., 2024). The details of baselines are presented below.
GCN (Welling & Kipf, 2016): A convolutional network that leverages renormalized adjacency matrices to aggregate neighborhood information in a computationally efficient manner.
GAT (Veličković et al., 2017): It introduces attention weights over neighbors, enabling each node prioritize important neighbors during message passing.
GIN (Xu al., 2018): uses MLPs to approximate injective functions over sets of neighbors, achieving powerful discriminative capacity aligned with the Weisfeller-Lehman test.
GraphSAGE (Hamilton et al., 2017): It aggregates information from randomly sampled neigh- bors, making scalable to large graphs.
TopKPool (Gao & Ji, 2019): It selects top-ranked nodes according to an adaptive projection score form pooled graph with reduced size.
SAGPool (Lee al., 2019): utilizes self-attention scores computed from graph convolutions guide node selection for pooling, capturing both feature and structural signals.
EdgePool (Diehl, 2019): It contracts edges iteratively to coarsen the graph while maintaining crucial topological structures.
ASAP (Ranjan et al., 2020): It combines node selection and clustering by learning soft assign- ments over local h-hop neighborhoods, allowing for adaptive structure-awarc pooling.
Graph Transplant (Park et al., 2022): A mixup-inspired data augmentation strategy that extracts meaningful subgraphs based on node saliency and generates hybrid samples through substructure- level interpolation.
GraphCL (You al., 2020): A contrastive learning framework that maximizes agreement be- tween different augmented views of a graph, using stochastic transformations.
GraphACL (Luo et al., 2023): It improves contrastive representation learning by constructing adversarial hard negatives and regularizing the feature space with orthogonality and divergence constraints.
TGNN 2023b): A dual-view semi-super framework that integrates message passing and kernel-based reasoning, encouraging consistency across views to exploit both labeled and unlabeled graphs.
17

---

Published as a conference paper at ICLR 2026
PiCO (Wang et al., 2022): It learns set of class-wise prototypes and employs contrastive objec- tives to align instance embeddings with their correct prototypes. We adopt a GraphSAGE encoder to enable graph-level upplications.
DEER (Gu et al., 2024): A partial-label graph learning method that selects reliable positíve pairs by measuring distribution divergence across augmented views. also performs soft label cor- rection via posterior estimation. However, it does not explicitly model substructures spectral signals, limiting its granularity in structural reasoning.
Training Protocol. All baselines are trained under partial-label supervision using a cross-entropy loss over candidate label sets. TGNN additionally optimizes consistency loss between dual views. For contrastive methods such as GraphCL, GraphACL, and PiCO, we apply their contrastive loss and the cross-entropy loss. Pooling-based methods are evaluated with fixed pooling ratio of 0.6 and use GraphSAGE as their encoder. All models are trained under identical random seeds for fair comparisons.
DETAILS OF IMPLEMENTATION
We implement all models using PyTorch with the PyG backend. two-layer GraphSAGE with 512 hidden units is adopted as the backbone encoder. The EMA momentum for prototype and label updates is set to steps. Eigen-decomposition is precomputed via sparse solvers to ensure efficiency. For ENZYMES, Letter-High, COIL-DEL, and COLORS-3, we partition the data into training, validation, and test sets with ratio of 80%:5%:15%. For CIFARIO, follow the popular split of 45,000 training, 5,000 validation, and 10,000 test samples, consistent with the protocol (Dwivedi et al., 2020). All these results are averaged over five independent runs with individual seeds.
3 = 0.99, and the propagation momentum
0.9 with E
18


Reviews:
[{"review_id": "6LYdQ89Fld", "reviewer": "Reviewer_kgnv", "summary": "The paper aims to solve a novel graph classification problem known as partial label graph learning where labels of each graph are ambiguous with a set of labels provided but not precise label. The paper proposed a novel framework that aims to establish both graph-graph relation from spatial view and spectral view and denoise the label set from the established graph pair relations. For spatial view, the author proposed to align subgraph structure with the clustered class-centered substructure prototype and for spectral view, the author aims to build band-frequency based alignment. Empirical results suggest a clear improvement of proposed method compared with various baselines from graph neural network based models and partial label learning from computer vision fields. Ablation results suggest each component's effectiveness. The author also show theoretical analysis on the convergence of the label confidence matrix and training loss.", "questions": "Please see weakness. I would like to know how the author considers their runtime on spectrum part and also how M is computed.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1.The paper discusses a novel problem called partial label graph learning problem which would be practical in real application setting where labels are ambiguous for actual datasets.  \n2. A novel framework is proposed that absorbs both spatial and spectral information for each graph to effectively capture useful information for denoise the noisy soft labels and train the classifier.\n3. The theoretical analysis looks sound and comprehensive.\n4. Empirical results suggest a clear improvements for proposed method compared with baselines from Graph neural network side and partial label learning benchmarks.", "weaknesses": "1. I think when it involves with the eigenvalue computation, especially for the dense and large-scale graph, the computation cost becomes expensive and prohibitive. This makes the spectral part of the framework not scalable. In the computation efficiency analysis, the author failed to discuss this important question and in my opinion falsely conclude the computation efficiency is comparable to standard GNN. For a dense and large-scale graph, the computation of eigenvalue and eigenvectors could be approaching O(n^2).\n2. I find some parts of the paper lacks explanation of the symbols. For example, in the spectrum part, k seems to be an index, yet, in the computation analysis, k becomes the number of eigenvalues. M is referred to as the binary mask, but there is no definition on how it should be computed, which makes the paper hard to follow at some points.", "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": "Aq6it6soZv", "reviewer": "Reviewer_Nemd", "summary": "This paper proposes a novel graph classification method in partial-label setting, which captures relations between graphs from both spatial and spectral views.", "questions": "- I am not quite understand Figure 3, please provide more explanations.\n- For Eq.16 and Eq. 17, which one is the final loss function?\n- Why using different q for different datasets?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- The proposed method designs a novel way to compute spatial and spectral relations between graphs.\n- The method's training complexity is linear in the number of edges and consistent with standard GNN-based methods.\n- The method applies a binary mask to enable partial supervision.", "weaknesses": "- The equations lack explanations. Why do you design the spatial relations by Eq.(5), which consists of two components. Why do you use Eq.(7)  to compute X^(p) . What is the deeper meaning behind these equations.\n- How to decide the binary mask M, as it desides how many data are used for supervision. Does this method sensitive to M and the ratio of supervised data.", "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": "fAvWhvpOlt", "reviewer": "Reviewer_Qmcu", "summary": "The paper tackles the practical and underexplored problem of Partial-label Graph Learning (PLGL), which reflects real-world situations where graph labels are incomplete or uncertain. The proposed method PRISM integrates three complementary components, i.e., prototype-guided substructure alignment, spectral modeling, and hybrid relational graph propagation, to address label ambiguity from spatial, spectral, and relational perspectives.", "questions": "1. How is the cross-graph substructure alignment implemented in practice? Can the authors show that this step does not cause extra computational cost?\n2. Since each graph has its own Laplacian basis, how does the method handle spectral inconsistency when using multi-band features?\n3. The convergence proof assumes a well-trained classifier with correct one-hot outputs. What happens if this assumption does not hold? Any discussion or experiments?\n4. Could the authors test the model under different candidate set sizes, noise levels, or open-set cases (where true labels are missing)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The approach is conceptually coherent and well-motivated, combining local structural cues with global spectral information for more reliable supervision. Experimental results on multiple benchmarks demonstrate clear performance improvements over existing weakly supervised and graph learning methods, supporting the effectiveness of the proposed framework.", "weaknesses": "1. Graphs differ significantly in size and structure, making cross-graph substructure alignment both conceptually unclear and potentially computationally expensive. The paper does not explain how this process is implemented or efficiently approximated, and when dealing with large graphs with many nodes and edges, it could still lead to severe computational bottlenecks.\n\n2. Each graph has its own Laplacian basis, making frequency bands difficult to compare across graphs. The paper does not explain how spectral features are aligned or normalized, and when the structural differences between graphs are large, ensuring that their spectral representations are meaningfully aligned remains a significant challenge.\n\n3. The theory assumes a perfectly trained classifier with one-hot outputs. In practice, momentum updates and label propagation interact, so this assumption may not hold.\n\n4. Limited robustness evaluation. The work does not systematically evaluate different candidate set sizes, nor does it examine performance under varying noise levels or open-set scenarios.", "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": "oglSf5EO7R", "reviewer": "Reviewer_Nyo7", "summary": "This paper proposes PRISM, a framework for Partial-Label Graph Learning (PLGL). It resolves label ambiguity by integrating local spatial cues (substructure matching) with global spectral cues (frequency analysis). These views are used to construct a relational graph that guides an iterative label propagation process. Experiments show PRISM achieves state-of-the-art results, demonstrating strong robustness to label noise.", "questions": "1. Theorems 1/2 assume the GNN already maps samples near the correct prototypes and the classifier recognizes them perfectly; they describe an ideal fixed point rather than how the model reaches it under noisy supervision, offering little insight into the core challenge.\n2. Is the claim that the model's complexity is O(|E| d) reasonable? Finding the top-k neighbors for all graphs in a batch seems like it would be at least an O(N^2) operation, which can be very slow. The paper doesn't seem to have accounted for this cost.\n3. The paper claims the spatial and spectral views are complementary, but neither the theory nor the experiments really show how they help each other. Is there an example where one view gets it wrong, but the other one corrects it? Otherwise, it looks more like a simple combination of two methods.\n4. Looking at your ablation study (Table 2), removing the \"Relational Inference\" step causes the biggest performance drop. This makes me wonder: is the final label propagation step the real key to the performance boost? It might mean that the spatial and spectral encoders you focus on are not the main reason for the model's great results.\n5. In Section 3.1, you mentioned a key step called \"confidence-based filtering\" for updating the prototypes, but it's never explained how it works. Without it, it's hard to fully understand your method.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The manuscript tackles an important, practical task: learning from graphs that only provide a candidate label set, and it states the setup clearly for real applications.\n2. It shows strong results with noticeable margins on several benchmarks and stays stable as label noise increases, which points to solid robustness.\n3. The pipeline is modular and easy to adapt and swap encoders or spectrum modules without redesigning the whole method.", "weaknesses": "1. The theory relies on very strong assumptions and does not explain how the model actually learns under noisy supervision; it mostly describes behavior at an ideal fixed point.\n2. The paper does not convincingly show that the two views truly help each other; ablations suggest the label-propagation step may account for most gains, not the new encoders, so the claimed synergy remains unclear.\n3. Some key implementation details are missing, such as how confidence-based filtering is done, and the complexity claim skips the likely quadratic cost of cross-graph similarity and Top-k selection, which can mislead readers about scalability.", "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)