Oral Presentations

Virtual Nodes Go Temporal

Authors: Sofiane ENNADIR, Yassir Jedra, Oleg Smirnov, Lele Cao

Date: December 10, 2025

Time slot: 9:30-9:50 (MST)

Abstract: Learning representations of temporally evolving graphs, also known as Continuous-Time Dynamic Graphs (CTDGs), has gained considerable attention due to their ability to model a wide range of real-world phenomena. Recent efforts extend the well-established message-passing paradigm and Graph Neural Network (GNN) models, originally designed for static graphs, to account for the temporal dimension of dynamic graphs. Although these methods have shown promising results, they often inherit limitations from their static counterparts, particularly regarding the capture of long-range interactions. In static settings, adding Virtual Nodes (VNs) has proven effective in overcoming locality constraints and boosting performance. In this work, we conduct a theoretical analysis of the impact of VNs in CTDG-based models. Specifically, we introduce the concept of information flow, which examines how information propagates through a graph following an event. From this perspective, we highlight inherent limitations of existing CTDG-based approaches and demonstrate how adding VNs can address these constraints. Building on these insights, we propose k-TVNs, a framework that incorporates a set of fully connected VNs, each representing a distinct community within the graph. Through both theoretical investigation and empirical validation, we show that incorporating VNs substantially improves the performance of CTDG models.

OpenReview: https://openreview.net/forum?id=jdKtkiH9ze

Efficient Neural Common Neighbor for Temporal Graph Link Prediction

Authors: Xiaohui Zhang, Yanbo Wang, Xiyuan Wang, Muhan Zhang

Date: December 10, 2025

Time slot: 9:50-10:10 (MST)

Abstract: Temporal graphs are widespread in real-world applications such as social networks, as well as trade and transportation networks. Predicting dynamic links within these evolving graphs is a key problem. Many memory-based methods use temporal interaction histories to generate node embeddings, which are then combined to predict links. However, these approaches primarily focus on individual node representations, often overlooking the inherently pairwise nature of link prediction. While some recent methods attempt to capture pairwise features, they tend to be limited by high computational complexity arising from repeated embedding calculations, making them unsuitable for large-scale datasets like the Temporal Graph Benchmark (TGB). To address the critical need for models that combine strong expressive power with high computational efficiency for link prediction on large temporal graphs, we propose Temporal Neural Common Neighbor (TNCN). Our model achieves this balance by adapting the powerful pairwise modeling principles of Neural Common Neighbor (NCN) to an efficient temporal architecture. TNCN improves upon NCN by efficiently preserving and updating temporal neighbor dictionaries for each node and by using multi-hop common neighbors to learn more expressive pairwise representations. TNCN achieves new state-of-the-art performance on Review from five large-scale real-world TGB datasets, 6 out of 7 datasets in the transductive setting and 3 out of 7 in the inductive setting on small- to medium-scale datasets. Additionally, TNCN demonstrates excellent scalability, outperforming prominent GNN baselines by up to 30.3 times in speed on large datasets. Our code is available at \href{https://github.com/GraphPKU/TNCN}{https://github.com/GraphPKU/TNCN}.

OpenReview: https://openreview.net/forum?id=ffsDVGiKRm

Generalized Degrees for Scalable Discrete Time Dynamic Graph Generation

Authors: Kjartan van Driel, Leonardo Niccolò Ialongo, Pablo Andrés Astudillo, Stefan Thurner

Date: December 10, 2025

Time slot: 10:10-10:30 (MST)

Abstract: The evolution of many real-world systems is best described by dynamic graphs, whose statistical properties reflect the constraints of the system. When forecasting their dynamics, the goal is to generate a time series of graphs respecting these underlying constraints. Existing scalable dynamic graph learning methods, however, are designed for local tasks such as link prediction or node classification, and their independent, local predictions are ill-suited for graph generation. This limitation is particularly relevant for discrete time dynamic graphs, where coarse time resolution induces dependencies among edges within each snapshot. We propose using a generalized notion of degrees to model such dependencies directly, thereby shifting the focus from individual links to node dynamics. This approach bypasses the need to learn a sparse graph representation, and yields an inductive representation that enables the generation of large-scale discrete-time dynamic graphs.

OpenReview: https://openreview.net/forum?id=yVJXsCC8NY

TANGO: Graph Neural Dynamics via Learned Energy and Tangential Flows

Authors: Moshe Eliasof, Eldad Haber, Carola-Bibiane Schönlieb

Date: December 11, 2025

Time slot: 9:00-9:20 (MST)

Abstract: We introduce TANGO, a dynamical-systems framework for graph representation learning that steers node features via a learned energy landscape. At its core is a learnable Lyapunov function whose gradient defines an energy-decreasing direction, guaranteeing stability and convergence. To preserve flexibility, we add a learned tangential message-passing component that evolves features along energy level sets. This orthogonal decomposition—gradient descent plus tangential evolution—enables effective signal propagation even in flat or ill-conditioned regions common in graph learning, mitigates oversquashing, and remains compatible with diverse GNN backbones. Empirically, TANGO achieves strong performance across node and graph classification and regression benchmarks, validating jointly learned energy functions and tangential flows.

OpenReview: https://openreview.net/forum?id=c3aN3wecSt

Short-Range Oversquashing

Authors: Yaaqov Mishayev, Yonatan Sverdlov, Tal Amir, Nadav Dym

Date: December 11, 2025

Time slot: 9:20-9:40 (MST)

Abstract: Message Passing Neural Networks (MPNNs) are widely used for learning on graphs, but their ability to process long-range information is limited by the phenomenon of oversquashing. This limitation has led some researchers to advocate Graph Transformers as a better alternative, whereas others suggest that it can be mitigated within the MPNN framework, using virtual nodes or other rewiring techniques.

In this work, we demonstrate that oversquashing is not limited to long-range tasks, but can also arise in short-range problems. This observation allows us to disentangle two distinct mechanisms underlying oversquashing: (1) the bottleneck phenomenon, which can arise even in low-range settings, and (2) the vanishing gradient phenomenon, which is closely associated with long-range tasks.

We further show that the short-range bottleneck effect is not captured by existing explanations for oversquashing, and that adding virtual nodes does not resolve it. In contrast, transformers do succeed in such tasks, positioning them as the more compelling solution to oversquashing, compared to specialized MPNNs.

OpenReview: https://openreview.net/forum?id=rmX8Jamnyg

Learning Kronecker-Structured Graphs from Smooth Signals

Authors: Changhao Shi, Gal Mishne

Date: December 11, 2025

Time slot: 9:40-10:00 (MST)

Abstract: Graph learning, or network inference, is a prominent problem in graph signal processing (GSP). GSP generalizes the Fourier transform to non-Euclidean domains, and graph learning is pivotal to applying GSP when these domains are not known. With the recent prevalence of multi-way data, there has been growing interest in product graphs that naturally factorize dependencies across different ways. However, the types of graph products that can be learned are still limited for modeling diverse dependency structures. In this paper, we study the problem of learning a Kronecker-structured product graph from smooth signals. Unlike the more commonly used Cartesian product, the Kronecker product models dependencies in a more intricate, non-separable way, but posits harder constraints on the graph learning problem. To tackle this non-convex problem, we propose an alternating scheme to optimize each factor graph in turn and provide theoretical guarantees for its asymptotic convergence. We also modify the proposed algorithm to learn graphs of the strong product, a denser graph product that covers the Kronecker product. We conduct experiments on synthetic and real-world graphs and demonstrate our approach’s efficacy and superior performance compared to existing methods.

OpenReview: https://openreview.net/forum?id=kuDtgSMEFn

Less is More: Using Buffer Nodes to Reduce Excessive Majority Node Influence in Class Imbalance Graphs

Authors: Less is More: Using Buffer Nodes to Reduce Excessive Majority Node Influence in Class Imbalance Graphs

Date: December 11, 2025

Time slot: 14:30-14:50 (MST)

Abstract: Graph Neural Networks (GNNs), despite success in node classification, struggle with class-imbalanced graphs, leading to minority node misclassification. Existing methods that synthesize minority nodes often overlook how majority nodes propagate misleading information through majority-minority edges; our analysis confirms this negative impact. To address this, we propose BufferGraph, a framework that inserts buffer nodes on such edges. These nodes act as controlled bottlenecks to reduce excessive majority node influence. And we theoretically demonstrate they reduce minority node feature distortion. Experiments on five real-world datasets show BufferGraph improves accuracy by up to 2% over state-of-the-art methods, excelling in imbalanced settings and for minority classes with high heterophily. Code is available at \url{https://github.com/Persdre/BufferGraph}.

OpenReview: https://openreview.net/forum?id=6ikB5L1kzq

Cross-Domain Graph Anomaly Detection via Test-Time Training with Homophily-Guided Self-Supervision

Authors: Delaram Pirhayatifard, Arlei Silva

Date: December 11, 2025

Time slot: 14:50-15:10 (MST)

Abstract: Abstract: Graph Anomaly Detection (GAD) has demonstrated great effectiveness in identifying unusual patterns within graph-structured data. However, while labeled anomalies are often scarce in emerging applications, existing supervised GAD approaches are either ineffective or not applicable when moved across graph domains due to distribution shifts and heterogeneous feature spaces. To address these challenges, we present GADT3, a novel test-time training framework for cross-domain GAD. GADT3 combines supervised and self-supervised learning during training while adapting to a new domain during test time using only self-supervised learning by leveraging a homophily-based affinity score that captures domain-invariant properties of anomalies. Our framework introduces four key innovations to cross-domain GAD: an effective self-supervision scheme, an attention-based mechanism that dynamically learns edge importance weights during message passing, domain-specific encoders for handling heterogeneous features, and class-aware regularization to address imbalance. Experiments across multiple cross-domain settings demonstrate that GADT3 significantly outperforms existing approaches, achieving average improvements of over 8.2% in AUROC and AUPRC compared to the best competing model.

OpenReview: https://openreview.net/forum?id=sB3LqdOlNb

Differentiable Community Detection with Graph Neural Networks and Stochastic Block Models

Authors: William Arliss, W. Graham Mueller

Date: December 11, 2025

Time slot: 15:10-15:30 (MST)

Abstract: We propose a set of loss functions adapted from Stochastic Block Model (SBM) likelihood functions to train Graph Neural Networks (GNNs) for the task of unsupervised community detection. Identifying latent community structures is a prominent challenge for many graph applications. SBMs are classical models that describe the generating process of random graphs and are commonly used to infer community structure. The likelihood functions associated with SBMs are well-defined, differentiable, and measure the quality of inferred community partitions; this makes them particularly useful for unsupervised learning with GNNs. Our proposed loss functions are independent of any specific GNN architecture and demonstrate competitive or improved community detection performance against several alternatives. Evaluation is carried out on multiple architectures and datasets, offering a thorough empirical analysis of the state of community detection with GNNs.

OpenReview: https://openreview.net/forum?id=T1vdfm1THf

Exploring Intrinsic Structures of Hyperedges as Point Clouds

Authors: Lige Zhang, Dongmian Zou

Date: December 12, 2025

Time slot: 14:30-14:50 (MST)

Abstract: Hypergraph neural networks (HNNs) provide a powerful framework for modeling high-order relationships in complex data. However, existing approaches often overlook the intrinsic patterns carried by hyperedges. Some methods simplify a hyperedge as a fully connected subgraph or treat it as an intermediate node-like entity, which limits the expressivity of the resulting models and neglects the potentially rich information of hyperedges. In this work, we offer a new perspective for hypergraph modeling by modeling a hyperedge as a point cloud with learnable features. Building on this view, we present a novel Hypergraph Kernel Network (HypKN) framework for hypergraph representation learning, which fully exploits the intrinsic hypergraph structure. The core component in HypKN is a Kernel Attention Message Passing (KAMP) module, which mimics the classical convolution operation defined for non-Euclidean data structures and enjoys provable stability results. We evaluate HypKN on ten real-world and synthetic hypergraph datasets for node classification, where it consistently outperforms classical HNN baselines and achieves state-of-the-art performance on several benchmarks.

OpenReview: https://openreview.net/forum?id=CIYl0o3d5d

One Model, Any Conjunctive Query: Graph Neural Networks for Answering Queries over Incomplete Knowledge Graphs

Authors: Krzysztof Olejniczak, Xingyue Huang, Mikhail Galkin, Ismail Ilkan Ceylan

Date: December 12, 2025

Time slot: 14:50-15:10 (MST)

Abstract: Motivated by the incompleteness of modern knowledge graphs, a new setup for query answering has emerged, where the goal is to predict answers that do not necessarily appear in the knowledge graph, but are present in its completion. In this paper, we formally introduce and study two query answering problems, namely, query answer classification and query answer retrieval. To solve these problems, we propose ANYCQ, a model that can classify answers to any conjunctive query on any knowledge graph. At the core of our framework lies a graph neural network trained using a reinforcement learning objective to answer Boolean queries. Trained only on simple, small instances, ANYCQ generalizes to large queries of arbitrary structure, reliably classifying and retrieving answers to queries that existing approaches fail to handle. This is empirically validated through our newly proposed, challenging benchmarks. Finally, we empirically show that ANYCQ can effectively transfer to completely novel knowledge graphs when equipped with an appropriate link prediction model, highlighting its potential for querying incomplete data.

OpenReview: https://openreview.net/forum?id=Fo2GLDelI1

GL Equivariant Metanetworks for Learning on Low Rank Weight Spaces

Authors: Theo Putterman, Derek Lim, Yoav Gelberg, Michael M. Bronstein, Stefanie Jegelka, Haggai Maron

Date: December 12, 2025

Time slot: 15:10-15:30 (MST)

Abstract: Low-rank adaptations (LoRAs) have revolutionized the finetuning of large foundation models, enabling efficient adaptation even with limited computational resources. The resulting proliferation of LoRAs together with the recent advances of weight-space learning present exciting opportunities for applying machine learning techniques that take these low-rank weights themselves as inputs. In this paper, we investigate the potential of Learning on LoRAs (LoL), a setup where machine learning models learn and make predictions on datasets of LoRA weights. Motivated by previous weight-space learning works, we first identify the inherent parameter symmetries of our data – low-rank decompositions of weights – which differ significantly from the parameter symmetries of standard neural networks. To efficiently process LoRA weights, we develop several symmetry-aware invariant or equivariant LoL models. In diverse experiments, we show that our LoL architectures can process LoRA weights to predict CLIP scores, finetuning data attributes, finetuning data membership, and accuracy on downstream tasks. We also show that LoL models trained on LoRAs of one pretrained model can effectively generalize to LoRAs trained on other models from the same model family. As an example of the utility of LoL, our LoL models can accurately estimate CLIP scores of diffusion models and ARC-C test accuracy of LLMs over 50,000 times faster than standard evaluation. As part of this work, we finetuned and will release datasets of more than ten thousand text-to-image diffusion-model and language-model LoRAs.

OpenReview: https://openreview.net/forum?id=fHRRYBZAmS

Position: Beyond Euclidean – Foundation Models Should Embrace Non-Euclidean Geometries

Authors: Neil He, Jiahong Liu, Buze Zhang, Ngoc Bui, Ali Maatouk, Irwin King, Menglin Yang, Melanie Weber, Rex Ying

Date: December 12, 2025

Time slot: 15:30-15:50 (MST)

Abstract: In the era of foundation models and Large Language Models (LLMs), Euclidean space has been the de facto geometric setting for machine learning architectures. However, recent literature has demonstrated that this choice comes with fundamental limitations. At a large scale, real-world data often exhibits inherently non-Euclidean structures, such as multi-way relationships, hierarchies, symmetries, and non-isotropic scaling, in a variety of domains, such as languages, vision, and the natural sciences. It is challenging to effectively capture these structures within the constraints of Euclidean spaces. This position paper argues that moving beyond Euclidean geometry is not merely an optional enhancement but a necessity to maintain the scaling law for the next-generation of foundation models. By adopting these geometries, foundation models could more efficiently leverage the aforementioned structures. Task-aware adaptability that dynamically reconfigures embeddings to match the geometry of downstream applications could further enhance efficiency and expressivity. Our position is supported by a series of theoretical and empirical investigations of prevalent foundation models. Finally, we outline a roadmap for integrating non-Euclidean geometries into foundation models, including strategies for building geometric foundation models via fine-tuning, training from scratch, and hybrid approaches.

OpenReview: https://openreview.net/forum?id=WoK4o90lln