🕸️ Graph Learning

🧪 ICML2026 · 35 paper notes

📌 Same area in other venues: 📷 CVPR2026 (8) · 🔬 ICLR2026 (118) · 💬 ACL2026 (24) · 🤖 AAAI2026 (37) · 🧠 NeurIPS2025 (54) · 📹 ICCV2025 (1)

🔥 Top topics: GNNs ×5 · LLM ×4 · Diffusion Models ×3 · Reasoning ×3 · Anomaly Detection ×3

Aitchison Embeddings for Learning Compositional Graph Representations

This paper proposes AICoG, which represents nodes as mixtures of latent archetypes on a simplex and learns graph embeddings using Aitchison geometry and Isometric Log-Ratio (ILR) coordinates. While maintaining the same expressiveness as Euclidean latent distance models, it ensures that node role similarity has an endogenous interpretation based on relative trade-offs of proportions.

An Approximation Algorithm for Graph Label Selection

This paper provides the first \(\tilde{O}(\log^{1.5} n)\) approximation algorithm for Graph Label Selection without label budget relaxation. By employing tree cut sparsification, flow decision-making, and dynamic programming on trees, it transforms the originally globally coupled node selection problem into a solvable combinatorial optimization pipeline.

Anchor-guided Hypergraph Condensation with Dual-level Discrimination

AHGCDD reformulates hypergraph condensation (HGC) from a decoupled paradigm of "training a structure generator then matching trajectories" into an end-to-end framework. It embeds structural information into initial features using Heat-Kernel-PageRank, synthesizes sparse learnable hyperedges via an anchor-guided approach based on feature distances, and replaces expensive HNN retraining with a dual-level discrimination loss (prototype MMD + instance-level contrastive). It achieves ≥SOTA across 5 hypergraph benchmarks with up to a 144× speedup.

Are Common Substructures Transferable? Riemannian Graph Foundation Model with Neural Vector Bundles

This paper redefines "transferable common substructures" in graph pre-training as behavioral invariance within the representation space. It constructs Gauge using neural vector bundles, gated geometric flattening, and Dirichlet loss, enabling graph models to achieve stronger structural generalization in cross-domain few-shot transfer, zero-shot link prediction, and graph isomorphism tasks.

Beyond Model Base Retrieval: Weaving Knowledge to Master Fine-grained Neural Network Design

The M-DESIGN framework is proposed to model neural network design as a retrieval-augmented iterative modification process. By constructing a Modification-Gain Graph to encode fine-grained architectural editing effects and utilizing Bayesian dynamic task similarity to calibrate transfer signals online, it achieves design-space optimality in 26 out of 33 GNN tasks.

Deep Neural Sheaf Diffusion

This paper identifies that Neural Sheaf Diffusion (NSD) loses its theoretically guaranteed resistance to collapse at deep layers because the "disagreement signal" of the sheaf Laplacian vanishes as diffusion converges. DNSD replaces the Laplacian with a sheaf adjacency operator and incorporates LayerNorm, odd activation functions, and per-stalk gating. This allows the sheaf architecture to be stably stacked up to 16 layers for the first time, achieving up to a 30 pp improvement over GNN/NSD baselines on synthetic long-range tasks and consistent leads on real-world heterophilic graph benchmarks.

DTKG: Dual-Track Knowledge Graph-Verified Reasoning Framework for Multi-Hop QA

DTKG bisects multi-hop QA into "parallel fact verification vs. chain reasoning." It first routes questions to the appropriate branch using a few-shot classifier. The parallel branch verifies atomic facts using KG triples, while the chain branch performs DFS path expansion with scoring-based pruning on Wikidata. Combined with "task-aware" denoising, it achieves a performance gain of 5%–29.5% over single-strategy baselines like KGR and ToG across six datasets.

ERAlign: Energy-based Representation Alignment of GNNs and LLMs on Text-attributed Graphs

Addressing the difficulty of aligning GNN and LLM representations on Text-Attributed Graphs (TAGs), this paper proposes a set energy-based model (set EBM). It projects both representations into a shared latent space, measures distribution misalignment using Cramér distance for layer-wise alignment, and employs a sampling-free Energy Discrepancy (ED) training objective to minimize energy. The method achieves state-of-the-art (SOTA) performance across 8 TAG datasets.

Finding the Minimal Parameter Budget for Implicit Reasoning: A Data Complexity Driven Scaling Law for Language Models

Starting from the Knowledge Graph Completion (KGC) task, this paper proves and measures that the "minimal parameter budget required for implicit reasoning" follows a linear scaling law based on Graph Search Entropy as the complexity metric. Each parameter supports approximately \(0.008\) bits of reasoning information, challenging the naive intuition that "larger models always yield stronger reasoning."

Fixed Aggregation Features Can Rival GNNs

The paper proposes Fixed Aggregation Features (FAF): multi-hop neighborhoods are compressed into tabular features using non-trainable aggregation operators like mean/sum/max/min/std and fed into an MLP. On 12 out of 14 node classification benchmarks, it matches or outperforms fine-tuned GCN/GAT/GraphSAGE and even Graph Transformers, systematically questioning the necessity of trainable neighborhood aggregation in GNNs.

Full-Spectrum Graph Neural Network: Expressive and Scalable

This paper generalizes the univariate eigenvalue filter \(g(\lambda_i)\) of classical spectral GNNs to a bivariate filter \(g(\lambda_i,\lambda_j)\), lifting signals from the node domain to the node-pair domain. Theoretically, this approach can approximate Local 2-GNNs (surpassing 1-WL). By utilizing low-rank tensor decomposition, it avoids explicit \(n^2\times n^2\) calculations, achieving strong results in heterophilic graph node classification and substructure counting.

ProMoS: Generalist Graph Anomaly Detection via Prototype-Based Distillation

ProMoS treats a frozen self-supervised GNN as a "normality prior teacher" and distills it into a suite of shared and sparsely activated lightweight student branches. By aligning teachers and students to a cross-graph shared semantic space via learnable prototypes, it achieves the first fully label-free, zero-shot, and cross-graph transferable generalist graph anomaly detector.

Generative Representation Learning on Hyper-relational Knowledge Graphs via Masked Discrete Diffusion

This paper introduces the "Fact Generation" task, extending Hyper-relational Knowledge Graph (HKG) completion from "filling a single blank" to "generating complete facts from arbitrary mask patterns or even from scratch." It proposes KREPE, the first generative HKG representation learning method: it encodes intra-fact and inter-fact dependencies via contextual message passing and models the joint conditional distribution of missing components using masked discrete diffusion. KREPE achieves SOTA on link prediction across three HKG benchmarks and significantly outperforms strong LLM baselines (e.g., GPT-5.2 / Gemini 3 Pro) in fact generation (e.g., WikiPeople- generation from scratch: 0.855 vs. LLM best 0.343).

GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning

GILT reformulates node, edge, and graph few-shot classification into a unified token-based in-context learning problem. By utilizing a pure numerical architecture consisting of "linear GCN for structural extraction + asymmetric prototype tokens + two-stage attention Transformer + prototype head," it achieves graph-native ICL without relying on LLMs or requiring any downstream tuning. In 5-shot settings, it outperforms both LLM-based and tuning-based GFMs while being 1 to 4 orders of magnitude faster.

Graph-GRPO: Training Graph Flow Models with Reinforcement Learning

To address the challenge that "Graph Flow Models (GFMs) are difficult to align with complex objectives using reinforcement learning," this paper proposes Graph-GRPO. First, it derives the non-differentiable Monte Carlo rate matrix in GFM sampling into an analytical expression, making the entire denoising trajectory differentiable and trainable via GRPO. Second, it introduces a refinement strategy that performs "local noise injection and re-generation" on high-scoring graphs. With only 50 denoising steps, it achieves 95.0%/97.5% V.U.N. on Planar/Tree datasets and outperforms previous graph RL and genetic algorithm methods in molecular optimization (protein docking, PMO).

Identifying and Correcting Label Noise for Robust GNNs via Influence Contradiction

ICGNN defines the "Influence Contradiction Score" (ICS) on graph diffusion matrices to measure the suspicion of node labels from both structural and attribute perspectives. It utilizes a Gaussian Mixture Model (GMM) soft thresholding to identify dirty labels and performs convex combination soft correction based on neighbor predictions, outperforming specialized methods such as NRGNN, RTGNN, CGNN, and ProCon across six graph benchmarks.

KBQA-R1: Reinforcing Large Language Models for Knowledge Base Question Answering

Redefines KBQA from a "one-shot logical expression generation" task to a "multi-turn decision process." It utilizes Referenced Rejection Sampling guided by gold-standard action sequences to generate executable reasoning trajectories for SFT cold start, followed by GRPO optimization based on F1 outcome rewards. This allows an 8B Llama to outperform both GPT-4 prompting methods and graph retrieval SOTA across three benchmarks: WebQSP, GrailQA, and GraphQ.

L2G-Net: Local to Global Spectral Graph Neural Networks via Cauchy Factorizations

The authors precisely decompose the basis of the Graph Fourier Transform (GFT) into "local GFTs for each subgraph \(\times\) a sequence of Cauchy matrices," reducing the \(O(n^3)\) eigendecomposition complexity to \(O(kn^2)\) (where \(k\) is the number of cut edges between subgraphs). By interleaving learnable spectral filters within this factorization, they develop a family of local-to-global spectral GNNs capable of running on large graphs with 569k nodes, achieving performance comparable to Transformers with several orders of magnitude fewer parameters.

Learnable Kernel Density Estimation for Graphs and Its Application to Graph-Level Anomaly Detection

LGKDE embeds each graph as a "node distribution" using a learnable deep MMD metric, overlays a multi-scale kernel density estimation (KDE) on this metric space, and trains end-to-end via a self-supervised contrastive signal where "normal graph density is higher than its structure-aware perturbed version." This provides the first unified framework for graph-level density estimation with theoretical guarantees—including consistency, convergence rates, robustness, and generalization bounds—while consistently outperforming strong GNN, contrastive, and one-class baselines across over ten graph anomaly detection benchmarks.

MedCoG: Maximizing LLM Inference Density in Medical Reasoning via Meta-Cognitive Regulation

MedCoG enables LLMs to perform a three-dimensional self-assessment of "complexity / familiarity / knowledge density" for medical questions before invoking SCoT, memory, and knowledge graphs (KG) on demand. This approach increases inference density (theoretical cost/actual cost required to achieve equivalent accuracy) to 6.2×, while improving average accuracy from 34.5% (AFlow) to 37.5% across five MedQA hard sets.

Message Tuning Outshines Graph Prompt Tuning: A Prismatic Space Perspective

This paper proposes Prismatic Space Theory (PS-Theory), treating the frozen GNN foundation model as a layer-wise piecewise linear mapping that performs "prismatic" refraction on the input manifold. It rigorously proves that an upper bound exists for the adaptation capability of graph prompt tuning. Consequently, Message Tuning (MTG) is introduced, which injects learnable "message prototypes" into each layer and dynamically fuses them with native messages. MTG theoretically breaks the aforementioned upper bound and outperforms existing graph prompt methods across 15 datasets and 6 pre-training strategies.

Physics-Informed Coarsening for Multigrid Graph Neural Surrogates

This paper trains an Encoder-Processor-Decoder multigrid GNN surrogate for finite element simulation in solid mechanics. The core innovation is replacing geometric heuristics (FPS) or learned attention in "coarsening (downsampling) node selection" with "TopK scoring based on the discrete residual of momentum conservation equations." This concentrates coarse-layer computational resources on dynamically critical regions like stress concentrations, contact interfaces, and large deformations, reducing rollout RMSE from the Prev. SOTA \(11.46\times 10^{-3}\) to \(6.5\times 10^{-3}\) (approx. 43% improvement) on the DeformingPlate dataset.

Polynomial Neural Sheaf Diffusion: A Spectral Filtering Approach on Cellular Sheaves

PolyNSD replaces the "single-step spatial diffusion" of Sheaf Neural Networks with a learnable \(K\)-th order polynomial spectral filter applied to the normalized sheaf Laplacian. Using Chebyshev three-term recurrence for stable computation, a single layer achieves a \(K\)-hop receptive field and controllable low/band/high-pass responses. A surprising finding is that using only diagonal restriction maps outperforms existing NSD models that require dense, high-dimensional stalks, significantly reducing parameters, memory, and runtime.

Quantile-Free Uncertainty Quantification in Graph Neural Networks

QpiGNN proposes a GNN node-level prediction interval framework that requires "no quantile input and no post-processing." By employing a dual-head GNN (one head for mean prediction and one for half-width) paired with a label-level joint loss that directly optimizes "coverage + interval width," it achieves a 22% increase in average coverage and a 50% reduction in interval width across 19 synthetic and real-world datasets.

RADE: Random Add-Drop Edge as a Regularizer

RADE simultaneously performs random edge deletion and addition during GNN training, aligns training and inference through "expectation-preserving" aggregation correction, and adaptively tunes add/drop rates using GradNorm, allowing a single augmentation to mitigate both overfitting and over-squashing.

Rethinking Feature Alignment in Generalist Graph Anomaly Detection: A Relational Fingerprint-based Approach

Addressing the negative transfer problem in generalist graph anomaly detection where "PCA alignment only unifies dimensions but not semantics," this paper proposes a 5-dimensional "Relational Fingerprint" (neighborhood position/direction/global direction consistency + degree + clustering coefficient) to explicitly extract anomaly-indicative clues as cross-domain universal features. Combined with a domain-shared Transformer encoder and an SNR-guided domain-adaptive recalibration module, it achieves SOTA with "universal positive transfer" across 14 datasets.

Structure-Centric Graph Foundation Model via Geometric Bases

SCGFM reformulates cross-domain graph foundation models as a "triangulation" problem in metric-measure spaces: it learns a set of \(K\) trainable geometric bases \(\{B_k\}\), where each graph is mapped to a set of structural coordinates \(\mathbf{w}\) via a softmax of its Gromov–Wasserstein distances \(\delta_k\) to each basis. Node features are then aggregated into a uniform dimension using OT plans on the bases. This approach moves beyond the limitations of traditional GFMs that require aligned node feature spaces, outperforming baselines in both in-domain and OOD few-shot graph/node classification.

T-GINEE: A Tensor-Based Multilayer Graph Representation Learning

T-GINEE combines CP tensor decomposition with Generalized Estimating Equations (GEE) to explicitly model cross-layer dependencies in multilayer networks—offering theoretical guarantees and superior scalability, overcoming OOM limitations of other tensor methods on million-node graphs (DBLP, Stack Overflow).

Understanding Truncated Positional Encodings for Graph Neural Networks

This paper theoretically demonstrates that while spectral and walk encodings are equivalent in their "full" forms, their expressive power differs significantly in the "truncated" versions used in practice. Truncated spectral encodings may not even be stronger than the 1-WL test. Consequently, the authors suggest the empirical rule: "Since truncation is necessary, mix positional encodings from different families," and validate this on real-world datasets.

Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs

Ours models CNF formulas as a "clause-literal hypergraph + clause interaction graph" and decomposes variable-level representations into polarity-invariant and polarity-equivariant components. By training with polarity-flip consistency regularization, the prediction accuracy for unsat-core variables is significantly improved.

View Space: Representation Learning Across Arbitrary Graphs

This paper proposes the concept of View Space, elevating graphs from 2 dimensions (node-feature) to 3 dimensions (node-feature-view) to achieve a unified representation across arbitrary feature dimensions and semantic graphs. This marks the first time a graph model can perform cross-domain reasoning without fine-tuning, similar to NLP/CV foundation models, outperforming GraphAny by an average of 8.93% across 27 downstream tasks.

What Makes a Desired Graph for Relational Deep Learning?

This paper points out that "mechanically converting database schemas into graphs" is not what GNNs desire, as such graphs systematically suffer from information overload and semantic fragmentation. The authors propose an end-to-end "Structural Optimizer" that uses learnable gating for information filtering and templated structural injection to recover task-related edges. Across 26 tasks in RELBench, this approach improves accuracy while frequently reducing inference overhead.

What Structural Inductive Bias Helps Transformers Reason Over Knowledge Graphs? A Study with Tabula RASA

This paper employs RASA, a minimalist and decomposable Graph Transformer variant, to conduct controlled experiments. It finds that the most effective structural inductive bias in multi-hop KGQA stems from topological constraints provided by adjacency masks, rather than learnable relation parameters such as relation-type bias, query scaling, or value gating.

When Do Graph Foundation Models Transfer? A Data-Centric Theory

This paper utilizes graphons to represent graphs of varying sizes and domains within a unified continuous space. It proves that cross-domain output discrepancies in graph foundation models (GFMs) can be decomposed into two finite sampling errors and an intrinsic graphon domain discrepancy. Synthetic and real-world experiments demonstrate that graph size, structural shift, and spectral positional encoding stability collectively determine transfer success.

Whom to Query for What: Adaptive Group Elicitation via Multi-Turn LLM Interactions

This paper extends multi-turn questionnaire-style elicitation from the decision of "what question to ask" to a joint decision of "whom to query and what to query." It utilizes LLMs to estimate the information gain of questions and heterogeneous GNNs to propagate and impute missing responses across a group relationship graph, thereby recovering group preferences faster under a limited respondent budget.