Physics-Aware Random Walk Fingerprints for Scalable Power Grid Graph Classification

Adnan Anwar

cs.LGSep 4, 2026

Physics-Aware Random Walk Fingerprints for Scalable Power Grid Graph Classification

Authors: Adnan Anwar

Organizations: School of Information Technology and a member of the Deakin Cyber Research & Innovation Hub, Deakin University, Melbourne, Australia

Abstract

Recent benchmarks such as PowerGraph provide large collections of power-grid graphs for cascading-failure classification. Graph neural networks (GNNs) achieve strong predictive performance on this task, but typically require end-to-end training and model-specific tuning, while their latent representations can be difficult to relate to physically meaningful propagation patterns. Random Walk Fingerprints (RWF) offer a scalable and interpretable alternative, but existing variants primarily emphasise topology and node-level information, leaving grid-relevant operational edge states in the walk dynamics. We propose Multi-Channel Physics-Aware Random Walk Fingerprints (MC-PA-RWF) for power systems, a lightweight graph-level representation framework that introduces physical edge states into random-walk propagation. The method constructs multiple edge-weighted channels from domain-relevant attributes, extracts a channel-specific fingerprint from each weighted graph, and concatenates the resulting vectors into a compact representation. Experiments on three PowerGraph benchmark systems show substantial improvements over topology-only RWF and competitive balanced accuracy against strong GNN baselines, including Graph Convolutional Networks (GCN), Graph Attention Networks (GAT), Graph Isomorphism Networks with edge features (GINE), and Transformer-based Graph Convolutional Networks (TransformerConv). At the largest evaluated settings, the node-edge extension MC-PA-RWF+ achieves around 98.04% - 99.32% balanced accuracy and improves failure-class F1 over the strongest GNN baseline by 1.60 -- 5.84 percentage points, with statistically significant gains across all three systems.

Figures & tables

Fig. 1 : Overview of the proposed MC-PA-RWF framework.

Method	Time complexity
Random walk kernel [ 12 ]	$O(N^{2}n^{3})$
NetLSD [ 13 ]	$O(Nrm+Nr^{2}n)$
FGSD [ 14 ]	$O(Nn^{2})$
NetSimile [ 16 ]	$O(Nf(n+n\log n))$
RWF-D [ 8 ]	$O(N\tau_{c}mn)$
RWF-D-feature [ 8 ]	$O(N\tau_{c}(mn+pn^{2}))$

TABLE I : Time complexity comparison of graph methods.

Dataset	Nodes	Edges	Graphs	Used	Classes
IEEE24	24	38	21,500	1k–21.5k	Stable / Failure-prone
IEEE39	39	46	28,000	1k–28k	Stable / Failure-prone
UK	29	99	64,000	5k–64k	Stable / Failure-prone

TABLE II : PowerGraph graph-level classification datasets [ 2 ] .

Family	Method	1k	3k	5k	10k	15k	21.5k
RWF (Original)	RWF-D [ 8 ]	71.78 $\pm$ 4.15	72.29 $\pm$ 4.12	66.75 $\pm$ 1.22	67.51 $\pm$ 1.77	67.06 $\pm$ 1.26	67.04 $\pm$ 0.74
	RWF-D-feature [ 8 ]	93.00 $\pm$ 5.70	96.09 $\pm$ 1.86	96.33 $\pm$ 1.59	97.02 $\pm$ 1.11	97.50 $\pm$ 1.00	97.81 $\pm$ 0.45
GNN	GCN [ 4 ]	75.53 $\pm$ 2.66	85.01 $\pm$ 4.50	89.04 $\pm$ 1.54	92.80 $\pm$ 0.85	93.90 $\pm$ 1.14	95.23 $\pm$ 1.25
	GAT [ 5 ]	76.98 $\pm$ 2.06	88.50 $\pm$ 1.95	90.29 $\pm$ 1.38	91.96 $\pm$ 1.47	93.34 $\pm$ 1.99	92.90 $\pm$ 2.06
	GINE [ 6 ]	83.38 $\pm$ 4.54	93.45 $\pm$ 2.74	92.51 $\pm$ 2.81	96.82 $\pm$ 0.62	97.78 $\pm$ 0.51	97.84 $\pm$ 0.82
	TransformerConv [ 7 ]	88.43 $\pm$ 3.20	94.42 $\pm$ 1.96	95.23 $\pm$ 1.93	97.59 $\pm$ 0.67	98.06 $\pm$ 1.08	98.76 $\pm$ 0.49

TABLE III : IEEE24 bus test system balanced accuracy (%) across different graph sizes

Fig. 2 : Classification performance across dataset sizes for IEEE24, IEEE39, and UK benchmark test systems.

Family	Method	1k	3k	5k	10k	20k	28k
RWF (Original)	RWF-D [ 8 ]	62.43 $\pm$ 7.51	69.88 $\pm$ 3.98	73.28 $\pm$ 3.16	69.51 $\pm$ 2.54	71.23 $\pm$ 1.86	71.96 $\pm$ 1.48
	RWF-D-feature [ 8 ]	73.65 $\pm$ 7.96	92.03 $\pm$ 3.35	95.74 $\pm$ 2.70	98.12 $\pm$ 0.83	97.66 $\pm$ 0.72	98.15 $\pm$ 0.37
GNN	GCN [ 4 ]	76.67 $\pm$ 9.20	82.69 $\pm$ 3.50	84.07 $\pm$ 3.37	89.05 $\pm$ 2.50	91.04 $\pm$ 1.69	93.96 $\pm$ 1.30
	GAT [ 5 ]	78.22 $\pm$ 6.09	83.09 $\pm$ 4.33	84.56 $\pm$ 3.86	89.01 $\pm$ 1.86	90.13 $\pm$ 2.37	90.48 $\pm$ 0.96
	GINE [ 6 ]	86.75 $\pm$ 9.39	91.75 $\pm$ 2.49	94.33 $\pm$ 1.31	96.56 $\pm$ 1.52	97.87 $\pm$ 0.55	97.41 $\pm$ 0.80
	TransformerConv [ 7 ]	77.63 $\pm$ 11.17	88.25 $\pm$ 6.94	90.76 $\pm$ 6.27	94.36 $\pm$ 2.98	97.17 $\pm$ 1.07	97.76 $\pm$ 0.81

TABLE IV : IEEE39 bus test system balanced accuracy (%) across different graph sizes.

Method	1k	3k	5k	10k	20k	28k
RWF-D-feature [ 8 ] $\pm$	82.05 $\pm$ 6.76	93.99 $\pm$ 3.71	97.22 $\pm$ 1.70	98.44 $\pm$ 0.48	98.51 $\pm$ 0.34	98.63 $\pm$ 0.38
MC-PA-RWF (Adpt.)	87.19 $\pm$ 7.16	95.46 $\pm$ 3.66	97.84 $\pm$ 2.57	98.50 $\pm$ 0.51	98.92 $\pm$ 0.39	98.91 $\pm$ 0.40

TABLE V : IEEE39 fusion results: balanced accuracy (%)

Family	Method	5k	10k	20k	64k
RWF (Original)	RWF-D [ 8 ]	50.00 $\pm$ 0.00	50.30 $\pm$ 0.68	50.00 $\pm$ 0.00	50.77 $\pm$ 0.47
	RWF-D-feature [ 8 ]	50.00 $\pm$ 0.00	50.00 $\pm$ 0.00	50.14 $\pm$ 0.30	51.79 $\pm$ 0.27
	RWF-D-feature-balanced	50.10 $\pm$ 4.85	52.84 $\pm$ 5.25	57.51 $\pm$ 4.41	58.54 $\pm$ 1.94
GNN	GCN [ 4 ]	91.46 $\pm$ 8.17	94.39 $\pm$ 1.75	95.10 $\pm$ 1.70	96.43 $\pm$ 1.25
	GAT [ 5 ]	93.28 $\pm$ 7.01	90.71 $\pm$ 15.25	95.09 $\pm$ 1.30	98.62 $\pm$ 0.61
	GINE [ 6 ]	94.87 $\pm$ 3.72	97.16 $\pm$ 2.16	96.37 $\pm$ 1.87	99.36 $\pm$ 0.30

TABLE VI : UK test system balanced accuracy (%) across different graph sizes.

Dataset	Size	Best GNN	GNN F1	Prop. F1	$p$ -value	Stat. Sig.
IEEE24 [ 2 ]	21.5k	TransConv	97.24%	98.84%	0.0015	Yes
IEEE39 [ 2 ]	28k	TransConv	91.03%	96.87%	0.0024	Yes
UK [ 2 ]	64k	TransConv	96.95%	99.05%	0.0147	Yes

TABLE VII : Failure Class comparison against the best GNNs

Graph Classification

Graph classification assigns labels to whole graphs, using their connectivity, node and edge attributes, and learned representations.

See all 38 papers

Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features
Sep 24, 2026Anne M. Tumlin, Ben Wooding, Zhenxuan Shao +3Neural Network Verification Reachability Analysis
Vanderbilt University, Nashville, TN, USA
PowerModelsGAT-AI: Physics-Informed Graph Attention for Multi-System Power Flow with Continual Learning
Feb 24, 2026Chidozie Ezeakunne, Jose E. Tabarez, Reeju Pokharel +1Physics-Informed GNNs Power Systems
Los Alamos National Laboratory, Los Alamos, NM, USA · Department of Physics, University of Central Florida, Orlando, FL 32816 USA
Graph Machine Learning: An Opportunity for Power Systems
Aug 17, 2026Martin Sadric, Sebastian Pütz, Christian Nauck +4Power Systems Graph Neural Networks

Sep 24, 2026J/K move · Enter open · S save

Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features

Anne M. Tumlin, Ben Wooding, Zhenxuan Shao, Diego Manzanas Lopez+2

Vanderbilt University, Nashville, TN, USA

Neural Network Verification Reachability Analysis Certified Robustness Power Systems

Open paper AskPDF arXiv

Graph neural networks (GNNs) have become a prominent approach for developing fast, topology-aware surrogates in electric power systems, supporting tasks such as power flow (PF) analysis, optimal power flow (OPF) estimation, and cascading failure analysis (CFA). Despite this growing use, formally verifying GNN-based models remains challenging, with existing methods limited in scope. We extend the neural network verification (NNV) framework to graph-structured inputs through GraphStar sets, a generalization of Star sets that captures uncertainty over both node and edge features. This extension enables the propagation of linear message-passing operations and the sound approximation of ReLU nonlinearities for GNN architectures, including graph convolutional network (GCN) and graph isomorphism network with edge features (GINE) layers. We evaluate GNNV across three power system tasks, PF, OPF, and CFA, on the IEEE-24, IEEE-39, and IEEE-118 test cases, as well as two standard graph classification benchmarks, ENZYMES and PROTEINS. Our results show that GNNV provides tighter robustness guarantees than CORA on graph classification models with ReLU-based activations and, for the first time, delivers edge-aware robustness guarantees for GINE-based PF and OPF models under joint node and edge perturbations.

Abstract

Graph Classification

Explore similar work

Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features

PowerModelsGAT-AI: Physics-Informed Graph Attention for Multi-System Power Flow with Continual Learning

Graph Machine Learning: An Opportunity for Power Systems