Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity Article Swipe

MAKE IMPACT

Van Thuy Hoang , O‐Joun Lee · YOU? · · 2023 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2308.09517

Graph representation learning (GRL) methods, such as graph neural networks and graph transformer models, have been successfully used to analyze graph-structured data, mainly focusing on node classification and link prediction tasks. However, the existing studies mostly only consider local connectivity while ignoring long-range connectivity and the roles of nodes. In this paper, we propose Unified Graph Transformer Networks (UGT) that effectively integrate local and global structural information into fixed-length vector representations. First, UGT learns local structure by identifying the local substructures and aggregating features of the $k$-hop neighborhoods of each node. Second, we construct virtual edges, bridging distant nodes with structural similarity to capture the long-range dependencies. Third, UGT learns unified representations through self-attention, encoding structural distance and $p$-step transition probability between node pairs. Furthermore, we propose a self-supervised learning task that effectively learns transition probability to fuse local and global structural features, which could then be transferred to other downstream tasks. Experimental results on real-world benchmark datasets over various downstream tasks showed that UGT significantly outperformed baselines that consist of state-of-the-art models. In addition, UGT reaches the expressive power of the third-order Weisfeiler-Lehman isomorphism test (3d-WL) in distinguishing non-isomorphic graph pairs. The source code is available at https://github.com/NSLab-CUK/Unified-Graph-Transformer.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2308.09517

PDF

https://arxiv.org/pdf/2308.09517

OA Status

green

Cited By

2

Related Works

10

OpenAlex ID

https://openalex.org/W4386044015

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4386044015

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2308.09517

Digital Object Identifier

Title

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

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2023

Year of publication

Publication date

2023-08-18

Full publication date if available

Authors

Van Thuy Hoang, O‐Joun Lee

List of authors in order

Landing page

https://arxiv.org/abs/2308.09517

Publisher landing page

PDF URL

https://arxiv.org/pdf/2308.09517

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2308.09517

Direct OA link when available

Concepts

Computer science, Theoretical computer science, Graph isomorphism, Discriminative model, Graph, Feature learning, Artificial intelligence, Line graph

Top concepts (fields/topics) attached by OpenAlex

Cited by

2

Total citation count in OpenAlex

Citations by year (recent)

2025: 2

Per-year citation counts (last 5 years)

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload