Every Sentence Is a Graph

Part I set the baseline: hashed TF-IDF over the same 754 messages retrieves a thread-mate at 8.57x chance, and 92% of messages are one-shot linearly separable. The measurement code from that part (Fisher separability, RID, margin distributions) is reused unchanged here so the numbers stay on one scale.

This part replaces vocabulary with grammar and measures the same things.

Reed–Kellogg diagrams are a dependency grammar

Subject and predicate on the baseline, objects after the verb, modifiers on slanted lines below. A dependency parser produces the same object in machine-readable form: every token points at its syntactic head, and the root points at itself.

  if    SCONJ  mark    -> are
  you   PRON   nsubj   -> are
  are   AUX    advcl   -> read
  ...
  read  VERB   ROOT    -> read   <-- ROOT
  this  DET    det     -> message
  very  ADV    advmod  -> important
  important ADJ amod   -> message
  message NOUN dobj    -> read

Four descriptors, deliberately separated

Each keeps a different slice, so the results can say which part of “structure” carries the signal:

descriptor	keeps	discards
WL subtree hashes	subtree structure + (POS, dep) labels	all vocabulary
Laplacian spectrum	pure graph shape	labels and vocabulary
Role skeleton	the subject–verb–object spine	modifiers, vocabulary
Tree stats	depth, branching, arc length	nearly everything

In Weisfeiler–Lehman each token starts labelled (POS, dep) rather than by its word. Each round replaces a label with a hash of itself plus the sorted multiset of its neighbours’ labels, so after k rounds a label encodes the k-hop neighbourhood. Sorting the neighbours is what makes it canonical: “the very important message” and “the important very message” produce identical hashes, which is correct, since they are the same diagram.

The Laplacian spectrum is included partly to answer an objection. Fisher separability is defined through an inner product, and a graph does not have one, so the question cannot be posed on a dependency tree directly. Eigenvalues of the normalized Laplacian are a vector, and a similarity-invariant signature of the graph’s shape.

Separability

English sentence shapes are monotonous. Across 4,773 sentences there are 91 distinct role skeletons, the top 10 cover 76%, and the entropy is 4.36 bits, or about 21 effective shapes. VERB:dobj+nsubj alone accounts for 17.6% of sentences.

On that basis I expected pure structure to lose on every measure. It did not:

representation	dim	separability	RID
lexical (TF-IDF baseline)	512	0.8955	15.29
WL structure (no words)	512	0.9090	14.61
Laplacian spectrum	16	0.0000	3.21
role skeleton	512	0.2525	9.75
tree stats	5	0.0000	5.44
lexical + WL	1024	0.9205	15.02

WL hashes contain no vocabulary — a test asserts that two sentences differing only in their words hash identically — and they score 0.9090 against TF-IDF’s 0.8955.

The 21-shape ceiling applies to the global skeleton, and WL does not measure the global skeleton. Two rounds capture local subtree neighbourhoods, so what varies between messages is which small structures appear and in what proportion. The descriptor that does measure the skeleton directly, role_skeleton, scores 0.2525, which is what the ceiling predicts.

The Laplacian spectrum is last in the table. A 20-node tree’s normalized spectrum carries little information, and pooling to mean±sd across a message removes most of what is left.

Retrieval reverses the order

Same representations, scored on retrieving a thread-mate:

	separability	thread retrieval
lexical	0.8955	8.57×
WL structure	0.9090	2.42×

Structure is as distinguishable as vocabulary and much less semantically organized. Combining them does not help either; every structural addition lowered retrieval:

	thread lift	vs baseline
lexical alone	8.57	—
+ Laplacian spectrum	7.36	−14%
+ WL	6.57	−23%
+ lexicalised arcs	6.22	−27%
+ graphlets (paths, siblings)	5.47	−36%

Pooling was the other candidate explanation — squashing every arc in a message into one bag destroys subgraph identity, so perhaps the representation was fine and the aggregation was wrong. Querying with individual sentences instead of whole messages, max-sentence scoring came out worse than pooling for four of five representations.

Authorship and anomaly

Leave-one-out nearest centroid across 101 mailboxes, majority-class baseline 0.0743:

representation	accuracy	lift
lexical	0.3196	4.30×
lexicalised arcs (word + dep)	0.2056	2.77×
WL structure (no words)	0.1512	2.04×
role skeleton	0.0146	0.20×
Laplacian spectrum	0.0106	0.14×

15% accuracy across 101 authors with no vocabulary at all is 2x the baseline. The signal sits in which constructions a person uses; spectrum, role skeleton and tree stats all score below the rate you get by always guessing the most prolific author.

Ranking messages by distance from the corpus centroid in shape space turns up start date : 4/14/01 ; hourahead hour : 21 ; no ancillary, which is machine-generated schedule data and structurally unlike prose. The score correlates −0.587 with sentence count, so roughly a third of it is brevity rather than construction. Not corrected yet.

The space

Every dot is one sentence, placed by the shape of its dependency tree with vocabulary removed. Colouring by similarity to the query separates a near band; colouring by source message does not.

loading 4,773 sentence points…

Colour by

Similarity to querySource messageMessage length

Selected

Click a point in the plot.

Spin

Drag to rotate. Click a point to inspect it.

The query sentence is “i called you last nite re: roi model, but only got the answering machine.” Its six nearest neighbours in the full space are a legal disclaimer, a note about buying a coffee table, and a request for a fax number, at cosine 0.503–0.516.

Three axes hold 13.4% of the variance

The plot above shows under a seventh of the structure. Where the rest of it goes:

Variance per principal component

loading…

Grand tour

A continuously moving 2D projection of all eight components. Structure that lives in dimensions 4–8 appears and vanishes as the projection sweeps past it.

Speed

Set to 0 to hold one projection still.

Colour

Similarity to querySentence length

Named axes

Nobody can say what PC4 is. These five are measurable properties of a sentence diagram, so a line crossing them means something you can read.

Highlight

All sentencesQuery's neighboursDeepest 5%

The spectrum has no elbow: 6.2%, 4.3%, 2.9%, decaying smoothly to 1.4% at PC8, with eight components holding 22.8% between them. A low-dimensional surface observed through noise produces a sharp drop followed by a flat tail. Smooth decay across eight components means the variance really is spread out.

The grand tour sweeps a 2D window continuously through all eight components, so clusters invisible in PC1–PC3 appear and disappear as it turns. Every static projection is a choice about which directions to drop.

Principal components are directions of variance, and PC4 has no name. The parallel-coordinate view uses five measurable properties of a diagram instead. Highlighting the query’s neighbours shows what they share: middling token count, shallow depth, low branching. They are structurally unremarkable sentences, which is why they are near each other, and why that says nothing about what they are about.

Summary

Across two corpora, three labels and fourteen representations, structure adds distinguishability and subtracts semantic organization. That held after correcting the IDF asymmetry and after removing pooling as an explanation. Structural representations suit anomaly detection and authorship, and do not suit a topical index.

Part III measures something a vector cannot express at all, and the ranking there comes out differently.

All measurements use the same deduplicated 754-message, 4,773-sentence corpus as Part I, with seed 20260807; the result tables above are the published record.