Graph Structure As Transformer Context

Summary

This page is the synthesis handle for a narrow design question: how should a mostly standard Transformer receive graph structure as context, especially for Kubernetes OTEL Control Gym?

The local answer is not “use a graph Transformer” as a single category. The useful design space is a set of graph-context interfaces:

• pairwise structural attention bias;
• explicit node and edge tokens;
• reversible graph serialization or graph-to-sequence traversal;
• learned graph-token vocabularies;
• visibility masks or sparse relation masks when a sourced baseline is added.

These interfaces can make graph structure visible to a Transformer, but they are not by themselves evidence for an action-conditioned world model. The OTEL target remains:

observation + graph context + action/control input
  -> next observation + reward/label

Mechanism Map

Pattern	Main source	How graph structure enters the Transformer	OTEL adaptation	Main risk
Pairwise attention bias	Graphormer	Shortest-path distance, degree/centrality, and edge-path features become attention-bias terms.	Bias attention by service distance, dependency direction, edge type, and call-path structure.	Strong graph prior, but modifies attention and has quadratic scaling pressure.
Node and edge tokens	TokenGT	Nodes and edges are ordinary tokens; endpoint identifiers and type identifiers expose incidence.	Services/resources become node tokens; directed dependencies become edge tokens; action targets can point to tokens.	Identifier stability under topology drift, service renames, autoscaling, and ephemeral Kubernetes objects.
Reversible graph serialization	GraphGPT	Eulerian or semi-Eulerian paths serialize nodes, edges, and attributes into a reversible sequence.	Serialize whole service graphs, ego-subgraphs around affected services, trace-induced subgraphs, or action-targeted subgraphs.	Path stochasticity and subgraph sampling can disrupt temporal alignment and incident localization.
Reversible serialization plus BPE	Graph Tokenization	Frequency-guided graph serialization plus BPE turns recurring substructures into discrete graph tokens.	Learn reusable service-topology motifs such as fan-out, queue, cache, database dependency, or rollout target neighborhoods.	Continuous telemetry and timestamps still need typed numeric/time-series channels.
Learned graph-token vocabulary	GQT	A graph-specialized tokenizer learns quantized hierarchical tokens before Transformer processing.	Use as an optional graph-front-end for service topology and local neighborhoods.	Not the purest no-GNN path: the tokenizer can use graph-specialized machinery and may hide rare operational edges.
Visibility or adjacency mask	Winning the L2RPN Challenge	Grid adjacency constrains which power-grid elements attend to each other inside a graph-structured policy/value model.	Use visibility masks for physically or operationally reachable service/resource neighborhoods before action-effect prediction.	Domain-specific policy evidence; not a general graph tokenizer or proof of graph-context transfer.
Intervention-derived influence graph	Guided Machine Learning for power grid segmentation	Simulator interventions define a directed weighted graph over line-flow variables before clustering.	Use controlled rollouts or incident/action logs to derive effect graphs, then compare them with service topology.	Representation evidence; not a Transformer architecture or policy benchmark.
Heterogeneous domain graph	Graph Neural Networks for Transmission Grid Topology Control	Separates current and potential busbar connectivity to avoid hiding action-relevant topology information.	Distinguish current service dependencies from possible routing/deployment/control targets.	Power-grid GNN evidence; the Transformer interface still needs a tested token/bias design.
Line-graph local observation encoder	Graph-based distributed RL	Converts grid observations into a homogeneous line graph so a shared GNN enriches each line agent’s local view.	Build action-targeted local graph views for subcontrollers.	GNN policy evidence; no Transformer interface or learned transition rollout.
Graph action/risk surrogate	Soft-label topology actions, Gibbs priors, and Varying Grid Topology	Graph encoders help rank candidate topology actions or predict post-action overload risk.	Use graph context to score candidate remediations before expensive simulation or live execution.	Mostly GNN/surrogate evidence; multi-step action-conditioned Transformer world models remain untested.

Cell-Complex Boundary

Topological Neural Operators is not a Transformer graph-context method, but it sharpens the boundary for graph time-series interfaces. Some physical quantities naturally live on vertices, edges, faces, or volumes, and their interactions are governed by incidence, codifferential, Hodge, and harmonic operators rather than arbitrary node-feature mixing. For power-grid, robotics, or operational telemetry experiments, this is a warning against flattening every structured quantity into anonymous channels: the model interface should preserve typed support, directionality, and action affordances when those structures determine future-state dynamics.

OTEL Graph Time-Series Contract

For k8s-otel-control-gym, graph structure SHOULD be treated as context, not as an anonymous channel order. The minimum model input contract is:

graph segment:
  graph.json or topology snapshot
  service/resource metadata
  edge type, direction, protocol, endpoint, and ownership metadata
 
observation segment:
  node_features.parquet time patches
  edge_features.parquet time patches
  selected event/log/trace streams
 
action segment:
  action_type
  target_service or target_edge
  parameters / control input
  status, precheck, postcheck
 
target:
  next node/edge observations
  reward
  labels or diagnosis fields

The model can then be tested on whether graph context improves action-effect prediction, not merely passive forecasting.

Recommended Baselines

The first k8s-otel-control-gym model suite SHOULD compare graph-context interfaces under matched data, context length, and compute:

1. No-graph / ID-only baseline. Flatten node and edge observations with service IDs only. This proves whether graph structure is actually helping.
2. TokenGT-style node/edge tokens. Make services/resources node tokens and directed dependencies edge tokens. Add time patches and action/control-input tokens explicitly.
3. Graphormer-style attention bias. Keep the token layout simple but add directed shortest-path distance, dependency direction, edge type, and action-target relation as pairwise biases.
4. Graph serialization baseline. Serialize graph snapshots or subgraphs with GraphGPT/Graph Tokenization-style traversal, then interleave telemetry and action segments.
5. Learned graph-tokenizer front-end. Try a GQT-like vocabulary only after the simpler baselines establish what graph details must be preserved.

The pragmatic first implementation should be a hybrid of explicit node/edge tokens plus relation biases. It keeps the Transformer ordinary enough for standard sequence tooling while making service topology visible before investing in learned graph vocabularies.

For power-grid or OTEL graph experiments, include a direct message-passing baseline such as Graph Neural Solver or LEAP-style models when applicable. This tests whether Transformer graph-context interfaces beat a domain-specific graph neural surrogate, but it should not be counted as Transformer evidence.

IO-Aware GNN Layers makes that direct-GNN baseline a performance-hygiene requirement rather than a throwaway comparison: if the baseline uses slow DGL/PyG composition that materializes edge-wise tensors, it may be measuring framework overhead more than the value of message passing. For OTEL experiments, report wall-clock latency, peak memory, preprocessing/reordering cost, graph degree distribution, and whether the GNN layer used fused attention, degree-aware reductions, cached cuSPARSE, or default framework kernels.

Action-Conditioned Boundary

This source cluster is graph-learning or graph-context evidence. It does not by itself test controlled DevOps trajectories, interventions, rewards, or counterfactual rollouts.

That boundary matters. A model that encodes the service graph well is still only a graph-aware passive dynamics model until it receives logged actions and is evaluated on:

• next node/edge feature prediction after an action;
• action delta versus NOOP;
• candidate-action ranking by reward;
• counterfactual prediction under alternative actions;
• closed-loop regret or recovery quality on the live stand.

For a non-OTEL graph-control precedent, see Grid2Op: graph-structured numeric observations, topology/control inputs, simulator-backed next states, and safety/cost outcomes. The transferable point is the action-conditioned graph contract, not the power-grid domain itself.

Graph context should distinguish physical topology from functional influence graphs. The latter may group non-adjacent components and can be more relevant for action-effect prediction, but it depends on the simulator, intervention set, or incident/action logs used to derive the graph.

The fresh Grid2Op papers add a second warning: graph context must preserve action affordances, not only current adjacency. A representation that only says which objects are connected now can omit which objects could become connected after a busbar/topology action. For OTEL, the analogous distinction is current dependency topology versus possible deployment, routing, scaling, rollback, feature-flag, or traffic-shaping targets.

Recent Grid2Op graph papers also disagree on the best representation route for busbar/action-affordance information: heterogeneous current/potential connectivity versus homogeneous line-graph preprocessing. Treat this as a benchmarked design choice, not a settled rule.

Relation To Foundation TSFM Agenda

Agenda slot	Verdict	Evidence	Missing pieces
Context interface	partially closes	The source cluster gives concrete ways to encode graph structure as Transformer context.	Needs an OTEL schema that joins graph context with observation windows, events, and action history.
Native multivariate encoding and high-channel scaling	adjacent	Node/edge tokens, graph serialization, and graph-token vocabularies avoid flattening service telemetry into anonymous channels.	Needs graph time-series experiments with topology drift, missing streams, and high-cardinality telemetry.
Control and counterfactuals	insufficient evidence	Graph context is necessary for action-conditioned observability world models.	Needs observation + graph + action/control input -> next observation/reward experiments.

Open Questions

• Which interface wins under matched compute for OTEL episodes: node/edge tokens, pairwise attention bias, graph serialization, learned graph tokens, or a hybrid?
• Which IO-aware direct-GNN baseline is the right matched-compute comparator for each graph-context interface: cached SpMM, fused CSR graph attention, degree-aware reductions, or block-sparse Tensor Core attention?
• How should time be represented: one graph-token set per timestep, temporal patches per node/edge token, or a flattened sequence over (time, graph element) pairs?
• What identifier scheme survives service renames, topology changes, autoscaling, and ephemeral Kubernetes objects?
• Should the graph tokenizer learn motifs from one OpenTelemetry Demo graph, from many generated graph variants, or from external production topologies?
• How should graph time-series benchmarks distinguish physical topology from intervention-derived influence or effect graphs when they disagree?
• How do we test that graph compression does not erase rare but intervention-relevant edges?

Related Pages

• Kubernetes OTEL Control Gym
• Observability Time Series
• High-Dimensional Time Series Forecasting
• Latent Tokenization
• Tokenizer Transfer
• World Models
• Foundation Time-Series Model Research Agenda
• Graph Observability Benchmarks
• Grid2Op