Predicting Path Failure In Time-Evolving Graphs

1 INTRODUCTION

• The paper focuses on predicting a path's near-future status in evolving graphs, with applications such as forecasting network failures or traffic congestion so preventive measures can be taken promptly.Earlier time-evolving graph studies cited here focus on node classification.Source: §1 · p. 1
• The task combines node time-series observations with evolving graph structure, whose temporal behavior can be non-stationary and abruptly affected by structural changes.Examples include rush-hour seasonality and traffic redirected after a road closure.Source: §1 · p. 1
• LRGCN models within-snapshot node correlations as intra-time relations and dependencies between adjacent snapshots as inter-time relations, jointly capturing temporal dependency and graph dynamics.The model uses relational GCN to process both relation types.Source: §1 · p. 2
• SAPE embeds arbitrary-length paths as fixed-length vectors and uses self-attention to highlight important path nodes, supporting interpretability and downstream path-failure diagnosis.The paper also reports that SAPE improves classification performance and provides interpretable path embeddings and node importance.Source: §1 · p. 2
• Macro-F1 was 61.89% on the telecommunication network and 86.74% on the California traffic network, outperforming competing methods by at least 5% and 4%, respectively.These results are reported for LRGCN-SAPE path-failure and path-congestion prediction.Source: §1 · p. 2

2 PROBLEM DEFINITION

• The formulation focuses on directed graphs, although the authors state that their methodology also applies to undirected graphs.Source: §2 · p. 2
• A time-evolving graph is a sequence of snapshots, each defined by its adjacency matrix and node observations; edges may become unavailable or newly available over time.The paper gives link failures and road congestion or closure as examples of changing edges.Source: §2 · p. 2
• A path is represented as an ordered sequence of nodes, and node observations are recorded as signals over time.The paper describes each node's signals as a vector of values.Source: §2 · p. 2
• A path's availability is service-dependent, not simply physical connectivity; in a telecommunication network, it can depend on whether packet latency is below a predefined threshold.The task predicts availability from the past M time steps for the next F time steps.Source: §2 · p. 2
• The prediction input includes observations of the path's nodes, and the target is the path's availability in the next F time steps based on the past M time steps.The task is formulated as classification with a cross-entropy training objective.Source: §2 · p. 2
• In the example, path ⟨a,b,c,d⟩ remains available in the observed past despite ⟨b,d⟩ becoming unavailable, and its future availability is the prediction target.The nodes represent switches in the telecommunication network.Source: Figure 1 · p. 2, §2 · p. 3

3.1 Framework

• The framework uses two LRGCN layers for node representations, then SAPE and a fully connected layer to calculate path-classification loss.The first LRGCN layer encodes the time-evolving graph and initializes the second; the final-time-step outputs supply node representations.Source: §3.1 · p. 3, Figure 2 · p. 4, §3.2.3 · p. 5

3.2 Time-Evolving Graph Modeling

• The time-evolving graph model generalizes graph convolution to process node time series together with changing graph structure.It models within-snapshot node correlation and temporal dependency between adjacent snapshots.Source: §3.2 · p. 3, §3.2.1 · p. 3

3.2.1 Static graph modeling.

• For a static directed snapshot, R-GCN models node correlation using incoming and outgoing relations with asymmetric normalization.Stacking R-GCN layers provides multi-hop normalization.Source: §3.2.1 · pp. 3–4

3.2.2 Adjacent graph snapshots modeling.

• For adjacent snapshots, the model represents same-time node correlation and directed, asymmetric dependencies from the previous time step as four relation types.The types are intra-incoming, intra-outgoing, inter-incoming, and inter-outgoing; the inter-time dependency uses the Markov property.Source: §3.2.1 · p. 3, §3.2.2 · p. 4, Figure 3 · p. 4

3.2.3 The proposed LRGCN model.

• LRGCN uses gated memory with graph convolution to jointly capture long-term temporal dependency and graph-structure dynamics.Its gates select inputs to update the memory cell and retain or forget its prior state.Source: §3.2.3 · p. 5

3.3 Self-Attentive Path Embedding

• SAPE applies an LSTM to path-node representations, then self-attention to learn node importance and produce a fixed-length path embedding.The embedding is size-invariant, addressing arbitrary path lengths.Source: §3.3 · p. 5

4 EXPERIMENTS

• The experiments evaluate path failure prediction in a telecommunications network and path congestion prediction in a California traffic network.Source: §4 · p. 6

4.1.1 Telecommunication network (Telecom).

• The telecom dataset covers 626 switches over three months, with 15-minute observations and a 24-hour history used to predict failures in the next 24 hours.A path instance is labeled as failure when alarms are triggered within the next 96 time steps.Source: §4.1.1 · p. 6

4.1.2 Traffic network (Traffic).

• The traffic dataset covers 4,438 District 7 sensor stations over three months, recording hourly average speed and occupancy as graph structure changes with node status.The graph has 2,160 hourly time steps.Source: §4.1.2 · p. 6
• Traffic evaluation samples 200 Dijkstra shortest paths, splits 1460×200/200×200/500×200 instances, and predicts next-hour congestion from 24-hour histories.A path instance is labeled congested if two consecutive stations are labeled congested within the next time step.Source: §4.1.2 · p. 6

• Baselines span DTW path similarity, temporal-only FC-LSTM, static-graph DCRNN and STGCN, and LRGCN variants that compare path representations and evolving versus static graphs.Source: §4.2 · p. 6
• For fair comparison, DCRNN, STGCN, and LRGCN use the same static graph and LSTM path representation.Source: §4.2 · pp. 6–7
• Each method is run three times, reporting average Precision, Recall, and Macro-F1; Precision and Recall are computed for the positive class, while Macro-F1 averages both classes' F1 scores.Source: §4.2 · p. 7

4.3.1 Classification performance.

• LRGCN beats DCRNN and STGCN by at least 1% in Macro-F1 on both datasets; LRGCN-SAPE (static) also beats Group 3 methods by at least 1%.The comparisons distinguish graph-evolution modeling from the path-representation contribution.Source: §4.3.1 · p. 7

4.3.2 Training efficiency.

• LRGCN-based methods converge faster than other methods, and after three epochs LRGCN-SAPE (evolving) has the lowest validation loss.Figure 6 presents the learning curves.Source: Figure 6 · p. 7, §4.3.2 · p. 7

4.3.1 Classification performance.

• LRGCN-SAPE (evolving) performs best overall; relative to LRGCN-SAPE (static), it raises Macro-F1 by 1.34% on Telecom and 1.90% on Traffic.These are the reported gains on the two datasets.Source: Table 2 · p. 7, §4.3.1 · p. 7, Table 3 · p. 8

4.3.3 Benefits of graph evolution modeling.

• For a path affected by a closed station, evolving SAPE gives more attention to a nearby station affected subsequently, while static SAPE emphasizes a distant node.Figure 7 encodes attention by node radius; its map colors indicate traffic intensity and a star marks the closed station.Source: §4.3.3 · p. 7, Figure 7 · p. 8

4.3.4 Effect of the number of views.

• Figure 8 evaluates the effect of SAPE’s number of views on Traffic.Source: Figure 8 · p. 8

4.3.5 Path embedding visualization.

• Among 1,000 Traffic test paths, t-SNE embeddings place paths with the same label near one another geometrically.Figure 9 shows the two-dimensional embedding visualization, with color indicating path label.Source: Figure 9 · p. 8, §4.3.5 · p. 8

4.3.6 Effect of the normalization methods.

• Asymmetric normalization outperforms symmetric normalization in Precision and Macro-F1 on both datasets, with a larger advantage on Telecom.The authors relate the difference in advantage to the networks’ differing link directions.Source: Table 4 · p. 8, §4.3.6 · p. 8

Failure prediction and traffic forecasting

• Prior failure-prediction work uses sequential pattern matching, SVM classification, or Bayesian networks with ARIMA; traffic methods include statistical models and deep learning [23].Source: §5 · p. 9

Path representation

• Deepcas uses bidirectional GRU [11] and Prox-Embed uses LSTM with max pooling; SAPE instead uses self-attention to encode node importance in a unified path representation [12] [14].The passage notes that long paths can challenge RNNs through exploding or vanishing gradients.Source: §5 · p. 9

Neural networks on graphs

• DCRNN [13] and STGCN [22] model spatial and temporal dependencies on static graphs, whereas LRGCN targets graphs whose structure changes over time.Source: §5 · p. 9

Conclusion

• LRGCN jointly models within-snapshot node correlations and temporal dependencies between adjacent snapshots as intra-time and inter-time relations.Source: §6 · p. 9
• SAPE is proposed to provide interpretation and improve performance through a new path representation method.Source: §6 · p. 9
• On a real-world telecommunication network and a California traffic network, LRGCN-SAPE outperforms competitors in path failure prediction and produces meaningful path representations.Source: §6 · p. 9

A.1 Telecommunication network

• The metropolitan transmission network contains 626 switches and records sensor data from February 1 to April 30, 2018.Switches are linked by directed optical-fiber edges.Source: §A.1 · p. 10
• Each switch records observations every 15 minutes; average sending and receiving power form an 8449 × 626 × 2 feature matrix.Features are normalized to the range [0, 1].Source: §A.1 · p. 10
• For 853 paths, an alarm detector labels failure when warning messages exceed an hourly threshold; 24 hours of history predict failure in the next 24 hours.Source: §A.1 · p. 10
• Optical-link failure or availability, determined using bit error rate, is used to construct the time-evolving graph.Source: §A.1 · p. 10

A.2 Traffic network

• The study uses CalTrans PeMS District 7 data from June 1 to August 30, 2018, covering 4,438 stations with hourly speed and occupancy features.The resulting feature matrix has dimensions 2160 × 4438 × 2; missing feature values are replaced with 0 and values normalized to [0, 1].Source: §A.2 · p. 10
• The static graph connects adjacent stations on the same freeway and direction in Absolute Postmile order, with every edge weighted 1.Each station is a node.Source: §A.2 · p. 10
• For each of 200 sampled shortest paths of length 2–50, congestion is labeled when two consecutive nodes are congested simultaneously; 24 hours of history predict congestion in the next hour.Source and target nodes are randomly selected, and Dijkstra’s algorithm finds the shortest path; the labels form a 2160 × 200 matrix.Source: §A.2 · p. 10
• At each time step, a closure removes a station’s incoming and outgoing edges, while congestion halves their weights.These rules construct the time-evolving graph snapshots.Source: §A.2 · p. 10

B DETAILED EXPERIMENT SETTINGS

• DTW compares paths as bags of nodes using maximum node similarity, but does not model node correlations or graph structure.For multivariate node time series, it sums squared DTW similarities across variables.Source: B DETAILED EXPERIMENT SETTINGS · p. 10
• FC-LSTM uses two temporal LSTM layers and an LSTM path-representation layer, whereas DCRNN models node correlation through diffusion.Both approaches use an LSTM path representation and fully connected output; DCRNN’s maximum diffusion step is 3, and its DCRNN and LSTM output dimensions are 8.Source: B DETAILED EXPERIMENT SETTINGS · pp. 10–11
• STGCN models node correlation and temporal dependency with two convolution layers and an intervening GCN layer, using temporal kernel size 3 and graph kernel size 1.Its graph-model and LSTM output dimensions are both 8.Source: B DETAILED EXPERIMENT SETTINGS · p. 11
• LRGCN replaces DCRNN’s graph model and uses hidden dimension 96; its SAPE variants use fixed settings, with the evolving variant modeling graph-structure dynamics.The static variant replaces LSTM path representation with SAPE; both SAPE variants set v = 8, ds = 32, and r = 8.Source: B DETAILED EXPERIMENT SETTINGS · p. 11