Student Research Abstract: Using Local Activity Encoding for Dynamic Graph Pooling in Stuctural-Dynamic Graphs
S. Beddar-Wiesing. ACM/SIGAPP Symposium on Applied Computing (SAC), page 604--609. ACM, (2022)
Abstract
Graphs have recently become more popular for modeling real-world
as well as theoretical problems, and several Machine Learning algorithms
for learning on them have developed. For graphs that change
over time, however, research is still at an early stage. This article proposes
a framework DynHeatmaP that generates a constant-size
graph sequence representation of graphs whose structure changes
over time (structural-dynamic, SDG) in linear time. The framework
uses a representation of additions and deletions of nodes and edges
(events) to perform dynamic graph pooling. Our algorithm translates
the dynamic changes of the nodes and edges to a heatmap
representation of the current node activity, regarding additions and
deletions in the neighborhood, respectively. The created activity
heatmap is utilized as probabilities of the nodes to be sampled in the
subsequent pooling step. In addition, the neighborhood of selected
nodes has been sampled such that the ratio of additions and deletions
is represented accordingly. The obtained downsampled graph
sequence can then be used representatively as input to a GNN for
learning on the original stream. Focussing on the active regions
in a graph, the fast pooling process can reduce the training time
significantly and addresses the problem of unbalanced datasets in
real-world applications modeled as sparse graphs.