EPIC: Graph Augmentation with Edit Path Interpolation via Learnable Cost

1 Introduction

Graph data has become increasingly important in various domains, such as social networks, bioinformatics, and recommendation systems [Hu et al., 2020; Morris et al., 2020; Leskovec et al., 2007]. Despite the increasing importance, the limited size and diversity of existing graph datasets often limit the performance of graph-based models. One way to overcome this limitation is to augment the existing dataset, a technique that has found success in the other domains [Shorten and Khoshgoftaar, 2019; Iwana and Uchida, 2021].

An interpolation between points is a recognized method for data augmentation, yet this approach does not seamlessly translate to graphs, due to the irregular structures inherent to them. Prior solutions have either adopted a continuous relaxation of graph structures into regular domains [Han et al., 2022] or employed transplantation of graph components [Park et al., 2022], thereby circumventing the difficulties associated with graph interpolation.

We propose a novel interpolation method for graphs based on the concept of graph edit distance [Ullmann, 1976]. The graph edit distance, a widely-accepted metric, quantifies graph similarity by determining the minimum number of necessary edit operations, such as insertions, deletions, or substitutions of nodes and edges. From the graph edit distance between two graphs, we construct a graph edit path representing the transformation process from one graph to the other through the edit operations. The intermediate graphs along this path can be seen as an interpolation between two graphs and are used to augment the training set.

However, the conventional edit distance with operation counts may overlook the significance of individual operations, such as those that affect functional groups in molecular graphs [Durant et al., 2002; Zhang et al., 2020]. In response to this, we propose a context-sensitive cost model built through an edit distance learning framework that maximizes the distance between graphs with different labels while minimizing those with the same label. This enables us to learn a cost model that better reflects the underlying graph data characteristics.

By combining the graph edit distance metric with the learned cost model, we present a novel graph dataset augmentation method named Edit Path Interpolation via learnable Cost (EPIC). Through rigorous experimental evaluations on various graph classification tasks, we demonstrate the superiority of our method in comparison to existing techniques. Additional experiments with noisy labels show the robustness of our approach against the others.

2 RelatedWork

2.1 Graph Edit Distance

The graph edit distance is a metric that quantifies the dissimilarity between two graphs [Ullmann, 1976]. It measures the minimum number of edit operations required to transform one graph into another. These edit operations include node and edge insertion, deletion, and substitution. The computational complexity of obtaining graph edit distance is known to NP-complete [Abu-Aisheh et al., 2015]. A number of works addressing the problem of the high computational cost have been proposed. Cross et al. [1997] casts the optimization process into a Bayesian framework with a genetic search algorithm. Myers et al. [2000] adopts the Levenshtein distance to model the probability distribution for structural errors in the graph-matching. In Justice and Hero [2006], a binary linear programming formulation of the graph edit distance for unweighted, undirected graphs is proposed. Fischer et al. [2015] proposes an approximated graph edit distance based on Hausdorff matching. Wang et al. [2021a] adopts the deep learning method to efficiently prune the search tree in computation.

Recently, deep neural network-based graph edit distance learning methods have been proposed. In contrast to the traditional fixed cost distance, these methods learn the cost of individual edit operations. One standard approach to learning costs using neural networks involves obtaining embeddings from node and edge attributes, which are then used to compute the edit distance in a supervised manner [Cort´es et al., 2019]. However, these approaches require ground truth node correspondences provided by an oracle between two graphs, which are inapplicable in various situations. Riba et al. [2021] learns the cost using node features extracted by graph neural networks and optimize the cost by approximating graph edit distance to Hausdorff distance. The Hausdorff distance is an effective method for approximating the graph edit distance in quadratic time, but it is not suitable for edit path construction since it allows one-to-many substitution between nodes.

2.2 Graph Augmentation

Augmentation methods for graph-structured data aim to improve the generalization ability of neural networks by creating diverse training samples. The most commonly used augmentation methods are based on random modifications of original data. For example, DropNode [Feng et al., 2020] and DropEdge [Rong et al., 2019] uniformly drop nodes and edges, respectively. A subgraph sampling [You et al., 2020; Wang et al., 2020] and motif swap [Zhou et al., 2020] perturb the subgraph of the original graph via subgraph matching. FLAG [Kong et al., 2022] adds adversarial perturbation to node features. These methods assign the same labels before and after the perturbation.

To overcome the simplicity of basic approaches, mixupbased augmentation has been proposed. Manifold Mixup [Wang et al., 2021b] interpolates embeddings from the last layer for two graphs and uses it as a graph representation of the augmented graph. SubMix [Yoo et al., 2022] proposes a node split and merge algorithm to perturb original graphs and then mix random subgraphs of multiple graphs. S-Mixup [Ling et al., 2023] uses an alignment matrix from the graph matching network [Li et al., 2019] to mix node features. G-Mixup [Han et al., 2022] mixes graphons [Airoldi et al., 2013] extracted from different classes of graphs. GREA [Liu et al., 2022] proposes a rationalization identification algorithm that extracts a subgraph explaining a property of the graph best and uses the subgraph to curate augmented graphs.

3 EPIC: Edit Path Interpolation via Learnable Cost

In this section, we first describe a graph data augmentation method with a graph edit path. We then propose a method to learn a graph edit distance by learning the cost of individual edit operations.

3.1 Augmentation with Graph Edit Path Construction of Graph Edit Path

We consider a graph G = (V, E) associated with node and edge attributes. The graph edit distance is a metric that quantifies the dissimilarity between two graphs. It measures the minimum number of edit operations required to transform one graph into another or computes the total cost of edit operations if the cost of individual operations varies. These edit operations involve node and edge insertion, deletion, and attribute substitution.

Once the graph edit distance is computed, a graph edit path can be obtained by applying a series of edit operations from a source graph to reach a target graph. It represents the stepby-step transformation from one graph to another while minimizing the edit distance.

The graph edit distance is generally invariant to the order of edit operations. However, there are certain dependencies between node and edge operations. The node deletion operation can only be performed after all the connected edges are deleted. The edge insertion operation can only be performed when the two target nodes are presented.

We only consider the node operations in order to reduce the computational complexity of graph edit distance. Specifically, when a new node is inserted into a graph, we perform edge insertion operations for all edges whose adjacent nodes are given after insertion. When a node is deleted, we perform edge deletion operations for all edges connected to the deleted node. When a node is substituted, we perform edge insertion, deletion, and substitution operations accordingly. The detailed algorithm is provided in Algorithm 1. By doing so, we can construct the graph edit path whose length is equal to the number of node edit operations in the computation of the graph edit distance. Figure 1 illustrates an example of a graph edit path between two graphs and possible augmentation.

Graph Augmentation and Label Assignment

We use the graph edit path to construct an augmented graph. We randomly sample two graphs in the training set. The graph edit distance between the two graphs is computed, then the graph edit path is constructed with node operations in random order. The samples obtained from a graph edit path are used as augmented graphs. To prevent the case where the augmented graph is already presented in the training set, we add an additional node feature indicating whether the graph is from the augmentation set or not.

To assign a label to the augmented graph, we use the cost of edit operations from the augmented graph to the source and the target graphs. Let (o1, ..., on) be a sequence of edit operations applied to transforming source graph GS to target graph GT , and c(o) be the real-valued cost function of operation o, which is precisely defined in Subsection 3.2. With the

Algorithm 1 Applying node operation

Input: A node operation (u → v), source graph GS = (VS, ES), target graph GT = (VT , ET ), and the current

• graph GC = (VC, EC) Output: The updated graph GC+1 = (VC+1, EC+1) 1: GC+1 = copy(GC) 2: if u = ∅ then 3: Insert the node v to VC+1. 4: else if v = ∅ then 5: Delete the node u from VC+1. 6: else 7: Substitute the node u with the node v in VC+1. 8: end if 9: for each edge (u,w) in EC do 10: if node w ∈ VT and edge (v,w) not in ET then 11: Remove the edge (v,w) from EC+1. 12: else if node w ∈ VT and edge (v,w) in ET then 13: Substitute edge attributes of (v,w) in EC+1 with those of (v,w) in ET if needed. 14: end if 15: end for 16: for each edge (v, x) ∈ ET adjacent to node v in VT do 17: if node x ∈ VC and edge (u, x) not in EC then 18: Insert the edge (v, x) to EC+1. 19: end if 20: end for

corresponding one-hot classification label of the source graph yS and the target graph yT , the label of the augmented graph ¯y obtained by applying the first m operations (o1, ..., om) is computed as

where c(·) measures the cost of an operation. The assigned label is inversely proportional to the operation cost to reach the source or target from the augmented graph.

3.2 Learning Costs of Edit Operations

The standard unit cost model [Ullmann, 1976; Fischer et al., 2015; Riesen and Bunke, 2009] of the graph edit distance is incapable of measuring the importance of each operation as all operations are assigned the same cost, regardless of their significance or impact. However, the importance of edit operations would differ based on the context of the dataset. For example, changes in a functional group of molecular graphs can lead to larger semantic perturbation than the other parts in a property prediction task [Durant et al., 2002; Zhang et al., 2020]. Therefore, the edit operation leading to a large semantic modification should cost more than the others. To measure the importance of each operator in the computation of graph edit distance, we propose a learning algorithm for the operation cost based on a neural network model.

Triplet Loss for Learning Distance

A good cost function should be problem dependent. We use the triplet loss with known labels [Schroff et al., 2015] to learn the graph edit distance and the operation costs therein. We assume that the pair of graphs within the same class has a relatively shorter edit distance than those of different classes. Let GED(G,G′ ) be the distance between graphs G and G′ . We propose a triplet loss-based objective function to encode our intuition:

where G+ is a positive example whose label is the same as G, G- is a negative example whose labels are different from G, and γ is a margin hyperparameter.

Graph Edit Distance as Constrained Optimization

The computational complexity of graph edit distance computation is NP-complete [Abu-Aisheh et al., 2015]. Learning graph edit distance often requires relaxation to make the algorithm tractable [Fischer et al., 2015; Riesen and Bunke, 2009]. To simplify the learning, we assume that the cost of node operation subsumes the cost of dependent edit operations, similar to the construction of the edit path. With the simplified assumption, we only need to consider the following three cases when computing the edit distance between source graph GS = (VS, ES) and target graph GT = (VT , ET ) with operation cost function c : VS ∪∅×VT ∪∅ → R, where ∅ represents an empty node:

• Node u in VS is substituted by node v in VT with substitution cost c(u, v).
• Node u in VS is deleted with deletion cost c(u, ∅).
• Node v in VT is inserted with insertion cost c(∅, v).

We construct a cost matrix that encapsulates all required costs to compute the edit distance between two graphs. The cost matrix is constructed as

where n and m are the number of nodes in GS and GT , respectively.

With the cost matrix, the problem of computing the graph edit distance can be reduced to solving the assignment problem. Since the node in the source graph can only be substituted or deleted, only one operation can be performed in each of the first n rows. Similarly, since the node in the target graph can only be substituted or inserted, only one operation in each of the first m columns can be performed in edit distance computation. A binary assignment matrix X, whose size is the same as the cost matrix, is introduced to indicate which operation is performed in edit distance computation. With the assignment matrix, the computation of graph edit distance can be formulated as a constrained optimization problem

Design Cost Function with Neural Networks

We introduce the graph neural network framework to parameterize the cost function c. Specifically, we use the embedding distances between two nodes as the substitution cost. Let hu and hv be the output embedding of node u ∈ GS and v ∈ GT from a graph neural network. We use the distance between two embeddings as a substitution cost, i.e., cθ(u, v) = ||hu - hv||2, where θ is the parameter of the graph neural network. The embeddings of the graph neural network encode the neighborhood structure of the target node. If the embeddings of two nodes are similar, then the two nodes are likely to play a similar role in the graph. Hence, the substitution cost measures the structural similarity between two nodes. For the insertion and deletion operations, we additionally introduce a multi-layer perceptron, i.e., cθ,ϕ(u, ∅) = MLPϕ(hu) and cθ,ϕ(∅, v) = MLPϕ(hv), where ϕ denotes the parameters of MLP. The MLP computes the cost of insertion and deletion using the embedding of a node. We use the same network for both insertion and deletion. The graph neural networks encode the local structure of nodes into node embeddings. Consequently, by considering the costs of node operations, we effectively encapsulate the information regarding the neighborhood edges as well.

Optimization with a Differentiable Assignment Matrix

To learn the graph edit distance, we need to minimize the loss in Equation 2 w.r.t θ and ϕ. However, this optimization involves a non-differentiable optimization problem w.r.t the assignment matrix X in Equation 4. The Hungarian algorithm [Kuhn, 1955] can be used to find the optimal assignment X for each iteration of the stochastic gradient descent step. However, the Hungarian algorithm is non-differentiable and has a computational complexity of O(n3 ), making it difficult to employ during gradient-based optimization. We instead employ the Sinkhorn-Knopp algorithm [Sinkhorn and Knopp, 1967] to address this issue to obtain a differentiable assignment matrix. The Sinkhorn-Knopp algorithm transforms a non-negative matrix into a doubly stochastic matrix to approximate the Hungarian algorithm. Specifically, Sinkhorn-Knopp iteratively updates a soft assignment matrix ˜X via two intermediate variables u and v. Once u and v are initialized as a vector of ones, i.e., u(0) = [1, · · · , 1]⊤, at kth iteration of Sinkhorn-Knopp approximates the assignment

where each entry of matrix K is parameterized by the cost matrix and a regularizer parameter δ as Kij = exp(-Cij/δ), and 1 is a vector of ones. δ is a regularization term controlling the sharpness of the assignment matrix.

Note that the back-propagation algorithm needs to optimize the entire iterative process of the Sinkhorn-Knopp approximation. In experiments, we set the number of maximum iterations to 10 to reduce the computational cost. After learning the cost function, to augment a pair of randomly selected graphs, we first compute the cost matrix and then create a graph edit path using the optimal assignment from the Hungarian algorithm. Figure 2 shows the overall illustration of our proposed approach.

4 Experiments

In this section, we first show the effect of EPIC in graph classification tasks over 11 datasets. We further evaluate the robustness of GNNs with our method against corrupted labels. We provide additional analysis of our model selection process.

4.1 Effect of Augmentation for Graph Classification

Datasets. We used eight classification datasets: NCI1, BZR, COX2, Mutagenicity, IMDB-BINARY, IMDB-MULTI, PROTEINS, ENZYMES from TUDataset [Morris et al., 2020] and three classification dataset: BBBP, BACE, HIV

from MoleculeNet [Wu et al., 2018]. The datasets cover a wide range of tasks, including social networks, bioinformatics, and molecules.

Baselines. For baseline augmentation models, we use two graph augmentation methods as baselines: one that modifies a single graph, DropEdge [Rong et al., 2019], DropNode [Feng et al., 2020], Subgraph [You et al., 2020] and FLAG [Kong et al., 2022], another that mixes information from two graphs, SubMix [Yoo et al., 2022], Manifold-Mixup (M-Mixup) [Wang et al., 2021b], G-Mixup [Han et al., 2022], GREA [Liu et al., 2022], and S-Mixup [Ling et al., 2023]. We also report the performance of a vanilla model without augmentation.

Implementation details. We first learn the cost of edit operations for each dataset. We use Adam optimizer [Kingma and Ba, 2014] with a learning rate decay of 0.1 every 25 epochs. We train the cost function for 100 epochs on TUDataset. While we use the Sinkhorn-Knopp approximation with k = 10 in Equation 5 for training, the Hungarian algorithm is used for inference to obtain an optimal assignment given costs. We perform graph classification tasks with GIN [Xu et al., 2018] and GCN [Kipf and Welling, 2016] as a backbone model for augmentation. When we train each backbone model, for a fair comparison, we use the same hyperparameters and architecture tuned from the vanilla model for our method and other baseline models. We follow the Open Graph Benchmark setting [Hu et al., 2020] for MoleculeNet dataset. When training classification models, we compute the edit path between randomly paired graphs in each batch and use randomly chosen graphs from the edit path as augmentation. We use the validation set to choose the portion of augmented data points.

Classification results. Table 1 shows the overall results of the TUDataset for graph classification tasks. Our augmentation method outperforms the other baselines on seven and five datasets with GIN and GCN backbones, respectively, and achieves the second-best performance on one and two datasets with GIN and GCN. Table 2 shows the AUC-ROC scores with MoleculeNet datasets. We achieve the best performance on all datasets except for one second-best performance with GIN and GCN backbones over other baselines. The results from two benchmarks show our augmentation method consistently improves the generalization of GNNs.

4.2 Robustness Analysis

Verma et al. [2019] theoretically demonstrates that mixupbased augmentation enhances the robustness of deep neural networks against noisy labels. We also conduct a similar study. Following the settings used in Han et al. [2022] and Ling et al. [2023], we randomly corrupt labels in the training set of IMDB-BINARY, IMDB-MULTI, and Mutagenicity datasets and test the model performance with the uncorrupted test set. We run the experiments with three different proportions of noise: {0.2, 0.4, 0.6} based on GIN. Except for the noise, we use the same setting used in Subsection 4.1. Table 3 shows the classification accuracy with different proportions of noisy labels. EPIC outperforms the other baseline models, except for one case, showing the robustness of our augmentation under the noisy environment.

4.3 Ablation Studies

In this subsection, we show the result of ablation studies on each component in EPIC. Further ablation studies are shown in Appendix A.

Cost function variations. We test the effectiveness of the learnable cost function against other variations of the cost function. We use two variations of the cost function: unit cost, which measures the number of edit operations, and feature-distance cost, which measures the distance between two input node features, adopted from Ling et al. [2023]. The result in Table 4a shows that the learnable cost outperforms the other cost functions across all datasets. The results empirically verify our claim that the good cost function should be problem-dependent and can be learned from the dataset. We

(a) Classification accuracy with augmentation

• (b) Distance-based classification accuracy

Table 4: Comparisons between three different cost functions.

also classify the graphs in the test dataset based on their distance to the closest graph in each class. If the cost is learned properly, the distance from a test graph to the graph in the same class should be close to each other. Table 4b shows the result of distance-based classification. In most cases, EPIC outperforms the other fixed-cost methods. Results for all TUDataset can be found in Appendix B.

Hungarian vs Sinkhorn-Knopp. We investigate the impact of a differentiable assignment matrix with the SinkhornKnopp algorithm against a fixed assignment matrix from the Hungarian algorithm in the process of training. In Figure 3, we present the training and validation curve on the HIV dataset. In general, the Sinkhorn-Knopp algorithm shows a more stable learning process than the Hungarian algorithm. The training loss with Hungarian has not been stabilized after 20 epochs in HIV datasets. Moreover, the validation loss of Sinkhorn-Knopp is consistently lower than Hungarian after certain iterations. We conjecture that the non-smooth loss surface of Hungarian makes the gradient descent work hard, and eventually, the model fails to reach a good local minimum, whereas the smooth loss surface of Sinkhorn-Knopp results in a better performance despite being an approximation of Hungarian.

4.4 Qualitative Analysis

To examine how the results of the learned distance are reflected in the augmented graph, we conduct an experiment with a lollipop dataset whose structural properties are easily visualized. The (m, n)-lollipop graph consists of a head, a complete graph with m nodes, and a tail, a chain structured n nodes. The lollipop dataset consists of graphs with varying m and n. The label of a graph is the size of the head, i.e., m. Figure 4 displays examples of the trained graph edit distances and the corresponding edit path. With a positive pair, the learned graph edit distance substitutes the head nodes from the source graph for those of the target graph. Eventually, it maintains the complete subgraph of the head along the edit path. Additionally, we present the assigned cost for substitution to each node in Appendix C, which consistently shows the effectiveness of the cost function for EPIC.

5 Conclusion

In this paper, we propose a novel approach for graph dataset augmentation based on the graph edit distance. Our method overcomes the limitations of linear interpolation techniques in the non-Euclidean domain and provides a tailored augmentation solution for graph data. Through extensive experiments on benchmark datasets, we have demonstrated the effectiveness of our approach in improving the performance and robustness of graph-based models.

A Further Ablation Studies

In this section, we describe the ablation studies for model configuration. Specifically, we examine methods for determining the operation order in the edit path and the number of iterations in the Sinkhorn-Knopp algorithm.

Iterations of the Sinkhorn-Knopp algorithm. We adopt the Sinkhorn-Knopp algorithm to approximate the Hungarian algorithm to make the assignment matrix differentiable for optimization during training as described in Subsection 3.2. To analyze the effect of the number of iterations of the Sinkhorn-Knopp algorithm, we evaluate the classification performance under varying values of k in Equation 5. Table 5 presents the results of an ablation study. We further experiment to observe how well the assignment matrix, XS, derived from the Sinkhorn-Knopp algorithm approximates the assignment matrix, XH, from the Hungarian algorithm, as the parameter k varies. Firstly, we calculate both assignment matrices from our learned cost function on the test dataset and compute the Frobenius norm of the difference between the two matrices, ||XA||F = ||XS -XH||F , and then, measure an average of each Frobenius norm across the entire dataset. Figure 5 shows the average of Frobenius norm with varying k. We observe that the error decreases as k increases, suggesting that the Sinkhorn-Knopp algorithm's assignment matrix becomes more similar to the assignment matrix from the Hungarian algorithm. However, as k increases, the computational cost required for training also increases, indicating a trade-off relationship.

Operation ordering. When calculating the edit distance, the specific operation order does not affect the final result. To construct the edit path, we need to determine the operation order. In our analysis, we investigate the difference between two choices of operation orders. To maintain the local connectivity of the target graph within the edit path, we employ a breadth-first search (BFS) on the target graph, and node insertion/deletion/substitution is performed following the BFS order. The results in Table 6 compare randomly ordered augmentation with BFS-ordered augmentation on eight datasets. We find no significantly better ordering choices between these two methods. To minimize additional computational overhead, we utilize random ordering for the main result.

B Results on TUDataset Based on Cost Function Variations

In this subsection, we show the full result of classification described in Table 4 based on different cost functions: the unit cost, which counts edit operations, and the feature-distance cost, derived from Ling et al. [2023], which measures the distance between input node features. Table 7a demonstrates that the learnable cost outperforms other cost functions on all datasets. The result empirically proves our claim that an effective cost function should be problem dependent and learned from the dataset.

Also, if the cost is learned correctly, the graph with the shortest graph edit distance to a given graph should be in the same class. Under this premise, we classify the graphs in the test dataset based on their distance to the closest graph in each

(a) Classification accuracy with augmentation

• (b) Distance-based classification accuracy

(b) Average substitution costs between positive pair

Figure 6: Analysis of substitution cost on lollipop graph. Normalized average substitution costs between source nodes and target nodes for negative pair are shown in Figure 6a and positive pair in Figure 6b. The costs are averaged across the entire dataset.

class. Table 7b shows the result of distance-based classification. In most cases, EPIC outperforms the other fixed-cost methods.

C Further Analysis on Lollipop Dataset

To further show the effectiveness of the cost function for EPIC, we analyze the cost for substitution to each node on the lollipop dataset. (m, n)-lollipop graph consists of a head, a complete graph with m nodes, and a tail, a chain structured n nodes, with varying m and n. We use the number of heads as the label of a graph, i.e., m. Figure 6 shows the head-to-head, head-to-tail, and tail-to-tail substitution costs. For instance, the head-to-head substitution cost measures the average substitution costs between the head nodes from the source graph with those of the target graph.

With the negative pair, the average node substitution cost for the head nodes is 0.97, whereas the average for the tail nodes is 0.04. These results align with our intuition that editing the head, closely related to the label, incurs a high cost. Thus, any modification to this part leads to substantial changes in the label. With the positive pair, the head-to-head and tail-to-tail substitution costs are 0.07 and 0.2, respectively. Those values are much smaller than 0.8 of head-tail costs. The lower cost for the head-head substitution in a positive pair resulted from the fact that it involves the exchange of nodes associated with the same label. Similarly, the low cost for the tail-to-tail substitution aligns well with our intuition since the nodes are unrelated to the label. In contrast, the head-to-tail substitution is assigned a high cost because it substitutes a label-associated part with a non-associated part. This preserves the head part of every graph on the edit path between positive-pair, ensuring that the augmented graph keeps the same label over the path.

Acknowledgements

This work was supported by Institute for Information & communications Technology Promotion (IITP) grant funded by the Korea government (MSIP) (No. RS-2019-II191906: Artificial Intelligence Graduate School Program (POSTECH)), Basic Science Research Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education (2022R1A6A1A03052954, 2022R1C1C1013366, RS-2024-00337955), and the Technology Innovation Program (No. 20014926, Development of BIT Convergent AI Architecture, Its Validation and Candidate Selection for COVID19 Antibody, Repositioning and Novel Synthetic Chemical Therapeutics) funded by the Ministry of Trans, Industry & Energy (MOTIE, Korea).

Contribution Statement

Jaeseung Heo and Seungbeom Lee contributed equally to the paper as the first authors.