{"id":"32dc5e95-7cba-482f-aeb0-6e60dfab0b1a","arxiv_id":"1908.06482","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"GraphExp extracts small acyclic subgraphs that faithfully reproduce a target node's belief-propagation marginal on large cyclic Markov random fields.","lead":"This paper introduces GraphExp, a beam-search method that finds small tree-shaped subgraphs of a graphical model whose belief-propagation marginal for a target node closely matches the marginal on the full graph. It is aimed at making belief-propagation inferences on large, cyclic graphs interpretable for human users.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The empirical case for faithful explanation rests on hand-set homophily potentials and an unverified beam search; a calibrated-model reproduction is needed before the claimed superiority transfers.","rationale":"The reader's weakest assumption correctly identified the synthetic hand-set potentials as a key vulnerability. My stress-test agrees but sharpens the point: since Theorem II.1 rules out a submodular or monotone objective, there is no theoretical guarantee for the beam search, so the experiments are the entire support for the central faithfulness claim. The fixed 0.9-diagonal compatibility matrices and 0.9-on-true-class priors for non-Yelp networks create strongly assortative models in which tiny trees can match the full BP marginal without demonstrating that the method works on realistic heterogeneous dependencies. The missing user study, absent code/data, and lack of error bars compound the problem, but they are secondary to the core question of whether the reported rankings would survive a calibrated-model reproduction. I do not see an internal contradiction that would justify rejection; the right outcome is to keep the reader's CONDITIONAL verdict and require the proposed calibrated-model check before the strongest claims are accepted. Agreement is partial rather than full because I place additional weight on the absence of any approximation guarantee, which makes the empirical evaluation the sole load-bearing evidence.","tokens_in":17693,"tokens_out":8879,"duration_ms":98285,"concrete_test":"Re-run the Cora (or BlogCatalog) experiment from Table IV with MRF potentials estimated from the data (e.g., maximum pseudo-likelihood on a training split) instead of the fixed 0.9-diagonal/0.1-(c-1) potentials, and recompute the symmetric KL for GE-G(k=3), Comb, and the baselines. If the method ranking changes, or Comb's faithfulness degrades to a level that is no longer meaningfully better than the baselines, the claimed superiority is an artifact of the hand-set potentials.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Because Theorem II.1 shows the Eq. (4) objective is neither submodular nor monotone, Algorithm 1's beam search has no approximation guarantee; the central faithfulness claim rests entirely on the empirical comparison. That comparison is weakened by the way the MRFs are instantiated: for all non-Yelp networks, Sec. IV-B fixes every compatibility matrix to 0.9 on the diagonal and 0.1/(c-1) elsewhere and every labeled-node prior to 0.9 on the true class. These strongly homophilous synthetic potentials make it easy for a 5-node tree containing the target and a few labeled neighbors to reproduce b_X, so the reported low symmetric KL and the ranking of methods may be artifacts of the parameter choice rather than evidence about real inference tasks. The paper provides no code, data, or error bars for Table IV, and the user study announced at the start of Sec. IV is not reported. Consequently the strongest claim—'superior performance on 10 networks'—is not yet supported for calibrated or heterogeneous models.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper addresses interpretability of belief propagation (BP) inferences on Markov random fields (MRFs). The authors formulate the task as finding a small acyclic subgraph that, when used for BP, yields a marginal for a target node close to the full-graph marginal, measured by symmetric KL divergence. They claim that the optimization is NP-hard and that the objective is neither submodular nor monotone, and they propose GraphExp, a beam-search algorithm with two variants (GE-G and GE-L), parallelization, and a pruning strategy. Experiments on 10 networks compare the method against random, DeepWalk-based embedding, and LIME baselines, and a visualization case study is discussed.","tokens_in":17865,"tokens_out":7670,"duration_ms":72843,"significance":"If the claims are fully supported, the paper offers a principled and scalable way to generate diverse, simple explanations for a common inference algorithm, filling an important gap: prior work on graphical-model explanation did not handle cycles or target the inference process itself. The constrained cross-entropy formulation is clean, the local/global search trade-off is a reasonable design contribution, and the scalability analysis is concrete. However, the NP-hardness result is only cited rather than proved, the non-submodularity counterexample is not numerically verified, and the empirical evidence rests on hand-set potentials and an evaluation metric identical to the optimized objective. The significance of the work is therefore potentially high but not yet established.","major_comments":[{"comment":"The MRF parameters for all seven non-Yelp networks are hand-set: compatibility matrices have 0.9 on the diagonal and 0.1/(c-1) elsewhere, and labeled-node priors are 0.9 on the true class. These strongly homophilous potentials make it easy for a small tree containing the target and a few labeled neighbors to reproduce the marginal, so the reported low symmetric KL values and the ranking over baselines may be specific to this parameter choice. The paper's central claim of superior performance on real applications therefore needs support from calibrated models or real posterior distributions.","section":"Section IV-B (Experimental Setting) and Table IV"},{"comment":"The evaluation uses Eq. (4), which is exactly the objective minimized by GE-G. While baselines are compared fairly on the same metric, this measures how well the method achieves its own training target, not an independent notion of explanation quality. More importantly, the comparison is confounded by subgraph size: Comb builds subgraphs of average size 6.1–7.9 while GE-G(k=3) has average size at most 5.0, and the authors note in Section IV-D that faithfulness is positively correlated with size. No error bars or test statistics are reported that would support the claim of statistical significance.","section":"Section IV-D and Table IV"},{"comment":"The claim that the optimization in Eq. (4) is NP-hard is not proved; the text states it is 'similar to exhaustive feature selection' and cites [11] and [1]. No reduction from a known NP-hard problem (e.g., Steiner tree or k-median on graphs) to the constrained, acyclic subgraph problem is given. The abstract's 'We prove' is therefore misleading.","section":"Section III and Abstract"},{"comment":"The counterexample is asserted but not verified. The proof says 'One can run BP on G_i ... to find \\tilde{b}_X' and states an inequality, but it reports neither the beliefs on X nor the resulting symmetric KL distances. As written, the reader cannot check the claimed violation of submodularity and monotonicity; the proof needs explicit numbers or a small script.","section":"Theorem II.1"},{"comment":"The manuscript announces a user study ('we conduct user study to demonstrate the usability of GE-G') but no user-study results appear. The utility example on Yelp spam detection also lacks quantitative evidence: the logistic regression model is described but its coefficients, performance, and statistical significance are not provided. Claims about usability and utility are thus unsupported.","section":"Section IV and Section IV-G"},{"comment":"The 'safe pruning' claim that pruning does not hurt faithfulness is supported only by three curves on Yelp networks, without error bars, and no formal guarantee is given. The abstract's unconditional phrasing 'without hurting faithfulness' exceeds what the experiments establish.","section":"Section III-B and Fig. 4"}],"minor_comments":[{"comment":"There are several typos: Section IV has 'demostrate' for 'demonstrate', Section IV-G has 'reivewer' for 'reviewer', Fig. 3 caption has 'exlaining' for 'explaining', and Table II has 'Random varaibles' for 'Random variables'.","section":"Throughout"},{"comment":"'Compatibility metrics' should be 'compatibility matrices'.","section":"Section IV-B"},{"comment":"The pseudocode does not specify how the 'top k extensions' are ranked; this is only described in the text. Please add a pointer or make the pseudocode self-contained.","section":"Algorithm 1"},{"comment":"The caption appears garbled ('C e n t e r e d: t a r g e t n o d e'); please fix the formatting.","section":"Fig. 7 caption"},{"comment":"The proof of Theorem III.1 is trivial; consider moving it to a remark.","section":"Theorem III.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a solid core idea but appears to be incomplete in its current form. The NP-hardness proof is missing, the non-submodularity counterexample is unverified, the promised user study is absent, and the empirical comparison is confounded by subgraph size and hand-set potentials. These issues are fixable within the manuscript's scope, but they all bear on the central claims. The lack of code and data may also hinder reproducibility, and I would encourage the editor to request them."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing to know about arXiv:1908.06482 is that it defines a genuinely new problem: explaining a single belief-propagation marginal on a cyclic MRF by finding a small acyclic subgraph that, when re-run through BP, produces a nearly identical marginal. This is the right question for trust and debugging in fraud detection and similar settings. The authors propose a beam-search algorithm (GraphExp) with two variants, and they prove that the objective—symmetric KL between the full and subgraph marginals—is neither submodular nor monotone, so no greedy approximation guarantee is possible. That negative result is honest and useful.\n\nCredit where due: the problem formulation is novel relative to LIME, sparse covariance methods, and parameter-sensitivity analysis. The tree guarantee is trivial but worth stating. The pruning and parallelization experiments on Yelp are plausible, and the security finding (false negatives correlate with reviewer degree) is a nice demonstration of utility. The authors do not hide that their objective lacks submodularity.\n\nThe soft spots, roughly in order of severity:\n\nFirst, the empirical case for \"superior performance\" rests on synthetic potentials. For all non-Yelp networks, compatibility matrices are fixed to 0.9 on the diagonal and 0.1/(c-1) elsewhere, and priors to 0.9 for labeled nodes' true classes. That is an extremely homophily-friendly setting where a five-node tree containing a couple of labeled neighbors will nearly reproduce the target marginal. The reported low symmetric KL values are not surprising, and the ranking of methods may not transfer to calibrated or heterogeneous models. The stress-test note is right about this.\n\nSecond, the NP-hardness claim in the abstract is supported only by a citation to feature selection, not by a reduction. They do prove non-submodularity/non-monotonicity with a counterexample, which is enough for their algorithmic point, but the abstract overstates.\n\nThird, the user study announced in Section IV is not in the paper. Section IV-G is a visualization plus logistic-regression analysis, not a user experiment. That undermines the interpretability claims.\n\nFourth, Table IV has no error bars, and no code or data are released. Minor issues: the \"superlinear\" parallel speedup is suspicious without details, and \"safe pruning\" is only empirically validated.\n\nThe core algorithmic idea is sound, but the paper oversells its evidence. I would send it to a serious referee: the problem is important, the method is sensible, and the flaws are fixable with better experiments and more restrained claims. Engage with it.\n\nBest","headline":"A clean new problem formulation with a sensible beam search, but the empirical claims outrun the hand-set potentials and the missing user study.","tokens_in":18397,"tokens_out":4241,"would_cite":true,"duration_ms":41512,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes GraphExp, a beam-search method that explains belief-propagation inferences by extracting small trees whose target-node marginal closely matches the full graph's marginal.","keywords":["belief propagation","Markov random fields","model explanation","graph sparsification","beam search","symmetric KL divergence","scalable inference","fraud detection"],"falsifier":"Run GraphExp and the baselines on the same ten networks with MRF parameters estimated by maximum likelihood or cross-validation rather than hand-set, and compare the symmetric KL values; if the advantage of GraphExp over the baselines narrows or reverses, the claimed superiority depends on the synthetic parameterization.","tokens_in":17451,"feed_emoji":"🌲","tokens_out":4945,"duration_ms":46511,"temperature":0.7,"pith_summary":"This paper tries to establish that belief-propagation inferences on large cyclic graphical models can be explained by small tree-shaped subgraphs: for any target node, one can extract a subgraph with at most a handful of nodes, run belief propagation on it, and get a marginal for that node close to the marginal computed on the full graph. The authors formulate this as minimizing the symmetric KL divergence between the full-graph marginal and the subgraph marginal under an acyclicity and size constraint. They prove the optimization is NP-hard and that its objective is neither monotonic nor submodular, ruling out standard greedy guarantees, and they propose a beam-search algorithm, GraphExp, with two variants and a pruning strategy for scalability. Empirically, on ten networks with up to millions of nodes, the method reports lower symmetric KL divergence than LIME, embedding-based, and random baselines. If correct, this gives end-users a small, inspectable tree on which the inference's marginal is reproduced, supporting verification and debugging of model outputs.","feed_headline":"Small trees faithfully reproduce belief-propagation marginals","feed_subtitle":"GraphExp finds small acyclic subgraphs whose target marginals match full-graph belief propagation on ten networks.","key_machinery":"The load-bearing object is the constrained cross-entropy objective of Eq. (4): symmetric KL divergence between the marginal of a target node on the full cyclic MRF and the same marginal on a candidate acyclic subgraph. The search starts from the target node alone and greedily adds one neighbor at a time under an acyclicity constraint, evaluating each extension with a fresh belief-propagation run. Two instantiations are given: GE-G, which directly minimizes the global objective at each step, and GE-L, which back-traces messages and beliefs locally and stops when a prior explains a message. The beam keeps multiple candidate trees to provide diverse explanations, and the safe pruning strategy drops low-ranking candidates without, according to the experiments, degrading faithfulness. The non-submodularity theorem explains why the algorithm cannot rely on a $(1-1/e)$ approximation guarantee and instead must be evaluated empirically.","core_discovery":"The central claim is that explaining a belief-propagation marginal is equivalent to finding a small acyclic subgraph $\\tilde{G}$ of the original MRF $G$ that minimizes $d(b_X,\\tilde{b}_X)=KL(b_X\\|\\tilde{b}_X)+KL(\\tilde{b}_X\\|b_X)$, where $b_X$ is the target marginal on $G$ and $\\tilde{b}_X$ the marginal computed on $\\tilde{G}$. For any target $X$, a solution is a tree grown from $X$ one node at a time, and the paper proves that every output of its beam search is a tree. The paper also proves that exhaustive search for the optimal subgraph is NP-hard and that the objective is neither monotonic nor submodular, so no greedy algorithm carries a constant-factor guarantee. GraphExp therefore uses beam search to keep several candidate trees, evaluates each extension by rerunning belief propagation on the enlarged tree, and prunes the search space when the graph is dense. The reported result is that on ten networks from four domains the combined explanation reliably produces smaller symmetric KL divergence than the compared alternatives.","pith_inferences":["A natural extension the authors do not pursue is to apply the same extraction objective to other inference algorithms, such as loopy belief propagation with different message schedules or sampling-based marginals, treating the extracted tree as a surrogate that must match the algorithm's output rather than the model's true posterior.","The symmetric KL objective could be used as a training signal: one could search over trees not only to explain a fixed model but to choose model parameters that make the faithful explanation smaller, connecting explanation length to model simplicity.","Because the faithfulness measure is only evaluated under hand-set potentials, a testable next step is to compare extracted trees when the MRF parameters are learned from data; the authors' claims would be strengthened if the same advantage persists under calibrated potentials.","The Yelp security finding suggests the explanations can double as a diagnostic for biased detectors; one could formalize this by measuring whether explanation trees for false negatives systematically overweight high-degree neighbors across multiple datasets."],"forward_implications":["On any MRF where belief propagation converges, a user can inspect a tree of at most $C$ nodes and see the message-passing computations that produce an approximation of the target marginal, without tracing the entire call graph.","Explanations are acyclic by construction, so the recursive self-reference that arises from cycles in loopy belief propagation is avoided.","Multiple diverse explanations from the beam let users choose the tree that matches their mental model, and the combined explanation (Comb) is the most faithful in the reported experiments.","The pruning strategy gives a practical speedup on dense graphs while keeping faithfulness roughly unchanged, supporting interactive use on networks with millions of edges.","The extracted trees can be used to audit a deployed detector, as demonstrated by the finding that some false negatives in Yelp spam detection are driven by reviewer prolificacy."],"supporting_citations":[{"why":"Supplies the symmetric KL faithfulness measure and the ratification goal for explanations of Bayesian belief networks.","marker":"[41]"},{"why":"Provides LIME, the state-of-the-art black-box explanation baseline that GraphExp is compared against.","marker":"[35]"},{"why":"Supplies the Yelp review networks, the prior/compatibility settings for spam detection, and the detector whose errors are analyzed.","marker":"[34]"},{"why":"Gives the submodular maximization guarantee that the paper shows does not apply to its objective.","marker":"[30]"},{"why":"Supplies the diverse m-best beam-search idea used to maintain multiple candidate explanations.","marker":"[3]"},{"why":"Provides prior work on sparse graphical approximations that does not explain belief propagation, used as a contrast in problem framing.","marker":"[8]"},{"why":"Supplies prior sensitivity-analysis explanations for Markov networks, contrasted with GraphExp's inference-level explanations.","marker":"[5]"},{"why":"Supplies the citation network datasets (Cora, Citeseer, PubMed) used in the collective classification experiments.","marker":"[29]"},{"why":"Provides DeepWalk node embeddings used by the Embedding baseline for constructing subgraphs.","marker":"[33]"}],"fun_headline_variants":["Beam search grows small trees that explain graph inferences","Scalable explanations via tree subgraphs for belief propagation","GraphExp: faithful tree explanations for large graphs","Explaining inferences with minimal trees via beam search","Tree subgraphs replicate marginals at scale with beam search"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experiments assume that the synthetic model parameters chosen for each network—homophily potentials with 0.9 on the diagonal and 0.9 priors for labeled nodes—reflect the true dependency structure; if they do not, the reported faithfulness rankings may not transfer to deployed systems.","fun_headline_variants_meta":{"raw":{"variants":["Beam search grows small trees that explain graph inferences","Scalable explanations via tree subgraphs for belief propagation","GraphExp: faithful tree explanations for large graphs","Explaining inferences with minimal trees via beam search","Tree subgraphs replicate marginals at scale with beam search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000218,"raw_usage":{"total_tokens":1461,"prompt_tokens":985,"completion_tokens":476,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":601,"completion_tokens_details":{"reasoning_tokens":401}},"tokens_in":601,"tokens_out":476,"duration_ms":6032,"temperature":1.0,"reasoning_tokens":401,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:36:45.043788+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run GraphExp and the baselines on the same ten networks with MRF parameters estimated by maximum likelihood or cross-validation rather than hand-set, and compare the symmetric KL values; if the advantage of GraphExp over the baselines narrows or reverses, the claimed superiority depends on the synthetic parameterization.","supporting_citations":[{"cited_title":"Explanation in bayesian belief networks","cited_arxiv_id":null,"evidence_quote":"Supplies the symmetric KL faithfulness measure and the ratification goal for explanations of Bayesian belief networks."},{"cited_title":"Why should i trust you?: Explaining the predictions of any classifier","cited_arxiv_id":null,"evidence_quote":"Provides LIME, the state-of-the-art black-box explanation baseline that GraphExp is compared against."},{"cited_title":"Collective opinion spam detection: Bridging review networks and metadata","cited_arxiv_id":null,"evidence_quote":"Supplies the Yelp review networks, the prior/compatibility settings for spam detection, and the detector whose errors are analyzed."},{"cited_title":"An analysis of approximations for maximizing submod- ular set functions","cited_arxiv_id":null,"evidence_quote":"Gives the submodular maximization guarantee that the paper shows does not apply to its objective."},{"cited_title":"Diverse m-best solutions in markov random fields","cited_arxiv_id":null,"evidence_quote":"Supplies the diverse m-best beam-search idea used to maintain multiple candidate explanations."},{"cited_title":"Sparse inverse covariance estimation with the graphical lasso","cited_arxiv_id":null,"evidence_quote":"Provides prior work on sparse graphical approximations that does not explain belief propagation, used as a contrast in problem framing."},{"cited_title":"Sensitivity analysis in markov networks","cited_arxiv_id":null,"evidence_quote":"Supplies prior sensitivity-analysis explanations for Markov networks, contrasted with GraphExp's inference-level explanations."},{"cited_title":"Collective graph identification","cited_arxiv_id":null,"evidence_quote":"Supplies the citation network datasets (Cora, Citeseer, PubMed) used in the collective classification experiments."}],"review_version":1}