PaperlayerView exact revision on arXiv

Source-linked AI summary

Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning

Pan Li, Yanbang Wang, Hongwei Wang, Jure Leskovec

arXiv:2009.00142v4cs.LGstat.ML

TL;DR

GNNs are limited by the 1-WL test when representing structurally different node sets, while higher-order alternatives often target entire graphs and do not exploit sparsity. The paper proposes Distance Encoding and two GNN integrations with theoretical guarantees and efficient graph-structure use. Across three tasks, the models outperform WLGNNs by up to 15% and also surpass task-specific baselines, while remaining limited on some distance-regular graphs and by unexplored DE instantiations.

  • Problem

    GNNs can assign identical representations to structurally different node sets because their expressive power is bounded by the 1-WL test.

    Source: §1 · p. 2, §2.2 · p. 4

  • Method

    Distance Encoding maps distances from a target node set to graph nodes and is used either as extra node features or to control message aggregation.

    Source: §1 · p. 2

  • Results

    Up to 15% improvement in average accuracy over WLGNN was achieved across node-role, link-prediction, and triangle-prediction tasks, with performance also exceeding task-specific baselines.

    Source: §1 · p. 2

  • Takeaways & Limitations

    DE provides a general, theoretically characterized way to strengthen structural representations of node sets while using sparse graph structure for efficiency and scalability.

    Source: §1 · p. 2, §6 · p. 10

    DE-GNN-1 does not exceed WLGNN on distance-regular graphs with the same intersection array, and the paper evaluates only four DE instantiations across three task levels.

    Source: §3.2.2 · p. 7, §6 · p. 10

Abstract

from arXiv · show

Learning representations of sets of nodes in a graph is crucial for applications ranging from node-role discovery to link prediction and molecule classification. Graph Neural Networks (GNNs) have achieved great success in graph representation learning. However, expressive power of GNNs is limited by the 1-Weisfeiler-Lehman (WL) test and thus GNNs generate identical representations for graph substructures that may in fact be very different. More powerful GNNs, proposed recently by mimicking higher-order-WL tests, only focus on representing entire graphs and they are computationally inefficient as they cannot utilize sparsity of the underlying graph. Here we propose and mathematically analyze a general class of structure-related features, termed Distance Encoding (DE). DE assists GNNs in representing any set of nodes, while providing strictly more expressive power than the 1-WL test. DE captures the distance between the node set whose representation is to be learned and each node in the graph. To capture the distance DE can apply various graph-distance measures such as shortest path distance or generalized PageRank scores. We propose two ways for GNNs to use DEs (1) as extra node features, and (2) as controllers of message aggregation in GNNs. Both approaches can utilize the sparse structure of the underlying graph, which leads to computational efficiency and scalability. We also prove that DE can distinguish node sets embedded in almost all regular graphs where traditional GNNs always fail. We evaluate DE on three tasks over six real networks: structural role prediction, link prediction, and triangle prediction. Results show that our models outperform GNNs without DE by up-to 15\% in accuracy and AUROC. Furthermore, our models also significantly outperform other state-of-the-art methods especially designed for the above tasks.

1 Introduction

GNNs support graph and node-set representation learning but are limited by the 1-WL test, motivating Distance Encoding as a more expressive, efficient extension. DE-based models distinguish challenging structures and improve performance across node-role, link, and triangle prediction tasks.

1 Introduction

  • Shortest-path distances can separate node colors in the illustrated regular graph because only blue nodes have another node at shortest-path distance 3.The example shows why distance information can distinguish structures that WLGNN cannot.Source: Figure 1 · p. 2
  • 1-WL-bounded GNNs can produce identical representations for structurally different nodes or node sets, especially in regular graphs without discriminatory attributes.This limitation also affects node-pair representations needed for link prediction.Source: §1 · p. 2
  • Distance Encoding (DE) maps graph-distance information from a target node set to every graph node, using measures such as shortest-path distance or generalized PageRank scores.DE can be incorporated as extra node features or used to control message aggregation.Source: §1 · p. 2
  • DE-GNN and DEA-GNN provide theoretical guarantees for distinguishing non-isomorphic node sets in almost all sparse regular graphs where WLGNNs fail.The models can represent nodes, node-pairs, larger node sets, and entire graphs while remaining independent of node identifiers.Source: §1 · p. 2
  • Up to 15% improvement in average accuracy over WLGNN was reported across node-structural-role, link-prediction, and triangle-prediction tasks.The methods also outperformed baselines designed specifically for these tasks.Source: §1 · p. 2

2 Preliminaries

The preliminaries define structural representations as permutation-invariant mappings of node-set and graph-feature tuples, then characterize WLGNNs through their relationship with the 1-WL test. This framework establishes both the desired invariance and the expressive limitation that the paper's methods address.

2.1 Graph Representation Learning

  • Structural representation is a permutation-invariant function of a node set and graph features, so isomorphic tuples must receive the same representation.Permutation invariance removes dependence on absolute node identifiers and supports inductive generalization.Source: §2.1 · p. 3
  • The framework covers node classification for p=1, link prediction for p=2, and entire-graph representation when the target set is all nodes.The paper primarily studies fixed, small node sets whose size does not depend on graph size.Source: §2.1 · p. 3
  • If a structural representation distinguishes every pair of non-isomorphic tuples, a three-layer ReLU network can universally approximate invariant functions under compactness and continuity conditions.This theorem links structural distinguishability to universal approximation.Source: §2.1 · p. 3

2.2 Weisfeiler-Lehman Tests and WLGNN for Structural Representation Learning

  • 1-WL iteratively aggregates and hashes node-neighborhood colors; differing final color configurations certify non-isomorphism, but matching configurations do not always do so.This asymmetry motivates measuring GNN expressive power by which non-isomorphic structures they can distinguish.Source: §2.1 · p. 3, §2.2 · p. 4
  • WLGNNs mimic 1-WL and include GCN, GraphSAGE, GAT, MPNN, and GIN, with their structural representation power bounded by the 1-WL test.With injective aggregation and neural maps and enough layers, WLGNNs distinguish structures that 1-WL distinguishes, but not those 1-WL cannot.Source: §2.2 · p. 4
  • WLGNNs cannot distinguish equal-sized node sets in r-regular graphs unless node or edge features are discriminatory.This is the central expressive limitation addressed by the proposed structural features.Source: §2.2 · p. 4

3 Distance Encoding and Its Power

Distance Encoding augments GNNs with permutation-invariant distances from a target node set, improving structural representation beyond 1-WL while retaining sparse-graph efficiency. DE-GNN distinguishes many regular-graph structures theoretically, whereas its DE-1 form has limits on distance-regular graphs; DEA-GNN offers alternative aggregation control with the same theoretical bounds.

3.1 Distance Encoding

  • Distance Encoding maps each graph node to a permutation-invariant distance representation relative to a target node set, using measures such as shortest-path distance or generalized PageRank.For a set S, DE aggregates node-to-node encodings over v ∈ S; random-walk landing probabilities provide a general construction that includes SPD and generalized PageRank.Source: §3.1 · pp. 4–5

3.2 DE-GNN— Distance Encodings as Node Features

  • DE-GNN incorporates DEs by concatenating them with initial node attributes, and proper models use injective neural mappings and aggregation functions.The construction is compatible with WLGNN architectures and can be instantiated with injective components under countable inputs.Source: §3.2 · p. 5

3.2.1 The Expressive Power of DE-GNN

  • With SPD-based DE, DE-GNN distinguishes equal-sized node sets in almost all sampled r-regular graphs with probability 1−o(n^-1) within logarithmic-depth bounds.The result applies for 3 ≤ r < (2 log n)^1/2 and extends to non-overlapping node sets in a single sufficiently random regular graph.Source: §3.2.1 · p. 5
  • DE-GNN-1 can distinguish uniformly sampled n-sized r-regular graphs with probability 1−o(1) using injective set pooling within ⌈(1/2+ϵ) log n / log(r−1)⌉ layers.This follows by aggregating node representations produced by DE-GNN-1 into a graph representation.Source: §3.2.1 · p. 6

3.2.2 The Limitation of DE-GNN

  • DE-GNN-1 is limited on connected distance-regular graphs with the same intersection array, where discriminatory node or edge attributes are required to distinguish target nodes.The limitation concerns node representations using DE-1; the Shrikhande and 4 × 4 Rook’s graphs provide an example of this setting.Source: §3.2.2 · pp. 6–7
  • DE-GNN-2 can distinguish certain edges in the Shrikhande and 4 × 4 Rook’s graphs, even though the 2-WL test and related higher-order models fail on those node-pairs.The figure illustrates how differing DE-2 neighborhoods yield different intermediate representations after message-passing layers.Source: Figure 2 · p. 6, §3.2.2 · p. 7
  • Generalizing the regular-graph power theorem to distance-regular graphs remains challenging because analytic-friendly random models for distance-regular graphs are unavailable.Thus, the stronger DE-p behavior is demonstrated by examples rather than by a corresponding general theorem.Source: §3.2.2 · p. 7

3.3 DEA-GNN— Distance Encoding-1’s as Controllers of the Message Aggregation

  • DEA-GNN uses DE-1 values to control message aggregation, preserves DE-GNN’s established guarantees, and can trade complexity against performance through truncated or top-K aggregation.Its theoretical power is no worse than DE-GNN’s but remains bounded by the same limitation theorem; practical performance may vary across datasets and applications.Source: §3.3 · pp. 7–8

4 Related Work

Prior work improves structural representation through higher-order or task-specific methods, but often targets entire graphs, incurs tensor or pooling costs, or lacks permutation-invariant distance encodings. DE models relate these approaches theoretically while retaining sparse-graph processing and arbitrary node-set representations.

Higher-order graph representation methods

  • Higher-order GNNs such as Ring-GNN and PPGN target entire-graph representations and can be difficult to scale because they do not exploit graph sparsity.DE-GNN instead represents node sets of arbitrary sizes and can distinguish some node-pairs that 2-WL-limited methods cannot.Source: §4 · p. 8

Task-specific structural representation methods

  • SEAL, PGNN, and related methods motivate DE, but DE provides simpler node-pair representations than SEAL’s SortPooling and stronger permutation-invariant inductive behavior than PGNN’s anchor encodings.The paper presents DE as the first of these lines to derive a theoretical characterization and use it to improve related models.Source: §4 · p. 8

Aggregation-based related methods

  • DEA-GNN unifies several aggregation-based models, including MixHop, GDC, PowerGNN, PAGTN, and MAT, while explaining their representation-power bounds through DE.The paper also reports link-prediction success for generalized-PageRank aggregation when DEs are supplied as extra node attributes.Source: §4 · p. 8

5 Experiments

Experiments evaluate DE-GNN and DEA-GNN on node, node-pair, and node-triad tasks, showing consistent gains over WLGNNs and task-specific baselines.

Experimental setup

  • DE-GNN and DEA-GNN are evaluated on node-role classification, link prediction, and triangle prediction using six real graphs.The tasks represent target node sets of sizes 1, 2, and 3, respectively.Source: §5 · p. 8

Model instantiation

  • DE-GNN variants use shortest-path distances or landing probabilities as node attributes, while DEA-GNN-SPD uses shortest-path distances to control multi-hop aggregation.Experiments use GCN as the WLGNN basis and average results over 20 random seeds.Source: §5 · p. 9

Node-level results

  • DE-GNN significantly outperforms the baselines on node-role classification except on Europe-Airport, with landing probabilities slightly better than shortest-path distances for DE-1.GIN is the strongest WLGNN baseline on the node-level task, while Struc2vec is also competitive.Source: §5 · p. 9, Table 1 · p. 9

Node-pair-level results

  • DE-GNN-SPD significantly outperforms SEAL on link prediction, reducing error rates by more than 10% and by almost 30% on NS.The results indicate that DE-2 supplies the key signal, while SEAL’s complex graph-level readout is not necessary.Source: §5 · p. 9, Table 1 · p. 9

Node-triad-level results

  • For triangle prediction, shortest-path distance is substantially better than landing probabilities as DE-3, while higher-order DEs yield larger gains over WLGNNs.The supplied results also discuss positional-information limitations in PGNN that do not affect DE-3 in the same way.Source: §5 · pp. 9–10

Aggregation comparison

  • DEA-GNN-SPD improves DE-GNN-SPD by almost 1% across most tasks, demonstrating the benefit of multi-hop aggregation at an additional scalability cost.DEA-GNN-SPD aggregates multi-hop neighbors simultaneously.Source: §5 · p. 10

6 Conclusion and Discussion

The conclusion presents distance encoding as a theoretically characterized way to improve GNN structural representations while retaining scalable sparse-graph processing. It also identifies unresolved theoretical questions and unevaluated extensions.

6 Conclusion and Discussion

  • Distance encoding offers a new framework for improving GNN structural representation power with non-asymptotic expressive-power analysis and scalability based on sparse graph structure.The models can be trimmed to sampled ego-networks for extremely large graphs.Source: §6 · p. 10
  • The paper evaluates only four DE instantiations across three task levels, leaving other PageRank, attention-based, graph-level, and subgraph-counting applications for future work.The authors specifically mention more principled PageRank edge attributes and attention mechanisms over DEs.Source: §6 · p. 10
  • DE-1 has limitations on distance-regular graphs, including when used as node attributes or message-aggregation controllers, and its connection to spectral methods needs further characterization.The paper identifies this as a bridge between GNN and spectral approaches but states that rigorous characterization remains needed.Source: §6 · p. 10
  • Theorem 3.3 does not explain why higher-order DEs produce larger empirical gains, and tighter bounds are needed because its probabilistic quantization is not tight.The unresolved issue is how the probability depends on the node-set size p.Source: §6 · p. 10

A Proof of Universal Approximate Theorem for Structural Representation

The proof embeds node-set structures into an augmented compact feature space, transfers the representation problem through bijections, and applies universal approximation results under continuity and compactness assumptions.

Universal approximation

  • Because the augmented space is compact and the transferred representation distinguishes its non-isomorphic elements, a three-layer ReLU network universally approximates the invariant target function.The conclusion follows by applying Theorem 4 and using the mutual bijections among the original and augmented representations.Source: A Proof of Universal Approximate… · p. 15

Assumptions

  • The proof assumes a compact feature space and continuity of the target function over that space for every node set.These assumptions support the subsequent universal-approximation argument.Source: A Proof of Universal Approximate… · p. 15

Space construction

  • An augmented tensor space adds a binary diagonal slice to encode the selected node set, creating a bijection between augmented tensors and structural tuples.The original graph features occupy the first k dimensions, while the added slice identifies selected nodes.Source: A Proof of Universal Approximate… · p. 15

Bijection transfer

  • The structural representation and invariant target function transfer to the augmented space through the tuple–tensor bijection.The transferred representation distinguishes non-isomorphic augmented tensors whenever the original representation distinguishes the corresponding tuples.Source: A Proof of Universal Approximate… · p. 15

Continuity

  • Continuity is preserved under the transferred metric, so the augmented target function remains continuous.Lemma A.1 establishes this continuity transfer from the original space to the augmented space.Source: A Proof of Universal Approximate… · p. 15

B Proof for The Power of WLGNN for Structural Representation

The proof extends the standard WLGNN–1-WL correspondence from whole-graph representations to structural representations of node subsets by changing only the final readout.

Theorem proof

  • If two structural tuples cannot be distinguished by 1-WL, WLGNN outputs are identical; with injective aggregation and neural updates, distinguishable tuples receive different outputs given enough layers.This establishes the structural-representation analogue of the 1-WL expressive-power characterization.Source: B Proof for The Power of WLGNN for… · p. 15

Proof strategy

  • The extension from graph representations to structural representations changes only the final aggregation readout, which operates on the target node subset rather than all nodes.The remaining proof follows the logic of the corresponding results in with minor revision.Source: B Proof for The Power of WLGNN for… · pp. 15–16

C Proof for The Power of DE — Theorem 3.3

Theorem 3.3 shows that proper DE-GNNs distinguish fixed-size node sets in almost all sampled regular graphs, including cases where WLGNNs fail. The proof uses distance-labeled rooted subtrees, configuration-model growth, and edge-configuration randomness, while extending from single nodes to node sets and irregular-graph classes.

C Proof for The Power of DE — Theorem 3.3

  • With probability at least 1−o(n−1), a proper DE-GNN-p distinguishes two fixed-size node sets in independently sampled simple r-regular graphs when 3 ≤ r < (2 log n)1/2, using shortest-path distance.Source: C Proof for The Power of DE — Theorem… · pp. 16, 21
  • The single-node shortest-path result extends to fixed-size node sets and to neural encodings of landing-probability lists without reducing discriminatory power.The extension uses injective aggregation and the countable structure of shortest-path and landing-probability values.Source: C Proof for The Power of DE — Theorem… · p. 16
  • The proof’s node-set probability bound may be loose for p > 2, and obtaining a tight bound is left for future work.This is the stated limitation of Lemma C.1.Source: C Proof for The Power of DE — Theorem… · p. 16
  • DE-GNN representations depend on depth-L rooted subtrees whose distance labels enable distinctions that WLGNNs miss in regular graphs.The proof illustrates that two target nodes in 3-regular graphs can acquire different subtree representations when DE-1 labels are used.Source: C Proof for The Power of DE — Theorem… · p. 16, Figure 3 · p. 17
  • The proof grows distance layers in the configuration model and shows that, with high probability, layer sizes and interlayer edge counts remain sufficiently large over a logarithmic range.These bounds ensure many edges connect successive distance layers, creating enough randomness for distinct edge configurations.Source: C Proof for The Power of DE — Theorem… · pp. 17–19
  • For many distance layers, the probability that two sampled graphs share every relevant edge configuration is sufficiently small to make identical DE-labeled subtrees unlikely.The argument bounds each configuration probability and combines the bounds across logarithmically many layers.Source: C Proof for The Power of DE — Theorem… · pp. 17–21

D Discussion on node sets over irregular graphs

  • For irregular graphs, 1-WL color classes induce regular subgraphs with equitable cross-class neighborhoods, so DE may further distinguish nodes within those classes.The paper suggests that DE’s regular-graph capability can help break the regularity left unresolved by 1-WL.Source: D Discussion on node sets over… · p. 21

E Proof for The Limitation of DE-1 — Theorem 3.7

Theorem 3.7 identifies a limitation of DE-1: in connected distance-regular graphs with the same intersection array, distance-based subtree patterns remain identical. This follows because walk counts and landing-probability lists are determined by shortest-path distance, so distinguishing requires informative node or edge attributes.

E Proof for The Limitation of DE-1 — Theorem 3.7

  • DE-GNN-1 must rely on discriminatory node or edge attributes to distinguish nodes in connected distance-regular graphs sharing an intersection array.Without such attributes, the rooted DE-1-labeled subtrees are identical across the compared graphs.Source: E Proof for The Limitation of DE-1 —… · pp. 21–22
  • In a distance-regular graph, the intersection array fixes how many neighbors at each distance appear beneath every subtree node.Thus, subtrees rooted at any nodes in graphs with the same intersection array have the same DE-1 color spreading.Source: E Proof for The Limitation of DE-1 —… · p. 22
  • Walk counts of every length depend only on shortest-path distance and the common intersection array, not on vertex identities.The induction expresses each walk count through the neighboring distance levels determined by the intersection-array parameters.Source: E Proof for The Limitation of DE-1 —… · p. 22
  • K-hop aggregation does not necessarily reduce the required number of layers proportionally: both compared models need at least two layers in the illustrated case.DEA-GNN-1-2-hop cannot halve the depth needed by DE-GNN-1 for that distinction.Source: Figure 5 · p. 23
  • Because distance-regular graphs are regular, shortest-path distances and landing-probability lists are bijectively related, so replacing SPD with landing probabilities does not overcome this limitation.The same subtree argument therefore applies to the generalized DE-1 representation.Source: E Proof for The Limitation of DE-1 —… · pp. 22–23

F Proof for DEA-GNN— Corollary 3.8 and Further Discussion

The section shows that DEA-GNN can still fail on distance-regular graphs with identical intersection arrays, while multi-hop aggregation can distinguish almost all sampled regular-graph node sets under stated conditions.

Further Discussion

  • K-hop aggregation combines representations from nodes within K hops, but set aggregation can reduce feature discrimination and prevent a K-fold layer reduction.The two-tree example shows that DEA-GNN-1-2-hop may still require two layers although aggregation spans two hops.Source: F Proof for DEA-GNN— Corollary 3.8 and… · p. 23

Confirmation to the first question

  • DEA-GNN-1 must rely on discriminatory node or edge attributes to distinguish nodes in connected distance-regular graphs sharing an intersection array.Without such attributes, representations depend only on distance to the target and the common intersection array.Source: F Proof for DEA-GNN— Corollary 3.8 and… · pp. 23–24

Confirmation to the second question

  • For target sets of size p in uniformly sampled r-regular graphs with 3 ≤ r < (2 log n)^1/2, a proper DEA-GNN-p-K-hop distinguishes the sets with high probability within a logarithmic layer bound.The stated construction uses a constant ε and positive integer K, with layers below ⌈(1/2 + ε) log n / (K log(r−1))⌉.Source: F Proof for DEA-GNN— Corollary 3.8 and… · p. 24

Proof strategy

  • The proof uses distance-based layers and edge configurations across consecutive distance shells to propagate distinguishing differences to the target node.For K-hop aggregation, configurations concatenate the K adjacent-shell configurations and differences propagate after approximately ⌈k/K⌉ layers plus a constant.Source: F Proof for DEA-GNN— Corollary 3.8 and… · p. 24

G.1 Datasets

The experiments use three airport networks for node-role classification and three additional networks for link and triangle prediction, with task-specific baselines and ego-network-based implementations.

G.1 Datasets

  • Three airport networks support node-role classification, with airports labeled into four passenger-flow levels from connectivity patterns.Brazil-Airports, Europe-Airports, and USA-Airports contain 131, 399, and 1,190 nodes respectively.Source: §G.1 · p. 25
  • C.ele, NS, and PB support link and triangle prediction, with positive test links or triangles removed during training to avoid label leakage.The datasets range from a neural network and collaboration network to political web-page references.Source: §G.1 · p. 25

G.2 Baseline Details

  • The comparison includes GCN, GraphSAGE, GIN, Struc2vec, PGNN, and SEAL, covering WLGNNs, kernels, positional embeddings, and task-specific graph methods.GNN baselines use node degrees when attributes are unavailable to preserve inductive capability.Source: §G.2 · pp. 25–26
  • Task-specific readouts use a neural classifier for node roles and difference pooling followed by a trainable projection for link and triangle prediction.SEAL instead uses SortPooling over ego-network node representations for link prediction.Source: §G.2 · p. 26

G.3 DE-GNN Variants Details.

  • Mini-batch training extracts the union of L-hop ego-networks around the target node set, removing edges internal to the target set before applying the models.The union can be extracted by a single breadth-first search.Source: §G.3 · p. 26

S. For G′

This section details shortest-path and random-walk distance encodings, their use as node features or aggregation controls, and the empirical comparison of DEA-GNN variants.

Distance Encoding variants

  • DE-GNN-SPD encodes truncated shortest-path distances as one-hot node attributes, with dmax limiting the encoded neighborhood distance.Distances can be precomputed or obtained while traversing extracted ego-networks, and dmax ≤ L can reduce overfitting.Source: S. For G′ · p. 26
  • DE-GNN-LP encodes random-walk landing probabilities, which contain finer-grained distance information but do not always improve performance substantially in practice.Shortest-path distance can be inferred from the first non-zero random-walk feature.Source: S. For G′ · p. 27

Aggregation-controlled variants

  • DEA-GNN-SPD uses shortest-path encodings to control aggregation over direct, 2-hop, or 3-hop neighbors while retaining the same extra node features.Implementing L layers requires extracting ego-networks out to LK hops.Source: S. For G′ · p. 27
  • DEA-GNN-PR uses generalized PageRank-based propagation over the whole graph rather than ego-networks, with the PageRank restart value 0.9 chosen heuristically.Other PageRank scores, including heat-kernel and time-dependent variants, may also be used.Source: S. For G′ · p. 27

Model comparison

  • DEA-GNN-PR performs worse than DEA-GNN-SPD but remains substantially better than WLGNNs for link and triangle prediction.The authors attribute GDC’s weaker link-prediction performance to omitting DEs as node attributes.Source: S. For G′ · p. 27, Table 2 · p. 28

G.4 Model performance without validation datasets

The appendix reports performance under no-validation-set settings, hyperparameter procedures, and the scalability limitation of higher-order WL-style approaches.

G.4 Model performance without validation datasets

  • Using validation datasets in the main text is motivated by the fact that published Struc2vec and SEAL results used best testing performance during training.The no-validation appendix produces similar conclusions for the proposed models relative to baselines.Source: §G.4 · p. 28
  • Without validation sets, DEA-GNN variants significantly outperform the strongest baselines, SEAL and GIN, across the reported tasks.The additional results use average accuracy, while the accompanying table also reports AUC where applicable.Source: §G.4 · p. 28, Table 3 · p. 28, Table 4 · p. 28

G.5 Hyperparameters Tuning.

  • Hyperparameters are selected by grid search, and each model is trained to cross-entropy convergence with the best result over 20 random seeds reported.The listed hyperparameters and ranges are summarized in Table 5.Source: §G.5 · pp. 28–29, Table 5 · p. 29

H A Brief Introduction of Higher-Order Weisfeiler-Lehman Tests

  • Higher-order WL tests color k-tuples through iterative aggregation, but even 2-WL aggregates over n^2 tuples and may not exploit graph sparsity.Ring-GNN and PPGN target 2-WL expressive power but are reported as non-scalable and evaluated for entire-graph tasks.Source: H A Brief Introduction of Higher-Order… · p. 29

Related papers

Loading 2009.00142v4…