Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: 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.
For 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.

main_review: Strengths
* Paper is well written
* The proposed method is a novel contribution that combines ideas from CRFs and GNNs.

Weaknesses
* 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.
* 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.
 
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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 

main_review: Update following revision / author comments:

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

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

Original review follows:

Strengths:

The methods are well-chosen for the task. The method is simple enough that other researchers may use it.

The empirical results are solid and interesting. 

The paper is well-written. 

Weaknesses:

The 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
optimization 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. 

After 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?



Some more specific suggestions are below:

Spell 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". 

The 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".

Sec. 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?

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

Sec. 3.3: "intractable partition function" -- The intractability depends on the graph, right? E.g., consider chains, trees, acyclic graphs..

Sec. 4.1: "compute the a representation"

More 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?

References:

Guosheng Lin, Chunhua Shen, Anton van dan Hengel, Ian Reid. Efficient piecewise training of deep structured models for semantic segmentation. CVPR 2016.

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


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.
review_title: null

final_score: rating: 10: strong accept, should be highlighted at the conference
review_content: 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. 
It 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.

--- update after rebuttals
I have read other reviews and the authors' replies, as well as extra experiments. I am maintaining my score.
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).

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

The model and algorithm descriptions are excellent. 

Baselines 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.
(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_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".
The 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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Strengths
- 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.
- 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.
- The model is technically sound.
- Experiments cover several benchmarks. The model is tested on multiple datasets and shows very promising results.
- The paper is well-written and easy to follow.

Weaknesses
- 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.
- 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_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.
review_title: null

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)