acceptodds
Under review as a conference paper at ICLR 2027

Information-based Invariance, Equivariance, and Expressivity for Graph Neural Networks

Abstract

Graph Neural Networks (GNNs) leverage the topology of graphs to learn informative representations. It is known that the same information is often represented in nonisomorphic forms. In this paper, we postulate that GNNs should be invariant/equivariant and expressive with respect to these variations. We introduce the notions of invariance/equivariance of GNNs with respect to these variations and prove that current GNN architectures are not invariant/equivariant to these variations. We propose a general approach to modify a GNN to make it invariant/equivariant to these variations. We also generalize the current notion of expressivity to consider these variations and investigate the expressivity of the invariant/equivariant GNNs. Our empirical studies using multiple GNN architectures over real-world graphs indicate that our approach achieves perfect invariance/equivariance and improves the accuracy of current GNNs on average without imposing significant time overhead.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Representation invariance, Equivariance, Information-preserving transformations, Graph neural networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_kEhvOpenReview ↗
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
  1. very dense theories and mathematically polished methods
  2. plug in tool with minimal modification to the GNN architecture
  3. method achieves invariance and equivariance which can be checked from the empirical check in table 1.
Critical weaknesses
  1. 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.
  2. 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.
  3. 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
  1. if possible, would you be able to scale your methods to larger graph datasets?
  2. 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?
  3. what should be the main theoretical results that an reviewer needs to pay the most attention to?
8 comments

W1

hard to follow: the paper is structured in a way that the reviewer struggles to follow.

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

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).

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.

VariantTypes / relationsNodesEdgesReplaced reified node type (added edges)
OGBN-MAG18 / 823,050,75042,222,014– (all four relations reified)
OGBN-MAG27 / 722,006,75253,569,211affiliation authorship–institution (13,435,193)
OGBN-MAG37 / 715,545,672100,060,753topic assignment authorship–field of study (72,848,895)
∪_i OGBN-MAG_i8 / 1023,050,750128,506,102both

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).

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.

ModelMethodOGBN-MAG1OGBN-MAG2OGBN-MAG3MeanMacro-F1
RGCNOriginal44.30 ± 0.0845.46 ± 0.2343.34 ± 0.1844.3725.33
Augmentation41.59 ± 0.5741.70 ± 0.6242.20 ± 0.4141.8325.18
Universal Graph45.55 ± 0.09 (one model)45.5526.59
Invariant45.55 ± 0.0945.55 ± 0.0945.55 ± 0.0945.5526.59
SlotGATOriginal36.79 ± 0.2737.03 ± 0.1939.40 ± 0.2937.7411.82
Augmentation34.28 ± 0.7234.44 ± 1.0937.52 ± 0.3835.4111.99
Universal Graph40.21 ± 0.46 (one model)40.2113.42
Invariant40.21 ± 0.4640.21 ± 0.4640.21 ± 0.4640.2113.42
MAGNNOriginal27.86 ± 0.3028.70 ± 0.7828.34 ± 0.2728.305.05
Augmentation27.39 ± 1.8727.37 ± 1.8827.71 ± 1.6727.494.91
Universal Graph28.94 ± 0.70 (one model)28.945.06
Invariant + Union28.94 ± 0.7028.94 ± 0.7028.94 ± 0.7028.945.06
SeHGNNOriginal (type-collapsed)41.31 ± 0.1343.20 ± 0.0641.53 ± 0.1242.0123.01
Augmentation (type-collapsed)39.09 ± 0.5239.28 ± 0.5140.90 ± 0.4239.7621.40
Universal Graph (type-collapsed)43.11 ± 0.27 (one model)43.1123.68
Invariant (type-collapsed)43.11 ± 0.2743.11 ± 0.2743.11 ± 0.2743.1123.68
Original (relation-aware)39.20 ± 0.1540.95 ± 0.0739.05 ± 0.1739.7321.59
Augmentation (relation-aware)38.14 ± 0.5138.74 ± 0.5339.04 ± 0.2538.6421.54
Universal Graph (relation-aware)40.79 ± 0.33 (one model)40.7922.08
Invariant (relation-aware)40.79 ± 0.3340.79 ± 0.3340.79 ± 0.3340.7922.08

W2 and Q1 (continued)

Table R2 (continued).

ModelMethodOGBN-MAG1OGBN-MAG2OGBN-MAG3MeanMacro-F1
PAINOriginal23.49 ± 1.1425.81 ± 0.1527.02 ± 2.6025.444.62
Augmentation23.07 ± 1.4623.06 ± 1.2822.85 ± 0.8622.992.72
Universal Graph24.93 ± 1.07 (one model)24.933.73
Invariant24.93 ± 1.0723.44 ± 0.00⁽¹⁾23.44 ± 0.00⁽¹⁾23.94⁽¹⁾2.93⁽¹⁾
Invariant Reduced27.68 ± 0.30⁽²⁾27.68 ± 0.30⁽²⁾27.38 ± 0.00⁽¹⁾27.58⁽¹⁾5.43⁽¹⁾
PathNetOriginal27.30 ± 0.00⁽¹⁾27.33 ± 0.00⁽¹⁾27.82 ± 0.00⁽¹⁾27.48⁽¹⁾4.59⁽¹⁾
Augmentation26.14 ± 0.00⁽¹⁾26.13 ± 0.00⁽¹⁾26.31 ± 0.00⁽¹⁾26.19⁽¹⁾3.84⁽¹⁾
Universal Graph27.13 ± 0.00⁽¹⁾ (one model)27.134.98
Invariant27.13 ± 0.00⁽¹⁾27.13 ± 0.00⁽¹⁾27.13 ± 0.00⁽¹⁾27.13⁽¹⁾4.98⁽¹⁾
Invariant Reduced27.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).

ModelMethodτ, 1 vs 2τ, 1 vs 3τ, 2 vs 3Max abs. ΔpMean abs. Δp
RGCNOriginal0.6630.6670.5980.9460.0018
Augmentation0.9480.7930.7860.8620.0008
Invariant1.0001.0001.0000.0000.0000
SlotGATOriginal0.2480.1690.1600.0050.0001
Augmentation0.7750.5830.5400.0040.0000
Invariant1.0001.0001.0000.0000.0000
MAGNNOriginal0.8450.8510.8900.4760.0007
Augmentation0.9910.9790.9730.1920.0003
Invariant + Union1.0001.0001.0000.0000.0000
SeHGNNOriginal (type-collapsed)0.5550.5730.5450.9870.0011
Augmentation (type-collapsed)0.9360.7890.8010.8930.0007
Invariant (type-collapsed)1.0001.0001.0000.0000.0000
Original (relation-aware)0.5390.5690.5430.9900.0012
Augmentation (relation-aware)0.9320.7720.7620.9320.0007
Invariant (relation-aware)1.0001.0001.0000.0000.0000
PAINOriginal0.7010.6440.6900.8400.0021
Augmentation0.9260.8370.8380.4810.0011
Invariant1.000⁽¹⁾1.000⁽¹⁾1.000⁽¹⁾0.0000.0000
Invariant Reduced1.000⁽²⁾1.000⁽¹⁾1.000⁽¹⁾0.0000.0000
PathNetOriginal0.816⁽¹⁾0.818⁽¹⁾0.822⁽¹⁾0.7860.0013
Augmentation0.989⁽¹⁾0.906⁽¹⁾0.905⁽¹⁾0.4940.0006
Invariant1.000⁽¹⁾1.000⁽¹⁾1.000⁽¹⁾0.0000.0000
Invariant Reduced1.000⁽¹⁾1.000⁽¹⁾1.000⁽¹⁾0.0000.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.

ModelMethodTraining (min)Preprocessing (s)Preprocessing RAM (GiB)
RGCNOriginal15.633.53.61
Augmentation35.6106.98.01
Universal Graph18.976.26.86
Invariant19.8173.57.04
SlotGATOriginal373.533.54.37
Augmentation981.8107.28.05
Universal Graph441.159.26.89
Invariant441.2166.77.08
MAGNNOriginal139.91,043.553.87
Augmentation158.43,130.456.25
Universal Graph249.92,376.063.13
Invariant + Union236.22,021.456.67
SeHGNNOriginal (type-collapsed)32.9173.430.26
Augmentation (type-collapsed)53.4399.938.15
Universal Graph (type-collapsed)32.5207.334.14
Invariant (type-collapsed)32.0262.334.17
Original (relation-aware)34.7245.132.29
Augmentation (relation-aware)113.8645.045.20
Universal Graph (relation-aware)38.6252.036.37
Invariant (relation-aware)38.4332.232.80
PAINOriginal377.4238.515.19
Augmentation365.0715.523.36
Universal Graph790.4483.029.56
Invariant764.9⁽¹⁾391.629.60
Invariant Reduced631.6⁽¹⁾418.325.85
Reviewer_bAymOpenReview ↗
Rating
2(−1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the invariance, equivariance, and expressivity of graph neural networks (GNNs) with respect to information-based equivalences, where non-isomorphic graphs may represent the same information. The authors introduce bijective graph mappings to characterize such equivalences and show that existing GNN architectures are not necessarily invariant or equivariant to these mappings. To address this issue, the authors propose a general approach to modifying the structural bias of existing GNNs using conditional graphs.

Critical strengths
  1. The paper considers information-based equivalences beyond conventional graph isomorphism. This is a meaningful problem, as the same underlying information can be represented by different graph structures in applications such as knowledge graphs and biological networks. Investigating the behavior of GNNs under such transformations is potentially valuable.
  2. The paper introduces information-based equivalences using bijective graph mappings and focuses on mappings that can be represented by switching operations. It further extends the notions of invariance, equivariance, and expressivity to these equivalences, providing a theoretical framework for analyzing GNNs beyond conventional graph isomorphism.
  3. The paper provides theoretical results concerning the invariance of the modified GNNs, the minimality of the constructed structural biases, and the preservation of expressivity under the stated assumptions. These results provide theoretical support for the proposed approach.
Critical weaknesses
  1. The advantages of the proposed conditional-graph approach over alternative methods are not sufficiently clear. The proposed method assumes that information-preserving mappings are already given. Given these mappings, it is unclear why modifying the structural bias of existing GNNs is preferable to directly transforming equivalent graphs into a common representation. Although the paper includes a universal-graph baseline and reports comparisons in predictive performance and training time, the preprocessing costs of constructing the invariant structural biases and the universal graph are not systematically evaluated. A more comprehensive comparison of the overall computational overhead would help clarify the practical advantages of the proposed approach.

  2. The method relies on predefined information-preserving mappings. The proposed construction requires information-preserving mappings to be specified in advance. However, identifying such mappings may require domain knowledge and may not be straightforward for graphs with complex structures. Although the paper mentions existing methods for inferring mappings, it remains unclear how easily the proposed approach can be applied to new datasets where these mappings are not readily available. This dependence may limit the practical applicability of the method.

  3. The practical implications of the minimality guarantee are unclear. Proposition 6 establishes the minimality of the constructed structural bias under a specific partial order. However, this notion of minimality does not necessarily imply minimal computational cost or the smallest number of conditional graphs and propagation edges. It would be helpful to clarify how the theoretical minimality guarantee relates to the actual efficiency of the proposed method.

Questions for authors
  1. Given that the information-preserving mappings are assumed to be known, could the authors further clarify the advantages of modifying GNN structural biases over directly transforming equivalent graphs into a common representation? In particular, how do the preprocessing costs of the proposed method compare with those of the universal-graph approach?

  2. Could the authors clarify whether the information propagation patterns induced by conditional graphs can be implemented through graph rewiring or virtual-edge augmentation using the same mappings? If so, what additional benefits does the conditional-graph framework provide?

  3. How are the information-preserving mappings obtained for the datasets used in the experiments? How would the proposed method be applied to datasets where such mappings are not readily available or are only partially known?

  4. Could the authors clarify how the theoretical minimality and expressivity guarantees relate to practical GNN implementations? In particular, how does the minimality of the structural bias relate to computational efficiency,?

7 comments

W1 and Q1

The advantages of the proposed conditional-graph approach over alternative methods are not sufficiently clear.

We do not assume that all mappings are given. Please see our responses to W2 and Q3.

It is often too time- and resource-intensive to create and maintain a universal graph (common representation). First, to create a common representation for an input graph G given a group of mappings, we must first create each variation, which requires finding homomorphism mappings from the switchings in the group to the graph. Finding these matches is subgraph homomorphism, which is NP-hard in general, and it must be repeated over the whole graph for every mapping in the group. We then must compute the union of these variations and eliminate redundant edges. On our datasets, whose switchings are small, building the universal graph takes 3–314 seconds, but its cost grows with the size of the graph, whereas our algorithm (Section 4.3) runs only on the structural bias, whose size does not depend on the graph. Our models also find the occurrences of their conditional graphs in the graph, but only those of the structural bias, and this cost is included in Table R1. Our approach therefore avoids building and storing the universal graph. The model's own preprocessing is then no slower than for the Universal Graph in 16 of the 23 rows of Table R1 that use the versions of Table 1 (details under Preprocessing cost below). In addition, the process of preparing a universal representation must be repeated when the underlying graph evolves. With our approach, only the stored graph is updated, whereas the universal graph must also re-materialize every encoding of the changed part and keep these copies consistent.

Second, since the universal representation can be considerably larger than the original graph (on Freebase, 493 million edges, 466 times as many as the released graph; Appendix H.1, Table 5), it takes a significant amount of storage and time to pre-process it for training, e.g., up to 11 times the memory of our approach for some datasets (RGCN on Freebase; Table R1).

Two invariant versions for CMPNN, PAIN, and PathNet. The revised submission reports two invariant structural biases for the three architectures that read the graph along paths or walks: CMPNN, PAIN, and PathNet (Appendix H.3). The Invariant contains every semantic relation that the mapping relates, as for the other architectures. Invariant Reduced omits the semantic relations that the model's paths or walks already reach through the remaining ones; e.g., a shortcut relation of WN18RR or Freebase composes base relations that the paths traverse anyway. Both are compiled identically from every variant, so both are exactly invariant; they differ only in what the model aggregates or samples, and therefore in accuracy and cost. Table 1 reports Invariant Reduced for all three models in every cell, as a fixed rule rather than a choice per cell; averaged over the variants and seeds, its validation score is at least that of the Invariant in every cell except PAIN on IMDb, where it is 0.08 points lower. For MAGNN, Table 1 uses the Union metapaths, which contain every metapath of every variant.

Preprocessing cost (Table R1). Table R1 reports the preprocessing cost of every method, measured once per method and variant on CPU (Appendix H.4). Preprocessing builds the input that a model reads before training: the typed edges (RGCN), the metapath instances (MAGNN), the feature channels (SeHGNN), the rooted paths (PAIN), and the message graphs and walk graphs that CMPNN, SlotGAT, and PathNet build at the start of training. For the Original and the Universal Graph, this input is built from the stored graph; for the invariant version, it is built from the compiled structural bias of the variant at hand. Building the universal graph itself, which needs every variant, is not included in Table R1 (Freebase: 314 seconds; WN18RR: 14; IMDb: 3–9; DBLP: 5). On IMDb and DBLP, every method preprocesses its input in seconds and with about 1 GiB of memory. On Freebase, the Universal Graph is usually the most expensive input to build. For RGCN, it takes 1,274 seconds and 48.4 GiB, against 517 seconds and 4.2 GiB for the invariant version, i.e., 11 times the memory. For MAGNN, it takes 571 against 284 seconds; for SeHGNN, 562 against 439 seconds (908 against 797 for SeHGNN + relation-aware); and for PathNet, 1,973 seconds against 6 for Invariant Reduced. Conversely, the invariant version is more expensive to preprocess where its bias is compiled from each variant while the Universal Graph reads a stored graph, e.g., RGCN on WN18RR (64 against 1 second).

W1 and Q1 (continued)

Training cost (Table R1). Training time, in contrast, is comparable (Table R1, last three columns; Appendix H.5, Table 50). Where the invariant structural bias is the union of the variants' biases (all four models on DBLP, SlotGAT on Freebase, and Invariant Reduced of CMPNN, PAIN, and PathNet on IMDb), the invariant version and the Universal Graph train the same model. Elsewhere, the invariant version is faster in some cells and slower in others: CMPNN on WN18RR trains in 828 minutes with the Invariant and 163 with Invariant Reduced, against 991 for the Universal Graph, and SeHGNN on IMDb-NC in 1.07 against 3.50 minutes, whereas MAGNN with the Union metapaths on Freebase takes 86 against 29 minutes. The main difference lies in what each approach requires. The universal graph must be built from every variant before training, and every input, including a graph the model has not seen, must first be rewritten into the universal graph by applying every switching occurrence by occurrence (Appendix H.8). The invariant version is trained on the variant at hand, and it gives bitwise identical outputs, without retraining, on variants it has never seen (Appendix H.8).

Table R1. Preprocessing (wall time and peak RAM, measured once on CPU) and training time (mean over variants ± seed std) of Orig, Univ, and Inv. Univ excludes building the universal graph itself (Freebase: 314 s; WN18RR: 14 s for all four graphs; IMDb: 3–9 s; DBLP: 5 s). Each model's own preprocessing only: models that read RGCN's stores (CMPNN, SlotGAT on LP, PathNet) exclude RGCN's build (see the RGCN rows); PathNet's is its walk build, including its two-hop index. †^\daggerOne model, trained and measured on WN18RR1; its compiled input is identical on every variant. Preprocessing (first table) and training time (second table).

TaskModelTime (s): Orig / Univ / InvRAM (GiB): Orig / Univ / Inv
IMDb-NCRGCN3.18 / 3.31 / 4.991.13 / 1.14 / 1.16
SlotGAT13.89 / 12.88 / 11.821.44 / 1.39 / 1.45
MAGNN (Union)6.80 / 5.80 / 6.060.89 / 0.89 / 0.93
SeHGNN10.90 / 25.51 / 15.291.15 / 1.25 / 1.13
PAIN (Inv)40.70 / 85.31 / 222.641.76 / 2.19 / 6.06
PAIN (Inv Reduced)40.70 / 85.31 / 79.961.76 / 2.19 / 2.57
PathNet (Inv)1.96 / 2.83 / 2.650.80 / 0.81 / 0.81
PathNet (Inv Reduced)1.96 / 2.83 / 2.500.80 / 0.81 / 0.81
Freebase-NCRGCN448.83 / 1,274.40 / 516.8943.29 / 48.43 / 4.22
SlotGAT3,212.83 / 9,499.33 / 9,499.339.25 / 9.77 / 9.77
MAGNN (Union)184.65 / 570.58 / 283.5416.57 / 17.88 / 16.57
SeHGNN193.53 / 561.71 / 439.4916.58 / 17.88 / 16.83
SeHGNN + relation-aware276.56 / 907.89 / 796.8016.57 / 17.88 / 16.57
PAIN (Inv)1,789.35 / 5,199.82 / 5,277.133.82 / 3.92 / 3.17
PAIN (Inv Reduced)1,789.35 / 5,199.82 / 427.623.82 / 3.92 / 2.86
PathNet (Inv)693.78 / 1,972.79 / 1,999.2653.58 / 53.61 / 53.61
PathNet (Inv Reduced)693.78 / 1,972.79 / 6.1553.58 / 53.61 / 1.02
IMDb-LPRGCN3.99 / 4.12 / 6.441.13 / 1.14 / 1.16
SlotGAT3.72 / 3.90 / 3.850.70 / 0.71 / 0.72
MAGNN (Union)5.56 / 5.69 / 6.160.89 / 0.89 / 0.93
CMPNN (Inv)8.02 / 5.81 / 4.520.76 / 0.77 / 0.76
CMPNN (Inv Reduced)8.02 / 5.81 / 4.480.76 / 0.77 / 0.76
DBLP-LPRGCN2.07 / 2.12 / 5.380.56 / 0.56 / 0.54
SlotGAT4.88 / 5.00 / 4.930.49 / 0.50 / 0.50
MAGNN (Union)12.52 / 19.55 / 19.531.40 / 1.40 / 1.41
CMPNN (Inv = Inv Reduced)5.15 / 5.48 / 5.340.50 / 0.49 / 0.50
WN18RR-LPRGCN0.45 / 1.07 / 64.180.53 / 0.55 / 0.62
SlotGAT5.57 / 7.30 / 7.630.70 / 0.76 / 0.75
CMPNN (Inv)15.40 / 43.62 / 44.470.94 / 0.97 / 0.74
CMPNN (Inv Reduced)15.40 / 43.62 / 8.920.94 / 0.97 / 0.96

Training time (min, mean over variants ± seed std):

TaskModelOrigUnivInv
IMDb-NCRGCN0.74 ± 0.070.70 ± 0.020.70 ± 0.00
SlotGAT0.66 ± 0.090.90 ± 0.070.89 ± 0.03
MAGNN (Union)2.68 ± 0.294.04 ± 0.444.34 ± 0.73
SeHGNN1.41 ± 0.153.50 ± 0.301.07 ± 0.03
PAIN (Inv)28.57 ± 3.2748.97 ± 9.56185.47 ± 17.58
PAIN (Inv Reduced)28.57 ± 3.2748.97 ± 9.5648.65 ± 9.04
PathNet (Inv)5.45 ± 0.025.62 ± 0.015.72 ± 0.02
PathNet (Inv Reduced)5.45 ± 0.025.62 ± 0.015.61 ± 0.01

W1 and Q1 (continued)

Table R1 (continued).

TaskModelOrigUnivInv
Freebase-NCRGCN11.65 ± 1.8220.42 ± 3.4825.35 ± 5.32
SlotGAT266.41 ± 99.79606.09 ± 119.82606.82 ± 120.75
MAGNN (Union)20.69 ± 4.2428.95 ± 6.5186.25 ± 24.96
SeHGNN1.19 ± 0.031.23 ± 0.031.23 ± 0.02
SeHGNN + relation-aware3.23 ± 0.456.17 ± 0.515.21 ± 0.23
PAIN (Inv)127.52 ± 16.72131.16 ± 19.18103.63 ± 21.06
PAIN (Inv Reduced)127.52 ± 16.72131.16 ± 19.18162.72 ± 21.27
PathNet (Inv)32.86 ± 0.7643.53 ± 0.8742.81 ± 0.35
PathNet (Inv Reduced)32.86 ± 0.7643.53 ± 0.8723.42 ± 0.12
IMDb-LPRGCN3.69 ± 0.393.49 ± 0.153.72 ± 0.50
SlotGAT0.62 ± 0.141.08 ± 0.330.91 ± 0.11
MAGNN (Union)14.91 ± 2.0222.53 ± 6.3916.54 ± 0.65
CMPNN (Inv)12.19 ± 2.4213.54 ± 4.2412.72 ± 4.05
CMPNN (Inv Reduced)12.19 ± 2.4213.54 ± 4.2413.53 ± 4.27
DBLP-LPRGCN0.79 ± 0.020.92 ± 0.010.93 ± 0.01
SlotGAT2.79 ± 0.492.49 ± 0.052.62 ± 0.21
MAGNN (Union)90.57 ± 26.44110.65 ± 33.52111.48 ± 33.54
CMPNN (Inv = Inv Reduced)258.32 ± 22.15285.81 ± 0.11286.25 ± 0.62
WN18RR-LPRGCN39.79 ± 6.3738.35 ± 7.1742.11 ± 4.61
SlotGAT21.84 ± 3.8536.52 ± 4.9033.35 ± 2.52
CMPNN (Inv)394.08 ± 46.89990.81 ± 1.00827.90 ± 0.66†
CMPNN (Inv Reduced)394.08 ± 46.89990.81 ± 1.00162.72 ± 23.38

Third, we have added a paragraph, "Computing Structural Bias for ΦnT\Phi_n^{\mathcal{T}}", with Proposition 7, at the end of Section 4.3 of the revised submission, which explains how our method overcomes some of the challenges with the exponential growth in the unobserved compositions of the input mappings. We show that, unlike the universal representation baseline method, our approach avoids creating possibly exponentially many compositions of some mappings in T\mathcal{T}.

Fourth, the data preparation to create the universal representation must be done in some data transformation languages, e.g., Cypher or Python, with which end-users are often not familiar. Our approach avoids this manual data transformation process. Fifth, a graph dataset is often used for multiple purposes and by multiple users in an organization. Consider user A who would like to learn to perform node classification on graph G and user B who queries G for some information. Using the universal graph approach forces user A to copy the entire G and maintain its own version of G. This approach might not be possible in many organizations due to possible privacy and data leakage issues. Using our approach, different users can use and share the same dataset.

We explain the advantages of conditional graphs over rewriting the input graph in our response to Q2. Finally, our approach provides a flexible platform for implementing other methods of indirectly modifying the message passing and information sharing patterns to instill invariance in a wide variety of GNNs without the overhead of directly modifying the input graph. For example, one can use our approach based on conditional-graphs to implement the idea of always using only a fixed subset of all message passing patterns across all variants for a given set of mappings, e.g., Invariant Reduced in our experiments (Appendix H.3).

W2

The method relies on predefined information-preserving mappings.

We agree with the reviewer that, in some cases, domain knowledge may be required to specify the set of initial mappings. In these cases, domain knowledge can help increase the accuracy, reliability, and invariance of graph learning, akin to physics informed deep learning. Due to the rapidly growing application of graph learning in various domains, we will witness increasing numbers of these cases. Even if an initial set of mappings is inferred from data or extracted from domain knowledge, the problem of efficient invariant learning is challenging. It is important to provide a principled approach to naturally and efficiently include this domain knowledge in the training process. Our approach provides such a platform to encode domain knowledge in a wide variety of GNN architectures. Moreover, our approach returns invariant results on the compositions of these mappings, which are partially known and not directly specified. As explained in our response to W1, our approach also avoids creating possibly exponentially many compositions of the input mappings (Section 4.3). As explained in our response to Q3, in our experiments, we inferred or mined the mappings from the data.

Reviewer_Uy3fOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper studies a limitation of graph neural networks: two graphs can encode the same underlying information while having different, non-isomorphic structures, and a GNN may produce different predictions depending on which representation is used. It formalizes these information-preserving transformations as bijective graph mappings, represented by pairs of graph patterns called switchings, and extends the conventional notions of invariance, equivariance, and expressivity to these transformations. The main methodological contribution is an algorithm that modifies a GNN's structural bias using conditional graphs, which separate the context required to identify a graph pattern from the edges over which information is propagated. The authors prove that the resulting structural bias achieves invariance under a specified mapping and claim that the modification is minimal under their proposed ordering of structural biases, preserves the original model's expressivity, and can strictly increase expressivity in some cases. They instantiate the method for seven architectures and evaluate it on IMDb, DBLP, WN18RR, and Freebase, covering node classification and link prediction. The experiments compare the original models, training on multiple graph variants, a universal graph formed by combining variants, and the proposed invariant versions; the latter achieve a reported Kendall rank correlation of 1.000 across variants, improve the original task metric in 14 of 23 model–task combinations, and remain within 0.2 points of the original in five more. The results also expose meaningful costs and exceptions: some configurations run two to four times slower, and four model–task combinations lose accuracy, with the largest concerns arising from dense shortcut relations and architecture-specific propagation constraints.

Critical strengths
  • The paper studies how GNN predictions can change when the same information is stored in different graph structures. This is relevant to knowledge graphs and heterogeneous networks. The proposed method modifies existing GNNs to make them invariant to specified graph transformations, without requiring training on every graph variant.

  • The method is tested on seven GNN architectures and four datasets, covering node classification and link prediction. The method achieves a reported Kendall's tau of 1.000 across graph variants. It also improves accuracy in 14 of 23 model–task settings and stays within 0.2 points of the original model in five more.

Critical weaknesses

(W1) Theoretical concerns: The group definition in Theorem 1 may not be mathematically correct as written. The expressivity and minimality claims also need clearer assumptions and stronger proofs.

On page 3, Theorem 1 defines $ \Phi_T^n=\Gamma_T\cup\Pi_n $ and claims that this union is a group under composition. Here, ΓT\Gamma_T is generated by the specified structural mappings, while Πn\Pi_n is the group of node permutations. The union of two groups is not generally a group. Closure under composition would require, in particular, that composing a structural mapping with a node permutation always produces an element of the union. That does not follow merely because each set is individually a group. This is especially concerning because the paper defines equivalence classes and the proposed notion of expressivity using the action of ΦTn\Phi_T^n. The issue is therefore not simply a notation problem in an isolated theorem; it potentially affects the equivalence relation underlying the expressivity definition. The natural correction would be to define the group generated jointly by the structural mappings and the permutations, for example, $ \left\langle \Gamma_T\cup\Pi_n\right\rangle, $ and then establish that this group acts on the specified graph family and preserves the intended information. Alternatively, the authors could provide a stronger condition under which the union itself is closed under composition. I would not regard this as resolved by the later observation that invariance under individual generators extends to their compositions. That observation may be sufficient for the invariance result, but it does not by itself establish the group and orbit claims as stated.

(W2) Theorem 3 is stated more broadly than its proof supports. Theorem 3 states that, for all mappings τ\tau and GNNs ff, the invariant model fτf_\tau is at least as expressive as ff under the proposed equivalence. However, the proof in Appendix E.4 explicitly assumes that the pattern-aggregation, total-aggregation, and update functions are injective. It also simplifies the setting by assuming that all nodes share a label and have no features, before claiming that the argument extends to other cases. Those assumptions are not included in the theorem's statement. More importantly, injectivity is a substantive condition in expressivity theory, not a property of arbitrary practical GNNs. A learned neural network's aggregation or update function need not be injective.

(W3) Limited evaluation of generality: The experiments use four datasets and a limited set of predefined graph transformations. Although the results are promising, they do not fully establish how well the method works with other transformations or when the supplied mappings are imperfect.

(W4) Incomplete evidence for invariance and equivariance: The paper reports identical prediction rankings across graph variants, but identical rankings do not guarantee identical prediction scores or embeddings. Direct comparisons of model outputs would provide stronger evidence, and the empirical evaluation of equivariance is limited.

(W5) the minimality claim. The paper repeatedly describes its changes as the minimal possible modifications required to achieve invariance. The formal result, however, establishes minimality relative to a particular partial ordering over structural biases. That is a more limited statement than global minimality over all invariant architectures or all possible modifications to a GNN. The proof of Proposition 6 in Appendix E.3 is also too terse for the strength of the claim. It argues that removing a conditional graph destroys an isomorphism-preserving correspondence, and that removing a context or propagation edge breaks the construction. This does not obviously cover every alternative structural bias that could be smaller under the paper's ordering.

Questions for authors

(Q1) Please address the theoretical concerns in W1, W2, and W5.

(Q2) Can exact invariance be verified directly, and can the equivariance claim be demonstrated? The paper reports Kendall-τ\tau=1.0, but identical rankings do not imply identical output scores. Could the authors report maximum absolute differences between prediction scores or embeddings across equivalent variants and demonstrate equivariance for at least one representative architecture?

(Q3) How much of the benefit remains under alternative, realistic schema transformations? The four datasets provide a useful controlled evaluation, but most variants are generated from the same underlying graph using a predefined family of rewrites. Could the authors test one additional transformation family, or evaluate an unseen composition of the specified transformations, while keeping the same task and split?

7 comments

W1

Theoretical concerns: The group definition in Theorem 1 may not be mathematically correct as written.

Definition of the groups (W1, Q1). We have followed the reviewer's comment and have rewritten and redefined the group definition in the paragraph on Composition of Mappings in Section 2 of the revised submission according to the joint composition of permutations and mappings in Φ\Phi and ΓT\Gamma^{\mathcal{T}}.

The revised paragraph defines the two groups as follows. Given a set of mappings T\mathcal{T} on G\mathcal{G} that is closed under inverse, ΓT\Gamma^{\mathcal{T}} is the set of all mappings constructed from the mappings in T\mathcal{T} by finite compositions, together with the mapping ι\iota that maps every graph in G\mathcal{G} to an isomorphic graph preserving node ids, labels, and features; Proposition 3 shows that inverses, compositions, and ι\iota can again be expressed by sets of switchings, and Theorem 1 states that ΓT\Gamma^{\mathcal{T}} is a group with composition on G\mathcal{G}. For a set of graphs G⊆Gn\mathcal{G} \subseteq \mathcal{G}^n that is closed under isomorphism, ΦnT=⟨ΓT∪Πn⟩\Phi_n^{\mathcal{T}} = \langle \Gamma^{\mathcal{T}} \cup \Pi^n \rangle is the set of all the compositions of the mappings in ΓT\Gamma^{\mathcal{T}} and the permutations in Πn\Pi^n, and Theorem 2 states that ΦnT\Phi_n^{\mathcal{T}} is a group with composition in G\mathcal{G}.

W2

Theorem 3 is stated more broadly than its proof supports.

Assumptions of Theorem 4 (W2, Q1). As explained in the appendix, we follow the standard and established assumptions in the theoretical analysis of expressivity with regard to isomorphism, e.g., Xu et al., 2019, we assume that the functions PAGG, TAGG, and UPDATE in Equation 2 in the input GNN to the algorithm in Section 4.3 are injective. We have followed the reviewer's comment and clarified this assumption before and in the statement of Theorem 4 in the revised submission - Theorem 3 of the original submission. The added sentence reads: "Following standard and established assumptions in the theoretical analysis of expressivity with regard to isomorphism (Xu et al., 2019; Morris et al., 2019; Geerts and Reutter, 2022), we assume that the functions PAGG, TAGG, and UPDATE in Equation 2 in the input GNN to the algorithm in Section 4.3 are injective." The new theorem is as follows:

For all mappings τ and GNN f, if the functions PAGG\text{PAGG}, TAGG\text{TAGG}, and UPDATE\text{UPDATE} in Equation 2 are injective, we have f⪯τfτf \preceq_\tau f_\tau. Also, there is a mapping τ and GNN f such that f≺τfτf \prec_\tau f_\tau.

We agree with the reviewer that injectivity is a substantive condition and that the aggregation and update functions of a trained network need not be injective. It is, however, the standard assumption under which the expressivity of GNNs is analyzed with respect to isomorphism (Xu et al., 2019; Morris et al., 2019; Geerts and Reutter, 2022), and it can be realized by common architectures, e.g., by sum aggregation followed by a multi-layer perceptron (Xu et al., 2019). Theorem 4 should therefore be read as a statement about what the modified architecture can express: our modification of the structural bias does not remove any distinction between graphs that the original architecture can make, and it can add some. It is not a statement about particular accuracy of a certain trained model, and we have made no such direct claim.

Labels and features in the proof (W2, Q1). The proof assumes, for the sake of brevity, that all nodes share a label and have no features. Labels and features enter only as additional inputs to the injective PAGG, TAGG, and UPDATE functions and do not change their injectivity, so the argument applies unchanged to labelled nodes with features; the revised proof (Appendix E.4) says so explicitly.

W3 and Q3

Limited evaluation of generality: The experiments use four datasets and a limited set of predefined graph transformations.

We address the two parts of the comment in turn: whether the benefit extends beyond the given transformations (Q3), and how the method behaves when the supplied mappings are imperfect (W3).

W3 and Q3 (continued)

A new transformation family: reification (Q3). The revised submission also adds a family of transformations that is not a rewrite of our earlier graphs. On OGBN-MAG, the largest graph of the study by number of nodes (15.5–23.1 million nodes per variant), the variants reify relations, i.e., represent an edge by a node connected to both of its endpoints, and the two switchings move the institutions of an author and the fields of study of a paper between their reified nodes and the authorship nodes. The invariant versions of all six architectures run on it are exactly invariant (Kendall-τ = 1), whereas the Originals have Kendall-τ between 0.19 and 0.86; for five of the six, the invariant version is also at least as accurate as the Original on its best variant, within 0.2 points (Appendix H.5, Table 49).

Imperfect mappings (1): only some mappings are known (W3). In Appendix H.9 (Tables 56 and 57, Figure 5; summarized in Table R1), we give the algorithm each switching alone, on every task with more than one switching. Theorem 3 then guarantees invariance only between the variants that the known switchings relate; we call each such group of variants a block. The results match this prediction exactly: in all 51 cells, the 69 pairs of variants within a block give bitwise identical outputs at every seed, and none of the other 138 pairs reaches Kendall-τ = 1. Across blocks, the invariant versions behave like the Originals, so their mean pairwise Kendall-τ is still above the Original's in 49 of the 51 cells. Their accuracy lies between that of the Original and that of the invariant version given every switching, or within 0.74 points of that range, in all but three cells; e.g., RGCN reaches 63.76 Micro-F1 on IMDb-NC with the actor switching alone, against 63.05 for the Original and 65.31 with both switchings. A missing switching therefore reduces the gain of the invariant version rather than breaking it.

Table R1. Incomplete mappings, per task (condensed from Table 56 of the revised submission): task metric (Micro-F1 / MRR) averaged over variants, and mean pairwise Kendall-τ across all variants, each averaged over the invariant versions of the task (the Original once per architecture). Within every block of variants that the known switching relates, the outputs are bitwise identical in every cell (Table 57). Switching 1 / 2: director / actor (IMDb-NC), two-hop / three-hop shortcut relations (Freebase-NC), area on the venue / – (DBLP-LP), inverse / shortcut relations (WN18RR-LP). –: not run (on DBLP-LP, the author switching alone). On WN18RR, the invariant versions of RGCN and SlotGAT use the relations that occur in some variant, so this reference differs from Table 1. Each cell: task metric (Micro-F1 / MRR, averaged over variants) / mean pairwise Kendall-τ across all variants.

TaskVersionsOriginalSwitching 1 aloneSwitching 2 aloneEvery switching
IMDb-NC961.78 / 0.75961.45 / 0.83361.26 / 0.83461.82 / 1.000
Freebase-NC1063.33 / 0.63862.11 / 0.76361.53 / 0.80161.87 / 1.000
DBLP-LP546.57 / 0.59045.82 / 0.737– / –45.96 / 1.000
WN18RR-LP438.99 / 0.39039.41 / 0.61238.99 / 0.64139.67 / 1.000

W3 and Q3 (continued)

Imperfect mappings (2): noisy mappings and noisy data (W3). In Appendix H.6 (Tables 51 and 52; summarized in Table R2), we corrupt 2, 5, or 10% of the occurrences of a switching by rewiring them to a random node, dropping them, or adding a spurious one, with three seeds on every task. Under noise in the mapping, each variant is corrupted independently, so the variants are no longer equivalent. Where a corrupted edge can be checked against information the variant still holds (the base relations from which the shortcut relations of WN18RR and Freebase are composed, and the paper–area relation of DBLP when a spurious area is added), it never enters the compiled structural bias, so the invariant version stays exactly invariant (Kendall-τ = 1); on WN18RR and Freebase, its accuracy does not change, while the Originals and the Universal Graph lose up to 3.2 points. Where it cannot be checked (IMDb and DBLP), no model can be exactly invariant, but the invariant versions degrade gracefully: their mean Kendall-τ is 0.81, 0.78, and 0.76 at 2, 5, and 10%, against 0.68, 0.68, and 0.67 for the Original, and it is higher than the Original's at 109 of 135 points. Under noise in the data, a single corruption is written into every variant, so the variants remain equivalent; the invariant versions stay exactly invariant at all 261 points and lose about as much accuracy as the baselines at 10% (1.88 points, against 1.84 for the Original and 1.94 for the Universal Graph). The exception is DBLP-LP, where the invariant structural bias is the union of the variants' biases, so the invariant version and the Universal Graph are the same model and lose the same 3.49 points; most of this comes from MAGNN with the Union metapaths, which contain every encoding of the corrupted relation (7.17 points, against 1.29 for the Original).

Table R2. Noisy mappings and noisy data, per task (condensed from Tables 51 and 52 of the revised submission). A fraction ε of the occurrences of a switching is rewired, dropped, or duplicated by a spurious one; values are averaged over seeds, the three kinds of corruption, and the invariant versions of the task (the Original and the Universal Graph once per architecture). Original, ε = 0.1: under noise in the mapping. Inv, noise in the data: minimum over all points. Two cells that do not measure robustness are left out (RGCN on IMDb-LP, at chance level in two of three seeds, and one MAGNN version on DBLP-LP that never reads the corrupted relation; Appendix H.6). Kendall-τ (first table) and change of the task metric (second table).

TaskVersionsOrig, clean / ε=0.1Inv, noise in mapping, ε=0.02 / 0.05 / 0.1Inv, noise in data (min)
IMDb-NC90.759 / 0.7160.818 / 0.790 / 0.7611.000
Freebase-NC100.638 / 0.5951.000 / 1.000 / 1.0001.000
IMDb-LP30.601 / 0.6120.764 / 0.720 / 0.7451.000
DBLP-LP30.540 / 0.6050.831 / 0.805 / 0.7911.000
WN18RR-LP20.252 / 0.2341.000 / 1.000 / 1.0001.000

Change of the task metric at ε = 0.1 (points):

TaskMapping noise: Inv / Orig / UnivData noise: Inv / Orig / Univ
IMDb-NC-0.62 / -0.86 / -0.72-0.79 / -0.69 / -0.77
Freebase-NC0.00 / -1.09 / -1.50-2.92 / -2.90 / -2.55
IMDb-LP-0.18 / +0.12 / -0.43-0.32 / -0.17 / -0.26
DBLP-LP-0.92 / -1.22 / -3.27-3.49 / -0.92 / -3.49
WN18RR-LP0.00 / -0.07 / +0.23-4.07 / -4.43 / -3.70

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.