Graph Edit Networks

Benjamin Paassen, Daniele Grattarola, Daniele Zambon, Cesare Alippi, Barbara Hammer

Predicting how a graph changes over time is a fundamental challenge in machine learning. Whether it’s an epidemic spreading through a population, a social network evolving, or a piece of code being refactored, the underlying structure isn't just shifting its connections—nodes are appearing and disappearing, too.

In their ICLR 2021 paper, "Graph Edit Networks," Benjamin Paassen and colleagues introduce a novel way to handle this "graph-to-graph" learning problem by moving away from dense matrix predictions and toward sparse, interpretable graph edits.

The Problem with Existing Methods

Most Graph Neural Networks (GNNs) are designed for "graph-in, scalar-out" tasks like classification or regression. When it comes to "graph-in, graph-out" tasks, the field hits a wall.

Existing methods usually fall into two camps:

  1. Link Prediction: These assume a fixed set of nodes and only predict which edges appear or vanish. They cannot handle a network where new members join or old ones leave.
  2. Graph Generators: These often build graphs from scratch (node by node). While powerful, they are computationally expensive and fail to exploit the fact that a graph at time $t+1$ is usually very similar to the graph at time $t$.

The authors identify a critical gap in time-series prediction on graphs: we lack a natural interface to describe general topological changes—including changes to the node set—in a way that is sparse, local, and efficient.

Methodology: The Graph Edit Network

Graph Edit Networks (GENs) treat graph evolution as a sequence of discrete "edits" (insert, delete, relabel) rather than a change in a dense adjacency matrix. The core innovation is the GEN layer, which takes node embeddings from a standard GNN and produces numerical "edit scores."

The Graph Edit Network Pipeline

The Pipeline

  1. Embedding: A standard GNN (like a GCN or GAT) computes a vector for every node in the current graph $G_t$.
  2. Scoring: The GEN layer uses these embeddings to score potential actions: Should this node be deleted? Should a new node be inserted next to it? Should this edge be removed?
  3. Translation: An algorithm converts these scores into an edit script—a sequence of operations like del(node_i) or ins(node_new).
  4. Application: The script is applied to $G_t$ to produce the predicted $G_{t+1}$.

Training such a network is tricky because we don't always know the "ground truth" sequence of edits. The authors prove that you only need a mapping between the nodes of two graphs to construct a valid training signal. By using Graph Edit Distance (GED) approximators, they can generate these mappings automatically, allowing the network to learn the shortest path of changes between two states.

Experiments and Key Results

The authors evaluated GEN on a mix of synthetic and real-world dynamical systems, including graph dynamics (Edit Cycles, Degree Rules, Conway’s Game of Life), tree dynamics (Boolean Formula simplification), and real-world scaling datasets (HEP-Th citation network).

Performance on Edit Cycles
  • Superior Accuracy: On tasks involving node changes, GEN achieved 100% precision and recall for node insertions and deletions. Baselines like Variational Graph Autoencoders (VGAE) failed significantly on these tasks because they aren't designed to change the node set.
  • Sparsity is Efficiency: By predicting edits instead of the whole adjacency matrix, complexity drops from quadratic ($O(N^2)$) to roughly linear ($O(N)$). On the HEP-Th dataset, using an "edge filtering" trick allowed the GEN's backward pass to scale with an exponent of 0.93 (effectively linear), making it viable for graphs with thousands of nodes.
  • Interpretability and Locality: Edits are local and transparent. If a model predicts delete(node_7), the reason is much more understandable to a human observer than a shifted value in a dense matrix.

Limitations and Future Work

While powerful, GENs currently rely on a Markovian Assumption, looking only at the current graph ($G_t$) to predict the next ($G_{t+1}$) without a memory of the past. Integrating GENs with recurrent architectures like EvolveGCN could address this. Additionally, the quality of training depends heavily on having a good node mapping; while GED approximators work, they can become a bottleneck for highly complex, non-isomorphic transitions. Finally, because decisions are local, the model might struggle with global rules unless the underlying GNN is deep enough to propagate that global information to every node.

Summary updated

Abstract

While graph neural networks have made impressive progress in classification and regression, few approaches to date perform time series prediction on graphs, and those that do are mostly limited to edge changes. We suggest that graph edits are a more natural interface for graph-to-graph learning. In particular, graph edits are general enough to describe any graph-to-graph change, not only edge changes; they are sparse, making them easier to understand for humans and more efficient computationally; and they are local, avoiding the need for pooling layers in graph neural networks. In this paper, we propose a novel output layer - the graph edit network - which takes node embeddings as input and generates a sequence of graph edits that transform the input graph to the output graph. We prove that a mapping between the node sets of two graphs is sufficient to construct training data for a graph edit network and that an optimal mapping yields edit scripts that are almost as short as the graph edit distance between the graphs. We further provide a proof-of-concept empirical evaluation on several graph dynamical systems, which are difficult to learn for baselines from the literature.
BibTeX
@inproceedings{paassen2021graph,
  author = {Benjamin Paassen and Daniele Grattarola and Daniele Zambon and Cesare Alippi and Barbara Hammer},
  title = {{Graph Edit Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
}

Loading related content...

Figure