Diffusion Probabilistic Models for Structured Node Classification
Authors: Hyosoon Jang
Seonghyun Park
Sangwoo Mo
Sungsoo Ahn
Venue: NeurIPS 2023 poster (2023)
Keywords: diffusion model
graph neural network
structured prediction
node classification
TL;DR: We investigate the use of a diffusion probabilistic model for structured node classification based on its ability to learn joint dependencies and make predictions conditioned on partially known data.

Abstract: This paper studies structured node classification on graphs, where the predictions should consider dependencies between the node labels. In particular, we focus on solving the problem for partially labeled graphs where it is essential to incorporate the information in the known label for predicting the unknown labels. To address this issue, we propose a novel framework leveraging the diffusion probabilistic model for structured node classification (DPM-SNC). At the heart of our framework is the extraordinary capability of DPM-SNC to (a) learn a joint distribution over the labels with an expressive reverse diffusion process and (b) make predictions conditioned on the known labels utilizing manifold-constrained sampling. Since the DPMs lack training algorithms for partially labeled data, we design a novel training algorithm to apply DPMs, maximizing a new variational lower bound. We also theoretically analyze how DPMs benefit node classification by enhancing the expressive power of GNNs based on proposing AGG-WL, which is strictly more powerful than the classic 1-WL test. We extensively verify the superiority of our DPM-SNC in diverse scenarios, which include not only the transductive setting on partially labeled graphs but also the inductive setting and unlabeled graphs.

Diffusion Probabilistic Models for Structured Node Classification
Hyosoon Jang', Seonghyun Park', Sangwoo Mo², Sungsoo Ahn'
POSTECH
University of Michigan
(hsjang1205, shaprkk sungoo sungsoo. ahn)@postech. ac.kr, swmoQumich edu
Abstract
This paper studies structured node classification on graphs, where the predictions should consider dependencies between the node labels. In particular, we focus on solving the problem for partially labeled graphs where essential to incorporate the information in the known label for predicting the unknown labels. To address this issue, we propose a novel framework leveraging the diffusion probabilistic model for structured node classification IDPM-SNC) At the heart of our framework is the extraordinary capability of DPM-SNC to (a) learn a joint distribution over the labels with expressive reverse diffusion process and (b) make predictions conditioned on the known labels utilizing conttrid-oosttraieed sampling. Since the DPMs lack training algorithms for partially labeled data, we design novel training algorithm to apply DPMs, maximizing a new variational lower bound. We also theoretically analyze how DPMs benefit node classification by enhancing the expressive power of GNNs based on proposing AGG-WL, which is strictly more powerful than the classic 1- test. We extensively verify the superiority of our DPM-SNC in diverse scenarios, which include not only the transductive setting on partially labeled graphs but also the inductive setting and unlabeled graphs
Introduction
In this paper, we address the node classification problem, which a fundamental problem machine learning graphs with various applications, such as social networks [I] and citation networks [2]. One representative example is transductive problem to classify documents from a partially labeled citation graph. Recently, graph neural networks (GNNs) [3, 4] have shown great success in this problem over their predecessors [5, 6]. Their success stems from the high capacity of non-lineat neural architectures combined with message passing.
However, the conventional GNNs are incapable of structured node classification: predicting node labels while considering the node-wise label dependencies [7-9]. That is, given graph G' with vertices V and node labels {y,
V). a GNN with parameter 9 outputs an unstructured prediction, ie., (3. Yy (G) pe (yyl (t)pe(y))GG))) for i, E V. Especially, this limitation becomes problematic in transductive setting where the prediction can be improved by incorporating the known labels, e.g., output (3 [., yÿ) for known yj- In Figures 1(a) and (bb), elaborate this issue with example where the conventional GNN fails to make the correct prediction.
To resolve this issue, recent studies have investigated combining GNNs with classical structured prediction algorithms, i.e., schemes that consider dependencies between the node labels [8-13]. They combine GNNs with conditional random fields [14], label propagation [15], or iterative classification algorithm [2]. Despite the promising outcomes demonstrated by these studies, their approach relies on the classical algorithms to express joint dependencies between node labels and may lack sufficient expressive power or consistency in incorporating known labels.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

00000
(a) Input
(b) GCN [3]
GMNNN [7]
(d) CLGNN [13]
DPM-SNC (ours)
Figure 1: Results of various methods to solve node classification on a non-attribute and partially
labeled cyclic grid. (a) The task estimate p(yulyy G) where the known labels yr are highlighted in green and the unknown labels yu are colored in gray. (b)-(e) Red highlights the incorrect predictions made by the corresponding algorithm. Conventional GNN (GCN) fails make an informative prediction while our DPM-SNC is the only method to perfectly predict all the labels.
Contribution. We propose novel framework for structured node classification called DPM-SNC. Our key idea is leverage the diffusion probabilistic model (DPM) [16], motivated by two significant advantages of DPM for structured node classification: (a) it can effectively learn joint distribution over both the unknown and the known labels, and (b) can easily incorporate conditions during inference via posterior sampling. Figure highlights that DPM significantly outperforms previous methods when the prediction problem requires a complete understanding of label dependencies.
However, DPM cannot be directly applied to the transductive scenario, where the model needs to maximize its log-likelihood for partially labeled graphs. We propose novel training algorithm to address this challenge. Our method maximizes a new variational lower bound of the marginal likelihood of the graph over the unlabeled nodes, involving the alternative optimization of DPM and variational distribution. In this process, we estimate the variational distribution from the current DPM using similar approach fixed-point iteration [17]. After training, DPM can predict the remaining node labels by constraining its predictions with the given labeled nodes, utilizing the
manifold-constrained sampling technique [18].
In addition, we provide a theoretical analysis that supports the benefits of DPM-SNC for node classification by enhancing the expressive power of GNNs. To this end, we derive an analog of our DPM-SNC based on the Weisfeiler-Lehman (WL) [19] test, evaluating the ability to distinguish non-isomorphic graphs Specifically, we prove that DPM-SNC as powerful as our newly derived aggregated Ceisfeiler-Lhhmand (AGG-WLL WL) test, which is strictly more powerful than the 1-WL test, a known analog standard GNN architectures [20] such GCN [3] and GAT [21].
We demonstrate the effectiveness of DPM-SNC on various datasets, covering both transductive and benchmarks: Pubmed, Cora, and Citeseer [22]; Photo and Computer [23]; and Empire and Ratings [24]. Additionally, introduce synthetic benchmark to evaluate the ability to capture both short and long-range dependencies. DPM-SNC outperforms the baselines, including both homophilic and heterophilic graphs. In the inductive setting, conduct experiments on four benchmarks: Pubmed, Cora, Citeseer, and PPI [25]. Furthermore, we evaluate DPM-SNC on the algorithmic reasoning benchmark [26], which requires a higher-level understanding of node relations. DPM-SNC also outperforms previous algorithms for these tasks.
inductive settings. In the transductive setting, we conduct experiments
To summarize, contribution can be listed as follows:
We explore DPM as effective solution for structured node classification due to its inherent capability in (a) learning the joint node-wise label dependency in data and (b) making predictions conditioned on partially known data (Section 3).
We propose a novel method for training a DPM on partially labeled graphs that leverages the probabilistic formulation of DPM to maximize the variational lower bound (Section 4).
We provide theoretical analysis of how DPM enhances the expressive power of graph neural networks, strictly improving its capability over the I-WL test (Section 5).
Our experiments demonstrate the superiority over the baselines in both transductive and inductive settings. We additionally consider heterophilic graphs and algorithmic reasoning benchmarks to extensively evaluate the capability of DPMs in understanding the label dependencies (Section 6).

---

2
Related Work
Graph neural networks (GNNs). Graph neural networks (GNNs) are neural networks specifically designed to handle graph-structured data. Over the past years, GNNs have shown promising outcomes in various tasks related to graph representation learning [3. 4, 27, 28]. In the case of node classification, GNNs aggregate neighboring node information and generate node representations for label predictions. Their expressive power has been analyzed through the lens of the CeisfeilerLehmmene (WL) test [19], a classical algorithm to distinguish non non-isomorppic graphs. For example, Xu et al. [20] proved how the expressive power of conventional GNNs is bounded by the 1-dimensional WL (1-WL) test.
Structured node classification with GNNs. Apart from investigating the power of GNNs to discriminate isomorphic graphs, several studies focused improving the ability of GNNs to learn the joint dependencies [7, 9, 13, 26, 29-31]. In particular, researchers have considered GNN-based structured node classification [7. 9, 13]. First, Qu al., [7] parameterize the potential functions of conditional random fields using a GNN and train it using pseudo-likelihood maximization [32]. Next, Qu al., [9] proposed a training scheme with a GNN-based proxy for the conditional random field. Hang et al., [13] proposed an iterative classification algorithm groordhh-bbaed learning framework of GNNs that updates each node-wite prediction by aggregating previous predictions on neighboring nodes.
Diffusion probabilistic models (DPMs). Inspired by non-equilibrium thermodynamics, DPMs are latent variable models (LVMs) that learn reverse diffusion process and construct data from noise distribution. Recent studies demonstrated great success of DPMs in various domains, e.g.. generating images [33], text [34], and molecules [35]. An important advantage of diffusion models is their ability to incorporate additional constraints. This allows DPM to solve the posterior inference problems, e.g., conditioning on the partially observed data recover the original data [18, 36, 37].
3 Diffusion Probabilistic Models for Structured Node Classification
In this section, we introduce the problem of structured node classification and discuss the limitations of graph neural networks (GNNs) in addressing this problem (Section 3.1). We then explain how the diffusion probabilistic models (DPMs) offer promising solution for this problem (Section 3.2).
3.1 Structured node classification
We address structured node classification, which involves predicting node labels while consider- ing their joint dependencies. Specifically, we focus on predicting labels in partially labeled
reverse process
node node-wise wise predictions
graphs, where some true labels are known in ad-
vance. Our goal is to devise an algorithm that
considers the dependencies with known labels to enhance predictions for unknown labels.
To be specific, our problem involves graph G G=(2, (V,E,, x) consisting of nodes V. edges E, and node attributes denote the node labels by y = {y i E V}. We let V. and Vo denote the set of labeled and unlabeled nodes, while z and yu de- note the corresponding labels for each set, e.g., yL = {v i E V Our objective is to pre- diet the unknown labels yu by training partially labeled graph, aiming to infer the true conditional distribution p(yc G. yr).
{I;
V}. We also
step
step 50
step 100
known
diffusion and projection
Figure 2: The reverse process makes predictions with label dependencies. The node color indicates the label value, and opacity reflects the likelihood.
the
We point out that the conventional GNNs [3, 4, 27, 28] are suboptimal for estimating p(yu G, yy) since their predictions on the node labels are independently conditioned on the input, i.c., their predictions are factorized by Pe (yooloo G, yy) = I. Po (Jr Namely, conventional GNNs cannot incorporate the information of the known labels yL into prediction of the unknown labels yo-
We also show structured node classification to be important for unlabeled graphs in Section 5.
3

---

unlabeled
Algorithm DPM-SNC
1: Train mean-field GNN Po Gy
2: Initialize the buffer B by Polyu (G).
inserts Yu
posterior sampling
3: repeat
(6,y))
(G.y)
buffer B
4: for 1..=-,,..,.. do
5: Get yu ~ Py G, yn) using
(a) Update the buffer with samples from pe (yu G. yr.).
manifold-constrained sampling.
6: Update B t B--Be }
diffusion
[B] K, remove oldest one in B.
8:
end for
samples
9:
for = = l,..., N₂ do
10:
Sample yv ~ B.
buffer
maximize lower bound (G, (l))
(G, y)
11:
Update to maximize LVLB with G,
(b) Update the DPM parameter to maximize LVLB.
and y yr U yu.
12:
end for
Figure 3: Illustration of DPM-SNC training on par- tially labeled graphs, repeating steps (a) and (b).
13:
until converged
Structured prediction algorithms [2, 14] overcome this issue by solving two tasks: (a) learning a joint distribution pa (yu, yr. (G) to maximize the likelihood of labeled data (o(y.. and (b) inferring from the distribution pa (yo [,, yL) conditioned on known labels.
3.2 Diffusion probabilistic models for structured node classification
In this work, we consider diffusion probabilistic models for structured node classification (DPM- SNC) motivated by how their strengths align with the essential tasks for solving structured node classification, outlined in Section 3.1. In particular, DPMs are equipped with (a) high expressivity in learning joint distribution conditioned on partially observed data.
data and (b) the ability easily infer from posterior distribution
To this end, we formally describe DPMs that generate node-wise labels y associated with graph G. high level, our DPM consists two parts: the forward process, which injects noise into the labels, and the reverse process, which denoises to predict the true labels y [16]. Given the number of diffusion steps T, the forward process constructs a sequence of noisy labels (1:T) = (1) ..... yT) using a fixed distribution ( (1:7)
(3y(1: (g ()) starting from the true label ())) y. Next, given an initial
noises (T) sampled from (T)) ), the reverse process Po (y (0:T~1) (T) G) is trained to recover
the forward process conditioned on the graph G. We defer the detailed parameterization to Section
To be specific, the forward and the reverse process are factorized as follows:
olyy (--1), t=1
II
Po (0T (T)
G)
II (y (t-) (0) (*),)) G),
where the training of the reverse process is trivial on fully-labeled graph (y, G) by maximizing the variational lower bound of the marginal log-likelihood log PgpooyyCC (G) = log > Eya Po po (0:T) G)
with respect to the noisy labels y (1:T) sampled from the forward process [16].
By leveraging shared latent variables (*) across multiple steps in the reverse process, the reverse process effectively considers the dependencies in the output. Next, DPMs can easily infer from a posterior distribution conditioned on partially observed data. Specifically, the incremental updating of (!) for 1, 1,.... allows the DPM to incorporate the known label yL. e.g., applying itera- tive projection with manifold-baat Po Po G. yr.) conditioned on the known labels yr.- See Figure 2 for an illustration of DPM for structured node classification with known labels.
correction [18]. This enables inference from the distribution
We relax the discrete labels one-hot vectors apply the forward process.

---

4 Training Diffusion Probabilistic Models on Partially Labeled Graphs
Despite the potential of DPMs for structured node classification, they lack the algorithms to learn from partially labeled graphs, i.e., maximize the likelihood of known labels. To resolve this issue, introduce a novel training algorithm for DPM-SNC, based on maximizing a variational lower bound for the log-likelihood of known labels.
Variational lower bound. a high-level, our algorithm trains the DPM to maximize the log- likelihood of training data log pe (yL G),, which is defined as follows:
L = po G)
log Σ
Σ YU BaTT)
po poly yu y (.T
However, this likelihood is intractable due to the exponentially large number of possible combinations for the unknown labels yu and the noisy sequence of labels (2:1), To address this issue, we train the DPM based on a new variational lower bound L 2 LVL.B. expressed as follows:
LVLB Eyturlla (vc)
B (
log Pe ( (G) log q( (2:))) log (veclll))) (I)
Here, q()) is variational distribution factorized by (yu. y (1:T) yy)) g (3) (E), where
y = yu yz. We provide detailed derivation Appendix A.I.
Parameterization. We define the reverse process po (t (b( (4) G) with Gaussian distribution, where the mean value parameterized by a graph neural network (GNN) and the variance set to be a hyper-parameter. Following the prior work [16], we also employ a Gaussian diffusion to parameterize the forward process ( (1:7)
ly) as follows:
T = II N 0 (B B,I).
4 11)
where I is identity matrix, .I...., Br are fixed variance schedules. We the variance schedule to promote (g)()))()) (T; 0.1) by setting 3t < Bt+1 for t = . - 1 and Br 1. Finally, we describe the variational distribution (y) as an empirical distribution over a fixed-size buffer B containing multiple estimates of the unknown labels yu- This buffer is updated throughout the training. We provide more details on our parameterization in Appendix A.2.
Training algorithm. To maximize the variational lower bound, we alternatively update the GNN- based reverse process Pe(v. y (I:))) and the buffer-based variational distribution ((yolyc). In particular, we update the parameters 0 of the reverse process pe (y, y (1:T) G) to maximize the Monte Carlo approximation of Live by applying ancestral sampling to the variational distribution (1-(1 y (3y (yr.), i.e., sampling yv from the buffer B and applying the diffusion process to y. This is the same as the original denoising-based training of DPM [16] with estimated unknown labels, where the detailed training objective is described in Appendix A.3.
Next, we update the variational distribution q by inserting samples from the distribu- tion pa Pa(yu [G, yL) into the buffer B. This update is derived from the condition (3yuly)) Po(yu yL) being necessary to maximize LVLB. similar to the derivation of fixed-point iteration for optimization [17]. We describe the overall optimization procedure in Figure and Algorithm 1.4
Finally, we emphasize that our training algorithm is specialized for DPMs. Previous studies in- troducing variational lower bounds for structured node classifications [7, 38] face intractability in maximizing log (g(()) or sampling from po(yu [G, y).)) They require defining the pseudo- likelihood for the former [32], or parameterizing variational distribution for the latter. However, in our case, the formal simply requires maximizing the lower bound LVLB. and the latter is easily solved by manifold-consee constraiied sampling [18].
We conisroidc sampling of DPM to infer from the distribution (e IG, yL. [18]. The detailed sampling procedure is described Appendix A.4.
'In practice, we initialize the buffer B with samples from a mean- mean-field GNN Pu(y(G), which outputs an independent joint distribution over node labels, i.e., po (o I. y1) = Hlev po po
5

---

5 Theoretical Analysis
In this section, present secondary motivation for using DPMs in node classification, distinet from the one given in Section and Section 4. Specifically, we demonstrate that DPMs provably enhance the expressive power of conventional GNNs for solving the graph isomorphism test, implying improved expressive power for node classification problems as well.
To this end, assess the expressive power of our DPM-SNC by its analog for discriminating isomorphic graphs, which we call the aggregated Weisfeiler-Lehman (AGG-WL) test. Then, we show that LGG-WWLE is strictly more powerful than the 1-dimensional WL (1-WL) test [19], which is an analog of GNNs [20]. We formalize our results in the following theorem.
Theorem 1. Let I-WL-GNN be GNN as powerful as the 1-WL test. Then, DPM-SNC using 1-WL-GNN is strictly more powerful than the I-WL-GNN in distinguishing non-isomorphic gruphs
We provide the formal proof in Appendix B. At a high level, both the 1-WL test and the AGG-WL test assign colors to nodes and iteratively refine them based on the colors of neighboring nodes, enabling the comparison of graph structures. The key difference is that AGG-W applies perturbations into the initial graph create multiple augmented graphs, and aggregates the results of the 1-WL algorithm each augmented graph. The perturbations and aggregation can be done by node-wise concatenations with binary random features and hashing multiset of the refined graph colors, respectively. Hence, any graph pair distinguishable by the 1- test is also distinguishable by our AGG-WL test, and there exist pairs of graphs indistinguishable by the WL test but distinguishable by our variant.
We remark that our analysis can be casily extended to applying other latent variable models, e.g.. variational auto-encoders [39] normalizing flows [40]. for node classification. In this analysis, sampling a latent variable corresponds to fixing a perturbation for color assignments at initialization, and aggregating
the perturbed graphs corresponds computing the prediction labels with marginalization over the latent variables. Our theory is based on that of Bevilaqua al. [41] which was originally developed for analyzing particular GNN architecture; our key contribution lies in extending this analysis to the latent variable models.
the true
Experiments
6.1 Transductive setting
We first evaluate the performance of our algorithm in the transductive setting. Specifically, we conduct an evaluation of DPM-SNC on synthetic data, as well as real-world node classification problems. We consider different types of label dependencies by considering both homophilic and heterophilic graphs. We provide the details of our implementation in Appendix C.I.
Synthetic data. In this experiment, we create 2 x n non-attributed cyclic grid. Each node assigned either binary label, with neighboring nodes having different labels. We consider two scenarios: one where the known labels are randomly scattered throughout the graph, and another where they are clustered local region. Examples of both scenarios are illustrated in Figures 4(a) and 4(b). These two scenarios verify the capability for capturing both short and long-range dependencies between node labels. The data statistics are described in Appendix D.
(a) Scattered
(b) Localized
Figure 4: Illustration of two scenarios. Green highlights known labels.
Table 1:
The transductive node classifica- tion accuracy on synthetic data. Bold num- bers indicate the best performance.
Method
Scattered
Localized
GCN [3]
50.1
51.3
We compare DPM-SNC with conventional GNN that ignores the label dependencies and other structured node classification methods: GMNN [7], GONN [8], and CL.GNN [13]. We describe the detailed experimen- tal setup Appendix E. We report the performance using five different random seeds.
+ GMNNN [7]
64.2
48.214s
+ G [8]
10.
51.3114
CLGNN [13]
87.0+24
53.4+21
DPM-SNC
98.5
90.9

---

Table The transductive node classification performance. N-Ace. and Sub-Ace. denote the node- level and subgraph-leva accuracy, respectively. Bold numbers indicate the best performance among the structured prediction methods using the same GNN.
Pubmed
Cora
Citeseer
Photo
Computer
Method
N-Acc. Sub-Ace.
N-Ace.
Sub-Acc.
N-Ace.
Sub-Acc.
N-Ace.
Sub-Acc.
N-Acc. Sub-Acc.
LP [42]
69.1 45.7.00
68.1
46.91s0
16.
29.8
81.0.20
37.2
69.9.22
15.1 1ia
C&S [43]
77.3 #00 57.1
80.2
60.1 +00
69.5 =a0
47.9
90.1
48.5
81.6 #as 24.5
BPN [44]
78.2 111 48.4
82.5
63.8 i09
73.3 207
51.9
89.0
44.1 214
80.4 114
22.3
PTA [45]
80.1
55.2
82,9
62,6
71.3
51.4sai
91.1=1s
51.0ais
81.6x12
26.3
GCN [3]
79.7
55.8.16
81,41os
59.3
70.9
49.8
91.0-1a
52.0at
82.411a
27.0a
+I.PA [12]
79.62n6
53.5
81.7107
60.3
71.01ss
50.2114
91.321a
52,9
83.7
28.5
GGNNN [7]
82.6=1n
58.1+14
82,6+09
61.8+1a
72.8+00
52.0=as
91.2-11
54.3+14
82,0=1a
28.0+14
NG [8]
80.
56,921
82.5 to4
:2.3
73.9
53.1
90.7=1u
53.0a2n
1
28.1
-CLGNN [13]
=0.7
57.8=07
81,9
61.8=aa
72.0=a7
$1.6#09
91.1=19
53,4
83.3+12
28.5+14
-DPM-SNC
83.0
59.2
83.2
63.1
74.4
53.62n6
92.2.08
55.3
84.1
29.7118
GAT [211
19.1
55.8
81.5
61.3
71.0ans
50.8
90.8-11
50.8219
83.
27.8
+LPA [12]
78.7
56.0=11
81,5
60.7=0a
71.3209
50.1
91.3-as
$2.7=21
84.4
29.4
+GNNN [7]
79.6208
57.0.o7
82.3
62.2.ss
71.7109
51.41n9
91.421n
53.1218
83.3
29.1
GGNNN 18]
27.
55.9
82.7
62.7
74.0gns
53.7
91.5_m9
52.61na
83.1
28.8114
-LGNNN [13)
80.0=os
57.5
81,8
61.5
12.
52.1+as
90.6=0s
51.9
82.6+12
28.4
DPM--NC
81.7
59.0=11
83,8
63.8
74.3
54.0
92.0=os
54.0=24
84.2a12
30.0=30
GCNII [46]
82.0=os
57.2=11
84,0+04
63,4+0a
72.9+as
52.1
91.2-12
53.2+1s
82.5+14
26,6+13
DDPM-SNC
83,8=07
61.6-09
85.3+04
65.8
74.1+as
54.1+a9
92,8-1.1
54.2+12
84.4
29.2+
The results, presented in Table 1, demonstrate that our method significantly improves accuracy compared to the baselines when labeled nodes are scattered. This highlights the superiority of DPM- SNC in considering label dependencies. Furthermore, our method also excels in the localized labeled nodes scenario, while the other baselines fail. These results can be attributed to the capabilities of DPMs for capturing long-range dependencies through iterative reverse diffusion steps.
Homophilic graph. In this experiment. we consider five datasets: Pubmed, Cora, and Citeseer [22]; Photo and Computer [23]. For all datasets, 20 nodes per class are used for training, and the remaining nodes are used for validation and testing. Detailed data statistics are in Appendix D.
We compare DPM-SNC with conventional GNN, and structured prediction baselines. We compare with label propagation based methods: LP [42], C&S [43], BPN [44], and PTA [45]. We also consider NN, GMNN, and CLGNN. We describe the detailed experimental setup in Appendix E.2. As the backbone network, we consider GCN and GAT [21]. We further evaluate our algorithm with the recently developed GCNII [46]. For all the datasets, we evaluate the node-level accuracy. We also report the subgraph-level accuracy, which mea- sures the ratio of nodes with all neighboring nodes be- ing correctly classified. The performance is measured using ten different random seeds.
Table 3:
The transductive node classifica- tion accuracy on heterophilic graphs. Bold numbers indicate the best score.
Empire
Rating
H₂GCN [47]
60.11
36.47=azz
CPGNN [48]
63.96
39.79=a77
GPR-GNN [49]
64.
44. 24.
FSGNN [50]
79.92
52.74
GloGNN [51]
59.63
36,89
FAGCN [52]
65.22.105
44. 12
GBK-GNN [53]
74.57 t:44
45,98
JacobiConv [54]
71.14
43.55
GCN [3]
73.69
48. 48.70
The results are presented in Table 2. Our method outper- forms the structured ceddiction-spccialiii baselines in both node-label and subgraph-level accuracy. These re- sults highlight the superiority of DPM-SNC in solving real-world node classification problems. Furthermore, even when we combine with GCNII [46], DPM-SNC consistently improves performance regardless of the backbone network.
SAGE [4]
53.63 85.74+067
GAT [21]
80.87
49.0 29.
GAT-sep [24]
88.751041
52. 52.70.ua2
GT [55]
86.51 +003
51.17=ase
GT-sep [24]
87.324039
52, 18230
DPM-SNC
89.52
54.6620.9
Heterophilic graph. To validate whether our framework can also consider heterophily dependencies, we consider recently proposed heterophilic graph datasets: Empire and Ratings [24), where most heterophily-specte GNNs fail to solve. In Table 3, we compare our method with six GNNs:
7

---

Table 4: The inductive node classification performance. N-Acc., G-Acc., and Fl denote the node-level accuracy, graph-level accuracy, and micro-F1 score, respectively. Bold numbers indicate the best performance among the structured prediction methods using the same GNN.
Pubmed
Cora
Citeseer
PPI
Method
N-Ace.
G-Acc.
N-Acc.
G-Ace.
N-Acc.
G-Acc.
F1
GCN [3]
80.25
54.5810si
83.36204
59.67.a.s:
76.37
49.84
99.15
+G [8]
80.32.am0
53.931am
83.60
59.78.
76.34
50.76.04:
99.33
CLLGNN [13]
80. 80.22+005
53.98+054
83,45=034
60.24+0.1
75.71
50.51+aas
99.22=-0m
+SPN [9]
80.78
54.91 an
83.85
60.35
76.25
51.02210
99.35
+DPM-SNC
80.58
55.16
84.09
60.88 10.36
77.01
:1.44:055
99.46.0m
GAT (21)
80.10=045
54.38+054
79.71=141
56,66 16.66+144
74,91
49.87
99.
99.54=0m1
+GNNN [8]
79.88+aa2
54.66+029
81.19=045
58, 58.68++.34
+5,45+002
50.86=a.
99,56==m
+CLGNN [13]
80.23
81.38
58.8 1M::
75.45
50.662aas
99.55
+SNN [9]
79.95
14.82
81.61
59. 19..31
75.41
51.04:aas
99.46.0m
DPM-SNC
80.26
54.26=047
81.79=044
59.55
76.46+0.50
52.05=a71
99.63=am
GCN, SAGE [4], GAT, GAT-sep [24]. GT [55], and GT-sep [24]. We also compare with eight heterophily-specific GNNs: H₂GCN [47], CPGNN [48], GPR-GNN [49], FSGNN [50], GloGNN [51], FAGCN [52], GBK-GNN [53], and JacobiConv [54]. We employ GAT as a backbone network of DPM-SNC. For all the baselines, we use the numbers reported by Platonov et al. [24).
Table shows that our method again achieves competitive performance on heterophilic graphs. While existing heterophill-speccin GNNs do not perform well on these datasets [24], our method shows improved performance stems from the extraordinary ability for considering label dependencies involving heterophily label dependencies.
6.2 Inductive setting
We further show that our DPM-SNC works well not only in transductive settings but also in inductive settings which involve inductive node classification and graph algorithmic reasoning. We provide the details of our implementation in Appendix C.2.
Inductive node classification. Following Qu et al. [9], we conduct experiments on both small-scale and large-scale scale graphs. We construct small-scale graphs from Pubmed, Cora, and Citeseer, and construct large-scale graphs from PPI [25]. The detailed data statisties are described in Appendix D.
We compare our DPM-SNC with the conventional GNN and three structured node classification methods: G3NN, CLGGNN, and SPN [9]. As the backbone network of each method, consider GCN and GAT. We evaluate node-level accuracy across all datasets and supplement it with additional metrics: graph-level accuracy for small-scale graphs and micro-FI score for large-scale graphs. The graph-level accuracy measures the ratio of graphs with where all the predictions are correct. We report the performance measured using ten and five different random seeds for small-scale and large-scale graphs, respectively. The detailed experimental setup is described in Appendix E.3.
We report the results in Table 4. Here, DPM-SNC shows competitive results compared to all the baselines except for Pubmed. These results suggest that the DPM-SNC also solves inductive node classification effectively, thanks their capability for learning joint dependencies.
Algorithmic reasoning. We also evaluate our DPM-SNC to predict the outcomes of graph algorithms, e.g., computing the shortest path between two nodes. Solving such tasks using GNNs has gained much attention since it builds connections between deep learning and classical computer science algorithms. Here, we show that the capability of DPM-SNC to make structured prediction even brings benefits to solving the reasoning tasks by a deep understanding between algorithmic elements.
We evaluate the performance of our DPM-SNC on three graph algorithmic reasoning benchmarks proposed by Du al. [26]: edge copy, connected component, and shortest path. The detailed data statistics are described in Appendix D. Here, we evaluate performance graphs with ten nodes. Furthermore, we also use graphs with 15 nodes to evaluate generalization capabilities. We report the performance using element- wise mean square error.
8

---

Table 5: Performance graph algorithmic reasoning tasks. Bold numbers indicate the best perfor- mance. Same-MSE and Large-MSE. indicate the performance on ten, and 15 nodes, respectively.
Edge copy
Connected components
Shortest path
Method
Same-MSE
Large-MSE
Same-MSE
Large-MSE
Same-MSE
Large- MSE
Feedforward
0.3016
0.3124
0.1796
0.3460
0.1233
1,4089
Recurrent [56]
0.3015
0.3113
0.1794
0.2766
0.1259
0,1083
Programmatic [57]
0.3053
0.4409
0.2338
3.1381
0.1375
0.1290
Iterative feedforward [58]
0.6163
0.6498
0.4908
1.2064
0.4588
0.7688
IREM [26]
0.0019
0.1424
0.2171
0.0274
0.0464
DPM-SNC
0.0011
0.0038
0.0724
0.1884
0.0138
0.0286
85
Number of layers
5
65.7
67.1
68.4
67.3
68.0
4
69.6
70.4
71.1
70.7
71.0
Accuracy
74
Accura
75
10.9
21.3
71.3
71.9
73
70
Pubmed
Cora
72
GCNII
71.4
72.1
72.4
72.4
72.9
Citeseer
DPM-SNC
5
10
40
80
40 Step
60
80
71
0.02
0.04
0.06
0.08
Diffusion steps
Time (s)
Figure 5: Accuracy with varying Figure 6: Accuracy for changes Figure 7: Accuracy with varying inference time.
GNN layers and diffusion steps. in diffusion steps.
We compare method with five methods reported by Du al. [26), including feedforward neural network, recurrent neural network [56], Pondernet [57], iterative feedforward [58], and IREM [26]. For all the baselines, edge-wise targets, we modify DPM-SNC to make edge-wise predictions. We describe the detailed experimental setup in Appendix E.4.
the numbers reported by Du et al. [26]. As these tasks are defined on
We report the results in Table 5. Our DPM-SNC outperforms the considered baselines for five out of the six tasks. These results suggest that the diffusion model can easily solve algorithmic reasoning tasks thanks to its superior ability to make structured predictions.
6.3 Ablation studies
Here, conduct three ablation studies empirically analyze framework. All the results measured over ten different random seeds.
Diffusion steps vs. number of GNN layers. We first verify that the performance gains in DPM-SNC mainly stem from the reverse diffusion process which learns the joint dependency between labels. To this end, vary the number of diffusion steps along with the number of GNN layers. We report the corresponding results in Figure 5. One can observe that increasing the number of diffusion steps provides non-trivial improvement in performance, which cannot be achieved by just increasing the number of GNN layers.
Accuracy over diffusion steps. We investigate whether the iteration in the reverse process progres- sively improves the quality of predictions. In Figure 6, we plot the changes in node-level accuracy in the reverse process the number of iterations increases. The results confirm that the iterative inference process gradually increases accuracy, eventually reaching convergence.
Running time vs. performance. Here, we investigate whether the DPM-SNC can make a good trade-off between running time and performance. In Figure 7, we compare the change accuracy of DPM-SNC with GCNII over the inference time on Citeseer by changing the number of layers and diffusion steps for DPM-SNC and GCNII, respectively. The backbone network DPM-SNC is two-layer GCN, One can observe that our DPM-SNC shows competitive performances compared to the GCNII at a similar time. Also, while increasing the inference times of the GCNII does not enhance performance, DPM-SNC shows further performance improvement.

---

7 Conclusion and Discussion
In this paper, we propose diffusion probabilistic models for solving structured node classification (DPM-SNC). Extensive experiments on both transductive and inductive settings show that DPM-SNC outperforms existing structured node classification methods, An interesting avenue for future work is the study of characterizing the expressive power of GNNs make structured predictions, i.e., the ability to learn complex dependencies between node-wise labels.
Limitations. Our DPM-SCN makes a trade-off between accuracy and inference time through the number of diffusion steps. Therefore, we believe accelerating our framework with faster diffusion- based models, e.g., denoising diffusion implicit models (DDIM) [59] is an interesting future work.
Acknowledgements
This work partly was supported by Institute of Information & communications Technology Planning & Evaluation (IITP) grant funded by the Korea (OVI)) (No. IITP-2019-0-01906, Ar- tificial Intelligence Graduate School Program(POSTECH)) the National Research Foundation of Korea(NRF) grant funded by the Korea governmen((MSIT) (No. 2022RICICI0133 IC1C1013366), and Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the
Ministry of Attp:atinnn22222AAAAAAAAAAA
References
[1] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pages 417-426, 2019.
[2] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008 1,
[3] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:
2016. 1. 2, 6, 7,8
[4] Will Hamilton. Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeurIPS, 30, 2017. 1, 8
[5] Karsten M Borgwardt and Hans Peeerr Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM'05) pages 8-pp. IEEE, 2005.
[6] Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855-864, 2016.
[7] Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. In Inter- national conference on machine learning, pages 5241-5250. PMLR, 2019. 1, 2, 3, 5, 6, 7, 22
[8] Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph- based semi-supervised learning. Advances in Neural Information Processing Systems, 32, 2019. 7,8
[9] Meng Qu, Huiyu Cai, and Jian Tang. Neural structured prediction for inductive node classifica- tion. arXiv preprint arXiv:2204.07524, 2022. 1, 3, 8, 23
[10] Tengfei Ma, Cao Xiao, Junyuan Shang, and Jimeng Sun. CGNF: Conditional graph neural fields, 2019.
[11] Colin Graber and Alexander Schwing. Graph structured prediction energy networks. Advances in Neural Information Processing Systems, 32, 2019.
[12] Hongwei Wang and Jure Leskovec. Unifying graph convolutional neural networks and label propagation. arXiv preprint arXiv:2002.06755. 2020. 7
[13] Mengyue Hang. Jennifer Neville, and Bruno Ribeiro. A collective learning framework to boost gnn expressiveness for node classification. International Conference on Machine Learning, pages 4040-4050. PMLR, 2021. 2, 6, 8, 17
10

---

[14] John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. 2001. 1,
[15] Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. 2002. 1
[16] Jonathan Ho. Ajay Jain, and Picter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 2020. 2, 5, 14
[17] BE Rhoades. Some fixed point iteration procedures. International Journal of Mathematics and
Mathematical Sciences, 14(1):1-16, 1991. 2, 5
[18] Hyungjin Chung, Byeongsu Sim, Dohoon Ryu, and Jong Chul Ye. Improving diffusion models for inverse problems using manifold constraints. arXiv preprint urXiv:2206.0094/ 00941, 2022. 2,
4, 5, 15
[19] Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra
which appears therein. nti, Series, 2(9):12-16, 1968. 2, 3, 6, 16
[20] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018. 3, 21
[21] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. 2, 8 8
[22] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning, pages 40-48. PMLR, 2016. 2, 7, 23
[23] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv: 1ee.11111100066 2018. 2, 7, 23
[24] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations. 2, 7,
8. 23, 25
[25] Marinka Zitnkk and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):1190-i198, 2017. 2, 8, 23
[26] Yilun Du, Shuang Li, Joshua Tenenbaum, and Igor Mordatch. Learning iterative reasoning through energy minimization. In International Conference on Machine Learning, pages 5570- 5582. PMLR, 2022. 2, 3, 8, 9, 22, 24, 26
[27] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXivv/7100 10903, 2017. 3
[28] Ben Chamberlain, James Rowbottom, Maria I Gorinova, Michael Bronstein, Stefan Webb, and Emanuele Rossi. Grand: Graph neural diffusion. In International Conference on Machine Learning, pages 1407-1418. PMLR, 2021.
[29] David Belanger and Andrew McCallum. Structured prediction energy networks. In International Conference on Machine Learning, pages 983-992, PMLR, 2016.
[30] Colin Graber, Ofer Meshi, and Alexander Schwing. Deep structured prediction with nonlinear output transformations. Advances in Neural Information Processing Systems, 31, 2018.
[31] Victor Garcia Satorras, Zeynep Akata, and Max Welling, Combining generative and discrimi- native models for hybrid inference. Advances in Neural Information Processing Systems, 32, 2019. 3
[32] Julian Besag. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), 24(3): 179-195, 1975. 3,5
[33] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans on image synthesis. Advances in Neural Information Processing Systems, 34:8780-8794, 2021.
[34] Xiang Lisa Li, John Thickstun, Ishaan Gulrajani, Percy Liang, and Tatsunori Hashimoto. Diffusion-LA LM improves controllable text generation. arXiv preprint 14217 2022.

---

[35] Emiel Hoogeboom, Victor Garcia Satorras, Clément Vignac, and Max Welling. Equivariant diffusion for molecule generation in 3d. In International Conference on Machine Learning.
pages 8867-8887. PMLR, R, 2022. 3
[36] Hyungjin Chung, Jeongsol Kim, Michael T Mccann, Marc I. Klasky, and Jong Chul Ye. Diffu- sion posterior sampling for general noisy inverse problems. arXiv preprint arXiv:2209. 14687,
2022. 3
[37] Jiaming Song, Arash Vahdat, Morteza Mardani, and Jan Kautz. Pseudoinverse- diffusion models for inverse problems. In International Conference on Learning Representations, 2023.
3
[38] Joseph J Pfeiffer III, Jennifer Neville, and Paul N Bennett. Overcoming relational learning biases to accurately predict preferences in large scale networks. In Proceedings of the 24th International Conference World Wide Web, pages 853-863, 2015. 5
[39] Diederik P Kingma and Max Welling, Auto-encoding variational bayes. arXiv preprint
1rXiv:1312.61 14, 2013. 6
[40] Danilo Rezende and Shakir Mohamed. Variational inference with normalizing flows. In International conference machine learning, pages 1530-1538. PMLR, 2015. 6
[41] Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. arXiv preprint arXiv:2 210.22200000910,, 2021. 6, 17
[42] Fei Wang and Changshui Zhang. Label propagation through linear neighborhoods. In Pro- ceedings of the 23rd international conference on Machine learning, pages 985-992, 2006.
7
[43] Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining label propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2020.
[44] Jaemin Yoo, Hyunsik Jeon, and U Kang. Belief propagation network for hard inductive semi-supervised learning. In IJCAI, pages 11178-4884, 2019. 7
[45] 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, pages 3651-3662, 2021. 7
[46] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725-1735.
PMLR, 2020. 7
[47] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793-7804, 2020. 7, 8
[48] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In Proceedings the AAAI Conference on Artificial Intelligence, volume 35, pages 1 11168-11766 2021. 7,8 8
[49] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. 7,8
[50] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. arXiv preprint arXiv:2105.07633 2021. 7.8
[51] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. arXiv preprint arXiv:2205.0743 073008, 2022. 7.8
[52] Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In AAAI. AAAI Press, 2021. 7, 8
[53] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated bi-kerlel graph neural networks for modeling both homophily and heterophily, 2022. 7.8
12

---

[54] Xiyuan Wang and Muhan Zhang. How powerful are spectral graph neural networks. In International Conference on Machine Learning. pages 23341-23362. PMLR, 2022. 7. 7
[55] Yunsheng Shi, Zhengjie Huang, Shikun Feng. Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervissd classification. arXiv preprint arXiv:2009.03300 2020. 7,8
[56] Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34:6695-6700 2021.
9
[57] Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning to ponder. In 8th
ICMI. Workshop on Automated Machine Learning (AutoMI.). 9
[58] Jascha Sohl-Diccstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsuper- vised learning using nonequilibrium thermodynamics. In International Conference on Machine Learning, pages 2256-2265. PMLR, 2015.
(59] Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In International Conference Learning Representations. 10
[60] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances Neural Information Processing Systems, 34:9061-9073 2021. 17
[61] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. International Conference on Machine Learning, pages
4663-4673. PMLR, 2019. 18
[62] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017. 22
[63] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre- trainiann graph neural networks, arXiv preprint arXiv: 1905. /2265,
2019. 26
13

---

A Details of DPM on partially labeled graphs
A.1 Derivation of variational lower bound
In this section, we provide a detailed derivation the variational lower bound in Equation (1).
log Po (y) log E polsu ((ni))
po (yL [G, yu. y (
po y (1:
log E Eive v (1L)
(ye y (1:2)) (r.))
G) q y (1:T)) (z)) log logge(( (y (ITT)
2 yaee a (1 wL)
= Bycver (ttyeggmmlln
log (1:3) (G) p( y)) log ((vcclb))
= Becuerles) [8 (Bot
(oy Dlogoo (1:1)))) (( log ((rell)))))))
A.2 Parameterization
Here, provide more detailed parameterization for DPM-SNC. Following the Gaussian diffusion, parameterize p(y² and (y ( as (x(()) and Nyy woyy") G.
respectively, Here, we set of to 3g. We also define (o G, as follows:
Be
( G,t,
Vi co co(t(",G.t)
(2)
Vo
where dr - 3, and a₁ III Og We implement the residual function Eo ( (,, through GNN. The implementation details are described in Appendix C.
A.3
Detailed training objective
We describe the detailed training objective of LVLB for optimization. We first rewrite LVLB follows:
LVLB
log (2) - log 4(2 (0y (1:17 (0)) - log ((vrler)))
Ee(werlee (
B
(I
(1)(0) ()) + logrly (m))) log (ev ((vrr (en.))
E 1
log
po (1 (t) (()((-2)12)) +logpyy(1)) - log ((2L)1))
E (
log
(0)))))))))))11)) ( y)
((2)(0))) (2))
(o (1))
+ log p(y)21)
log (ogggueleu ((g
log
((y(t-1) y() y)
((y(T))y)
T
(a G, ()))
( log p(y
-Egguluu)
E Bg(g((:))1))
log a( 11()) y)
log ((1r)11))
(T)())
=Bggoulle)
Σ
(t) DPM + C log
log a (()))))))))
where S is a training objective for a / step, and C is a constant with respect to the parameters
Following Ho al. [16], we simplify c(t) with residual function (t) G, in Equation (2).
c C CCEE--((.1)
20 - a,) ||e colvāry + VI- G,t)
where C' is constant with respect to the parameters 0. An additional suggestion from Ho et al. [16] to set all weights of the mean squared error to one instead of /2 /2a - ax), and we follow this suggestion in this paper.
14

---

A.4 Manifold-constrained sampling
Algorithm 2 Manifold-conssraineed sampling
1: Input: Graph G, node attributes æ, labels yt, and temperature of randomness 7².
2: Get ( ~ (T) 0
Initial sampling
3: for 1..,.....
4: Get (2;
5: Set g(t) t Yas
(((=1)
Bot
E0(y
(t
1) G,t
+ 00112
11-1142
6: Set ((+ t 1
(((+)))
1-he1
co
(++1) G,++1)
Vas+i
Vi-mi12
7: Set (()) t
7(t)
-Y (1y(1
VL 14 ((++1)
> caaifold-constrainee gradient
8:
Set yo t DU
(t)
9:
Get 0, 0, 1)
10: Set Vi. Varyr. + v1 04
Projection step
11: Set y(()) t UL Uuy
12: end for
(0)
13:
return yo
To sample from po(ye you G, yr), we use a manifold-constrained sampling proposed by Chung et
al. [18]. Here, the update rule of the reverse process for = O,..., 1 defined as follows:
g())
1
((+))
Bi+1
(tt1
G,t+1) a++12
Val
VI actl
40 Y0
(
(t)
y( =g()) 7 dgit+))
yL VL (1-1)
2
(4)
yL v o. + v1 0+Z
where z is sampled from (2 0, 72) The Equation (3) is temporal reverse diffusion step before applying the manifold-constrainee samplings. The Equation (4) applies the manifold-constrained gradient 0y(++1) 1 VL (t+)) Here, g is the label estimate in + steps defined as follows:
0
i ((+1)
()((t)))
1 ā+t1 co (y (++ Eo(y(tt),G,++))) ,,1+1))
Vau+1
VI 04+1
where y is hyper-parameter We set y to 1/1/y/ -i 1 The Equation (5) is projection step. Additionally, we introduce parameter control the randomness; when we set zero, the modified reverse step becomes deterministic. This allows to control the randomness in obtaining samples. We describe the detailed sampling algorithm in Algorithm
15

---

B WL test and GNN's expressiveness
In this section, we provide the proof of Theorem in detail.
B.1
Preliminaries
Algorithm 3 I 1-dimensional Weisfeiler-Lehman algorithm
Input: Graph G (VG, go 2 and the number of iterations T.
2: Output: Color mapping Xo Do + C.
3: Initialize: Let (²) <- hash(rr,) for u E VC.
4: for tort=10 l...., ".....,Ta do
5: for each E yo do
6: Set (c(()) + hash(xx Axx (u) (o()))
7: end for
8: end for
9: Return: x2
We denote set as O}. and multiset as {.). which is set allowing duplicate elements. We represent the cardinality of set multiset S as [S]. A graph is denoted G (VC
where yo stands for the set of nodes, E for the set of edges, and x = { : v E ya for the mode-wise attributes. We also use (N) graph G. We abbreviate a set of integers using the notation [m]] = (O....,,, m). We also assume the hash functions are all injective and denote them by hash(-).
{u yc fu, u) Ed} denote the set of neighbor nodes of node e in
Definition (Vertex coloring). Vertex coloring Xa(v) is an injective hash function that maps a vertex in graph G to color from abstract color set C. Next, with slight abuse of notation, we let the graph color XG indicate the multiset of node colors in graph G, ie., X = (xx(v)= : E VOB. B.
Now we explain the I-dimensional Weisfeiler-Lehmarl (1-WL) algorithm [19], a classical algorithm distinguish non-isomorphic graphs. At a high level, the 1-WL test iteratively updates node colors based on their neighbors until a stable coloring is reached. To be specific, given vertex v. the initial node color X (v) is set using an injective hash function on the node attribute x.. At each iteration, each node color is refined based on the aggregation of neighbor node colors, e.g., Kx6- (w)= : u E (N(v)) B. At the final T-th iteration, the algorithm returns the graph color xe. We provide detailed description in Algorithm 3.
The 1-WL test allows to compare a pair of graphs G, H using the refined graph colors xē x the two graph colors Xe and X are not equivalent, two graphs G, H are guaranteed be non- isomorphic. Otherwise, the test is inconclusive, i.e., the two graphs G, H are possibly isomorphic. We provide an example run of the 1- test in Figure 8(a), where the test inconclusive.
Related to the I-WL. algorithm, we first prove a characteristic of that will be later used in our proof.
Lemma 1. Consider running I-WL on two graphs G = (VG, E x0) and H = (y" E" x If the initial graph colors of two graphs are distinct, i.e., x2 # XB. the respective outputs of the I-WL Tf' also distinct, i.e XG # XH-
1-1 The rest of the proof is Proof. We first prove that X6 # Xir is satisfied when X²= * XH straightforward by induction on t. To be specific, the 1-WL updates X and Xas as follows:
N = (hasb(x (v), (v), xxx=(() u No(e) : or vOB. X Khash(xi> (v), xxx= (w): : e NH (v)B) 'dB. Since hash(-) is an injective function, Xa and X are distinct for Xo= + x t-1
B.2 AGG-WL test
Next, we describe the newly proposed AGG-WI test, which an analog of our DPM-SNC. Similar to the 1-WL test, our AGG-WL test assigns node colors and iteratively refines them based on the
16

---

neighbor node colors. However, AGG-WL generates augmented graphs at initialization, creating multiple "views" on the graph with diverse initial vertex coloring. Then applies 1-WL on each of the augmented graphs to obtain the augmented graph colors. Finally, AGG-WI aGG--Wa.ggreettes the augmented graphs colors.
The complete algorithm is described in Algorithm 4. Given graph G = (VG,E* x0) and the set of possible node-wise augmentations z the algorithm generates augmented graph G particular, the augmented graph Gm is defined as follows:
G = (VC, gG a ".",, Ec = {(-,0 2 2;") : x" = : E V/, x" E 2
where th is an augmentation method z The algorithm creates an augmented graph G by node-wise concatenation of nm its node attributes æ.C where _. denotes the node-wise attribute augmented by zmh The symbol -||- denotes the concatenation of two elements. Furthermore, z is unique token, where G has the same information as G. Also, with a slight abuse of notation, we let AGG indicate the multiset of augmented graph colors, i... fx m E []]] Here, | denotes the cardinality of set n
the graph color returned by the AGG-WL XG
AGG =
Algorithm 4 Aggregation Weisfeiler-ILhhmg algorithm
1: Input: Graph G (VG, EG .r.). the number of iterations T, and the augmentation set 2
2: Output: Color mapping Xe yc -> C.
3: Initialize: Generate 2 augmented graphs G = =(VG, Ea : Gm)) where & {(x x(²)
e E yC) for zm E gc Let x (v) t- hash(a for v E VG m [|
4: for t ===1, .... T do
5: for each
do
6: for E [| do
7:
Xem (v) hash(x 1-1 (v), (xx : E Nom (v)))
8: end for
9: end for
10: end for AGG
11: XG
16x- E []
12:
Return: XG
AGO
Our contribution is establishing the connection between the AGG-WL and the DPM-SNC: aggregation of refined graph colors for augmented graphs and marginalization over latent variables. More detail between DPM-SNC and the AGG-WL test described in Appendix B.3.2.
We note that our algorithm bears some similarities with several previous studies. The DS-W WI. and DSS-WL WI. test [41] defined modified WL-test based on the set of subgraphs (instead of augmented graphs) with a modified edge set E'. Hang et al. [13] uses a collective algorithm to consider pseudo- labels as additional inputs to boost GNN expressiveness. However, they rely on the assumption that one can find an "optimal" pseudo-label to discriminate a pair of graphs, which may be hard to realize in practice. Zhange et al. [60] proposed labeling tricks that learns capture dependence between nodes also by adding additional features, but mainly focus on link prediction in inductive settings.
B.3 Proof of Theorem 1
Let us start by restating Theorem 1.
Theorem 1. Let I-WL-GNN be GNN powerful as the 1-WL test. Then, DPM-SNC using 1-WL-GNN is strictly more powerful than the I-WL-GGN in distinguishing non-isomorphic graphs
Proof. We divide the proof into two parts, Appendices B.3.1 and B.3.2. In Appendix B.3.1, we show that the AGG-WL test is strictly more powerful than the 1-WL test. In Appendix B.3.2, we show that DPM-SNC using 1-WL-GNN is as powerful as the AGG-WI test. From these two proofs, one can conclude that DPM-SNC using a 1-WL-GNN is strictly more powerful than 1-WL-GNNS in distinguishing non-isomorphic graphs.
17

---

B.3.1 Expressiveness of AGG-WL test
In this subsection, we prove that the AGG-WL test is strictly more powerful that the 1-WL test. The high-level idea is showing that (i) the AGG-WL test least as powerful as the 1-WL test, i.e., any two graphs distinguishable by the I-WL test is also distinguishable by the AGG-WL test, and (ii) there exist two non-isomorphic graphs that are indistinguishable by the 1-WL test, but distinguishable by our AGG-WL test.
Lemma 2. AGG-WS WL is at least as powerful as WL in distinguishing non-isomorphic graphs, i.e., any two non-isomorphic graphs G, H distinguishable by WL are also distinguishuble by AGG-WL.
Proof. We first note that both 1-WL, and AGG-WI. can discriminate two non-isomorphic graphs with distinct sizes in straightforward way. Therefore, we focus on non-trivial cases for two graphs = (VG EG x.C,, H (VH, E x where the number of nodes and edges are same, ie., | Vd 1.1691
1 The cardinality of the augmentation sets are also the same, [ = 1z We prove if these two graphs G, H are distinguishable by the I-WL, two graphs G, H are also distinguishable by the AGG-WL, i.e., if xa + Xir. then x + X1I
First, since xe # X is satisfied, X6 # X is trivial. Additionally, the initial graphs colors of graph augmented by the unique token and any other augmentations are distinct, i.c., X6 of 0 - X x2 This implies X6 & AGG = .x X = according to Lemma 1 which
one can shows distinct initial graph colors produce the distinct outputs of 1-WL. Since x E XG AGG
AGG
see that XG * xH
AGG
Next, we show that there exist two graphs G. H indistinguishable by the 1-WL test, but distinguishable by the AGG-WI WL test. We first show a simple example from Figure 8(a), then for a family of circular skip link (CSL) graphs [61].
Lemma 3. Two graphs A, are indistinguishable by the I-WL. but distinguishable by the AGG- WL.
Proof. In Figure 8(a), two graphs A, B with 6 nodes are given. Here, the graph color computed by the 1-WL are equivalent, i.e., X = X (two light blue nodes and four gray nodes). Therefore, two graphs A, B are indistinguishable by the 1-WL.
Next, prove that graphs A, B are distinguishable by the AGG-WL. Since Lemma shows 1-LL always computes a distinct graph color from distinct initial graph colors, we only need to show that there exists augmented graphs AT DTth with the same initial color has distinct graph
colors computed by the 1-WL. Then, for two augmented graph sets {ATh m [[ZV]] []} and
{B" 18mmm m E [|Z)* []}, we can show that the graph colors computed by AGG-WL are always distinct.
We show simple case, where augmented graphs with non-zero augmentation
node results dis- tinct graph colors computed by the AGG-WL. We denote "single binary node feature augmentation", z' the case where node i is non-zero augmented and other nodes are augmented with zero, e.g.,
23 = (0, 0, 1,0,0. 0, 0}. In Figure 8(b) the non-zero augmented node is colored in blue, and others colored transparent. After applying the 1-WL. algorithm each graph, we obtain the graph color a and X for i E {I...., 6). It is clear that xx i {I,...,6)] 6} + Ux : {l...., 6) H. thereby two graphs A, B are distinguishable by AGG-WL.
Circular skip link graphs. CSL graph is denoted as CSL(n, r). where n is the number of nodes, i.e., V = (0, (0,...,.l - } and is the skip connection length. For and r,, r < 1 must hold. There exists 2n edges, between node and (i+1) 1) mod n forming cycle, and between nodes and (i+r) mod n forming a skip link for i E {O...., -11- 1}.
Lemma 4. For n 2 8, E n/2 - 1}. two graphs CSL(n, 2) and CSL(n, r) are indistinguishable by the 1-WL, but distinguishable by the AGG-WL
Proof. We first give a brief proof of why CSL(n, 2) and CSL(R, r) are indistinguishable by the 1-WL, then prove they are distinguishable by WL. We consider a non-trivial case where the node attributes are all same, i.e., (c) = (u) for E DC.
Let the initial color be cu for all the nodes for graphs CSL(n, 2) and CSL(n, r). x²(v) = co Ve yG G E (n,L(n, 2), (SL(n,r)). Then, for all nodes E DG, the color refinement process can
18

---

A
A²
A²
A3
A
A
A6
XA
AA
X
X
X
X
B
B1
B
B3
B
B
B6
XB
XB
XB²
XBa
XB*
Xg
X
(a) 1-WL
(b) AGG-WL
Figure example of two non-isomorphic graphs A, B indistinguishable by 1-WL,, but dis- tinguishable by the AGG-WI. (a) Two graphs A, B are associated with nodes sharing the same attribute. The 1-WL computes the same graph color for A, B, i... x² = X (b) Applying AGG- WL with "single binary node feature augmentation" to the graphs A and B. This results in six cases for each graph. One can see that the multiset of augmented graph colors are different, i.c. [x (1......0 6 * lx : (1...., ,,, }) thereby two graphs A, B are distinguishable by the AGG-WL.
than be written as (v) hash(co, fco, co, co, co.) All nodes have identical colors eı for both graphs CSL(n, 2), CSL(n, r). refining the initial graph color. Therefore CSL(n,, 2) and CSL(n,,) are indistinguishable by the 1-W..
Now we consider the AGG-WL. Again, we only need to show that there exists augmented graphs A', Bi with the same initial color but having distinct graph colors refined by the 1-WL. Given symmetry, there is only one case of an augmented graph that adds a non-zero augmentation to one node. We v. denote the i-th node in graph and denote the augmented node up- We denote each augmented graph as CSL(n, 2) CSL(n, r and let the initial color (1)) = C1, and Vi {l...., 1}. VG (CSL(n, 2) CSL(n, (o( = cp.
Iteration We focus on the four nodes connected to up. Since r [3,n/2 1), two node Un-ry Cr distinct. The color refinement be written following:
F {Ui, U2, Un 2n XesL(n.2) (v) hash(co, fee, Co. co, coll) c2.
For u & (M1, U2 1n on -n-2)- 2). X (v) = hash(co, ( Co Co. co Gol)) = C3-
For (Ur,er, 1 on x ( (v) hash(co. [ Co. Co, Co C2.
u (U1, 1n )n ( (v) hash(co, [ co, co B) C3.
19

---

(SL(8,2)
XCSL(882)
T
CSL 2)
XCSL(
XCSL(82))*
CSL(8,3)
XCSL(8.3)
CSL(8, (8, 3)
(CS)()3))
(CS)
(a) Original graph and 1-WL coloring
(b) AGG WL coloring on CSL(8, 2) CS,( (8)
Figure 9: Example
non-attribute CSL(S8 2), CSL( 3) graph. (a) 1-WL returns graph 7
color for two graphs, i.e., XCSL(8,2) XCSL(8,3) (b) Considering symmetry, there is only one type of augmented graph that with non-zero augmentation on one node, we denoted the augmented graph as CSL((8 2) and CSL((8 3) In the process of 1-WL assigning colors augmented graph, they result different graph color from the second iteration, and one can conclude XCSL(8.2)) # (83))
Therefore CSL((8,) 2), CSL(8, 3) are distinguishable by the AGG-WL.
Since 1-WL showed XCSL(n.2) = XcsL(n.)) and augmented graphs showed XCSL(n,2)) XCSL(n.))" two graphs are indistinguishabl.
Iteration 2. Again, focus four nodes connected th- Here, describe color refinement for nodes U1 Pn-1, U2 2 since the following is enough to prove two graph colors are distinct.
For (vi, Pn- }. 2 (c)L( (v) hash (c2, ((1,, 022 02 Ca B} Ca-
For E [V2, Un -n (n,21 (u) = hash (c2, ffi, Cs e3 B}} =
For (V1, 11,, J. x(sL(n.))) (v) hash (c2, (c), c3 ca Ca 1I) Gg-
Since cs & (CsL(,,2)1, graphs are distinguishable, i.e., (CSL( * XCSL(
Then XESL(m.2) A X(SL(n.))) is satisfied as proved in Lemma 1, thereby two graphs CSL(n, 2) and CSL(n, r) are distinguishable by the AGG-WL.
In Figure 9, we provide an example with CSL(8, and CSL(8, 3), indistinguishable by the 1-WL but distinguishable the AGG-WL.
B.3.2 Correspondence between DPM-SNC and AGG-WL
Now, we explain the connection between the DPM-SNG and the AGG-W WL test. high-level, we show how DPM-SNC simulates the color refinement process of the AGG-WL, Our main idea stems from the marginalization in DPM-SNC, which can define the probability of the graph color X with the marginalization over augmented graphs. i.c., Po(X DPM-SNC considers sample space of graph colors, where each member X obtained from (x =) with an augmented graph GmD represented by "², By construction, DPM-SNC considers graph colors refinements for multiple augmented graphs, similar to how AGG-WL works.
Po(X )p(z (G) Specifically,
Lemma 5. DPM-SNC using 1-WL-GNN is as powerful as the AGG-WL test in distinguishing non-isomorphic graphs.
'The node labels is replaced to the graph color and applying a latent variable is interpreted as applying augmentation the given graph.
20

---

Proof. We show that if two graphs G, H are distinguishable by AGG- WL test, it is also distinguish- able by the DPM-SNC. Assume that the two graphs G, H are distinguishable by the AGG-WL. Then, the following condition is satisfied
AGG XG
AGG fix E 112 # XH H
[12
where the AGG-WL produces distinct sets of refined graph colors for G, H. Next, we discuss how the DPM-SNC can distinguish G, H. To this end, we first assume a GNN which as powerful as the 1-WL test [20], denoted as 1-WL-GNN. Specifically, we denote XG GNN the 1- I-WL-GNN, where X6m * X implies XGm * XH"
GNN graph color refined by
GNN for any augmented graph pair Gm .H"
Then, under the AGG + AGG the following condition is also satisfied.
Mx E [1 & M
GNN
[1
Here, we assume that DPM-SNC utilizes this I-WL-GNN to output graph color conditioned on an augmented graph, i.e., po (x z). Then, we can connect po (x z=t) with Xm as follows:
pe(x|G, = 1[x = XG
GNN
where II(a b] is an indicator function whose value is a and otherwise. Next, we also assume that p(z|G) is uniform distribution over 2 Then one show that:
(x(G)) = 2
GNN I = X
1
Then it follows that Px(X + H) since fxx@NN m E |1 + 1xx m E !| Therefore, G, H are distinguishable by DPM-SNC.
GNN
GNN
Our proof is valid when considering the multiple outputs. However, our practical implementation of DPM-SNC does not use multiple outputs at inference time since the DPM only considers the multiple random variables in the training objective." To this end, in Appendix F, we also investigate the inference scheme which aggregates multiple outputs to make final predictions."
'Our inference method described Appendix "In practice, we also use Gaussian diffusion for defining p(z(G), which still allows the GNN to consider infinite augmentations.
21

---

C
Implementation
In this section, we provide more details how we implement the DPM-SNC for experiments.
C.1 Transductive settings
Here, we provide the detailed implementation of DPM-SNC for transductive node classification.
Model architecture. We parameterize the residual function Eg (t) G,,)) of reverse diffusion step using a L-layer message-passian paseeegpssnnngggg GNN as follows:
( (t) G. 1) s(h(4)),
h (E) (COMBINE 2 (h (6-1) (..)))++ f(t))l( 9q ((h ((.,)) E E)).
(6) AGGREGATE
where ((h(1)) is multi-layer perceptron that estimates the residual using the final node represen- tation. AGGREGATE(-) and COMBINE functions are identical to the backbone GNN, and -|I- indicates the concatenation. Here, bę is z2 2:11y,") The f(.) sinusoidal positional embedding function [62]. We fix the dimension of sinusoidal positional embedding to 128.
Buffer construction. Following the temperature annealing approach of Qu et al. [7] in sampling pseudo-labels for optimization, we also control the temperature of randomness obtaining yo from (y G, Vr for buffer construction. To be specific, use the variance multiplied by the temperature E [0, 1J, instead of the original variance in the reverse diffusion step, e.g., setting 7 to zero makes the deterministic sampling.
Inference. To make final predictions yo from Po G, yy) for evaluation, we eliminate the randomness in inference time, i.e., set temperature to zero." If the target is one-hot relaxation of discrete labels, we also discretize the final prediction by choosing a dimension with maximum value.
C.2 Inductive setting
Here, provide the details of DPM-SNC for inductive node classification and graph algorithmic reasoning. For the inductive node classification, we use the same model architecture as in the transductive setting and use the deterministic inference strategy. For the graph algorithmic, we modify DPM-SNC to perform edge-wise prediction.
Graph algorithmic reasoning. Since the targets of the graph algorithmic reasoning task are defined on the edge-level, we apply a diffusion process the edge labels. We then recover the edge-level noisy labels through the reverse process.
The denoising model architecture in the reverse process has similar architecture the model architecture of IREM [26]. Specifically, the noisy edge target (f) is updated as follows. First, the noisy edge labels y and edge features are concatenated and passed through to the GNN layer, which aggregates them to obtain the node representation. Next, we apply element-wise addition of the time embedding vector to the node representation. Then, we concatenate pair of node representations and noisy targets for the given edges and then apply a two-layer MLP to update edge labels.
In contrast to the node classification, we maintain randomness at inference time, i.c., we use the stochastic reverse process for obtaining edge labels. This approach is consistent with the IREM, which also includes randomness at inference time.
We also investigate various stochastic inference strategies in Appendix F
22

---

D Data statisties
D.1 Synthetic data
We generate 1000 2 non-attributed cyclic grid and 100 x non-attributed cyclic grid for scattered
and localized training nodes scenarios, respectively. Then, we split 30%, 30%, and 40% of the entire nodes into training, validation, and test nodes.
Scattered training nodes: We randomly sample nodes in the graph to split them into training, validation, and test nodes."
Localized training nodes: We select the nodes in the region within the 30 grid as training nodes. Then, we randomly sample the remaining nodes in the graph to split them into validation and test nodes.
For illustrative purposes, we also describe both scenarios in Figure 10 with smaller graphs.
(a) Scattered-training
(b) iittvilidttst/vvaiiaaiionnn
(c) Localized-trainngg (d) test/validation
Localized-
Figure 10: Illustration of two scenarios. The non-gray nodes represent nodes in each split.
D.2
Transductive node classification datasets
Table 6: The data statistics of transductive node classification datasets.
Dutaset
nodes
i edges
features
classes
(training/valddatioonnsss) nodes
Pubmed [22]
19717
44338
500
(60/500/ /0/05000/000)
Cora [22]
2708
5429
1433
(440/5000/1000
Citeseer [22]
3327
4732
3703
( (120/500) 5500 1000)
Photo [23]
7487
119043
745
(160/ (74077087)
Computers [23]
13381
34493
767
10
(200/300/ 12881)
Roman [24]
22662
32927
300
18
(11331/5665, (5655//6666//66
Ratings [24]
24492
93050
300
(12246/6 26/////11//////
Here, consider graph with partially labeled nodes. We describe the data statistics in Table 6.
D.3
Inductive node classification datasets
Table 7: The data statistics of inductive node classification datasets.
(training/valiaationnnsss) data
Dataset
features
classes
graphs
Avg. nodes
Avg. I edges
Pubmed [9]
500
(60/500/100) 1100)
(5.0/5..45.6)
(6.7/5.8/6.7)
Cora [9]
1433
(1400 0000000//// (1000)00)
(5.6/4..944.7)
(7.0/5.8/5.3)
Citeseer [9]
3703
(120/55 /5////00//00 10000)
(4.0/3.8/3.8)
(4.3/4.0 3/8)
PPI [25]
500
(20/2/2)
(2245.3/3257.0/27622)
000998000)
Here, we consider datasets consists of a set of graphs. We describe the data statistics in Table 7.
Additionally, also consider training with additional cyclic grid for visualization in Figure 1.
23

---

D.4 Graph algorithmic reasoning datasets
Following Du et al. [26], we generate training graphs in each training step. Here, the training graphs are composed of graphs of varying sizes, ranging from two to ten nodes. The node features are initialized zero, and the labels are defined on the edges, e.g., the shortest distance between two nodes. Then, we evaluate performance on graphs with ten nodes. Furthermore, we also use graphs with 15 nodes evaluate generalization capabilities.
24

---

E
Experiments setup
In this section, we describe the detailed experimental setup. For all experiments, we use a single GPU of NVIDIA GeForce RTX 3090. The tlyee-parameteen for each experiment are described in the following subsections.
E.1 Synthetic dataset
In this experiment, we implement each method with a one-layer GCN with 16 hidden dimensions. We search the learning rate within (1e-3, 5e-3, 1e-2) 2] for all methods. Other haper-parameters of each method follow their default settings. For DPM-SNC, we fix the diffusion step to 100. We also set the size of the buffer to 50 and insert five samples into the buffer for every 30 training step. We use a pre-trained mean-field GNN until the buffer is updated 10 times.
E.2 Transductive node classification
Table 8: The hyper-parameter search ranges for the homophilic graph. For hyper- parameters without a specific method in parentheses, applies all methods in the respective category.
Method
Hyper-parameterss
Search range
learning rate
{le-3, 5e-3, 3, 1e-2) [le- 3,50 3, Ie 2
methods
weight decay
number of layers
[2,4]
GNN-based methods (LPA, GMNN, GºNN CLGGNN, DPM-SNC)
hidden dimension
(64, 128)
weight of constraints for prrectunrd (LPA, G
(0.1, 10.0)
pseudo-labels sampling temperature
(0.1.0.3, 1.03
(GMNN, CL.GNN, DPM-SNC)
number label propagation hidden dimension (PTA) damping factor
{10, 100)
Non-GNN methods (L.,, PTA)
644, 128)
00.1, 0.3,, 0.5)
Homophilc graph. We describe the pappee--rramtter search ranges in Table 8. Additionally, we apply dropout with p 0.5 except for LP. Other srper-parameters of each method follow their default settings. For DPM-SNC, we fix the diffusion step to 80. We also set the size of the buffer to 50 and insert five samples into the buffer for every 100 training step. We use pre-trained mean-field GNN until the buffer is updated 20 times.
Heterophilic graph. Here, we describe the hyper- parameter settings for DPM-SNC as we use the num-
Table 9: The hyper-parametes search ranges of DPM-SNC for the heterophilic graph.
bers reported by Plantov et al. [24] for baselines. We describe the hyper-parameter search ranges in Table 9. Additionally, we apply dropout with p = 0.5, and we fix the diffusion step to 80. We also set the size of the buffer to 50 and insert five samples into the buffer for every 100 training step. We use pre-trained mean- field GNN until the buffer is updated 100 times.
Search range
leamiing weight decay
(3e-5, le- 4, 3e {0, 1,lee-,1e 1c-4]
number of layers
[2,4]
hidden dimension
512]
sampling temperature
(0.1, 1.0}
E.3
Inductive node classification
Table 10: The hyper- parammer search ranges of all methods for the inductive node classificaiton.
parameeprraeeeess Search range
leamnigg rate weight decay
(le-3, 5e-3, 1e-2) for small-scale graphs and (3e-5, 1e-4,,3e44 for huge-scale graphs
le 1e-3,55 5e 3, 2) for small-scale graphs and (0, 1e-5, 1e-4) for huge-scale graphs [2.4]
number of layers hidden dimension
128] for small-scale graphs and (512, 1024) for huge-scale graphs
We describe the hyper-parament search ranges Table 10. For the small-scale graph datasets, i.e., Pubmed, Cora, and Citeseer, we apply dropout with p 0.5. For the huge-scale graph datasets, i.e., PPI, we include the linear skip connection between each GNN layer. Other method follow their default settings. For DPM-SNC, we fix the diffusion step to 80.
of each
25

---

E.4 Algorithmic reasoning
Here, we describe the hyper-parameter settings for DPM-SNC as we use the numbers reported by Du et al. [26] for baselines. We search the learning rate and weight decay within (e--4, 1e-3) and {0, 1c-5, 1e-4), respectively. The hyper-parameters of the model are the same as the model implementation of IREM, using a three-layer GINEConv [63] with a 128 hidden dimension. We fix the diffusion step to 80.
26

---

Additional experiments
Ablations on various inference schemes. We also study various inference strategies for our DPM-SNC. We first investigate how temperature control affects label inference in real-world node classification tasks. In Figure (a), we plot the changes in accuracy for various temperatures т. One can see that reducing the randomness of DPM-SNC gives better prediction in real-world node classification tasks.
We also consider sampling various numbers of predictions for node-wise aggregation to improve performance. In Figure (b),,, the number of samples is increased to 2 the deterministic and the node-wise aggregation inference schemes show similar accuracy, and there are only minor performance improvements on Citeseer. In practice, classification tasks since the node-wise aggregation requires relatively long time.
deterministic inference in the node
80
80
Accuracy
Accuracy
70
70
Pubmed
Pubmed
60
Cora
Cora
Citeseer
Citeseer
50
502
0.00
0.25
0.50
0.75
1.00
2
2
20
Temperature
Number of samples (b)
Figure 11: (a) Accuracy with varying temperature. (b) Accuracy with the varying number of samples. The dashed line represents the accuracy of the deterministic inference scheme.
27


Reviews:
[{"review_id": "MfA2JGeDNL", "reviewer": "Reviewer_rLqd", "summary": "This paper proposes a new framework called the Diffusion Probabilistic Model for Structured Node Classification (DPM-SNC), which leverages diffusion probabilistic models for structured node classification on graphs. The framework aims to account for dependencies between node labels. The two key aspects of DPM-SNC are: (a) learning a joint distribution over the labels using an expressive reverse diffusion process and (b) making predictions based on known labels using manifold-constrained sampling. The authors test DPM-SNC in diverse scenarios, including partially labeled graphs in a transductive setting, as well as unlabeled graphs and in an inductive setting.", "questions": "1. Why did the authors exclusively use GCNII for the proposed method and not for the competitor models?", "limitations": "The authors have acknowledged the limitations of their approach.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. The paper effectively applies probabilistic diffusion, one of the hottest techniques in the community, to the structured node classification problem.\n2. DPM-SNC can be used in combination with any graph neural network (GNN) and to enhance performance on node classification tasks. This improvement is not solely empirical, as the authors provide theoretical analysis tying it to enhanced theoretical expressive power.\n3. The authors conduct a comprehensive experimental evaluation, showing DPM-SNC's superior performance in both transductive and inductive node classification tasks.", "weaknesses": "1. Although it is understandable that certain technical details are relegated to the appendix due to space limitations, the main paper could benefit from being more self-contained. This could be achieved by shortening the introduction or reducing some figures. Without referring to the appendix, especially for readers without expertise in diffusion models, it's difficult to grasp exactly how DPM-SNC makes predictions.\n2. The paper lacks a discussion or comparison with similar works that combine deep neural networks and label propagation for structured node classification [1, 2]. These works could be used as additional baselines or in discussions related to the proposed method.\n3. It appears that a limitation of the proposed method is that the diffusion process operates on (noisy versions of) labels of nodes, not their representation vectors. As a result, while DPM-SNC seems to work well for node classification problems, it's unclear whether the trained model could be effectively used as a general node embedding model for solving edge- or graph-level problems, or multi-label classification problems.\n\n[1] Huang et al., Combining Label Propagation and Simple Models Outperforms Graph Neural Networks, ICLR 2021\n[2] Yoo et al., Belief Propagation Network for Hard Inductive Semi-Supervised Learning, IJCAI 2019", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer rLqd,\n\nWe express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.\n\n---\n\n**W1. For readers without expertise in diffusion models, the main paper could benefit from being more self-contained.** \n\nWe will follow your suggestion and make space to introduce diffusion models in **Section 3.2**, using contents from **Appendix A** and **Appendix C**. We will also provide more details on the implementation, e.g., we relax the discrete labels to one-hot vectors to apply Gaussian forward diffusion process.\n\n---\n\n**W2. Two similar works could be used in discussion or as additional baselines.** \n\nWe will incorporate your valuable suggestion in our future manuscript. Both works are based on label propagation that linearly updates the node-wise predictions based on neighboring predictions. DPM-SNC mainly differs by using non-linear updates. In **Table A**, we show how our method outperforms the new baselines.\n\n*Table A. Transductive node classification performance.*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{Pubmed} & \\text{Cora} & \\text{Citeseer} \\newline\n\\hline\n\\text{C} \\\\& \\text{S} & 77.3 \\pm{0.0} & 80.2\\pm{0.0} & 69.5\\pm{0.0}\n\\newline\n\\text{BPN} & 78.2 \\pm{1.5}& 82.5 \\pm{0.9} & 73.3 \\pm{0.7}\n\\newline\n\\text{GCN+DPM-SNC} & \\textbf{83.0} \\pm{0.9} & \\textbf{83.2} \\pm{0.5} & \\textbf{74.4} \\pm{0.5}\n\\newline\n\\hline\n\\end{array}\n\n---\n\n**W3. Can your work effectively solve edge-level, graph-level, or multi-label classification?**\n\nYes. We already have solved edge-level tasks (algorithmic reasoning) and multi-label classification (PPI) in **Table 5** and **Table 4**, respectively. For graph-level problems, we did not conduct the experiments since our main focus is to use DPM-SNC for considering dependencies between multiple labels.\n\nNevertheless, to further alleviate your concern, we additionally consider graph classification by assigning a graph label as identical node-wise labels. We construct the final graph-level prediction via mean pooling over node-wise predictions. In **Table B**, our method still improves base GNN in some graph-level problems (MUTAG and IMDB-B). We hypothesize that the performance is improved due to the (1) enhanced expressive power and (2) expanded receptive field of GNN with repeated reverse diffusion. \n\n*Table B. Graph classification performance.*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{MUTAG} & \\text{IMDB-B} \\newline\n\\hline\n\\text{GCN} & 86.1 \\pm{5.5} & 73.2 \\pm{5.6} &\n\\newline\n\\text{GCN+DPM-SNC} & \\textbf{87.1} \\pm{5.1} & \\textbf{75.9} \\pm{3.4} \n\\newline\n\\hline\n\\end{array}\n\n\n---\n\n**Q1. Why did the authors exclusively use GCNII for the proposed method and not for the competitor models?** \n\nWe originally used GCNII to show our architecture-agnostic improvement of DPM-SNC on various GNNs. Nevertheless, to further resolve your concern, we conduct an additional experiment that combines GCNII with other competitors. In **Table C**, our method still outperforms other baselines.\n\n\n*Table C. Transductive node classification performance.*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{Pubmed} & \\text{Cora} & \\text{Citeseer} \\newline\n\\hline\n\\text{GCNII} & 82.0\\pm{0.8} & 84.0\\pm{0.6} & 72.9\\pm{0.5}\n\\newline\n\\text{GCNII+LPA} & 82.6\\pm{2.1} & 82.8\\pm{1.5} & 72.6\\pm{0.4}\n\\newline\n\\text{GCNII+G3NN} & 83.3\\pm{1.2} & 84.1\\pm{0.9} & 73.8\\pm{0.8}\n\\newline\n\\text{GCNII+GMNN} & 82.5\\pm{1.0} & 83.3\\pm{1.1} & 73.4\\pm{0.3}\n\\newline\n\\text{GCNII+CLGNN} & 82.9\\pm{0.9} & 84.3\\pm{0.4} & 73.2\\pm{0.6}\n\\newline\n\\text{GCNII+DPM-SNC} & \\textbf{83.8}\\pm{0.7}& \\textbf{85.3}\\pm{0.6} & \\textbf{74.1}\\pm{0.5}\n\\newline\n\\hline\n\\end{array}"}, {"review_id": "eLlkynQIMY", "reviewer": "Reviewer_kJkj", "summary": "This paper investigates the use of diffusion probabilistic models (DPM) to model node-wise label dependencies for structured node classification. The proposed DPM-SNC generalizes diffusion probabilistic models to work on partially labeled graphs in the transduction settings. The proposed model is proved to be more expressive than the classic 1-WL test. Experimental results demonstrate the effectiveness of the proposed model.", "questions": "See weaknesses above.", "limitations": "No potential negative societal impact of this work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper leverages the merits of diffusion probabilistic models (DPM) for structured node classification. A new training algorithm is proposed, which generalises DPM to work on partially labeled graphs.\n2. The theoretical analysis proves the improved expressive power of the proposed model.\n3. The design of experiments is thorough and the reported results demonstrate the effectiveness of the proposed model on various graph-based tasks.", "weaknesses": "1. The idea of using diffusion models is borrowed from the field of computer vision, where the diffusion and reverse process is more intuitive. However, why structured node classification would benefit from the diffusion and reverse process? Why the reverse process can be defined as a Gaussian distribution on graphs? \n\n2. It is unclear how the proposed model is applied to inductive node classification and what benefits the diffusion model can offer in inductive settings. \n\n3. As observed from Table 4, the performance of the proposed method is comparable or with limited improvements. More elaborations on these points are necessary. Also, the datasets used for inductive settings (except for PPI) are mostly used for transductive settings. Experiments on other relevant datasets should be added for inductive settings. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer kJkj,\n\nWe express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.\n\n---\n\n**W1-1. How does reverse diffusion benefit structured node classification?**\n\nThe reverse diffusion outputs a predictive distribution for structured node classification with *an additional degree of freedom to incorporate dependencies between labels* (**Section 3.1** and **Section 3.2**). This is particularly useful for prediction on partially labeled graphs, where the known labels provide additional information about the unknown labels, e.g., **Figure 1**. Among the structured node classification baselines, reverse diffusion is especially powerful since it enables *non-linear updates* (via GNN) to incorporate label dependencies *while easily conditioning on the known labels* (via manifold-based sampling [1]). \n\nAs a more intuitive analogy, our benefit is akin to using diffusion models for image inpainting, i.e., filling out the missing pixels in an incomplete image. Similar to how diffusion models are suitable for predicting unknown pixels from known ones, diffusion model is also suitable for predicting unknown node labels from the known ones.\n\n---\n\n**W1-2. How can the reverse process be defined as a Gaussian distribution on graphs?** \n\nTo define the diffusion and reverse process for node labels, we relax the node label into a continuous one-hot vector and apply Gaussian diffusion to this vector (similar to applying Gaussian diffusion to an RGB vector in a pixel).\n\n---\n\n**W2. How is the model applied to inductive node classification and what benefits the diffusion model can offer?**\n\nWe train our model with the same DPM-SNC algorithm. However, the set of unlabeled nodes $y_{U}$ is empty during training in the inductive setting, so our algorithm skips manifold-constrained sampling and buffer updates. At evaluation, we infer the labels without any conditioning on the known labels.\n\nNext, using a diffusion model benefits inductive node classification through propagating information via label-wise dependencies, similar to other inductive neural structured prediction baselines [2]. We also note how the diffusion model enhances the expressive power of GNNs (**Section 5**) even for inductive node classification. \n\n---\n\n**W3-1. It is necessary to elaborate on why the improvement is limited for inductive node classification (Table 4).**\n\nThe improvements are relatively small since there are no known labels, which is a significant information to be incorporated as inputs for structured prediction. Nevertheless, we would like to point out how our framework improves the performance over baselines, hence useful.\n\n---\n\n**W3-2. Except for PPI, the datasets used for inductive settings are mostly used for transductive settings.**\n\nWe first clarify that our experiments on algorithmic reasoning (**Table 5**) are also inductive.\n\n*Table D. Graph algorithmic reasoning tasks on graphs with 10/15 nodes.*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{Edge copy} & \\text{Connected components} & \\text{Shortest path} \\newline\n\\hline\n\\text{Feedforward} & 0.3016/0.3124 & 0.1796/0.3460 & 0.1233/1.4089 \n\\newline\n\\text{IREM} & 0.0019/\\textbf{0.0019} & 0.1424/0.2171 & 0.0274/0.0464\n\\newline\n\\text{DPM-SNC} & \\textbf{0.0011}/0.0038 & \\textbf{0.0724}/\\textbf{0.1884} & \\textbf{0.0138}/\\textbf{0.0286}\n\\newline\n\\hline\n\\end{array}\n\nTo further incorporate your concern, we experiment on additional datasets (PPI-{1,2,10} [2], DHFR [3]) in **Table E**. One can observe how our method still demonstrates a consistent improvement over the baselines. \n\n*Table E. Inductive node classification performance (F1 score for PPI and accuracy for DHFR).*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{PPI-1} & \\text{PPI-2} & \\text{PPI-10} & \\text{DHFR} \\newline\n\\hline\n\\text{GCN} & 65.08 \\pm{0.39} & 71.67 \\pm{0.22} & 96.16 \\pm{0.03} & 89.12 \\pm{0.71} & \n\\newline\n\\text{GCN+CLGNN} & 66.02 \\pm{0.42} & 71.82 \\pm{0.33} & 96.28 \\pm{0.04} & 91.48 \\pm{1.06} & \n\\newline\n\\text{GCN+SPN} & 68.12 \\pm{0.19} & 74.05 \\pm{0.15} & 95.34 \\pm{0.14}  & 89.95 \\pm{0.78} & \n\\newline\n\\text{GCN+DPM-SNC} & \\mathbf{70.08} \\pm{0.43} & \\mathbf{76.20} \\pm{0.43} & \\mathbf{97.00} \\pm{0.09} & \\mathbf{92.26} \\pm{0.63} &\n\\newline\n\\hline\n\\end{array}\n\n---\n\n**References**\n\n[1] Chung et al., Improving Diffusion Models for Inverse Problems using Manifold Constraints, NeurIPS 2022\n\n[2] Qu et al., Neural Structured Prediction for Inductive Node Classification, ICLR 2022\n\n[3] Wen et al., Meta-Inductive Node Classification across Graphs, SIGIR 2021"}, {"review_id": "kopETArDOK", "reviewer": "Reviewer_JeF8", "summary": "This paper proposes a diffusion probability model learning method for structured node classification, named DPM-SNC. The contributions of this paper are as follows. First, this paper leverages the high capacity of DPMs in learning joint label dependency and predicting posterior distribution conditioned on partially known data by devising DPM-SNC. Second, this paper introduces a new variational lower bound to train a DPM on partially labelled graphs. Moreover, this paper proposes AGG-WL test to theoretically analyse the expressive power of DPM-SNC using 1-WL-GNNs, which is more powerful than 1-WL-GNNs. Finally, detailed experiments on both transductive and inductive settings demonstrate DPM-SNC’s impressive performance.", "questions": "1.\tAdd more explanation to AGG-WL.", "limitations": "Authors have adequately addressed the limitations in this paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "There are strengths of proposed method:\n1.\tApplying DPM to learning partially labeled node label, to the best of our knowledge, is novel.\n\n2.\tThe experiments are detailed analyzed with both synthetic and real world data, which points out the strength of the method in different scenarios. The algorithmic reasoning shows the influence of different algorithmic elements in DPM, with great performance compared with baseline.\n", "weaknesses": "However, there are several drawbacks:\n1.\tThe idea to apply DPM to learn the joint distribution over the labels is novel. However, this paper has little novelty to DPM itself, which utilizes manifold-constrained sampling from previous works.\n2.\tThe analysis for expressive power follows the color assignments description in 1-WL test. The details of AGG-WL, the perturbations, and the aggregation need more explanation. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer JeF8,\n\nWe express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.\n\n\n---\n\n**W1. What is the novelty of this work compared to DPM itself?** \n\n\nWhen compared to the exisiting works on DPM, our work is the first to (a) train DPM in a semi-supervised setting using a new variational lower bound and (b) theoretically analyze the expressive power of a DPM by deriving an analog based on the Weisfeiler-Lehman (WL) test, i.e., aggregated WL test. We believe such contributions are quite novel even in the entire research field of DPMs.\n\n---\n\n**W2/Q1. The details of AGG-WL, the perturbations, and the aggregation need more explanation.** \n\nTo alleviate your concern, we will add a more detailed description of AGG-WL in Section 5. As stated in **Appendix B.2**, AGG-WL applies perturbations into the initial graph to create multiple augmented graphs, and aggregates the results of the 1-WL algorithm on each augmented graph. The perturbations are node-wise concatenations of node attributes $\\boldsymbol{x}$ with binary random features $\\boldsymbol{z}$. The aggregation represents hashing a multiset of the augmented graph colors to obtain the final graph color. \n\nIf you additionally point out any unclear aspects, we would be happy to provide a detailed description.\n"}, {"review_id": "aXjMUVpcdq", "reviewer": "Reviewer_7A8R", "summary": "The paper addresses the issue of structured node classification on graphs that consider dependencies between node labels. While GNNs have shown great success in machine learning on graphs, they predict node labels independently.\nThe authors propose a novel framework, DPM-SNC (Diffusion Probabilistic Models for Structured Node Classification), in which they use DPMs to learn a joint label distribution over both known and unknown labels while making predictions based on known labels using manifold-constrained sampling. Additionally, they present a novel training algorithm for DPMs. Theoretical analysis shows that it enhances the expressive power of GNNs. Experiments across multiple settings demonstrate the effectiveness of the proposed approach.\n", "questions": "1. What are the training and inference costs of the proposed method? How do they compare to the baselines?\n2. Regarding model training, do you use the same objective as DDPM to optimize the GNN parameters? Based on my understanding of your paper and code (correct me if I am wrong), the $q(y_U|y_L)$ term in the objective is not used to update $\\theta$. Instead, it is optimized by updating the buffer $\\mathcal{B}$. Maybe the \"Training algorithm\" paragraph could be revised so that it better reflects the proposed method?\n3. Among all kinds of generative models, why do you choose DPMs?", "limitations": "I do not see any significant, unreported negative societal impact.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "**Originality**\n\nThis paper ...\n- combined GNNs and DPMs for structured node classification.\n- proposed using manifold-constraint sampling for the transductive setting.\n- gave a novel expressivity metric, AGG-WL and proved that DPM-SNC is more powerful than its backbone 1-WL-GNN.\n\n**Quality**\n\nIn general, the math is solid and the claims are intuitive and/or empirically validated. The experiments are extensive.\n\n**Clarity**\n\nThe paper is well-written and easy to follow.\n\n**Significance**\n\nThe paper makes interesting and inspiring theoretical connections. Realistically, I am not so sure that this technique would be adopted in a production setting considering its cost and complexity.", "weaknesses": "No major flaws. See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer 7A8R,\n\nWe express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.\n\n---\n\n**Q1. What are the training and inference costs of the proposed method? How do they compare to the baselines?** \n\nTo resolve your question, we provide the statistics on training and inference time in **Table F**. \n\n*Table F. Time costs (sec) for (training/inference).*\n\\begin{array}{lccc}\n\\hline\n\\text{Methods}  & \\text{Pubmed} & \\text{Cora} & \\text{Citeseer} \\newline\n\\hline\n\\text{GCN} & 1.96/0.004 & 2.89/0.003 & 2.09/0.004\n\\newline\n\\text{GCN+CLGNN} & 639.04/0.074 & 608.19/0.061 & 862.40/0.078\n\\newline\n\\text{GCN+DPM-SNC} & 362.75/0.362 & 265.73/0.335 & 464.52/0.397 \n\\newline\n\\hline\n\\end{array}\n\nOverall, the structured prediction requires long training time to train the complicated node-wise label dependencies compared to learning only independent node-wise predictions. For prolonged inference time, we believe accelerating diffusion models, e.g., denoising diffusion implicit models (DDIM) [1], is an important future research direction (as described in limitations). \n\n---\n\n**Q2. Maybe the \"Training algorithm\" paragraph could be revised so that it better reflects the original DPM objective and updating buffer instead of the variational distribution.**\n\nIndeed, we use the original DPM objective given samples from the variational distribution. We will modify the paragraph to better reflect this point. However, it is worth noting that updating the buffer is equal to updating the variational distribution represented by the empirical distribution of the buffer, as mentioned in Line 168 and 176. \n\n---\n\n**Q3. Among all kinds of generative models, why do you choose DPMs?** \n\nWe chose DPM due to its ability to incorporate known labels easily as an additional condition. Once the generative distribution is trained, considering additional conditions, i.e., known labels, becomes non-trivial for other generative models like variational autoencoders. However, DPM defines a generative distribution using gradients of log density across multiple time steps, which enables incorporating known labels through manifold-based sampling [2].\n\n---\n\n**References**\n\n[1] Song et al., Denoising Diffusion Implicit Models, ICLR 2021\n\n[2] Chung et al., Improving Diffusion Models for Inverse Problems using Manifold Constraints, NeurIPS 2022\n"}, {"review_id": "iFIOzTlKGY", "reviewer": "Reviewer_w4tc", "summary": "This paper focuses on structured node classification on graphs by integrating diffusion probabilistic models to generate label distributions for unknown nodes. The authors design a novel training algorithm to apply DPMs, and a new variational lower bound. Theoretical analysis proves the proposed model is strictly more powerful than the classic 1-WL test. Experimental results also show its superiority over baseline methods on both inductive and transductive settings.", "questions": "- Please explain the reason of introducing diffusion problistic models. How can diffusion process improves GNNs on partially labeled graphs?\n- What is the computational complexity of DPM-SNC?", "limitations": "Please refer to the weaknesses.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and structured.\n- Application of diffusion problistic models in node classification is novel.\n- The theoredical analysis of 1-WL test is convincing.", "weaknesses": "- The use of diffusion problistic model is not well motivated? The reason for using diffusion process for partially labeled graphs is not explained.\n- It lacks a analysis of computational complexity of DPM-SNC, since it requires multiple steps of sampling.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer w4tc,\n\nWe express our deep appreciation for your time and insightful comments. In what follows, we address your comments one by one.\n\n---\n\n**W1/Q1. The diffusion problistic model is not well motivated. Why use diffusion process for partially labeled graphs?** \n\nFor the partially labeled graphs, we use the diffusion probabilistic model to incorporate known label information into the unknown label predictions. Specifically, known labels can be benefical by providing *an additional degree of freedom to incorporate dependencies between labels* (**Section 3.1** and **Section 3.2**), e.g., Figure 1. Among the structured node classification baselines, reverse diffusion is especially powerful since it enables *non-linear updates* (via GNN) to incorporate label dependencies *while easily conditioning on the known labels* (via manifold-based sampling [1]). \n\nWe also note how this motivation is reinforced by the state-of-the-art performance of the diffusion probabilistic model for the well-studied image inpainting problem: predicting unknown pixels from known pixels. This is a similar task to incorporate known (pixel) labels to predict unknown (pixel) labels. \n\n---\n\n**W2/Q2. It lacks a analysis of computational complexity of DPM-SNC, since it requires multiple steps of sampling.**\n\nThe time complexity is the number of diffusion steps $T$ times the time complexity of the backbone GNN that parameterizes the reverse diffusion. The space complexity is identical to the corresponding GNN, as reverse diffusion step $t$ only requires results obtained from the previous step $t+1$. For example, consider parameterizing DPM with GCN, where we use a hidden dimension of $F$ and $L$ layers. Since the GCN has $O(L|\\mathcal{V}|F^2+L|\\mathcal{E}|F)$ time complexity, the reverse process requires $O(T(L|\\mathcal{V}|F^2+L|\\mathcal{E}|F))$ time complexity. \n\n---\n\n**References**\n\n[1] Chung et al., Improving Diffusion Models for Inverse Problems using Manifold Constraints, NeurIPS 2022\n\n[2] You et al., L$^2$-GCN: Layer-Wise and Learned Efficient Training of Graph Convolutional Networks, CVPR 2020\n"}]

Author rebuttal:

Meta-review: In this paper the authors address  structured node classification on graphs, where there are possible dependencies between the node labels.The authors develop a new approach that  leverages the diffusion probabilistic model for structured node classification (DPM-SNC). In addition to theoretical analysis, the authors present results of extensive evaluations showing DPM-SNC's superior performance compared to baselines. The reviews agreed that the paper presents a novel, technically solid and potentially impactful contribution. There were also some questions about novelty of the work with respect diffusion probabilistic models, training and inference costs, computational complexity, etc, which the authors addressed during the rebuttal phase.
Decision: Accept (poster)