{"id":"42937197-2a85-4650-b19a-4fec73e8220f","arxiv_id":"1908.09393","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A probabilistic matrix factorization method that prunes graph edges with negative latent-feature correlations improves prediction accuracy and keeps computation linear in the number of nonzeros.","lead":"This paper introduces a method that finds and removes unreliable edges in the similarity graphs used to improve matrix factorization predictions. It reports better prediction accuracy on several recommendation datasets and can analyze a graph with three million edges on a laptop, which matters because noisy side information is common in real-world systems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The M-step's contested-edge identification is not validly grounded: tau=0 lies outside the GLASSO equivalence regime and sign-consistency is unverified, so the removed edges may not be contested and the accuracy gains could be generic sparsification.","rationale":"The central claim is that removing 'contested edges' improves prediction accuracy and scalability. For that claim, the mechanism matters: the method must actually identify edges that are harmful because they contradict the data-driven latent-feature relations. The reader's weakest assumption correctly locates the fragility in the M-step: the thresholding rule in Equation (8) is the only link between the observed data and the graph update, and its theoretical support is a GLASSO equivalence that is invoked at tau=0, a parameter regime where the cited conditions do not apply. I agree with that diagnosis. I would add two sharpenings. First, the object being thresholded is E[S_D], a posterior expectation of the second moment under an approximate posterior; this is not a sample covariance drawn from the prior, so the Fattahi-Sojoudi guarantee (which concerns sample covariances of i.i.d. draws) is not directly applicable even if tau were positive. Second, the paper's own simulations show only moderate detection accuracy, so the empirical improvements could in principle arise from the sparsification effect of removing edges rather than from the targeted removal of contested edges. A random-removal control would separate these explanations. Other concerns (missing error bars, the non-stationary convergence claim, the column-wise independence approximation) are real but secondary: they affect the strength of the empirical evidence and the correctness of tangential theoretical statements, whereas the M-step validity is load-bearing for the paper's main scientific claim. Since the evidence is broad and the method is plausible, the appropriate verdict remains conditional pending this test.","tokens_in":16099,"tokens_out":15860,"duration_ms":161314,"concrete_test":"Run a controlled synthetic experiment with the same generative setup as Section 4.1 (known true graph, known contested edges, graph fidelity 0.7). Compare GPMF against two controls: (a) GRALS on the original graph, and (b) GRALS on a graph produced by removing exactly the same number of edges as GPMF does, but chosen uniformly at random (or by smallest absolute covariance) so that no contested-edge information is used. If control (b) achieves RMSE within noise of GPMF, the accuracy gain is not attributable to contested-edge identification and the central claim fails. If GPMF clearly outperforms random-removal controls across fidelity levels, the contested-edge mechanism is supported despite imperfect detection.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Equation (8) removes graph edges whose expected sample covariance E[S_D] is below tau=0. The paper justifies this by the Fattahi-Sojoudi thresholding/GLASSO equivalence, but that result is stated for sufficiently large penalty tau and roughly 10N non-zeros. At tau=0 the GLASSO penalty vanishes, the solution is the dense inverse SCM, and the support-equivalence argument is vacuous; sign-consistency (sign(Theta_ij) = -sign(S_ij)) is not guaranteed for arbitrary covariance matrices. Moreover, E[S_D] is a posterior second moment under an approximate posterior, not a sample covariance from the prior, so the cited equivalence does not directly apply to the object being thresholded. The paper's own synthetic evaluation (Section 4.1) reports only 31.7% of true contested edges removed and 19% of true edges wrongly removed at 7% observations, and the conclusion concedes the GLASSO approximation is only moderately successful. If the M-step does not reliably identify contested edges, the improvement over GRALS could be caused simply by removing graph edges and weakening the prior, rather than by the contested-edge mechanism claimed in the abstract. The central claim therefore rests on an unvalidated identification step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript introduces GPMF, a probabilistic formulation of graph-regularised matrix factorization in which the precision matrices of the latent-feature priors are graph Laplacians, and GRAEM, an alternating algorithm that—after a PMF initialization—uses a thresholded posterior sample-covariance matrix to delete graph edges whose latent-feature correlation is negative (the 'contested edges'). The authors show in Lemma 1 that, conditional on a fixed graph, the MAP objective coincides with the GRALS objective. The central empirical claims are that pruning contested edges improves RMSE relative to GRALS on Flixster, MovieLens100k, Epinions, and MovieLens20M, and that the pruning step has linear cost, allowing a 300k-node/3M-edge graph to be processed in under ten minutes on a laptop.","tokens_in":16397,"tokens_out":6536,"duration_ms":63525,"significance":"If the identification step works as claimed, the contribution is practically valuable: a linear-time graph-pruning heuristic that improves accuracy and can be appended to GRALS, with a principled probabilistic derivation and experiments on standard benchmarks. The paper is also honest in reporting mixed results (Yahoo Music, KPMF with pruned graphs) and in acknowledging that the GLASSO approximation is only moderately successful in simulation. The main significance is limited, however, by the fact that the contested-edge identification—the mechanism behind the claimed accuracy gains—is not convincingly validated, and the claimed convergence guarantee does not follow from the cited tools.","major_comments":[{"comment":"The pruning rule in Eq. (8) thresholds E[S_D] at τ=0 and is justified by the sign-consistency and sparsity-equivalence results of Fattahi and Sojoudi. Those results are stated for a sufficiently large penalty τ with a highly sparse GLASSO solution (roughly 10N non-zeros). At τ=0 the GLASSO penalty vanishes, the solution is the dense inverse sample covariance, and the support-equivalence argument does not apply. The paper's own synthetic evaluation (Section 4.1) reports that only 31.7% of true contested edges are removed and 19% of true edges are wrongly removed at 7% observations, and the conclusion states that the GLASSO approximation is 'only moderately successful.' Because Eq. (8) is the entire M-step, the central claim that accuracy gains come from removing contested edges rests on an unvalidated approximation. I ask the authors to verify sign-consistency at the operating point, to compare against thresholding at positive τ where the cited equivalence has support, and to include a control such as random edge removal at the same rate to show the gains are not generic sparsification.","section":"§3.3.3, Eq. (8)"},{"comment":"The quantity thresholded in Eq. (8) is E[S_D] = (1/D) Σ_d (Σ_post_{U:d} + μ_post_{U:d} μ_post_{U:d}^T), a posterior second moment computed under a column-wise-independence approximation and MAP substitution. This is not an empirical sample covariance of i.i.d. draws from the model, so the cited GLASSO/thresholding equivalence—which is a statement about sample covariance matrices—does not directly apply to the object being thresholded. The authors should either derive the thresholding rule for posterior second moments under their approximate posterior, or explicitly treat Eq. (8) as a heuristic and validate it empirically; the current text moves between 'MLE' and 'highly-efficient approximation' without establishing which claim is being made.","section":"§3.3.1–3.3.4"},{"comment":"The abstract and Section 3 state that the EM formulation 'guarantees convergence' and that the method inherits the global convergence guarantees of GRALS via Xu and Yin. Those guarantees apply to block-coordinate minimization of a fixed biconvex objective. Here the M-step does not maximize Q (it heuristically changes the graph), and the graph change alters the regularizer in the subsequent E-step, so the objective is not fixed across iterations. The convergence claim is therefore unsupported as stated. Please state the precise convergence property that is guaranteed, or weaken the claim to empirical convergence.","section":"Section 3, Algorithm 1"}],"minor_comments":[{"comment":"The sentence 'we get the same accuracy for Flixster with almost halved edges' is accurate from the table, but the accompanying claim that the pruned graph improves 'arbitrary algorithms' is contradicted by the MovieLens100k KPMF result (0.9336 vs 0.9374).","section":"Section 4.2, Table 1"},{"comment":"The notation switches between Λ_U and L_U^+ without consistently naming the regularization strength; in Eq. (4) the factor σ^2/2 appears without explaining that the posterior has been multiplied by σ^2.","section":"Section 2, Eq. (4)"},{"comment":"The text says 'at worst GPMF is only as bad as using the original corrupted graph,' but at high noise PMF appears competitive, and the comparison point is not clearly defined; please clarify.","section":"Section 4.1, Figure 2"},{"comment":"The proportion of remaining edges is reported in figure titles, but for MovieLens20M the caption says '40NN graph' while the text reports 10/20/40-NN results; it would help to state all edge-retention rates in one table.","section":"Section 4.2, Figure 3"},{"comment":"Several typos should be corrected: 'effect' for 'affect' (Section 1), 'helf' for 'half' (Section 4.2), 'samge' for 'same' (Appendix B.2), and inconsistent verb tense in Section 4.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"I agree with the stress-test assessment: the M-step identification is the load-bearing weakness. The paper is not circular, and the empirical work is honest, but the central mechanism needs stronger support before publication. The convergence claim should also be corrected or softened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a look if you work on matrix completion with side information. The core idea is new: instead of taking a side-information graph as fixed, prune edges whose latent-feature correlations are negative, using a cheap GLASSO-style thresholding step. The paper shows that this pruning, applied once after a PMF initialization, improves RMSE over GRALS on several benchmarks and handles a 300k-node graph in minutes. That is a real practical result.\n\nThe paper does several things well. The GPMF generative model and the EM derivation are clean, Lemma 1 correctly connects the model to the GRALS objective, and the appendices give the posterior derivations. The experiments are broad, synthetic and real, including large-scale, and the authors are honest that their GLASSO approximation only moderately identifies contested edges in simulations.\n\nThe soft spots are in the M-step justification. Equation (8) thresholds E[S_D] at tau=0 and calls the negative entries contested edges, citing Fattahi-Sojoudi equivalence. That equivalence holds for sufficiently large penalty and roughly 10N non-zeros; at tau=0 the GLASSO penalty disappears and the support-equivalence argument is empty. Also, E[S_D] is a posterior second moment under an approximate distribution, not a sample covariance from the prior, so the theorem does not directly apply. The paper does not verify sign-consistency on real data. That said, the impact is not fatal: the synthetic experiments report only 31.7% CE removal at 7% observations, yet the method still improves prediction accuracy, so the benefit seems robust to imperfect edge identification. But it means the 'contested edge' mechanism is not cleanly established; the gain could partly come from generic sparsification or from the one-step EM effectively reweighting the graph. The convergence guarantee is also asserted for a changing-graph objective, but since the algorithm uses a single M-step, this is more a presentation issue than a practical one.\n\nOne thing I miss is released code. The algorithm is simple, but the sparse-Cholesky and CG details matter for reproducing the timing claims.\n\nOverall: solid, useful, incremental work. I would send it to review; the authors should either fix the M-step theory or reframe it as a heuristic with empirical support.","headline":"A practical graph-pruning step for matrix factorization that works in experiments, but the contested-edge story is better supported empirically than theoretically.","tokens_in":16913,"tokens_out":2474,"would_cite":true,"duration_ms":26655,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Prune bad graph edges to make matrix factorization better and faster","keywords":["matrix factorization","graph side-information","contested edges","graphical lasso","expectation maximization","collaborative filtering","probabilistic matrix factorization","large-scale graphs"],"falsifier":"Take a synthetic 400 by 400 setup with a known true graph and a known fraction of planted contested edges, run GRAEM's zero-threshold M-step, and also run an explicit constrained graphical-lasso solve on the same expected sample covariance, then compare the two edge sets and the RMSE of each; if the sets diverge substantially under the paper's reported settings (7% observed entries, $\\sigma^2 = 0.01$), the claimed equivalence is not what drives the accuracy gain.","tokens_in":15871,"feed_emoji":"🧹","tokens_out":8063,"duration_ms":78057,"temperature":0.7,"pith_summary":"The paper claims that noisy, irrelevant graph side-information hurts matrix-factorization prediction, and that the fix is to delete graph edges whose latent-feature covariance is negative, the contested edges. It introduces GPMF, a probabilistic model that places a graph-shaped Gaussian prior on the columns of the latent feature matrices, and GRAEM, an expectation-maximization algorithm that alternates a graph-regularized least-squares E-step with a cheap M-step that prunes contested edges by thresholding an estimated sample covariance matrix at zero. The paper argues this pruning is a graphical-lasso approximation and adds no computational complexity: the method stays linear in the number of non-zeros, and runtime shrinks as edges are removed. A reader should care because, if correct, the result means graph side-information can be made both more accurate and cheaper to use through one simple step that any graph-regularized matrix-completion method could adopt. Experiments report lower RMSE than the scalable baseline on Flixster, MovieLens 100k/20M, and Epinions, and full processing of a 300k-node, three-million-edge Yahoo Music graph in under ten minutes on a laptop.","feed_headline":"Prune bad graph edges to make matrix factorization better and faster","feed_subtitle":"A zero-threshold EM step removes edges that disagree with the data, cutting RMSE on four benchmarks and keeping runtime linear.","key_machinery":"The load-bearing object is the adjacency update rule: an edge survives only if the expected sample covariance $E[S_D]$ of the latent features is at least the threshold $\\tau$ (set to zero), otherwise it is removed as contested. The paper computes this expectation by decomposing each outer product into posterior covariance plus outer product of posterior means, then approximates the posterior covariance with an unbiased Monte Carlo estimate from K samples drawn via sparse Cholesky factorization of a block-diagonal approximation to the posterior precision; this column-wise independence assumption makes the Cholesky step linear in the graph size. The step is justified as a constrained graphical-lasso approximation by sign-consistency results saying that, for sparse and large problems, thresholding the sample covariance marks the same non-zeros as the graphical lasso would.","core_discovery":"The central discovery is that a graph edge is worth keeping only if the latent features of its endpoints are positively correlated given the observed ratings; edges with negative estimated covariance actively mislead the factorization, and removing them helps. GPMF formalizes this by replacing the spherical priors of probabilistic matrix factorization with full-covariance Gaussian priors whose precision matrices are regularized Laplacians built from the graph, so the prior becomes a Gaussian Markov random field. Using EM, the M-step estimates the expected sample covariance of the latent feature columns and removes entries whose covariance is below $\\tau=0$, which the authors identify as contested edges via sign-consistency results for the graphical lasso. The paper shows the E-step MAP objective equals the GRALS objective, giving convergence guarantees, and that the extra M-step is linear-cost; on real benchmarks the pruned graphs improve RMSE while using fewer edges, and on a densified 40-nearest-neighbour MovieLens20M graph GPMF improves while the fixed-graph baseline worsens.","pith_inferences":["Not stated in the paper: the zero threshold is a heuristic rather than a verified regime of the underlying equivalence theorem. One could stress-test it by replacing Equation (8) with an explicit constrained graphical-lasso solve on the same covariance and comparing both the edge sets and final RMSE; the paper's own synthetic numbers (only 31.7% to 44.3% of planted contested edges recovered) sugge","Not stated in the paper: the column-wise independence assumption that makes the posterior covariance tractable is also a modelling restriction, because a full inverse-Kronecker-sum covariance would couple the latent-feature columns. Extending the M-step to a low-rank plus diagonal correction could capture more signal without breaking linear complexity.","Not stated in the paper: because the M-step is written as an adjacency update, it is a model-selection rule for the Gaussian Markov random field graph itself, which connects the method to graph-learning problems and suggests an iterative or annealed version could trade graph sparsity against accuracy in a principled way.","A testable extension, absent from the paper, is to apply the pruned graph to graph-convolutional matrix-completion models, which the paper benchmarks but does not train on the updated graph; if the gain transfers, contested-edge removal is a model-agnostic graph-denoising step."],"forward_implications":["On the reported benchmarks GPMF/GRAEM achieves RMSE 0.8857 on Flixster versus 0.9152 for GRALS, and 0.7887 on MovieLens20M (40NN) versus 0.7922, so pruning edges improves accuracy over keeping the full graph.","The method's complexity remains linear in the number of non-zeros; each removed edge shrinks the adjacency matrix, making the regularized least-squares iterations cheaper, and the paper demonstrates a 300k by 300k graph with 3 million edges updating in under ten minutes on a laptop.","The generated graph is reusable: feeding the pruned graph to KPMF preserves or improves accuracy (77% of Douban user edges, 65% of MovieLens 100k edges), suggesting contested-edge removal is a general preprocessing step for graph-regularized matrix completion.","Increasing graph density from 10 to 40 nearest neighbours degrades GRALS but lets GPMF keep improving, so noisy graphs can be rendered useful instead of discarded.","On synthetic data with 10% observed entries, GPMF nearly matches the accuracy of the true graph, while GRALS needs about 30% observations for comparable accuracy; when observation noise grows, GPMF degrades to at worst the corrupted-graph baseline."],"supporting_citations":[{"why":"Supplies GRALS, the scalable graph-regularized alternating least squares baseline whose objective GPMF generalizes, and the Yahoo Music scalability setting.","marker":"Rao et al. [2015]"},{"why":"Provides the sign-consistency and sparsity equivalence between thresholded sample covariance and graphical lasso that justifies removing contested edges by zero-thresholding.","marker":"Fattahi and Sojoudi [2019]"},{"why":"Shows how large-scale sparse inverse covariance estimation can be done by thresholding and max-det matrix completion, supporting the linear-cost sparse Cholesky approximation of the posterior covariance.","marker":"Zhang et al. [2018]"},{"why":"Supplies the graphical lasso as the sparse maximum-likelihood solver for the precision matrix and the connected-component property used in the M-step.","marker":"Mazumder and Hastie [2012]"},{"why":"Defines probabilistic matrix factorization, the model GPMF extends and the initialization used before the EM steps.","marker":"Mnih and Salakhutdinov [2008]"},{"why":"Introduces kernelized PMF with graph priors, the full-covariance-prior ancestry of the model, and provides the KPMF baseline compared in experiments.","marker":"Zhou et al. [2012]"},{"why":"Provides the sRMGCNN deep-graph baseline and the 3k Flixster/Douban subsets used in real-data comparisons.","marker":"Monti et al. [2017]"}],"fun_headline_variants":["Remove contested graph edges for better matrix completion","Graph side-information is often wrong: prune the bad edges","EM-based edge pruning speeds up matrix factorization","Prune edges that disagree with data to boost factorization","Linear-time edge removal improves matrix factorization accuracy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The rule that decides which edges are contested relies on the theorem that thresholding the sample covariance at zero marks exactly the edges the graphical lasso would set to zero; the paper sets the threshold to zero on real datasets without verifying the theorem's conditions, so if those conditions fail the deleted edges need not be the contested ones.","fun_headline_variants_meta":{"raw":{"variants":["Remove contested graph edges for better matrix completion","Graph side-information is often wrong: prune the bad edges","EM-based edge pruning speeds up matrix factorization","Prune edges that disagree with data to boost factorization","Linear-time edge removal improves matrix factorization accuracy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000676,"raw_usage":{"total_tokens":3074,"prompt_tokens":943,"completion_tokens":2131,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":559,"completion_tokens_details":{"reasoning_tokens":2059}},"tokens_in":559,"tokens_out":2131,"duration_ms":17150,"temperature":1.0,"reasoning_tokens":2059,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:12:53.298370+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a synthetic 400 by 400 setup with a known true graph and a known fraction of planted contested edges, run GRAEM's zero-threshold M-step, and also run an explicit constrained graphical-lasso solve on the same expected sample covariance, then compare the two edge sets and the RMSE of each; if the sets diverge substantially under the paper's reported settings (7% observed entries, $\\sigma^2 = 0.01$), the claimed equivalence is not what drives the accuracy gain.","supporting_citations":[{"cited_title":"Collaborative filtering with graph information: Consistency and scalable methods","cited_arxiv_id":null,"evidence_quote":"Supplies GRALS, the scalable graph-regularized alternating least squares baseline whose objective GPMF generalizes, and the Yahoo Music scalability setting."},{"cited_title":"Graphical lasso and thresholding: equivalence and closed-form solutions","cited_arxiv_id":null,"evidence_quote":"Provides the sign-consistency and sparsity equivalence between thresholded sample covariance and graphical lasso that justifies removing contested edges by zero-thresholding."},{"cited_title":"Large-scale sparse inverse covariance estimation via thresholding and max-det matrix completion","cited_arxiv_id":null,"evidence_quote":"Shows how large-scale sparse inverse covariance estimation can be done by thresholding and max-det matrix completion, supporting the linear-cost sparse Cholesky approximation of the posterior covariance."},{"cited_title":"Probabilistic matrix factorization","cited_arxiv_id":null,"evidence_quote":"Defines probabilistic matrix factorization, the model GPMF extends and the initialization used before the EM steps."},{"cited_title":"Kernelized probabilistic matrix factorization: Exploiting graphs and side information","cited_arxiv_id":null,"evidence_quote":"Introduces kernelized PMF with graph priors, the full-covariance-prior ancestry of the model, and provides the KPMF baseline compared in experiments."},{"cited_title":"Geometric matrix completion with recurrent multi-graph neural networks","cited_arxiv_id":null,"evidence_quote":"Provides the sRMGCNN deep-graph baseline and the 3k Flixster/Douban subsets used in real-data comparisons."}],"review_version":1}