Graph Neural Networks

Also known as GNN

Follow this topic Ask about this topic

Latest papers 686

88 papers in the last four weeks, up 31% on the four weeks before. 0.5% of all new papers.

Oct 10, 2025

CRPS-LAM: Probabilistic Regional Weather Forecasting with Continuous Ranked Probability Score

Limited-Area Models (LAMs) enable weather forecasting over regional domains at higher resolutions than what is computationally feasible for global models. At such high resolutions, machine learning approaches for weather prediction increasingly rely on ensemble methods to produce probabilistic forecasts. However, existing machine learning LAMs are not scalable due to relying on computationally costly diffusion models or inefficient graph neural networks. We tackle this by introducing a new hybrid CNN/GNN architecture, tailored to the LAM weather forecasting problem. Using this architecture, we construct the DET-LAM deterministic model, producing LAM forecasts both more efficiently and accurately than its graph-based competitor. We then tackle the ensemble forecasting problem, by using this architecture as a backbone for the generative model CRPS-LAM. CRPS-LAM is trained using a Continuous Ranked Probability Score (CRPS) objective, enabling efficient training and sampling in a single forward pass. This yields a speedup of

\approx \times 39

compared to diffusion-based baselines. We evaluate our approach on regional domains in northern Europe, demonstrating that CRPS-LAM produces skillful and well-calibrated forecasts across a range of atmospheric variables.

Erik Larsson, Joel Oskarsson, Tomas Landelius +1

Linköping University · ETH AI Center · SMHI & Linköping University

Graph Neural Networks Ensemble Learning Probabilistic Forecasting Spatiotemporal Forecasting Weather Forecasting

Oct 6, 2025

Fractional Heat Kernel for Semi-Supervised Graph Learning with Small Training Sample Size

We develop a source-driven fractional heat-kernel framework for semi-super-vised graph learning that combines nonlocal propagation with sustained label information. A fixed nonzero label source compatible with the Laplacian null space prevents asymptotic collapse into that space, providing a mechanism for mitigating oversmoothing at long diffusion times. The fractional order controls the relative modal attenuation and the spectral weighting of the sustained response, while the diffusion time sets the propagation horizon. We characterize conservation laws and equilibria on normalized and disconnected graphs, develop a null-space deflation, and analyze the approximation of the propagators. On Two-Moon, fractional orders improve source-free propagation, while compatible source-driven diffusion exceeds

96\%

mean accuracy with one training label per class at orders

0.8

and

1

. On Cora and CiteSeer, the source-driven pipeline improves mean accuracy over GAT by

9.2

and

8.0

percentage points at one training label per class, with model selection on

500

labeled validation nodes and closely comparable classical and fractional pipeline configurations; it matches GAT on PubMed and trails it at ten and twenty labels per class on Cora. Within GraphHeat, validation-based exponent selection at a common diffusion time yields a paired gain of

1.45

percentage points at one label per class.

Farid Bozorgnia, Vyacheslav Kungurtsev, Shirali Kadyrov +1

Graph-Based Semi-Supervised Learning Graph Diffusion Graph Neural Networks

Oct 5, 2025

Toward Uncertainty-Aware and Generalizable Neural Decoding for Quantum LDPC Codes

Quantum error correction (QEC) is essential for scalable quantum computing, yet decoding errors via conventional algorithms result in limited accuracy (i.e., suppression of logical errors) and high overheads, both of which can be alleviated by inference-based decoders. To date, such machine-learning (ML) decoders lack two key properties crucial for practical fault tolerance: reliable uncertainty quantification and robust generalization to previously unseen QEC codes. To address this gap, we propose a Quantum Bayesian graph Attention decoder (QuBA) that enables expressive error-pattern recognition alongside calibrated uncertainty estimates. Building on QuBA, we further develop a multi-phase training framework with enhanced cross-domain robustness enabling decoding beyond the training set called Sequential Aggregate Generalization under Uncertainty (SAGU). Experiments on bivariate bicycle (BB) codes and their coprime variants demonstrate that (i) both QuBA and SAGU consistently outperform the classical baseline belief propagation (BP), achieving up to a two orders of magnitude reduction in logical error rate (LER) under confident-decision bounds on the coprime BB code

[[154,6,16]]

; (ii) SAGU achieves decoding performance comparable to or even outperforming QuBA's domain-specific training approach.

Xiangjun Mi, Frank Mueller

North Carolina State University, Raleigh, NC 27695, USA

OOD Generalization Uncertainty Quantification Graph Neural Networks

Sep 28, 2025

GraphIFE: Rethinking Graph Imbalance Node Classification via Invariant Learning

The class imbalance problem refers to the disproportionate distribution of samples across different classes within a dataset, where the minority classes are significantly underrepresented. This issue is also prevalent in graph-structured data. Most graph neural networks (GNNs) implicitly assume a balanced class distribution and therefore often fail to account for the challenges introduced by class imbalance, which can lead to biased learning and degraded performance on minority classes. We identify a quality inconsistency problem in synthesized nodes, which leads to suboptimal performance under graph imbalance conditions. To mitigate this issue, we propose GraphIFE (Graph Invariant Feature Extraction), a novel framework designed to mitigate quality inconsistency in synthesized nodes. Our approach incorporates two key concepts from graph invariant learning and introduces strategies to strengthen the embedding space representation, thereby enhancing the model's ability to identify invariant features. Extensive experiments demonstrate the framework's efficiency and robust generalization, as GraphIFE consistently outperforms various baselines across multiple datasets. The code is publicly available at https://github.com/flzeng1/GraphIFE.

Fanlong Zeng, Wensheng Gan, Kangjie Chen +1

School of Intelligent Systems Science and Engineering, Jinan University, Zhuhai 519070, China · School of Cybersecurity, Tianjin University, Tianjin 300354, China · University of Illinois Chicago, Chicago, USA

Class-Imbalanced Learning Graph Neural Networks Data Augmentation Invariant Representation Learning Node Classification

Sep 26, 2025

Self-Improving Neural Pruning: A Graph Neural Network Framework for Scalable Mixed Bundle Pricing

Mixed bundle pricing is a classic revenue management problem arising in industries such as e-commerce, tourism, and video games. It refers to designing product combinations (i.e., bundles) and determining their prices to maximize expected profit. Exact mixed-bundling formulations capture this structure but are computationally intractable because the number of possible bundles grows exponentially with the number of products. We propose a graph neural network (GNN)-guided pruning framework for scalable (non-)additive bundle pricing. Instead of learning on the exponential bundle-level formulation, we encode each instance as a compact customer-product graph and train an edge-output GNN to learn the product-assignment probabilities from optimal mixed-bundling solutions. The predicted probabilities are then converted into restricted candidate bundle families through fixed cutoff pruning and progressive cutoff pruning; the final prices and assignments are obtained by solving the mixed bundling formulation over the retained bundles. We further introduce a GNN-guided local search and an iterative self-improvement procedure for larger instances. The local search refines the retained bundle family by prioritizing high-confidence add/drop moves, while the iterative self-improvement procedure generates high-quality solutions on larger instances for retraining. Theoretically, we show that under mild distinguishability conditions the proposed edge-output GNN class is expressive enough to recover the optimal product-assignment mapping. Experiments show that the proposed policies recover over 98% of the optimal profit on small instances and outperform bundle-size pricing on larger instances with substantial runtime savings.

Liangyu Ding, Chenghan Wu, Guokai Li +1

School of Data Science, The Chinese University of Hong Kong, Shenzhen, Guangdong, China

Graph Neural Networks Combinatorial Optimization Neural Combinatorial Optimization

Sep 23, 2025

Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learning

Neural algorithmic reasoning (NAR) is a paradigm that trains neural networks to execute classic algorithms by supervised learning. Despite its successes, important limitations remain: inability to construct valid solutions without post-processing and to reason about multiple correct ones, poor performance on combinatorial NP-hard problems, and inapplicability to problems for which strong algorithms are not yet known. To address these limitations, we reframe the problem of learning algorithm trajectories as a Markov decision process, which imposes structure on the solution construction procedure and unlocks the powerful tools of imitation and reinforcement learning (RL). We propose the GNARL framework, encompassing the methodology to translate problem formulations from NAR to RL and a learning architecture suitable for a wide range of graph-based problems. We achieve high rates of reaching correct states on several CLRS-30 problems and performance matching or exceeding much narrower NAR approaches for NP-hard problems. Remarkably, GNARL remains applicable when no expert algorithm is available, though reward-driven learning can exhibit greater variability than direct supervision.

Alex Schutz, Victor-Alexandru Darvariu, Efimia Panagiotaki +2

Oxford Robotics Institute, University of Oxford · Stateful Robotics

Graph Neural Networks Reinforcement Learning Neural Algorithmic Reasoning RL for Combinatorial Optimization Algorithmic Reasoning Neural Combinatorial Optimization

Sep 15, 2025

Learning Contact Dynamics through Touching: Action-conditional Graph Neural Networks for Robotic Peg Insertion

We present a learnable physics-based model that predicts motion of the robot end effector and reaction force-torque in contact-rich manipulation. The model represents the end effector and the environment as interacting meshes in a graph structure, and conditions its prediction explicitly on the applied control input. It predicts object-level pose update directly, while the reaction torque emerges from a per-vertex force field. Training is self-supervised using only joint encoder and force-torque data while the robot is randomly touching the environment without task context. In simulation, our model transfers to peg insertion with unseen concave geometry, where an MPC agent using it reaches up to 98% success rate, and after fine-tuning on self-collected data matches an agent planning with the ground truth dynamics at the tightest 1 mm clearance. In the real world, it outperforms the system-identified MuJoCo model by 45% in position and by 74% and 63% in force and torque error.

Zongyao Yi, Joachim Hertzberg, Martin Atzmueller

German Research Center for Artificial Intelligence, DFKI Niedersachsen, Osnabrück, Germany · Osnabrück University, Institute of Computer Science, Osnabrück, Germany

Graph Neural Networks Contact-Rich Robotic Manipulation Robot Dynamics Learning Robotic Insertion Robot Learning

Sep 8, 2025

Alternative Graph Neural Networks: Synergizing GEV Models and Deep Learning for Travel Mode Choice Modeling

Generalized extreme value models capture dependence among choice alternatives in discrete choice modeling, but require this dependence to be predefined, symmetric, and shared uniformly across individuals. Recent efforts to synergize discrete choice models with deep neural networks have improved predictive performance but still cannot explicitly represent alternative dependence within neural architectures. To address these gaps, we introduce the alternative graph -- a graph in which nodes represent choice alternatives and edges encode their dependence -- and propose Alternative Graph Neural Networks (Alt-GNNs), a family of GNN-based discrete choice models that embed alternative dependence within a unified framework. Theoretically, Alt-GNNs incorporate multinomial logit, nested logit, and ASU-DNN as special cases and enable innovative model designs, including Nested Alt-GNN, Complete Alt-GNN, and Attention Alt-GNN. Alt-GNNs are consistent with random utility maximization theory, enforce behavioral constraints through alternative graphs, and offer a novel graph-based interpretation of utility functions. Empirically, on two travel mode choice datasets from London and Chicago, Alt-GNNs significantly improve predictive performance over all benchmark models in mode choice modeling because of their flexible alternative graph design and vast hyperparameter space. Even the simplest Alt-GNN variant -- Nested Alt-GNN -- generalizes the nested logit model while preserving its unique two-layer substitution properties, enabling graph-based behavioral constraints over otherwise unconstrained behavioral patterns from deep neural networks.

Yuqi Zhou, Zhanhong Cheng, Dingyi Zhuang +3

aDepartment of Urban and Regional Planning, University of Florida · dDepartment of Civil and Environmental Engineering, Massachusetts Institute of Technology · bCollege of Architecture, Texas A&M University +1

Graph Neural Networks Discrete Choice Modeling

Aug 25, 2025

A Note on Graphon-Signal Analysis of Graph Neural Networks

A recent paper, ``A Graphon-Signal Analysis of Graph Neural Networks'', by Levie, analyzed message passing graph neural networks (MPNNs) by embedding the input space of MPNNs, i.e., attributed graphs (graph-signals), into a space of attributed graphons (graphon-signals). Based on extensions of standard results in graphon analysis to graphon-signals, the paper proved a generalization bound and a sampling lemma for MPNNs. However, there are some missing ingredients in that paper, limiting its applicability in practical settings of graph machine learning. In the current paper, we introduce several refinements and extensions to existing results that address these shortcomings. In detail, 1) we extend the main results in the paper to graphon-signals with multidimensional signals (rather than 1D signals), 2) we extend the Lipschitz continuity to MPNNs with readout with respect to cut distance (rather than MPNNs without readout with respect to cut metric), 3) we improve the generalization bound by utilizing robustness-type generalization bounds, and 4) we extend the analysis to non-symmetric graphons and kernels.

Levi Rauchwerger, Ron Levie

Graph Neural Networks Message Passing Neural Networks

Aug 22, 2025

RF-Informed Graph Neural Networks for Accurate and Data-Efficient Circuit Performance Prediction

Accurately predicting the performance of active radio frequency (RF) circuits is essential for modern wireless systems but remains challenging due to highly nonlinear behavior and the high computational cost of traditional simulation tools. Existing machine learning (ML) surrogates often require large datasets to generalize across various topologies or are not accurate on held-out circuits. This work presents a lightweight, data-efficient, and topology-aware graph neural network (GNN) framework for predicting key performance metrics of active RF circuit classes, such as low-noise amplifiers (LNAs), mixers, voltage-controlled oscillators (VCOs), power amplifiers (PAs), and voltage amplifiers (VAs). The proposed framework employs RFIC domain-informed feature indexing to enable cross-topology adaptability by cheap encoding of functional device semantics (e.g., differential pair and varactor transistors) and efficient knowledge transfer. The surrogate model represents circuits using device-terminal graph abstractions to preserve fine-grained connectivity and transistor-level symmetry. The final model is generalized to a wide variety of classes by being trained in parallel. Experimental results demonstrate accurate modeling of multimodal and heavy-tailed RF performance distributions, achieving an average mean relative error (MRE) of 2.71% across nineteen topologies, an improvement of 3.3x and 20x faster in training over prior art, and the generalization to held-out topologies is improved by ~26.2x. Furthermore, this work shows ~36x training data efficiency compared to state-of-the-art, demonstrating its effectiveness for scalable and deployment-ready RF design automation.

Anahita Asadi, Leonid Popryho, Inna Partin-Vaisband

Department of Electrical and Computer Engineering, University of Illinois Chicago, Chicago, IL 60607 USA

Neural Surrogate Modeling Graph Neural Networks Electronic Design Automation Data-Efficient Learning

Jul 27, 2025

Learning Latent Graph Geometry via Fixed-Point Schrödinger-Type Activation: A Theoretical Study

We study neural architectures in which each hidden layer is defined by the stationary state of a dissipative Schrödinger-type dynamics on a learned latent graph. On stable branches, the local stationary problem defines a differentiable implicit graph layer. To learn the graph itself, we optimize over the stratified moduli space of weighted graphs and equip each stratum with a non-degenerate Kähler-Hessian metric that keeps natural-gradient descent and face crossing well posed. We then show that a multilayer stationary network is equivalent to an exact global stationary problem on a supra-graph, and that it admits a penalized global relaxation whose stationary states converge to the exact one as the penalty parameter tends to infinity. Reverse-mode differentiation is recovered as the adjoint of the exact global system, and the penalized adjoint converges to it in the same limit. Finally, under finite-dimensional strong-monotonicity and admissible-lift assumptions, the corresponding represented hypothesis classes coincide among resolvent feed-forward networks, graph-stationary networks, supra-graph stationary systems, and sheaf-based architectures with unitary connection. The resulting structural identifications yield complexity bounds controlled by sparse graph or supra-graph geometry rather than dense ambient connectivity.

Dmitry Pasechnyuk-Vilensky, Martin Takáč

MBZUAI, UAE

Graph Structure Learning Graph Neural Networks Graph Representation Learning Sheaf Neural Networks Neural Network Approximation Theory

May 19, 2025

Graph Alignment for Benchmarking Graph Neural Networks and Learning Positional Encodings

We propose a novel benchmarking methodology for graph neural networks (GNNs) based on the graph alignment problem, a combinatorial optimization task that generalizes graph isomorphism by aligning two unlabeled graphs to maximize overlapping edges. We frame this problem as a self-supervised learning task and present several methods to generate graph alignment datasets using synthetic random graphs and real-world graph datasets from multiple domains. For a given graph dataset, we generate a family of graph alignment datasets with increasing difficulty, allowing us to rank the performance of various architectures. Our experiments prove that there is an optimal task difficulty for having a statistically relevant ranking of different models and that, even on a structure-only task, anisotropic models perform better compared to isotropic ones. To further prove that our synthetic task capture meaningful information, we show its effectiveness for self-supervised GNN pre-training: the learned node embeddings can be leveraged as positional encodings by transformers for graph regression or can be used to reconstruct the full structure of the graph with

98\%

accuracy. To support reproducibility and further research, we provide an open-source Python package to generate graph alignment datasets and benchmark new GNN architectures. The source code is available at https://github.com/adrien-lagesse/graph-alignment-benchmark.

Adrien Lagesse, Marc Lelarge

INRIA, École Normale Supérieure - PSL, Paris, France.

Graph Neural Networks Synthetic Benchmark Generation Positional Encoding Graph Matching

May 17, 2025

Relation-Aware Graph Foundation Model

In recent years, large language models (LLMs) have demonstrated remarkable capability to generalize across diverse natural language processing tasks, inspiring the development of graph foundation models (GFMs) for large-scale pre-training. However, unlike language models with explicit token units, graphs lack a well-defined unit for generalization, making it challenging to design effective pre-training strategies. In this work, we propose REEF, a novel GFM framework that leverages relation tokens as the fundamental units. We construct a vocabulary of relation tokens to encode relational information within graphs. To accommodate diverse relations, we introduce two hypernetworks that adaptively generate the parameters of aggregators and classifiers in graph neural networks based on relation tokens. In addition, we design another hypernetwork to construct dataset-specific projectors and incorporate a dataset-level feature bias into the initial node representations, enhancing flexibility across different datasets with the same relation. Extensive experiments demonstrate that REEF consistently outperforms existing methods in both pre-training and transfer learning, highlighting its potential as a general-purpose graph foundation model.

Jianxiang Yu, Jiapeng Zhu, Yibo Zhao +4

School of Data Science and Engineering, East China Normal University · Ant Group

Graph Neural Networks Graph Representation Learning Graph Foundation Models

May 16, 2025

Understanding and Mitigating Under-Confidence in GNNs from the Final Layer

Graph Neural Networks (GNNs) have demonstrated remarkable effectiveness on graph-based tasks. However, their predictive confidence is often miscalibrated, typically exhibiting under-confidence, which harms the reliability of their decisions. Existing calibration methods for GNNs normally introduce additional calibration components, which fail to capture the intrinsic relationship between the model and the prediction confidence, resulting in limited theoretical guarantees and increased computational overhead. To address this issue, we propose a simple yet efficient graph calibration method. We establish a unified theoretical framework revealing that model confidence is jointly governed by class-centroid-level and node-level calibration at the final layer. Based on this insight, we theoretically show that reducing the weight decay of the final-layer parameters alleviates GNN under-confidence by acting on the class-centroid level, while node-level calibration acts as a finer-grained complement to class-centroid-level calibration, which encourages each test node to be closer to its predicted class prototype in the final-layer representations. Extensive experiments validate the superiority of our method. The code is released at https://github.com/huangJC0429/SCAR.

Jincheng Huang, Jie Xu, Xiaoshuang Shi +3

School of Computer Science and Engineering, University of Electronic Science and Technology of China · Southeast University

Graph Neural Networks Uncertainty Calibration

Mar 31, 2025

Traffic Engineering in Large-scale Networks with Generalizable Graph Neural Networks

Traffic Engineering (TE) in large-scale networks like cloud Wide Area Networks (WANs) and Low Earth Orbit (LEO) satellite constellations is a critical challenge. Although learning-based approaches have been proposed to address the scalability of traditional TE algorithms, their practical application is often hindered by a lack of generalization, high training overhead, and a failure to respect link capacities. This paper proposes TELGEN, a novel TE algorithm that learns to solve TE problems efficiently in large-scale network scenarios, while achieving superior generalizability across diverse network conditions. TELGEN is based on the novel idea of transforming the problem of "predicting the optimal TE solution" into "predicting the optimal TE algorithm", which enables TELGEN to learn and efficiently approximate the end-to-end solving process of classical optimal TE algorithms. The learned algorithm is agnostic to the exact underlying network topology or traffic patterns, and is able to very efficiently solve TE problems given arbitrary inputs and generalize well to unseen topologies and demands. We train and evaluate TELGEN with random and real-world topologies, with networks of up to 5000 nodes and 3.6x10^6 links in testing. TELGEN shows less than 3% optimality gap while ensuring feasibility in all testing scenarios, even when the test network has 2-20x more nodes than the largest training network. It also saves up to 84% TE solving time than traditional interior-point method, and reduces up to 79.6% training time per epoch than the state-of-the-art learning-based algorithm.

Fangtong Zhou, Xiaorui Liu, Ruozhou Yu +1

Department of Computer Science, North Carolina State University, Raleigh, NC, 27606, USA · School of Computing and Augmented Intelligence, Arizona State University, Tempe, AZ, 85287, USA

Graph Neural Networks Learning to Optimize

Mar 16, 2025

GenShin: Guiding Rational Liposome Design by Ranking Liposomal Protein Corona through a Docking-Pose-Free GNN

Rational design of lipid nanoparticles (LNPs) for tissue-specific delivery critically depends on predicting the composition of the protein corona that forms on the lipid surface after intravenous administration. However, conventional characterization of the protein corona relies on costly and time-consuming mass spectrometry experiments, which require physically prepared liposome samples and therefore cannot serve as a pre-synthesis screening strategy for large candidate lipid spaces. The adsorption of plasma proteins onto liposomal surfaces is shaped by lipid chemical structures, protein properties and the biological environment, making this process difficult to simulate directly. In this work, we propose that scoring lipid-plasma protein pairs and ranking the resulting scores can provide a practical signal for revealing the relative composition of the liposomal surface protein corona.Here we introduce GenShin, a geometry-enhanced pose-free graph neural network designed to score lipid-plasma protein pairs. GenShin is pretrained on compound-protein affinity data to initialize a generalizable scoring function and is then fine-tuned on a rank fine-tuning dataset constructed from liposomal protein-corona abundance measurements to adapt the model to lipid-plasma protein pair scoring. Before fine-tuning, GenShin achieves competitive pose-free affinity prediction on the PDBbind v2016 benchmark compared with representative pose-dependent models. CASF-2016 perturbation experiments using the pretrained GenShin model further show that pose-dependent inference substantially degrades when intermolecular poses are unreliable, whereas GenShin remains stable without requiring such poses. This supports the practical advantage of GenShin for large-scale lipid-protein scoring.

Pingfei Zhu, Hongyi Liu, Xueyan Liu +2

Key Laboratory of symbolic Computation and Knowledge Engineering of ministry of education, Jilin University, Qianjin Street 2699, Changchun, Jilin Province, 130012, China · State Key Laboratory of Natural and Biomimetic Drugs, School of Pharmaceutical Sciences, Peking University, Xue Yuan Road 38, Beijing 100191, China

Graph Neural Networks Materials Science Molecular Property Prediction

Jan 15, 2025

Reforge: Low-Latency Distributed GNN Serving with Selective Embedding Recomputation

Graph Neural Networks (GNNs) have been widely adopted for their ability to compute expressive node representations in graph datasets. However, serving GNNs on large graphs is challenging due to the high communication, computation, and memory overheads of constructing and executing computation graphs, which represent information flow across large neighborhoods. Existing approximation techniques in training can mitigate the overheads but, in serving, still lead to high latency and/or accuracy loss. To this end, we propose Reforge, a system that enables low-latency GNN serving for large graphs with minimal accuracy loss through two key ideas. First, Reforge employs selective recomputation of precomputed embeddings, which allows for reusing precomputed computation subgraphs while selectively recomputing a small fraction to minimize accuracy loss. Second, we develop computation graph parallelism, which reduces communication overhead by parallelizing the creation and execution of computation graphs across machines. Our evaluation with large graph datasets and GNN models shows that Reforge significantly outperforms state-of-the-art techniques.

Geon-Woo Kim, Donghyun Kim, Jeongyoon Moon +5

The University of Texas at Austin · Georgia Institute of Technology

Efficient Neural Network Inference Graph Neural Networks Inference-Time Optimization

Nov 29, 2024

MEGA: Message Passing Neural Networks for Multigraphs with EdGe Attributes

Edge-attributed multigraphs, in which multiple edges with distinct attributes connect the same pair of nodes, arise naturally in many real-world systems. In these graphs, effective learning requires preserving information from repeated interactions while distinguishing contributions from different neighbors. Existing neural network solutions for edge-attributed multigraphs remain limited: some lose information from repeated interactions, while others break permutation equivariance. To address this, we introduce neighbor-aware aggregation, an operator that first combines multi-edge features for each neighbor and then aggregates across neighbors. This operator captures per-neighbor statistics that standard single-stage aggregation cannot represent. Building on this operator, we present MEGA-GNN, a model-agnostic message-passing framework for edge-attributed multigraphs. We show that MEGA-GNN is permutation equivariant and has the same asymptotic complexity as standard GNNs with edge updates. We evaluate our approach on datasets from social networks and financial transaction networks. Neighbor-aware aggregation consistently improves GNN performance and matches or surpasses state-of-the-art methods.

H. Çağrı Bilgi, Kubilay Atasu

1Delft University of Technology

Graph Neural Networks Graph Representation Learning Message Passing Neural Networks

Oct 14, 2024

Information propagation dynamics in Deep Graph Networks

Graphs are a highly expressive abstraction for modeling entities and their relations, such as molecular structures, social networks, and traffic networks. Deep Graph Networks (DGNs) have emerged as a family of deep learning models that can effectively process and learn such structured information. However, learning effective information propagation patterns within DGNs remains a critical challenge that heavily influences the model capabilities, both in the static domain and in the temporal domain (where features and/or topology evolve). Given this challenge, this thesis investigates the dynamics of information propagation within DGNs for static and dynamic graphs, focusing on their design as dynamical systems. Throughout this work, we provide theoretical and empirical evidence to demonstrate the effectiveness of our proposed architectures in propagating and preserving long-term dependencies between nodes, and in learning complex spatio-temporal patterns from irregular and sparsely sampled dynamic graphs. In summary, this thesis provides a comprehensive exploration of the intersection between graphs, deep learning, and dynamical systems, offering insights and advancements for the field of graph representation learning and paving the way for more effective and versatile graph-based learning models.

Alessio Gravina

University of Pisa Department of Computer Science

Graph Neural Networks Graph Representation Learning Dynamic Graph Learning Spatiotemporal GNNs

Sep 9, 2024

Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning

Over the past decade, Graph Neural Networks (GNNs) have achieved great success on machine learning tasks with relational data. However, recent studies have found that heterophily can cause significant performance degradation of GNNs, especially on node-level tasks. Numerous heterophilic benchmark datasets have been put forward to validate the efficacy of heterophily-specific GNNs, and various homophily metrics have been designed to help recognize these challenging datasets. Nevertheless, there still exist multiple pitfalls that severely hinder the proper evaluation of new models and metrics: 1) lack of hyperparameter tuning; 2) insufficient evaluation on the truly challenging heterophilic datasets; 3) missing quantitative evaluation for homophily metrics on synthetic graphs. To overcome these challenges, we first train and fine-tune baseline models on

27

most widely used benchmark datasets, and categorize them into three distinct groups: malignant, benign and ambiguous heterophilic datasets. We identify malignant and ambiguous heterophily as the truly challenging subsets of tasks, and to our best knowledge, we are the first to propose such taxonomy. Then, we re-evaluate

11

state-of-the-arts (SOTA) GNNs, covering six popular methods, with fine-tuned hyperparameters on different groups of heterophilic datasets. Based on the model performance, we comprehensively reassess the effectiveness of different methods on heterophily. At last, we evaluate

11

popular homophily metrics on synthetic graphs with three different graph generation approaches. To overcome the unreliability of observation-based comparison and evaluation, we conduct the first quantitative evaluation and provide detailed analysis.

Sitao Luan, Qincheng Lu, Chenqing Hua +3

Mila - Quebec Artiﬁcial Intelligence Institute · 1McGill University

Graph Neural Networks Node Classification Graph Heterophily

Aug 29, 2024

GREAT: A Graph Edge Attention Network for the Electric Vehicle Routing Problem with Asymmetric Costs

Due to the ongoing electrification of transportation systems, energy-based routing problems such as the Electric Vehicle Routing Problem (EVRP) are becoming increasingly important. Unlike Euclidean routing problems, the EVRP involves asymmetric energy costs caused by road topology. Existing learning-based routing approaches are based on graph neural networks (GNNs) or transformer architectures operating on Euclidean node coordinates, making them poorly suited for asymmetric, non-Euclidean edge-based metrics such as energy consumption. To address this, we propose the Graph Edge Attention Network (GREAT), a novel GNN-related architecture that operates purely in edge space rather than on node coordinates, making it naturally compatible with asymmetric routing costs. Integrated into an end-to-end reinforcement learning framework, GREAT jointly optimizes routing and charging decisions for the EVRP. We train the model using real-world energy consumption data from San Francisco, derived from physical road networks enriched with topological features, and evaluate generalization on datasets from San Francisco, Vienna, and Gothenburg. Across diverse battery sizes (15-40 kWh) and customer demand distributions, GREAT outperforms a strong HGS-based EVRP heuristic in most tested settings, achieving energy reductions of up to 8.78% while reducing runtime by a factor of 60. Moreover, we benchmark against a custom adaptive large neighborhood search (ALNS) that jointly optimizes routing and charging. GREAT achieves competitive performance at a faster runtime, and we show that the ALNS can profit from a warm start with the GREAT solution. We further evaluate GREAT on standard (asymmetric) routing problems, including Traveling Salesman Problem, Capacitated Vehicle Routing Problem, and Orienteering Problem, where it achieves state-of-the-art performance among neural methods for non-Euclidean settings.

Attila Lischka, Filip Rydin, Jiaming Wu +2

Chalmers University of Technology · University of Gothenburg

Vehicle Routing Graph Neural Networks RL for Combinatorial Optimization Electric Vehicle Charging

Jul 5, 2024

SSP-GNN: Learning to Track via Bilevel Optimization

We propose a graph-based tracking formulation for multi-object tracking (MOT) where target detections contain kinematic information and re-identification features (attributes). Our method applies a successive shortest paths (SSP) algorithm to a tracking graph defined over a batch of frames. The edge costs in this tracking graph are computed via a message-passing network, a graph neural network (GNN) variant. The parameters of the GNN, and hence, the tracker, are learned end-to-end on a training set of example ground-truth tracks and detections. Specifically, learning takes the form of bilevel optimization guided by our novel loss function. We evaluate our algorithm on simulated scenarios to understand its sensitivity to scenario aspects and model hyperparameters. Across varied scenario complexities, our method compares favorably to a strong baseline.

Griffin Golias, Masa Nakura-Fan, Vitaly Ablavsky

Applied Physics Laboratory University of Washington Seattle, WA 98105 USA · Paul G. Allen School of Computer Science University of Washington Seattle, WA 98105 USA

Graph Neural Networks Visual Object Tracking Multi-Object Tracking

Jun 7, 2024

GENIE: Watermarking Graph Neural Networks for Link Prediction

The rapid adoption, usefulness, and resource-intensive training of Graph Neural Network (GNN) models have made them an invaluable intellectual property in graph-based machine learning. However, their wide-spread adoption also makes them susceptible to stealing, necessitating robust Ownership Demonstration (OD) techniques. Watermarking is a promising OD framework for deep neural networks, but existing methods fail to generalize to GNNs due to the non-Euclidean nature of graph data. Existing works on GNN watermarking primarily focus on node and graph classification, overlooking Link Prediction (LP). In this paper, we propose GENIE (watermarking Graph nEural Networks for lInk prEdiction), the first scheme to watermark GNNs for LP. GENIE creates a novel backdoor for both node-representation and subgraph-based LP methods, utilizing a unique trigger set and a secret watermark vector. Our OD scheme is equipped with Dynamic Watermark Thresholding (DWT), ensuring high verification probability while addressing practical issues in existing OD schemes. We extensively evaluate GENIE across 4 diverse model architectures (i.e., SEAL, GCN, GraphSAGE and NeoGNN), 7 real-world datasets and 21 watermark removal techniques and demonstrate its robustness to watermark removal and ownership piracy attacks. Finally, we discuss adaptive attacks against GENIE and a defense strategy to counter it. The codebase and related artifacts are publicly available at our Project Page.

Venkata Sai Pranav Bachina, Aaryan Ajay Sharma, Ankit Gangwal +1

IIIT Hyderabad, India

Graph Neural Networks Robust Watermarking

Mar 17, 2024

Graph Unitary Message Passing

Unitarity is a useful principle for stabilizing deep neural networks, but in graph neural networks (GNNs) instability is induced not only by learnable parameters but also by the graph propagation operator. Motivated by this distinction, we propose Graph Unitary Message Passing (GUMP), a message-passing framework that uses a unitary propagation operator on a transformed graph to avoid graph-induced exponential decay under repeated propagation. GUMP combines (i) a graph transformation that maps an input graph to an Eulerian line-graph construction admitting unitary adjacency matrices, and (ii) a practical unitary projection procedure based on Newton-Schulz iteration. Theoretical analysis clarifies that, under standard analysis assumptions, unitary propagation keeps the graph-propagation term depth-stable, while vanilla normalized propagation exhibits exponential decay in its non-trivial spectral components. Across synthetic long-range tasks, TUDataset benchmarks, and LRGB datasets, GUMP improves over vanilla message passing and achieves competitive or superior performance against strong baselines. Code is available at https://github.com/ucker/gump_code.

Haiquan Qiu, Quanming Yao

Department of Electrical Engineering, Tsinghua University · 2Beijing National Research Center for Information Science and Technology · 3State Key laboratory of Space Network and Communications

Graph Neural Networks Message Passing Neural Networks

Mar 2, 2024

Teaching MLP More Graph Information: A Three-stage Multitask Knowledge Distillation Framework

We study the challenging problem for inference tasks on large-scale graph datasets of Graph Neural Networks: huge time and memory consumption, and try to overcome it by reducing reliance on graph structure. Even though distilling graph knowledge to student MLP is an excellent idea, it faces two major problems of positional information loss and low generalization. To solve the problems, we propose a new three-stage multitask distillation framework. In detail, we use Positional Encoding to capture positional information. Also, we introduce Neural Heat Kernels responsible for graph data processing in GNN and utilize hidden layer outputs matching for better performance of student MLP's hidden layers. To the best of our knowledge, it is the first work to include hidden layer distillation for student MLP on graphs and to combine graph Positional Encoding with MLP. We test its performance and robustness with several settings and draw the conclusion that our work can outperform well with good stability. Code implementation is in https://github.com/lijunxian111/KMP.

Junxian Li, Bin Shi, Erfei Cui +2

Xi’an Jiaotong University · Arizona State University, Tempe, USA · Tongji University, Shanghai, China

Knowledge Distillation Graph Neural Networks Cross-Architecture Knowledge Distillation Graph Representation Learning Feature-Based Knowledge Distillation

Jun 8, 2023

Point-Voxel Absorbing Graph Representation Learning for Event Stream based Recognition

Sampled point and voxel methods are usually employed to downsample the dense events into sparse ones. After that, one popular way is to leverage a graph model which treats the sparse points/voxels as nodes and adopts graph neural networks (GNNs) to learn the representation of event data. Although good performance can be obtained, however, their results are still limited mainly due to two issues. (1) Existing event GNNs generally adopt the additional max (or mean) pooling layer to summarize all node embeddings into a single graph-level representation for the whole event data representation. However, this approach fails to capture the importance of graph nodes and also fails to be fully aware of the node representations. (2) Existing methods generally employ either a sparse point or voxel graph representation model which thus lacks consideration of the complementary between these two types of representation models. To address these issues, we propose a novel dual point-voxel absorbing graph representation learning for event stream data representation. To be specific, given the input event stream, we first transform it into the sparse event cloud and voxel grids and build dual absorbing graph models for them respectively. Then, we design a novel absorbing graph convolutional network (AGCN) for our dual absorbing graph representation and learning. The key aspect of the proposed AGCN is its ability to effectively capture the importance of nodes and thus be fully aware of node representations in summarizing all node representations through the introduced absorbing nodes. Extensive experiments on multiple event-based classification benchmark datasets fully validated the effectiveness of our framework.

Yuxiang Zhang, Chengguo Yuan, Xiao Wang +2

aSchool of Computer Science and Technology, Anhui University, Hefei 230601, China.

Event-Based Vision Graph Neural Networks Graph Representation Learning Graph Pooling 3D Representation Learning