{"id":"0d188882-9f23-48eb-809e-4d9d8f825c24","arxiv_id":"1908.01528","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"FLUID is a common formal model based on equivalence relations that can define, adapt, and compare structural graph summaries, computed by one generic algorithm in worst-case quadratic and often linear time.","lead":"This paper proposes FLUID, a formal language of equivalence-relation operators that can express 19 existing structural graph summary models. It also presents a single parameterized algorithm that computes any FLUID-defined summary in worst-case O(n^2) time, with experiments on billion-edge web graphs.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Definition 14's related-property-instances relation ρ is not well-defined as written: it quantifies over the very equivalence class being defined and admits multiple fixed points, so the four Goasdoué et al. encodings in Table 3 lack a precise semantics.","rationale":"The reader's CONDITIONAL verdict is appropriate. The paper's core program is valuable: the composition of equivalence relations via intersection and extended union is coherent, the O(n^2) worst-case analysis is supported by the algorithmic sketch and the explicit quadratic inference example in §5.2.6, and Section 6, though not a runtime benchmark, does support the inference-growth claims it directly measures. However, the expressiveness claim over the 19 literature models is the central contribution, and four of the Table 3 rows depend on the instance parameterization with ρ. Definition 14 defines ρ by quantifying over its own equivalence classes and, as the fixed-point test shows, admits multiple relations satisfying the stated condition. This is a formal correctness gap in the printed manuscript, not merely a disagreement with prior consensus. It is repairable by adding a least-fixed-point or transitive-closure definition, which is why the appropriate verdict remains CONDITIONAL rather than REJECT. I also note that Definition 9's set parameterization is inconsistent with Example 4 as printed, but that defect is more localized and more plausibly typographical; the ρ issue affects more Table 3 rows and is the more load-bearing concern.","tokens_in":30263,"tokens_out":17056,"duration_ms":178554,"concrete_test":"Formalize the operator Φ(R) induced by Definition 14: (s,s′)∈Φ(R) iff there exists s′′∈[s]_R with an outgoing triple shared with s′ (or an incoming triple, for target-related properties), or symmetrically for some s′′′∈[s′]_R. On the four-triple graph G={(a,p,x),(b,p,x),(c,q,y),(d,q,y)}, check whether both R1={{a,b},{c,d}} and R2=V×V satisfy Φ(R_i)=R_i. If both are fixed points, ρ is not uniquely defined by the printed text; then request the intended least fixed point and re-derive the four Table 3 rows using [ρ] against Goasdoué et al.'s original definitions to confirm the encodings.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that every FLUID expression denotes a well-defined equivalence relation and that Table 3 expresses all 19 literature models rests on Definition 14's instance parameterization. Four Table 3 rows (Weak Summary, Strong Summary, Typed Weak Summary, Typed Strong Summary) are written as SE[ρ] with related property instances ρ. The formal sentence defines s∼ρs′ iff there exists s′′∈[s]ρ such that s′′ shares an outgoing (or, for target-related properties, incoming) triple with s′, or symmetrically for [s′]ρ. Since [s]ρ is the equivalence class of the very relation being defined, this is not an inductive definition and no least-fixed-point or transitive-closure construction is supplied. The ambiguity is real: on the graph with triples (a,p,x), (b,p,x), (c,q,y), (d,q,y), both the component partition {{a,b},{c,d}} and the universal relation V×V satisfy the stated biconditional. Under V×V, a∼c because d∈[a]V×V shares (q,y) with c, and c∼a because b∈[c]V×V shares (p,x) with a. Thus the text does not pin down a unique ρ. Without a precise ρ, the FLUID encodings of the Weak, Strong, Typed Weak, and Typed Strong summaries are not well-defined, so the paper's headline expressiveness claim is not established as written. A charitable transitive-closure reading would repair the defect, but that repair is not present in the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces FLUID, a formal language for defining structural graph summaries of RDF graphs. FLUID consists of three simple schema elements (POC, PC, OC), one complex schema element (CSE), six parameterizations (label, set, chaining, direction, inference, instance), and payload elements. The authors claim that all 19 graph summary models surveyed in Section 3 can be expressed in FLUID (Table 3), and that any FLUID-defined summary can be computed by one parameterized algorithm in O(n^2) worst-case time and linear time in typical cases. They provide a complexity analysis (Section 5), an explicit quadratic blow-up example under inference (Example 9), and an empirical study of four large RDF datasets (Section 6) that measures the effect of RDFS inference on graph size.","tokens_in":30448,"tokens_out":14174,"duration_ms":132387,"significance":"If the formal problems identified below are repaired, the paper makes a useful contribution: a single, parameterized framework for exact structural graph summaries, with an expressiveness map over 19 models and a uniform algorithm. The complexity analysis is mostly sound, and the explicit n^2/4-triple example for inference is a concrete worst-case illustration. The paper also ships an open-source implementation, which supports reproducibility. However, the formal expressiveness claim currently rests on two definitions that are not well-formed, and the empirical 'typical running time Θ(n)' claim goes beyond what is actually measured.","major_comments":[{"comment":"The relation ρ of related property instances is not well-defined as written. The condition 'there exists s′′∈[s]ρ such that ...' quantifies over the equivalence class of the very relation being defined, with no base case or least-fixed-point construction. The ambiguity is real: on the graph with triples (a,p,x), (b,p,x), (c,q,y), (d,q,y), both the component partition {{a,b},{c,d}} and the universal relation V×V satisfy the stated biconditional. Since Table 3 expresses the Weak Summary, Strong Summary, Typed Weak Summary, and Typed Strong Summary as SE[ρ], the paper's central expressiveness claim over the literature is not established for these four rows. The repair is straightforward — define ρ as the transitive closure of the relation that relates s and s′ when there is a non-rdf:type property p and object o with (s,p,o) and (s′,p,o) (and the analogous target-related condition) — but that construction is not present in the manuscript.","section":"Section 4.2.6, Definition 14 and Table 3"},{"comment":"The set parameterization is internally inconsistent. For SSE∈{PC,POC}, the first disjunct makes any two vertices with at least one outgoing edge equivalent whenever S is nonempty, so Example 4's statement that PCrel|{p1,p2} yields at most four summaries is false: all non-isolated vertices would collapse into a single class. For SSE∈{OC,POC} and S=∅, the second disjunct is vacuously true for pairs where one vertex has no relevant outgoing triple, which can equate vertices with and without types, contradicting Example 3's two-class description. Because Table 3 uses OCtype|∅ and OCtype|VC in the Typed Weak Summary and Typed Strong Summary rows, these rows also lack a precise semantics. The intended notion (an 'overflow' class for vertices with elements outside S, plus ordinary SSE comparison for vertices whose elements all lie in S) needs to be formalized with the empty-set and single-vertex cases handled explicitly.","section":"Section 4.2.2, Definition 9 and Examples 3–4"},{"comment":"The paper's headline empirical claim — 'typical running time of Θ(n)' — is not supported by the experiments reported. Section 6 measures the size of the RDFS vocabulary graph and the number of additional types/properties that inference would add; it does not report wall-clock times for computing any FLUID summary, let alone on graphs with billions of edges. At most, the data support a claim about the growth of the materialized graph under inference. Please either add actual build-time experiments (e.g., for the SSE and CSE cases with and without inference) or revise the abstract and contribution (III) to state the measured quantity precisely.","section":"Section 6 and Section 1 (contribution III)"}],"minor_comments":[{"comment":"The call InfInMap.Put(v, VG.InferOntologyInformation(OUT)) passes OUT, but the loop is over incoming triples IN; this appears to be a typo and should use IN.","section":"Algorithm 1, line 28"},{"comment":"The notation is type-inconsistent: CSE^1 is a 3-tuple of equivalence relations, whereas CSE^k for k≥2 denotes an equivalence relation. The recursion should be stated directly on the induced equivalence relations, as Example 5 does informally.","section":"Definition 10"},{"comment":"Lemma 1 is asserted without proof; since the subsequent complexity analysis relies on it, a short argument (or a reference to the hash-based memoization) should be supplied.","section":"Lemma 1"},{"comment":"The discussion of transitive closure for the instance parameterization is handwavy; a precise statement of the data structure (e.g., union-find or memoized traversal) and its amortized cost is needed to justify the claim that the time complexity does not increase.","section":"Section 5.2.7"},{"comment":"There is a typo in 'we compared the size of one graph summary with and and without inference'; the duplicated 'and' should be removed.","section":"Section 6.4"}],"recommendation":"major_revision","confidential_remarks":"The paper is an extended version of a workshop paper, and the extensions are substantial: the set parameterization, related property instances, payload elements, a uniform algorithm, and a more detailed complexity analysis. The formal defects in Definitions 9 and 14 are local and repairable, but they affect Table 3's expressiveness claims and the formal status of the language. I would be satisfied if the authors replace Definition 14 with a non-circular construction (e.g., transitive closure), rewrite Definition 9 to match Examples 3–4, and either add runtime experiments or soften the Θ(n) empirical claim. The topic is appropriate for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is the first real attempt at a common formal language for structural graph summaries, and the mapping onto 19 existing models is a solid piece of scholarship. The idea of defining schema elements as equivalence relations and composing them with a handful of parameterizations is genuinely useful, and the single generic algorithm is a real contribution. The complexity analysis is mostly convincing: the O((λ+κ)n) result for simple and complex elements, the chaining factor k, and the explicit quadratic inference example are all there. The table translating the literature is careful, and the paper gives credit where it is due.\n\nThe soft spots are real, but they are concentrated in a few places. Definition 9, the set parameterization, is broken as written: the first disjunct merges all non-isolated vertices whenever S is non-empty, which contradicts Example 4 and the intended semantics used by the Typed Weak and Typed Strong summaries. This is not a subtle ambiguity; it is a bug in the definition. Definition 14, the related-property-instances relation ρ, is circular: it quantifies over [s]ρ, the very class being defined, and the stress-test example correctly shows that multiple equivalence relations satisfy the biconditional. The four Goasdoué et al. rows in Table 3 therefore lack a precise semantics as printed. A transitive-closure repair would probably work, but that repair is not in the manuscript. Algorithm 1 has a copy-paste typo in the inference preparation step (it reads OUT for the incoming map, line 28). Finally, the abstract's “typical running time Θ(n)” is not supported by Section 6, which measures how much RDFS inference would inflate the graph data, not the runtime of the summarization algorithm. That is an overclaim, though it is easy to fix by rewording.\n\nNone of these problems sink the overall program. The central derivation in Section 5.2 is plausible, the core language is new and well-motivated, and the flaws are specific and correctable. I would not cite the current version in my own work until Definitions 9 and 14 are repaired, but I would bring it to a reading group and I would send it to peer review. The field could genuinely benefit from a corrected FLUID.","headline":"FLUID is a genuinely useful unifying proposal for structural graph summaries, but the current manuscript has two definition bugs, a copy-paste error, and an overstated empirical claim; all are fixable and it deserves serious review.","tokens_in":31108,"tokens_out":2521,"would_cite":false,"duration_ms":26024,"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":"FLUID unifies 19 graph summary models under one language","keywords":["graph summarization","RDF graphs","equivalence relations","semantic web","bisimulation","RDF Schema","parameterized algorithms","linked data"],"falsifier":"Take a small graph in which two vertices share one property directly and a third vertex shares a different property with one of them, then try to compute $\\rho$ from Definition 14 by iterating to a fixed point; if the final partition depends on the starting partition or no fixed point exists, the instance parameterization is not well-defined and the expressiveness claim over the literature fails. A second check is to pick any one of the 19 literature models, compute its canonical vertex partition and the partition given by its FLUID encoding in Table 3 on a series of random graphs, and look for a discrepancy.","tokens_in":29906,"feed_emoji":"🕸️","tokens_out":6636,"duration_ms":66898,"temperature":0.7,"pith_summary":"FLUID is a formal common language for defining structural summaries of RDF graphs. The paper's central claim is that every one of the 19 structural graph summary models it analyzes can be written as an expression built from four schema elements and six parameterizations, all operating through equivalence relations over vertices. If that claim is right, graph summaries designed in isolation for different tasks are special cases of one model, and a single parameterized algorithm can compute any of them. The paper proves that computing a FLUID-defined summary takes $O(n^2)$ time in the worst case with respect to the number of edges $n$, typically $\\Theta(n)$ in practice on billion-edge web graphs; adding RDF Schema inference can make the worst case quadratic because inferred triples can multiply.","feed_headline":"One language expresses all 19 graph summary models","feed_subtitle":"FLUID reduces semantic graph summaries to equivalence relations and computes them in near-linear time on billion-edge graphs.","key_machinery":"The load-bearing object is the equivalence relation itself: a FLUID graph summary model is a triple of a data graph, an equivalence relation over vertices, and payload elements. The elementary relations POC, PC, and OC compare subjects by their outgoing predicate–object pairs, predicates, or objects; the complex schema element $(\\sim_s, \\sim_p, \\sim_o)$ lifts this to arbitrary equivalences on subjects, predicates, and objects, which is how neighbor schemas enter. Six parameterizations modify these relations, and the extended union $\\cup_{\\text{ex}}$ combines relations in an 'or' fashion while preserving the equivalence property. Because every schema element is an equivalence relation, the algorithm can extract each vertex's schema once, hash it, and merge vertices with equal hashes via union-find; this is what makes the single parameterized algorithm and the near-linear typical behavior possible.","core_discovery":"The discovery is a unification: the many structural graph summary models in the literature, despite being built for different tasks and defined with different data structures, all partition vertices according to structural features that can be captured by equivalence relations. The paper defines three simple schema elements—predicate-object cluster, predicate cluster, and object cluster—and one complex schema element, plus six parameterizations (label, set, chaining, direction, inference, and instance) that adjust what the schema elements see. It then shows that all 19 analyzed models from the literature correspond to FLUID expressions, and that any such expression is computed by one parameterized algorithm. Consequences in the paper: no new algorithm is needed for a new summary definition, summaries become comparable by their parameter settings, and reasoning-augmented summaries can still be computed, with worst-case $O(n^2)$ time and typical $\\Theta(n)$ behavior on large real-world graphs.","pith_inferences":["The paper leaves implicit that its language gives a translation-invariant notion of equivalence between summary models: two models are the same if their FLUID expressions define the same vertex partition, which could be checked mechanically once the encodings are fixed.","An extension not in the paper would apply the same equivalence-relation language to property graphs rather than RDF, treating ordinary vertex labels as a special edge or as part of the label parameterization; the schema elements would not need to change.","A testable consequence is that the quadratic blow-up from inference is avoidable by evaluating reasoning lazily during schema extraction instead of materializing all inferred triples; the paper discusses inference inside versus outside but not this intermediate option."],"forward_implications":["Any FLUID-defined summary, including combinations not found in the literature, can be computed by the same parameterized algorithm, so a new summary definition does not require a new implementation.","All 19 analyzed models become comparable as parameter choices within one language, which makes it possible to state precisely where two summaries differ.","Without the inference parameterization, summaries can be built in time and space linear in the number of edges; the worst case stays quadratic only when materialized RDF Schema inference is used.","The empirical analysis of four large Linked Open Data graphs indicates that vocabulary graphs stay small (about 5 percent of the data graph on average) while inference can add 2 to 20 times more properties and types, supporting the paper's suggestion to apply inference outside the summary."],"supporting_citations":[{"why":"Defines the survey scope of structural semantic graph summaries and the feature table that FLUID must cover.","marker":"[10]"},{"why":"Introduces attribute-based and class-based collections, the two simple summaries encoded as PCrel and OCtype.","marker":"[8]"},{"why":"Defines Characteristic Sets with outgoing and incoming property sets, encoded as the bidirectional predicate cluster with count payload.","marker":"[33]"},{"why":"Defines Weak, Strong, Typed Weak, and Typed Strong summaries plus related-property instances, which drive the instance parameterization and four FLUID encodings.","marker":"[18]"},{"why":"Defines SchemEX and provides the hash-map construction technique and one of the large empirical datasets.","marker":"[27]"},{"why":"Supplies the label and height parameterizations and k-bisimulation features encoded through chaining.","marker":"[43]"},{"why":"Defines the A(k)-index and efficient k-bisimulation computation that FLUID's chaining parameterization reproduces.","marker":"[25]"},{"why":"Defines the T-index over incoming predicate paths, encoded as direction- and chaining-parameterized FLUID.","marker":"[32]"}],"fun_headline_variants":["All 19 graph summary models, one FLUID framework","FLUID: One language to define any graph summary","Unifying 19 summary models with equivalence relations","Compute any graph summary in near-linear time","19 summaries, one parameterized algorithm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the related-property instance relation $\\rho$ in Definition 14 is well-defined, even though its definition refers to the equivalence classes $[s]_\\rho$ it is supposed to create; four of the literature encodings in Table 3 depend on this relation, so if $\\rho$ is ambiguous the expressiveness claim is not settled.","fun_headline_variants_meta":{"raw":{"variants":["All 19 graph summary models, one FLUID framework","FLUID: One language to define any graph summary","Unifying 19 summary models with equivalence relations","Compute any graph summary in near-linear time","19 summaries, one parameterized algorithm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000291,"raw_usage":{"total_tokens":1722,"prompt_tokens":989,"completion_tokens":733,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":605,"completion_tokens_details":{"reasoning_tokens":662}},"tokens_in":605,"tokens_out":733,"duration_ms":7912,"temperature":1.0,"reasoning_tokens":662,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:10:56.732455+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small graph in which two vertices share one property directly and a third vertex shares a different property with one of them, then try to compute $\\rho$ from Definition 14 by iterating to a fixed point; if the final partition depends on the starting partition or no fixed point exists, the instance parameterization is not well-defined and the expressiveness claim over the literature fails. A second check is to pick any one of the 19 literature models, compute its canonical vertex partition and the partition given by its FLUID encoding in Table 3 on a series of random graphs, and look for a discrepancy.","supporting_citations":[{"cited_title":"ˇCebiri´ c, F","cited_arxiv_id":null,"evidence_quote":"Defines the survey scope of structural semantic graph summaries and the feature table that FLUID must cover."},{"cited_title":"Campinas, T","cited_arxiv_id":null,"evidence_quote":"Introduces attribute-based and class-based collections, the two simple summaries encoded as PCrel and OCtype."},{"cited_title":"Goasdou´ e, P","cited_arxiv_id":null,"evidence_quote":"Defines Weak, Strong, Typed Weak, and Typed Strong summaries plus related-property instances, which drive the instance parameterization and four FLUID encodings."},{"cited_title":"Konrath, T","cited_arxiv_id":null,"evidence_quote":"Defines SchemEX and provides the hash-map construction technique and one of the large empirical datasets."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the label and height parameterizations and k-bisimulation features encoded through chaining."},{"cited_title":"Milo and D","cited_arxiv_id":null,"evidence_quote":"Defines the T-index over incoming predicate paths, encoded as direction- and chaining-parameterized FLUID."}],"review_version":1}