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.

    Source: §I · p. 1, C. Motivation for Physics-Aware Edge… · p. 4, A. RQ1: Do Physics-Aware RWF Improve… · p. 8

  • 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.

    Source: §I · p. 2, A. Dataset and Task · p. 6

  • 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.

    Source: §VI · p. 8, §VII · p. 10

  • 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.

    Source: §VII · p. 10

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.Source: §I · p. 1
  • 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.Source: §I · p. 1
  • Standard RWF offers scalable, interpretable graph-level vectors but is primarily topology-driven and does not let edge attributes direct walk dynamics.Source: §I · p. 1
  • 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.Source: §I · p. 2
  • Experiments on IEEE24, IEEE39, and UK PowerGraph systems improve over topology-only RWF, remain competitive with GNN baselines, and improve failure-class detection.Source: §I · p. 2

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.

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.

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.Source: A. Problem Formulation and Overview · p. 4
  • MC-PA-RWF transforms edge attributes into weighted adjacency matrices, extracts one structural RWF fingerprint per channel, and concatenates the results.Source: A. Problem Formulation and Overview · p. 4
  • Each channel represents a distinct physical interaction pattern over the same graph support, so the final representation contains multiple edge-state-dependent propagation views.Source: A. Problem Formulation and Overview · p. 4

B. Physics-Aware Edge-Channel Construction

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.Source: C. Channel-Wise Random Walk Fingerprints · p. 5

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.Source: C. Channel-Wise Random Walk Fingerprints · p. 5

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.Source: C. Channel-Wise Random Walk Fingerprints · p. 5

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.Source: C. Channel-Wise Random Walk Fingerprints · p. 5

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.Source: D. MC-PA-RWF+ Node-Edge Extension · p. 5

Channel selection

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.Source: D. MC-PA-RWF+ Node-Edge Extension · p. 5

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.Source: D. MC-PA-RWF+ Node-Edge Extension · p. 5

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.Source: E. Complexity Analysis · p. 5

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.Source: E. Complexity Analysis · p. 5

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.Source: F. Algorithm · pp. 5–6

Pipeline

  • The extraction pipeline constructs physical channel adjacencies, partitions nodes using channel-weighted degrees, and extracts structural RWF summaries.Source: F. Algorithm · p. 6

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.Source: §V · p. 6

Metrics

  • Balanced accuracy is the primary metric, while failure-class F1 measures identification of failure-prone operating scenarios.Source: §V · p. 6

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.Source: A. Dataset and Task · p. 6

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.Source: A. Dataset and Task · p. 6, B. Benchmark Methods · p. 7

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.Source: B. Benchmark Methods · pp. 6–7

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.Source: C. Evaluation Metrics and Implementation · p. 7
  • 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.Source: C. Evaluation Metrics and Implementation · p. 7

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.Source: §VI · p. 8, B. RQ2: Does Multi-Channel Fusion… · p. 9

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.Source: A. RQ1: Do Physics-Aware RWF Improve… · p. 8
  • 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.Source: A. RQ1: Do Physics-Aware RWF Improve… · p. 8

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.Source: B. RQ2: Does Multi-Channel Fusion… · p. 9
  • 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.Source: B. RQ2: Does Multi-Channel Fusion… · p. 9
  • 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.Source: B. RQ2: Does Multi-Channel Fusion… · p. 9

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.Source: C. RQ3: How Do the Proposed Methods… · p. 9
  • 98.04% balanced accuracy: MC-PA-RWF+ exceeds TransformerConv by 0.28 percentage points on IEEE39 at 28k graphs.TransformerConv reaches 97.76%.Source: C. RQ3: How Do the Proposed Methods… · p. 9
  • 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.Source: C. RQ3: How Do the Proposed Methods… · p. 9

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.Source: 1) Failure-Class (F1) Detection · p. 10, §VII · p. 10

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.Source: §VII · p. 10

Related papers

Loading 2609.04943v1…