{"id":"601e3917-2a49-4b45-8825-6ee56fe30178","arxiv_id":"1908.05153","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ANGPN jointly learns an adaptive neighborhood graph and propagates node features through it, improving semi-supervised classification accuracy by a few points over fixed-graph GCN on SVHN, CIFAR, 20News, and CoraML.","lead":"The paper introduces ANGPN, a graph neural network that builds its neighborhood graph while it propagates features, instead of using a fixed graph. It reports small accuracy gains over GCN and several graph models on four image and text benchmark datasets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (9) uses η from Dx rather than from Q = Dx − βFFᵀ, so Algorithm 1 does not solve the stated optimization; rows of S need not sum to one.","rationale":"The reader's weakest assumption correctly identifies the gap in the closed-form update. My independent check of the algebra confirms it: substituting Q = Dx − βFFᵀ into the standard solution of min Σ Q_ij S_ij + γ||S||²_F with row-sum constraints yields η depending on the k smallest entries of Q. The paper's Eq. (9) instead uses η from Dx, and the accompanying remark confirms the authors sorted Dx. This matters because F is updated each iteration, so Q changes; using a fixed η computed from Dx cannot keep rows normalized. The result is that the S used in the forward pass is not the minimizer of the ANFP objective, so the 'optimal neighborhood graph' claim lacks a derivation-level basis. This is a correctable problem: recomputing η from Q and re-running the experiments would settle whether the reported gains persist. It does not, by itself, impugn the empirical comparisons, so the appropriate verdict remains CONDITIONAL, as the reader concluded. I agree with the reader's choice; no change to the verdict is needed.","tokens_in":8909,"tokens_out":4099,"duration_ms":39840,"concrete_test":"Take a small random instance (n=20, d=5), fix γ=0.1, β=0.3, H random Gaussian, set F=H, compute S via Eq. (9) as written (η from Dx). Compute row sums and report the maximum deviation from 1. Next, recompute S using the correct η from the sorted entries of Q = Dx − βFFᵀ and verify row sums are 1 to machine precision. Then run two iterations of Algorithm 1 and check whether the row sums of S drift further when η is frozen from Dx. If the first row sums deviate beyond 1e-6 while the corrected version does not, Eq. (9) does not solve Eq. (8) as written.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section II-B, Eq. (9), states that the row-wise minimizer of Eq. (8) is S_ij = max{ −(1/(2γ))(Dx − βFFᵀ)_ij + η, 0 } with η = 1/k + (1/(2kγ))Σ_{j=1}^k Dx_ij, where Dx rows are sorted. This is the closed form for minimizing Σ Dx_ij S_ij + γ||S||²_F subject to row sums one, as in Nie et al. [14]. But the actual objective in Eq. (8) contains Q = Dx − βFFᵀ, and the correct η must be computed from the k smallest entries of Q, not of Dx. Since F changes in every step of Algorithm 1, Q changes, and a single η computed from Dx (line 4) does not enforce Σ_j S_ij = 1 after the first iteration. Consequently the S produced by Algorithm 1 is not the solution of the optimization problem that defines ANFP, and the claim that ANGPN learns an optimal neighborhood graph is not supported by the derivation. The error is internal to the paper, not a matter of differing from community consensus: the formula cited from [14] applies to the matrix appearing in the linear term, and here that matrix is Q.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Adaptive Neighborhood Graph Propagation Network (ANGPN), a semi-supervised learning method that alternately learns a row-stochastic neighborhood graph S from pairwise distances and propagates node features through that graph inside a GCN-like architecture. The model is derived from an optimization problem, ANFP, that combines a graph-learning term, a graph-smoothness term on features, and a feature-fitting term. The authors derive a closed-form update for S, a closed-form update for F, then approximate the F-update with a one-step power iteration and truncate the alternating procedure to T steps. Experiments on SVHN, CIFAR, 20News, and CoraML compare ANGPN with LP, ManiReg, DeepWalk, DGI, GraphSAGE, GCN, and GAT at 10%, 20%, and 30% label rates; Table I reports consistent, modest accuracy gains over the fixed-graph baselines.","tokens_in":9226,"tokens_out":6509,"duration_ms":67359,"significance":"If the derivation were sound, the paper would present a principled approach to jointly learning the neighborhood graph and the feature representation, which is a timely and useful idea. The empirical comparison in Table I is the main strength: ANGPN outperforms GCN, GAT, DGI, and GraphSAGE on all four datasets at most label rates, and the gains are consistent across five random splits. The comparison against an NGPN baseline in Table II also supports the benefit of the cooperative graph-learning mechanism. The paper does not provide code, so the quantitative results cannot be independently checked, but the experimental setup with multiple label rates and standard baselines is reasonable. However, the derivation of the S-update has a load-bearing error that undermines the claim that Algorithm 1 solves the stated optimization; the current significance is therefore empirical rather than theoretical.","major_comments":[{"comment":"The closed-form update for S is not the minimizer of Eq. (8). The objective in Eq. (8) has a linear coefficient Q = Dx − βFF^T, not Dx alone, and the row-sum constraint Σ_j S_ij = 1 requires the Lagrange multiplier η_i to be computed from the sorted entries of Q_i. Specifically, the row-wise solution is S_ij = max{(η_i − Q_ij)/(2γ), 0}, and the constraint forces η_i = 1/k_i + (1/(2k_iγ)) Σ_{j=1}^{k_i} Q_ij over the positive entries of row i. Since F changes in every iteration of Algorithm 1, Q changes, and the fixed η computed from Dx in line 4 cannot enforce unit row sums except when β=0. The cited result [14] applies to the matrix appearing in the linear term, which is Q here. Therefore Algorithm 1 does not solve Eq. (5), and the claim that ANGPN learns an optimal neighborhood graph is not supported by the derivation. This is an internal inconsistency, not a matter of differing from community consensus.","section":"Section II-B, Eq. (9) and Algorithm 1, lines 4–6"},{"comment":"The one-step power iteration F = (αS + (1−α)I)H does not solve the closed-form F-update of Eq. (11), and no analysis is given for the truncated T-step approximation with T=2. The abstract and introduction claim a 'unified formulation' that 'learns an optimal neighborhood graph,' but the actual network uses a doubly approximated algorithm: the S-update is not exact as shown above, and the F-update is a one-step approximation rather than the fixed point of Eq. (11). The paper should state explicitly what objective, if any, the truncated algorithm optimizes, and explain why this approximation preserves the cooperative benefit of graph construction and feature propagation. Without this, the 'optimal graph' language overstates what is demonstrated.","section":"Section III-A, Eq. (13) and Algorithm 1"}],"minor_comments":[{"comment":"In the description of the NGPN baseline, 'constructs the graph S via Eq.(15)' appears to be a typo: Eq. (15) is the cross-entropy loss. The intended reference is likely Eq. (8) or Eq. (9). Similarly, 'conducts feature propagation on S via Eq.(19)' refers to a nonexistent equation; the intended update is likely Eq. (13).","section":"Section IV-C"},{"comment":"The parameter k in the formula for η is not defined in the model. In the adaptive-neighbors literature, k denotes the number of selected neighbors (the number of positive entries in a row), but here the manuscript uses it as if it were a single global constant. Please clarify whether k is a user-set neighbor count, the average number of positives, or another quantity, and how it interacts with γ in determining sparsity.","section":"Section II-B, Eq. (9)"},{"comment":"The statement that ANGPN has 'similar time consuming with GAT' is not supported by the reported complexity O(T(kn + 2dn^2)). Since S is an n×n dense matrix, the O(n^2 d) dependence on n is qualitatively different from GAT's dependence on edges and feature dimensions, especially for the dataset sizes used here. Please justify or rephrase the complexity comparison.","section":"Section III-C"},{"comment":"The text says 'Figure 2 shows the performance of ANGPN method across different number of convolutional layers,' but the displayed figure is labeled Figure 1 and the caption describes the same content. Please correct the figure numbering and make the cross-references consistent.","section":"Section IV-D and Figure 1"},{"comment":"For SVHN and CIFAR, the manuscript says a 'commonly used CNN feature descriptor' is extracted but does not specify which descriptor or how it was obtained. Please state the feature extraction method so that the experiments are reproducible.","section":"Section IV-A"}],"recommendation":"major_revision","confidential_remarks":"The main issue is the S-update derivation: as written, Algorithm 1 does not solve the stated optimization, and this is directly tied to the paper's central 'optimal graph' claim. The fix is conceptually local (recompute η from Q = Dx − βFF^T inside the loop), but it changes the algorithm and may affect the reported numbers. The authors should either correct the derivation and rerun the experiments, or reposition the paper as a heuristic with empirical support. The relation to the authors' prior GOCN/GmCN papers (refs [12], [13]) should also be clarified; the novelty appears incremental, and the current derivation relies heavily on those earlier models plus Nie et al.'s adaptive-neighbors formula."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short take: the paper has a real empirical finding but a load-bearing derivation gap in the graph update. The idea is to replace the fixed graph in GCN feature propagation with an adaptive neighborhood graph learned from pairwise distances, in the style of Nie et al.'s adaptive neighbors with a closed-form row-normalized solution. The model iterates between updating S and propagating features. On four datasets, ANGPN beats fixed-graph GCN, GAT, DGI, and GraphSAGE by 1–3 accuracy points, and beats its own NGPN baseline. That is an incremental but real contribution, and the experiments look okay on their face, though no code or detailed hyperparameters are given.\n\nThe main problem is in Section II-B. The objective in Eq (8) has the matrix Q = Dx - beta FF^T in the linear term. The closed-form solution in Eq (9) is correct only if eta is computed from the k smallest entries of Q. As written, Algorithm 1 computes eta once from Dx and reuses it while F changes. Unless beta=0, nothing enforces the row-sum constraint sum_j S_ij = 1 after the first update. So S produced by Algorithm 1 is not the solution to the stated minimization, and the claim that ANGPN learns an 'optimal' neighborhood graph is not supported by the derivation. This is an internal inconsistency, not a matter of differing from community consensus. The stress-test note is right.\n\nThe paper could be fixed by deriving the correct eta for Q and updating it, or by explicitly reframing S as a heuristic and dropping the optimality claim. Also, gamma and k are never reported, the graph construction for the fixed-graph baselines is unspecified, and the novelty relative to the authors' own GOCN and GmCN is modest — those already couple graph construction and convolution, and this paper essentially swaps in Nie et al.'s adaptive-neighbors objective. That said, the empirical comparison against external baselines is independent, so the result is not a fitted claim.\n\nBottom line: worth a serious referee, but only after revision. I'd send it to review with major revision required. It is not a desk reject, but I wouldn't cite it in my own work right now. It is a reasonable reading-group paper for graph learning folks, especially as a case study in checking whether the update actually solves the stated optimization.","headline":"Useful incremental model for adaptive graph learning in GCNs, but the derivation of the graph update has a real gap that must be fixed before the optimality claim can stand.","tokens_in":9717,"tokens_out":2041,"would_cite":false,"duration_ms":21039,"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":"A single model that builds and uses its neighborhood graph in the same pass reports higher semi-supervised accuracy than fixed-graph GCN and GAT.","keywords":["semi-supervised learning","graph convolutional networks","adaptive neighborhood graph","feature propagation","graph construction","node classification","label propagation"],"falsifier":"Run Algorithm 1 on a small random instance (for example $n=6$, $d=3$, $\\gamma=1$, $\\beta=0.3$, $\\alpha=0.5$), compute the $S$ produced by Eq. (9), and check whether every row sums to 1; if any row does not, the update does not satisfy the constraint of Eq. (8), so Eq. (9) as written is not the minimizer the paper claims.","tokens_in":8684,"feed_emoji":"📈","tokens_out":9243,"duration_ms":85447,"temperature":0.7,"pith_summary":"The paper proposes that a graph neural network should not take its neighborhood graph as a fixed input: it can learn the graph from pairwise distances at the same time that it propagates features, so that graph construction and convolution reinforce each other. It introduces the Adaptive Neighborhood Graph Propagation Network (ANGPN), built on an Adaptive Neighborhood Feature Propagation (ANFP) model, and reports that this joint learning yields higher semi-supervised classification accuracy than fixed-graph GCN, GAT, DGI, GraphSAGE, and classical label-propagation methods on SVHN, CIFAR, 20News, and CoraML, with gains of roughly one to three accuracy points. If the claim is right, it matters because most GCN variants fix the graph in advance, and for data without a natural graph (images, text) the graph is currently built in a separate stage that may be suboptimal for the learning task.","feed_headline":"Adaptive graph beats fixed-graph GCN by 1–3 points","feed_subtitle":"ANGPN learns the neighborhood graph while propagating features, improving semi-supervised classification on SVHN, CIFAR, 20News, and CoraML.","key_machinery":"The load-bearing object is the adaptive neighborhood graph $S \\in \\mathbb{R}^{n\\times n}$, a row-stochastic confidence matrix in which $S_{ij}$ says how likely node $j$ is a neighbor of node $i$. It is updated by the closed-form rule $S_{ij} = \\max\\{-(D^x-\\beta FF^T)_{ij}/(2\\gamma)+\\eta, 0\\}$ and then used to propagate features through $F = (\\alpha S + (1-\\alpha)I)H$; the objective above couples the two so that the graph is shaped by the current representation and the representation is shaped by the graph. This combined update, called Adaptive Neighborhood Feature Propagation (ANFP), is what lets one ANGPN layer construct and convolve a graph in the same step.","core_discovery":"Graph convolution in a GCN can be decomposed into feature propagation followed by a nonlinear transformation. Treating propagation as the equilibrium of an iterative update $F^{(t+1)} = \\alpha A F^{(t)} + (1-\\alpha)H$, the paper derives an equivalent optimization problem and then replaces the fixed adjacency $A$ with an adaptive row-stochastic graph $S$, coupling graph construction and feature propagation in a single objective: $\\min_{S,F} \\sum_{i,j} D^x_{ij} S_{ij} + \\gamma \\|S\\|_F^2 + \\beta \\operatorname{tr}(F^T(I-S)F) + \\mu \\|F-H\\|_F^2$ subject to $S \\mathbf{1} = \\mathbf{1}$, $S \\ge 0$. The central claim is that the $S$ learned this way is an optimal neighborhood graph for the convolution itself, and that alternating updates of $S$ and $F$ --- approximated in each layer by a one-step power iteration --- give consistently better semi-supervised classification than networks that use a fixed graph.","pith_inferences":["The learned $S$ is effectively a soft, distance-based attention map; fusing it with feature-based attention would be a natural next step that the paper does not explore.","Recomputing distances from propagated features at each layer, which the paper mentions only as an option, would let the graph track semantic shifts and is a directly testable variant.","The $O(n^2)$ distance matrix limits the method to moderate graph sizes; anchor-graph or block approximations of $S$ would be needed to scale the same idea to very large datasets."],"forward_implications":["If the central claim is right, image and text classification can skip the separate k-nearest-neighbor graph stage and still get higher accuracy, because the graph is shaped by the task itself.","The gains over GCN, GAT, DGI, and GraphSAGE persist across 10%, 20%, and 30% labeled rates, suggesting the improvement is structural and not a quirk of one split.","The comparison with NGPN, which constructs a graph first and then propagates with $\\beta=0$, indicates the cooperative $\\beta>0$ coupling is what drives the improvement.","Because the ANFP block only changes how the propagation matrix is obtained, it can be dropped into other GCN-style architectures that currently use a fixed adjacency."],"supporting_citations":[{"why":"Gives the closed-form adaptive-neighbor update used in Eq. (9).","marker":"[14]"},{"why":"Motivates incorporating graph learning into the unified objective.","marker":"[15]"},{"why":"Provides the GCN layer design, the fixed-graph baseline, and the one-step propagation approximation.","marker":"[7]"},{"why":"Is the adaptive-weighting baseline that ANGPN is compared with and aims to outperform.","marker":"[4]"},{"why":"Is the earlier unified graph-construction/convolution model that ANGPN extends.","marker":"[12]"},{"why":"Supplies the equivalent optimization view of feature propagation used to derive Eq. (4).","marker":"[10]"},{"why":"Motivates the iterative feature propagation scheme in Eq. (1).","marker":"[16]"}],"fun_headline_variants":["Adaptive graph beats fixed graph in GCN","Learn the graph while propagating features","One-step adaptive graph for semi-supervised GCN","Joint graph learning and convolution for GCN","GCN that tunes its own neighborhood graph"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the closed-form rule used to compute each row of the adaptive graph actually minimizes the stated constrained problem; because the rule's threshold uses only the original distances, the learned rows are not guaranteed to sum to one once the representation-dependent term $\\beta FF^T$ is included, and the optimality claim rests on that equation.","fun_headline_variants_meta":{"raw":{"variants":["Adaptive graph beats fixed graph in GCN","Learn the graph while propagating features","One-step adaptive graph for semi-supervised GCN","Joint graph learning and convolution for GCN","GCN that tunes its own neighborhood graph"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000306,"raw_usage":{"total_tokens":1763,"prompt_tokens":966,"completion_tokens":797,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":582,"completion_tokens_details":{"reasoning_tokens":730}},"tokens_in":582,"tokens_out":797,"duration_ms":8369,"temperature":1.0,"reasoning_tokens":730,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:21:44.302744+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 on a small random instance (for example $n=6$, $d=3$, $\\gamma=1$, $\\beta=0.3$, $\\alpha=0.5$), compute the $S$ produced by Eq. (9), and check whether every row sums to 1; if any row does not, the update does not satisfy the constraint of Eq. (8), so Eq. (9) as written is not the minimizer the paper claims.","supporting_citations":[{"cited_title":"Clustering and projected clustering with adaptive neighbors,","cited_arxiv_id":null,"evidence_quote":"Gives the closed-form adaptive-neighbor update used in Eq. (9)."},{"cited_title":"Unsupervised feature selecti on with struc- tured graph optimization,","cited_arxiv_id":null,"evidence_quote":"Motivates incorporating graph learning into the unified objective."},{"cited_title":"Data representati on and learning with graph diffusion-embedding networks,","cited_arxiv_id":null,"evidence_quote":"Supplies the equivalent optimization view of feature propagation used to derive Eq. (4)."},{"cited_title":"Label propagation through linear neigh- borhoods,","cited_arxiv_id":null,"evidence_quote":"Motivates the iterative feature propagation scheme in Eq. (1)."}],"review_version":1}