Source-linked AI summary
Dynamic Graph Convolutional Networks
Franco Manessi, Alessandro Rozza, Mario Manzo
TL;DR
The paper targets classification of structured data represented as graphs that change over time, a setting the authors identify as insufficiently addressed by neural architectures. It proposes combining GCNs and LSTMs, and reports promising results, including superiority over baselines in several evaluated tasks.
Problem
Existing neural graph models do not manage dynamic graphs, while dynamic graphs require handling changing vertices or edges and temporal information.
Method
The paper proposes two approaches combining modified GCN layers with modified LSTMs for sequences of graphs and vertex features.
Results
The approaches outperform considered baselines for semi-supervised sequence-of-vertices classification, while CD-GCN outperforms them for supervised sequence-of-graphs classification.
Takeaways & Limitations
The results support jointly using graph convolutional features and recurrent temporal modeling for the paper’s vertex- and graph-focused sequence-classification tasks.
Takeaways & Limitations
GCNs lack dynamic vertex-feature and edge-connection handling, while LSTMs lack explicit graph-structured information.
Abstract
from arXiv · showhide
Many different classification tasks need to manage structured data, which are usually modeled as graphs. Moreover, these graphs can be dynamic, meaning that the vertices/edges of each graph may change during time. Our goal is to jointly exploit structured data and temporal information through the use of a neural network model. To the best of our knowledge, this task has not been addressed using these kind of architectures. For this reason, we propose two novel approaches, which combine Long Short-Term Memory networks and Graph Convolutional Networks to learn long short-term dependencies together with graph structure. The quality of our methods is confirmed by the promising results achieved.
1 Introduction
The paper addresses classification on structured data whose graph nodes and edges can change over time. It proposes combining GCNs for graph structure with LSTMs for temporal dependencies, extending the approaches to vertex- and graph-focused applications.
- Graphs represent structured datasets as nodes connected by weighted edges that encode local and spatial relationships.
- Existing classification studies mainly focus on static graphs, although real-world graphs may change nodes and edges over time.
- Few neural network models directly encode graph structure, and none known to the authors manage dynamic graphs.
- The proposed approaches combine GCNs, which manage structured data, with LSTMs, which capture temporal information and long short-term dependencies.
- The methods address vertex-focused classification and are extended to graph-focused applications.
- GCNs distribute supervised-loss gradients across labeled and unlabeled nodes to learn graph-based representations.
2 Related Work
Related work includes feature-based, label-propagation, network-embedding, graph-neural-network, and dynamic-network methods. However, existing neural graph architectures do not properly handle temporal information, while many established techniques cannot manage graphs that change over time.
- Traditional structured-data methods identify structural features for conventional learners or propagate labels for direct classification.
- DeepWalk learns vertex representations from truncated random walks, encoding graph relations in a vector space for statistical models.
- Dynamic-network methods model changing graphs through latent features, temporal support-vector data, or node, correlation, and dynamic factors.
- Graph neural network research generalizes neural networks to structured graphs and maps graphs and nodes into Euclidean representations for classification or regression.
- These neural network architectures are not able to properly deal with temporal information.
3 Our Approaches
The paper introduces dynamic graph-convolutional architectures that combine graph processing with recurrent temporal modeling for vertex- and graph-focused sequence classification.
- Architecture rationale: GCNs process graph-structured information but do not handle changing vertex features or edge connections, while LSTMs model long short-term dependencies without explicitly exploiting graph structure.These complementary limitations motivate their integration.
- Architecture rationale: The proposed architectures combine extended Graph Convolution layers with modified LSTMs to learn from graph structure and vertex features over ordered graph sequences.The approach targets dynamic settings in which graph structure and features evolve over time.
- Dynamic graph-convolution layers: The Waterfall Dynamic-GC layer applies graph convolution at each sequence step with trainable parameters shared across steps.Its output is a sequence of new vertex representations.
- Dynamic graph-convolution layers: The Concatenate Dynamic-GC layer concatenates each graph-convolved feature representation with its corresponding input vertex features, also sharing weights across sequence steps.The resulting representation preserves both graph-convoluted and plain vertex features.
- Input representation: For graph sequences sharing the same vertex set, each time step is represented by an adjacency matrix and a vertex-feature matrix, and the models accept ordered sequences of these matrices.The framework also reduces to static vertex- or graph-focused applications when the sequence length is one.
- Task-specific architectures: The vertex LSTM processes graph-convolutional features in parallel across vertices using shared training weights, after which task-specific fully connected layers produce vertex- or graph-level predictions.The vertex-focused task predicts class probabilities for vertices, whereas the graph-focused task aggregates vertex-based predictions into sequence-level outputs.
4 Experimental Results
Experiments evaluate the proposed architectures on vertex-focused DBLP sequences and graph-focused CAD-120 sequences against neural-network baselines. The results show strong performance, robustness to labeling ratio, and lower parameter counts than the largest baseline.
- Datasets: The experiments evaluate vertex-focused classification on DBLP and graph-focused classification on CAD-120 using temporal graph data.DBLP contains yearly co-author graphs; CAD-120 contains frame-level graphs built from skeleton joints and objects.
- Experimental setup: The proposed WD-GCN and CD-GCN are compared with GCN, fully connected, LSTM+FC, and FC+LSTM+FC baselines using Accuracy and Unweighted F1 Measure.The architectures are evaluated with shared Monte Carlo cross-validation splits and tuned hyperparameters.
- DBLP results: Both proposed architectures outperform the considered baselines for semi-supervised classification of the DBLP vertex sequences.Wilcoxon testing against all baselines yields p-value < 0.6% for both employed scores.
- DBLP results: 872.206 and 163.406 parameters are used by the best WD-GCN and CD-GCN, respectively, versus 1.314.006 for the largest FC+LSTM+FC network.The proposed models therefore achieve their reported performance with fewer parameters than the largest tested network.
- DBLP results: WD-GCN and CD-GCN show little sensitivity to the labeling ratio and have roughly equivalent Accuracy and Unweighted F1 Measure performance.The labeling-ratio experiment averages results over 10 Monte Carlo cross-validation iterations.
- CAD-120 results: CD-GCN is the only proposed architecture to outperform all baselines on CAD-120, while WD-GCN performs similarly to the baselines.The authors associate CD-GCN’s advantage with augmenting vertex features using graph-convolutional features when the sequence contains few vertices.
5 Conclusions and Future Works
The paper introduces two neural-network approaches for dynamic vertex and graph sequence classification, combining modified graph-convolutional and LSTM components. Experiments report task-dependent superiority, while future work should clarify small-graph performance differences and explore broader architectural variants.
- Contributions: The two approaches address semi-supervised classification of vertex sequences and supervised classification of graph sequences.They are based on modified graph-convolutional layers connected with a modified LSTM.
- Experimental findings: Both approaches outperform the considered baselines for semi-supervised classification of vertex sequences, while CD-GCN is superior for supervised classification of graph sequences.The performances were assessed on two datasets against baselines.
- Limitations and future work: Differences between WD-GCN and CD-GCN for small graphs may stem from CD-GCN's feature augmentation approach, a conjecture left for future work.The paper presents this explanation as a hypothesis rather than an established finding.
- Limitations and future work: Future extensions include replacing LSTM with alternative recurrent units, extending the graph-convolutional unit, and evaluating deeper combined architectures.These directions are proposed as interesting extensions of the current work.