{"id":"2b226b1b-cf55-43ba-b35e-12fc3acf6821","arxiv_id":"2411.14094","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"GNN-MultiFix combines graph features, propagated training labels, and DeepWalk position embeddings to improve multi-label node classification.","lead":"This paper studies multi-label node classification, where each node can have several labels, and reports that standard graph neural networks often lose to a simple neighbor-vote baseline. It proposes GNN-MultiFix, a model that feeds node features, propagated training labels, and position embeddings into one classifier.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 'all multi-label datasets' claim is contradicted by the paper's own Tables 3 and 4 on Yelp and Synthetic2 (homophily=1.0).","rationale":"I read the paper's central claim as two-part: empirical improvement over baselines across all multi-label datasets, and theoretical expressiveness increase. The most load-bearing issue is the empirical claim because it is the abstract's headline and is directly falsified by the paper's own tables. The reader correctly noted this in the rationale but placed the weakest assumption on the positional module; I partially agree with that emphasis. The theoretical proof is also a sketch, but because the method's value is primarily empirical, the overclaim is the more damaging concern. A straightforward rerun settles it, so the conditional verdict remains appropriate rather than a rejection.","tokens_in":18242,"tokens_out":5166,"duration_ms":49299,"concrete_test":"Run the released code with the hyperparameters in Table 8 on Yelp and on Synthetic2 (rhomo=1.0), and compare each GNN-MultiFix variant against GraphSage and MajorityVote using per-split Average Precision with correctly computed error bars. If GNN-MultiFix still fails to beat GraphSage on Yelp and MajorityVote at rhomo=1.0, the abstract should be revised from 'all multi-label datasets' to 'most evaluated settings' and the significance claim should be removed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central empirical claim in the abstract, that GNN-MultiFix demonstrates significant improvement across all multi-label datasets, is contradicted by the paper's own reported results. In Table 3, on Yelp, the best baseline GraphSage achieves 0.251 Average Precision, while GNN-MultiFix-Linear, MLP1, and MLP3 achieve 0.200, 0.217, and 0.238 respectively; none of the three variants outperforms GraphSage. In Table 4 (and Table 11), on Synthetic2 at label homophily 1.0, MajorityVote achieves 0.847, while the best GNN-MultiFix variant (MLP1) achieves 0.832. The ablation in Table 6 further shows that on DBLP the full model (0.935) is not better than removing the positional module (0.934), so the benefit is dataset-dependent. The 'all datasets' claim is load-bearing because it is the headline contribution; if it does not hold on two of the evaluated settings, the paper's conclusions must be qualified. Additionally, the reported standard deviations in Table 9 are internally inconsistent (e.g., Mlp on BlogCat: 0.043 ± 0.63, impossible for Average Precision bounded in [0,1]), so the 'significant' part of the claim cannot currently be assessed statistically.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-label node classification in the transductive setting. It argues that standard GNNs underperform simple label-only baselines such as MajorityVote, and it analyzes per-node training losses on BlogCat and DBLP to support the claim that GNNs fail to learn on multi-label data. The main proposal, GNN-MultiFix, combines three input modules: feature propagation, label propagation, and positional (DeepWalk) embeddings, and the paper proves a theoretical expressiveness result relative to the base GNN. Experiments on four real-world datasets and two synthetic families compare three GNN-MultiFix variants against twelve baselines and include an ablation study.","tokens_in":18601,"tokens_out":4331,"duration_ms":42726,"significance":"If substantiated, the paper would fill a real gap: multi-label node classification is understudied relative to multi-class classification, and the observation that simple MajorityVote beats many GNN designs is practically relevant. The proposed three-module architecture is simple and the code release is a positive contribution. However, the headline claim of improvement across all datasets is contradicted by the paper's own reported numbers, and the reported standard deviations are internally inconsistent, so the statistical significance claim cannot currently be assessed. The theoretical expressiveness result is also not matched by the implemented positional module. The central idea is defensible, but the current evidence requires substantial qualification.","major_comments":[{"comment":"The abstract and conclusion claim that GNN-MultiFix achieves significant improvement across all multi-label datasets, but the paper's own results contradict this. In Table 3, on Yelp, GraphSage achieves Average Precision 0.251 while the best GNN-MultiFix variant (MLP3) achieves 0.238. In Table 4, on Synthetic2 with label homophily 1.0, MajorityVote achieves 0.847 while the best GNN-MultiFix variant (MLP1) achieves 0.832, and at homophily 0.2, Mlp achieves 0.362 while the best GNN-MultiFix variant achieves 0.288. The claim should be qualified to 'most settings' and the text in Section 6.2 ('our model and its variants demonstrate significant enhancements') should be aligned with these counterexamples.","section":"Abstract, Section 6, Conclusion; Tables 3 and 4"},{"comment":"The reported standard deviations are incompatible with Average Precision being bounded in [0,1]. For example, Table 9 reports Mlp on BlogCat as 0.043 ± 0.63, DeepWalk on PCG as 0.229 ± 1.00, and GCN-LPA on DBLP as 0.801 ± 1.24; Table 10 reports DeepWalk as 0.181 ± 0.71; Table 11 reports DeepWalk as 0.813 ± 0.95. Since the word 'significant' is load-bearing, the authors must either correct the variability measures or provide proper significance tests. As written, the statistical evidence cannot be evaluated.","section":"Appendix A.2.4, Tables 9-11"},{"comment":"The theoretical expressiveness claim is only partially supported by the implemented method. Lemma 1 shows that, by feeding true training labels as input (Eq. 2), the label representation becomes a weighted sum of neighbor labels; this is an expressiveness gain by construction, not a property of the GNN architecture itself. Theorem 1 then claims that isomorphic test nodes can be distinguished using positional representations, but the implemented module uses DeepWalk embeddings, which are not guaranteed to assign different vectors to nodes with isomorphic computational graphs; in symmetric graphs two such nodes may have identical random-walk statistics. The proof should either state conditions under which the implemented Φv separates such nodes or restrict the claim to the theoretical instantiation (e.g., Katz similarity) and verify that the implementation satisfies those conditions.","section":"Section 4.2, Lemma 1 and Theorem 1; Section 4.1.3"},{"comment":"The claim that GNNs 'fail to learn' on multi-label data is based on visual inspection of box plots of per-node training losses without quantitative thresholds, convergence criteria, or comparison across seeds. As presented, this is not a falsifiable empirical analysis. The authors should add quantitative evidence, such as the fraction of nodes whose loss remains above a defined threshold at convergence, to support the failure-to-learn claim.","section":"Section 3 and Figures 3-4"}],"minor_comments":[{"comment":"The baseline enumeration uses 'iiii' for the fourth group; the numbering should be corrected to a consistent scheme.","section":"Section 5, Baselines list"},{"comment":"The caption contains the typo 'numebr' instead of 'number'.","section":"Table 7 caption"},{"comment":"Table 3 and Table 9 report slightly different values for the same method on Yelp, e.g., GNN-MultiFix-Linear 0.200 vs 0.201 and GNN-MultiFix-MLP3 0.238 vs 0.237; the authors should ensure the two tables are fully consistent or explain the source of the discrepancy.","section":"Tables 3 and 9"},{"comment":"The positional encoding loss is described only abstractly via the functions I and f; the text should specify the concrete objective used in the implementation, for example the exact SkipGram negative-sampling formulation, so that the method is reproducible from the paper alone.","section":"Section 4.1.3, Eq. (4)"},{"comment":"On BlogCat, the full GNN-MultiFix-Linear achieves exactly the same score (0.225) as the variant without the feature module; the text says removing the feature module has 'little effect,' but the exact equality deserves explicit discussion.","section":"Section 7, Table 6"},{"comment":"The use of true training labels as input to the label representation module should be discussed explicitly as a potential source of train/test distribution shift, especially for datasets with very few labels per node, since this choice is central to the method's design.","section":"Section 4.1.2, Eq. (2)"}],"recommendation":"major_revision","confidential_remarks":"The paper addresses an understudied problem and the code release is a positive feature. The central claims, however, are currently overstated relative to the reported experimental results, and the statistical reporting needs correction. The theoretical analysis, while suggestive, is not yet aligned with the implemented positional module. With a careful revision that qualifies the claims and fixes the statistics, the paper could be suitable for publication. I do not see grounds for rejection, since the underlying approach is plausible and the issues appear fixable within the manuscript's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look, but its headline claim does not survive contact with its own tables. GNN-MultiFix combines feature aggregation, a no-reset label propagation, and DeepWalk positional embeddings for multi-label node classification. That is a reasonable modular recipe, and the training-dynamics story is a useful prompt: on BlogCat and DBLP, standard GNNs leave a long tail of high-loss nodes, and a simple MajorityVote baseline beats many learned models. That is a genuinely interesting observation.\n\nThe soft spots are load-bearing. The abstract promises \"significant improvement across all the multi-label datasets,\" which is false on the numbers the paper reports: on Yelp, GraphSage gets 0.251 Average Precision while the best GNN-MultiFix variant gets 0.238; on PCG, GNN-LSPE gets 0.528 versus GNN-MultiFix's best 0.254. The paper's own text acknowledges some of these failures (e.g., Mlp winning on low-homophily synthetic), but the abstract and conclusion do not. Also, the reported standard deviations are impossible for AP bounded in [0,1] — e.g., Mlp on BlogCat: 0.043 ± 0.63 — so the \"significant\" part of the claim is unsupported statistically.\n\nThe theory is a sketch. Theorem 1 says the method is strictly more expressive than the base GNN because labels or positional information break ties. That is plausible, but the proof's second case assumes a positional representation like Katz factorization, while the implementation uses DeepWalk embeddings, which carry no such guarantee. The \"expressiveness\" gain comes mostly from feeding true training labels into the network as input, so the comparison against baselines that do not use labels as features is not apples-to-apples. The paper cites Sato's label-as-features work but never runs that baseline.\n\nWhat is genuinely useful: the ablation shows module importance shifts with dataset characteristics (positional module is critical on BlogCat, label module on DBLP), and the framework allows swapping the base GNN. That is a solid engineering contribution, if the claims are reined in.\n\nRecommendation: send to review, but only with a clear request to fix the abstract, add label-as-features baselines, and repair the error reporting. A serious referee will find the core problem and the modular method worth engaging; the current form overpromises.\n\nI'd bring it to reading group as a cautionary example of claim/report mismatch.","headline":"Useful modular method and a real empirical observation, but the 'improves all datasets' claim is contradicted by the paper's own tables and the error reporting is impossible; needs revision before acceptance.","tokens_in":19028,"tokens_out":3851,"would_cite":false,"duration_ms":34564,"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":"GNN-MultiFix claims that multi-label node classification needs features, labels, and positions together, not just neighborhood aggregation, and that the combination makes any base GNN strictly more expressive.","keywords":["multi-label node classification","graph neural networks","label propagation","positional encoding","transductive learning","graph isomorphism expressivity","node classification","DeepWalk embeddings"],"falsifier":"Construct or find a multi-label graph family in which label assignment is independent of node positions—for example, two identically structured clusters with identical local neighborhoods but labels assigned independently of position—then compare GNN-MultiFix with and without the positional module. If removing the positional module does not change average precision, the claim that positional encoding is the mechanism behind the reported gains would be falsified.","tokens_in":17987,"feed_emoji":"🕸️","tokens_out":4800,"duration_ms":45592,"temperature":0.7,"pith_summary":"Graph neural networks are usually judged on multi-class benchmarks or isomorphism tests, but the paper argues that this misses the harder, realistic case of multi-label node classification, where each node can carry several labels. It shows experimentally that standard GNNs underfit multi-label data even with abundant labeled nodes, and that a simple majority vote over labeled neighbors often beats them. The paper then claims that even the most expressive GNN, in the graph-isomorphism sense, cannot separate two nodes with identical local structure but different labels when node attributes are absent and labels are not fed in. To fix this, it proposes GNN-MultiFix, which combines three independent node representations—features, propagated labels, and a positional embedding—and proves that the combination is strictly more expressive than the base GNN. On four real-world and two synthetic multi-label datasets, every version of the method improves over all baselines.","feed_headline":"Three-way input beats GNNs on multi-label nodes","feed_subtitle":"Feature, label, and position modules outperform even high-expressive GNNs on all tested multi-label datasets.","key_machinery":"The load-bearing object is the three-module representation $\\mathbf{h}_v = \\mathrm{COMB}(\\mathbf{h}^{(K)}_{f_v}, \\mathbf{h}^{(N)}_{\\ell_v}, \\Phi_v)$: a feature module that aggregates one-hop neighborhoods with a GCN-style rule; a label module that initializes training nodes with true label vectors and test nodes with padding, then propagates for $N$ layers using the same weighted aggregation without the reset step that classical label propagation uses; and a positional module that embeds nodes by DeepWalk's random-walk co-occurrence, whose loss $\\mathcal{L}(u,v) = (1 - I(u,v))\\, f(\\Phi_u, \\Phi_v)$ pushes far-apart nodes apart. The proof that GNN-MultiFix strictly exceeds the base GNN's expressivity runs through Lemma 1: with a uniform random-walk transition matrix $P$, $N$ label-propagation steps give $\\mathbf{h}_{\\ell_v} = \\sum_w P^N_{vw} \\mathbf{y}_w$, so the label module encodes the label distribution of each node's $N$-hop training neighborhood; isomorphic nodes with different such distributions, or with different positions when the neighborhoods are unlabeled, become distinguishable.","core_discovery":"On its own terms, the paper establishes two failures: GNNs do not learn reliably from multi-label graphs—training dynamics show many atypical nodes whose losses stay high even when the mean training loss converges—and expressive power measured by graph isomorphism does not translate into distinguishing power for node labels, because two nodes with isomorphic computational graphs can sit in different parts of the network and have different labels. The proposed solution is to stop treating node labels as supervision only and instead feed three signals into the classifier: a standard GNN feature representation, a label representation obtained by propagating known labels through the graph without resetting training nodes to their true labels, and a positional representation from short random walks. Theorem 1 states that every node the base GNN can separate, GNN-MultiFix can also separate, and some nodes the base GNN conflates are separated by the label or position module. The abstract's empirical claim is that this yields significant improvement across all multi-label datasets tested.","pith_inferences":["A consequence the paper leaves implicit is that on featureless, low-homophily graphs the positional module carries almost the entire task; on any graph family where short random walks do not track label similarity, that module would likely stop helping and could hurt.","The strict expressivity proof holds for the general framework, but the implemented positional module uses learned DeepWalk embeddings rather than a deterministic position encoding, so the theorem's guarantee does not automatically apply to the exact configuration evaluated; swapping in a deterministic distance-based encoding would make the theory match the experiment.","The synthetic results where MajorityVote nearly solves the task suggest that some existing multi-label benchmarks are dominated by local label structure, so gains on those datasets should be read as gains on the hard core beyond what neighbor labels already reveal."],"forward_implications":["If the central claim holds, a simple majority-vote baseline should become a standard comparison for any future GNN work on multi-label node classification, since it outperforms most existing GNNs on several real datasets.","GNN-MultiFix can be built on top of any base GNN as its feature module, so the expressivity gain transfers; the method is a plug-in rather than a replacement architecture.","The label propagation module's number of layers $N$ controls how far label influence reaches, which matters when labels are shared locally despite low overall homophily.","The positional module's random-walk co-occurrence provides a position signal complementary to both features and labels, and performance persists even when node features are entirely absent, as on BlogCat.","On the synthetic homophily sweep, the method nearly matches the majority-vote ceiling at high homophily while beating all other baselines, suggesting the gains are not just from exploiting trivial local label agreement."],"supporting_citations":[{"why":"Supplies the multi-label datasets, the label-homophily measure, and the observation that higher-order neighborhood exploitation is insufficient for multi-label node classification.","marker":"[34]"},{"why":"Provides the GCN architecture used as the default feature representation module and as one of the main baselines.","marker":"[10]"},{"why":"GCN-LPA is the baseline that previously unified label propagation with GNNs; the label module is contrasted with its weight-adjustment approach.","marker":"[26]"},{"why":"GNN-LSPE is the main positional-encoding baseline, since it augments input features with structural and positional representations.","marker":"[6]"},{"why":"DeepWalk is the implementation used for the positional embedding module and is also a standalone baseline.","marker":"[14]"},{"why":"Cited in the proof as a way to obtain positional representations by factorizing a node similarity matrix, such as Katz similarity, for distinguishing isomorphic nodes.","marker":"[13]"},{"why":"ID-GNN-F ast is the identity-aware baseline that injects positional information into input features.","marker":"[31]"},{"why":"LANC is the label-informed baseline designed for multi-label node classification and is the strongest such competitor in the experiments.","marker":"[36]"},{"why":"H2Gcn is the heterophily-robust baseline used to show that designs for low-homophily multi-class graphs still fail on multi-label data.","marker":"[37]"}],"fun_headline_variants":["Triple-signal fix outperforms GNNs on multi-label graph nodes","GNNs fail on multi-label nodes; feature, label, and position fix","Three inputs—feature, label, position—beat GNNs on multi-label nodes","Multi-label node classification fixed by gnn plus label and position info","GNNs stumble on multi-label nodes; triple input gets them right"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The method leans on the assumption that how close two nodes are in the graph, measured by short random walks, tracks how similar their labels are; if that fails for a graph family, the positional module that drives the reported gains stops working.","fun_headline_variants_meta":{"raw":{"variants":["Triple-signal fix outperforms GNNs on multi-label graph nodes","GNNs fail on multi-label nodes; feature, label, and position fix","Three inputs—feature, label, position—beat GNNs on multi-label nodes","Multi-label node classification fixed by gnn plus label and position info","GNNs stumble on multi-label nodes; triple input gets them right"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000492,"raw_usage":{"total_tokens":2430,"prompt_tokens":967,"completion_tokens":1463,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":583,"completion_tokens_details":{"reasoning_tokens":1362}},"tokens_in":583,"tokens_out":1463,"duration_ms":11463,"temperature":1.0,"reasoning_tokens":1362,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:32:28.268145+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct or find a multi-label graph family in which label assignment is independent of node positions—for example, two identically structured clusters with identical local neighborhoods but labels assigned independently of position—then compare GNN-MultiFix with and without the positional module. If removing the positional module does not change average precision, the claim that positional encoding is the mechanism behind the reported gains would be falsified.","supporting_citations":[{"cited_title":"Multi-label node classification on graph-structured data.Transactions on Machine Learn- ing Research, 2023","cited_arxiv_id":null,"evidence_quote":"Supplies the multi-label datasets, the label-homophily measure, and the observation that higher-order neighborhood exploitation is insufficient for multi-label node classification."},{"cited_title":"Graph neural networks with learnable structural and positional representations","cited_arxiv_id":null,"evidence_quote":"GNN-LSPE is the main positional-encoding baseline, since it augments input features with structural and positional representations."},{"cited_title":"Deepwalk: Online learning of social representations","cited_arxiv_id":null,"evidence_quote":"DeepWalk is the implementation used for the positional embedding module and is also a standalone baseline."},{"cited_title":"Asymmetric transitivity preserving graph embedding","cited_arxiv_id":null,"evidence_quote":"Cited in the proof as a way to obtain positional representations by factorizing a node similarity matrix, such as Katz similarity, for distinguishing isomorphic nodes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"LANC is the label-informed baseline designed for multi-label node classification and is the strongest such competitor in the experiments."},{"cited_title":"Beyond homophily in graph neural networks: Current limitations and effective designs","cited_arxiv_id":null,"evidence_quote":"H2Gcn is the heterophily-robust baseline used to show that designs for low-homophily multi-class graphs still fail on multi-label data."}],"review_version":1}