Graph Neural Networks

Also known as GNN

Follow this topic Ask about this topic

Graph Neural Networks (GNNs) study how to learn from data whose entities and relationships form a graph, supporting tasks such as node classification, link prediction, and graph or molecular property prediction. Common approaches include message-passing networks such as GCN, GraphSAGE, and GIN, attention-based Graph Transformers, and spectral, geometric, or higher-order methods that encode richer structure. They are used on benchmarks such as Cora and ogbn-arxiv, as well as in molecular modeling, recommender systems, scientific simulation, and network control. Key open challenges include handling heterophilic graphs, preserving useful information in deep networks without oversmoothing or oversquashing, and achieving reliable generalization, robustness, and efficiency on large or shifting graphs.

Latest papers

752 papers73 papers in the last four weeks, down 13% on the four weeks before. 0.5% of all new papers.

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 Contact Force Estimation

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

Graphon Theory 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

Jun 14, 2025

RAW-Explainer: Post-hoc Explanations of Path Reasoning Graph Neural Networks for Knowledge Graph Completion

Path reasoning graph neural networks have demonstrated state-of-the-art performance on knowledge graph completion tasks such as link prediction. However, interpreting their predictions remains a challenging open problem, as most GNN explainability methods target node-level or graph-level tasks. In this paper, we propose RAW-Explainer (

\underline{Ra}

ndom

\underline{W}

alk Explainer), a novel explainability method tailored to path reasoning GNNs that generates connected, concise, and interpretable subgraph explanations for link prediction in knowledge graphs. Our method uses heterogeneous information to identify factual explanations and encourages connectivity through a random walk objective, using a parameterized model for efficient collective explanation. Furthermore, RAW-Explainer overcomes the distribution shift issue when evaluating explanatory subgraphs that are orders of magnitude smaller than the full graph by proposing a robust evaluator that generalizes to the subgraph distribution. Extensive results on standard knowledge graph completion benchmarks demonstrate that our approach strikes a balance between explanation quality and computational efficiency. Code and data are available at: https://github.com/colab-nyuad/RAWExplainer

Ryoji Kubo, Samyam Lamichhane, Djellel Difallah

New York University Abu Dhabi, Abu Dhabi, United Arab Emirates

GNN Explainability Graph Neural Networks KG Completion

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 · Singapore Management University · Southeast University +1

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

Mar 4, 2025

Incorporating graph neural network into route choice model

Route choice models are one of the most important foundations for transportation research. Traditionally, theory-based models have been utilized for their great interpretability, such as logit models and Recursive logit models. More recently, machine learning approaches have gained attentions for their better prediction accuracy. In this study, we propose novel hybrid models that integrate the Recursive logit model with Graph Neural Networks (GNNs) to enhance both predictive performance and model interpretability. To the authors' knowldedge, GNNs have not been utilized for route choice modeling, despite their proven effectiveness in capturing road network features and their widespread use in other transportation research areas. We mathematically show that our use of GNN is not only beneficial for enhancing the prediction performance, but also relaxing the Independence of Irrelevant Alternatives property without relying on strong assumptions. This is due to the fact that a specific type of GNN can efficiently capture multiple cross-effect patterns on networks from data. By applying the proposed models to one-day travel trajectory data in Tokyo, we confirmed their higher prediction accuracy compared to the existing models.

Yuxun Ma, Toru Seo

Department of Civil and Environmental Engineering, Institute of Science Tokyo, 2-12-1-M6-10, Meguro, Ookayama, 152-8552, Tokyo, Japan

Discrete Choice Modeling Graph Neural Networks

Feb 19, 2025

Towards Invariance to Node Identifiers in Graph Neural Networks

Message-Passing Graph Neural Networks (GNNs) are known to have limited expressive power, due to their message passing structure. One mechanism for circumventing this limitation is to add unique node identifiers (IDs), which break the symmetries that underlie the expressivity limitation. In this work, we highlight a key limitation of the ID framework, and propose an approach for addressing it. We begin by observing that the final output of the GNN should clearly not depend on the specific IDs used. We then show that in practice this does not hold, and thus the learned network does not possess this desired structural property. Such invariance to node IDs may be enforced in several ways, and we discuss their theoretical properties. We then propose a novel regularization method that effectively enforces ID invariance to the network. Extensive evaluations on both real-world and synthetic tasks demonstrate that our approach significantly improves ID invariance and, in turn, often boosts generalization performance.

Maya Bechler-Speicher, Moshe Eliasof, Carola-Bibiane Schonlieb +2

Blavatnik School of Computer Science, Tel-Aviv University · Meta · Department of Applied Mathematics and Theoretical Physics, University of Cambridge +3

Graph Neural Networks Invariant Representation Learning GNN Expressivity

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

Nov 17, 2024

Label Ensemble Perspective for Reduced-Complexity Graph Node Classification under Label Noise

Graph Neural Networks (GNNs) have been widely employed for semi-supervised node classification tasks on graphs. However, the performance of GNNs is significantly affected by label noise, that is, a small amount of incorrectly labeled nodes can substantially misguide model training. Mainstream solutions define node classification with label noise (NCLN) as a reliable labeling task, often introducing node similarity with quadratic computational complexity to more accurately assess label reliability. To this end, in this paper, we introduce the Label Ensemble Graph Neural Network (LEGNN), a lower complexity method for robust GNNs training against label noise. LEGNN reframes NCLN as a label ensemble task, gathering informative multiple labels instead of constructing a single reliable label, avoiding high-complexity computations for reliability assessment. Specifically, LEGNN conducts a two-step process: bootstrapping neighboring contexts and robust learning with gathered multiple labels. In the former step, we apply random neighbor masks for each node and gather the predicted labels as a high-probability label set. This mitigates the impact of inaccurately labeled neighbors and diversifies the label set. In the latter step, we utilize a partial label learning based strategy to aggregate the high-probability label information for model training. Additionally, we symmetrically gather a low-probability label set to counteract potential noise from the high-probability label set. Extensive experiments on six datasets demonstrate that LEGNN achieves strong classification performance while maintaining computational efficiency. Moreover, it exhibits good scalability on datasets with over one hundred thousand nodes and one million edges.

Rui Zhao, Bin Shi, Zhiming Liang +4

School of Computer Science and Technology, Xi’an Jiaotong University, China · Ministry of Education Key Laboratory of Intelligent Networks and Network Security, China · Shaanxi Province Key Laboratory of Big Data Knowledge Engineering, China +2

Graph Neural Networks Node Classification Graph-Based Semi-Supervised Learning

Nov 13, 2024

Graph Neural Networks for Supply Chain Management: A Framework and Real World Benchmark

Graph Neural Networks (GNNs) have recently gained traction in transportation, bioinformatics, language and image processing, but research on their application to supply chain management remains limited. Supply chains are inherently graph-like, making them ideal for GNN methodologies, which can optimize and solve complex problems. The barriers include a lack of proper conceptual foundations, familiarity with graph applications in SCM, and real-world benchmark datasets for GNN-based supply chain research. To address this, we discuss and connect supply chains with graph structures for effective GNN application, providing detailed formulations, examples, mathematical definitions, and task guidelines. Additionally, we present a multi-perspective real-world benchmark dataset from a leading FMCG company in Bangladesh, focusing on supply chain planning. We discuss various supply chain tasks using GNNs and benchmark several state-of-the-art models on homogeneous and heterogeneous graphs across six supply chain analytics tasks. Our analysis shows that GNN-based models consistently outperform statistical Machine Learning and other Deep Learning models by around 10-30% in regression, 10-30% in classification and detection tasks, and 15-40% in anomaly detection tasks on designated metrics. With this work, we lay the groundwork for solving supply chain problems using GNNs, supported by conceptual discussions, methodological insights, and a comprehensive dataset.

Azmine Toushik Wasi, MD Shafikul Islam

Department of Industrial and Production Engineering, Shahjalal University of Science and Technology, Sylhet, Bangladesh · Department of Mechanincal and Industrial Engineering, Louisiana State University, Baton Rounge, LA, 70803, USA

Supply Chain Management Graph 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

Aug 2, 2024

Physics Inspired Neural Networks Enable Efficient Graph Coloring

Combinatorial optimization problems near algorithmic phase transitions represent a fundamental challenge for both classical algorithms and machine learning approaches. Among them, graph coloring is a prototypical constraint satisfaction problem characterized by phase transitions that fragment the solution space into distinct clusters, making the search for valid solutions challenging. Here we introduce a physics-inspired neural framework that learns to solve large-scale graph coloring instances by combining graph neural networks with statistical-mechanics principles. Our approach integrates a planting-based supervised signal, symmetry-breaking regularization, and iterative noise-annealed neural dynamics to navigate complex solution landscapes. When the number of iterations scales quadratically with graph size, the learned solver successfully tackles increasingly challenging instances, even in regimes where finding valid solutions becomes particularly difficult, demonstrating its ability to extract meaningful information from the graph structure. The model generalizes from small training graphs to instances up to 20 times larger, demonstrating that neural architectures can learn scalable algorithmic strategies that remain effective in hard connectivity regions. These results establish a general framework for learning neural solvers that operate near fundamental phase boundaries in combinatorial optimization and inference.

Lorenzo Colantonio, Andrea Cacioppo, Federico Scarpati +3

Department of Physics, Sapienza University of Rome

Combinatorial Optimization Neural Combinatorial Optimization Graph Neural Networks

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 24, 2024

GC4NC: A Benchmark Framework for Graph Condensation on Node Classification with New Insights

Graph condensation (GC) is an emerging technique designed to learn a significantly smaller graph that retains the essential information of the original graph. This condensed graph has shown promise in accelerating graph neural networks while preserving performance comparable to those achieved with the original, larger graphs. Additionally, this technique facilitates downstream applications like neural architecture search and deepens our understanding of redundancies in large graphs. Despite the rapid development of GC methods, particularly for node classification, a unified evaluation framework is still lacking to systematically compare different GC methods or clarify key design choices for improving their effectiveness. To bridge these gaps, we introduce GC4NC, a comprehensive framework for evaluating diverse GC methods on node classification across multiple dimensions including performance, efficiency, privacy preservation, denoising ability, NAS effectiveness, and transferability. Our systematic evaluation offers novel insights into how condensed graphs behave and the critical design choices that drive their success. These findings pave the way for future advancements in GC methods, enhancing both performance and expanding their real-world applications. Our code is available at https://github.com/Emory-Melody/GraphSlim/tree/main/benchmark.

Shengbo Gong, Juntong Ni, Noveen Sachdeva +2

Emory University · Google Deepmind

Graph Neural Networks Node Classification

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 GNN Watermarking

Jun 3, 2024

The Interpretable and Effective Graph Neural Additive Networks

Graph Neural Networks (GNNs) have emerged as the predominant approach for learning over graph-structured data. However, most GNNs operate as black-box models and require post-hoc explanations, which may not suffice in high-stakes scenarios where transparency is crucial. In this paper, we present a GNN that is interpretable by design. Our model, Graph Neural Additive Network (GNAN), is a novel extension of the interpretable class of Generalized Additive Models, and can be visualized and fully understood by humans. GNAN is designed to be fully interpretable, offering both global and local explanations at the feature and graph levels through direct visualization of the model. These visualizations describe exactly how the model uses the relationships between the target variable, the features, and the graph. We demonstrate the intelligibility of GNANs in a series of examples on different tasks and datasets. In addition, we show that the accuracy of GNAN is on par with black-box GNNs, making it suitable for critical applications where transparency is essential, alongside high accuracy.

Maya Bechler-Speicher, Amir Globerson, Ran Gilad-Bachrach

Blavatnik School of Computer Science, Tel-Aviv University · Department of Bio-Medical Engineering, Edmond J. Safra Center for Bioinformatics, Tel-Aviv University

Graph Neural Networks GNN Explainability Interpretable ML

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 Over-Smoothing in GNNs

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

Graph Positional Encoding 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

Jun 3, 2023

Harnessing Trust in Directed Graphs: Redefining Robustness of Graph Learning

Existing research on robust Graph Neural Networks (GNNs) focuses predominantly on undirected graphs, overlooking the trustworthiness inherent in the link directions of directed graphs. In this work, we analyze the limitations of current approaches from both the attack and defense perspectives and redefine the robustness of GNNs in directed graphs. From the attack side, we introduce a more realistic directed graph attack setting that addresses the shortcomings of existing attacks. From the defense side, we propose a simple yet effective message-passing framework that serves as a plug-in layer to strengthen GNN robustness while avoiding a false sense of robustness. Our findings show that the trust signals encoded in directed graphs can be harnessed to substantially improve the robustness of GNNs. When combined with existing defense strategies, the framework achieves state-of-the-art robust performance alongside strong clean accuracy against both transfer and adaptive attacks. These results point to a novel and promising direction for strengthening the robustness of graph deep learning.

Zhichao Hou, Xitong Zhang, Wei Wang +2

North Carolina State University · Michigan State University · Meta +1

Graph Neural Networks Adversarial Robustness Graph Robustness Adversarial Attacks