Size-Invariant Graph Representations for Graph Classification Extrapolations

1. Introduction

• The task is inductive graph classification when training and deployment graphs differ in size or vertex-attribute arrangements, without access to test-distribution samples.The introduction asks whether GNNs remain robust under these shifts and whether a classifier can extrapolate without test samples.Source: §1 · p. 1
• The paper assumes cause-mechanism independence and invariant P(Y|G), and focuses on simple undirected graphs with discrete vertex attributes.It frames extrapolation through a causal model because test samples are unavailable.Source: §1 · p. 1
• The authors introduce a causal model for graph-size and vertex-attribute distribution shifts, then propose a GNN- and graphon-based representation invariant to those shifts.The representation is presented as capable of extrapolating from a single training environment, such as graphs of one size.Source: §1 · pp. 1–2
• In most experiments, neither IRM nor Xu et al.’s GNN extrapolation modifications performed well on OOD graph-classification tasks.The paper frames these results against shifts in graph size and vertex attributes.Source: §1 · pp. 1–2

2. Graph Classification: A Causal Model Based on Random Graphs

• Under ICM, P_tr(Y|G)=P_te(Y|G), so the train/test shift comes from graph distributions; without test graphs or a proxy, extrapolation requires assumptions about causal mechanisms.The model allows training and test environment supports not to overlap.Source: §2 · pp. 2–3
• The SCM extends graphon random-graph modeling with vertex attributes: an unknown graphon W determines labels and graph structure or attributes, while a hidden environment represents properties that shift.Graph size is determined by the environment, and the label is generated from W and independent noise.Source: §2 · p. 2
• The test graph uses a coupled generation process that replaces the training environment with a test environment while reusing some random variables; environment changes can alter graph size and attributes.The test graph’s adjacency is defined as in training, and its attributes use the same function.Source: §2 · pp. 2–3
• In the Erdős–Rényi example, train and test graphs can have disjoint size supports while sharing edge probability p, and the target can be p, which is invariant to graph size.The edge probability is generated from shared uniform noise and a constant graphon.Source: §2 · p. 3
• In the SBM example, blocks determine edge probabilities through a symmetric matrix P, and a two-block task can use the between-block probability P_1,2 as a size-invariant target.Vertices are assigned to blocks by intervals of latent uniform variables.Source: §2 · p. 3
• The attribute-augmented SBM example ties distinct vertex attributes to blocks and lets the environment change the attribute distributions assigned within each block.The example uses four one-hot colors, with two colors associated with each block.Source: §2 · p. 3

3. E-Invariant Graph Representations

• Traditional graph methods can exploit spurious correlations between environment and label-relevant structure, hindering prediction when the test distribution shifts.Source: §3 · p. 4
• An E-invariant representation has OOD test error equal to training-distribution generalization error and performs no worse than evaluation under the training environment distribution.Source: §3 · p. 4
• IRM may fail for unseen test environments with nonlinear representations and cannot support size extrapolation when training contains only one environment.Source: §3 · p. 4

3.1. An Approximately E-Invariant Graph Representations for Our Model

• The explicit representation encodes induced subgraph densities for connected attributed subgraphs up to size k as distinct one-hot graph features.Source: §3.1 · p. 4
• GNN representations can be regularized to bring same-topology graphs with different attributes closer when those differences do not materially affect training accuracy.Source: §3.1 · p. 5

3.2. Theoretical Description of our E-Invariant Graph Representations

• Under the stated attribute-invariance assumption, representations of different-sized graphs with the same graphon become nearly identical for k much smaller than both graph sizes.Source: §3.2 · pp. 5–6
• When observed graphs are relatively small, the small k needed for approximate invariance can compromise the representation’s ability to extract information about the graphon.Source: §3.2 · p. 6

OOD extrapolation in graph classification and size extrapolation in GNNs

• Prior graph extrapolation studies cover applications and datasets, but do not provide guarantees of test extrapolation performance, a causal model, or proof that tasks require extrapolation across environments.The review contrasts this work with Xu et al. (2021), Hu et al. (2020), and studies in physics, reasoning, and graph algorithms.Source: §4 · p. 6

Causal reasoning and invariances

• Causal-invariance research includes ICM, causal discovery from change, disentanglement, IRM, and REx, which focuses on training environments with the greatest impact on training.The passage groups these efforts as work on counterfactual inference and invariance.Source: §4 · p. 6
• Unlike methods that seek invariance across observed environments, this work targets single-environment training and test support outside the training support, without access to test data during training.The review identifies Mouli & Ribeiro (2021) as prior single-environment representation learning, while noting those methods are not graph-specific.Source: §4 · p. 6

Graph classification using induced homomorphisms

• Induced-homomorphism features have been used for graph kernels and subgraph-based prediction, but the reviewed methods do not focus on invariant representations or extrapolation.The review also notes that these kernel methods can perform poorly on some tasks.Source: §4 · p. 7

Expressiveness of graph representations

• Representation expressiveness concerns generalization over the training distribution, so it is orthogonal to OOD extrapolation.The passage relates expressiveness to model-family bias and potential training-distribution generalization error, assuming sufficient data and appropriate optimization.Source: §4 · p. 7

5. Empirical Results

• The evaluation tests Γ1-hot, ΓGIN, and ΓRPGIN with GIN or RPGIN and an MLP, against graph-kernel and GNN baselines, with IRM used when multiple training-size environments are available.The reported measures include training and validation accuracy and extrapolation test accuracy.Source: §5 · p. 7

5.1. Size extrapolation tasks for unattributed graphs

• Γ1-hot, ΓGIN, and ΓRPGIN extrapolate across the unattributed-graph experiments, while IRM adds no improvement in the multi-environment Erdős–Rényi task.The compared methods had similar or often identical validation and test accuracies; Table 1 reports mean and standard deviation of accuracy.Source: Table 1 · p. 8, §5.1 · p. 8

5.2. Size/attribute extrapolation for attributed graphs

• ΓGIN and ΓRPGIN achieve higher test accuracy than representations that exploit training attribute correlations, while IRM has no beneficial impact.Adding larger training graphs closer to test sizes increases the extrapolation accuracy of most methods.Source: Table 2 · p. 8, §5.2 · p. 8

5.3. Experiments with real-world datasets that violate our causal model

• ΓGIN or ΓRPGIN ranks among the top four methods on every real-world dataset except NCI109, using OOD-test MCC.The evaluation uses real-world OOD splits based on graph size and datasets that violate the stated causal-model assumptions.Source: Table 3 · p. 9, §5.3 · p. 9

• The work defines a representation approximately invariant to train/test changes in its causal model and reports empirical benefits on synthetic and real-world datasets against standard baselines.It also contributes a blueprint for defining graph extrapolation tasks through causal models.Source: §6 · p. 9

• E-invariance requires the representation to satisfy the stated condition across training and test environments.The definition quantifies over environments in the supports of Etr and Ete.Source: A. Proof of Proposition 1 · p. 17
• If Γ is E-invariant, its OOD test error equals its generalization error over the training distribution.The proposition considers a permutation-invariant representation and a downstream function.Source: A. Proof of Proposition 1 · p. 17
• The proof notes that the label depends only on W and independent random noise, so Y is E-invariant.The argument refers to Definitions 1 and 2 and Figure 1.Source: A. Proof of Proposition 1 · p. 17

• The argument assumes the vertex-attribute function is invariant across training and test environments and considers k up to the smaller graph size.The theorem concerns graphs satisfying Definitions 1 and 2.Source: B. Proof of Theorem 1 · p. 17
• The proof states that the density bound converges as graph size grows and extends the result to vertex-attributed graphs under the stated structural causal model assumptions.It says a similar bound can be obtained for tind and that the difference between the convergent values is preserved.Source: B. Proof of Theorem 1 · pp. 17–18
• For vertex-attributed graphs, the proof treats expected induced homomorphism densities as a martingale because the attribute function is invariant to the environment.It defines the initial expected density as t*(Fk, W).Source: B. Proof of Theorem 1 · p. 18

C. Biases in estimating induced homomorphism densities

• A multiplicatively biased density estimator can preserve the expected learned representation when READOUTΓ sums vertex embeddings.The result compares the expected representation with that obtained from true induced connected homomorphism densities.Source: C. Biases in estimating induced… · p. 19
• The result relies on GNN+ learning functions over k′-vertex subgraphs, for which it is described as a most expressive representation.This allows the learned representation to match that formed from true densities when the bias-corrected density values meet the stated condition.Source: C. Biases in estimating induced… · p. 19

D. Review of Graph Neural Networks

• The paper obtains graph representations by applying GNNs to connected induced subgraphs and averaging their resulting representations.The subgraph computations are differentiable and can be learned end-to-end.Source: D. Review of Graph Neural Networks · p. 19
• GNNs update vertex states by repeatedly combining each vertex’s previous state with information aggregated from its neighbors.The neighborhood aggregation can use a permutation-invariant function and may sample neighbors rather than aggregate all of them.Source: D. Review of Graph Neural Networks · p. 19

E. Further Related Work

• Subgraphs are the framework’s basis for fitting training data and extrapolating to OOD graphs, with the rationale linked to exchangeable-graph and graph-limit theory.The discussion frames this as a foundation for graph classification across distribution shifts.Source: E. Further Related Work · p. 20
• Graphlet counting can be sensitive to attribute shifts, whereas the paper’s GNN approach learns task-tailored compressed representations of attributed subgraphs.The discussion notes that downstream models using attributed-subgraph counts may not have seen enough examples of some types during training.Source: E. Further Related Work · p. 21
• The discussion contrasts subgraph-based extrapolation with methods that use other graph features, domain knowledge, adversarial robustness, or regularization and augmentation.It treats dynamic-graph representation as a mostly separate direction from graph-wide learning across a dataset of graphs.Source: E. Further Related Work · pp. 20–21

F.1. Model implementation

• The experiments use GIN, GCN, PNA, and RPGIN implementations, with graph-kernel baselines implemented using graphkernels and SVMs.The paper also pre-processes estimated induced homomorphism densities for its procedure and the graphlet counting kernel.Source: §F.1 · p. 22
• For ΓGIN and ΓRPGIN, the model sums latent representations of k-sized connected induced subgraphs, weighting each by its induced homomorphism density.Γ1-hot instead uses a vector of subgraph densities and a learnable weight matrix to map them into a graph representation.Source: §F.1 · p. 22

F.2. Schizophrenia Task: Size extrapolation

• In the schizophrenia task, 20 of 145 brain graphs are held out for testing, with healthy test graphs reduced from 264 vertices to an average of 178.2.The held-out graphs are balanced across healthy and schizophrenic patients; hyperparameters are chosen with stratified five-fold cross-validation, followed by retraining with ten initialization seeds.Source: §F.2 · pp. 22–23

F.3. Erd˝os-R´enyi Connection Probability: Size Extrapolation

• For Erdős–Rényi classification, training graphs have size 80 or sizes 70 and 80, while all test graphs have size 140.The task predicts edge probability p ∈ {0.2, 0.5, 0.8}, using induced homomorphism densities for subgraphs of size k = 5.Source: §F.3 · p. 23

F.4. Extrapolation performance over SBM attributed graphs

• In the attributed SBM task, training graphs have size 20, sizes 14 or 20, or sizes 20 or 30; test graphs have size 40.Vertex-color probabilities are reversed between training and test environments, and the graph label is the cross-block edge probability.Source: §F.4 · p. 24

F.5. Extrapolation performance in real world tasks that violate our causal model

• The real-world evaluation trains on graphs below the 50th size percentile and tests on graphs above the 90th percentile.Ten percent of the training graphs are held out for validation.Source: §F.5 · p. 24
• The experiments use subgraph size k = 4 and restrict the subgraph vocabulary for NCI1, NCI109, and DD to the most common types.The retained counts are 100 for NCI1 and NCI109 and 30,000 for DD; PROTEINS retains all distinct subgraphs.Source: §F.5 · p. 24
• To address class imbalance, the neural models reweight classes using training proportions and are evaluated at the epoch with the highest validation Matthew Correlation Coefficient.The passage points to Table 4 for the dataset statistics.Source: §F.5 · p. 25, Table 4 · p. 25