A Lovász Theta Parameter and Theta Body for Signed Graphs
arXiv:2608.01716
2026
Architecture
2 ideas extracted · analyzed Aug 31, 2026
What the math gives to ML
The paper develops a Lovász-type geometric representation for signed graphs using unit vectors and an orthogonal involution, whose fixed and anti-fixed subspaces encode switching behavior. This structure transfers naturally to signed graph neural networks: hidden states can be decomposed into switching-invariant and switching-odd channels, yielding exact gauge-equivariant message passing. The associated prescribed inner-product geometry also gives a differentiable embedding regularizer for signed relations. The extracted material does not expose enough of the full two-matrix SDP to reproduce the complete theta-body hierarchy, so the most reliable experiments target the involution and spherical geometry.
Ideas from this paper
Unverified
2026
Replace a conventional signed-graph message-passing layer with two coupled feature channels: a fixed channel invariant under switching and an anti-fixed channel that changes sign under switching. Unsigned aggregation updates invariant features, while signed aggregation updates anti-invariant features, implementing the paper's sphere-plus-involution representation at the hidden-state level.
Useful6/10
Difficulty4/10
Novelty5/10
Unverified
2026
Use the Lovász-style prescribed inner product as a differentiable regularizer on node embeddings. Positive and negative signed relations are compared through the identity or the involution respectively, encouraging a representation whose geometry respects signed colouring constraints and remains invariant to switching gauges.
Useful5/10
Difficulty3/10
Novelty6/10