{"id":"7a9df8e1-2df8-4400-a661-4078a9612006","arxiv_id":"1908.06543","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"The paper introduces GEM-Bench, a 100-network benchmark and GFS-score for evaluating graph embedding methods on link prediction, and reports that SDNE and HOPE generally outperform traditional heuristics.","lead":"This paper builds a benchmark for comparing graph embedding methods on 100 real-world networks and introduces a normalized score, GFS, to rank them. It reports that deep embedding methods such as SDNE often beat classic link prediction heuristics, and it releases a Python library to run the comparisons.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Table 2's GFS-score ranking is underdetermined: the embedding dimension used to compute it is never specified, while Section 4.4 shows rankings shift with dimension, so the claim that embeddings outperform heuristics rests on an unstated hyperparameter choice.","rationale":"The reader's weakest_assumption concerns the representativeness of ISRW-sampled subgraphs; that is a real external-validity risk. I focus instead on a more immediate internal threat: the GFS-score values in Table 2 are not reproducible because the embedding dimension is unspecified. Section 4.4 explicitly shows method rankings that depend on dimension, so the central numerical evidence for the headline claim is underdetermined. The paper also reports no standard deviations despite the table title, so the stability of the GFS ranking is unverifiable. A dimension-fixed recomputation of Table 2 would settle whether the conclusion survives. This concern does not refute the benchmark's usefulness, but it makes the current CONDITIONAL verdict appropriate and adds a specific condition: report and justify the dimension-selection protocol before GFS rankings are used.","tokens_in":18776,"tokens_out":10607,"duration_ms":106777,"concrete_test":"Recompute all entries of Table 2 twice, once with embedding dimension fixed at 24 and once at 27, using the same train/test splits and random baseline for all methods; also record the macro-GFS P@100 ordering in each case. If the top-ranked method or the set of embedding methods that beat all four heuristics differs between the two runs, the GFS-score requires a stated dimension-selection policy (for example, optimal per-graph dimension or an explicit average over 24-27) before the central claim is assessable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative support for the claim that embeddings outperform traditional link prediction is Table 2, but the GFS-score in Eq. (1) is a function of the embedding dimension d, and the paper never states which d (or set of d values) produced the GFS values. Section 4.4 documents that performance is dimension-dependent: SDNE's MAP improves as d goes from 24 to 27, HOPE's P@100 deteriorates, and Laplacian Eigenmaps overfits at higher d (Figures 2 and 3). Because Table 2's scores (e.g., SDNE micro-GFS MAP 11.0 vs Common Neighbors 2.8, or the micro/macro P@100 reversal between HOPE and SDNE) are not tied to a reproducible dimension-selection protocol, the ranking and the 'embeddings generally beat heuristics' conclusion can change under a different hyperparameter choice. Table 2's title promises standard deviations but none are reported, so the stability of the GFS ranking cannot be assessed from the paper. This is an incompleteness in the definition of the reported quantity, not a claim that the conclusion is false.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces GEM-BEN, a benchmark for evaluating graph embedding methods on link prediction. It assembles a corpus of 100 real-world graphs, mostly from CommunityFitNet with additions from SNAP, grouped into social, biological, economic, and technological domains. The paper evaluates four graph embedding methods (Laplacian Eigenmaps, Graph Factorization, HOPE, SDNE) and four traditional link prediction baselines (Preferential Attachment, Common Neighbors, Jaccard Coefficient, Adamic-Adar) using MAP and P@100. It proposes a GFS-score, defined as the average over graphs of the ratio between a method's performance and a random baseline, with micro, macro, and per-domain variants. The central empirical claim is that graph embedding approaches outperform traditional link prediction methods across the benchmark, with SDNE generally ranked first. The paper also analyzes sensitivity to graph size, density, and embedding dimension, and documents a Python library implementing the benchmark.","tokens_in":19026,"tokens_out":2888,"duration_ms":30796,"significance":"If the results are made reproducible, the benchmark and the GFS-score would be a useful community resource for comparing graph embedding methods on a broader set of real networks than is typical in the literature. The release of the gemben library and the explicit goal of supporting evaluation of future methods are concrete strengths. The paper also provides falsifiable aggregate rankings across domains and metrics. However, the central quantitative claim currently rests on several unstated experimental choices, so the significance is conditional on completing the methodological specification.","major_comments":[{"comment":"Table 2 is titled 'Average and standard deviation of GFS-score' but no standard deviations are reported anywhere in the table or text. For example, the paper states SDNE beats HOPE by a large margin on micro-GFS MAP (11.0 vs 6.1), but without the spread across graphs the reader cannot judge whether this difference is stable or driven by a few graphs. Please report standard deviations or per-graph score distributions for the GFS values.","section":"Section 3.3, Eq. (1), Table 2"},{"comment":"The link prediction protocol is underspecified. The paper does not state how many edges are hidden for testing, how negative samples are generated, what the positive-to-negative ratio is, whether P@100 is computed over all nodes or a sample, or whether the same train/test splits are used for every method. Since the definition of em(g, a) in Eq. (1) depends on these choices, the GFS-score is not uniquely defined by the text, and protocol differences can affect the comparison between embedding methods and heuristics. Please describe the exact evaluation protocol, including any random seed and number of runs.","section":"Section 3.1 and Section 3.2"},{"comment":"The benchmark uses Induced Subgraph Random Walk Sampling (ISRW) to sample 'some huge social graphs while keeping the same graph density,' but it does not say which graphs were sampled, what sampling parameters were used, or whether the induced subgraphs preserve the properties relevant to embedding performance such as degree distribution, community structure, and diameter. Since the GFS-score averages over these graphs, any distortion introduced by sampling affects the external validity of the ranking for the original large networks. Please list the sampled graphs and provide a comparison of key structural properties before and after sampling.","section":"Section 3.1"}],"minor_comments":[{"comment":"The text reads 'an and overview of graph embeddings'; this should be 'an overview of graph embeddings.'","section":"Section 1.3"},{"comment":"The sentence 'We use Induced Subgraph Random Walk Sampling (ISRW) to sample some huge social graphs while keeping the same graph density to ensure' is incomplete and should be finished.","section":"Section 3.1"},{"comment":"There is a typo in the phrase 'the bias of the embedding method towards specific nodes int he graph'; 'int he' should be 'in the.'","section":"Section 3"},{"comment":"These figures would benefit from error bars or shaded confidence bands; the text states observations about consistent performance and low variance, but the plots show single curves without dispersion information.","section":"Figures 2 and 3"},{"comment":"The appendix first describes ten synthetic graph generators but Section 6.3 refers to 'eleven synthetic graph datasets'; this inconsistency should be corrected.","section":"Appendix, Section 6.2 vs 6.3"},{"comment":"The paper calls '8 state-of-the-art methods' in the contributions, but only four are graph embedding methods and the other four are traditional heuristics; the wording should distinguish 'methods' from 'baselines.'","section":"Section 1.2 and Section 3.5"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for the journal and the benchmark idea is timely. The main concern is not with the internal logic of the GFS-score definition, which is straightforward, but with the absence of the protocol details needed to reproduce Table 2 and to interpret the claimed ranking. The self-citations to the authors' earlier survey are used as background and do not appear to feed the central result. I would support publication after the experimental protocol and dimension-selection procedure are specified precisely, and after the standard deviations promised by Table 2 are actually reported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this is a genuinely useful benchmark paper, and the broad conclusion that graph embeddings beat Common Neighbors and friends on a large, varied corpus is credible. But the headline GFS-score table is not reproducible as reported, because the paper never states the embedding dimension used to compute it or the link-prediction protocol.\n\nWhat's new: the assembled corpus of 100 networks organized by domain, the GFS-score normalization against a random baseline, the open-source gemben library, and a fairly systematic comparison of four embedding methods against four traditional heuristics. The appendix is honest: on simple synthetic graphs the heuristics actually win, which is a nice counterpoint to the main narrative. The citation pattern is fine; the self-citations are to the authors' own survey and prior library work, which is appropriate.\n\nSoft spots: Section 3.3 defines GFS-score as a function of the link prediction scores, but Section 4 never says how many edges are hidden, how negative samples are drawn, or what embedding dimension was used for Table 2. Table 2's title promises average and standard deviation; I see averages only. Section 4.4 documents that performance shifts with dimension (SDNE improves, HOPE P@100 degrades), so the exact ranking in Table 2 depends on an unstated hyperparameter. That is a reproducibility gap, not a sign the conclusion is wrong: the figures show SDNE and HOPE beat the heuristics across the displayed range of dimensions. The ISRW sampling of some \"real\" social graphs is also underdescribed; those graphs are no longer the originals, and the paper should say which graphs were sampled and what properties were preserved.\n\nWho is this for: anyone developing or evaluating graph embedding methods who wants a larger test bed than the usual two or three networks. The paper deserves a serious referee, but it needs a substantial revision to report the protocol and error bars, and ideally a sensitivity analysis over dimensions for the GFS-score.","headline":"A useful benchmark resource with a credible broad claim, but the headline GFS-score table is missing the protocol details needed to reproduce it.","tokens_in":19514,"tokens_out":2522,"would_cite":true,"duration_ms":26086,"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":"Graph embedding methods, led by SDNE, outperform traditional link-prediction heuristics across a 100-graph benchmark, and the paper's GFS-score turns that comparison into a reusable ranking.","keywords":["graph embedding","link prediction","benchmark","GFS-score","graph representation learning","network embedding evaluation","domain-specific graph properties","embedding dimension"],"falsifier":"Run the same eight methods on a held-out set of large real networks that are not in the benchmark corpus, with per-method hyperparameter tuning; if traditional heuristics match or beat the embedding methods on average, the claim that embeddings outperform traditional methods is refuted.","tokens_in":1493,"feed_emoji":"📊","tokens_out":3172,"duration_ms":95830,"temperature":0.7,"pith_summary":"This paper tries to settle how graph embedding methods should be compared. Embedding each node of a network into a low-dimensional vector space is popular, but published comparisons are scattered: each method is tested on a few favorable graphs with its own metrics, so no one can say which method will work on a new graph. The authors build a benchmark of 100 real-world networks spanning social, biological, technological, and economic domains, run four embedding methods and four traditional link-prediction heuristics on all of them, and define a normalized score, GFS-score, that averages performance relative to random prediction. Their central claim is that embedding methods broadly beat traditional heuristics, with SDNE ranking first overall, and that GFS-score gives a reusable way to rank any embedding method and to choose one for a given graph domain.","feed_headline":"Embedding methods beat classic link predictors on 100 graphs","feed_subtitle":"A normalized GFS-score ranks any embedding method across domains and metrics.","key_machinery":"The load-bearing object is GFS-score, a normalized evaluation score that divides a method's link-prediction performance, measured by MAP or P@100, by the performance of a random predictor and averages the ratio over a set of graphs. It has micro, macro, and per-domain variants, so one number ranks methods while the domain components show where the advantage comes from. The supporting machinery is the benchmark itself: 100 real-world graphs with varied size (200 to 1500 nodes), density, diameter, and clustering, grouped into four domains, evaluated with two complementary metrics that capture global and local prediction quality.","core_discovery":"On the paper's own terms, the discovery is that graph embedding methods reliably outperform traditional non-parametric link-prediction heuristics across a broad corpus. Averaged over 100 real graphs and normalized by a random predictor, the best embedding method, SDNE, achieves a micro-GFS MAP score of 11.0, compared with 2.8 for Common Neighbors, and a macro-GFS MAP score of 10.1 against 4.8 for the best heuristic. The margin is domain-dependent: traditional heuristics still do well on social graphs, while economic graphs, which lack community structure, defeat the heuristics almost entirely and favor SDNE. HOPE, which preserves higher-order proximity, takes the top P@100 score in biology and social domains. The paper argues that GFS-score, with micro, macro, and per-domain components, is a principled way to rank existing and future methods and to expose which graph properties each method exploits.","pith_inferences":["A natural extension the authors leave implicit is to turn GFS-score into a recommender: fit a model from cheap graph statistics (density, diameter, clustering coefficient) to the best-performing method, then predict the right embedding for an unseen graph without running every method.","Because only four embedding methods are ranked, the leaderboard is a snapshot; applying the same framework to newer neural link predictors could reorder the top ranks without changing the framework's validity.","Since GFS-score is a ratio to a random baseline, reporting absolute MAP and P@100 alongside the ratio would make the comparison more informative for graphs where the random baseline is very weak.","A concrete experiment suggested by the appendix: generate graphs that combine community structure with power-law degree distributions and check whether embedding methods regain the advantage they hold on real networks, which would identify the structural driver of that advantage."],"forward_implications":["Someone with a new graph can use per-domain GFS-scores to pick an embedding method instead of testing all candidates, because the paper finds performance is consistent within a domain.","Future embedding methods can be plugged into the accompanying open-source library and compared on the same 100 graphs with the same random-normalized score, replacing ad hoc claims of improvement on a few datasets.","The failure of traditional heuristics on economic graphs implies that methods capturing non-local structure, not just neighborhood overlap, are necessary for link prediction in domains without clear community structure.","Embedding dimension is not neutral: SDNE improves as dimensions rise while Laplacian Eigenmaps overfits, so fair comparisons must report and justify dimension.","The synthetic-graph results show simple generated graphs are not a substitute for real benchmarks, since classic heuristics can beat embeddings when the generator's structure matches the heuristic."],"supporting_citations":[{"why":"Supplies 86 of the 100 real-world graphs used as the benchmark corpus.","marker":"[13]"},{"why":"Supplies the remaining 14 real-world graphs in the benchmark.","marker":"[14]"},{"why":"Provides the four-domain taxonomy used to group graphs and compute per-domain scores.","marker":"[15]"},{"why":"Gives the sampling method used to reduce huge social graphs while preserving density.","marker":"[35]"},{"why":"Defines Laplacian Eigenmaps, one of the four embedding methods evaluated.","marker":"[17]"},{"why":"Defines Graph Factorization, one of the four embedding methods evaluated.","marker":"[9]"},{"why":"Defines HOPE, the higher-order-proximity embedding method that leads P@100 in two domains.","marker":"[21]"},{"why":"Defines SDNE, the deep-autoencoder embedding method with the top GFS-scores.","marker":"[10]"},{"why":"Defines the Common Neighbors baseline used for comparison.","marker":"[1]"},{"why":"Defines the Adamic-Adar baseline used for comparison.","marker":"[2]"}],"fun_headline_variants":["SDNE tops 100-graph embedding benchmark","Embeddings beat heuristics on 100 real-world graphs","GFS-score ranks graph embedding methods fairly","New benchmark: SDNE wins, but social graphs favor heuristics","100 graphs, one score: GFS ranks embeddings"],"cache_read_input_tokens":21760,"weakest_assumption_plain":"The rankings depend on the 100 benchmark graphs being representative: if the sampled versions of large social graphs distort degree distributions, community structure, or diameter, the GFS-scores will not transfer to the original networks or to other graph families.","fun_headline_variants_meta":{"raw":{"variants":["SDNE tops 100-graph embedding benchmark","Embeddings beat heuristics on 100 real-world graphs","GFS-score ranks graph embedding methods fairly","New benchmark: SDNE wins, but social graphs favor heuristics","100 graphs, one score: GFS ranks embeddings"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000721,"raw_usage":{"total_tokens":3282,"prompt_tokens":1038,"completion_tokens":2244,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":2167}},"tokens_in":654,"tokens_out":2244,"duration_ms":16260,"temperature":1.0,"reasoning_tokens":2167,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:41:23.958559+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the same eight methods on a held-out set of large real networks that are not in the benchmark corpus, with per-method hyperparameter tuning; if traditional heuristics match or beat the embedding methods on average, the claim that embeddings outperform traditional methods is refuted.","supporting_citations":[{"cited_title":"Ghasemian, H","cited_arxiv_id":null,"evidence_quote":"Supplies 86 of the 100 real-world graphs used as the benchmark corpus."},{"cited_title":"Leskovec, R","cited_arxiv_id":null,"evidence_quote":"Supplies the remaining 14 real-world graphs in the benchmark."},{"cited_title":"Clauset, E","cited_arxiv_id":null,"evidence_quote":"Provides the four-domain taxonomy used to group graphs and compute per-domain scores."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the sampling method used to reduce huge social graphs while preserving density."},{"cited_title":"Belkin, P","cited_arxiv_id":null,"evidence_quote":"Defines Laplacian Eigenmaps, one of the four embedding methods evaluated."},{"cited_title":"Ahmed, N","cited_arxiv_id":null,"evidence_quote":"Defines Graph Factorization, one of the four embedding methods evaluated."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines HOPE, the higher-order-proximity embedding method that leads P@100 in two domains."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines SDNE, the deep-autoencoder embedding method with the top GFS-scores."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Common Neighbors baseline used for comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Adamic-Adar baseline used for comparison."}],"review_version":1}