CS Paper Radar

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

Ilya Brekin, Ariela Moldavskaya, Elina Sidorova, Ural Valeev

cs.LG ·submitted 2026-10-23 13:32 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Evaluating invariance training with certified answer-changing controls in neural graph algorithms

cs.AI ·2026-11-18 ·Zhe Dong, Fang Qin
similarity 0.59
Abstract · 25 pages, 3 figures, 16 tables

Invariance training aims to make neural algorithmic reasoners robust to answer-preserving input changes and is judged by accuracy and by how rarely such edits change predictions. We ask whether this evaluation detects lost sensitivity to answer-changing edits on minimum spanning trees of synthetic graphs, where both directions can be certified. Attaching a subgraph through one bridge provably preserves every original label. Attaching it through two edges, oracle-selected to change a label, and lowering one weight inside the graph serve as answer-changing controls; a response is a changed prediction on an edge whose label changes. A reproduced graph transformer (GDT) within its published accuracy range changes a provably fixed label on 53.3-65.9% of the 64-vertex graphs it solves exactly after a 64-vertex bridge attachment; removing the connecting edge changes little. With 16-vertex graphs and attachments, three invariance objectives lower GDT violations from 2.91% to 0.52-2.02% of pairs at essentially unchanged accuracy. Training also lowers the response to two-edge attachments from 97.6% to 66.0-79.0%, while the response to in-base weight edits stays near 99.5%. At 64 vertices accuracy also falls, but on 16-vertex bases only the attachment control reveals the loss. A message-passing network loses some attachment response at small penalty weights but gains little invariance. Running the conventionally trained GDT on each biconnected block separately removes all observed violations and keeps accuracy and both responses, so the task does not force the trade-off. Sensitivity checks for trained invariance should include certified answer-changing edits that attach material as the training edits do.

0.30

NodeGround: A Node Classification Benchmark in the Graph Foundation Model Era

cs.LG ·2026-09-30 ·Jinmo Lee, Dooho Lee, Minho Jeong, Jaemin Yoo
benchmarkcode/data similarity 0.59
Abstract

Can a pretrained graph model replace training and tuning a separate predictor for each dataset? Answering this requires evaluating prediction quality alongside computational cost. We present NodeGround, a node classification benchmark that puts graph foundation models (GFMs) and dataset-specific supervised learning under a common evaluation framework. The benchmark spans 51 datasets and evaluates six GFMs alongside 15 supervised methods under two label-availability regimes. Shared data partitions, validation-only model selection, controlled hyperparameter searches, and multiple predictive metrics make comparisons systematic, while workflow measurements account for adaptation, training, tuning, and inference. The results favor carefully tuned graph neural networks overall. GraphPFN reaches third place by Elo when more labels are available, yet its relative strengths vary substantially with dataset properties. Efficiency comparisons further qualify the benefits of pretrained reuse: GVT and GraphPFN appear on the Pareto frontiers when supervised methods are represented by their default and fully tuned configurations. Adding intermediate tuning budgets removes this advantage for GVT and leaves GraphPFN extending the estimated frontier in the label-rich setting alone. Thus, reusing pretrained parameters does not yet provide a broadly reliable route to either stronger predictions or cheaper workflows. We release the evaluation pipeline, run-level records, and an open leaderboard at https://github.com/nums-ai/nodeground.

0.46

Graph Label Alignment: A Diagnostic Atlas for Graph Classification

cs.LG cs.AI ·2026-11-10 ·Neelam Akula, Varun Shiralkar, Murat Kantarcioglu, Baris Coskunuzer
top venuebenchmark similarity 0.58
Abstract · 40 pages

Graph classification benchmarks vary widely in difficulty: some are solved by simple pooled baselines, while others remain challenging for GNNs and graph transformers. We take a data-centric view and ask whether benchmark success is driven by genuine structure--feature reasoning or by label signal already accessible from restricted marginal views. We introduce graph label alignment, a lightweight diagnostic that measures label accessibility through two supervised probes computed without training a graph encoder: structural label alignment (SLA), based on permutation-invariant topological and spectral summaries, and feature label alignment (FLA), based on pooled node features with edges removed. Across real graph classification benchmarks and multiple pooled backbones, the resulting SLA--FLA plane strongly organizes test accuracy, with low-alignment datasets forming a consistent regime where standard pooled pipelines struggle. To probe what lies beyond marginal accessibility, we introduce controlled interaction-dominated stress tests, including heterophilic ego-graphs and synthetic Twins tasks whose structural and feature marginals are matched across classes but whose role--feature couplings differ. These results show that high alignment explains much of easy benchmark performance, while low alignment reveals regimes where success requires preserving structure--feature correspondence beyond standard pooled representations.

0.38

ProtLink: Sequence and Multispecies Graph Context for Protein Interaction Prediction

cs.LG q-bio.MN ·2026-11-07 ·Xingyuan Zhang
similarity 0.57
Abstract · Submitted to AI for Scientific Research at AAAI 2027

Predicting protein-protein interactions (PPIs) from sequence alone is difficult, while known interaction networks may provide informative biological context. We introduce ProtLink, a sequence-conditioned graph-learning framework that combines frozen ESM-2 representations with protein interaction topology and orthogroup-mediated connections between species. We compare sequence-only models, GraphSAGE, a homogeneous graph transformer, and a heterogeneous graph transformer (HGT) for human PPI prediction. In an initial edge-level comparison, three-layer multispecies HGT with ESM-2 650M features achieves an average precision (AP) of 0.980 under random negative sampling, compared with 0.951 for the homogeneous transformer; its AP decreases to 0.878 with two-hop-preferred negatives. In controlled three-seed experiments, three-layer full-graph HGT obtains an AP of $0.9701\pm0.0022$, exceeding an orthogroup-only model ($0.9435\pm0.0094$). The corresponding two-layer comparison shows little additional benefit from non-human PPI edges, consistent with the greater message-passing depth needed to transmit their information. For human proteins excluded from training interactions, multispecies HGT achieves $0.8335\pm0.0094$ AP versus $0.6482\pm0.0052$ for a sequence-only pair model. These results identify the value, depth dependence, and limits of evolutionary graph context while distinguishing prediction of held-out edges from generalization to held-out proteins.

0.20

Graph-Localized Coverage for Conformal Prediction on Inductive Graphs

cs.LG stat.ML ·2026-11-02 ·Jinwen Xu, Qin Lu, Georgios B. Giannakis
similarity 0.57
Abstract

Conformal prediction (CP) provides marginal coverage guarantees, but marginal coverage does not determine where prediction errors occur on a graph. Queries from different graph neighborhoods can exhibit substantially different levels of uncertainty even when aggregate coverage remains near its target. We introduce GLocalCP, an online CP framework for inductive node classification and edge prediction that combines marginal and graph-local calibration with uncertainty-adaptive prediction sets. Specifically, GLocalCP puts forth a novel uncertainty-adaptive nonconformality score that relies on the mutual information obtained from Monte-Carlo (MC) dropout based prediction. Then, it augments a global online threshold with a kernel-based local correction that propagates coverage feedback among similar graph queries. On the theoretical horizon, we establish pathwise $O(N^{-1/2})$ marginal calibration error without exchangeability or stationarity and, for the exact-kernel formulation, an explicit $O(N^{-1/2})$ graph-localized calibration guarantee. Experiments on seven node-classification and seven edge-prediction benchmarks show that similar marginal coverage can conceal substantially different local reliability. Our proposed GLocalCP maintains coverage near the target while consistently reducing graph-local calibration error. Uncertainty scaling in GLocalCP further reduces prediction-set size across all evaluated node and edge datasets while leaving marginal coverage essentially unchanged.

0.20

Self-Supervised Graph Representation Learning for In-The-Wild Wearable and Smartphone based Emotion Recognition

cs.LG cs.AIeess.SP ·2026-08-23 ·Ioannis N. Ziogas, Leontios J. Hadjileontiadis, Ahsan H. Khandoker, Aamna Al Shehhi
published similarity 0.56
Abstract · Published at ICASSP 2025. Copyright 2025 IEEE

Wearable and smartphone-based emotion recognition (WER) remains a challenging setting in affective computing, due to the notorious difficulty and bias associated with in-the-wild label collection. The high inter-and intra-subject emotional variability motivates us to explore WER modeling through graph node classification in a limited resources learning scheme powered by Self-Supervised Learning (SSL) graph masking augmentation tasks. We employ a subgraph sampling approach during training, utilizing labeled and unlabeled data, along with supervised, semi-supervised, and SSL mechanisms in a multi-task inductive graph neural network architecture. Our evaluations on K-EmoPhone through leave-one-group-out cross-validation in the binary arousal and valence tasks yield average accuracy gains of 4.3% and 7.8%, compared to the full resource setting, utilizing only 20% and 25% of the labels, respectively. Our model analysis sheds light on the relation of SSL graph augmentations to emotional arousal and valence and justifies the approach of SSL-driven subgraph training for in-the-wild WER.

0.51

Uncertainty Quantification Is Indispensable for Reliable Connectome-Based Graph Learning: A Narrative Review and Case Study

cs.LG ·2026-10-06 ·Mansooreh Pakravan
similarity 0.56
Abstract

While graph neural networks (GNNs) have shown substantial promise in connectome-based diagnostic classification, deterministic models inevitably suppress pipeline-induced noise and model ambiguities, yielding overconfident predictions. Although uncertainty quantification (UQ) is widely adopted in voxel-level segmentation, its role in connectomic graph learning remains largely unaddressed. This paper presents a comprehensive narrative review of UQ frameworks tailored to connectome graph learning alongside an empirical case study demonstrating the perils of uncalibrated predictions. We delineate sources of aleatoric and epistemic uncertainty across neuroimaging pipelines and review prominent UQ paradigms, from Bayesian approximations and ensemble methods to evidential learning and conformal prediction. In our case study, a temporal Graph Attention Network (GAT) trained on dynamic functional connectivity (dFC) matrices from the SUDMEX CONN dataset achieves 80.0% diagnostic accuracy (F1 = 0.794) for Cocaine Use Disorder. However, a post-hoc uncertainty audit via Monte Carlo dropout reveals severe overconfidence (ECE = 0.127), with misclassified subjects assigned prediction confidences up to 95%. This empirical divergence between discrimination and calibration underscores the confidence paradox in deep connectomics. Our findings establish that rigorous UQ, calibration, and selective prediction mechanisms are indispensable for deploying trustworthy graph-based biomarkers in clinical neuroscience.

0.16

Why don't Graph Transformers attend to the same token?

cs.LG ·2026-10-14 ·Alexandre Bismuth
publishedtheorycode/data similarity 0.56
Abstract · Accepted at the Geometric Distributional Deep Learning (GDDL) workshop at NeurIPS 2026. 8 pages, 1 figure. Code: https://github.com/alexandr…

In large language models (LLMs), attention concentrates heavily on the first token. This 'attention sink' is believed to protect deep models against over-mixing. Even though graph transformers face a related pressure, we find that a SoTA graph transformer, GRIT, rarely forms sinks on molecules, and that it sinks less when trained on larger graphs, the opposite of the trend in LLMs. In principle, a graph can prevent sinks: we prove and show empirically that its symmetry and locality limit the attention any node can receive. On molecules, however, with distinguishable atoms and global attention, neither limit prevents sinks; what stops them lies in the model. We find that the attention scoring function is the main cause. Replacing GRIT's gated logit with a dot product raises its sink rate from 0.09 to 0.68 on identical graphs. In Graph Transformers using dot-product attention, removing the sink gives about the same error as removing a random node, while GRIT's most-attended nodes matter to its predictions. Attention sinks are therefore a property of dot-product attention rather than of Transformers. In our experiments, they form when dot-product scoring has a distinguishable node to concentrate on.

0.46