A Polynomial Time Graph Isomorphism Algorithm via Self-Supervised Gradient Descent
Graph Isomorphism;Optimization;Self-Supervised Learning;Graph Matching;Graph Theory
Yes
No ethics review needed.
- Can you please be more precise about the usage of the edge weights in training and inference? Is $\alpha$ in Algorithm 1 a hard threshold that removes all edges with weight $<\alpha$? How to choose this?
- Assuming thresholding takes place: Is precision at 10 or ROC a good evaluation measure? In this case, I assume that one has no influence on the amount of edges that is selected by the explainer.
- Assuming no thresholding takes place: How can you ensure that the GNN after edge weighting only uses information of high weight edges, as claimed in the introduction. In this case, it seems that message passing uses all existing edges of the graph and may also reweight low weight edges from the explainer with suitable parameters.
- Furthermore both p@10 and ROC at some point require to select a threshold. Does this imply that the user needs to know/set the size of the explanations that they want to get?
- The explainer model seems to weight edges independently of graph topology, just based on attributes of the edge and the two incident nodes. This, however, implies that such an explainer cannot distinguish e.g. a C-C edge on a six-cycle from a C-C edge on a three-cycle. Hoever, it seems, that this is the case in Figure 1c. Are you using some particular preprocessing to add this information?

# Minor issues and typos
- l75 We introduces
- l203 two distributions are keps
- Algorithm 1 / Section 3.4.2 use inconsistent notation. While in Alg.1 $\alpha$ appears as threshold parameter, it appears as a tradeoff parameter in a different place. I suggest to rename one of the alphas and to consistently use the same sybmol for the threshold parameter in Alg.1 and Sec.3.4.2
- The paper is well structured and introduces all relevant concepts and steps
- Ante-hoc explainers -- in this case subgraphs on which the GNN model is allowed to learn solve several of the problems of instance based post-hoc explanations of graphs
- the overall architecture seems simple and elegant
The authors propose to learn an edge weighting scheme together with a graph neural network where the edge weights serve as explanation of the graph neural network. The combined training of the explainer and the GNN minimizes an Information Bottleneck objective to reduce the size of the explanations while maximizing the predictive performance of the GNN learner. Empirical experiments on suitably preprocessed datasets suggest that the method, called EAGER, works well in practice.
- It remains unclear from the presentation whether indeed subgraphs are used or whether the explainer computes an edge weight that just scales down edge attributes during training and/or inference. In the latter case, explanations would be not much helpful, I fear.
- The edge weighting approach to arrive at a subgraph(?) is not expressive enough to capture many phenomena that are taking place in graphs. See question below.
- It remains unclear how to control the size of the explanations/subgraphs
Yes
No ethics review needed.
*Algorithm (Line 13)* : How is Line 13 implemented? The algorithm appears to contain an implicit loop that could hinder scalability, and row-based argmax does not satisfy column constraints.

*Pareto Trade-off Analysis*: Have  the authors tried generating Pareto trade-off plots showing runtime vs. accuracy across methods?
Effective on Specific Datasets: PTGI shows improved accuracy in benchmark datasets for synthesized and real-world graphs, particularly when compared to convex-relaxation-based GI algorithms.
The paper introduces the Polynomial Time Graph Isomorphism (PTGI) algorithm, which aims to solve the graph isomorphism (GI) problem through an optimization-based approach. PTGI uses self-supervision mechanism along with  gradient descent, to address the challenges of local optima caused by graph symmetries. The algorithm  demonstrates high accuracy in identifying isomorphic graphs across synthesized and real-world datasets. The authors provide empirical evidence of PTGI’s efficiency and accuracy, comparing its performance favorably against state-of-the-art convex relaxation-based GI algorithms.
*Insufficient Baseline Comparisons*: The paper evaluates PTGI primarily against other optimization-based GI algorithms, without considering approximate GED solvers using either neural and combinatorial approaches. Given that the algorithm incrementally constructs node alignments, it is unclear what advantages it offers over traditional branch-and-bound GED solvers.

*Missing Discussion on Relevant Literature*: The paper is missing discussion/baseline using entropic regularization with Gumbel noise, which is known to aid in symmetry breaking and could potentially address the limitations mentioned in section 3.3.

*Numerous Typos and Incomplete Proofreading*: The manuscript contains multiple typographical errors, such as in lines 104 and 138. 

*Misleading Polynomial-Time Claim*: The title and naming of PTGI imply a general polynomial-time solution to the GI problem. However, PTGI is an approximate solver, which should be clearly reflected in the title and framing to avoid misinterpretation.
Yes
No ethics review needed.
1) In line 70, the authors say various graph types. What exactly are various graph types? 
2) In line 117, authors say “real-world graphs are not neccessarily “friendly””. Can the authors provide any theoretical justification or concrete arguments rather than just a claim?
3) Does their algorithm work on graphs with repeating eigenvalues? If yes, what is the proof?
4) What happens if we try random initialization for graphs shown in Figure 1? 
5) In lines 342-346, the authors claim that only little impact can be seen on the performance. What is the little impact? This probably implies that the data generation process did not generate challenging cases.
6) The authors claim that the computational complexity of their method is $O(n^4)$ but isn’t it $O(T \times n^4)$? What is T chosen in Algorithm 1? 
7) How does your algorithm perform on strongly regular graphs or distance regular graphs?
Addressed an important theoretical problem
This paper presents the Polynomial Time Graph Isomorphism (PTGI) algorithm, an optimization-based approach designed to address the interesting and challenging problem of isomorphism. The authors claim to present a practical GI algorithm. I recommend rejection of this submission. Kindly refer to the weakness and Questions section for detailed technical comments.
1) The authors present an approximate and not exact isomorphism algorithm, which may be more suited for graph-matching problems. I think certain cases might require an exact algorithm and not an approximate one. While computational complexity is important for isomorphism, the accuracy or correctness of the proposed algorithm should also be considered. 
2) The paper lacks major theoretical contributions. 
3) Incomplete literature review: The authors should discuss the following GCN or GNN papers on isomorphism:
- Z Chen, S Villar, L Chen, J Bruna, On the equivalence between graph isomorphism testing and function approximation with gnns, Neurips 2019
- Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR 2019 
- Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks, Neurips 2019
- Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations, ICML 2019
- Charilaos I Kanatsoulis and Alejandro Ribeiro. Graph neural networks are more powerful than we think.
- Feng, J., Chen, Y., Li, F., Sarkar, A., and Zhang, M. How powerful are k-hop message passing graph neural networks.
- Huang, Y., Peng, X., Ma, J., and Zhang, M. Boosting the Cycle Counting Power of Graph Neural Networks with I^2-GNNs.
- Zhou, C., Wang, X., Zhang, M. From Relational Pooling to Subgraph GNNs: A Universal Framework for More Expressive Graph Neural Networks 
4) Comparison from existing baselines: The authors should compare their method to the above (relevant) baselines/papers.
5) Comparison on well-known datasets: 
- Kindly see the circular skip link CSL dataset from Murphy et al, ICML 2019 
- Kindly see the BREC dataset. Refer: Wang, Y., and Zhang, M. Towards Better Evaluation of GNN Expressiveness with BREC Dataset.
6) In line 61, the authors claim “in polynomial time, without constraints on graph types or properties”. I'm afraid that's obviously not right because the isomorphism problem can not be solved in polynomial time. Do the authors have any theoretical proof for this claim? I believe the experiments are done on the family of graphs where the proposed algorithm does not fail. Hence, the authors are not discussing the graphs for which the proposed algorithm fails.
7) Nauty is widely accepted as the practical GI algorithm. Refer [https://www.sciencedirect.com/science/article/pii/S0747717113001193](https://www.sciencedirect.com/science/article/pii/S0747717113001193). The authors should compare their work to Nauty at least empirically to claim improvement on practical graph isomorphism.  
8) The average run time is almost linear for GI, but the proposed algorithm has an average runtime of $O(n^4)$.  
9) The worst run time of the proposed algorithm might be better than exponential, but the average run time is still worse. I feel that the authors are doing unfair comparisons. 
10) Various presentation issues: The contributions on lines 64-71 can be shortened. I feel it is too verbose. Tables 2 and 3 entries can be arranged horizontally to save some space and enhance readability.
Yes
No ethics review needed.
- I would name the types of special graphs in paragraph 2 of page 1 (planar graphs, ordered graphs, etc.)

- I wonder to what extent the GI problem is still relevant in times of GNNs?

- I have the feeling that the paragraph below Table 1 (starting with For each graph..." Includes several redundancies with texts above. 

- Is there a way to extend PTGI to weighted or labelled graphs? This would greatly extend the applicability of the algorithm.

- Is self-supervision really effective in highly symmetrical graphs?
-Nice algorithm that improves the computation of GI w.r.t. both accuracy and computation time

-Convincing experimental results 

-Good literature review although some more papers for the PR community could be included (e.g. Optimal quadratic-time isomorphism of ordered graph or A decision tree approach to graph and subgraph isomorphism detection)
In this paper, a novel approximate algorithm for the graph isomorphism problem is presented. The main idea is to use a self- supervised signal that incrementally builds on a graph isomorphism by adding a vertex correspondence in each iteration. The algorithm is suboptimal as it does not guarantee that an isomorphism can be found between two isomorphic graphs.
-I feel that subgraph isomorphism (or in general error-tolerant graph matching like graph kernels or other graph matching methods) have greater practical relevance. In other words, I doubt the practical relevance of the GI problem even though it is -- without a doubt -- a very important scientific topic. 

- This point of criticism goes in the same direction as the point mentioned above. I wonder to what extent the GI problem is still relevant in times of GNNs?

- A particular weakness of the method is that it can only be applied to unlabeled graphs (both nodes and edges). I also wonder whether or not the labeling can be helpful for your algorithm (especially for the real world graphs)?

- In the introduction I somehow miss the most recent applications of graphs (and maybe you can mention some real world application of GI as well)

- Personally, I do not like to see sentences like "demonstrates high accuracy... in polynomial time..." In the introduction. In the abstract such an anticipation of the conclusions of the results may be appropriate, in the introduction rather not. 
I would expect in the introduction to have some intuitive introduction, what is novel about the proposed method. Furthermore, I would expect to find out here what exactly the contribution is (in terms of the method). Especially, you should mention earlier that your method is a variant of the Vogelstein method (as stated on page 8) 

- In the introduction it is not well declared that your method is an approximate method for the GI problem (or tu put it more generally: you should better discriminate the two families of algorithms). Actually, you mention for the first time that PTGI is an approximate GI algorithm at the end of Section 4, which is too late. 

- You claim several times in your paper (in at least three places) that “we found that such type of optimization approaches often generate local optima...” Without empirical results/evidence, I find this somewhat tricky. 

- The running time chart (Fig. 2) is in my opinion not well explained and not thorough enough. You should include also plots of the reference systems.

- Since th ePTGI does not guarantee the ability to find an isomorphism between isomorphic graphs, this introduces an element of uncertainty in cases where the algorithm does not find an isomorphism.

- Being a self-supervisor, the effectiveness of this technique depends heavily on the quality of the self-generated labels. This may limit performance in situations with more complex graphs.

- Despite its efficiency compared to other algorithms, the complexity remains prohibitive in many contexts on the practical side.

- The algorithm is designed for unweighted and unlabelled graphs, limiting its applicability
@inproceedings{
anonymous2024a,
title={A Polynomial Time Graph Isomorphism Algorithm via Self-Supervised Gradient Descent},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=tPsZDNvMqJ},
note={under review}
}
Graph isomorphism (GI) is a fundamental problem in graph theory. 
Despite recent advancements, determining whether two graphs are isomorphic remains computationally challenging. 
This paper introduces the Polynomial Time Graph Isomorphism (PTGI) algorithm, an optimization-based approach leveraging self-supervision techniques to efficiently tackle the graph isomorphism problem. 
PTGI aims to escape local optima caused by graph symmetries and provides high accuracy in identifying isomorphic graphs in polynomial time. 
Experimental results demonstrate PTGI's effectiveness across various graph types, making it a valuable tool for practical applications.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Graph Isomorphism Optimization Self-Supervised Learning Graph Matching Graph Theory
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/a417efe6d8009eea1e32b41080bde6ab1f289266.pdf
unsupervised, self-supervised, semi-supervised, and supervised representation learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
A Polynomial Time Graph Isomorphism Algorithm via Self-Supervised Gradient Descent
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission