Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-Based Similarity

Van Thuy Hoang, O-Joun LeeAAAI 2024 · DOI

TL;DR

This paper introduces Unified Graph Transformer Networks (UGT), a novel approach to graph representation learning that effectively captures both local and global structural information. By introducing "virtual edges" between structurally similar nodes and a self-supervised task to preserve transition probabilities, UGT achieves state-of-the-art performance on various downstream tasks and demonstrates a stronger ability to distinguish non-isomorphic graphs than existing methods.

What Problem Does This Paper Address?

Graph representation learning (GRL) methods, like Graph Neural Networks (GNNs) and graph transformers, are powerful tools for analyzing graph-structured data. However, existing models often struggle with two key limitations:

  1. Ignoring Long-Range and Role-Based Similarity: Many GNNs and transformers primarily focus on local connectivity (i.e., immediate neighbors). This overlooks important long-range dependencies and the concept of "role-based similarity," where nodes might have similar functions or structural roles within the graph even if they are not directly connected or even far apart.
  2. Difficulty Integrating Local and Global Information: Effectively combining local structural features (like substructures) with global structural information (like node roles or overall graph topology) into a single, unified vector representation remains a challenge. This integration is crucial for tasks requiring a holistic understanding of the graph.

The paper argues that current methods, even those using positional encodings like Laplacian Eigenvectors, fail to adequately capture the similarity between local substructures and struggle to bridge the gap between local and global graph properties.

Methods

The proposed Unified Graph Transformer Networks (UGT) address these limitations through several novel components:

  • Unified Graph Transformer Networks (UGT): This is the core framework. It aims to learn unified representations that capture both local and global structural information.
  • Virtual Edges for Structural Similarity: UGT constructs "virtual edges" to connect distant nodes that are structurally similar. This similarity is determined by comparing ordered degree sequences within k-hop neighborhoods, using a dynamic time warping (DTW) approach similar to Struc2vec. This explicitly bridges long-range structural dependencies.
  • Structural Identity and Distance: To better capture local structure and role-based similarity, UGT introduces:
  • Structural Identity (I): Based on hierarchical role-based information (min, max, mean, std dev of degrees up to k-hop).
  • Structural Distance (d): A measure of similarity between structural identities.
  • Transition Probability for Global Information: To fuse local and global information, UGT leverages the p-step transition probability between nodes. This captures the awareness of connectivity and paths between nodes, reflecting global structure.
  • Self-Supervised Learning Task: A novel self-supervised learning objective is proposed to preserve these transition probabilities. It uses noise contrastive estimation to maximize the probability of paths connecting structurally similar nodes while minimizing it for unrelated pairs. This helps the model learn representations that reflect global structure.
  • Structural Identity in Self-Attention: The structural identity (I) is incorporated into the self-attention mechanism within each transformer layer, enhancing the model's ability to distinguish non-isomorphic substructures.

Datasets

The paper evaluates UGT on a variety of datasets across different tasks:

  • Node Clustering & Node Classification: Eleven publicly available datasets are used, covering homophily and heterophily graphs across domains like Air-traffic networks, Webpage networks, and Citation networks.
  • Graph Classification: Five datasets are used: Enzymes, Proteins, NCI1, NCI9 (from TUDataset), and OGBG MolHIV.
  • Isomorphism Testing: Graph8c and five Strongly Regular Graphs (SRGs) datasets are used, specifically chosen for containing 1d-WL and 3d-WL equivalent graph pairs to test the model's ability to distinguish non-isomorphic graphs.

Key Insights and Ideas

  • Virtual Edges are Key: The introduction of virtual edges to connect structurally similar but distant nodes is a powerful mechanism for capturing long-range dependencies that traditional local aggregation methods miss.
  • Role-Based Similarity Matters: Explicitly modeling structural similarity, independent of node features or direct connectivity, is crucial for understanding node roles and bridging gaps in graph structure.
  • Transition Probabilities as a Unifier: Using p-step transition probabilities provides a principled way to integrate local (k-hop) and global structural information, creating a more comprehensive representation.
  • Beyond Laplacian Eigenvectors: The paper highlights that standard positional encodings like Laplacian Eigenvectors might not fully capture structural similarity, leading to false signals for the model. UGT's structural identity and distance offer a more nuanced approach.
  • Stronger Isomorphism Testing: UGT's ability to reach third-order Weisfeiler-Lehman (3d-WL) power is a significant finding, indicating a superior capacity to distinguish complex graph structures compared to many existing GNNs.

Key Results

  • State-of-the-Art Performance: UGT significantly outperformed baseline models (GNNs and graph transformers) on node clustering, node classification, and graph classification tasks across multiple benchmark datasets.
  • Node Clustering: UGT achieved superior performance in terms of conductance and modularity, demonstrating its ability to capture graph density and community structures.
  • Node Classification: UGT showed significant improvements, particularly on heterophily graphs, by effectively capturing long-term dependencies and distinguishing similar substructures (roles).
  • Isomorphism Testing: UGT successfully distinguished non-isomorphic graph pairs up to 3d-WL, outperforming many baselines that failed on more complex SRG datasets.
  • Sensitivity Analysis: The performance of UGT generally improved with larger k-hop neighborhoods and the inclusion of virtual edges, suggesting the importance of both local context and long-range structural connections.

Limitations and Future Work

  • Computational Complexity: The paper acknowledges that the sampling technique for virtual edges and the computation of structural distance can lead to high computational complexity, especially for very large graphs.
  • Future Work: The authors plan to address the complexity issue by exploring graph coarsening and within-community proximity techniques. They also aim to further investigate the model's ability to learn large-scale graphs.

Summary updated

BibTeX
@inproceedings{hoang2024transitivity,
  author = {Van Thuy Hoang and O-Joun Lee},
  title = {{Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-Based Similarity}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i11.29138},
}
Figure