A Broader Picture of Random-walk Based Graph Embedding
- URL: http://arxiv.org/abs/2110.12344v1
- Date: Sun, 24 Oct 2021 03:40:16 GMT
- Title: A Broader Picture of Random-walk Based Graph Embedding
- Authors: Zexi Huang, Arlei Silva, Ambuj Singh
- Abstract summary: Graph embedding based on random-walks supports effective solutions for many graph-related downstream tasks.
We develop an analytical framework for random-walk based graph embedding that consists of three components: a random-walk process, a similarity function, and an embedding algorithm.
We show that embeddings based on autocovariance similarity, when paired with dot product ranking for link prediction, outperform state-of-the-art methods based on Pointwise Mutual Information similarity by up to 100%.
- Score: 2.6546685109604304
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Graph embedding based on random-walks supports effective solutions for many
graph-related downstream tasks. However, the abundance of embedding literature
has made it increasingly difficult to compare existing methods and to identify
opportunities to advance the state-of-the-art. Meanwhile, existing work has
left several fundamental questions -- such as how embeddings capture different
structural scales and how they should be applied for effective link prediction
-- unanswered. This paper addresses these challenges with an analytical
framework for random-walk based graph embedding that consists of three
components: a random-walk process, a similarity function, and an embedding
algorithm. Our framework not only categorizes many existing approaches but
naturally motivates new ones. With it, we illustrate novel ways to incorporate
embeddings at multiple scales to improve downstream task performance. We also
show that embeddings based on autocovariance similarity, when paired with dot
product ranking for link prediction, outperform state-of-the-art methods based
on Pointwise Mutual Information similarity by up to 100%.
Related papers
- Contrastive Learning for Non-Local Graphs with Multi-Resolution
Structural Views [1.4445779250002606]
We propose a novel multiview contrastive learning approach that integrates diffusion filters on graphs.
By incorporating multiple graph views as augmentations, our method captures the structural equivalence in heterophilic graphs.
arXiv Detail & Related papers (2023-08-19T17:42:02Z) - Community detection in complex networks via node similarity, graph
representation learning, and hierarchical clustering [4.264842058017711]
Community detection is a critical challenge in analysing real graphs.
This article proposes three new, general, hierarchical frameworks to deal with this task.
We compare over a hundred module combinations on the Block Model graphs and real-life datasets.
arXiv Detail & Related papers (2023-03-21T22:12:53Z) - Similarity-aware Positive Instance Sampling for Graph Contrastive
Pre-training [82.68805025636165]
We propose to select positive graph instances directly from existing graphs in the training set.
Our selection is based on certain domain-specific pair-wise similarity measurements.
Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
arXiv Detail & Related papers (2022-06-23T20:12:51Z) - Representing Videos as Discriminative Sub-graphs for Action Recognition [165.54738402505194]
We introduce a new design of sub-graphs to represent and encode theriminative patterns of each action in the videos.
We present MUlti-scale Sub-Earn Ling (MUSLE) framework that novelly builds space-time graphs and clusters into compact sub-graphs on each scale.
arXiv Detail & Related papers (2022-01-11T16:15:25Z) - Bayesian Graph Contrastive Learning [55.36652660268726]
We propose a novel perspective of graph contrastive learning methods showing random augmentations leads to encoders.
Our proposed method represents each node by a distribution in the latent space in contrast to existing techniques which embed each node to a deterministic vector.
We show a considerable improvement in performance compared to existing state-of-the-art methods on several benchmark datasets.
arXiv Detail & Related papers (2021-12-15T01:45:32Z) - Multi-task Self-distillation for Graph-based Semi-Supervised Learning [6.277952154365413]
We propose a multi-task self-distillation framework that injects self-supervised learning and self-distillation into graph convolutional networks.
First, we formulate a self-supervision pipeline based on pre-text tasks to capture different levels of similarities in graphs.
Second, self-distillation uses soft labels of the model itself as additional supervision.
arXiv Detail & Related papers (2021-12-02T12:43:41Z) - Joint Graph Learning and Matching for Semantic Feature Correspondence [69.71998282148762]
We propose a joint emphgraph learning and matching network, named GLAM, to explore reliable graph structures for boosting graph matching.
The proposed method is evaluated on three popular visual matching benchmarks (Pascal VOC, Willow Object and SPair-71k)
It outperforms previous state-of-the-art graph matching methods by significant margins on all benchmarks.
arXiv Detail & Related papers (2021-09-01T08:24:02Z) - A Robust and Generalized Framework for Adversarial Graph Embedding [73.37228022428663]
We propose a robust framework for adversarial graph embedding, named AGE.
AGE generates the fake neighbor nodes as the enhanced negative samples from the implicit distribution.
Based on this framework, we propose three models to handle three types of graph data.
arXiv Detail & Related papers (2021-05-22T07:05:48Z) - Auto-weighted Multi-view Feature Selection with Graph Optimization [90.26124046530319]
We propose a novel unsupervised multi-view feature selection model based on graph learning.
The contributions are threefold: (1) during the feature selection procedure, the consensus similarity graph shared by different views is learned.
Experiments on various datasets demonstrate the superiority of the proposed method compared with the state-of-the-art methods.
arXiv Detail & Related papers (2021-04-11T03:25:25Z) - Graph embedding using multi-layer adjacent point merging model [23.706877029336415]
We propose a novel graph embedding method using a multi-layer adjacent merging point model.
This embedding method allows us to extract different subgraph patterns from train-data.
numerical evaluations demonstrate that our proposed method outperforms many state-of-the-art methods.
arXiv Detail & Related papers (2020-10-28T05:35:04Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.