- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 1
Read review
Paper summary
This paper studies GNN invariance and equivariance under information-preserving graph transformations beyond standard graph isomorphism. The authors formalize these transformations using graph-pattern switchings and propose a general method to modify the structural bias of existing GNNs. Specifically, they introduce conditional graphs that separate the structural patterns used to identify relationships from the edges used for message passing, enabling different graph representations to induce equivalent computations.
The paper provides theoretical results concerning invariance, minimality, and expressivity of the modified architectures. Empirically, the authors evaluate their method on four graph datasets across seven GNN architectures, comparing against original models, data augmentation, and a universal-graph baseline. The results demonstrate exact invariance across the constructed graph variants, while predictive performance and computational overhead vary across tasks and architectures.
Critical strengths
- very dense theories and mathematically polished methods
- plug in tool with minimal modification to the GNN architecture
- method achieves invariance and equivariance which can be checked from the empirical check in table 1.
Critical weaknesses
- hard to follow: the paper is structured in a way that the reviewer struggles to follow. It is very hard to get information out of each paragraph and how it helps with the claims. I don't see any conclusion section after the experiment section.
- small scale empirical results: the paper runs on very small graph datasets (IMDb, DBLP, WN18RR, Freebase, Appendix H.1, node level less than 180,000 and edge number is on average less than 1M). I would expect similar results to be applied to, for example, Open Graph Benchmarks for larger graphs to see the effects of the method at larger scale, which would match the author's described "real-world" graphs.
- Potential issue with baseline: The largest accuracy improvement in Table 1 comes from CMPNN on WN18RR (+8.3 MRR points). However, Appendix Table 28 shows that Inv obtains exactly the same MRR as Orig on WN18RR1 (0.4238). The improvement comes entirely from the poor performance of Orig on WN18RR2 and WN18RR3. Orig to my understanding means the baseline GNN method, and WN18RR1 should be the unaugmented training dataset. In other words, if we simply do not augment the training dataset, the baseline GNN method is very close to the author's proposed method, which also achieves 0.4238 (Table 1).
The authors explain in Appendix H.5 that masking the training query does not remove its copies in the added relations, causing the original models to generalize worse. I am concerned that this comparison is affected by how the baseline handles these derived training edges. Would the reported improvement still hold if Orig correctly masked all copies of the training query...? If this is impossible, there seems to be unexplained benefits of augmenting a dataset to make the baseline worse. 4. Mariginal accuracy improvements: the authors claim the their method improves the accuracy of current GNNs on average. However, except the experiment result that the reviewer has pointed out on point 3 and DBLP dataset, there does not seem to be a convincing trends that the methods outperform the baseline, in Table 1. Most of the methods show little and even decreased accuracy compared with the baselines.
Questions for authors
- if possible, would you be able to scale your methods to larger graph datasets?
- if possible, could you explain the confounder in the model's accuracy improvement claim, i.e., the original graph dataset is augmented to make the baseline GNN methods perform worse?
- what should be the main theoretical results that an reviewer needs to pay the most attention to?
8 comments
W2 and Q1 (continued)
Models, and where the results are. We run the models of the paper on OGBN-MAG, except CMPNN, which we use for link prediction only: RGCN, SlotGAT, MAGNN, SeHGNN (with type-collapsed and with relation-aware channels), PAIN, and PathNet, i.e., seven models over six architectures, with the same protocol as on the other datasets. The dataset is described in Appendix H.1 (Table 6), the hyper-parameters in Appendix H.2 (Table 12), and the invariant structural bias of every architecture in Appendix H.3 (Tables 14, 15, and 18). Table R2 reports the results, Table R3 the degree of invariance, and Table R4 the cost of every method, condensed from the appendix. The full quantities are in Tables 19–21 (RGCN), 25–27 (SlotGAT), 34–36 (MAGNN), 40–42 (SeHGNN), 43–45 (PAIN), and 46–48 (PathNet), and the analysis is in Appendix H.5.
Results on OGBN-MAG (Table R2). The findings on the other datasets carry over to this scale. In (iii) and (iv), PAIN and PathNet are represented by Invariant Reduced; the two invariant versions are compared below. (i) The original GNNs depend on the representation. Their mean pairwise Kendall-τ across the variants ranges from 0.19 (SlotGAT) to 0.86 (MAGNN), and their Micro-F1 differs across the variants by up to 3.5 points (PAIN; 2.6 for SlotGAT and 2.1 for RGCN). Augmentation raises Kendall-τ to 0.63–0.98 but never reaches 1, and it is less accurate than the Original for every model. (ii) Our invariant versions are exactly invariant. For every model, Kendall-τ = 1, and the output probabilities are identical on every variant (maximum absolute difference 0). (iii) Invariance does not cost accuracy. For six of the seven models, the invariant version is more accurate than the Original's average over the variants, by 0.6 (MAGNN) to 2.5 (SlotGAT) Micro-F1 points, and at least as accurate as the Original on its best variant, within 0.2 points (Table 49 in Appendix H.5). The exception is PathNet, 0.2 points below the Original's average. For RGCN, SlotGAT, MAGNN, and SeHGNN, the invariant structural bias is the union of the variants' relations, so the invariant version and the Universal Graph train the same model; for PAIN, Invariant Reduced is also more accurate than the Universal Graph (see below). (iv) The cost remains moderate. The training time of the invariant version is 0.97 (SeHGNN) to 1.7 (MAGNN and PAIN) times that of the Original and 0.8 to 1.3 times that of the Universal Graph, and it is below Augmentation's for four of the seven models.
Table R2. OGBN-MAG venue classification results (condensed from Tables 19–21, 25–27, 34–36, 40–42, 43–45, and 46–48 of the revised submission). Micro-F1 (points), mean ± std over seeds, per variant; Mean and Macro-F1: mean over the variants. Three seeds unless marked ⁽ⁿ⁾ (number of seeds). Accuracy, precision, and recall are in the appendix tables.
| Model | Method | OGBN-MAG1 | OGBN-MAG2 | OGBN-MAG3 | Mean | Macro-F1 |
|---|---|---|---|---|---|---|
| RGCN | Original | 44.30 ± 0.08 | 45.46 ± 0.23 | 43.34 ± 0.18 | 44.37 | 25.33 |
| Augmentation | 41.59 ± 0.57 | 41.70 ± 0.62 | 42.20 ± 0.41 | 41.83 | 25.18 | |
| Universal Graph | 45.55 ± 0.09 (one model) | 45.55 | 26.59 | |||
| Invariant | 45.55 ± 0.09 | 45.55 ± 0.09 | 45.55 ± 0.09 | 45.55 | 26.59 | |
| SlotGAT | Original | 36.79 ± 0.27 | 37.03 ± 0.19 | 39.40 ± 0.29 | 37.74 | 11.82 |
| Augmentation | 34.28 ± 0.72 | 34.44 ± 1.09 | 37.52 ± 0.38 | 35.41 | 11.99 | |
| Universal Graph | 40.21 ± 0.46 (one model) | 40.21 | 13.42 | |||
| Invariant | 40.21 ± 0.46 | 40.21 ± 0.46 | 40.21 ± 0.46 | 40.21 | 13.42 | |
| MAGNN | Original | 27.86 ± 0.30 | 28.70 ± 0.78 | 28.34 ± 0.27 | 28.30 | 5.05 |
| Augmentation | 27.39 ± 1.87 | 27.37 ± 1.88 | 27.71 ± 1.67 | 27.49 | 4.91 | |
| Universal Graph | 28.94 ± 0.70 (one model) | 28.94 | 5.06 | |||
| Invariant + Union | 28.94 ± 0.70 | 28.94 ± 0.70 | 28.94 ± 0.70 | 28.94 | 5.06 | |
| SeHGNN | Original (type-collapsed) | 41.31 ± 0.13 | 43.20 ± 0.06 | 41.53 ± 0.12 | 42.01 | 23.01 |
| Augmentation (type-collapsed) | 39.09 ± 0.52 | 39.28 ± 0.51 | 40.90 ± 0.42 | 39.76 | 21.40 | |
| Universal Graph (type-collapsed) | 43.11 ± 0.27 (one model) | 43.11 | 23.68 | |||
| Invariant (type-collapsed) | 43.11 ± 0.27 | 43.11 ± 0.27 | 43.11 ± 0.27 | 43.11 | 23.68 | |
| Original (relation-aware) | 39.20 ± 0.15 | 40.95 ± 0.07 | 39.05 ± 0.17 | 39.73 | 21.59 | |
| Augmentation (relation-aware) | 38.14 ± 0.51 | 38.74 ± 0.53 | 39.04 ± 0.25 | 38.64 | 21.54 | |
| Universal Graph (relation-aware) | 40.79 ± 0.33 (one model) | 40.79 | 22.08 | |||
| Invariant (relation-aware) | 40.79 ± 0.33 | 40.79 ± 0.33 | 40.79 ± 0.33 | 40.79 | 22.08 |
W2 and Q1 (continued)
Table R2 (continued).
| Model | Method | OGBN-MAG1 | OGBN-MAG2 | OGBN-MAG3 | Mean | Macro-F1 |
|---|---|---|---|---|---|---|
| PAIN | Original | 23.49 ± 1.14 | 25.81 ± 0.15 | 27.02 ± 2.60 | 25.44 | 4.62 |
| Augmentation | 23.07 ± 1.46 | 23.06 ± 1.28 | 22.85 ± 0.86 | 22.99 | 2.72 | |
| Universal Graph | 24.93 ± 1.07 (one model) | 24.93 | 3.73 | |||
| Invariant | 24.93 ± 1.07 | 23.44 ± 0.00⁽¹⁾ | 23.44 ± 0.00⁽¹⁾ | 23.94⁽¹⁾ | 2.93⁽¹⁾ | |
| Invariant Reduced | 27.68 ± 0.30⁽²⁾ | 27.68 ± 0.30⁽²⁾ | 27.38 ± 0.00⁽¹⁾ | 27.58⁽¹⁾ | 5.43⁽¹⁾ | |
| PathNet | Original | 27.30 ± 0.00⁽¹⁾ | 27.33 ± 0.00⁽¹⁾ | 27.82 ± 0.00⁽¹⁾ | 27.48⁽¹⁾ | 4.59⁽¹⁾ |
| Augmentation | 26.14 ± 0.00⁽¹⁾ | 26.13 ± 0.00⁽¹⁾ | 26.31 ± 0.00⁽¹⁾ | 26.19⁽¹⁾ | 3.84⁽¹⁾ | |
| Universal Graph | 27.13 ± 0.00⁽¹⁾ (one model) | 27.13 | 4.98 | |||
| Invariant | 27.13 ± 0.00⁽¹⁾ | 27.13 ± 0.00⁽¹⁾ | 27.13 ± 0.00⁽¹⁾ | 27.13⁽¹⁾ | 4.98⁽¹⁾ | |
| Invariant Reduced | 27.26 ± 0.00⁽¹⁾ | 27.26 ± 0.00⁽¹⁾ | 27.26 ± 0.00⁽¹⁾ | 27.26⁽¹⁾ | 4.98⁽¹⁾ |
Table R3. OGBN-MAG degree of invariance (condensed from the same appendix tables). Kendall-τ per pair of variants, and the maximum and mean absolute difference of the output probabilities, averaged over the three pairs; over the seeds that both variants have (⁽ⁿ⁾: n seeds). The Universal Graph maps every variant to one graph, so its invariance is trivial (omitted).
| Model | Method | τ, 1 vs 2 | τ, 1 vs 3 | τ, 2 vs 3 | Max abs. Δp | Mean abs. Δp |
|---|---|---|---|---|---|---|
| RGCN | Original | 0.663 | 0.667 | 0.598 | 0.946 | 0.0018 |
| Augmentation | 0.948 | 0.793 | 0.786 | 0.862 | 0.0008 | |
| Invariant | 1.000 | 1.000 | 1.000 | 0.000 | 0.0000 | |
| SlotGAT | Original | 0.248 | 0.169 | 0.160 | 0.005 | 0.0001 |
| Augmentation | 0.775 | 0.583 | 0.540 | 0.004 | 0.0000 | |
| Invariant | 1.000 | 1.000 | 1.000 | 0.000 | 0.0000 | |
| MAGNN | Original | 0.845 | 0.851 | 0.890 | 0.476 | 0.0007 |
| Augmentation | 0.991 | 0.979 | 0.973 | 0.192 | 0.0003 | |
| Invariant + Union | 1.000 | 1.000 | 1.000 | 0.000 | 0.0000 | |
| SeHGNN | Original (type-collapsed) | 0.555 | 0.573 | 0.545 | 0.987 | 0.0011 |
| Augmentation (type-collapsed) | 0.936 | 0.789 | 0.801 | 0.893 | 0.0007 | |
| Invariant (type-collapsed) | 1.000 | 1.000 | 1.000 | 0.000 | 0.0000 | |
| Original (relation-aware) | 0.539 | 0.569 | 0.543 | 0.990 | 0.0012 | |
| Augmentation (relation-aware) | 0.932 | 0.772 | 0.762 | 0.932 | 0.0007 | |
| Invariant (relation-aware) | 1.000 | 1.000 | 1.000 | 0.000 | 0.0000 | |
| PAIN | Original | 0.701 | 0.644 | 0.690 | 0.840 | 0.0021 |
| Augmentation | 0.926 | 0.837 | 0.838 | 0.481 | 0.0011 | |
| Invariant | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 0.000 | 0.0000 | |
| Invariant Reduced | 1.000⁽²⁾ | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 0.000 | 0.0000 | |
| PathNet | Original | 0.816⁽¹⁾ | 0.818⁽¹⁾ | 0.822⁽¹⁾ | 0.786 | 0.0013 |
| Augmentation | 0.989⁽¹⁾ | 0.906⁽¹⁾ | 0.905⁽¹⁾ | 0.494 | 0.0006 | |
| Invariant | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 0.000 | 0.0000 | |
| Invariant Reduced | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 1.000⁽¹⁾ | 0.000 | 0.0000 |
Table R4. OGBN-MAG cost (condensed from the same appendix tables). Training time in minutes and preprocessing time and peak RAM of building the model's input (Appendix H.4), means over the variants (Augmentation and Universal Graph: one model). ⁽ⁿ⁾: fewest seeds of a variant.
| Model | Method | Training (min) | Preprocessing (s) | Preprocessing RAM (GiB) |
|---|---|---|---|---|
| RGCN | Original | 15.6 | 33.5 | 3.61 |
| Augmentation | 35.6 | 106.9 | 8.01 | |
| Universal Graph | 18.9 | 76.2 | 6.86 | |
| Invariant | 19.8 | 173.5 | 7.04 | |
| SlotGAT | Original | 373.5 | 33.5 | 4.37 |
| Augmentation | 981.8 | 107.2 | 8.05 | |
| Universal Graph | 441.1 | 59.2 | 6.89 | |
| Invariant | 441.2 | 166.7 | 7.08 | |
| MAGNN | Original | 139.9 | 1,043.5 | 53.87 |
| Augmentation | 158.4 | 3,130.4 | 56.25 | |
| Universal Graph | 249.9 | 2,376.0 | 63.13 | |
| Invariant + Union | 236.2 | 2,021.4 | 56.67 | |
| SeHGNN | Original (type-collapsed) | 32.9 | 173.4 | 30.26 |
| Augmentation (type-collapsed) | 53.4 | 399.9 | 38.15 | |
| Universal Graph (type-collapsed) | 32.5 | 207.3 | 34.14 | |
| Invariant (type-collapsed) | 32.0 | 262.3 | 34.17 | |
| Original (relation-aware) | 34.7 | 245.1 | 32.29 | |
| Augmentation (relation-aware) | 113.8 | 645.0 | 45.20 | |
| Universal Graph (relation-aware) | 38.6 | 252.0 | 36.37 | |
| Invariant (relation-aware) | 38.4 | 332.2 | 32.80 | |
| PAIN | Original | 377.4 | 238.5 | 15.19 |
| Augmentation | 365.0 | 715.5 | 23.36 | |
| Universal Graph | 790.4 | 483.0 | 29.56 | |
| Invariant | 764.9⁽¹⁾ | 391.6 | 29.60 | |
| Invariant Reduced | 631.6⁽¹⁾ | 418.3 | 25.85 |
W1
We have followed the reviewer's comment and rewritten revised submission to make the paper easier to follow. In particular, we have revised Section 2 to clarify the group structure of mappings, Section 4 to justify and elaborate on the details of our methods, and explained in further details the empirical study given the available space. We have also added a conclusion in the revised submission as follows:
The same information can be represented in various non-isomorphic graphs. Since current GNN architectures rely heavily on the topology of the input graphs to learn representations, they return different representations and consequently prediction results over representations of the same information. We formalize these variations of graphs as a group of mappings. We design an efficient approach to partially modify the inductive bias of a GNN architecture to make it invariant to an input group of mappings without transforming the input graph or changing the internal details of the GNN architecture. Thus, our approach can be used on a wide variety of GNN architectures. Our experiments on seven GNN architectures and five datasets show that our approach achieves exact invariance with robust accuracy for the published models usually at little extra cost.
W2 and Q1
A larger dataset: OGBN-MAG. We have followed the reviewer's comment and added OGBN-MAG from the Open Graph Benchmark to the revised submission. The task is venue classification of papers (349 classes) under the time split of the benchmark. Each variant has 15.5–23.1 million nodes and 42.2–100.1 million edges (Table R1), i.e., 86 to 128 times as many nodes as Freebase, the largest graph of the original submission (180,098 nodes).
Table R1. OGBN-MAG variants (Table 6 of the revised submission). The released graph has 736,389 papers, 1,134,649 authors, 8,740 institutions, and 59,965 fields of study; reified nodes: 5,416,271 citation, 7,145,660 authorship, 1,043,998 affiliation, and 7,505,078 topic-assignment nodes. Venue classification, 349 classes, time split 629,571 / 64,879 / 41,939 papers. Edges are directed; a reified node contributes one edge to each endpoint.
Why the variants reify edges. We build the variants by reifying edges, i.e., by representing an edge between two nodes by a node connected to both. Reification is needed because our framework is defined on graphs whose nodes carry labels and features and whose edges carry neither (Section 2): an edge is a pair of nodes, and a relation is identified only by the labels of its endpoints. A switching therefore rewrites patterns of labelled nodes and can move information only from one node to another. In the released OGBN-MAG, the information that a re-encoding moves, such as the institutions of an author or the fields of study of a paper, would have to be attached to the author–paper relation, i.e., to an edge, which our graphs cannot represent. Reifying the relations turns their edges into labelled nodes (citation, authorship, affiliation, and topic-assignment nodes), so that the re-encodings become switchings between patterns of labelled nodes; the authorship node plays the role of the link node of IMDb. OGBN-MAG1 reifies all four relations of the released graph. OGBN-MAG2 replaces the affiliation nodes by attaching the institutions of each author to every authorship node of that author, and OGBN-MAG3 replaces the topic-assignment nodes by attaching the fields of study of each paper to every authorship node of that paper. The mapping therefore has two switchings. Both are exact: a reified node has exactly one endpoint on each side, so it contracts back to its edge, and every variant reproduces the four relations of the released graph exactly (Appendix H.1).