Graph Classification via Reference Distribution Learning: Theory and Practice

Summary

Instead of compressing node embedding matrix into a graph-level vector, this paper proposes a reference distribution learning method GRDL especially designed for graph classification task. GRDL achieves graph classification by measuring the dissimilarity between distributions of the input graph and the references. Theoretical analysis of the generalization error bound offers guidance of hyperparameter tuning.

Strengths

- This paper is well-motivated to avoid information loss caused by node embedding downsampling. - The idea of considering graph classification as a distribution comparison problem is interesting. - The authors have solid mathematical skills.

Weaknesses

- The idea is borrowed from domain transfer learning but lacks adaption to graph classification task. In graph classification task, graphs in each dataset “are drawn i.i.d” as the authors mentioned at line 205. This means that although graphs have different classes, they belong to an identical distribution, which is contradictory to the hypothesis of this paper that different classes belong to different reference distributions. - In my opinion, this paper didn’t avoid information compression compared to mean pooling and max pooling. MMD unifies the source and target inputs as a vertex in the same RKHS and then calculate the distance between them. I think the mapping from embedding matrix into a vertex can be regarded as information compression, and the calculation of mean discrepancy is similar to mean pooling. - The time complexity is too high, the datasets used for large-scale experiments are unreasonable, and the competitors used in efficiency experiment is unreasonable. The time complexity is $O(N^2)$, which is the same as the highly criticised time-consuming node clustering pooling methods (such as DiffPool[1]), while node dropping methods (such as SAGP[2]) only requires a time complexity of $O(E)$. The complexity restricts its scalability to larger-scale graphs. Three so-called large-scale datasets are not really large-scale. They are only large in the number of graphs but not in the number of nodes in each single graph. The authors should add experiments on synthetic large-scale datasets. Besides, in time cost comparison, the authors didn’t choose competitors with SOTA efficiency but used two time consuming methods, which is quite unreasonable. - The theoretical contribution of generalization error bound is limited. Firstly, the result offers fuzzy insights into the choose of hyperparameters by giving “moderate-size message passing GIN”, and “moderate-size references”. How to define “moderate”? At line 240, the authors analysis that “a network with a smaller $L4 and $r4 may guarantee a tighter bound on the population risk compared to a larger one. Therefore, a promising strategy is to use a moderate-size message passing GNN”. What’s the causality between “smaller” and “moderate-size”? That’s quite confusing. Experimental results in Appendix show that hyperparameters are still choosed on trial and error. Besides, the generalization ability comparison with GIN with mean readout is meaningless because the competitor is not the SOTA. - Important baselines are missing in the experiments. Please add comparison results with recent graph pooling methods such as ASAP[3], MinCutPool[4], StructPool[5], MuchPool[6], TAP[7], Wit-TopoPool[8], and MSGNN[9]. References [1]Ying Z, You J, Morris C, et al. Hierarchical graph representation learning with differentiable pooling[J]. Advances in neural information processing systems, 2018, 31. [2]Lee J, Lee I, Kang J. Self-attention graph pooling[C]//International conference on machine learning. PMLR, 2019: 3734-3743. [3]Ranjan E, Sanyal S, Talukdar P. Asap: Adaptive structure aware pooling for learning hierarchical graph representations[C]//Proceedings of the AAAI conference on artificial intelligence. 2020, 34(04): 5470-5477. [4]Bianchi F M, Grattarola D, Alippi C. Spectral clustering with graph neural networks for graph pooling[C]//International conference on machine learning. PMLR, 2020: 874-883. [5]Yuan H, Ji S. Structpool: Structured graph pooling via conditional random fields[C]//Proceedings of the 8th International Conference on Learning Representations. 2020. [6]Du J, Wang S, Miao H, et al. Multi-Channel Pooling Graph Neural Networks[C]//IJCAI. 2021: 1442-1448. [7]Gao H, Liu Y, Ji S. Topology-aware graph pooling networks[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021, 43(12): 4512-4518. [8]Chen Y, Gel Y R. Topological pooling on graphs[C]//Proceedings of the AAAI Conference on Artificial Intelligence. 2023, 37(6): 7096-7103. [9]Lv Y, Tian Z, Xie Z, et al. Multi-scale Graph Pooling Approach with Adaptive Key Subgraph for Graph Representations[C]//Proceedings of the 32nd ACM International Conference on Information and Knowledge Management. 2023: 1736-1745.

Questions

Please refer to the weaknesses.

Rating

4

Confidence

5

Soundness

2

Presentation

3

Contribution

2

Limitations

N/A

Summary

The paper introduces a novel algorithm called GRDL for graph classification. GRDL treats each graph’s latent node embeddings given by GNN layers as a discrete distribution and directly classify distributions without global pooling. The authors derived generalization error bounds for GRDL and verified them numerically. The experiments on many graph datasets show the superiority of GRDL. GRDL is 10 times faster than leading competitors.

Strengths

* Originality: The proposed algorithm GRDL and the theoretical results are novel. * Quality: The paper is well-organized and contains rich theoretical results and numerical comparisons. * Clarity: The motivation (e.g. Example 2.1), assumptions, optimization, implication of theorems, and the experimental setting have been clearly explained. * Significance: Graph classification is a challenging problem due to the difficulty in converting nodes’ embeddings to a vector as the global representation of each graph. The proposed method gets rid of readout operations and directly classifies the discrete distributions formed by nodes’ embeddings. It can outperform graph kernels, GIN, and graph transformers. Moreover, the paper proved that the proposed model has better generalization ability than the baseline GIN, which is a big contribution.

Weaknesses

There is no major weakness found. Please refer to my questions in the next section.

Questions

* Besides GIN, there are other GNN models such as GCN and GAT. Why did the authors consider GIN only in the theoretical analysis and experiments? * I think the parameter $\theta$ of the Gaussian kernel can be absorbed into the neural network parameter. I suggest the authors discuss the necessity of setting or optimizing $\theta$ separately. * In Theorem 3.2, the bound is related to $K$, the number of classes. But, in many literature of generalization analysis, the bound is not related to the number of classes. Could the author explain the difference?

Rating

7

Confidence

5

Soundness

4

Presentation

3

Contribution

4

Limitations

The authors discussed the limitations in Section 6.

Summary

This paper proposes to make graph-level predictions via distribution comparison between node-level representations and discrete reference distributions. The authors claim that their proposed method avoids the requirements of graph pooling for graph-level tasks. and reduce the risk of information loss. Theoretical and empirical justification results are provided.

Strengths

- The authors propose a novel and simple method for graph classification and provide theoretical analysis on the generalization bound. The discussion is clear and extensive. - The method shows advantage in time cost compared to related works. - The authors performed extensive ablation study on the proposed method.

Weaknesses

- Equation in L138-139 (a missing equation index?) also requires summation over nodes. The description of "avoid graph pooling operation" seems to be overclaimed. I suggest that the authors reconsider it. - An ablation study on the discrimination loss and the usage of node-level representation is required. I think the main improvement in performance may be attributed to the discrimination loss. It helps the model learn distant representations for graphs of different labels in the feature space. The performance of the proposed method should be compared with and without the discrimination loss. Besides, the authors should also implement a baseline with discrimination loss where node representations are first sum-pooling and then compared with the reference distribution. - Minor: Latest baseline models are required for a comprehensive empirical comparison, such as graph pooling including SEP[1], GMT[2], and CoCN[3] and graph transformers including Exphormer[4], GRIT[5], and MPNN-VN[6]. Considering the time limitation and the similarity of the datasets, a comparison on part of the datasets will be sufficient. [1] Structural entropy guided graph hierarchical pooling. ICML'22 [2] Accurate Learning of Graph Representations with Graph Multiset Pooling. ICLR'22 [3] All in a row: Compressed convolution networks for graphs. ICML'23 [4] Exphormer: Sparse Transformers for Graphs. ICML'23 [5] Graph Inductive Biases in Transformers without Message Passing. ICML'23 [6] On the Connection Between MPNN and Graph Transformer. ICML'23

Questions

Please refer to the weaknesses.

Rating

6

Confidence

3

Soundness

2

Presentation

3

Contribution

3

Limitations

Yes. The authors describe the limited performances of the proposed method on certain datasets.