Neural Structured Prediction for Inductive Node Classification
Authors: Meng Qu
Huiyu Cai
Jian Tang
Venue: ICLR 2022 Oral (2022)

Abstract: This paper studies node classification in the inductive setting, i.e., aiming to learn a model on labeled training graphs and generalize it to infer node labels on unlabeled test graphs. This problem has been extensively studied with graph neural networks (GNNs) by learning effective node representations, as well as traditional structured prediction methods for modeling the structured output of node labels, e.g., conditional random fields (CRFs). In this paper, we present a new approach called the Structured Proxy Network (SPN), which combines the advantages of both worlds. SPN defines flexible potential functions of CRFs with GNNs. However, learning such a model is nontrivial as it involves optimizing a maximin game with high-cost inference. Inspired by the underlying connection between joint and marginal distributions defined by Markov networks, we propose to solve an approximate version of the optimization problem as a proxy, which yields a near-optimal solution, making learning more efficient. Extensive experiments on two settings show that our approach outperforms many competitive baselines.

Published as a conference paper at ICLR 2022
NEURAL STRUCTURED PREDICTION FOR INDUCTIVE NODE CLASSIFICATION
Meng Qu Huiyu C,i .Jinn Tang! 33,4
Mila- Québec AI Institute
Université de Montréal
HHEC Montréal
*Canadian Institute for Advanced Research (CIFAR)
ABSTRACT
This paper studies node classification in the inductive setting, i.e., aiming learn a model on labeled training graphs and generalize it to infer node labels on unlabeled test graphs. This problem has been extensively studied with graph neural networks (GNNs) by learning effective node representations, as well as traditional structured prediction methods for modeling the structured output of node labels, e.g., conditional random fields (CRFs). In this paper. we present a new approach called the Structured Proxy Network (SPN), which combines the advantages of both worlds. SPN defines flexible potential functions of CRFs with GNNs. However, learning such a model is nontrivial as it involves optimizing a maximin game with high-cost inference. Inspired by the underlying connection between joint and marginal distributions defined by Markov networks, we propose to solve an approximate version of the optimization problem a proxy, which yields near- optimal solution, making learning more efficient. Extensive experiments on two settings show that our approach outperforms many competitive baselines
INTRODUCTION
Graph-structured data are ubiquitous in the real world, covering a variety of applications. This paper studies node classification, fundamental problem in the machine learning community. Most existing efforts focus on the transductive setting (Kipf & Welling/ 2017 Veličković al.) 2018), i.e., using small set of labeled nodes in graph to classify the rest of nodes. In this paper. we study node classification in the inductive setting (Hamilton et al. 2017). which receiving growing interest. Given some training graphs with all nodes labeled, we aim to classify nodes in unlabeled test graphs.
This problem has been recently studied with graph neural networks (GNNs) (Kipf & Welling 2017] Hamilton et al. 2017 Gilmer et al., 2017 Veličković et al. 2018). GNNs infer the marginal label distribution of each node by learning useful node representations based on node features and edges. Once GNN is learned training graphs, it can be further applied test graphs to infer node labels. Owing to the high capacity of nonlinear neural architectures, GNNs achieve impressive results on many datasets. However, labels, and therefore node labels are predicted separately without modeling structured output.
limitation of GNNs is that they ignore the joint dependency of node
Indeed, modeling structured output has been widely explored by the literature of structured predic- tion (BakIr et al. 2007). Structured prediction methods predict node labels collectively, so the label prediction of each node can be improved according to the predicted labels of neighboring nodes. One representative approach is the conditional random field (CRF) (Lafferty et al. (001). A CRF models the joint distribution of node labels with Markov networks, and thus training CRFs becomes learning task in graphical models, while predicting node labels corresponds to an inference task. Typically, the potential functions in CRFs are parameterized as log-linear functions, which suffer from low model capacities. One remedy for this is to define potential functions with GNNs (Ma) ct al. 2018 Qu et al. 2019). However, most of the effective methods for learning CRFs involve
"Equal contribution.
Codees available at httpt:tt//////t http://gggguuubbcccee/eeeeeeeeee

---

Published as a conference paper at ICLR 2022
maximin game (Wainwright& & Jordan 2008 Sutton & McCallum, 2012
making learning often hard to converge, especially when GNNs are used to parameterize potential functions. Besides, as learning CRFs requires doing inference the graphical models, the combined model requires long run time.
In this paper, we address these challenges by proposing SPN (Structured Proxy Network), which is high in capacity, efficient in learning. and able to model the joint dependency of node labels. SPN is inspired by theoretical works in graphical models (Wainwright & Jordan| 2008), which reveal close connections between the joint label distribution and the node/edge marginal label distribution in Markov network. Based on that, we approximate the original optimization problem with a proxy problem, where the potential functions in CRFs are defined by combining a collection of node/edge pseudomarginal distributions, which are parameterized by GNNs that satisfy few simple constraints. This proxy problem can be easily solved by maximizing the data likelihood on each node and edge, which yields a near-optimal joint label distribution on training graphs. Once the model is learned, we apply to test graphs and run loopy belief propagation (Murphy et al., 1999) to infer node labels. Experiments on two settings against both GNNs and CRFs prove the effectiveness of our approach.
Note that although SPN tested on inductive node classification, this method is quite general and can be applied to many other structured prediction tasks as well, such as POS tagging (Church) 1988) and named entity recognition (Sang & De Meulder 2003). Please refer to Sec. 4.3 for more details.
2 RELATED WORK
Graph neural networks (GNNs) perform node classification by learning useful node representa-
tions (Kipf & Welling 2017 Gilmer et al. 2017; Veličković et al. 2018). Most earlier efforts focus
on designing GNNs for transductive node classification (Yng et al. 2016 Gao & Ji
2019
Xhonneux
cet al. 2020). and many recent works move to the inductive setting Hamilon et al.
2017
Gao et al.
2018 Chiang al. 2019: Li et al. 2019 Chen et al.) 2020a| Zeng al. (2020). Because of high
capacity and efficient training, GNNs achieve impressive results on inductive node classification.
Despite the success, GNNs only try to model the marginal distribution of each node label and pre- dict node labels separately without considering joint dependency. In contrast, SPN models joint distributions of node labels with CRFs, which predicts node labels collectively to improve results.
Another type of approach for inductive node classification is structured prediction, which focuses on modeling the dependency of node labels, so that the predicted node labels are more consistent. One representative approach is structured SVM (T'sochantaridis et al. 2005 Finley & Joachims) 2008 Sarawagi Gupta 2008), but it lacks a probabilistic interpretation to handle the uncertainty of the prediction. Another representative probabilistic approach is conditional random field (Lafferty et al.. 2001 Sutton & McCallum] 2006). which models the distribution of output spaces by using a Markoy network. CRFs have been proven effective in many applications, such POS tagging (Lafferty ct al. 2001), shallow parsing (Sha & Pereira 2003), image labeling (He et al. 2004), and sequence
label Ing (Lample al.) 2016 Ma & Hovy 2016 Liu et al. 2018). Nevertheless, the potential
functions in CRFs are typically defined as log- lon-linear functions, suffering from low model capacity.
There are also some recent works trying combine GNNs and CRFs. Some works GNNs to solve inference problems in graphical models (Dai et al.) 2016 Satorras et al., 2019:; Zhang et al.)
2020; Chen et al., 2020b; Satorras & Welling [0220). In contrast, our approach uses GNNs to
parameterize the potential functions in CRFs, which is in a similar vein to Ma et al. (2018) ) Qu
al.
(2019); Ma et al. 2019 202T): Wang et al. (202T). Among them, Ma et al. (2018) and Qu
et al. 2019) optimize the pseudolikelihood (Besag 1975) for model learning, and Wang et al. (022))
optimizes a cross-entropy loss on each single node, which can yield poor approximation of the true joint likelihood (Koller & Friedman| 2009 Sutton & McCallum 2012). Our approach instead
solves a proxy problem, which yields a near-optimal solution to the original problem of maximizing likelihood, and thus gets superior results. For Ma et al. (2019) and Ma al. (2021), they focus transductive node classification and continuous labels respectively, which are different from our work.
Lastly, learning CRFs has also been widely studied. Some works solve maximin game surrogate for learning (Sutton&& & McCallum (012) and some others maximize a lower bound of the likelihood function (uttonn& & McCallum, 2009). However, these maximin games often hard to optimize and the lower bounds are often loose. Different from them, we follow Wainwright et al. (2003) and build an approximate optimization problem as a proxy, which is easier solve and yields better results.
2

---

Published as a conference paper at ICLR 2022
3 PRELIMINARY
This paper focuses on inductive node classification (Hamilton et al. 2017). a fundamental problem in both graph machine learning and structured prediction. We employ probabilistic formalization for the problem with some labeled training graphs and unlabeled test graphs. Each training graph is given (y Xv, E), where Xy and y are features and labels of of nodes V. and E a set of edges. For each test graph (x.. F.), only features Xy and edges E are given. Then we aim to solve:
Learning, On training graphs, learn probabilistic model to approximate p(yv Xy. E). Inference. For each test graph, infer node labels y according to the distribution p(y X E).
The problem has been extensively studied in both graph machine learning and structured prediction fields, and representative methods are GNNs and CRFs respectively. Next, we introduce the details.
3.1 GRAPH NEURAL NETWORKS
For inductive node classification, graph neural networks (GNNs) learn node representations predict marginal label distributions of nodes. GNNs assume all node labels are independent conditioned on node features and edges, so the joint label distribution is factorized into set of marginals as below:
po E) = II sEV
po (uslxxv E
(1)
Each marginal distribution pe (v. Xv: E) is modeled as a categorical distribution over label candidates, and the label probabilities are computed by applying linear softmax classifier to the representation of node In general, node representations are learned via the message passing mechanism (Gilmer et al. 2017). which brings high capacity to GNNs. Also, owing to the factorization in Eq. (T. learning and inference can be easily solved in GNNs, where simply need to compute loss and make prediction on each node separately. However, GNNs approximate only the marginal label distributions of nodes on training graphs, which may generalize badly and result in poor approximation of node marginal label distributions on test graphs. Also, the labels of different nodes are separately predicted according to their own marginal label distributions, yet the joint dependency of node labels is ignored.
3.2 CONDITIONAL RANDOM FIELDS
For inductive node classification, conditional random fields (CRFs) build graphical models for node classification. A popular model is the pair-wise CRF, which formalizes the joint label distribution as:
(yv XV. E) = Zo(xv, E)
exp Σ
(v,, Xv, SEV
Σ (+.0)
Oze(Uo. Vc, Xv. E}}
(2)
where (xv; E) is the partition function. (, Xv; ; F)) and (ys: Yr, Xv: E) are sealar scores contributed by each node and each edge (s, l). In practice, these O-functions can be either defined as simple linear functions or complicated GNNs. To make the notation concise, we will omit xv and E in the i-functions, c.g., simplifying 0, (v., Xv, E)) as (y.). With these O-functions, CRFs are able to model the joint dependency of node labels and therefore achieve structured prediction.
However, learning CRFs maximize likelihood po E) on training graphs is nontrivial in gen- eral, as the partition function (xv, E)) is typically intractable in graphs with loops. Thus, a major line of research instead optimizes maximin game equivalent to likelihood maximization (Wainwright & Jorddn 2008). The maximin game for each training graph (yt, Xv, F)) is formalized as follows:
max log po V [Vv, E) = max min C(O, q), with C(O,
4
(0,(v)) - -E, E,, (v+)) +
Σ
(0srVV..8 vi) - E (v.. 1 (Vo, w0)} - H H[g(yv)] (3)
SEV
(+.))E
Here, g(yv) ) is variational distribution on node labels, q (v.) and gec (v=: ye are its marginal distribu- tions on nodes and edges. [[g[yv)] == BB [log glyv)] is the entropy of g(yv). Given the max- imin game, g and can be alternatively optimized via coordinate descent (Sutton & McCallum 2012). In each iteration, we first update the node and edge marginals {g.(y=))sev.
ga (Us, Br (x,0EE
3

---

Published as a conference paper at ICLR 2022
S7
NodeGNN
Iu
ay
EdgeGNN
Cuyy
Pseudomarginals by node and edge GNNs
CRF for joint label distribution
Graph
Figure I: Framework overview of the SPN. Our approach formulates a proxy optimization problem for learning, which is much easier to solve. Given graph, node GNN and an edge GNN are used to predict the pseudomarginal label distributions on each node and each edge respectively. Then these pseudomarginals serve as building blocks to construct near-optimal joint label distribution.
towards those defned by po- This can be done by MCMC, but the time cost is high, so approximate inference is often used, such as loopy belief propagation (Murphy et al. 1999). After q is optimized, we further update O-functions with the node and edge marginals defined by via gradient descent.
The optimal 0-functions are characterized by the following moment conditions:
Po(ys|xy xv, E) Iy {y.} E po (ys: ye /v,, , E) = Iogt (V.. ye))
v(s,t)
where Il [b] is an indicator function whose value is if a = and 0 otherwise. See Sec. A and Sec. in appendix for detailed derivation of the maximin game well as the moment-matching conditions.
B
Once the O-functions are learned, they can be further applied to each test graph (xy, E3) to predict the joint label distribution as pe (yyplxx- E). Then the best label assignment yi can be inferred by using approximate inference algorithms, such loopy belief propagation (Murphy al. 1999).
The major challenge of CRFs lies in learning. On the one hand, learning relies on inference, meaning approximate the node and edge marginals
that we have to update (g. (ya) (yy=))evv J.v. (ya, y/) (t)] (s.)) of pa at each step, which can be expensive. On the other hand, as learning involves a maximin game and the optimal q of the inner minimization problem in Eq. (3) intractable, we can only maximize an upper bound of the likelihood function for 9, making learning unstable. The problem becomes even more severe when 0 is parameterized by highly nonlinear neural models, e.g. GNNs.
MODEL
In this section, we introduce our proposed approach Structured Proxy Network (SPN). The general idea of SPN is to combine GNNs and CRFs by parameterizing potential functions in CRFs with GNNs, and therefore SPN enjoys high capacity and can model the joint dependency of node labels.
However, as elaborated in Sec. 3.2 learning such a model on training graphs is challenging due the maximin game in optimization. Inspired by the connection between the joint and marginal distributions of CRFs, we instead construct a new optimization problem, which serves as a proxy for model learning. Compared with the original maximin game, the proxy problem is much easier to solve, where we can simply train two GNNs to approximate the marginal label distributions on nodes and edges, and further combine these pseudomarginals (defined in Prop. I into a near-optimal joint label distribution. This joint label distribution can be further refined by optimizing the maximin game, although it is optional and often unnecessary, as this distribution is often close enough to the optimal one. With this proxy problem for model learning, learning becomes more stable and efficient.
Afterwards, the learned model used to predict the joint label distribution on test graphs. Then we run loopy belief propagation to infer node labels. Now, we introduce the details of our approach.
4.1 LEARNING
The learning task aims at training 9 to maximize the log- log-likelihood function log (e (xv, E)) for each training graph xy, E), which is highly challenging. Therefore, instead of directly optimizing this goal, we solve an approximate version of the problem as a proxy, which is training a node GNN and an edge GNN to maximize the log-likelihood of observed labels nodes and edges.
4

---

Published as a conference paper at ICLR 2022
The Proxy Problem. The proxy problem is inspired by Wainwright & Jordan (2008) which points out that the marginal label distributions on nodes and edges defined by a Markov network have inherent connections with the joint distribution. This connection is stated in the proposition below.
Proposition 1 Consider set of nonzero pseudomarginals (Ta ( SEV and (Tarlys, ve) (O0EE which satisfy En, Tax yr) = (B)))) and Ey. Tac Ut) To (V)))) for all (s,t) t) E E.
If we parameterize the O-functions of po in Eq. in the following way:
Tst (Us: ye) To (y
02(u.) = log V
Ose(Usr Ho) = log
V(s E E,
(5)
then {T, (y., Jsev and (Teclys Me (EAYER are specified by a fixed point of the sum- con-product loopy belief propagation algorithm when applied to the joint distribution po. which implies that:
To (U=) = (v.)
E
(ae vo) = V3). v(s,t) E E.
(6)
The proof is provided in Sec. C With the proposition, we observe that we parameterize the functions by combining a of pseudomarginals (Ta(H)) and (Tar yt (s,))E in the way defined by Eq. ( then those pseudomarginals can well approximate the true marginals of the joint distribution pe. i.c., (8))) = (ys) and (3). y1) = (p( yt) for all nodes s and edges (s, Given this precondition, if we further have To (ye) == Iy; (ve and (Be Mr) se L( [ye, yr) then the moment- moment-matching matching conditions in Eq. (4) for the optimal f-functions are roughly satisfied. This implies the joint distribution (y (xv, E) derived in this way is near-optimal one.
With the observation, rather than directly using GNNs to parameterize the f-functions, we use a node GNN and an edge GNN to parameterize the pseudomarginals {Ta Jev and (T (Mo, Ue (..))). For the pseudomarginal (y)) on node we apply the node GNN to node features Xy and edges E, yielding representation u, for node s. Then we apply softmax classifier u, to compute T (ya):
{ug)ues GNN mode (xv, E);
(y()) softmax(f (u.))))
where f maps node representation to a | dimennnsaia logit and y is the node label set. Similarly, we apply the edge GNN to compute a representation V. for each node s, and model Tat (Ve, Mc) as:
(viJ.ev GNNo (xv, E)
(yc Mt) softmax(g(v.. vz)) (y., Mr],
(8)
where g is function mapping a pair of representations ((D) x ()') dimeensional logit.
Given the parameterization, we construct the following problem as proxy for learning f-functions:
min 7,0
Σ d (ua)
Σ d (M(o (Ves H)) Tad (ye.)))))))
SEV
(x.))E
Tec Vt)
subject to
0, = =o
Oe (vs.)))) = llog
(9)
To (y.)
and
Tae vt) = Te(3))) Tan Mr) = Ta (ys),
for all nodes and edges, where dl can be any divergence measure between two distributions. By solving the above problem, (Ta (ye) beev and (Tee Mt (t.)EE will be valid pseudomarginals which can well approximate the true labels, i.e., To (y.) Re Lng [Vs)) and Fae (yr Me) ~ Ily: (We y.)]. Then according to the constraint in the second line of Eq. (9. 0-functions are formed in way to enable T=())) RJ Pe (ys) ) and Tu Me) RS Poooss M13 as stated the Prop. [ Combining these two sets of formula results in po (y())) zs Ly: [v. and (y(ye 31) Re Iy; {y+)- We see that the nomennt-mtchhin conditions in Eq. (4) for the optimal joint label distribution are roughly achieved, implying that the derived joint distribution po (yv xv, F.) is near-optimal solution the original learning problem.
One good property of the proxy problem is that can be solved easily. The last consistency constraint be ignored during optimization, since by optimizing the objective function, the optimal pseudomarginals 7 should well approximate the observed node and edge marginals, ie.. T, (v.) ) x Ly; {ya} and Tue (B.: Mr) ss [ oz) (y.. ye)] and hence 7 will almost naturally satisfy the consistency constraint. We also tried some constrained
(i.e. E,, (ys, vt) 7, (v:) and Σ,, Tse (V., y1) (u.))
5

---

Published as a conference paper at ICLR 2022
optimization methods to handle the consistency constraint, but they yield no improvement. See Sec. D of appendix for more details. Thus, we can simply train the pseudomarginals parameterized by GNNs to approximate the true node and edge labels on training graphs, i.e., minimizing d( {y, J. Ts (ys))
and d(((we wt > (ys. ), Tax (Vs, yt)). Then we build O-functions as in Eq. (5) to obtain a near-optimal joint distribution. In practice, we choose d to be the KI. divergence, yielding objective for as:
max
log (NG)+
Σ (,,))
log ( v().
(10)
This objective function very intuitive, where we simply try to optimize the node GNN and edge GNN to maximize the log-likelihood function of the observed labels on nodes and edges.
Refinement. By solving the proxy problem, we can obtain near-optimal joint distribution. In practice, we observe that when we have large amount of training data, further refining this joint distribution by solving the maximin game in Eq. (3) for a few iterations can lead to further improve- ment. Formally, each iteration of refinement has two steps. In the first step, we run sum-product loopy belief propagation (Murphy et al. 1999). which yields a collection of node and edge marginals (i.c., {g. (y.))ev and {qst Me) J ()))) E) approximation the marginals defined by pg. In the second step, we update the o-functions parameterized by the node and edge GNNs to maximize:
Σ (o,(0))) - (x (v.)))
Σ (O= vt)) - Egg. w/) (ys Dt]] (s,))E
(11)
REV
Intuitively, we treat the true label y and (v² vf") of each node and edge positive examples, and encourage the f-functions to raise up their scores. Meanwhile, those labels sampled from q (ya) and qst (ya: yr) act negative examples, and the O-functions updated to decrease their scores.
4.2 INFERENCE
After learning, we apply the node and edge GNNs to each test graph (Xy, F.) to compute the functions, which are integrated into an approximate joint label distribution pe (Y \xv, E). Then we this distribution to infer the best labely for each node E V. where two settings are considered.
Node-level Accuracy. Typically, we care about the node-level accuracy, i.c., how likely we can correctly classify a node test graphs. Intuitively, the best label y for each test node ă V should be predicted as y = arg max,, Po (ys xy: E), where po (y xx. EE) is the marginal label distribution of node ø induced by the joint ( x E). In practice. the exact marginal is intractable, so we apply loopy belief propagation (Murphy et al. 1999) for approximate inference. For each edge (š, i) test graphs, we introduce message function m²)s((s) and iteratively update all messages as:
(Ua) x Σ (cxp(((;(1)) + (ur(Va, vi))
II (EN(
mz-i(vi))
(12)
where N()) denotes the set of neighboring nodes for node s. Once the above process converges or after sufficient iterations, the label of each node ø can be inferred in the following way:
y arg (Oxx((xpp)))())
II my=s(
(13)
(EN(3)
Graph-level Accuracy. In some other cases, might care about the graph-level accuracy, i.e., how likely we can correctly classify all nodes a given test graph. In this case, the best prediction of node labels is given by y arg maxy, p(y; (xp, E). This problem can be approximately solved by the max-product variant of loopy belief propagation, which simply replaces the sum over yi in Eq. (2) with max (Weiss & Freeman 2001). Afterwards, the best node label can be still decoded via Eq. 13
4.3 DISCUSSION
In practice, many structured prediction problems can be viewed as special cases of inductive node classification, where the graphs between nodes have some special structures. For example in sequence labeling tasks (e.g., named entity recognition), the graphs between nodes have sequential structures. Thus, SPN can be applied these tasks well. In order for better results, one might replace GNNs with other neural models which are specifically designed for the studied task to better estimate the pseudomarginals, For example in sequence labeling tasks, recurrent neural networks can be used.

---

Published as a conference paper at ICLR 2022
5 EXPERIMENT
5.1 DATASETS
We consider datasets in two settings, which focus node-level and graph-level accuracy respectively.
Node-level Accuracy, The node-level accuracy measures how likely a model can predict the correct label of a node in test graphs. We use the PPI dataset (Zitmik & Leskovee 2017 Hamilton et al.) 2017), which has 20 training graphs. To make the dataset more challenging, we also try using only the first 1/2/10 training graphs, yielding another three datasets PPI-1, PPI-2, and PPI-10. Besides, we also build a DBLP dataset from the citation network in [Tagg et al. (2008). Papers from eight conferences treated as nodes, and we split them into three categories for classification according to conference domains ? 2014) of words in the title and abstract as node features. The training/valiin validationn/test graph is formed as the citation graph of papers published before 1999, from 2000 to 2009, after 2010 respectively.
For each paper, we compute the mean GloVe embedding (Pennington et al.
Graph-level Accuracy. The graph-level accuracy measures how likely model can correctly classify all the nodes for given test graph. We construct three datasets from the Cora, Citeseer, and Pubmed datasets used for transductive node classification (Yang et al. 2016). Each raw dataset has a single graph. For each training/validatiioneess graph. We denote the datasets as Cora*, Citeseer*, Pubmed
node of the raw dataset, we treat its ego network as
5.2 COMPARED ALGOITHTS
Graph Neural Networks. For GNNs, choose few well-known model architectures for compar- ison, including GCN (Kipf& & Welling 2017). GraphSage (Hamilton et al. 2017), GAT (Veličkovid
al. 2018). Graph U-Net (Gao & Ji 2019) and GCNII (Chen et al. 2020a).
Conditional Random Fields. For CRFs, we consider three variants. (1) CRF-linear: This variant uses linear f-functions in Eq. 2 which takes the features on nodes and edges for computation. (2) CRF-GNN. This variant parameterizes the f-ffuccionss as 0g (y())) with f and g defined in Eq. 7 and Eq. (8). where the node representations are generated by different GNN architectures (e.g.. CRF-GAT). We train these models via the maximin game as in Eq. (3) with sum-product loopy belief propagation.
fu, and 6.r 9t) = 9[V,. Ve).
(3) GMNN. We also consider GMNN (Qu et al., 2019), an approach combining GNNs and CRFs, which optimizes the pseudolikelihood function for learning.
Our Approach. For SPNs, we try different GNN architectures for defining the node and edge GNNs (e.g., SPN-GAT), By default, we only solve the proxy problem without performing refinement. We systematically compare the results with and without refinement in part 2 of Sec. 5.5
5.3 EVALUATION METRICS
On Cora*, Citeseer*, and Pubmed*, we report the percentage of test graphs where all the nodes are correctly classified (i.e., graph-level accuracy). On DBLP and PPI, we report accuracy and micro-F1 based on the percentage of test nodes which are correctly classified (i.e., node-level accuracy). For Cora*, Citeseer*, and Pubmed we run each compared method with 10 different seeds to report the mean accuracy and the standard deviation. For DBLP and PPI, we run each method with 5 seeds.
5.4 EXPERIMENTAL SETUP
For GNNs, by default we use the same architectures (e.g., number of neurons, number of layers) as used in the original papers. Adam (Kingma & Bal 2015) is used for training. For the edge GNN in Eq. (8), we add a hyperparameter 7 to control the annealing temperature of the logit g(ve, v:) before the softmax function during belief propagation. Empirically, we find that max-product belief propagation works better than the sum- num-product variant in most cases, so we use the max-product version by default. By default, we do not run refinement when training SPNs. See Sec. for details.
ML: ICML/NcurIPS. CV: ICCV/CVPR/ECCV. NLP: ACL/EMNI-//NACT
'The local subgraph formed by a node and its direct neighbors.
7

---

Published as a conference paper at ICLR 2022
Table 1: Result on PPI datasets (in %). SPNs get consistent improvement on GNNs and CRFs.
Algorithm
FPI-1
PPF2
PPI-10
PPI
Accuracy
Micro-F1
Accuncy
Micro-Fi F1
Aucuracy
Micro-F1 F1
Accuracy
Micro-F Fl
GCN
0.10
34.35
56.10
0.36
0.10
R2.28
0.89
GupbSAGE
81 0.07
67:30
84.13++ 0.04
72.93
0.04
0.03
92.
0.05
98.51
97.5
GAT
77.49 +0.20
60.72
0.25
81.35 + 0.19
68.55
+ 0.30
96.14
0.15
93.53
0.24
98.85
0.05
98.06
0.08
Graph U-Net
77.17 0.07
55.54
= 0.33
78.22
= 0.04
59.12
+ 0.30
83.15
= 0.04
68.70
0.08
86.29
0:04
75.57
0.18
GCNI
80.99 0.07
65.79
0225
84.81
0.06
74.54
4 0.14
97.53 4 0.01
95.86
0.01
99.39
0.00
98.97
0.00
CRI--innar
18.30
67.20
0.65
50.17
69.98
50.61
CRE-GCN
76.33 0.21
50.79
0.74
76.27
1: 0.10
49.47 1 0.63
77.08
0.07
52.36
0.72
77.34
0.07
53.60
0.36
CRE-CiaphSAAE
0.288
54.57
1.07
77.25 + 0.36
$3.48 + 1.00
77.65 + 0.38
54.44
1.34
77.21
+ 0.19
54.
3.09
CRF-GAT
76.50 0.49
$2.95
+ 0.40
76.76
0.61
55.01 + 0.93
74.58 + 0.92
54.98
1.13
70.42
+ 0.72
53.27 + 0.42
CRF-GONT
79.98 0.32
61.22
81.73
0.33
66.37
0.56
87.10
0.40
96.94
94.95 0.19
GMNN
57.20
81.21
67.46
2.92
94.67 +: 2:77
90.72
97.00
94.69
SPN-GCN
77.07 0.05
51.15
0.17
78.02
0.05
55.73 1 0.15
$0.59 1 0.01
61.36
0.11
0.20 82.56
66.70 0.77
SPN-GGupEAAGE
82.11 1111:000 0.03
68.56
0.07
85.40 1 0.05
74.45
1 0.07
95
1 0.02
91.99
0.04
98.55
0.02
97.56 0.03
SPN-GAT
79.01 0.1.7
64.02
0.40
83.55
0.12
72.57
+ 0.18
96.68
+ 0.13
94.41
0.31
99.04
0300
98.
0.10
SPN-GCNII
67.80
85.83
0.04
75.96
0.05
97.55
0.01
0.02
99.41
99.02
Table 2: Accuracy on Cora*, Citeseer*, Pubmed* DBLP (in %). SPNs achieve the best result.
Algorithm
Cora
Citeseer
Pubmed
DBLF
GCN
57.26 = 0.66
46.24 = 0.61
34 = 0.45
76.60 + 2.32
GraphSAGE
49.02 2.37
41.32 + 2.41
48.61
+ 1.28
73,81
+ 0.90
GAT
$1.99 + 3,51
47,94 + 0.46
50.89
+ 0.52
79.16
1.44
Graph U.-Net
56.07 + 0.57
45.91 + 1.65
51.77
+ 0.97
75.21
+ 2.68
GCNII
59.15 1 0.67
46.39 1 0.92
53.54 1. 0.98
81,79 1 0.88
CRF-Tinear
42.78 + 3.94
40.00 + 0.31
41.90 + 2.91
54.26 + 1.27
CRF-GAT
49.10 - 3.80
42.89 + 1.30
47.79 + 1.33
59.
4.15
CRF-UNet
53.49 + 2.47
43.66 + 2.12
50.02 + 0.88
57.46
3.07
CRE-GCNII
36.18 5.75
38.27
1 4.82
41.71
1. 4.79
60.55
1 2.23
GMNN
54.30 1.15
48.46 + 1.06
51.70
+ 1.23
76.54 2.93
SPN-GAT
58.78 = 1.21
49.02 = 0.78
52.91
= 0.54
84.84 + 0.73
SPN-LNe
58.03 0.54
46.97
1.06
51.36
+ 0.67
80.11 + 1.59
SPN GCNII
60.47 0.49
48.34
1 0.50
54.35
1. 0.64
83.57 1 1.33
5.5 RESULTS
Comparison with other methods. The main results the two settings are presented Tab. D and Compared against different GNN models, approach achieves consistent improvement (the relative underperformance of SPN-GCN and SPN-SAGE is related to the capacity of the backbone by using these GNNs as backbone networks for approximating marginal label distributions on nodes and edges, which demonstrates SPNs are able to model the
Tab. 2
GNNs and is explained in Sec. G.1 G..
structured output of node labels by combining with CRFs, and thus achieve better results.
Besides, SPNs also achieve superior results to CRF-GNNs which are trained by directly solving the maximin game in Eq. 3 as well as GMNN which optimizes the pseudolikelihood function. This observation proves the advantage of our proposed proxy optimization problem for learning CRFs.
Table 3: Run time comparison (in sec).
Table Micro-Fi with and w/o refinement (in %).
Algorithm GAT
DELF
PPI
Algoritim
Reline
PPT-
PPI-10
PPI
23.15
46088
SPN.
w/o
71.52
0.21
98.38 2 0.10
(GAT) 500.43
271366.0
71.58
SPN(GAT) 46.86
962.92
SPN.
wio
73.33
0.08
91.99
0:04
97.56 4: 0.03
GropiSAGE
with
73.68 + 0.10
92.49
002
97.77 + 0.02
2. Effect of refinement. By solving the proxy optimization problem in Eq. (9) we can obtain a
near-optimal joint label distribution on training graphs, based on which we may optionally refine the distribution with the maximin game in Eq. (3. Next, we study the effect of refinement, and we present the results in Tab. 4 By only solving the proxy problem, our approach already achieves impressive well approximate the original learning problem. Only on
results, showing that the proxy problem datasets with sufficient labeled data (c.g., PPI-10, PPI), refinement leads to some improvement.
3. Model architecture. SPN uses node GNN and edge GNN for computing node and edge marginals independently. In practice, we can also use a shared GNN for both node and edge marginals. We show results of this variant in Tab. 6 where it also achieves significant improvement over GNNs.
Efficiency comparison. We have seen SPNs achieve better classification results than GNNs and CRFs. Next, we further compare their efficiency by showing the run time DBLP and PPI. For PPI,
8

---

Published as a conference paper at ICLR 2022
Table 5: Comparison of learning methods (in %).
Table 6: Micro-FI of model variants (in %).
Algorilhm
Cora
Chesser
Algwiihm
PPE-2
Maximin Game
49.10
3,80
42.89 1,30
54.98 1.13
GAT
60.72 + 0.25
68.55 + 0.30
93.53 + 0.34
SPN-GAT
Pacudolikclitooa
$4.30 = 1.15
48.46 1,06
90.72 = 5.28
mode and edge GINNs
64.02 1: 0.40
72.37 = 0.188
94.41 4: 0.21
Prony Problem
58,78 1.21
49,02 0.78
95.87
0.02
shared GNN
SPX-GAI
63.72 1 0.38
70.99 0.25
95.19 1 0.15
which has 121 labels, we only report the training times on a single label. We use GAT as the backbone network for CRFs and SPNs. GAT and CRF are trained for 1000 epochs to ensure convergence, For the SPN, we train the node GNN and edge GNN for node/edge classification as Eq. (10) with 1000 epochs. The run times are presented in Tab. SPNs take twice as long for training than GAT, as SPN needs to train a node GNN and an edge GNN. Compared with CRFs, we can see that SPNs are much more efficient, because the proxy optimization problem in SPNs is much easier solve.
OMA
Coach
Cpod
(a) DBLP training.
(b) DBLP validation.
(a) GAT.
(b) Edge GNN.
(c) SPN-GAT. (same as ground truth)
Figure 2: Convergence curves for solving the maximin game Eq. (3) during model learning.
Figure 3: Case study. SPN correctly predicts all node labels than GAT and the edge GNN.
5. Comparison of learning methods. Next, we investigate different methods for learning SPNs, including directly solving the maximin game, optimizing pseudolikelihood, and solving our proposed proxy problem. We show the results for optimizing SPN-GAT in Tab. 5 We see solving maximin game yields poor results due unstable training. Although the pseudolikelihood method performs much better, the result is still unsatisfactory as it is not good approximation of the true likelihood. By solving our proposed proxy problem, SPN achieves the best result, which proves its effectiveness.
6. Convergence analysis. To better illustrate the advantage of the proxy problem for learning CRFs, we look into the training curves of SPNs, SPNs w/o proxy, and CRFs when optimizing the maximin game in Eq. 33. For SPNs, we optimize the node and edge GNNs on the proxy optimization problem Eq. (9) before doing refinement with the maximin game, while for SPNs w/o proxy we directly perform refinement with the maximin game without solving the proxy problem. We show the results Fig. 2 CRFs and SPNs w/o proxy suffer from high variance and low accuracy. contrast, owing to the near-optimal joint distribution found by solving the proxy problem, SPNs get much higher accuracy with lower variance even without refinement (see initial results of SPNs at epoch 0). Also, the refinement process quickly converges after only a few epochs, showing good efficiency of SPNs.
Case study. To intuitively see how SPNs outperform GNNs, we conduct some case studies on Cora*. We use GAT backbone networks, and show the prediction made by the GAT (the node GNN), the edge GNN, and SPN in Fig. 3 In all three cases shown the figure, GAT (left column) makes inconsistent predictions linked nodes, it fails to model the structured output. The edge GNN (middle column) also makes a mistake in the bottom case. Finally, by combining GAT and edge GNN with CRF, the SPN (right column) is able predict the correct labels for all nodes.
CONCLUSION
This paper studied inductive node classification, and we proposed SPN to combine GNNs and CRFs. Inspired by the connection of joint and marginal distributions defined by Markov networks, we designed a proxy problem for efficient model learning. In the future, we plan to explore more advanced GNNs model the pseudomarginals
edges, which are key to improving node classification results in SPNs. In addition, SPNs model joint dependency of node labels by defining potential functions on nodes and edges, and also plan to further explore high-order local structures, e.g., triangles.

---

Published as a conference paper at ICLR 2022
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint, 2016.
Gökhan Baklr, Thomas Hofmann, Bernhard Schölkopf, Alexander J Smola, and Ben Taskar. Predict- ing structured data. MIT press, 2007.
Julian Besag. Statistical analysis of non-lattice data. The statistician, pp. 119- 195, 1975.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML, 2020a.
Xinshi Chen, Yufei Zhang, Christoph Reisinger, and Le Song. Understanding deep architecture with reasoning layer. NeurIPS, 2020b.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, 2019.
Kenneth Ward Church. A stochastic parts program and noun phrase parser for unrestricted text. In ANLC, 1988.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). ICLR, 2016.
Hanjun Dai, Bo Dai, and Le Song, Discriminative embeddings of latent variable models for structured data. In ICML, 2016.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Thomas Finley and Thorsten Joachims. Training structural svms when exact inference is intractable. In ICML, 2008.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In Proceedings of the 36th International Conference on Machine Learning. 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In KDD, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In NeurIPS, 2017.
Xuming He, Richard S Zemel, and Miguel Á Carreira-Perpiñán. Multiscale conditional random fields for image labeling. CVPR, 2004.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Daphne Koller and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.
John Lafferty, Andrew McCallum, and Fernando CN Pereira. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In ICML., 2001.
Guillaume Lample, Miguel Ballesteros, Sandeep Subramanian. Kazuya Kawakami, and Chris Dyer. Neural architectures for named entity recognition. NAACL-HLT, 2016.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In ICCV, 2019.
10

---

Published as a conference paper at ICLR 2022
Liyuan Liu, Jingbo Shang, Xiang Ren, Frank Xu, Huan Gui, Jian Peng, and Jiawei Han. Empower sequence labeling with task-aware neural language model. In AAAI, 2018.
Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph-based semi-supervised learning. In NeurlPS, 2019.
Jiaqi Ma, Bo Chang, Xuefei Zhang, and Qiaozhu Mei. Copulagnn: Towards integrating representa-
tional and correlational roles of graphs graph neural networks. In ICLR, 2021.
Tengfei Ma, Cao Xiao, Junyuan Shang, and Jimeng Sun. Cgnf: Conditional graph neural fields. ICLR Submission, 2018.
Xuezhe Ma and Eduard Hovy. End-to-end sequence labeling via bi-directional lstm-cnns-erf. In ACL, 2016.
Kevin P Murphy, Yair Weiss, and Michael I Jordan. Loopy belief propagation for approximate inference: An empirical study. In UAI, 1999.
Vinod Nair and Geoffrey E Hinton. Rectified linear units improve restricted boltzmann machines. In ICMI,, 2010.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In EMNLP, 2014.
Meng Qu, Yoshua Bengio, and Jian Tang. Gmnn: Graph markov neural networks. JCML, 2019.
Erik F Sang and Fien De Meulder. Introduction to the conll-2003 shared task: named entity recognition. arXiv preprint cs/0306050, 2003.
Sunita Sarawagi and Rahul Gupta. Accurate max-margin training for structured output spaces. In ICML, 2008.
Victor Gareia Satorras and Max Welling. Neural enhanced helief propagation on factor graphs. arXiv preprint, 2020.
Victor Garcia Satorras, Zeynep Akata, and Max Welling. Combining generative and discriminative models for hybrid inference. arXiv preprint, 2019.
Fei Sha and Fernando Pereira. Shallow parsing with conditional random fields. In HLT-NAACL. 2003.
Charles Sutton and Andrew McCallum. An introduction conditional random fields for relational learning. Introduction to statistical relational learning. 2006.
Charles Sutton and Andrew McCallum. Piecewise training for structured prediction. Machine learning, 2009.
Charles Sutton and Andrew McCallum. An Introduction to Conditional Random Fields. Now Publishers Inc, 2012.
Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. Arnetminer: extraction and mining of academic social networks. In KDD, 2008.
Ioannis Tsochantaridis, Thorsten Joachims, Thomas Hofmann, and Yasemin Altun. Large margin methods for structured and interdependent output variables. JMLR, 2005.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Martin J Wainwright and Michael Irwin Jordan. Graphical models, exponential families, and variational inference. Now Publishers Inc, 2008.
Martin Wainwright, Tommi Jaakkola, and Alan Willsky. Tree-reweighted belief propagation algorithms and approximate ml estimation by pseudo-moment matching. In AISTATS, 2003.

---

Published as a conference paper at ICLR 2022
Binghui Wang, Jinyuan Jia, and Neil Zhenqiang Gong. Semi-supervised node classification graphs: Markov random fields vs. graph neural networks. AAAI, 2021.
Yair Weiss and William T Freeman. On the optimality of solutions of the max-product belief- propagation algorithm in arbitrary graphs. IEEE Transactions Information Theory, 2001.
Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In ICML, 2020.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. ICML, 2016.
Jonathan Yedidia, Williim T Freeman, and Yair Weiss. Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Transactions information theory, 2005.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In ICLR, 2020.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li. Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks. ICLR, 2020.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. In JSMB, 2017.
12

---

Published as a conference paper at ICLR 2022
A DERIVATION OF THE MAXIMIN GAME
As discussed in the Sec. 3 optimizing the joint label distribution pa maximize the log-likelihood logpo (yly |xv, E) on training graph (yt, xv, E) is equivalent to solving a maximin game. In this section, we provide the detailed derivation.
Let (yv, xv. E) be the potential function as below:
yv,, E) exp
Σ
Ov E)+
E
Ose(Us: Ve, xv, E)
(14)
SEV
(a.))E
For each training graph Lyv.xy: E), we aim maximizing the following log likelhkee function:
log pogpoly [v,, E) log 1
Zx E) tho (y,, XV, E)
log (y v xv, E) log Zo (xv, E))
(15)
logvo(yyv Xv, E) log Σ woly,, E).
However, the term log Eyv syv Xv. E) is computationally intractable, need all the possible yv. To solve the problem, introduce variational joint distribution g(yv) defined on all node labels yy, and use the Jensen's 's inequality to derive an estimation of the term log Eyv (yv, xv, E') follows:
Volyv, Xv. E) g(vv) tho (ov,,, E)
log Σ Nolyv, E) = log Eg(xv)
yv
(16)
2 Ex(rv)
log
g(yv)
= B y flog tha (yv, xv. E)] - B (ov)(
The equation holds if and only if g(yv) = po F), and hence:
log Σ volyv, E) max
(Egtrv the (yv,xy E)] Excr [ogg(yv))
(17)
glyv)
By taking the above result into Eq. 15
obtain:
log Togpolyvlxe xv, E) log tho (yū xv, E) log Volyv, xv, F)
yv
(18)
min {log Voyg, xv, F) ((xv)
E Byyyy) Dlog (y Xv, E)] + (ogg [(x)))
As Vo(y,, E) exp 0, (Us; xv, F.) + Σ (G.jeE Ost Dt, xv, F)), we have:
logpalyy xv, E) min L(0,
(19)
with:
C(O, g) = -H(a(yv))
+ Σ (0.e
10 + E00.05 Ex, (v())))
(20)
(x.4)E
sEV
Therefore,
optimizing 0 to maximize the log-likelihood function is equivalent to solving the following maximin game:
log xv. E) max min L(e, g).
(21)
13

---

Published as a conference paper at ICLR 2022
B DERIVATION OF THE MOMENT-MATCHING CONDITIONS
In the CRF model defined the preliminary section, the parameter / consists of the output values of all O-functions. In other words, 0 = (0<(ve))wee)teev U ((st ww....e.......... where y is the set of all the possible node labels.
By definition, ( E) belongs to the exponential family. According properties of expo- nential family distributions, log Po xv, E) is strictly concave with respect to Therefore, the optimal 0 unique, which is characterized by the condition of a log logpo(yi/xv,, B) = 0. Formally, log pe ( xv. E) can be computed as below:
00
80
a
log peppyyilxv, E) = 00 log (yi, xv,
log (x(, E).
(22)
00, (ū.)
00
For 30
log Zo (xv, E), we have:
0
log Zo Z0
0
log Σ Vvlyv.XVV.
00
00
yv
Σ yv DA
a
th (VV, XV, E)
Exe Volyv, xv, F))
Eyr volyv, xv, , E)) 2
E))
Eyv vo (yv, Xv,
(23)
volyv, xv, E)
log (o xv, F)
Exi Voly xv,
E) 00
yv
Volyv, xv. F))
Σ
log (VV,, Xv, E)
Zo
Epolyv E))
log the (yv, vy,, Xv,
30
By combining the above two equations, we have:
i
log po (xv, E) a0 log the (yV, Bpa (vvllv, F)
log wolyv, xv. (24)
00
a0
The potential function 2hg above is defined as volyv, xv, E) explE sEv (v,,, xv, E) + Ee (ve Uh, xv, E)) J. If we consider each specific scalar 0g and taking the derivative with respect to the scalar to O, we obtain:
θ
log pe (y Xv. E))
(0,)
θ (0.)
log the (y xv, (y,,v, E)- Epolyvlxy,E)
log (yv, E)
(0,)
Iy: {
(U.) (v))))
E (yr (otv//xv,.. (xv, E))
Iu {Wa) (0. 0.(6s)
0
(25)
Tue {
(0,(0s) 0g (5m))
-oo(is E)
00, (T.) (1.)))
Iy; (0.} }
po ( |)v
which implies pe (0, (xv, E) Iy; {
for the optimal 0. Moreover, this equation holds for all
s E V and all ge E V.
Similarly, for each scalar (Be, (c), have that 0... log (olyi E) 0 is equivalent
to po(Dss Un xv. E) = Iyg (U.: }. This equation holds for (s, E E and the choices of (ge, 9t) y x y. Therefore, the optimal O-functions are characterized by the moment-matching conditions as below: Po (xv, E) Iy; {yo} Vs V. po(ve: v1 (x, E) Hoz (v. V(s E E. (26)
14

---

Published as a conference paper at ICLR 2022
C PROOF OF PROPOSITION
Next, we prove Prop. We first restate the proposition follows:
Proposition Consider a set of nonzero pseudomarginals (va( sev and (Ta Be MAO)EE which satisfy Ey, TVs V1) = Tx (B)) and my, Too = (V=) for all (s.t) E. If we parameterize the 0-functions of pa in Eq. (2) in the following way:
Tst (Ms Me) V(s,))
O2(ys) (V6))( As V
Ost yc) log
(27)
(=(U))TT(UE)
then (T, (vs and (Tec ()) are specified by a fixed point of the sun-product loopy belief propagation algorithm when applied to the joint distribution pa, which implies that:
Ty.) = po(ys) Ys E V, (yc 36) pe (sst) t) E.
(28)
Proof: To prove the proposition, we first summarize the workflow of the sum-product loopy belief propagation algorithm. sum-product loopy belief propagation, we introduce a message function
(y++(()) for each edge ts E
E. Then iteratively update all message functions follows:
mp-1((ss) x Σ exp(0.(8)) + +0e(Nss
II S'E(()A
(29)
where (t)) represents the set of neighbors for node t.
Once the process converges after sufficient iterations, the approximation of the node marginals and the edge marginals (i.e., (y=))))see and ( can be recovered by the message (..)
functions {m-=s ( as follows:
2. (1a)) x (x.((.(y)))
II NEN(s)
my myss((aa).
(30)
ast (ye M1) x (x.(O.(w.) + (v6) + Ose (V.,
II
(v+)(())
II my-((V)). (31)
(EN())
('EN()))
case, where parameterize the O-functions with set of pseudo- marginals as in Eq. (27p. For such a specific parameterization of the f-ffnctions, we claim that one fixed point of Eq. (29 achieved when m--+a (v.) for all (s. t) E. To prove that, notice that when all the message functions equal to I, the left side of Eq. (29 is apparently 1. The right side
Next, let move back
of Eq. (29) be computed as below:
Σ
exp(Ox(w:) + Ost
II
my (y+((()
Vi
SEN(())
Σ
exp(O:(u:) + -0e( v())
Tat (No Mr) (Nos
Σ
log To)e)())) + log
exp
Tx (Te
y/
Σ exp
log
Tse Tur
(32)
Ta (Ua))
Tat (ys:
Ta (Vs)
Vi
To (Va)
(v.)
We can see that both the left side and the right side of Eq. 29 are 1, and hence {m++s=(ss
1 (s.t)) specifies fixed point of sum- num-product loopy belief propagation. For this fixed point, qa (va) can be computed as follows:
gx(y)) exp(O.(v.))
II m4-s( = exp(0. =v(( (EN(s)
(33)
15

---

Published as a conference paper at ICLR 2022
Similarly, compute qsi (Vss ve)
(sc(Ve:V)) x exp(O,(u)) + (vr) + oz (ys 3c))
II
(Vs)
II ('E(())s
myr
MEN(s))
exp(O, + (.())) + (vc ve))
(34)
Tat (ut 310)
log (v..) + log (v:) log exp
(y))))t
From the above two equations, we can see that (T, (Ms)) hev and (Te ((.A)) are specified by fixed point (i.e., (y. 1 for all (s,t) E) of sum-product loopy belief propagation As sum-product loopy belief propagation often works well in practice to approximate the marginal distributions on nodes and edges, thus have T, (y,) Po for each node and Tu 9c) po (V.. Vt) for each edge.
D SOLVING THE PROXY PROBLEM WITH CONSTRAINED OPTIMIZATION
The key innovation of our proposed approach is on the proxy optimization problem which is used to approximate the original learning problem. Formally, the proxy optimization problem is stated as:
min 7,8
Σ .EV
(I: T + Σ d (1(2 w2) (1 9))) Tat (U. 11))
(u.))
(s,))E
(yo Me) Ozr (Vo+ = log To T.
subject to
0g log TlogT,((1)) (Ua);
(35)
and Σ Tar(Ms, Tr(().
Σ (u Mr) = Ts (ya),
nodes and edges, where can be any divergence measure between two distributions.
In our implementation, we ignore these consistency constraints, i.e., Eg. Tsr vt) Tx (vs) and Ey Tat (Ws, Me) = (Ms). This ie because by by optimizing the objective, the obtained pseudo- marginals would well approximate the observed node and edge marginals, i.e., Ta (ys) R y {y.) and Tax (V.. Me) z T(x;:05) ((v,, }r and hence т would almost naturally satisfy the constraints.
To demonstrate ignoring the consistency constraint makes sense, also tried constrained opti- mization method for solving the proxy problem. Specifically, we add a quadratic term to penalize the inconsistency between Tee (Mo: Vv)) and Ta (ya) as well as 7 (w:), resulting in the following problem:
min Σ d (Iu: (Va) + sEV
Σ (e,t)EE
v.). d (H(w:.wr) ((), Ted (ec Vs))
t Σ
Tat (Ve, vi) Te (1:))) + > Tul vc) - To(ua))
(36)
(s,0)E
Bt
Tst (Uss Mt)
subject to 0, = log Tu (ya).
(ze v1) = log
To (v))
for nodes and edges. Again, d is a divergence measure between two distributions, and we choose to use the KL divergence. is hyperparameter deciding the weight of the penalty term.
Table 7: Analysis of constrained optimization methods for solving the proxy problem.
Algorithm
Constrained Optimization who
Corn
Citeseer*
Pubmed
49.10 3.80
42.89
1.30
47.79 1.33
SPN-GAT
with
48.83 + 3.51
42.04
1.23
47.55
1.24
We conduct empirical comparison this constrained optimization method and our default implemen- tation where the consistency constraint is ignored. The results presented in Tab. 7 We can see that the constrained optimization method does not lead to improvement, which shows that ignoring the consistency constraint empirically reasonable.
16

---

Published as a conference paper at ICLR 2022
E UNDERSTANDING SPNs AS OPTIMIZING SURROGATE FOR THE LOG-LIKELIHOOD FUNCTION
In the model section, motivate SPNs from the moment-matching conditions of the optimal 0- functions. Specifically, we initialize the O-functions at a state where the moment-matching conditions approximately satisfied, yielding near-optimal joint distribution. Then we further tune the O-functions to solve the maximin game, Besides this perspective, SPNs can also be understood as optimizing a surrogate for the log- log-likel function. Next, we introduce the details.
Remember that maximizing the log-likelihood function is equivalent to solving a maximin game as: max log po (y xv; E) max min L(0,g), with [(0, --([(yvv]
9
(0.(vC) - g.. (v+))) 10. + Σ (a,))E
(Osc(VG vi) 10 Bcl1}.
(37)
.EV
Here, v(vv) is a joint distribution all the node labels. q, (ys) and qec ye) are the corresponding
marginal distributions.
Although the above maximin game is equivalent to the original problem of maximizing likelihood, solving the maximin game is nontrivial. In particular, there are two key challenges, i.e., (1) how to specify constraints to characterize valid joint distribution q(yv) and (2) how compute its entropy (q) = - Egyyv) flog gyyv).. To deal with the challenge, a common practice used loopy belief propagation to make the following two approximations:
(1) Instead of specifying constraints to let g(yv) be a valid joint distribution, we introduce a set of valid joint distribution. Specifically, these pseudomarginals are denoted as q {gs (V-)) U {gat (ye, (G.))) and they satisfy Ey, qar (ye Ut) q (3)) and Me 9st (ys: M/)) = q, (ys) for all (s, E E.
pseudomarginals approximation
(2) We approximate the entropy H (g) with Bethe entropy approximation B (ÿ), which is defined as follows:
log qae (Ns Mr) ( ) (3t)
H Bethe (7)
(lgg
Σ
(38)
sEV
(s,))E
With the two approximations, we get the following maximin game as surrogate for the likelihood maximization problem:
max po Xv, E) so max min LBene (0, 9).
(39)
0
with:
Betth (f.g) = - -Beehh (ÿ)
Σ (V v7) (. ve)) + E(0.())) Eg, (v. 10. (v.))).
(40)
(a.))E
This problem known as the Bethe variational problem (BVP) (Wainwright & Jordan 2008).
Such a problem can be solved by coordinate descent, where alternate between updating q to minimize LBehe (0, () and updating 0 to maximize Lfeth q). According to Yedidia et al. (2005). updating minimize LBehhe (6, 9) can be exactly achieved by running sum-product loopy belief propagation on Pa. where fixed point of the belief propagation algorithm yields a local optima ğ. On the other hand, updating 0 to maximize LReth (0, q) can be easily achieved by gradient ascent.
In addition to that, stationary point (0*, ,7") of the above BVP is specified by following conditions:
eneshe (0", (²))
L (0" . 0.
(41)
Oig*
00"
According to Yedidia et al. (2055) and Wainwright & Jordan 2008 the first condition is equivalent
to the condition that 9² specified by fixed-point of sum- com--prouct loopy belief propagation. The second condition states that the moment-matchie conditions are satisfied, i.c. q. (v.) = I,; {v.} on
each node and gse (y. y1) T(x wi)
w)) <e(((ye (t)) on each edge.
17

---

Published as a conference paper at ICLR 2022
For our proposed approach SPN, it can be viewed as solving the BVP as defined in Eq. (39 Through solving the proxy problem, SPN initializes 0 at a state where the conditions of stationary points in Eq. (41) approximately satisfied. Then the fine-tuning stage of SPN further adjusts 0 to solve the maximin game by alternatively updating 0 and 7j
More specifically, when solving the proxy optimization problem, by initializing in the way defined by Eq. (27, the collection pseudomarginal distributions (v.) lev and (Tar yt (a.c) is specified by a fixed point of sum-product loopy belief propagation according Prop. [ This implies 3i Beahee (), 0 for q = (T=))))<E) U {Tee yt. J). Meanwhile, as fev and (Tat)s are learned match the true labels y on each training graph, we thus have (y)) Re T, {y.} } on each node and Tax (Be. V/) = [(y wz > ( }b)] on each edge. Therefore, the conditions in Eq. (41) are approximately satisfied by (0, 7) with q {Tx (v.))
that 2
(Ts Ut.) Vt)) (e.()EE which means that solving the proxy problem yields 0 to roughly match the conditions of stationary points for the BVP in Eq. (39). Afterwards, the refinement stage of SPN is exactly trying to solve the maximin game of BVP in Eq. (39). where we alternate between updating ④ to minimize CBtte (0, 4) via sum uum-product loopy belief propagation and updating 0 to maximize (B, (0, q) via gradient ascent.
As result, we see that the SPN can also be understood as solving the Bethe variational problem in Eq. 39 which acts surrogate for the lideliidd function.
F EXPERIMENTAL DETAILS
Next, we describe our experimental setup in more details.
F.1 DATASETS
The statistics the datasets used in our experiment are summarized Tab. For the Cora*, Citeseer*, Pubmed" and PPI datasets, they are under the MIT license.
Table 8: Dataset statistics. ML and MC stand for multi-label classification and multi-class classifica- tion respectively.
Dutuset
Tusk
# Features
e Labels
Cimphs
Avg. # Nidds
Training Graphs
Avg. e Edges
# Grappts
Validition Grapli
Avg. # Nodes
Arg # Edges
# Graphs
Test Gruphs Avg. Noces
Avg. e lidges
PP1
MIL
30
121
20
2515,3
61315.4
2
1357
2752
Cons
MC
1433
140
5.6
7.0
500
4.9
5.8
1000
4.7
5.1
Gleacer
MC
3703
120
4.0
4.3
500
3.5
4.0
1000
3.8
3.8
Pabensa
MC
500
60
6.0
6.7
500
5.4
5.8
1000
5.6
DULP
MC
100
6483
10082
14142
48631
20813
159099
For the DBLP dataset, it is constructed from the citation network in Tang al. (2008). Scientific papers from eight conferences are treated as nodes, which are divided into three categories based conference domains for classification. For each paper, compute the mean Glo Ve embed- ding 6 (Pennington et al. 2014) of words in the title and abstract as features. We split the dataset into three disjoint graphs for training/validation/ess The training graph contains papers published before 1999 (with 1999 included). The validation graph contains papers published between 2000 and 2009 (with 2000 and 2009 included). The test graph contains papers published after 2010 (with 2010 included). There exists an undirected edge between two papers if one cites the other one. Cross-split edges (e.g., an edge between a paper in the training set and paper in the validation set) are removed.
For the PPI datasets, there are 121 binary labels, and we treat each binary label as an independent task. For each compared algorithm, we train a separate model for each task, and report the overall results across all tasks.
F.2 ARCHITECTURE CHOICES
To facilitate reproducibility, we use the GNN module implementations of Py PyTorch Geometric (Fey & Lenssen 2019). and follow the GNN models provided in the examples of the repository unless
ML. M.C.CN//AAAIISSSCCCCCCC//CCCCCCC v12.
httpps//orriginalstttt... htw.://al.aaaattaaaaame..aaaaaaa
18

---

Published as a conference paper at ICLR 2022
otherwise mentioned. Note that most architecture choices not optimal on the benchmark datasets, but we did not tune them since we only aim to show that our method brings consistent and significant improvement.
GCN (Kipf' & Welling, 2017). We set the number of hidden neurons to 16, and the number of layers 2. ReLU (Nair & Hinton 2010) is used the activation function. We do not dropout between GNN layers.
GraphSage (Hamilton et al., 2017). We the number of hidden neurons 64, and the number of layers to 2. ReLU (Nair & Hinton 2010) is used as the activation function. We do not dropout between GNN layers.
GAT (Veličković et al. 2018). We set the number of hidden neurons to 256 per attention head, and the number of layers to 3. The number of heads for each layer set to 4, 4 and 6. ELU (Clevert et al. 2016 is used as the activation function. We do not dropout between GNN layers.
Graph U-Net (Gao & Ji. 2019). We set the number of hidden neurons to 64 and the number of layers to We randomly dropout 20% of the edges from the adjacency matrix. We do not dropout node features or between layers.
set the number of hidden neurons to 2048 for citation datasets (Cora*, Citeseer*, 7 and DBLP) and 256 for the PPI dataset. We set the number of layers to 9. ReLU (Nar Hinton 2010) is used as the activation function. For PPI, layer normalization (Ba et al. 2016) applied between the GCNII layers. We do not dropout between GNN layers. We set the strength a of the initial residual connection to 0.5, and the hyperparameter to compute the strength of the identity mapping to 1.
GCNII (Chen et al. 2020a).
The function. In Eq. of the model section, we define as a function mapping pair of L- dimensional representations (1D) (2/)) dimmensiioo logit. Two variants of this function are used in our experiment. For the PPI and DBLP dataset, we use the linear variant, where the pair of node representations are concatenated and plugged into linear layer:
Ilineur (V., Vo) = W(v,: Vi] b,
(42)
where W E I ( x is the weight matrix and b E R x(X is the bias. For the citation datasets (Cora*, Citeseer*, Pubmed*),, we use the bilienar variant, where the pair of node representations are plugged in bilinear mapping:
Ibllinear (V.. vo) = (Wv.)
(43)
where W& E D is a weight matrix.
SPN with a shared GNN. By default, the SPN uses a node GNN and an edge GNN to approximate the pscudomarginals shared GNN for both pscudomarginals on nodes and edges. other words, u, = =., Vs E V (sce Eq. and Eq. (8) ) All the other components are the same the default SPN. The results of this variant are shown in Tab. of of the experiment section.
nodes and edges respectively. In the experiment, also consider using
F.3 HYPERPARAMETER CHOICES
GNNs and SPNs. For node classification, the learning rate of the node GNN Tg in GNNs and SPNs is presented in Tab. 9 For edge classification, the learning rate of the edge GNN Tat is presented in Tab. T0 For the temperature y used in the edge GNN Tat of SPNs, we report its values Tab.
CRF-linear. For CRF-linear training, we set the learning rate to 5 10-1
CRF-GNNs and SPN. For CRF and the refinement stage of SPN, we set learning rates to x 10-5
GMNN. For GMNN training, we the learning to 5 10-3
19

---

Published as a conference paper at ICLR 2022
Table 9: Learning rate of the node GNN Ta.
Algorithm
PPT
Cora
Citeser*
Pubmed
DBLP
GCN
GraphSage
5 10-3
5xx 10-
5x 10-
5x 10
5 10-a
GAT
1x
10
10-3
Graph U-Net
5 10
1x 10
1x 10
1x 10
GCNI
1x
1x10
1x
1x100
Table 10: Learning rate the edge GNN Tst-
Algorithm
PPI
Cora
Citeseer*
Pubmed
DBLP
GCN
x 10-3
5 10
1 10
x 10-3
GraphSage
10-3
1x 10-
1x 10-3
10-3
1x 10-3
GAT
1 10-3
1x 10
5 10"!
5x 10
5 10
Graph U-Net
1X000
10
1x100-2
GCNH
1 10
5x 10
1x
x
1 10
Table 11: Temperature of the edge GNN Tat-
Algorithm
PPI
Cora
Citeser
Pubmed
DELP
GCN
10
0.2
2
2
GraphSage
GAT
0.2
0.2
0.2
Graph U-Net
0.2
GCNII
0.5
0.5
0.5
2
F.4 COMPUTATIONAL RESOURCES
We run the experiment by using NVIDIA Tesla V100 GPUs with 16GB memory.
G ADDITIONAL RESULTS
In this section, we present some additional experimental results.
G.1 ADDITIONAL ANALYSIS OF GNN ARCIITECTURES
In this analysis, we study the effect of node/edge GNN architectures on SPNs. We fix one of the GNNs and change the capacity the other (Fig. 4 then evaluate SPN-GAT on PPI-1-0, subset of PPI-1 that only contains its first label. The results show that our model benefit from capacity gain in both node and edge GNNs, highlighting their effective synergy. This also explains the underperformance of SPN-GCN in Tab. where the edge GCN backbone with only two layers and 16 hidden neurons incapable of modeling the edge label dependencies and thus drags the performance behind. We also find that the node and edge GNNs need not share the same backbone, and in many cases SPNs with different node and edge GNNs perform superior to those with same backbone (Fig. 4. The expressiveness of edge GNNs is crucial to the performance of SPN. Though did not optimize the design of our edge GNNs, they have shown to be helpful in boosting the performance once plugged into approach.
Heads the Node GNN
-270
Node: NN Avchoccurr
AMA
-0.55
6700
-1.90
-0700
GAT
Edge
Edge
Figure 4: Left: effect of #heads in SPN-GAT, Right: effect of backbones in SPN,
20

---

Published as a conference paper at ICLR 2022
G.2 NODE-LEVEL ACCURACY ON CORA* CITESEER*, AND PUBMED*
In the experiment, we report the graph-level accuracy on the Cora*, Citeseer*, and Pubmed datasets, where SPNs consistently outperform other methods. Besides the graph-level accuracy, we also compute the node-level accuracy on these datasets, and the results are reported in Tab. T2 We can see that our approach still consistently outperforms other methods in terms of node-Ievel accuracy.
Table 12: Node-level accuracy on Cora*, Citeseer* Pubmed (in %).
Algorithm
Cora
Citeseer
Fubmed
GCN
79.85 + 0.24
72.25 = 0.71
78.05 0.35
GraphSAGE
73.43 1 1.67
62.48
2.19
73.99 1.26
GAT
79.65 1.25
74.15
0.12
78.62
0.52
Graph U-Net
0.63
71.36 1.37
77.93
GCNII
0.37
72.61 0.49
79.47 0.55
CRF-linear
68.47
65.88
0.88
65.93 1.93+2118
CRF-GAT
+.22
69.13 1.10
75.96 + 1.06
CRF-UNct
1.53
70.78 + 1.15
77.91 - 0.56
CRF-GCNII
35.98 7.40
33.73 + 5.87
60.55 4.17
GMNN
+
72.18 0.48
78.00
SPN-GAT
8..43
74.50 0.36
79.23 0.33
SPN-UNel
72.28 1. 0.94
78.70 1 0.37
SPN-GCNII
83.54 1: 0.27
74.04 1: 0.29
79.95 0.38
G.3 COMPARISON OF SUM-PRODUCT AND MAX-PRODUCT BELIEF PROPAGATION
As explained in section 4.2 the sum-product belief propagation algorithm more applicable to the case of node-level accuracy, as it aims at inferring the marginal label distribution on each node. Nevertheless, in practice we find that the max-product algorithm usually achieves better empirical node-level accuracy. For example, the results on the PPI-1 dataset are presented in Tab. 13
Table 13: Micro-F1 on PPI-10 (in %).
Algorithm
Micro-F1
Sum-product BP
94.50 0.16
Max-product BP
94.65 0.13
Because of the better empirical results, we choose use max- max-product belief propagation by default.
G.4 HYPERPARAMETER ANALYSIS
Finally, We present analysis of the hyperparameter (i.e., edge temperature) in Fig.
Test Acuuueuuuee
Text Accurscy
0.35
0.5
5.55
3.0
(a) Edge lemperature on Cora.
(b) Edge temperature on DBLP.
Figure 5: Hyperparameter analysis.
21


Reviews:
[{"review_id": "ujUhff1I-iv", "reviewer": "Reviewer_LsFg", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update following revision / author comments:\n\nThanks for clarifying and providing details on how the method compares to piecewise training. Having all of those details in the final paper would make it much stronger, and so I have raised my score. \n\nFor what it's worth, I'd suggest trying to describe the method in as general terms as possible so that people working on other structured prediction problems are more likely to learn about it and use it. The method is general and appears very promising, but currently the paper is very much written for graph problems, so I fear that researchers outside of the graph community may overlook it. Choosing a more specific name for the method could also help. The name \"Structured Markov Network\" is a bit too broad, as it just sounds like a Markov Network, which is a synonym for MRF. Maybe working \"proxy\" into the name you choose would be helpful.\n\nOriginal review follows:\n\nStrengths:\n\nThe methods are well-chosen for the task. The method is simple enough that other researchers may use it.\n\nThe empirical results are solid and interesting. \n\nThe paper is well-written. \n\nWeaknesses:\n\nThe original piecewise training paper (Sutton & McCallum, 2009) is cited, but is not discussed in any detail. No connection is made between the proxy problem and piecewise training. I think a connection should be made and discussed, especially because the experiments do not involve actually solving the proxy problem but rather omit the marginal consistency constraint (\"The last consistency constraint...can be ignored during optimization\"... \"We also tried some constrained\noptimization methods to handle the consistency constraint, but they yield no improvement\"). When refinement is not used (it is omitted in the main experiments since it doesn't consistently help) and when KL divergence is used for the divergence measure (as it is in the experiments), the actual training objective becomes even more similar to piecewise training. Piecewise training is fairly well-known in other communities like the vision community, e.g., Lin et al. (2016), so I think it's really important for this paper to draw a connection to piecewise training. I would suggest including piecewise training as a baseline to compare to, but I think that the SMN (without the marginal consistency constraint, without refinement, and when using KL) actually corresponds to a natural way to apply piecewise training to this problem. \n\nAfter reading the paper, I was confused by one part of the results: Why would SMN outperform CRF? That may suggest that the approximations made during learning are beneficial, which deserves follow-up investigation. A related question is: why is refinement not helpful? The CRF-G* settings correspond to using the same models as the corresponding SMN-G* settings, but the former seek to directly solve the maximin game using loopy BP for inference during learning (I believe), rather than use the proxy problem. The SMN results are consistently better than the corresponding CRF ones. Why is the proxy problem superior? Perhaps the CRF objective is not as good for learning as the proxy problem? The proxy problem can be viewed as using \"local supervision\" on specific nodes and edges, which may be more learnable from supervised datasets than the traditional CRF objective which is log loss on labelings of entire graphs. Or maybe it's due to training stability: An SMN that solely solves the maximin game (is this the same as the CRF-G* models?) is described as being unstable in Sec 5.5, #5. Can you provide more details about that? Is the instability due to the use of loopy BP as the inference algorithm? How about if you pretrain the GNNs for the potentials with maximum likelihood?\n\n\n\nSome more specific suggestions are below:\n\nSpell out SMN (\"Structured Markov Network\") the first time it appears in Sec 1. I would actually also suggest changing the terminology to something more specific. \"Structured Markov Network\" is a pretty generic term that would evoke several kinds of existing graphical models in people's minds. E.g., some people use the term \"Markov Network\" to refer to undirected graphical models in general, and so the addition of the term \"structured\" does not really add anything since graphical models are already \"structured\". \n\nThe definition of GNNs in 3.2 seems unnecessarily limited. A graph neural network does not have to produce distributions over anything -- it could simply represent a graph via autoencoder training with an L2 loss, for example. Please see surveys on GNNs, such as Zhou et al. (2021), which provide a richer characterization of GNNs. If you wish to define GNN in a more constrained way for purposes of this paper, then please add \"In the context of this paper, we define a GNN to be\".\n\nSec. 3.2: \"However, GNNs approximate only the marginal label distributions of nodes on training graphs, which may generalize badly and result in poor approximation of node marginal label distributions on test graphs.\" -- Why might they generalize badly? Would an estimate of the full label distribution be expected to generalize better? Is the paper implying here that noisy estimates of the marginals would generalize better than a noisy estimate of the joint?\n\nSec. 3.3: \"Conditional random fields (CRFs) build graphical models for node classification.\" CRFs are much broader than node classification. See my comment about GNNs above. \n\nSec. 3.3: \"intractable partition function\" -- The intractability depends on the graph, right? E.g., consider chains, trees, acyclic graphs..\n\nSec. 4.1: \"compute the a representation\"\n\nMore details are needed about the DBLP dataset. What exactly is the structure of the \"citation graphs\" mentioned? Also, it appears that there is only a single graph in train, validation, and test -- is that correct? The test set contains papers from \"after 2010\" -- does that include 2010 or is it only from 2011 onward? Are the train/val/test graphs disjoint? The papers in the test set will mostly be citing papers from the training and validation sets, or are the latter removed from the test graph to avoid overlapping nodes among splits?\n\nReferences:\n\nGuosheng Lin, Chunhua Shen, Anton van dan Hengel, Ian Reid. Efficient piecewise training of deep structured models for semantic segmentation. CVPR 2016.\n\nJie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, Maosong Sun. Graph Neural Networks: A Review of Methods and Applications. 2021.\n\n", "summary_of_the_paper": "This paper proposes a CRF for classifying nodes in graphs where the CRF has a potential for each node and edge in the graph. GNNs are used for computing the potentials, one GNN for node potentials and one GNN for edge potentials. For general graphs, computing the partition function is intractable, so approximations are used during both learning and inference.  Learning draws from prior work and combines learning pseudomarginals of nodes and edges with GNNs and optionally some steps of \"refinement\" by optimizing a maximin game equivalent to likelihood maximization. Inference uses sum-product or max-product loopy BP (they perform similarly, though max-product is slightly better). The procedure is called a \"Structured Markov Network\" (SMN). Experimental results on several graph node classification tasks show that SMNs outperform several baselines, including both CRFs with standard training (using approximate inference during training) and CRFs trained with pseudolikelihood. \n", "summary_of_the_review": "While the paper is well-written and the results show consistent improvements, the paper is lacking in terms of any connection made to piecewise training (which the best version of the SMN essentially boils down to, as far as I can tell) and an analysis of why optimizing the proxy problem is superior to the original learning problem. These are potentially fixable issues. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eUJdecnU-NE", "reviewer": "Reviewer_jqoo", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The motivation of model design is clear and reasonable. Modeling label dependencies is a natural way to improve GNNs, which is also supported by experiments.\n- The model inherits advantages of CRF, such as describing the dependency of node labels and providing probabilistic interpretation. In the meantime, the model supports efficient learning and inference.\n- The model is technically sound.\n- Experiments cover several benchmarks. The model is tested on multiple datasets and shows very promising results.\n- The paper is well-written and easy to follow.\n\nWeaknesses\n- The model is proposed for modeling discrete node labels on a graph. It is unclear how to extend the model to fit continuous node labels.\n- Insufficient baselines for comparison. For neural models that can describe node label dependencies, the paper compares with GMNN only. However, there are various recent works that are not compared, e.g., $G^3NN$ (Ma et al., 2019), CopulaGNN (Ma et al., 2021), LCM (Wang et al., 2021) to cite a few.", "summary_of_the_paper": "The paper aims to break the label independence assumption in existing GNNs. To this end, a combination of GNNs and CRF is proposed, named SMN. SMN improves GNNs by modeling the joint distribution among discrete node labels; SMN is a promising alternative to CRF as it provides efficient learning and inference procedures. Empirically, SMN achieves better node-level and graph-level prediction accuracies than several existing models, with minor additional runtime overhead.", "summary_of_the_review": "I think the model is reasonable both theoretically and empirically (though some recent baselines are not included for comparison). Overall, the merits outweigh the flaws, and I believe the paper is a good addition to the existing literature.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "TsbJKpTpbAI", "reviewer": "Reviewer_DQ8r", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n* Paper is well written\n* The proposed method is a novel contribution that combines ideas from CRFs and GNNs.\n\nWeaknesses\n* I consider the experiment section to be a minor weakness. I understand that the method sits in between CRFs and GNNs, but it would be great to compare against methods beyond those from CRFs and GNNs, e.g., SSVMs and others.\n* Another minor weakness. The technical contribution is limited as it builds on old ideas from graphical models. My understanding is that the key to efficiency relies on solving the proxy problem, which, as the authors stated, is an idea that dates back to at least the early 2000s in the context of graphical models.\n ", "summary_of_the_paper": "Authors study the problem of node labeling in the inductive case, i.e., at test time the goal is to label all the nodes of a given graph.\nFor that problem, several variants of GNNs and CRFs have been proposed in the past, and the authors propose a Structural Markov Network that uses GNNs to model the potential functions of a CRF with the subtle difference that a proxy optimization problem is solved to make learning more efficient. Experiments are provided to demonstrate the applicability of their method.\n", "summary_of_the_review": "In my opinion, the paper contains good contributions that are worth publishing at ICLR. While I think the experiments section could benefit from additional comparisons, the current state of the empirical evaluation is reasonable. A score of 7 would reflect better my evaluation of this work as I find the technical contributions to be okay but somewhat limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GZAlk8S7Dhv", "reviewer": "Reviewer_RSMV", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The technical approach exploits, in an innovative way, an insight from graphical models on the relation between pseudomarginals and the joint distribution stated in the main reference (Wainwright and Jordan 2009), to devise a formulation of a a surrogate training objective (the proxy problem) which turns out to be relatively easy to solve, leading to high predictive performance. The problem under consideration is important, and current solutions have the limitations pointed out in the paper (limited expressive capacity of CRF vs only marginal node classification for GNN models).\n\nThe paper reads very well, and hardly has any errors or inconsistencies. Information is provided at the right point, is complete and accurate. The split between main paper and supplementary material is good. The narrative and exposition flow well. \n\nThe model and algorithm descriptions are excellent. \n\nBaselines are strong, relevant, discussed well and evaluated fairly. The experimental methodology is appropriate, well implemented, described well. A large number of analytic experiments complete the main findings. The two evaluation metrics (node and graph-level accuracy) are adequate and it is an advantage that the proposed method can optimize for either at inference time. Experimental reporting is very good, with error bars. Experimental setups are presented accurately and consistently, at an adequate level of detail. The datasets are standard and easy to access, which contributes to reproducibility.\n(NB fig3 is missing a complete caption; colour coding is not explained; as a result sec5.5.7 doesn’t prove its point)", "summary_of_the_paper": "The paper targets the task of graph node classification in the inductive setting, taking an input node and edge feature representations, and inferring a categorical label for each node. It focuses on the case where it is not sufficient to classify a node independently of its neighbours, but where information stemming from predictions for neighbouring nodes needs to be taken into account. \nIt improves over the current approaches by offering a performant and efficient method to combine advantages of CRFs (joint inference) with the representational power afforded by GNNs, while overcoming the computational challenges. In particular, this paper improves on the closest attempts at combining CRF and GNN, Ma+ 2018 and Qu+ 2019, which use pseudolikelihood; Qu+ 2019 is used as baseline in experiments (“GMNN”), while pseudoloikelihood as training objective is investigated in sec5.5.5.\n\n--- update after rebuttals\nI have read other reviews and the authors' replies, as well as extra experiments. I am maintaining my score.", "summary_of_the_review": "If the scoring existed, I would give this paper a 9/10. Having to choose between 8 and 10, I have decided to go for 10, as I consider the paper to be much better than just \"good\".\nThe paper is very good under all aspects. Its contribution is clear, and the problem under consideration is real. One might argue that the innovation is slim because it consists of a single technical contribution; for this reason this might not be a game-changing paper, but it certainly improves on the state of the art by solving a tricky problem. The paper also has the merit of establishing a bridge between neural and graphical model techniques, thus encouraging further work which I expect to be fruitful.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the existing GNN based methods model the node labels independently and ignore the joint dependency of node labels. The CRF-based methods work in this setting, but they are hard to learn. Hence, this paper proposes to ease the learning difficulty by solving the proxy problem and simplifying the max-min problem.

The SMN model proposed in this work is much cheaper than the CRF method. For parameters, since the node GNN and edge GNN share parameters in layers, only a few amounts extra parameters are introduced. As for the training time, it just doubles the general GNNs. Compared with CRF methods, the cost saved by SMN is significant.

Empirically, SMN works well in most settings, in terms of both node-level accuracy and graph-level accuracy, the different backbones, and different datasets. Meanwhile, the authors provide results to show the effect of refinement, the shared GNNs, the different learning methods, convergence, and a tiny case study. The experimental results are significant and well organized.

After the rebuttal and discussion, all reviewers are in a favor of accepting this submission.
Decision: Accept (Oral)