Transitivity-Preserving Graph Representation Learning for Bridging Local Connectivity and Role-based Similarity
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.
Code (3)
Tasks
Graph ClassificationGraph Representation LearningIsomorphism TestingLink PredictionNode ClassificationNode ClusteringRepresentation LearningSelf-Supervised LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Asymmetric Transitivity Preserving Graph Embedding
Graph embedding algorithms embed a graph into a vector space where the structure and the inherent properties of the graph are preserved. The existing graph embedding methods cannot preserve the asymmetric transitivity we…
Graph EmbeddingLink PredictionEntailment Graph Learning with Textual Entailment and Soft Transitivity
Typed entailment graphs try to learn the entailment relations between predicates from text and model them as edges between predicate nodes. The construction of entailment graphs usually suffers from severe sparsity and u…
Graph LearningNatural Language InferenceEntailment Graph Learning with Textual Entailment and Soft Transitivity
Typed entailment graphs try to learn the entailment relations between predicates from text and model them as edges between predicate nodes. The construction of entailment graphs usually suffers from severe sparsity and u…
Graph LearningNatural Language InferenceStrong Transitivity Relations and Graph Neural Networks
Local neighborhoods play a crucial role in embedding generation in graph-based learning. It is commonly believed that nodes ought to have embeddings that resemble those of their neighbors. In this research, we try to car…
Graph Neural NetworkNode ClassificationTransitivity Recovering Decompositions: Interpretable and Robust Fine-Grained Relationships
Recent advances in fine-grained representation learning leverage local-to-global (emergent) relationships for achieving state-of-the-art results. The relational representations relied upon by such methods, however, are a…