Paper ID: 4 Title: Uprooting and Rerooting Graphical Models Review #1 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): This work provides an algorithm for transforming MRFs into new MRFs by uprooting (introducing a new variable to encode all singleton potentials) and rerooting them (removing an existing variable and re-encoding some singletons). This is a simple yet elegant idea with many possible applications towards improving efficiency of inferences. Clarity - Justification: The paper is very well written and easy to follow. Proofs of results could be provided, even if as general ideas or sketches. Significance - Justification: The idea of uprooting is not novel and rerooting is quite straightforward. I am not an expert in this very topic, but I fail to see a great novelty in rerooting. On the other hand, the viewpoint that rerooting offers is quite interesting, leading to Theorem 3. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): The paper is well written and my only main comment regards the proofs of lemmas and the theorem. While the ideas are somehow clear, it would be interesting to have a some sketches of the proofs or anything a bit more formal. The experiments use quite small networks, which is a bit disappointing, but I do understand the difficulty to compare methods over larger domains. ===== Review #2 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): This paper explores the idea of "uprooting" and "rerooting" a binary pairwise Markov random field model. The basic idea is that a model that includes both singleton and edge potentials can be converted into a model that involves only edge potentials. The basic "uprooting" construction first adds a new variable, connects it to all variables that have singleton potentials, derives an edge potential from the singleton potential using a simple mapping, and then removes the singleton potentials. The "rerooting" construction is similar to clamping, but to to symmetry in the uprooted model, inference only needs to be run once to obtain marginals, etc. The key idea is that the original, uprooted, and rerooted models are all equivalent, and MAP configurations can be transferred across different equivalent rerootings easily. The authors show that the uprooting-rerooting procedure can be applied to simplify inference computations by extending the balanced graph criterion to the case of models that are balanced under rerooting. This allows for generalizing many prior results. Clarity - Justification: This paper is very well written. It is clear and well-structured. The one point that could use more justification is the introduction of the maxtW heuristic. It is justified by noting that large edge potentials do not have a linear effect on the hardness of inference. The maxtW certainly has sub-linear scaling and a hard saturation level, but it's not clear how well motivated this is and why we might expect it to be superior to a non-saturating sub-linear scaling like log(|W|+1). Further discussion of this point would be useful. Significance - Justification: As the authors point out, the "uprooting" and "rerooting" ideas are not novel as uprooting to M+ was discussed in the past, and rerooting is basically equivalent to clamping. However, by combining these two operations, the authors obtain a general method for transforming a given model into an alternate equivalent model where inference may be more computationally tractable. They idea that a graph that does not satisfy the balance criteria can potentially be converted into one that does by uprooting and re-rooting the graph at a particular node immediately extends a number of results that depend on the graph being balanced or almost balanced. Finally, the authors show that when combined with commonly used approximate inference methods, the approach can yield a real benefit in terms of error reduction when good rerootings are available. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): * As mentioned above, more details should be given on the maxtW heuristic. * Section 5.2 is one of the denser sections of the paper. More discussion of the related work that is referenced in this section would be helpful to establish the significance of Theorem 3. * It seems like there should be a special case of these results that apply when a graph has multiple disconnected components. In this case, MAP inference in M0 decomposes into a separate optimization problems per-component. The current construction would appear to couple all components together by tying all variables to the newly introduced X0. It seems like this could be solved by adding a separate new variable for each component. This would allow for each component to be re-rooted separately. This generalization could be useful for composing clamping and re-rooting. For example, if a graph can be broken into components using clamping, this more general form of rerooting could be applied to each component. More generally, it seems like it might always be possible to apply the unrooting operation while introducing more than one new variable for an arbitrary graph. It's not clear what would happen under re-rooting in this case or whether this is useful at all, but a discussion along these lines may be interesting. ===== Review #3 ===== Summary of the paper (Summarize the main claims/contributions of the paper.): The paper introduces the idea of rerooting and uprooting binary Markov networks. Uprooting is the process of removing local biases by incorporating them as interactions with a single new variable. Rerooting is the reverse process, where any node can be removed from and uprooted model by incorporating its interactions as local biases. The paper basically suggests that this combination defines an equivalence class over binary Markov networks where instead of dealing with a particular instance it could be beneficial to work with an equivalent uprooted and then rerooted model. Clarity - Justification: The paper is for the most part very polished and clearly written. The notation is generally accessible and several examples are used to demonstrate the main ideas. The only place where it falls short in clarity is in section 5.2, where it uses a variety of polytopes (e.g. LOC, TRI and Cut polytope) without definition. Significance - Justification: This is the weak aspect of the paper as it is basically a collection of small contributions. The main contribution is the simple yet interesting idea of rerooting. The paper claims that its (rerooting’s) combination with uprooting 1) deepens our understanding; 2) may be applied to any existing algorithm to yield improved methods and; 3) generalizes earlier theoretical results. The paper fails to show how this could be useful in improving existing algorithms (claim #2) in any practical setting. Most of the improvements reported in the experimental results could be achieved by simple clamping. The theoretical generalizations (#3) are rather unimpressive. Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Overall, the paper provides some interesting intuitions, but the significance of its contribution is debatable. There are two directions in which uprooting and rerooting could improve inference: 1-- By proper choice of variable to clamp, we may be able to “balance” a model, and eventually use inference techniques for attractive Markov nets. However, we do not expect this to apply often in larger random models and practical settings. Is this correct? 2-- Uprooting gives us the option of rerooting/clamping a node that strongly interacts with other variables in the graphical model. The paper argues that this is advantageous to simple application of “clamping” (without uprooting) to the original model as we need to perform inference only once. However, what is gained seems to be minimal as clamping a single variable does not significantly improve inference on larger (practically important) models, and one needs to use a set or a sequence of variables to clamp. However, uprooting and rerooting can be applied only once. Moreover, even a single application of clamping corresponds to clamping of two variables in the uprooted model, and therefore the factor of two in computational cost of inference (compared to uprooting/rerooting) is reasonable. =====