What does an HDC graph encoder remember? Reviewing GraphHD-Order

How much graph structure does a classifier need?

Every graph encoder is a theory about what can safely be forgotten. In Hyperdimensional Computing (HDC), that choice is unusually visible: we decide which properties become hypervectors, which relationships are bound together, and which collections are bundled into one representation. Preserve too little, and graphs with different meanings can look alike. Preserve too much, and the encoder spends time on distinctions the classifier may never use.

In Beyond PageRank in GraphHD, Ignacio Sica and Gustavo Vazquez examine this trade-off by simplifying an existing HDC graph classifier.¹ The published GraphHD algorithm assigns hypervectors to nodes according to centrality rank, binds the endpoints of every edge, and bundles those edge representations. The paper’s GraphHD-Order variant removes endpoint binding and bundles centrality-based node hypervectors directly.

Across six topology-only benchmarks, the paper reports that GraphHD-Order often remains close to GraphHD while reducing runtime. That result is interesting, but narrower than “edges do not matter.” GraphHD-Order still uses edges indirectly because node centrality is calculated from graph topology. The real question is whether the classifier needs an explicit summary of which structural roles connect, after those roles have already been calculated.

We’ll look at what the published encoders remember, what the experiments establish, and why differences between the paper and its supplementary implementation leave the central result open to more than one interpretation.

What the encoders remember

All three encoders begin by calculating a centrality score for every node. That step has already compressed the graph. A score can tell us that a node is prominent, peripheral, or positioned between other nodes, but it does not preserve a complete neighborhood or reconstruct the adjacency matrix.

The encoders differ in what they do with those scores next.

Encoder	Node representation	What is bundled	Published representation retains
GraphHD	Independent hypervectors assigned by centrality rank	Bound endpoint pairs for every edge	Which centrality ranks tend to connect
GraphHD-Level	Correlated level hypervectors from centrality values	Bound endpoint pairs for every edge	Connected centrality levels and numerical proximity
GraphHD-Order	Correlated level hypervectors from centrality values	Node hypervectors directly	The distribution of centrality levels

Original GraphHD² orders nodes by PageRank and assigns an independent random hypervector to each position. If $r(v)$ is the rank of node $v$, an edge between $u$ and $v$ is represented by binding their rank hypervectors. The graph bundles all of those edges:

$$\mathbf{h}_{G}^{\text{GraphHD}} = \bigoplus_{(u,v)\in E} \left( \mathbf{h}_{r(u)}\otimes\mathbf{h}_{r(v)} \right).$$

This behaves like a compressed tally of endpoint-rank pairs. It can distinguish a graph where highly central nodes tend to connect to one another from one where they connect mostly to peripheral nodes. It still does not preserve node identities or the complete wiring pattern.

GraphHD-Level changes the node mapping. Rather than treating adjacent ranks as unrelated, the published algorithm quantizes the centrality value $c(v)$ to a correlated level hypervector $\mathbf{h}_{q(c(v))}$. Nearby values should therefore receive similar representations. It retains GraphHD’s endpoint binding:

$$\mathbf{h}_{G}^{\text{Level}} = \bigoplus_{(u,v)\in E} \left( \mathbf{h}_{q(c(u))}\otimes\mathbf{h}_{q(c(v))} \right).$$

GraphHD-Order uses the same published value-to-level mapping but removes edge encoding:

$$\mathbf{h}_{G}^{\text{Order}} = \bigoplus_{v\in V} \mathbf{h}_{q(c(v))}.$$

Once centrality has been calculated, this changes the encoding loop from processing edges to processing nodes. The paper describes that cost as $O(|E|)$ versus $O(|V|)$. Centrality computation itself is outside that comparison and may dominate the pipeline for path-based or iterative measures.

Marginal versus joint structural information

We can make the difference more precise by treating each encoded centrality level as a category. Let $n_i$ count nodes at level $i$, and let $m_{ij}$ count edges whose endpoints occupy levels $i$ and $j$:

$$n_i = \left|\{v\in V:q(c(v))=i\}\right|, \qquad m_{ij} = \left|\{(u,v)\in E:q(c(u))=i,\ q(c(v))=j\}\right|.$$

GraphHD-Order behaves like a marginal profile over the $n_i$ counts. GraphHD and GraphHD-Level behave like joint endpoint profiles over the $m_{ij}$ counts. The paper makes the same distinction in its discussion.

Question	Marginal profile	Joint endpoint profile
What is counted?	Nodes at each centrality level	Edges between pairs of centrality categories
Retained by	GraphHD-Order	GraphHD and GraphHD-Level
Can it notice rewiring that preserves node counts?	No	Sometimes, when endpoint-pair counts change
Can it reconstruct the complete graph?	No	No

“Joint” should not be confused with “complete.” Bundling discards which particular nodes contributed an endpoint pair. Two non-isomorphic graphs with the same endpoint-level counts can receive the same coarse structural summary.

This also explains why GraphHD-Order is not topology-free. Its information path is:

$$\text{edges} \longrightarrow \text{node centralities} \longrightarrow \text{centrality-level counts}.$$

GraphHD consults adjacency once more after centrality has been calculated:

$$\text{edges} \longrightarrow \text{node centralities} \longrightarrow \text{adjacent centrality-pair counts}.$$

The comparison is therefore about whether that last layer of relational information improves classification—not whether one encoder has structure and the other does not.

What the authors tested

The paper combines three encoders with six centrality choices: PageRank, degree, closeness, betweenness, Katz, and eigenvector centrality. It evaluates them on six public TUDataset benchmarks.³

Dataset	Graphs	Classes	Average nodes	Average edges	Prediction task
DD	1,178	2	284.32	715.66	Protein structure classification
ENZYMES	600	6	32.63	62.14	Enzyme class prediction
MUTAG	188	2	17.93	19.79	Mutagenicity prediction
NCI1	4,110	2	29.87	32.30	Anticancer activity classification
PROTEINS	1,113	2	39.06	72.82	Protein structure classification
PTC_FM	349	2	14.11	14.48	Carcinogenicity prediction

The encoders use connectivity alone. Available node labels, edge labels, and continuous attributes are excluded to remain compatible with the original GraphHD baseline. This is a controlled test of topology-only encodings, not a feature-complete biochemical classifier.

The paper describes 10,000-dimensional bipolar hypervectors, element-wise multiplication for binding, and sum-plus-sign bundling. Training bundles encoded graphs into one prototype per class, and prediction chooses the prototype with the highest cosine similarity. It reports 100 random 80/20 repetitions, weighted F1-score, accuracy, and CPU runtime.

Because many differences are small, the paper also describes a paired Wilcoxon signed-rank test with Holm–Bonferroni correction. It says all methods share the same split within a repetition. That pairing matters, and we’ll return to it when we compare the protocol with the released code.

This is best read as an ablation within the GraphHD family. The study does not re-run graph kernels, graph neural networks, or newer HDC graph methods under the same protocol.

The strongest reported results

Three findings carry most of the paper’s weight.

First, changing centrality usually produces small reported changes in GraphHD’s weighted F1-score. Table 3 summarizes a mean absolute difference of 0.010 from PageRank, a maximum of 0.034, and 7 significant comparisons among 28. Those statistics cannot be independently reconstructed from the released aggregate data, and the paper contains two relevant inconsistencies: its PTC_FM discussion reports a 0.032 advantage for degree while Table 2 rounds both degree and PageRank to 0.572, and its DD footnote omits closeness even though Table 2 reports a closeness result. The supplementary CSV also contains the DD closeness runs.

The safe conclusion is modest: the paper reports no centrality measure that wins consistently, while centrality choice changes runtime substantially. Degree is the clearest inexpensive candidate. Claims about Katz and eigenvector need more caution because of the released implementation discussed below.

Second, GraphHD-Level is the clearest negative result. Table 4 reports it as significantly worse than GraphHD in 32 of 34 evaluated cells, with no significant improvement and a mean weighted F1 difference of −0.066. Correlating nearby centrality values did not improve this experiment. That result applies to this design and protocol; it does not show that level hypervectors are generally unsuitable for graphs.

Third, GraphHD-Order is the promising simplification. Table 4 reports no significant difference from GraphHD in 22 of 34 cells, a significant loss in 12, no significant wins, and a mean difference of −0.013. The surrounding prose says 36 cells, but the table caption, omissions, and category totals all say 34.

The paper also reports speedups of roughly 1.1× to 3×. DD is the most striking case: it contains the largest graphs, averaging 284 nodes and 716 edges, and GraphHD-Order improves the reported mean F1-score across the available centralities. The authors suggest that bundling many edge hypervectors may saturate GraphHD’s representation and wash out useful differences.

That explanation is plausible, but it is not tested directly. DD could also favor broad centrality profiles, or GraphHD’s endpoint-pair signal could vary within each class rather than between classes. A dimensionality or graph-density sweep would help separate those explanations.

What the result may actually tell us

If we take the published algorithms at face value, GraphHD-Order’s result says something useful about task-relevant compression. The topology has already been compressed into centrality values. On many tested configurations, explicitly recording which centrality roles connect adds little reported class signal beyond the marginal profile.

That does not make the representations equivalent. GraphHD can react when rewiring changes endpoint-role counts; GraphHD-Order cannot react when the centrality-level profile remains unchanged. Similar classification scores tell us only that the classifier did not benefit reliably from that difference on these tests.

The distinction gives us a practical design hypothesis:

1. Begin with a centrality-profile encoder when the label should remain stable under rewiring that preserves that profile.
2. Add endpoint binding when connections between structural roles may change the label.
3. Use a richer encoder when the task depends on a motif, path, direction, neighborhood composition, or node and edge attributes.

These are application hypotheses, not tasks evaluated by the paper. They should be tested with transformations that hold one structural summary fixed while changing the next.

Which tasks might fit each summary?

GraphHD-Order is the natural first baseline when a class depends on the prevalence of structural roles. A network dominated by hubs can have a different centrality profile from a decentralized or chain-like network even when we ignore the identities of individual nodes. This may be useful for coarse graph retrieval, monitoring broad changes in network organization, or detecting graphs whose role distribution departs from a reference population.

GraphHD becomes more relevant when two graphs can contain similar roles but differ meaningfully in how those roles interact. Hub-to-hub connectivity, core-to-periphery wiring, or an unusual connection between otherwise common roles can change endpoint-pair counts without changing the marginal profile as much. GraphHD still supplies only a coarse relational summary, but it has a basis for noticing that difference.

Task requirement	First representation to test
Broad centrality profile or graph-size baseline	GraphHD-Order
Connections between centrality roles	GraphHD
Numerical proximity plus endpoint relationships	GraphHD-Level as an experiment
Exact motifs, paths, direction, or rich attributes	A richer graph encoder

GraphHD-Level has an intuitive intended niche: a small change in centrality should produce a small representational change while endpoint relationships remain available. The paper does not provide evidence for recommending it, however. Until the algorithm and implementation are reconciled and its quantization choices are tested directly, it is better treated as an unresolved experiment than a deployment choice.

The important point is to begin from the invariance the task needs. If rewiring should leave a label unchanged, GraphHD-Order’s insensitivity may be useful rather than deficient. If rewiring changes the meaning, that same invariance becomes a failure mode.

Evidence limits and reproducibility questions

The most important limitation is uncertainty about which representation produced the reported results. We reviewed the supplementary repository at immutable snapshot 40df6cc ↗ .⁴ Its behavior differs from the published algorithms in several consequential ways.

• centrality.py ↗ implements PageRank, degree, closeness, and betweenness explicitly, then sends every other metric name to degree. In this snapshot, requested Katz and eigenvector centralities are degree centrality.
• encoders.py ↗ implements GraphHD-Order by sorting the nodes and bundling library[0] through library[n-1]. Sorting changes which node receives each hypervector, but it does not change the set included in the final commutative bundle.
• The same file adds node hypervectors to GraphHD’s edge bundle. Its GraphHD-Level implementation maps relative rank to levels, adds node hypervectors, and permutes one endpoint—none of which appears in the published algorithms.

The GraphHD-Order difference can be tested directly. Using one shared library, we ran the released encoder logic on two differently wired six-node graphs with different rank orders. Their GraphHD-Order representations were identical in all 1,000 components. Under the same seed and library, the released GraphHD encoder differed in 271 components. This confirms an invariant already visible in the code: within a repetition, the snapshot’s GraphHD-Order representation depends on node count, not on the centrality values or their order.

The statistical analysis is also difficult to reproduce. experiments.py ↗ draws a split with random_state=None inside each configuration run, while benchmark_parallel.py ↗ dispatches configurations separately. The released code does not show an explicit mechanism for sharing split indices. The results CSV contains one mean, standard deviation, and timing summary per configuration, but not the per-repetition scores or predictions required to reproduce the Wilcoxon tests.

If the published algorithm produced the tables, the experiments may support a centrality-profile representation. If the released implementation produced them, graph size may explain some of GraphHD-Order’s performance. Until the artifacts are reconciled, the accuracy, significance, and timing values should be treated as results reported by the authors, not independently reproduced evidence for one exact encoder.

The HDC Labs perspective

For us, the paper exposes a fundamental encoder-design question: which distinctions must survive composition for the task to remain solvable?

GraphHD makes the division of labor clear. The encoder determines the geometry of graph representations. Training then bundles those representations into one class prototype, and similarity search can use only distinctions the encoder preserved consistently within each class. A prototype cannot recover structure that the encoder discarded.

Our discussion of holographic hypervectors provides intuition for the authors’ saturation hypothesis. With a plain bundle of near-orthogonal hypervectors, similarity to an individual component decreases roughly as $1/\sqrt{n}$. GraphHD’s bound edges are not necessarily independent, and its sign projection changes the details, so that relationship does not validate the DD explanation. It tells us what to measure: whether larger edge bundles reduce useful class separation.

Our post on permutation makes the complementary point. If position, direction, or traversal order matters, it must receive a distinguishable form before composition. Endpoint binding preserves one coarse association between centrality roles; it does not preserve a path, motif, or exact neighborhood.

The HDC Labs takeaway is not that simpler encoders always win. It is that encoder complexity should earn its place through task-relevant separability. A useful encoder reacts to transformations that should change the label and remains stable under transformations that should not.

Experiments we would run next

The next study should identify why the simpler encoder appears competitive before adding more benchmark rows.

We would begin with a conformance reproduction: implement each published algorithm and centrality measure independently, publish the split indices and seeds, and retain every repetition’s predictions. The released snapshot should be evaluated as a separate implementation rather than assumed to be the published one.

Then we would construct matched graph pairs at three structural levels:

1. Same node count, different centrality profiles: A published GraphHD-Order implementation should distinguish them; the reviewed snapshot should not.
2. Same centrality profile, different endpoint-role counts: GraphHD-Order should remain similar while GraphHD responds.
3. Same profile and endpoint-role counts, different motifs or paths: Both encoders may remain similar, showing when richer structure is needed.

To test saturation, we would vary node count, density, bundle cardinality, and hypervector dimension. Alongside F1-score, we would measure class-prototype margins, similarities between unrelated graph hypervectors, and retained edge signal before and after sign projection. If increasing dimension or reducing bundle size restores a GraphHD advantage, that would support the authors’ explanation.

Finally, we would add node and edge attributes explicitly and compare the corrected encoders with simple structural baselines, graph kernels, graph neural networks, and newer HDC graph methods such as VS-Graph⁵ under shared splits and hardware. Runtime should be separated into centrality calculation, encoding, prototype construction, and inference.

The goal is not one universally best graph encoder. It is to find the least expensive representation that remains sensitive to the structural changes each task considers meaningful.

Closing position

This paper asks the right question: not simply how much graph structure an HDC encoder can preserve, but whether preserving it improves classification enough to justify the cost. It also reports GraphHD-Level’s negative result rather than hiding it.

GraphHD-Order remains a valuable hypothesis, but the available evidence does not establish it as a replacement for GraphHD. The published algorithm represents a marginal centrality profile; the reviewed implementation represents node count. Those are different claims about what the encoder remembers.

The most useful next question is therefore concrete:

If we rewire a graph while preserving its centrality profile, should its label change?

If not, a correctly implemented GraphHD-Order may be enough. If connections between roles matter, endpoint binding may earn its cost. If the answer depends on a path, motif, direction, or attribute, the task needs a richer encoder than either one.

That is the broader lesson for HDC graph design. Preserve the transformations that matter to the task, ignore those that do not, and test the boundary directly.

Footnotes

1. Ignacio Sica and Gustavo Vazquez, “Beyond PageRank in GraphHD: Centrality Metrics and Efficient Hyperdimensional Encodings” ↗ , CLEI Electronic Journal 29, no. 4 (2026). ↩

2. Igor Nunes et al., “GraphHD: Efficient graph classification using hyperdimensional computing” ↗ , 2022 Design, Automation & Test in Europe Conference & Exhibition (DATE). ↩

3. Christopher Morris et al., TUDataset dataset catalogue ↗ . ↩

4. Gustavo Vazquez, CLEI-2025 supplementary repository at commit 40df6cc ↗ . ↩

5. Hamed Poursiami et al., “VS-Graph: Scalable and Efficient Graph Classification Using Hyperdimensional Computing” ↗ (2025 preprint). ↩