PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Adnan Anwar

arXiv:2609.04943v1cs.LGeess.SY

TL;DR

Power-grid graph classification needs representations that capture operational edge states alongside topology, while existing GNNs can be costly to tune and difficult to interpret physically. MC-PA-RWF adds multiple physics-aware edge-weighted propagation channels to RWF and concatenates their fingerprints. Across three PowerGraph systems, MC-PA-RWF+ achieves 98.04%–99.32% balanced accuracy and significantly improves failure-class F1 over the best GNN baseline.

  • Problem

    Power-grid classification methods need to capture operational edge states because topology-only RWF and node-focused variants do not direct walk propagation using critical line conditions.

  • Method

    MC-PA-RWF constructs multiple edge-weighted channels from physical attributes, extracts channel-specific RWF fingerprints, and concatenates them; MC-PA-RWF+ appends selected node-edge features.

  • Results

    98.04%–99.32% balanced accuracy and a 1.60–5.84 percentage-point failure-class F1 improvement over the best GNN baseline were achieved at the largest evaluated sizes, with significant gains across all three systems.

  • Takeaways & Limitations

    Physics-aware edge states provide essential graph-level classification information, while MC-PA-RWF offers a scalable and transparent alternative to fully latent graph representations.

Abstract

from arXiv · show

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 \textit{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.

I. INTRODUCTION

Power-grid graph classification requires representations that capture operational edge states, not topology alone. MC-PA-RWF addresses this gap with interpretable multi-channel physics-aware random walks and shows strong benchmark performance.

  • Power-system security depends on how stress, capacity limits, and failure effects propagate through attributed electrical connections, not topology alone.
  • GNNs model attributed power-grid graphs effectively, but require model-specific optimisation and tuning, while their latent representations can be difficult to relate to physical propagation patterns.
  • Standard RWF offers scalable, interpretable graph-level vectors but is primarily topology-driven and does not let edge attributes direct walk dynamics.
  • MC-PA-RWF constructs multiple edge-weighted channels for relationships such as flow intensity, capacity margin, coupling strength, and overload severity, then concatenates channel-specific fingerprints.
  • Experiments on IEEE24, IEEE39, and UK PowerGraph systems improve over topology-only RWF, remain competitive with GNN baselines, and improve failure-class detection.

A. Graph Classification Methods

Graph-classification methods trade off scalability, interpretability, and domain sensitivity. MC-PA-RWF targets this trade-off by combining fixed-length random-walk descriptors with physics-aware edge information.

  • Graph kernels capture structural patterns but can require pairwise graph comparisons, producing quadratic scaling with the number of graphs.
  • Fixed-length descriptors such as NetLSD, FGSD, and NetSimile scale more readily but may omit domain-specific interaction patterns driving cyber-physical outcomes.
  • RWF independently maps each graph to a compact fixed-length vector, offering a lightweight and interpretable alternative to pairwise kernels and neural training.
  • GNNs learn graph representations for power-system tasks, but end-to-end training requires optimisation and tuning, and latent features may be difficult to interpret physically.
  • MC-PA-RWF extends RWF by using flow intensity, capacity margin, coupling strength, and overload severity as edge-weighted channels that shape walk propagation.
  • An attributed graph is represented by node and edge sets, topology, node features, edge features, and a graph-level label, with a classifier trained on extracted vectors.

B. Random Walk Fingerprints (RWF)

RWF summarizes multi-step connectivity into fixed-length graph fingerprints using structurally aligned node groups. MC-PA-RWF preserves this scalable framework while adding edge-state-dependent propagation views.

  • RWF constructs an unsupervised graph-level representation by summarising random-walk connectivity over structurally aligned node groups.
  • The τ-step walk matrix records propagation strength between nodes, and RWF aggregates loop, within-group, and cross-group statistics across walk lengths.
  • Collecting these statistics yields a fixed-length fingerprint invariant to node ordering and compatible with graphs of different sizes.
  • Standard RWF is primarily topology-driven, whereas MC-PA-RWF extracts a separate RWF block from each physics-aware edge-weighted channel and concatenates the blocks.

A. Problem Formulation and Overview

MC-PA-RWF converts attributed power-grid edges into multiple normalized weighted views, applies channel-specific random-walk fingerprints, and concatenates them into a graph representation. The design preserves topology while encoding complementary physical operating conditions.

  • A. Problem Formulation and Overview: An attributed graph contains node and edge sets, topology, node attributes, edge attributes, and a graph-level label; the objective is a fixed-length fingerprint for classification.
  • A. Problem Formulation and Overview: MC-PA-RWF transforms edge attributes into weighted adjacency matrices, extracts one structural RWF fingerprint per channel, and concatenates the results.
  • A. Problem Formulation and Overview: Each channel represents a distinct physical interaction pattern over the same graph support, so the final representation contains multiple edge-state-dependent propagation views.
  • B. Physics-Aware Edge-Channel Construction: For each edge, a channel map converts its feature vector into a non-negative undirected weight, while non-edges receive zero weight.
  • B. Physics-Aware Edge-Channel Construction: The weighted channels preserve the original topology while modifying random-walk dynamics according to channel-specific physical information.
  • B. Physics-Aware Edge-Channel Construction: Power-grid edge features include active and reactive flows, line reactance, and rating; derived quantities include apparent flow, loading ratio, overload, remaining margin, and coupling.
  • B. Physics-Aware Edge-Channel Construction: These quantities encode complementary conditions: flow intensity, capacity usage, electrical coupling, and overload-related stress.
  • B. Physics-Aware Edge-Channel Construction: Scalar channels are median-scaled and clipped to reduce scale differences and limit extreme values before fingerprint extraction.

C. Channel-Wise Random Walk Fingerprints

Channel-wise RWF constructs propagation summaries separately for each physics-aware weighted channel, then concatenates them into a graph-level fingerprint that can distinguish identical topologies with different physical edge states.

  • Channel construction: Each channel produces a symmetrically normalised walk matrix from non-negative weighted edges, with zero-degree entries set to zero.Signed or directional quantities are converted to non-negative magnitudes, and channel weights are assigned symmetrically.
  • Physical interpretation: Channel-specific walks encode distinct physical propagation patterns, such as highly loaded paths for FI and stressed or overloaded lines for OS.The walk length τ controls the number of propagation steps summarised for each channel.
  • Fingerprint extraction: Nodes are partitioned into k structural groups using channel-specific degree-based orderings before within-group and between-group walk summaries are extracted.The resulting summaries are collected across groups and walk lengths.
  • Fingerprint assembly: Concatenating channel fingerprints yields a compact representation that distinguishes graphs sharing connectivity but differing in physical edge states.This extends topology-only RWF with edge-state-sensitive propagation information.

D. MC-PA-RWF+ Node-Edge Extension

MC-PA-RWF+ augments selected physics-aware edge-channel fingerprints with one node-feature RWF block, combining node-level operating information with edge-state propagation.

  • Node-edge extension: MC-PA-RWF excludes node-feature interactions from its channel-wise extractor, while MC-PA-RWF+ appends an RWF-D-feature block.The extension adds node-level operating information without changing the physics-aware edge-channel extraction itself.
  • Channel selection: MC-PA-RWF+ uses the validation-selected channel subset C+ = {FI, CM, OS}.
  • Feature composition: The node-feature block is computed once, while selected weighted edge-channel blocks contribute structural summaries from their respective propagation matrices.This avoids duplicating node-feature interactions across channels.
  • Classification: Both variants produce fixed-length graph-level vectors, after which an SVM performs supervised classification.Feature extraction is therefore separated from the final classifier.

E. Complexity Analysis

The proposed fingerprints retain linear scaling in the number of graph instances, with overhead governed by the fixed number of physical channels and the underlying RWF computation.

  • Complexity: MC-PA-RWF extraction has complexity O(NCτcmn), reflecting independent structural RWF computation across C weighted channels.Weighted-adjacency construction and channel-wise partitioning are lower-order costs under the stated assumptions.
  • Scaling: Both proposed variants remain linear in N, while graph-size dependence is inherited from RWF and channel overhead is controlled by a small fixed channel count.
  • Algorithm: MC-PA-RWF uses all physical channels, whereas MC-PA-RWF+ combines one node-feature block with selected edge-channel fingerprints.Algorithm 1 describes both variants as extracting structural RWF fingerprints from physics-aware edge-weighted channels.
  • Pipeline: The extraction pipeline constructs physical channel adjacencies, partitions nodes using channel-weighted degrees, and extracts structural RWF summaries.

V. EXPERIMENTAL SETUP

The experiments assess graph-level cascading-failure classification on PowerGraph systems of increasing dataset size, comparing physics-aware fingerprints with RWF and supervised GNN baselines.

  • Evaluation scope: The evaluation targets graph-level cascading-failure classification on PowerGraph benchmark systems under increasing dataset sizes.
  • Metrics: Balanced accuracy is the primary metric, while failure-class F1 measures identification of failure-prone operating scenarios.

A. Dataset and Task

The study evaluates binary graph-level cascading-failure classification on PowerGraph operating scenarios, comparing physics-aware RWF variants with topology-, node-feature-, and neural graph baselines under balanced-accuracy evaluation.

  • Task definition: Each graph represents a power-grid operating scenario with a triggering outage, labelled stable when DNS_i = 0 and failure-prone when DNS_i > 0.The binary labels are y_i = 0 for Stable/Class 0 and y_i = 1 for Failure-prone/Class 1.
  • Proposed representations: MC-PA-RWF constructs physical edge-weighted channels from topology and edge attributes, while MC-PA-RWF+ additionally appends node-feature evidence.The channels encode flow intensity, capacity margin, coupling strength, and overload severity; node attributes are excluded from the edge-channel extractor itself.
  • Baseline methods: The comparison includes topology-only RWF-D, node-feature RWF-D-feature, two physics-aware multi-channel variants, four single-channel diagnostics, and GCN, GAT, GINE, and TransformerConv.The single-channel variants isolate flow intensity, capacity margin, coupling strength, and overload severity.
  • Evaluation: Balanced accuracy is the primary metric because stable and failure-prone classes are imbalanced, with failure-class F1 additionally reported at the largest dataset sizes.Results are reported as means and standard deviations across repeated random seeds.
  • Evaluation: Preprocessing and model selection use training and validation data only, with shared splits and seeds across methods and paired t-tests at α = 0.05.RWF fingerprints are classified with SVMs, while GNNs use validation-based early stopping.

VI. RESULTS AND DISCUSSION

Across IEEE24, IEEE39, and UK benchmarks, physics-aware edge channels substantially improve cascading-failure classification over topology-only RWF, while multi-channel and node-edge representations remain competitive with GNNs. The strongest gains are especially evident for failure-prone-class detection and for the UK system, where topology-only and node-feature RWF remain near chance.

  • RQ3: Comparison with GNNs: MC-PA-RWF+ is competitive with strong GNN baselines in balanced accuracy and significantly improves failure-class F1 on all three systems at the largest evaluated sizes.The reported significance criterion is a paired two-sided t-test at the 0.05 level.
  • RQ1: Physics-aware classification: Topology-only RWF performs poorly, reaching 67.04% balanced accuracy on IEEE24, 71.96% on IEEE39, and 50.77% on UK at their largest evaluated sizes.The UK result remains close to the 50% balanced-accuracy baseline.
  • RQ1: Physics-aware classification: At the largest evaluated sizes, MC-PA-RWF reaches 99.15% on IEEE24, 97.15% on IEEE39, and 99.14% on UK, while MC-PA-RWF+ reaches 99.21%, 98.04%, and 99.32%.The node-edge extension is particularly strong on the UK benchmark compared with the original RWF variants.
  • RQ2: Multi-channel robustness: On IEEE24 at 21.5k graphs, PA-RWF-FI reaches 98.77% balanced accuracy, PA-RWF-CM 98.95%, PA-RWF-OS 98.60%, and PA-RWF-CS 67.62%.The results indicate that physical channels contribute differently to cascading-failure classification.
  • RQ2: Multi-channel robustness: MC-PA-RWF+ reaches 99.00% at 15k and 99.21% at 21.5k IEEE24 graphs, improving over PA-RWF-CM by 0.26 percentage points at 21.5k.MC-PA-RWF is highest at 3k, 5k, and 10k graphs, whereas MC-PA-RWF+ becomes strongest at the two largest sizes.
  • RQ2: Multi-channel robustness: Combining complementary physical channels improves representation robustness, while adding node features provides additional benefit when node states and line-level propagation patterns are informative.The study includes channel-level analysis to identify which transmission-line operating measurements contribute most strongly.

C. RQ3: How Do the Proposed Methods Compare with GNN Baselines?

MC-PA-RWF variants are competitive with strong GNN baselines across three power-system benchmarks, while achieving stronger failure-class detection at the largest evaluated settings. Their representations also preserve scalability and interpretability through physics-aware edge-state modelling.

  • Balanced-accuracy comparison: 99.21% balanced accuracy: MC-PA-RWF+ exceeds TransformerConv by 0.45 percentage points on IEEE24 at the largest setting.TransformerConv reaches 98.76% balanced accuracy.
  • Balanced-accuracy comparison: 98.04% balanced accuracy: MC-PA-RWF+ exceeds TransformerConv by 0.28 percentage points on IEEE39 at 28k graphs.TransformerConv reaches 97.76%.
  • Balanced-accuracy comparison: 99.32% balanced accuracy: MC-PA-RWF+ remains close to TransformerConv’s 99.63% on the UK benchmark at 64k graphs, without a statistically significant difference.MC-PA-RWF+ is statistically comparable to TransformerConv at this setting.
  • Failure-class detection: Failure-class F1 improves by 1.60–5.84 percentage points over the strongest GNN baseline across all three systems, with statistically significant gains.The gains are 1.60 points on IEEE24, 5.84 on IEEE39, and 2.10 on the UK benchmark.
  • Interpretability and scalability: MC-PA-RWF offers a scalable and transparent alternative to latent graph representations while preserving linear complexity with respect to the number of graph instances.Channel-level analysis indicates that dynamic edge attributes are more discriminative than static interaction properties alone.
Loading 2609.04943v1…