{"id":"78ff284a-b57a-4f9e-a7c3-261612d5b502","arxiv_id":"2501.12571","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"ML-guided graph exploration discovers hidden social network nodes with query costs only 1.2x (10% recall) to 1.4x (90% recall) of the known-topology baseline.","lead":"Researchers tested machine-learning strategies that find hidden users (bots, isolated people, influencers) in social networks whose full structure is unknown. They report that these strategies reach hidden users with at most 1.2 to 1.4 times as many queries as when the whole network is visible.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1.2x/1.4x 'at most' claim is not tied to a specific strategy and is contradicted by the reported DeepGL results in Enron-Periphery; no error bars support the worst-case wording.","rationale":"The reader's weakest assumption (realistic query model) is a valid external-validity concern, but the most load-bearing issue for the paper's central claim is internal: the numbers are not tied to a well-defined strategy and appear to be violated by one of the paper's own methods. If 'ML-based strategies' means all of DeepGL, base, and bandit, the Enron-Periphery DeepGL result contradicts it. If it means only the bandit, the abstract and conclusion are misleading. Either way, a reader cannot verify the 'at most' bound without per-trial data. The proposed test directly recomputes the maximum and resolves the ambiguity. The paper is otherwise carefully written: the extension to three hidden-node tasks is a genuine contribution, the bandit ensemble is sensible, and the retraining analysis is useful. The limitation section honestly notes pseudo-labels and the need for field studies, a separate point that supports the reader's CONDITIONAL verdict but does not replace the internal consistency check.","tokens_in":20368,"tokens_out":10940,"duration_ms":111361,"concrete_test":"Using the released GitHub code and data, recompute the per-trial normalized query cost for each strategy (DeepGL, base, bandit) at target fractions p=0.1 and p=0.9 (p=0.5 for Twitter) for every task-graph setting. Report the maximum over trials and settings for each strategy separately. Then check: (i) does any ML strategy exceed 1.2 at p=0.1 or 1.4 at p=0.9? (ii) if only the bandit (or best-per-setting model) stays within these bounds, does the abstract/conclusion need to name that strategy and add error bars? (iii) are the per-trial variances small enough to support an 'at most' statement? This single reanalysis will settle whether the headline quantitative claim is accurate as stated or must be qualified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract and conclusion assert a universal bound: 'when using ML-based strategies, the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4.' This claim is ambiguous and, under a literal reading, contradicted by the paper's own figures. In the Enron-Periphery setting, the DeepGL strategy is reported as 'very poor' and the y-axis of Figure 5 for that panel extends to 2.0, meaning normalized query cost at the 90% target fraction can exceed 1.4. Thus the 1.2/1.4 bounds cannot apply to all ML strategies; they must refer to the best-performing strategy per setting (often the bandit), but the paper never states this restriction. Moreover, the normalized query cost is presented as a single average over 10 (or 3) trials with no error bars or confidence intervals, so 'at most' is an unsupported worst-case phrasing, not a statistically grounded bound. The known-topology baseline is itself an ML model trained only on queried labels, so the multipliers are relative to that model, not to an omniscient oracle. The checklist states error bars are reported, but Figures 3, 5, and 6 show only point averages, an internal inconsistency.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the problem of discovering hidden nodes (Sybil nodes, peripheral nodes, and influencers) in unknown social networks. The authors formulate three target-node discovery tasks, propose an ML-guided graph exploration framework in which querying a node reveals its label and its neighbors, and evaluate several strategies: LightGBM classifiers with basic features, with additional DeepGL node embeddings, simple heuristics (MOD, TN), a known-topology ML baseline, and a D3TS bandit that combines classifiers. Experiments on Facebook, Enron, Epinion, and Twitter Japan datasets compare the fraction of discovered targets against the fraction of queried nodes and report normalized query costs relative to the known-topology baseline. The abstract and conclusion claim that ML-based strategies discover 10% of hidden nodes at a query cost at most 1.2 times the known-topology cost, and 90% at most 1.4 times, and that a bandit-based combination achieves efficient discovery across settings.","tokens_in":20629,"tokens_out":6119,"duration_ms":56868,"significance":"If the empirical results hold, the paper provides a useful demonstration that ML-based graph exploration can discover hidden nodes nearly as efficiently as when the full graph topology is known, across three qualitatively different target definitions (clustered Sybils, sparse peripheral nodes, and central influencers). The paper also contributes a cautionary finding that node embeddings are helpful in some settings but harmful in others, and that a simple bandit ensemble of two classifiers is a robust unified strategy. Strengths include the use of multiple real social graphs, release of source code on GitHub, explicit documentation of the query model, and a candid limitations section. The main reservations concern the precision and statistical support for the headline 1.2x/1.4x claim, which is a central contribution of the paper.","major_comments":[{"comment":"The claim that 'the query cost of discovering 10% of the hidden nodes is at most only 1.2 times that when the topology is known, and the query-cost multiplier for discovering 90% of the hidden nodes is at most only 1.4' is not tied to a specific strategy and is not supported by the reported results as stated. In the Results section, the DeepGL strategy in the Enron-Periphery setting is described as 'very poor' (subsection 'Ensemble of Multiple Classifiers is a Robust Strategy'), and Figure 5 shows that this strategy's normalized query cost at the 0.9 discovery fraction can be well above 1.4. If the claim refers to the best-performing ML strategy per setting (often the bandit), that restriction must be stated explicitly and the multiplier should be derived from the plotted data with error bars; if it refers to all ML-based strategies, it is contradicted by the paper's own evidence. The current wording in the abstract and conclusion is therefore ambiguous and overbroad.","section":"Abstract and Conclusion"},{"comment":"The checklist states 'Yes' for 'Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?' but none of the figures (Figures 3, 5, 6, 7, or 8) include error bars, confidence intervals, or standard deviations. The Parameter Settings section explains that results are averages over 10 trials (3 for Twitter), but no measure of variance is provided. This is an internal inconsistency in the manuscript and it materially affects the 'at most' phrasing of the central numerical claim: without variance estimates, a worst-case bound of 1.2/1.4 cannot be justified.","section":"Paper Checklist, item 4(c) and Parameter Settings"},{"comment":"The known-topology baseline used to normalize query costs is itself a LightGBM model trained on the queried labels, not an omniscient oracle or the true optimal discovery process. The paper does state that this baseline is considered 'the upper bound of practical efficiency,' which is reasonable, but the abstract and conclusion phrase the result as 'comparable to that when the graph structure is known,' which may be misread as comparing to full knowledge of labels and structure. The authors should clarify in the abstract and conclusion that the comparison is against an ML model with access to the full topology, and that the multipliers are relative to that model.","section":"Methodology, 'Strategies for Discovering Hidden Target Nodes'"}],"minor_comments":[{"comment":"There is a missing space in 'adouble-edged sword'; the intended phrase is 'a double-edged sword.'","section":"Abstract"},{"comment":"The D3TS bandit parameters are said to be 'identical to those in the literature' (Murai et al. 2018), but the actual values of alpha, beta, and C are not specified in the manuscript. Please provide these values in the text or a table for reproducibility.","section":"Parameter Settings"},{"comment":"The selection of which known-topology result (DeepGL or base) to plot is described only in the text ('only the results from the more efficient one are presented'), but not in the figure caption itself. This post-hoc selection should be flagged prominently in the caption, as it affects the interpretation of the comparison.","section":"Results, Figure 3 caption"},{"comment":"The textual axis descriptions in the figures are ambiguous: some panels show '0 1' and others '0.0 0.5 1.0', and it is unclear whether the y-axis maximum differs across panels. Please redraw the figures with consistent, clearly labeled scales and include error bars or at least state the variance in the caption.","section":"Results, Figures 5 and 6"},{"comment":"The query model assumes that querying a node returns its true label and its complete adjacency list. This is an idealization of real social-media APIs and respondent-driven sampling, where labels may be noisy and neighbor lists incomplete. The Limitations section acknowledges the need for field experiments, but the abstract's practical wording ('discover hidden nodes with an efficiency comparable to that when the graph structure is known') would benefit from a caveat reflecting this assumption.","section":"Introduction and Limitations"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid empirical study with a clear problem formulation and a useful bandit-based combination strategy. The main issue is the headline quantitative claim (1.2x/1.4x), which is currently phrased as a universal statement over ML strategies but is not supported by the reported averages without error bars and without a precise definition of which strategy the bound applies to. The checklist inconsistency regarding error bars is also concerning and should be fixed before publication. The paper is squarely within the scope of the venue and, with the claims reworded and variance reported, would be a reasonable contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a competent empirical extension of the Murai et al. exploration framework to three hidden-node tasks where the assumption that targets cluster together fails. The bandit ensemble of classifiers is the most useful practical result: it gets near-best performance across settings without knowing which features will work. That is worth publishing.\n\nThe genuinely new content is the task formulations. Peripheral-node discovery and influencer discovery are not trivial extensions; they break the homophily assumption that made earlier target discovery work. The finding that ML-based exploration still nearly matches known-topology efficiency for these harder cases is real and non-obvious. The observation that DeepGL embeddings help for influencers but hurt for peripheral nodes is also honest and interesting.\n\nThe soft spots are in the presentation of the main quantitative claim. The abstract and conclusion say query cost is at most 1.2x (10%) and 1.4x (90%) when using ML-based strategies. That is not tied to a single strategy. Their own Figure 5 shows DeepGL in Enron-Periphery is 'very poor' and the panel's y-axis goes to 2.0, so that strategy's normalized cost at the 90% target fraction can exceed 1.4. The bound must be for the bandit or the best model, and the paper never states that restriction. Also, the checklist says error bars are reported, but the figures show point averages. That internal inconsistency matters because 'at most' is a worst-case claim that needs variance to be credible.\n\nThe query model is optimistic: it assumes querying a node reveals the true label and the full adjacency list. Real RDS and social media APIs have noisy labels, rate limits, and partial or sampled neighbor lists. The authors acknowledge pseudo-labels and the need for field experiments, but they do not discuss how the clean query model might weaken the transfer.\n\nThat said, the experiments are clearly specified, span four networks and three target types, and the disclosure that only the better known-topology model is shown is a conservative choice. No circularity or hidden fitting in the bandit; it learns from realized rewards, which is the stated objective.\n\nThis paper deserves a serious referee. I would send it out, but with a strong request to restate the bound, add error bars, and address robustness under partial neighbor revelation. The core empirical result is likely real; the headline overclaims it.\n\nYes, bring it to the reading group.","headline":"A solid empirical extension with a useful bandit result, but the 1.2x/1.4x claim is overbroad and unsupported by error bars.","tokens_in":21194,"tokens_out":3081,"would_cite":true,"duration_ms":30691,"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":"The paper claims that machine-learning-guided graph exploration finds hidden nodes in unknown social networks nearly as efficiently as when the full topology is known, with query cost at most 1.2x at 10% discovery and 1.4x at 90%.","keywords":["hidden node discovery","graph exploration","unknown social networks","node embeddings","bandit algorithms","Sybil detection","peripheral nodes","influencer discovery"],"falsifier":"Re-run the same exploration loop in a field setting with the query response degraded to a realistic level, for example a live social-media API that returns only a few hundred friends per query and a bot detector whose labels are only about 80% accurate, and compare the queries needed to reach 90% of targets with the known-topology baseline; if the multiplier exceeds 1.4, the reported efficiency does not transfer.","tokens_in":20125,"feed_emoji":"🔍","tokens_out":9047,"duration_ms":88196,"temperature":0.7,"pith_summary":"This paper addresses a practical mismatch: finding hidden populations such as Sybil accounts, socially isolated people, or influencers in a social network whose full structure is not known. It formulates discovery as an iterative query loop in which each queried node reveals its label and its neighbors, and a machine-learning model retrained on the growing observed subgraph chooses which frontier node to query next. On Facebook, Enron, Epinion, and Twitter graphs, the loop finds 10% of the targets with at most 1.2 times the queries needed when the entire topology is given to the model, and 90% of the targets with at most 1.4 times. The paper's second claim is that node embeddings help for influencer discovery but can degrade performance for peripheral and Sybil nodes, and its third is that a bandit selecting between embedding and non-embedding models keeps efficiency uniformly high. If these claims hold, expensive up-front mapping of a social graph is unnecessary for targeted discovery.","feed_headline":"Unknown-network searches find hidden nodes at near-oracle query cost","feed_subtitle":"ML-guided queries find 90% of targets for at most 1.4x the cost when the graph is known.","key_machinery":"The engine is a repeated train-score-query-retrain loop. At round $k$, the model sees only the partial graph $G_{k-1}$ of queried nodes and border nodes; features describe each border node's local neighborhood (target-neighbor counts, triangle ratios, two-hop target reach), optionally augmented by consistent inductive DeepGL embeddings computed on the evolving graph. LightGBM is retrained on the labels of queried nodes and assigns target probabilities to border nodes, and the highest-probability $m_k$ nodes are queried. A D3TS bandit, dynamic Thompson sampling with Beta-distributed rewards, picks between the base and embedding models so the exploration adapts per task. Efficiency is measured as normalized query cost: queries needed by a strategy, divided by queries needed by the same classifier when the full topology is given.","core_discovery":"Machine-learning-guided exploration of an unknown graph can discover hidden target nodes nearly as efficiently as an oracle that already knows the whole graph. Concretely, the query cost to discover 10% of the target nodes is at most 1.2 times the known-topology cost, and the cost to discover 90% is at most 1.4 times, across the eight task/network settings studied. This holds for three structurally different target definitions: Sybil nodes that cluster, peripheral nodes that sit in the low-coreness fringe, and influencer source spreaders and brokers that occupy the core. The paper also shows that DeepGL node embeddings improve influencer discovery by 20-30% but hurt some peripheral and Sybil settings, and that a dynamic Thompson-sampling bandit that switches between embedding-based and base-feature classifiers matches the better model in almost every setting.","pith_inferences":["If the query multipliers hold across more networks, local partial structure carries most of the signal needed for global label recovery, which narrows the practical gap between active and passive graph labeling.","A natural next experiment is to inject label noise and neighbor truncation into the current simulator to map where the 1.2/1.4 multipliers start to deteriorate.","The embedding-overfitting story suggests a cheap fix the paper does not test: feature selection or a lower-dimensional embedding model might recover the lost efficiency in peripheral and Sybil settings.","Used on sensitive attributes, the same loop could pinpoint vulnerable or dissident users efficiently, so the technology's privacy risk is proportional to its demonstrated efficiency."],"forward_implications":["Finding hidden populations becomes feasible without a precomputed map: an organization can query along the graph and still stay within 1.2-1.4x the queries an omniscient strategy would use.","Retraining matters: a model trained once on the initial subgraph performs much worse than per-round retraining, so any deployed system must update as it explores.","The bandit choice removes a design burden: practitioners do not need to know in advance whether embeddings help, since the algorithm learns which model to trust from rewards.","Simple heuristics such as highest degree or most target neighbors are not enough when targets are dispersed, so the ML query selection is the load-bearing component.","The same exploration framework handles clustered, peripheral, and influential targets, so one codebase can serve all three discovery tasks."],"supporting_citations":[{"why":"Supplies the base graph-exploration framework, the D3TS bandit, and the basic node features that the paper extends to target nodes that are not clustered together.","marker":"Murai et al. (2018)"},{"why":"Provides DeepGL, the inductive node-embedding algorithm whose double-edged effect on discovery efficiency is a central finding.","marker":"Rossi, Zhou, and Ahmed (2018)"},{"why":"Defines source-spreader and broker influencer scores and supplies the Twitter Japan graph used for influencer discovery.","marker":"Tsugawa and Watabe (2023)"},{"why":"Provides the Sybil-region construction with attack edges used to generate ground-truth Sybil labels.","marker":"Jia, Wang, and Gong (2017)"},{"why":"Supplies the k-core and coreness basis for defining peripheral nodes and the observation that influential spreaders occupy the core.","marker":"Kitsak et al. (2010)"},{"why":"Motivates the problem through respondent-driven sampling of hidden populations and the cost of interviews.","marker":"Heckathorn (1997)"},{"why":"Supplies LightGBM, the gradient-boosting classifier used for target prediction in every exploration strategy.","marker":"Ke et al. (2017)"}],"fun_headline_variants":["Hidden nodes found with near-oracle query efficiency","ML-guided graph search matches known-topology cost","Query cost within 1.4x of known graph for hidden nodes","Bandit-guided exploration finds hidden nodes efficiently","Near-oracle discovery of hidden social network nodes"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The claim depends on the query model in which asking a node reveals its true label and its complete adjacency list without noise, rate limits, or non-response.","fun_headline_variants_meta":{"raw":{"variants":["Hidden nodes found with near-oracle query efficiency","ML-guided graph search matches known-topology cost","Query cost within 1.4x of known graph for hidden nodes","Bandit-guided exploration finds hidden nodes efficiently","Near-oracle discovery of hidden social network nodes"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000145,"raw_usage":{"total_tokens":1187,"prompt_tokens":964,"completion_tokens":223,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":580,"completion_tokens_details":{"reasoning_tokens":148}},"tokens_in":580,"tokens_out":223,"duration_ms":2873,"temperature":1.0,"reasoning_tokens":148,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:02:51.351359+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the same exploration loop in a field setting with the query response degraded to a realistic level, for example a live social-media API that returns only a few hundred friends per query and a bot detector whose labels are only about 80% accurate, and compare the queries needed to reach 90% of targets with the known-topology baseline; if the multiplier exceeds 1.4, the reported efficiency does not transfer.","supporting_citations":[{"cited_title":"L.; Towsley, D.; and Gile, K","cited_arxiv_id":null,"evidence_quote":"Supplies the base graph-exploration framework, the D3TS bandit, and the basic node features that the paper extends to target nodes that are not clustered together."},{"cited_title":"A.; Zhou, R.; and Ahmed, N","cited_arxiv_id":null,"evidence_quote":"Provides DeepGL, the inductive node-embedding algorithm whose double-edged effect on discovery efficiency is a central finding."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines source-spreader and broker influencer scores and supplies the Twitter Japan graph used for influencer discovery."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the Sybil-region construction with attack edges used to generate ground-truth Sybil labels."},{"cited_title":"K.; Havlin, S.; Liljeros, F.; Muchnik, L.; Stanley, H","cited_arxiv_id":null,"evidence_quote":"Supplies the k-core and coreness basis for defining peripheral nodes and the observation that influential spreaders occupy the core."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the problem through respondent-driven sampling of hidden populations and the cost of interviews."}],"review_version":1}