- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes a computationally efficient graph classification framework that combines the multi-order actor representations, singular pooling and subgraph training. It argues that the theoretical conditions for sampling to preserve the propagated feature Gram matrices and the generalization and prediction stability guarantees for graph representations. Furthermore, substantial reduction of the training time demonstrated in real world datasets.
Critical strengths
The paper addresses the practical challenge of reducing the training cost of GNN through the subgraph sampling while retaining the useful graph information. This is interesting since the higher order neighborhood aggregation can increase computational cost in large graphs.
In Theorem 3.2, the authors shows theoretical guarantees connecting Gram-matrix preservation to singular-pooling representation stability and consistent classification predictions under certain conditions. This helps explain how subgraph sampling affects the model's predictions.
The paper proves the conditional generalization guarantees for subgraph trained models and actor level stability bounds under feature perturbations. These findings support the theoretical analysis characterize the generalization for unseen full graphs and identifying conditions under which singular-pooling representations remain stable.
Critical weaknesses
In Theorem 3.1 qd_min≥12 log(2m/η_d ) requires a sufficiently large minimum sampled degree. How applicable is this condition to real-world sparse graphs, and can the theoretical analysis be extended to graphs with low-degree nodes.
Theorem 3.3 establishes an O(n^(-1/2)) generalization rate by assuming that several error terms already decrease at this rate (G2-G4). However, the sampling discrepancy is not guaranteed to decrease with the number of training graphs at a fixed sampling ratio it is unclear whether these assumptions hold for the proposed SMaRS-GNN architecture and training procedure.
Empirical experiments accuracies of SMaRS_GNN for all the datasets do not outperform the MaRS baseline models like RS_GCN event if it achieves a reduction of training time. Therefore, the practical value of the computational cost reduction become less meaningful when the prediction accuracy declines considerably.
Experiments are conducted only on three real world datasets (Reddit-B, D&D, and PROTEINS), and D&D and PROTEINS contain protein-structure graphs. This make limited the diversity of the datasets and difficult to asses the generalizability and other measures claimed by the authors. More diverse graph classification datasets may strengthen the authors claims.
Questions for authors
Theorem 3.2 states the accuracy guarantee for the sampled and full graph with a fitted classifier. However, the experiments compare separately trained models. It is less clear how does this relate to the performance of the models trained on sampled subgraphs versus full graphs? For Other questions please see Weaknesses