CS Paper Radar

Topology-Adaptive Hyperbolic Graph Attention Networks Guided by the Hyperbolic Sombor Index

Haifang Cao, Boan Tao, Xiyuan Gao, Timing Li, Yu Wang, Pengfei Zhu

cs.LG ·submitted 2026-09-26 06:04 UTC · v1
benchmark

Abstract

Hyperbolic geometry has emerged as a principled space for representing hierarchical graphs. However, existing hyperbolic graph neural networks typically rely on shared curvature configurations and feature-driven attention, failing to explicitly exploit local hierarchical topological patterns. To bridge this gap, we introduce the Hyperbolic Sombor Index (HSO) as a lightweight structural prior for capturing hierarchy-indicative degree stratification. Building on this, we propose \textbf{HSO-GAT}, a topology-adaptive hyperbolic graph attention network that unifies geometric adaptation and message propagation. Specifically, it comprises two complementary modules: HSO-Guided Local Curvature Adaptation, which performs adaptive node-wise geometric scaling from aggregated node-level HSO signals, and HSO-Gated Hyperbolic Graph Attention, which enables structure-aware message passing through feature-conditioned gating. Theoretically, we establish the monotonic sensitivity of edge-level HSO to degree imbalance and analyze the validity and radial scaling properties of node-adaptive hyperbolic mappings. Extensive experiments on eight benchmark datasets demonstrate that HSO-GAT consistently achieves state-of-the-art performance in both node classification and link prediction tasks.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Edge-aware Attention Network for Graph Generation

cs.LG ·2026-10-20 ·Vincent Jung, Alba Carballo-Castro, Yiming Qin, Lonneke van der Plas, Pascal Frossard
published similarity 0.63
Abstract · Accepted at the Workshop on Graph Foundation Models and the Workshop on Structured Probabilistic Inference & Generative Modeling, ICML 2026,…

Graph generative models commonly use graph-specific Transformer architectures to jointly update node and edge features. However, these architectures do not directly benefit from recent hardware-aware attention implementations, limiting their scalability. The adaptation is, however, non-trivial: edge and graph-level features must be injected into pairwise attention scores, graph masks must be respected, and dynamic edge updates remain a major source of quadratic memory usage. We propose an edge-aware attention layer for graph generation that incorporates structural information through head-wise score modulation, while updating edge representations with a lightweight residual mechanism that retains attention-score dependent edge updates. This layer can be effectively implemented using PyTorch's FlexAttention. We achieve similar generation quality to our baseline while reducing peak GPU memory by around 65% and substantially improving training and sampling throughput. These results suggest that the proposed architecture is a practical step toward scalable graph foundation models.

0.16

Graph-dependent pooling: adaptive granularity in hierarchical graph neural networks

cs.AI cs.LG ·2026-10-24 ·Bohan Yoon, Hyejin Jang
similarity 0.62
Abstract

Graph Neural Networks are widely used to learn structural representations of relational data. Hierarchical graph pooling learns multi-level representations by progressively coarsening graphs; however, prior methods rely on predefined cluster numbers or fixed pooling ratios, limiting adaptability to individual graphs. We propose Graph-Dependent Pooling (GDPool), which dynamically determines pooling granularity for each graph. We analyze optimization conflicts among layer-wise objectives through gradient alignment, showing that independently supervised pooling levels can send conflicting gradients to shared parameters. GDPool uses self-attention to select graph-specific anchors representing structurally important nodes and constructs coarse graphs through soft node assignment. Experiments on metal-organic framework and molecular graph benchmarks show that GDPool consistently achieves the best predictive performance across all benchmarks. Evaluations using modularity and the effective number of clusters show that GDPool achieves consistently higher modularity than existing methods while the number of active clusters decreases monotonically with depth. Sensitivity analyses confirm stable behavior across hyperparameter and architectural choices.

0.13

HyBridge: Bridge-Guided Self-Supervised Hyperbolic Hypergraph Representation Learning

cs.SI cs.AI ·2026-11-12 ·So-Bin Jung, David Yoon Suk, Sang-Wook Kim
similarity 0.61
Abstract

Hypergraphs capture groupwise relationships among multiple nodes and often exhibit tree-like structures. Although hyperbolic space is well suited for modeling such structures, simply extending existing hypergraph representation learning (HRL) methods to hyperbolic space does not consistently improve performance. In this paper, we investigate the relationship between node structural properties and hyperbolic embedding radii and find that bridge nodes tend to lie closer to the center in graphs, whereas this relationship is not consistently observed in hypergraphs. We further find that conventional bridge score estimation may fail to capture the groupwise connectivity of hypergraphs. Motivated by these findings, we propose HyBridge, a self-supervised hyperbolic HRL framework that (1) estimates node bridge scores by considering the external connectivity of individual hyperedges, (2) learns node and hyperedge embeddings through hyperbolic hypergraph encoding, (3) guides node radial positions according to their bridge scores, and (4) employs contrastive learning to preserve node discriminability. Extensive experiments on 10 real-world hypergraphs demonstrate that HyBridge outperforms 22 competing methods, achieving performance improvements of up to 9.82% in node classification. For reproducibility, we provide the code at https://anonymous.4open.science/r/HyBridge/.

0.18

NearFormer: Linear-Size Sparse Attention via Randomized Near Neighbors

cs.LG cs.AI ·2026-11-09 ·Ali Parviz, Alex Cloninger, Gal Mishne
similarity 0.60
Abstract

Graph transformers can capture long-range interactions, but their quadratic attention cost limits their use on large graphs. We introduce \emph{NearFormer}, a graph transformer whose global attention is restricted to a randomized near-neighbor (NN) graph. NearFormer uses an efficient randomized construction to connect each node to a small number of near neighbors from a broader neighborhood defined by a label-independent feature or spectral geometry. For a fixed retained budget \(k\), the resulting attention support has linear size \(\mathcal{O}(|E|+nk)\). The NN graph is built once by within-bin search and then held fixed. We use these edges as sparse global-attention supports, with optional learned attention biases, while preserving the original graph for local message passing. Experiments on long-range graph benchmarks and synthetic structural tasks show that NearFormer provides a favorable accuracy--scalability trade-off relative to local message passing, dense and sparse attention.

0.16

PANDA: Prior-guided Attentional Dual-path Architecture

cs.LG ·2026-10-09 ·Rishabh Jain, Federico Belotti, Stefano Coniglio, Pietro Lio, Stefano Fiorini
top venuebenchmarkcode/data similarity 0.60
Abstract · Accepted at NeurIPS 2026

Hypergraph Neural Networks (HNNs), designed to model higher-order relations beyond pairwise interactions, typically rely either on fixed structural weights or on normalised attention. Fixed weights can propagate misleading information in heterophilic settings, while normalisation makes attention coefficients competitive, in the sense that, in a message-passing framework, increasing the weight of one sender must reduce the weight of others in the same aggregation set. Our main contribution is the introduction of PANDA (Prior-guided AttentioNal Dual-path Architecture), a plug-in for two-stage message passing HNNs applicable to both undirected and directed settings. The main path interpolates between learned receiver-normalised attention and structural incidence priors, while a non-competitive (not normalised) auxiliary path lets each sender contribute its own transformed information. We also show that, with fixed structural coefficients, PANDA recovers a certain complex-valued convolution operator adopted in previous works. Across four HNNs spanning spatial and spectral methods in both directed and undirected settings, plugging PANDA in yields an average improvement of 5.18 percentage points across eight real-world benchmark datasets. The code is available at https://github.com/jainris/panda.

0.49

Learning Pseudo-Riemannian Manifolds for Heterophilic Graphs via Graph Signature

cs.LG cs.AI ·2026-11-04 ·Yun Young Choi, Asung Kil, Sun Woo Park, Minho Lee, Seokhwan Kim
top venuetheory similarity 0.60
Abstract · Accepted at NeurIPS 2026. 41 pages, including appendix

Several widely used families of Graph Neural Networks carry a positive-definite geometric prior. Graph convolution read as heat diffusion needs a positive semi-definite operator, hyperbolic models place features on positive-definite Riemannian manifolds, and dot-product and GAT-style attention scores use positive-definite inner products. On heterophilic graphs, where edges often signify dissimilarity or structural repulsion, that prior is a mismatch: no positive-definite form can assign a negative squared distance to a direction the labels separate. To measure the mismatch, we introduce the Graph Signature Index ($s_{\mathcal{G}}$), the inertia of a class-compatibility matrix built from label topology alone, and we prove that no value of the edge or node homophily index in $(0,1)$ rules out a negative eigenvalue. We then propose the Pseudo-Riemannian Attention Network (PRAT), whose attention logit is a signed squared pseudo-distance under a learnable diagonal metric initialized from $s_{\mathcal{G}}$. The design is diagnose-then-learn: the signature supplies a sign structure that unconstrained training keeps outside near-zero directions, and the projection learns the rest of the metric around it. Across fifteen node-classification benchmarks PRAT outperforms or matches the strongest heterophily-adapted models. A controlled ablation ties that performance to the sign structure itself: with architecture and protocol fixed, forbidding the metric to be indefinite costs accuracy on the graphs $s_{\mathcal{G}}$ marks as indefinite and leaves the others unchanged.

0.43

Repurposing Unified Topological Signatures for Graph Representation Learning

cs.LG cs.AI ·2026-09-15 ·Sanyam Sanjay Jain, Anshika Krishnatray, Aditya Sharma, Vinti Agarwal
similarity 0.59
Abstract

Message-passing Graph Neural Networks (GNNs) iteratively propagate and aggregate local neighborhood information followed by global readout to learn graph representations. However, their discriminative power is upper-bounded by the Weisfeiler--Lehman (1-WL) graph isomorphism test. This prevents GNNs from distinguishing certain non-isomorphic graphs with identical local neighborhood structures, often leading to similar graph representations. Unified Topological Signatures (UTS) capture compact, multi-scale representation of global graph topology derived from persistent homology. We introduce two complementary UTS signatures: Graph_UTS- a static signature of the input graph topology, and Embedding_UTS- a dynamic signature of the evolving embedding topology. They encode structural information inaccessible to 1-WL-based message-passing GNNs, yet their capabilities are explored solely for post-hoc embedding-space analysis. We integrate UTS into GNN training across three architectural interventions: (i) UTS-Aug: augmenting with standard readout feature that encodes graph's true topology; (ii) UTS-Reg: topological regularizer that constrains representation collapse; (iii) UTS-Pool: topology-guided pooling that retains structurally critical nodes. We further leverage UTS as a layer-wise diagnostic to quantify oversmoothing during GNN training. Theoretically, we show that integrating UTS into GNN optimization strictly extends GNN expressivity beyond the 1-WL hierarchy. Experiments on three graph classification benchmarks show consistent benefits: Graph-UTS, Dual-UTS, and UTS-Pool improve accuracy across all three datasets, Embedding-UTS provides smaller but similarly consistent gains, and UTS-Reg's benefit varies across graph domains. Accuracy improves by up to 5.8% with Graph-UTS augmentation, by up to 1.9% with UTS-Reg, and achieves comparable performance to TOGL with UTS-Pool.

0.04

SAC-GCL: Structure-Aware Compression for Graph Contrastive Learning

cs.LG cs.SI ·2026-10-27 ·Muhammad Ifte khairul Islam, Tanvir Hossain, Esra Akbas
benchmark similarity 0.59
Abstract

Graph Contrastive Learning (GCL) has achieved remarkable success in self-supervised representation learning by maximizing agreement between augmented views of a graph. Although augmented view generation is the central step in GCL, existing models rely on stochastic augmentation of the input graph, such as edge perturbation and node masking, which lack structural awareness and frequently destroy critical topology or introduce semantically inconsistent views. While recent adaptive methods improve upon random perturbations, they primarily operate on localized node or edge neighborhoods and fail to capture higher-order, macro-level structural organization crucial for graph classification. To address this limitation, we propose Structure-aware Compression for Graph Contrastive Learning (SAC-GCL), a novel framework that employs structural decomposition and graph compression as a principled view generation strategy. Moving beyond random augmentations, SAC-GCL leverages structural decomposition techniques to extract cohesive subgraphs and condense them into supernodes, constructing coarsened graph views that preserve local density and capture higher-level structural patterns while reducing noise and redundancy. We leverage multiple cohesive subgraph models to derive complementary views of the graph, each capturing distinct structural properties. To capture multi-resolution information, a hierarchical view encoder processes these compressed views by initializing super-node features with shared-weight cohesive subgraph embeddings. Our results from extensive experiments on six benchmark datasets demonstrate that structure-aware compression provides a powerful alternative to random perturbations, yielding more robust and discriminative graph representations for graph classification tasks.

0.15