Interpreting Supervised Pairwise Graph Representations: Local Evidence, Confounding, and Provable Post-hoc Correction

Ilya Brekin; Ariela Moldavskaya; Elina Sidorova; Ural Valeev

cs.LGOct 23, 2026

Interpreting Supervised Pairwise Graph Representations: Local Evidence, Confounding, and Provable Post-hoc Correction

Authors: Ilya Brekin, Ariela Moldavskaya, Elina Sidorova, Ural Valeev

Organizations: HSE University, Moscow, Russia · Technion – Israel Institute of Technology, Technion City, Haifa 3200003, Israel · Lomonosov Moscow State University, Moscow, Russia · Ufa University of Science and Technology, Ufa, Russia

Abstract

Supervised pairwise graph representations convert pairwise predictive relations into sample-specific graphs, but graph-level accuracy does not by itself show that higher-order topology carries the signal. In a controlled Transformer error-detection task, supervised pairwise graphs outperform attention-as-adjacency (ROC-AUC $0.839$ versus $0.559$ ; the comparable no-confidence pair is $0.687$ versus $0.559$ ), but their apparent advantage over model confidence disappears after controlling for sequence length, which is almost perfectly recoverable from the pooled hidden state ( $R^2=0.9995$ ). On published HCP Emotion ensemble graphs, signed node aggregation already acts as an ensemble of supervised pairwise predictions. Edge magnitude alone is near chance; topology-aware augmentations change ROC-AUC by at most $0.004$ , with only sign-separated degree showing small positive changes across all tested graph sizes, while a validation-tuned three-layer GCN provides no measurable improvement over the signed node-summary baseline. A Fisher post-hoc corrector satisfies its distribution-agnostic guarantees across the evaluated feature representations and remains stable under reduced labelled budgets; in a near-error-free fMRI calibration regime the bound correctly becomes statistically uninformative. A separate cross-attention analysis identifies a redundant reversal circuit and downstream EOS-timing and copy failures. Higher-order topology should therefore be credited only after local supervised evidence and recoverable nuisance variables have been excluded.

Figures & tables

$d$	$h$ searched	$h^{\prime}$ searched	$h$ chosen	$h^{\prime}$ chosen
34	8,12,16	8,12	8	8
50	12,16,24,32	8,16	12	8
100	16,24,32,48	8,16,24	48	16
200	24,32,48	8,16,24	32	16

Table 1: Validation-selected GCN dimensions.

Method	Confidence	ROC-AUC
Softmax confidence	—	0.799
LogReg on raw hidden states	No	0.686
LogReg on flat graph features	No	0.699
LogReg on graph features + confidence	Yes	0.841
GNN on raw-attention graphs	No	0.559
No-confidence synolitic GNN	No	0.687

Table 2: Setup 1 principal test ROC-AUC results (

N_{\rm test}=2000

; base exact-match accuracy

72.4\%

Model / representation	Readout	Confidence	ROC-AUC
LogReg on flattened graph features	Flatten	No	0.699
LogReg on mean/max-pooled graph features	Mean/max pooling	No	0.634
No-confidence synolitic GNN	Flatten	No	0.687
Synolitic GNN ensemble	Flatten	Yes	0.839
Mean-pool GNN	Mean pooling	Yes	0.834
LogReg on graph features + confidence	Flatten	Yes	0.841

Table 3: Readout and architecture ablations in Setup 1.

Statistic	Correct	Error	Difference	$p$ -value
Mean strength	4.376	4.131	+0.246	$6.7\times 10^{-15}$
Max strength	30.14	25.97	+4.17	$3.0\times 10^{-18}$
Mean closeness	0.242	0.199	+0.043	$7.3\times 10^{-20}$
Mean betweenness	0.0103	0.0084	+0.0019	$3.6\times 10^{-21}$
Mean edge weight	0.778	0.762	+0.016	$6.7\times 10^{-15}$
Number of decisive edges	168.8	105.3	+63.4	$1.2\times 10^{-10}$

Table 4: Correct versus erroneous Transformer predictions.

Feature	Test ROC-AUC
value (raw hidden-state coordinate)	0.714
degree	0.670
strength	0.674
closeness	0.649
betweenness	0.629
all five features (flat)	0.696

Table 5: Setup 1 node-feature ablation.

Predictor	Test ROC-AUC
Length only, LogReg	0.628
Softmax confidence	0.799
Confidence + length, LogReg	0.840
Synolitic GNN ensemble	0.839

Table 6: Pooled Transformer comparisons.

Paradigm	Duration	No. blocks	After cropping
Emotion	0.941	0.500	0.500
Social	0.774	0.528	0.500
Motor	0.500	0.500	0.500
Language	0.848	1.000	1.000 (excluded)

Table 7: ROC-AUC of trivial structural predictors.

Added features	$d=34$	$d=50$	$d=100$
Magnitude centralities, dense	$-0.000$	$-0.002$	$-0.000$
Magnitude centralities, top 20%	$-0.001$	$-0.002$	$-0.000$
Magnitude centralities, top 10%	$+0.000$	$-0.002$	$+0.001$
Sign-aware centralities	$-0.002$	$+0.004$	$-0.000$
Sign-separated degree	$+0.003$	$+0.003$	$+0.001$

Table 8:

\Delta

ROC-AUC relative to signed mean-incident-weight LogReg; mean of three random region draws.

Figure 1: Setup 2 dimensionality ladder. For $d\in\{34,50,100,200\}$ , points summarize repeated random region subsets; the complete-graph result at $d=379$ is reported in the text and is not shown in this figure.

Feature $\Phi$	Accept bound	Accept empirical	Reject bound	Reject empirical
GNN score	0.650	0.704	0.722	0.821
Confidence	0.512	0.559	0.722	0.826
Raw $X$ (Fisher)	0.350	0.436	0.692	0.792
Graph topology (Fisher)	0.279	0.332	0.692	0.792
Graph summary (Fisher)	0.151	0.269	0.692	0.832

Table 9: Setup 1 Fisher corrector at

\Delta=0.8

Figure 2: Setup 1 corrector versus labelled correction budget. Empirical performance is stable from 25 examples; theoretical bounds tighten with larger calibration samples.

Figure 3: Setup 1 corrector trade-off across confidence parameter $\Delta$ . Empirical accept/reject rates consistently satisfy the corresponding lower bounds.

Graph Representation Learning

Graph representation learning develops methods for encoding nodes, edges, and whole graphs for prediction, comparison, and transfer.

See all 305 papers

Higher-Order Positional Encodings for Graph Representation Learning
Oct 1, 2026Caleb Stam, Aagrim Hoysal, Sanjukta KrishnagopalGraph Representation Learning Positional Encoding
University of California, Santa Barbara
Topology-induced Operators Reveal Complementary Graph Representations without Training
Sep 8, 2026Meng Qin, Jinqiang Cui, Hongwei Zheng +2Graph Representation Learning Graph Embedding
Department of Strategic & Advanced Interdisciplinary Research, Pengcheng Laboratory (PCL), Shenzhen, Guangdong, China. · Beijing Academy of Blockchain and Edge Computing, Beijing, China. · LMIB, NLSDE, and School of Artificial Intelligence, Beihang University, Beijing, China. +1
When Graph-JEPA Learns the Wrong Thing: Diagnosing and Repairing Category-Conditional Collapse
Aug 20, 2026Gollam Rabby, Sören AuerRepresentation Collapse Joint-Embedding Predictive Architecture
L3S Research Centre, Leibniz University Hannover, Hannover, Germany · TIB Leibniz Information Centre for Science and Technology, Hannover, Germany

Oct 1, 2026J/K move · Enter open · S save

Higher-Order Positional Encodings for Graph Representation Learning

Caleb Stam, Aagrim Hoysal, Sanjukta Krishnagopal

University of California, Santa Barbara

Graph Representation Learning Positional Encoding Graph Transformer Topological Representation Learning Topological Data Analysis Graph Positional Encoding

Open paper AskPDF arXiv

Many real-world systems exhibit higher-order interactions among groups of entities that cannot be captured by pairwise relationships alone. Graph Transformers and Graph Neural Networks increasingly rely on positional encodings to enrich graph representations, yet existing positional encodings are computed solely from the original graph and therefore cannot directly capture observed higher-order interactions. Topological Deep Learning addresses this limitation by lifting graphs to simplicial complexes, but typically requires performing message passing or attention on higher-order neural network representations. We introduce a representation learning paradigm that enriches graph representations with higher-order topology through positional encodings, enabling standard graph learning models to exploit lifted incidence structure without modifying the backbone. We derive a theoretical characterization of the expressivity of higher-order positional encodings, proving that node-level operators induced by higher-order lifts can mix graph Laplacian frequencies in ways that scalar graph spectral filters cannot. Guided by this theory, we instantiate higher-order positional encodings using Hodge Laplacians derived from clique complexes. Experiments with Graph Transformers on ZINC and controlled synthetic benchmarks demonstrate improvements in predictive performance, while a fixed-1-skeleton experiment shows that the pipeline can transmit higher-order information when cells are supplied independently of the graph. Together, our results establish higher-order positional encodings as a principled bridge between graph positional encodings and topological deep learning.

Abstract

Graph Representation Learning

Explore similar work

Higher-Order Positional Encodings for Graph Representation Learning

Topology-induced Operators Reveal Complementary Graph Representations without Training

When Graph-JEPA Learns the Wrong Thing: Diagnosing and Repairing Category-Conditional Collapse