{"id":"089888da-c216-427d-ba01-e0e0c3ee4432","arxiv_id":"1908.01769","paper_version":5,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"SPX jointly optimizes stress, edge crossings, crossing angle, and upwardness through weighted penalties, producing drawings with more balanced readability than single-criterion algorithms.","lead":"This paper presents SPX, a graph drawing framework that simultaneously optimizes several readability goals: accurate distances, few edge crossings, wide crossing angles, and upward direction for directed graphs. It gives visualization tools a single knob to balance these goals instead of sacrificing one for another.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"SPX's crossing-angle term is a soft weighted sum, so the claim that it 'explicitly maximizes the minimum crossing angle' is not supported; the objective can prefer layouts with worse minimum angles.","rationale":"I identified the objective mismatch in Section 3.2 as more load-bearing than the convergence issue flagged by the reader. Algorithm 1's convergence behavior is a practical concern and the paper honestly reports it; even without a guarantee, the framework can produce useful layouts if a good gradient-descent variant is chosen from the sweep. The crossing-angle objective, by contrast, is claimed in the abstract and in Section 3.2 to explicitly maximize the minimum crossing angle. That claim is false: the cost is a sum of cos^2-weighted crossing penalties, which can improve (decrease) while the actual minimum crossing angle gets worse. The paper's own Table 6 shows SPX's minimum angle falling far below the dedicated algorithms on a substantial fraction of the contest graphs. Since 'minimum crossing angle' is one of the three named X criteria in the central claim, this is a direct challenge to the paper's stated contribution. It is a correctable issue: the authors could rephrase the claim to 'encourages larger crossing angles' or implement a true min-max term. The empirical evaluation remains valuable, and the released code supports reproduction, so I would keep the verdict at conditional rather than reject. My concern differs from the reader's weakest assumption (convergence), hence agreement_with_reader is 'disagree'.","tokens_in":14526,"tokens_out":9328,"duration_ms":89435,"concrete_test":"Take a small graph with exactly two crossing edge pairs. Construct two layouts with identical stress and crossing count: Layout A has crossing angles 5 degrees and 85 degrees; Layout B has 40 degrees and 40 degrees. Using the released SPX code, evaluate the Section 3.2 penalty term (sum of cos^2(theta_i)) on both layouts, holding the base crossing penalty fixed. cos^2(5)+cos^2(85) is approximately 1.000, while 2*cos^2(40) is approximately 1.174, so the SPX objective prefers Layout A even though its minimum crossing angle is 5 degrees, far worse than Layout B's 40 degrees. If this holds, the objective does not maximize the minimum crossing angle, falsifying the central claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.2 defines the crossing-angle penalty as the edge-crossing penalty of Eq. (2) multiplied by cos^2(theta_i), summed over all crossing edge pairs. Minimizing this sum is a surrogate for angle quality, not an optimization of the minimum crossing angle: because cos^2 decreases monotonically from 1 at 0 degrees to 0 at 90 degrees, the term gives more weight to small angles, but a single very small angle can be offset by several near-90-degree angles or by stress. Thus the sentence in Section 3.2 that the penalty 'explicitly maximizes the minimum crossing angle' is incorrect. A genuine min-max formulation would impose theta_i >= theta for all crossings and then maximize theta. The abstract's central claim that SPX 'simultaneously optimizes ... minimum crossing angle' therefore overstates what the objective does. The reported CA numbers in Table 6 corroborate this: SPX's minimum crossing angle is often far from the dedicated angle optimizers (e.g., 2018-8: 3.01 degrees vs KIT 17.97 degrees; 2017-9: 15.46 degrees vs Tubingen 88.20 degrees), which is hard to reconcile with the abstract's 'close to the state-of-the-art' for this metric. This is not a convergence or implementation issue; it is a logical mismatch between the stated objective and the actual cost function.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Stress-Plus-X (SPX), a framework for graph layout that augments classical stress minimization with penalty terms for additional readability criteria: edge crossings, crossing angle, and upwardness for directed graphs. The objective is a weighted sum of stress and the penalties, with a hyperparameter K balancing stress against the X terms. The optimization alternates between solving a linear program for the auxiliary variables u and gamma of the crossing penalties and gradient descent on the vertex coordinates. The authors evaluate SPX against dedicated single-criterion algorithms on graph drawing contest graphs, community graphs, and directed acyclic graphs, and report that SPX produces layouts that are competitive on multiple metrics while staying close to state-of-the-art performance on the individual criteria. They also provide an open-source implementation.","tokens_in":14755,"tokens_out":7054,"duration_ms":66115,"significance":"If the claims were fully supported, SPX would be a useful practical contribution to multi-criteria graph layout, a topic for which few general frameworks exist. The paper offers a flexible, extensible formulation and an honest discussion of trade-offs, and the release of source code and benchmark data strengthens reproducibility. However, the central claims about explicitly optimizing the minimum crossing angle and about achieving results close to single-criterion state-of-the-art are not supported by the paper's own objective definition and data. The upwardness constraint mechanism is also underspecified. With revisions that correct these overstatements and clarify the optimization, the framework could be a valuable heuristic for balanced graph drawing.","major_comments":[{"comment":"The sentence \"this modified penalty function explicitly maximizes the minimum crossing angle\" is not correct as stated. The penalty is a weighted sum over crossing edge pairs of the crossing penalty of Eq. (2) multiplied by cos^2(theta_i). Minimizing this sum is a soft surrogate for angle quality; it can be reduced by improving most angles even if one very small angle remains, and the term competes with the stress term in Eq. (3). A genuine min-max formulation would require constraints of the form theta_i >= theta_min for all crossings and then maximize theta_min. The abstract's claim that SPX \"simultaneously optimizes ... minimum crossing angle\" therefore overstates what the objective actually does. Table 6 corroborates this: SPX's minimum crossing angles on several graphs are far below the dedicated angle optimizers (2018-8: 3.01 degrees vs 42.66 and 17.97; 2017-9: 15.46 degrees vs 88.20 and 47.64), which is not just a matter of balancing but a sign that the objective does not directly target the minimum. Please rephrase the claim as \"encourages large crossing angles\" or add an explicit min-max component.","section":"Section 3.2"},{"comment":"The abstract states that SPX \"achieves results that are close to the state-of-the-art algorithms that optimize these metrics individually,\" and Section 6.3 claims the crossing-angle results are \"generally within a factor of two of the other two teams.\" The data in the paper contradict these assertions. For crossing angles, Table 6 shows several graphs where SPX is more than a factor of two worse than both Tubingen and KIT (e.g., 2018-8: 3.01 vs 42.66 and 17.97; 2017-7: 20.72 vs 61.79; 2017-9: 15.46 vs 88.20 and 47.64). For crossing minimization, Tables 2-5 show that SPX never outperforms the EI or EP variants of Radermacher et al. on any of the four graph classes; its mean crossings are substantially higher (e.g., Plantri: 296.54 vs EI 109.45; Rome: 33.87 vs EI 16.95). The paper's contribution is the trade-off across criteria, not closeness to single-criterion optimizers, and the text should state this honestly rather than claiming near-state-of-the-art performance.","section":"Abstract and Section 6.3"},{"comment":"The paper says that upwardness is \"enforced directly with a linear constraint (y_v > y_u)\", but Algorithm 1's coordinate update is unconstrained gradient descent on the cost function. No projection, barrier term, or penalty for constraint violation is described anywhere in the optimization procedure. Since the evaluation section claims that SPX always produces completely upward drawings, the mechanism for enforcing these constraints must be specified and verified. As written, the upwardness results are not reproducible and the claim that upwardness is part of the SPX optimization is unsupported.","section":"Section 3.3 and Algorithm 1"},{"comment":"The alternating optimization in Algorithm 1 has no convergence guarantee. The paper demonstrates convergence on only two graphs (Figure 3) and notes that some gradient-descent variants diverge after reaching a minimum. The evaluation, however, applies all six variants across all datasets and selects the layout that minimizes the objective. This raises the question whether the reported results actually correspond to meaningful minima of the combined cost function, and the paper does not report the sensitivity of the final metrics to the choice of variant, K, or initialization. Please either provide a stopping rule that guarantees a non-increasing objective or report the distribution of final objective values and the variability of the reported metrics across the parameter sweep.","section":"Section 3.5"}],"minor_comments":[{"comment":"The header of Algorithm 1 says \"Stress-plux-X\"; this should be \"Stress-Plus-X\".","section":"Algorithm 1"},{"comment":"The sentence \"choosing the layout that maximizes the objective\" should read \"minimizes the objective,\" since Eq. (3) is a cost function to be reduced.","section":"Section 3.4"},{"comment":"The area comparison is confounded because SPX is evaluated without any resolution constraint, while the other algorithms may implicitly enforce minimum separation. The caveat is acknowledged in the text, but Table 1 still reports SPX as best in area; consider reporting area after a fair postprocessing step or labeling the metric as \"area ignoring resolution.\"","section":"Section 4.4 / Table 1"},{"comment":"The statement \"generally within a factor of two of the other two teams\" should be replaced with a precise numeric summary (e.g., median ratio or percentage of graphs within a factor of two), because Table 6 shows that in several cases the factor exceeds two by a wide margin.","section":"Section 6.3"}],"recommendation":"major_revision","confidential_remarks":"The paper has a useful framework and an honest empirical evaluation in several respects, but the overstatement of the crossing-angle objective and the missing upwardness constraint mechanism are load-bearing issues. The authors should be asked to either revise the claims to match what the objective actually does or to change the formulation. The comparison to state-of-the-art also needs to be presented more accurately. These issues are fixable within the scope of a revision, so I do not recommend rejection, but the current version cannot be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: SPX is a genuinely useful multi-criteria layout framework, but the abstract overstates how well it optimizes the minimum crossing angle. The soft-penalty objective encourages large crossing angles on average; it does not maximize the minimum. That mismatch needs fixing, but the core framework and evaluation are solid enough to warrant a revision and a serious review.\n\nWhat's new: SPX extends Shabbeer et al.'s stress-plus-crossings optimization with a binary crossing weight, a K hyperparameter, a cos^2 crossing-angle penalty, and upwardness linear constraints. The framework is clean and extensible. The empirical work is honest: they compare against KIT, Tübingen, and Sugiyama variants on contest and community graphs, reporting stress, crossings, crossing angle, drawing area, and neighborhood preservation. Code and data are public. That is real evidence and should be credited.\n\nThe strong parts: the crossing-minimization term with binary weights beats Shabbeer's compounding penalty on their corpus, and the upwardness constraints produce fully upward drawings while keeping stress competitive. The trade-off analysis in Figures 5 and 6 shows exactly what the framework is for.\n\nSoft spots, in proportion: (1) Section 3.2 claims the cos^2 penalty 'explicitly maximizes the minimum crossing angle.' That is not what a weighted sum does. A single very small angle can be offset by several near-90-degree crossings, so the objective is a surrogate for angle quality, not a min-max formulation. The abstract inherits this overclaim, and Table 6 shows the consequence: SPX's minimum crossing angle on 2018-8 is 3.01° versus Tübingen's 42.66°, and on 2017-9 it is 15.46° versus 88.20°. Calling those results 'close to the state-of-the-art' for the minimum is not supported. Rephrasing to 'crossing angle quality' or 'average crossing angle' would fix it without weakening the contribution. (2) Algorithm 1 is an alternating heuristic with no convergence guarantee. The paper shows it levels off on two graphs, which is evidence of behavior, not a proof. That is fine for a heuristic paper, but the limitation should be stated plainly rather than implied to hold generally. (3) Minor: Section 3.4 says 'choosing the layout that maximizes the objective' when minimizing is what the cost function requires. That typo should be corrected.\n\nWho this is for: graph drawing and information visualization researchers who want a practical tunable tool for balancing readability criteria, and anyone building on Shabbeer et al. It deserves a serious referee. I would recommend the editor send it to peer review with a request for revision, mainly to correct the crossing-angle framing and tone down the abstract. The framework is not the problem; the claims about what it optimizes are.","headline":"A practical multi-criteria layout framework whose crossing-angle objective is honestly a soft surrogate, not a true minimum maximizer; worth reviewing after the claims are corrected.","tokens_in":15331,"tokens_out":2447,"would_cite":true,"duration_ms":25336,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"SPX graph layout minimizes stress while optimizing crossings, angles, and upwardness in one cost function.","keywords":["graph drawing","stress minimization","edge crossings","crossing angle","upward drawing","multi-criteria optimization","graph readability","directed acyclic graphs"],"falsifier":"Run SPX on a graph outside the two convergence-test graphs with a fixed K and record combined cost, crossings, stress, and crossing angle over 100 iterations for all six gradient variants; the convergence assumption fails if no variant drives the cost down or if the metrics oscillate. A stronger check is to enumerate the true minimum of the combined cost on small graphs and compare it with SPX's final layout, since a consistent large gap would show the framework is not actually jointly optimizing.","tokens_in":14288,"feed_emoji":"📐","tokens_out":9333,"duration_ms":88178,"temperature":0.7,"pith_summary":"SPX ('Stress-Plus-X') is a graph layout framework whose central idea is that one cost function can minimize stress and other readability criteria at the same time. The paper adds three extra terms to the standard stress objective: a penalty for edge crossings, a version of that penalty weighted by the cosine of the crossing angle so that small angles become expensive, and, for directed acyclic graphs, linear constraints that force every edge to point upward. A hyperparameter K sets the balance between stress and the extra criteria, so a user can tilt the drawing toward one goal without abandoning the others. The reported experiments show layouts that are close to specialized algorithms on their home metric while doing better than those algorithms on stress, drawing area, and neighborhood preservation. The contribution is a demonstration that balancing several readability criteria in one optimization loop is practical, not just a wish list.","feed_headline":"One cost function balances four graph readability goals at once","feed_subtitle":"SPX drawings stay close to single-goal algorithms on each metric while avoiding extreme layouts.","key_machinery":"The load-bearing object is the combined cost function $cost(C,u,\\gamma,\\rho) = \\mathrm{stress}(C) + K \\times \\sum_{P} \\mathrm{penalties}(C,u,\\gamma,P)$, with coordinates $C$, balancing hyperparameter $K$, penalty weights in $P$, and separating-line variables $u$ and $\\gamma$. Two edges $A$ and $B$ do not cross exactly when a line separates them; linear-programming duality restates this as inequalities $Au+\\gamma e \\geq 0$ and $Bu+(1+\\gamma)e \\leq 0$, and the positive parts of the violations form a per-pair penalty that is zero for non-crossing pairs. The optimizer alternates: with coordinates fixed, it solves a linear program for the best $u$ and $\\gamma$ for each edge pair; with those fixed, gradient descent moves the coordinates. The crossing-angle version weights each crossing penalty by $\\cos^2(\\theta)$ where $\\theta$ is the crossing angle, so the smallest angles dominate, and upwardness enters as constraints $y_v > y_u$ on directed edges. This machinery lets the user combine criteria simply by adding a penalty to the sum.","core_discovery":"The central claim is that multiple graph layout criteria can be folded into one combined cost function together with stress, and that minimizing it by alternating a linear program with gradient descent produces drawings that are good on every criterion rather than extreme on one. The paper formalizes 'no crossing' for a pair of edges as the existence of a separating line; the violation of the resulting inequalities becomes a positive penalty, and the crossing-angle variant multiplies that penalty by $\\cos^2$ of the angle between crossing edges, making tiny angles costly and also rewarding the removal of crossings. Upwardness is enforced as linear constraints on vertex heights for directed acyclic graphs. Empirically, SPX beats stress-only layouts on crossings, comes within a factor of two of dedicated crossing-angle optimizers while beating them on stress, drawing area, and neighborhood preservation, and produces upward drawings of DAGs with lower stress and area than layered baselines while matching them on crossings.","pith_inferences":["The paper's convergence plots show that no single gradient variant works on all graphs; a robust version of SPX could select the variant or step schedule automatically by the combined cost, turning the current multi-start sweep into an adaptive solver.","Because the per-edge-pair linear programs are the computational bottleneck, replacing them with a batched or barrier formulation could scale SPX from hundred-vertex graphs to the larger contest graphs it currently handles in hours.","The cos-squared weighting mainly rewards increasing the smallest crossing angle; a soft-min over crossing angles might close the remaining gap to dedicated angle optimizers while keeping stress in the loop.","The readability studies the paper cites motivate a direct human-subject test of whether balanced SPX drawings actually speed up graph tasks compared with extreme single-criterion drawings."],"forward_implications":["A user can get a layout that is readable under several measures at once from a single run, instead of running separate single-criterion algorithms and choosing among extreme results.","Adding a new readability criterion to SPX only requires writing a penalty over edge pairs and inserting it with a weight, so the framework can absorb future criteria such as resolution, area, or neighborhood preservation.","For directed acyclic graphs, SPX is an alternative to layered drawing: it preserves upwardness while reporting lower stress and smaller drawing area than standard layered layouts.","The hyperparameter K gives a concrete dial for the stress-versus-X trade-off, which visualization systems can expose to end users."],"supporting_citations":[{"why":"Supplies the edge-crossing penalty built from separating-line inequalities; SPX replaces its compounding weight with a binary weight and adds the balancing hyperparameter.","marker":"[33]"},{"why":"Supplies the stress majorization routine used as SPX's stress component and as one source of initial layouts.","marker":"[16]"},{"why":"Defines the stress measure over all-pairs graph distances that SPX minimizes as its base criterion.","marker":"[22]"},{"why":"Provides the edge-crossing detection code used in the implementation and a dedicated crossing-angle baseline for comparison.","marker":"[8]"},{"why":"Provides a dedicated crossing-angle heuristic that serves as the reference for how close SPX gets to single-criterion performance.","marker":"[3]"},{"why":"Supplies the 400-graph corpus and the four crossing-minimization algorithms used to benchmark SPX's crossing penalty.","marker":"[30]"},{"why":"Provides the metric computations for stress, crossings, angle, area, and neighborhood preservation used throughout the evaluation.","marker":"[7]"},{"why":"Supplies a layered directed-graph drawing technique used as a baseline in the upwardness comparison.","marker":"[17]"}],"fun_headline_variants":["Four graph readability goals, one cost function","SPX: Jointly optimize stress, crossings, angle, upwardness","Multi-goal graph layout: stress plus crossings, angle, upwardness","One optimizer for stress, crossings, angle, and upwardness","Graph layout that balances stress, crossings, and angles"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the alternating optimization scheme (linear programming for the separating lines, then gradient descent on coordinates) converges to a good minimum of the combined cost on every graph, but the paper demonstrates convergence on only two graphs and reports that some gradient-descent variants diverge on one of them.","fun_headline_variants_meta":{"raw":{"variants":["Four graph readability goals, one cost function","SPX: Jointly optimize stress, crossings, angle, upwardness","Multi-goal graph layout: stress plus crossings, angle, upwardness","One optimizer for stress, crossings, angle, and upwardness","Graph layout that balances stress, crossings, and angles"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000735,"raw_usage":{"total_tokens":3232,"prompt_tokens":838,"completion_tokens":2394,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":454,"completion_tokens_details":{"reasoning_tokens":2310}},"tokens_in":454,"tokens_out":2394,"duration_ms":16597,"temperature":1.0,"reasoning_tokens":2310,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:13:04.746019+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run SPX on a graph outside the two convergence-test graphs with a fixed K and record combined cost, crossings, stress, and crossing angle over 100 iterations for all six gradient variants; the convergence assumption fails if no variant drives the cost down or if the metrics oscillate. A stronger check is to enumerate the true minimum of the combined cost on small graphs and compare it with SPX's final layout, since a consistent large gap would show the framework is not actually jointly optimizing.","supporting_citations":[{"cited_title":"In: NIPS Workshop on Challenges of Data Visualization (2010)","cited_arxiv_id":null,"evidence_quote":"Supplies the edge-crossing penalty built from separating-line inequalities; SPX replaces its compounding weight with a binary weight and adds the balancing hyperparameter."},{"cited_title":"In: Pach, J","cited_arxiv_id":null,"evidence_quote":"Supplies the stress majorization routine used as SPX's stress component and as one source of initial layouts."},{"cited_title":"A Greedy Heuristic for Crossing-Angle Maximization","cited_arxiv_id":"1807.09483","evidence_quote":"Provides the edge-crossing detection code used in the implementation and a dedicated crossing-angle baseline for comparison."},{"cited_title":"A Heuristic Approach towards Drawings of Graphs with High Crossing Resolution","cited_arxiv_id":"1808.10519","evidence_quote":"Provides a dedicated crossing-angle heuristic that serves as the reference for how close SPX gets to single-criterion performance."},{"cited_title":"In: The 20th Workshop on Algorithm Engineer- ing and Experiments (ALENEX’18)","cited_arxiv_id":null,"evidence_quote":"Supplies the 400-graph corpus and the four crossing-minimization algorithms used to benchmark SPX's crossing penalty."},{"cited_title":"https://github.com/felicedeluca/graphmetrics (2019)","cited_arxiv_id":null,"evidence_quote":"Provides the metric computations for stress, crossings, angle, area, and neighborhood preservation used throughout the evaluation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies a layered directed-graph drawing technique used as a baseline in the upwardness comparison."}],"review_version":1}