Research map / Graph learning / Graph self-supervised learning
Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-Based Similarity
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Unified Graph Transformer Networks (UGT), which samples k-hop plus structurally similar "virtual edge" context nodes and uses structural identity and p-step transition probability biases in self-attention, pre-trained with a transition-probability preservation objective, for node and graph-level tasks.
Problem
Graph transformers and GNNs capture local connectivity but miss long-range dependencies and node role-based (structural) similarity, and struggle to fuse local and global structural features into one representation.
Approach
Construct virtual edges between structurally similar distant nodes (based on DTW over ordered degree sequences), then encode structural distance (from hierarchical degree-based structural identity) and p-step transition probabilities as attention biases, pre-trained to preserve transition probabilities via a noise-contrastive/matrix factorization loss.
Key results
- On node classification, UGT reaches 88.74% on Cora and 76.08% on Citeseer, and 80.00% on Brazil, outperforming listed baselines in most datasets.
- UGT distinguishes all Graph8c and nine SRG non-isomorphic pairs (0 undistinguished), while GNNs such as GCN, GAT, GIN fail on SRGs.
- Ablation on Cora shows virtual edges combined with structural identity and Laplacian PE give the best accuracy (87.80% vs 86.32% without), with mixed results on other datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add pre-training (ablation) | UGT · Cora | accuracy: 74.63 $\pm$2.93 -> 88.74$\pm$0.6 | Helped |
| add Laplacian positional embeddings (λ) (ablation) | UGT · Graph8c | undistinguished graph pairs: 355 -> 0 | Helped |
| add structural identity (I) (ablation) | UGT · Graph8c | undistinguished graph pairs: 36,857.0 -> 0 | Helped |
| add virtual edges (ablation) | UGT · Cora | accuracy: 86.32 -> 85.40 | Mixed |
| add virtual edges (ablation) | UGT · Cornell | accuracy: 66.67 -> 55.56 | Hurt |
| add structural identity (I) (ablation) | UGT with virtual edges · Cornell | accuracy: 50.0 -> 66.67 | Helped |
| add Laplacian positional embeddings (λ) (ablation) | UGT with virtual edges · Brazil | accuracy: 76.92 -> 69.23 | Hurt |
| add structural distance (D) (ablation) | UGT · Cora | accuracy: 85.00 -> 86.87 | Helped |
| add transition probability (M) (ablation) | UGT · Brazil | accuracy: 76.92 -> 84.62 | Helped |
| add transition probability (M) (ablation) | UGT · Cornell | accuracy: 55.56 -> 61.11 | Helped |
| use UGT instead of GPS | node classification · Cora | accuracy: 62.12$\pm$1.00 -> 88.74$\pm$0.6 | Helped |
| use UGT instead of ANS-GT | node classification · Film | accuracy: 39.80$\pm$0.75 -> 36.84$\pm$0.62 | Hurt |
Surprising findings
- Ablations show that removing virtual edges can give better clustering performance, which the authors attribute to virtual edges confusing actual connectivity.
- UGT without pre-training underperforms the full model substantially on several datasets (e.g., Europe 44.94 vs 56.92), and GT and SAGE beat UGT on some heterophily datasets.
Limitations
- Global structural sampling over the whole graph incurs computational complexity that may hinder use on large graphs.
- Ablation results are mixed; virtual edges do not uniformly help and can reduce clustering performance.
- Claims of 3d-WL expressive power are supported mainly by empirical tests on small benchmark graphs (Graph8c, SRGs) rather than a formal proof in the text.
Experimental setup
Datasets: Brazil air-traffic Europe air-traffic USA air-traffic Chameleon Squirrel Film Cornell Texas Wisconsin Cora Citeseer Enzymes
Benchmarks: Brazil Europe USA Chameleon Squirrel Film Cornell Texas Wisconsin Cora Citeseer Enzymes
Metrics: accuracy conductance modularity number of undistinguished non-isomorphic graph pairs
Baselines: GCN GCNII GIN GAT GATv2 GraphSAGE WRGAT DeeperGCN GT SAN SAT GPS
Builds on: Graphormer Struc2vec GraRep Laplacian positional encoding
Closest papers by meaning
- Structure-Aware Transformer for Graph Representation Learning (ICML 2022 · similarity 0.91)
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (NeurIPS 2020 · similarity 0.90)
- Graph Transformer Networks (NeurIPS 2019 · similarity 0.90)
- Multiplex Graph Representation Learning with Homophily and Consistency (AAAI 2025 · similarity 0.88)
- Structural Information Enhanced Graph Representation for Link Prediction (AAAI 2024 · similarity 0.88)
- NLGT: Neighborhood-based and Label-enhanced Graph Transformer Framework for Node Classification (AAAI 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.