Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: The paper proposes to use graph neural networks (GNN) for inference in MLN. The main motivation seems to be that inference in traditional MLN is computationally inefficient. The paper is cryptic about precisely why this is the case. There is some allusion in the introduction as to grounding being exponential in the number of entities and the exponent being related to the number of variables in the clauses of the MLN but this should be more clearly stated (e.g., does inference being exponential in the number of entities hold for lifted BP?). In an effort to speed up inference, the authors propose to use GNN instead. Since GNN expressivity is limited, the authors propose to use entity specific embeddings to increase expressivity. The final ingredient is a mean-field approximation that helps break up the likelihood expression. Experiments are conducted on standard MLN benchmarks (UW-CSE, Kinship, Cora) and link prediction tasks. ExpressGNN achieves a 5-10X speedup compared to HL-MRF. On Cora HL-MRF seems to have run out of memory. On link prediction tasks, ExpressGNN seems to achieve better accuracy but this result is a bit difficult to appreciate since the ExpressGNN can't learn rules and the authors used NeuralLP to learn the rules followed by using ExpressGNN to learn parameters and inference.

Here are the various reasons that prevent me from rating the paper favorably:

- MLNs were proposed in 2006. Statistical relational learning is even older. This is not a paper where the related work section should be delegated to the appendix. The reader will want to know the state of inference and its computational complexity right at the very beginning. Otherwise, its very difficult to read the paper and appreciate the results.

- Recently, a number of papers have been tried to quantify the expressive power of GNNs. MLN is fairly general, being able to incorporate any clause in first-order logic. Does the combination with GNN result in any loss of expressivity? This question deserves an answer. If so, then the speedup isn't free and ExpressGNN would be a special case of MLN, albeit with the advantage of fast inference.

- Why doesn't the paper provide clear inference time complexities to help the reader appreciate the results? At the very least, the paper should provide clear time complexities for each of the baselines.

- There are cheaper incarnations of MLN that the authors should compare against (or provide clear reasons as to why this is not needed). Please see BoostSRL (Khot, T.; Natarajan, S.; Kersting, K.; and Shavlik, J. 2011. Learning Markov logic networks via functional gradient boosting. In ICDM)
review_title: Official Blind Review #3

final_score: rating: 3: Weak Reject
review_content: This paper proposes a framework for solving the probabilistic logic reasoning problem by integrating Markov neural networks and graph neural networks to combine their individual features into a more expressive and scalable framework. Graph neural networks are used for learning representations for Knowledge graphs and are quite scalable when it comes to probabilistic inference. But no prior rules can be incorporated and it requires significant amount of examples per target in order to converge. On the other hand, MLN are quite powerful for logical reasoning and dealing with noisy data but its inference process is computationally intensive and does not scale. Combining these two frameworks seem to result in a powerful framework which generalizes well to new knowledge graphs, does inference and is able to scale to large entities. 

Regarding its contribution, the paper seems to consider a training process which is done using the variational EM algorithm. The variational EM is used to optimize the ELBO term (motivation for this is the intractability of the computing the partition term). In the E-step, they infer the posterior distribution and in the M-step they learn the weights. The integration of variational EM algorithm and MLN has been explored in another work (pLogicNet: Probabilistic Logic Neural Networks for Reasoning), but this paper proposes a new pipeline of tools: MLN, GNN and variational EM which seem to outperform all the existing baseline methods.The paper looks technically sound to me and the evaluations results are delivered neatly, however the flow of the paper makes it a bit difficult to follow sometimes due to many topics covered in it.
Regarding the significance of the paper, it tries to combine logic reasoning and probabilistic inference which is of great interest among the researchers recently. ExpressGNN proves to generalise well and perform accurate inference due to the tunable embeddings added at the GNN.

Overall, the work of this paper seems technically sound but I don’t find the contributions particularly surprising or novel. Along with plogicnet, there have been many extensions and applications of Gnns, and I didn’t find that the paper expands this perspective in any surprising way. 

review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: In this paper the authors propose a system, called ExpressGNN, that combines MLNs and GNNs. This system is able to perform inference and learning the weights of the logic formulas.

The proposed approach seems valid and really intriguing. Moreover the problems it tackles, i.e. inference and learning over big knowledge graphs, are of foremost importance and are interesting for a wide community of researchers.
I have just one concern and it is about the experiments for the knowledge graph completion task. In fact, this task was performed only on one KG. I think the proposed system should be evaluated on more KGs.

For these reasons I think the paper, after an extension of the experimental results, should be accepted.

[Minor]
Page 3. “The equality holds” which equality are you talking about?

review_title: Official Blind Review #2

Meta-review: This paper is far more borderline than the review scores indicate. The authors certainly did themselves no favours by posting a response so close to the end of the discussion period, but there was sufficient time to consider the responses after this, and it is somewhat disappointing that the reviewers did not engage.

Reviewer 2 states that their only reason for not recommending acceptance is the lack of experiments on more than one KG. The authors point out they have experiments on more than one KG in the paper. From my reading, this is the case. I will consider R2 in favour of the paper in the absence of a response.

Reviewer 3 gives a fairly clear initial review which states the main reasons they do not recommend acceptance. While not an expert on the topic of GNNs, I have enough of a technical understanding to deem that the detailed response from the authors to each of the points does address these concerns. In the absence of a response from the reviewer, it is difficult to ascertain whether they would agree, but I will lean towards assuming they are satisfied.

Reviewer 1 gives a positive sounding review, with as main criticism "Overall, the work of this paper seems technically sound but I don’t find the contributions particularly surprising or novel. Along with plogicnet, there have been many extensions and applications of Gnns, and I didn’t find that the paper expands this perspective in any surprising way." This statement is simply re-asserted after the author response. I find this style of review entirely inappropriate and unfair: it is not a the role of a good scientific publication to "surprise". If it is technically sound, and in an area that the reviewer admits generates interest from reviewers, vague weasel words do not a reason for rejection make.

I recommend acceptance.
Decision: Accept (Poster)