AAAI2020.EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs

[soroush-ziaeinejad]

Main problem:

The main problem of the paper is the ability to train graph convolutional networks (GCNs) on dynamic graphs, which are graphs that change over time.

Applications:

The proposed method can be applied to various tasks such as dynamic graph prediction, node classification, and link prediction on dynamic graphs.

Existing Work:

The authors mention that existing works on dynamic graph analysis have primarily focused on static graphs and methods that can't capture the temporal dynamics of the graph. The proposed method aims to overcome these limitations. WILL BE COMPLETED

Method:

The proposed method, called EvolveGCN, is based on the idea of developing GCNs. A GCN is trained on a sequence of snapshots of the dynamic graph, and the parameters of the GCN are updated at each time step using a technique called evolutionary graph convolution. WILL BE COMPLETED

Input and output:

The input is a sequence of snapshots of the dynamic graph, and the output is a prediction for the future graph state.

Experimental Setup:

• Dataset:

  1. Stochastic Block Model (SBM): Random graph generating
  2. Bitcoin OTC
  3. Bitcoin Alpha
  4. UC Irvine messages
  5. Autonomous systems
  6. Reddit Hyperlink Network
  7. Elliptic

• Baselines:

  1. GCN: Static GCN
  2. GCN-GRU: a single GCN model co-trained with GRU
  3. DynGEM: unsupervised node embedding approach (using AE to maintain the past node information)
  4. dyngraph2vec: unsupervised node embedding approach (using AE and RNN to maintain the past node information) (DynmicGEM)

• Metrics:

  1. MAP
  2. MRR

Results:

• Results for Link Prediction: Best method in terms of MAP and MRR for datasets:

  1. SBM: EvolveGCN
  2. BC-OTC: DynAERNN
  3. BC-Alpha: DynAERNN
  4. UCI: EvolveGCN
  5. AS: EvolveGCN

• Results for Edge Classification: Best method in terms of F1 for datasets:

  1. BC-OTC: EvolveGCN
  2. BC-Alpha: EvolveGCN
  3. Reddit: EvolveGCN
  4. Elliptic: GCN-GRU

• Results for Node Classification: GCN-GRU beats EvolveGCN on this task. However, EvolveGCN performs better than static GCN.

[hosseinfani]

@soroush-ziaeinejad you can motivate your work by saying that no study investigate the effect on community prediction task and you want to do this. :)