A Spectral Framework for Assessing the Geodesic Distance Between Graphs

Answer to the weaknesses:

1. The Lim paper [1] does not address the problem of calculating a distance metric between graphs. Our work first performs graph matching and then converts the matched graphs to $n \times n$ real positive symmetric definite (SPD) matrices that naturally form a Riemannian manifold. Then the geodesic distance between data points is calculated using a Riemannian metric. Here graph matching is a crucial step that confirms the infimum distance between data points in the manifold. In the case of graphs of different sizes, we used a resistive distance-based spectral coarsening method to match their sizes and then proceeded with subsequent steps. To our knowledge, no previous work has used this method to determine the distance between graphs. The mentioned paper has influenced our idea generation and literature review, which we have properly cited in our paper. However, our problem statement is fundamentally different.

2. Common GNN models, such as Graph Isomorphism Networks (GIN), use message passing between convolutional layers, followed by one or more linear layers for the classification tasks. In contrast, Support Vector Classifiers (SVC) employ indefinite kernels that leverage the distances between points to distinguish between graph classes. To our knowledge, no method currently combines SVC with GNN classifiers. However, this could be an interesting direction for future work to improve classifier performance.

3. Thank you for bringing this to our attention. We have compared the accuracy of our classifier with the most common and widely used graph classification methods. Since our method does not require node features, we evaluated these classification models using graph datasets without node features to ensure a fair comparison. Although we are aware of some recent classification models that perform slightly better, we were unable to obtain their code, which is essential for us to benchmark on datasets without node features.

[1] Lek-Heng Lim, Rodolphe Sepulchre, and Ke Ye. “Geometric distance between positive definite matrices of different dimensions.” IEEE Transactions on Information Theory, 65(9):5401–5405, 2019.

Answer to the weaknesses:

1. Thanks to the reviewer for pointing out this very relevant concern. In Section 4.3, we aim to explore the relationship between graph cut mismatches and the generalized eigenvalues of the modified Laplacian (SPD) matrices. Unfortunately, we do not have a rigorous mathematical proof that directly connects these quantities. Instead, we provide approximate relationships between them. The generalized eigenvalues are used to compute the distance value (via the AIRM method), and there is a well-established connection between eigenvalues and graph cuts mismatches. To simplify the analysis, we focus on graphs of the same size to reduce computational complexity.

2. Thank you for your comment. The only assumption is that both graphs are connected to use our framework for computing GGDs. Therefore, this assumption does not limit the applicability of the method in real-world scenarios.

Answer to the questions:

1. Thanks to the reviewer for raising this question. We agree and have revised the abstract of our work to emphasize the development of the distance metric, with stability analysis and graph classification being crucial applications of our contribution.

Answer to the weaknesses:

The Lim paper [1] does not address the problem of calculating a distance metric between graphs. Our work first performs graph matching and then converts the matched graphs to $n \times n$ real positive symmetric definite (SPD) matrices that naturally form a Riemannian manifold. Then the geodesic distance between data points is calculated using a Riemannian metric. Here graph matching is a crucial step that confirms the infimum distance between data points in the manifold. In the case of graphs of different sizes, we used a resistive distance-based spectral coarsening method to match their sizes and then proceeded with subsequent steps. To our knowledge, no previous work has used this method to determine the distance between graphs. The mentioned paper has influenced our idea generation and literature review, which we have properly cited in our paper. However, our problem statement is fundamentally different.

[1] Lek-Heng Lim, Rodolphe Sepulchre, and Ke Ye. “Geometric distance between positive definite matrices of different dimensions.” IEEE Transactions on Information Theory, 65(9):5401–5405, 2019.

Answer to the weaknesses:

1. As discussed in our work, Phase 1 involves finding the correspondence between nodes using a Graph Matching Technique. When we consider two different adjacency matrices of the same graph, the GRAMPA method identifies the permutation matrix that enables us to determine the approximate node-to-node correspondence. The proof for this scenario, where we account for noise (i.e., two different adjacency matrices), is provided in Lemma A.2 and is explained in detail in the GRAMPA paper [1]. Our empirical results demonstrated exact recovery in this case, meaning that after graph matching, the second adjacency matrix matches the first, provided they originate from the same graph.

2. In Section 4.3, we explained the relationship between GGD and the structural mismatch of graphs. After obtaining a node-to-node correspondence using a graph-matching algorithm, we can determine the graph cut mismatch between two graphs for a set of nodes. This mismatch is the ratio of edges going out of that set of graph nodes. In Equation (11), we show that the largest generalized eigenvalue of the Laplacian matrices of the graphs serves as the upper bound for the maximum possible graph cut mismatch between two graphs for any set of nodes S ⊆ V, where V is the set of all nodes. Similarly, the other eigenvalues quantify the graph cut mismatches between the input graphs. When using the generalized eigenvalues to calculate the GGD value in Equation (9), this value correlates with the graph cut mismatches of the two graphs. These graph cut mismatch ratios are closely related to the structural mismatch of the input graphs.

3. We used modified Laplacian matrices, which are Symmetric Positive Definite (SPD), due to their theoretical support in forming a natural Riemannian manifold. Laplacian matrices are not Symmetric Positive Definite but are rather semi-definite. In the mathematical equation, it is clear that we need SPD matrices to compute their inverse for calculating the AIRM (Affine Invariant Riemannian Metric). However, this equation is used to calculate geodesics in the SPD manifold. Without the modification, using just the Laplacian matrices, we do not have proper information on whether the n*n Symmetric Positive Semi-Definite matrices create a Natural Riemannian Manifold or not. We have not found any previous work on this.

Nevertheless, we conducted experiments using the Laplacian matrices directly to calculate the GGD through the pseudoinverse and observed very poor results. The accuracy for SVC using GGD with the pseudoinverse was around 56.88%, compared to our result of 86.24%.

Answer to the questions:

1. In our method, we do not use resistances to determine whether the graphs are the same or not. Rather, if the graphs are the same or even of the same size, we do not need resistances. When the graphs are of different sizes, we calculate the resistive distances between the nodes of each edge in the larger graph and use coarsening until the sizes of the graphs are matched.

2. In the coarsening method, we need to calculate the effective resistance between nodes for all edges and repeat this process until we reach the target node count. Since this involves computing a large number of effective resistances, using the approximated method helps reduce computational cost. Furthermore, this approximation does not compromise our accuracy during the coarsening step. When the graphs reach the same size in terms of node numbers, we only need to calculate the eigenvalues once to obtain the similarity matrix.

3. Thanks to the reviewer for this valuable suggestion. In the supplementary section of our revised paper (Appendix A.1), we have included an algorithm flow.

[1] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. “Spectral graph matching and regularized quadratic relaxations: Algorithm and theory”. In International conference on machine learning, pp. 2985–2995. PMLR, 2020.

3.e. Thanks to the reviewer for raising this concern. When coarsening an edge, we calculate the effective resistance between the two nodes it connects. If the effective resistance is lower than that of other edges, the edge can be coarsened without significantly compromising the graph's structure. However, when proper node features are available, coarsening two nodes with different features, even if they are structurally close, could disrupt the graph's properties. By adjusting the weight, we can control the coarsening process. For instance, if the weight is sufficiently large, the modified effective resistance between nodes with different features will always outweigh that of nodes with similar features, effectively preventing their coarsening. In the highlighted section of 5.1 in the revised paper, we have provided additional clarification.

4. We agree that providing an algorithmic flow including all the proposed steps would greatly enhance understanding of the processes. In the supplementary section of our revised paper (Appendix A.1), we have included such a flow.

5. We applied our method to compare with existing classification techniques, using datasets that are commonly benchmarked in graph classification tasks. This benchmarking approach was also inspired by the TMD paper [2].

6. Assuming the reviewer is referring to the graph classification task using GINs, we employed the method described in the original GIN paper [3]. However, we agree with the reviewer that a train/test/validation split can lead to a more unbiased classification. To address this, we conducted experiments using an 80%-10%-10% split, instead of the 90%-10% split and observed the same results.

7. We understand the reviewer's concern. For readers with a strong background in Spectral Graph Theory and Graph Neural Networks, these paragraphs may seem unnecessary. However, we included them as supplementary material for those in the general Machine Learning field who may have a limited understanding of Graph Theory.

8. In our paper, we introduced the concepts of Graph Distances, reviewed related works, and outlined the motivation and contributions of our study in the introduction. Section 3 provided an overview of our methodology and a high-level description of the steps involved, while Section 4 offered a detailed explanation of the methods. In the revised draft, we have modified these three sections to minimize repetition.

Answer to the questions:

1. The reviewer is correct. In Equation 14, the resistive distance is calculated, while in Equation 15, the modified resistive distance is computed by adding the weighted Euclidean distance between node features. This error has been corrected in the revised version of the paper

2. In the revised draft, we have modified these three sections to minimize repetition.

3. We thank the reviewer for highlighting this point. We have revised Table 2 to present the results in a more consistent format.

4. All the appendix numbers have been updated in the revised paper as we included two additional sections. Here, we will mention the previous appendix numbers for reference.

We understand A.1 (Graph Adjacency and Laplacian Matrices), A.2 (Riemannian Manifold), A.3 (Effective Resistance in Graph Theory), A.8 (Using Normalized Laplacians for GGD Calculation) may be common knowledge for individuals with a background in Spectral Graph Theory and Riemannian Geometry. However, we included these sections as references to assist readers in the broader Machine Learning community who may have limited knowledge of these topics.

AIRM is a Riemannian metric on the Riemannian manifold. Based on this assumption, in A.4 (Detailed Proofs Showing GGD is a Metric), we provided the necessary proofs to establish GGD as a valid distance metric.

In A.7 (Comparison of Two Different Riemannian Metrics for SPD Matrices), we compared the two most well-known Riemannian metrics and explained why AIRM was selected as our metric of choice.

[1] Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. “Spectral graph matching and regularized quadratic relaxations: Algorithm and theory”. In International conference on machine learning, pp. 2985–2995. PMLR, 2020.

[2] Ching-Yao Chuang and Stefanie Jegelka. “Tree mover’s distance: Bridging graph metrics and stability of graph neural networks.” Advances in Neural Information Processing Systems, 35:2944–2957, 2022.

[3] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. “How powerful are graph neural networks?” In International Conference on Learning Representations, 2019.

Answer to the weaknesses:

1. Thanks to the reviewer for raising this question. Spectral distances have limitations when calculating the distance between co-spectral graphs (distinct graphs that share the same eigenvalues in their adjacency matrices). Our method, which employs the Riemannian metric, overcomes this limitation by using generalized eigenvalues derived from their modified Laplacian matrices.

2. Section 4.3 demonstrates the relationship between generalized eigenvalues and graph structural mismatches using the graph cut mismatch. This relationship is not limited to the most extreme generalized eigenvalues but applies to all the generalized eigenvalues computed with both graph Laplacians. Empirical results support our claim. For two graphs of the same size, we observe varying graph cut mismatches for different sets of corresponding nodes. The extreme eigenvalues align with the highest mismatches, followed by the second-largest eigenvalue corresponding to the next largest mismatch. Additionally, there are several node sets where the cuts in both graphs are nearly identical, resulting in a cut mismatch close to 1. This is also reflected in the generalized eigenvalues, where we observe a significant number of unity values. We have included Section A.7 in the supplementary material of our revised draft, demonstrating this example with a graph pair from the MUTAG dataset.

3.a. The coarsening step is essential for the formation of the Riemannian manifold (a cone of the Symmetric Positive Definite (SPD) matrices of the same sizes), whereas the graph matching is critical for computing the geodesic (shortest) distance between two modified Laplacian matrices. In other words, without converting two graphs of the ones with the same size, we can not use the Riemannian metric defined for SPD matrices; without doing graph matching, we can not compute the meaningful geodesic distance between two graphs since unmatched graphs will result in much greater distances on the aforementioned Riemannian manifold.

3.b. Unlike some existing matching methods that use only the extreme eigenvalues and eigenvectors, GRAMPA constructs the similarity matrix using all possible combinations of eigenvalues, thus achieving the most accurate alignment possible. Since the matching procedure in GRAMPA is performed using the eigenvalues and eigenvectors associated with the graph adjacency matrices, the proposed spectrum-preserving graph coarsening step will make sure the node merging step will not significantly impact such eigenvalues and eigenvectors. During our exploration of various graph-matching methods, we found that the spectral method GRAMPA produced better results compared to the others.

3.c. We employed an iterative process to determine the optimal value of $\eta$. In Lemma 4.1 of our paper, we referenced the selection method of $\eta$ proposed in the GRAMPA paper [2]. The regularization parameter is recommended to fall approximately within the range $[n^{-0.1}, c/log(n)]$, where n represents the number of nodes, and c is a positive constant that is typically set to unity (1) for approximations discussed later in the GRAMPA paper. For the MUTAG dataset, with an average node count n = 19.79, the range for $\eta$ is [0.335,0.742]. The GRAMPA paper also notes that the accuracy of the matching is not highly sensitive to this parameter within a specific range. For practical datasets, iterative methods are suggested for identifying the optimal value, which we discussed in Appendix A.11 of the revised draft (previously Appendix A.9 in the earlier version).

In our experiments, we tested with several values of $\eta$ and observed the highest accuracy at 0.5. Figure 6 illustrates the impact of $\eta$ on classification accuracy, revealing that the accuracy remains nearly constant for values between 0.2 and 0.5, supporting the GRAMPA paper's claim regarding the parameter's insensitivity.

3.d. To address the challenge of precisely matching the node counts of two graphs, we developed this spectral coarsening method with the goal of best-preserving graph spectral (structural) properties. Although there are several existing coarsening methods proposed for preserving graph spectral (structural) properties, they cannot control the number of nodes in the reduced graph. Our method is the only approach that allows us to coarsen edges one by one until the desired graph size is achieved, which is crucial for the subsequent graph matching and manifold formation steps.

I have read the various elements of answers, and the revisions made by the authors. I have also read the other reviews and the following discussions. I think that the reviewers have a point about the fact that the authors don't justify enough the novelty of their work w.r.t. the work of Him et al., and their GGD (for instance the need to use a coarsening technique, while Him et al. had another methods).
As there are also some other points that could benefit from major revisions (deeper than the one currently done), and despite the fact that I acknowledge that the authors tried to revise some of the points and made some efforst toward better clarity, I keep my review as it is.