{"id":"2cf9dc7f-019a-4843-95f0-198df11bd9f0","arxiv_id":"2509.07625","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"An embedding-guided variable-length evolutionary algorithm for three-objective influence maximization is reported to beat NSGA-II variants, though its claimed NP-hardness proof and experimental details are missing.","lead":"This paper defines a three-goal version of influence maximization: maximize reach, minimize seed cost, and minimize propagation time, and proposes an evolutionary algorithm that uses graph embeddings to guide crossover between seed sets of different sizes. The authors report higher hypervolume than three NSGA-II variants on four real networks, but the advertised hardness proof is absent and key experimental settings are unstated.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 2's hypervolume superiority claim is not checkable: the protocol (seed costs, p_uv, delay distribution, MC count, HV reference point) is unspecified, and HV>1 in three objectives implies unstated normalization; the advertised NP-hardness proof is also absent.","rationale":"The reader's verdict is CONDITIONAL and I agree. The most load-bearing issue is not the missing proof but the missing experimental protocol, because the paper's headline is an empirical superiority claim. Without the cost model, diffusion probabilities, delay distribution, MC budget, and HV normalization, Table 2 is a black box; the 'up to 19.3%' margin is a number, not a reproducible result. The HV>1 detail makes the problem concrete: either the objectives are unnormalized and HV is scale-dependent, or a reference point is used that the paper does not disclose. Both make the comparison unverifiable. The missing NP-hardness proof is a separate, explicit defect—the Introduction promises it and Section 3 does not deliver—but it is addressable and does not determine whether EVEA works. The baselines are only NSGA-II variants, so 'all baselines' overstates the comparison against state-of-the-art MOIM methods, but that is a scope issue. Overall, conditional remains the right verdict: the algorithmic idea is plausible, the code is released, and the issues are fixable by documenting the protocol and adding/removing the proof.","tokens_in":11202,"tokens_out":5620,"duration_ms":64486,"concrete_test":"Run the public GitHub code (github.com/fmyzckj) on the Facebook network with a fully specified protocol: degree-proportional c_i, p_uv=1/deg(u), a stated P_lat (e.g., fixed δt=1), at least 1000 Monte Carlo runs for σ(S), and a stated HV reference point. Recompute Table 2's EVEA vs. NSGA-II+Mutation row. If the HV margin on Facebook differs from the reported ~7.7% by more than a few points or the Wilcoxon p is ≥0.05, the headline claim fails. Separately, ask authors to supply the Set Cover reduction for IM-ICT; if no valid reduction is produced, remove that contribution claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 5.1 describes the datasets and says 'all algorithms are run for 1000 generations, population size fixed,' but never states the parameters that determine the three objectives: how c_i in Eq. (5) are assigned, what p_uv in Eq. (4) are used, what distribution P_lat(δt) in Eq. (6) is sampled, how many Monte Carlo simulations estimate σ(S), or the reference point/normalization for the HV in Table 2. The HV values exceed 1.0 (e.g., 1.0920, 1.1659). For three objectives in [0,1]^3 with reference at the origin, HV≤1, so either the objectives are unnormalized or the reference point is chosen to inflate values; without that information, the reported 5–19% margins and Wilcoxon p-values are not reproducible. Because the central claim is 'EVEA outperforms all baselines,' this missing protocol is load-bearing: different plausible parameter choices can change the Pareto fronts and the winner. The paper also advertises in the Introduction 'we rigorously prove the proposed IM-ICT's NP-hardness via a polynomial-time reduction from the Set Cover problem,' but no such reduction appears anywhere in Section 3; this omission does not by itself falsify the empirical comparison but it is an explicit missing support.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes IM-ICT, a tri-objective influence maximization problem that simultaneously maximizes influence spread, minimizes seed cost, and minimizes propagation latency, and presents EVEA, an embedding-aligned variable-length evolutionary algorithm. The authors claim that IM-ICT is NP-hard via a reduction from Set Cover, and that EVEA outperforms three NSGA-II variants on four real-world networks, reporting higher hypervolume and faster convergence. The manuscript includes objective definitions, algorithm pseudocode, and experimental tables and figures. The central claims are that the new formulation is well motivated and that EVEA is empirically superior, but both are currently under-supported: the advertised NP-hardness proof is absent, and the experimental protocol is not specified enough to reproduce the reported hypervolume results.","tokens_in":11456,"tokens_out":3205,"duration_ms":38736,"significance":"If the stated results hold, the paper would make a useful contribution to multi-objective influence maximization by adding propagation time as a third objective and by demonstrating a variable-length EA with an embedding-based crossover. The source-code release is a positive element, as are the comparisons against three NSGA-II variants with Wilcoxon significance tests. However, the significance is presently limited by missing technical support: the NP-hardness proof is promised but not delivered, and several load-bearing experimental parameters (seed costs, propagation probabilities, delay distribution, Monte Carlo effort, hypervolume reference and normalization) are not stated. These gaps prevent the reader from validating the main empirical claim and reduce the paper's current value to that of an algorithm proposal with encouraging but incomplete evidence.","major_comments":[{"comment":"The Introduction and the contribution list state that the paper \"rigorously prove[s] the proposed IM-ICT's NP-hardness via a polynomial-time reduction from the Set Cover problem.\" Section 3, which is the designated complexity section, contains only the objective definitions and formulation (7); no theorem, reduction, or proof appears anywhere in the manuscript. Since NP-hardness is advertised as an original contribution, this is missing support. The authors should either provide the full reduction and proof or remove the claim.","section":"§1, §3.2; contribution 1"},{"comment":"The central empirical claim that EVEA outperforms all baselines is not reproducible from the information given. The values of c_i in Eq. (5), the edge probabilities p_uv in Eq. (4), the delay distribution P_lat(δt) in Eq. (6), the number of Monte Carlo simulations used to estimate σ(S), and the hypervolume reference point and normalization are all unspecified. For three objectives confined to [0,1] with the origin as reference, HV cannot exceed 1, yet Table 2 reports values from 1.0920 to 1.1659, implying normalization or a different reference that is not disclosed. These choices can change the Pareto fronts, the HV margins, and the Wilcoxon outcomes. The authors must report the full evaluation protocol.","section":"§5.1, §5.3, Eqs. (4)–(6), Table 2"},{"comment":"The three baseline variants of NSGA-II are not instantiated precisely enough for a fair comparison. The paper cites [35] and [36] for variable-length crossover and mutation, but does not specify how those operators are adapted to IM-ICT, what hyperparameters are used for all algorithms (population size, crossover/mutation rates, embedding settings for EVEA), how many independent runs are averaged, or what exact Wilcoxon procedure is used. These details are necessary to judge whether the reported 5–19% HV improvements are robust or artifacts of asymmetric settings.","section":"§5.1, §5.3"},{"comment":"The \"necessity\" of the IM-ICT formulation is argued by showing Pareto surfaces generated by EVEA on the four networks. This is not independent evidence that the three objectives conflict; it only shows that EVEA returns a spread of solutions under its own objective definitions. A stronger demonstration would compare against a set of random or heuristic seed sets, or show that no single solution dominates on all three objectives across a broader sampling of the search space. As written, the empirical motivation is partly circular because the solver that is being evaluated is also used to establish the problem's structure.","section":"§5.2"}],"minor_comments":[{"comment":"The text says \"four benchmark datasets - Facebook, GRQC, and Gnutella,\" but lists only three, while Table 1 and Table 2 include Wiki as the fourth. Additionally, the abstract mentions Twitter and DBLP, which do not appear in the experiments. These inconsistencies should be fixed.","section":"§5.1, Table 1"},{"comment":"Line 5 reads \"Q←Embedding−Aligned_Crossover(Q)\" but Q has not been initialized and the two parent arguments are not shown. The algorithm should pass the selected parents P_G (or a mating pool) explicitly to the crossover routine.","section":"§4.1, Algorithm 1"},{"comment":"The notation for propagation latency is ambiguous: δt_k is sampled from P_lat_u(δt), but the subscript u and the summation range d(v_i,v_j) are not defined clearly, and P_lat_u is never specified as a distribution over hops or nodes. The authors should define the delay model more rigorously.","section":"Eq. (6)"},{"comment":"The time-complexity analysis claims O(N^2) per generation but ignores the cost of evaluating σ(S), which typically requires many Monte Carlo simulations and dominates the runtime in IM problems. The complexity statement should clarify whether evaluation cost is included or excluded.","section":"§4.4"},{"comment":"Reference [27] is incomplete (\"Zhu et al.\" with no full author list or title), and several other references have informal annotations appended inside the bibliography. The reference list needs to be brought to journal style.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The two promised contributions are both currently under-supported: the NP-hardness proof is missing and the experimental protocol is under-specified. These are fixable with additional content, so I view major revision as appropriate rather than rejection. The paper is within scope for the journal, and the source-code release is a positive signal, but the reported numbers should not be accepted as stated until the protocol is fully documented."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The useful part of this paper is the embedding-aligned variable-length crossover. Aligning parent nodes by Node2Vec before recombination is a concrete, sensible tweak for variable-length MOEAs on graphs, and the authors back it with released code. The reported hypervolume table is internally consistent: EVEA beats three NSGA-II variants on all four networks, and the Wilcoxon markers are at least plausible. The convergence curves support the speed claim. That is a real, if modest, algorithmic contribution.\n\nThe soft spots are structural and mostly fixable. First, the experimental protocol is not reproducible from the text. The paper never states how seed costs c_i are assigned, which propagation probabilities p_uv are used, what delay distribution is sampled, how many Monte Carlo runs estimate sigma(S), or the hypervolume reference point and normalization. The HV values exceed 1.0 for three objectives, so some normalization is happening but unstated. Without those details, the 5–19% margins and the Wilcoxon outcomes cannot be independently checked. That is load-bearing, because the central claim is empirical superiority.\n\nSecond, the Introduction promises a rigorous NP-hardness proof via a reduction from Set Cover, but Section 3 contains no proof and no reduction. That is an explicit missing support, not a minor omission. Third, the novelty claim is overstated: the paper's own related work ([21], [23]) already optimizes spread along with budget, fairness, or time, so IM-ICT is a re-listing of known objectives rather than a new problem. The authors should either benchmark against those methods or soften the framing. Fourth, the baselines are limited to the NSGA-II family, so \"state-of-the-art\" and \"all baselines\" claims are not supported.\n\nI agree with the reader's conditional verdict. The algorithm is plausible and the reported comparison is internally consistent, but the missing protocol and absent proof prevent acceptance as-is. This is a paper for a serious referee: the core idea deserves testing, but only after the authors document the full setup, remove or supply the proof, and frame the novelty against their own citations. My recommendation: send it to peer review with a request for major revision, not a desk reject. A cautious reader could get real value from the embedding-aligned crossover once the evaluation is checkable.","headline":"EVEA is a plausible variable-length MOEA variant with a missing experimental protocol and an advertised NP-hardness proof that never appears; the core idea is worth testing once the paper is reproducible.","tokens_in":12054,"tokens_out":1013,"would_cite":false,"duration_ms":13280,"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 tri-objective influence maximization problem—maximizing spread while minimizing seed cost and propagation time—is NP-hard, and a variable-length evolutionary algorithm with embedding-aligned crossover finds better Pareto fronts than NSGA-","keywords":["Influence Maximization","Multi-objective Optimization","Evolutionary Algorithm","Variable-length representation","Graph embedding crossover","Propagation latency","Seed cost","NSGA-II"],"falsifier":"Run EVEA and the three NSGA-II variants on the same four SNAP networks with every setting fixed and published (for instance, costs proportional to degree, p_uv=0.1 for all edges, delays sampled from an exponential with mean one time step, 10,000 Monte Carlo simulations, and a common normalized reference point). If EVEA's hypervolume advantage over NSGA-II+Mutation does not pass the Wilcoxon significance threshold on the majority of networks, or its convergence curves do not lead by the claimed 25–40%, the central empirical claim fails.","tokens_in":10987,"feed_emoji":"📈","tokens_out":4505,"duration_ms":40743,"temperature":0.7,"pith_summary":"This paper introduces IM-ICT, a multi-objective influence maximization formulation that optimizes three conflicting goals at once: maximize the expected number of activated nodes, minimize the total cost of seed nodes, and minimize propagation time under a latency-aware independent cascade model. The authors argue, with a small worked example and Pareto-surface experiments on four networks, that these objectives genuinely conflict, so a single-objective or two-objective treatment misses real decisions. They prove IM-ICT is NP-hard by a polynomial-time reduction from Set Cover, and they propose EVEA, an evolutionary algorithm that lets seed sets grow or shrink during search and uses graph-embedding-based crossover to recombine parents of different lengths. On Facebook, GRQC, Gnutella, and Wiki networks, EVEA reports higher hypervolume (up to 19.3% over the best baseline) and faster convergence (25–40%), plus smoother Pareto fronts. If these results hold, the paper's main contribution is a tractable, expressive formulation and a practical search method for decisions that must weigh reach, budget, and urgency together.","feed_headline":"Better spread-cost-time trade-offs beat NSGA-II on four networks","feed_subtitle":"A variable-length evolutionary algorithm with embedding-aligned crossover also converges up to 40% faster.","key_machinery":"The load-bearing mechanism is the embedding-aligned crossover: it aligns nodes across two parent seed sets by minimal Euclidean distance in a Node2Vec embedding, then swaps aligned nodes with crossover probability pc, allowing recombination of seed sets of different sizes while keeping topologically similar nodes. This is supported by variable-length mutation (add, delete, replace) and NSGA-II-style non-dominated sorting with crowding distance for environmental selection. The objective functions themselves—expected spread, total seed cost, and longest activation path—are the formal objects the algorithm optimizes; the complexity argument is a polynomial reduction from Set Cover.","core_discovery":"The central claim is that influence maximization should be treated as a three-objective problem—influence spread, seed cost, and propagation time—and that this problem, while NP-hard, is practically solvable by a variable-length evolutionary algorithm. The authors define the objectives formally (expected spread under the IC model; sum of node costs; maximum activation time under a latency-aware IC model), prove NP-hardness via a reduction from Set Cover, and design EVEA, whose key mechanism is an embedding-aligned crossover that pairs nodes from two parents by Euclidean distance in Node2Vec embedding space and swaps them with probability pc. EVEA then applies add/delete/replace mutation so s","pith_inferences":["An editorially added caution: reproducing Table 2 requires choices the paper does not state—seed cost assignment, edge probabilities, delay sampling distribution, Monte Carlo simulation count, and the reference point or normalization behind hypervolume values near one. Different choices could change the margins.","The embedding-alignment idea could be tested on other variable-length combinatorial problems, such as team formation or feature selection, where parent solutions have different sizes and topological structure matters.","A natural extension implied by the paper's own future-work remark is coupling the time objective with node geography; the current model treats time as hop-based only."],"forward_implications":["Any campaign that must respect a budget and a deadline—marketing, vaccination, rumor containment—gets a Pareto front of seed sets rather than one fixed k, so decision makers can pick the point matching their budget and deadline.","Variable-length representation means seed-set cardinality is not chosen in advance; the search itself reveals which sizes are worth paying for.","If the convergence numbers hold, EVEA's embedding-aligned crossover is a generally usable operator for variable-length multi-objective search on graphs, not just IM-ICT.","The NP-hardness result formalizes that no polynomial exact algorithm is likely, so evolutionary and heuristic approaches are the relevant class of methods."],"supporting_citations":[{"why":"Defines the IC and LT diffusion models and the expected-spread objective that all three objectives build on.","marker":"[1]"},{"why":"Supplies the NSGA-II framework and non-dominated/crowding selection used as baseline and as environmental selection.","marker":"[31]"},{"why":"Provides Node2Vec embeddings that the crossover operator uses to align nodes across parents.","marker":"[32]"},{"why":"Is the SNAP source of the four networks used in the experiments.","marker":"[34]"},{"why":"Defines the variable-length crossover baseline NSGA-II+Crossover that EVEA must beat.","marker":"[35]"},{"why":"Defines the variable-length mutation baseline NSGA-II+Mutation, the strongest reported competitor.","marker":"[36]"}],"fun_headline_variants":["Influence, cost, time: EVEA beats NSGA-II on four networks","EVEA: 19% better hypervolume, 40% faster for multi-objective IM","Three objectives, one algorithm: EVEA outdoes NSGA-II in IM","Joint influence, cost, time optimization: EVEA leads","EVEA wins on influence-cost-time trade-offs, converges 40% faster"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The empirical superiority claim rests on experimental settings that are not fully specified in the paper—costs, propagation probabilities, delay distributions, Monte Carlo effort, and hypervolume normalization—so the reported margins are not yet independently reproducible.","fun_headline_variants_meta":{"raw":{"variants":["Influence, cost, time: EVEA beats NSGA-II on four networks","EVEA: 19% better hypervolume, 40% faster for multi-objective IM","Three objectives, one algorithm: EVEA outdoes NSGA-II in IM","Joint influence, cost, time optimization: EVEA leads","EVEA wins on influence-cost-time trade-offs, converges 40% faster"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000958,"raw_usage":{"total_tokens":3892,"prompt_tokens":688,"completion_tokens":3204,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":432,"completion_tokens_details":{"reasoning_tokens":3102}},"tokens_in":432,"tokens_out":3204,"duration_ms":21499,"temperature":1.0,"reasoning_tokens":3102,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T21:57:09.723644+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run EVEA and the three NSGA-II variants on the same four SNAP networks with every setting fixed and published (for instance, costs proportional to degree, p_uv=0.1 for all edges, delays sampled from an exponential with mean one time step, 10,000 Monte Carlo simulations, and a common normalized reference point). If EVEA's hypervolume advantage over NSGA-II+Mutation does not pass the Wilcoxon significance threshold on the majority of networks, or its convergence curves do not lead by the claimed 25–40%, the central empirical claim fails.","supporting_citations":[{"cited_title":"Maximizing the spread of influence through a so- cial network","cited_arxiv_id":null,"evidence_quote":"Defines the IC and LT diffusion models and the expected-spread objective that all three objectives build on."},{"cited_title":"A fast and elitist multiob- jective genetic algorithm: Nsga-ii.IEEE transac- tions on evolutionary computation, 6(2):182–197, 2002","cited_arxiv_id":null,"evidence_quote":"Supplies the NSGA-II framework and non-dominated/crowding selection used as baseline and as environmental selection."},{"cited_title":"node2vec: Scalable feature learning for networks","cited_arxiv_id":null,"evidence_quote":"Provides Node2Vec embeddings that the crossover operator uses to align nodes across parents."},{"cited_title":"Snap: A general- purpose network analysis and graph-mining li- brary.ACM Transactions on Intelligent Systems and Technology (TIST), 8(1):1–20, 2016","cited_arxiv_id":null,"evidence_quote":"Is the SNAP source of the four networks used in the experiments."},{"cited_title":"An improved clustering based multi-objective evolutionary algorithm for influ- ence maximization under variable-length solu- tions.Knowledge-Based Systems, 256:109856, 2022","cited_arxiv_id":null,"evidence_quote":"Defines the variable-length crossover baseline NSGA-II+Crossover that EVEA must beat."},{"cited_title":"Influ- ence maximization in hypergraphs using multi- objective evolutionary algorithms","cited_arxiv_id":null,"evidence_quote":"Defines the variable-length mutation baseline NSGA-II+Mutation, the strongest reported competitor."}],"review_version":1}