Transduction on directed graphs via absorbing random walks
In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circu...
Saved in:
Main Authors: | , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
2020
|
Subjects: | |
Online Access: | https://hdl.handle.net/10356/139874 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-139874 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-1398742020-05-22T05:54:21Z Transduction on directed graphs via absorbing random walks De, Jaydeep Zhang, Xiaowei Lin, Feng Li, Cheng School of Computer Science and Engineering Engineering::Computer science and engineering Random Walks on Directed Graphs Transductive Learning In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality by means of symmetrization, we propose a novel random walk approach on directed graphs using absorbing Markov chains, which can be regarded as maximizing the accumulated expected number of visits from the unlabeled transient states. Our algorithm is simple, easy to implement, and works with large-scale graphs on binary, multiclass, and multi-label prediction problems. Moreover, it is capable of preserving the graph structure even when the input graph is sparse and changes over time, as well as retaining weak signals presented in the directed edges. We present its intimate connections to a number of existing methods, including graph kernels, graph Laplacian based methods, and spanning forest of graphs. Its computational complexity and the generalization error are also studied. Empirically, our algorithm is evaluated on a wide range of applications, where it has shown to perform competitively comparing to a suite of state-of-the-art methods. In particular, our algorithm is shown to work exceptionally well with large sparse directed graphs with e.g., millions of nodes and tens of millions of edges, where it significantly outperforms other state-of-the-art methods. In the dynamic graph setting involving insertion or deletion of nodes and edge-weight changes over time, it also allows efficient online updates that produce the same results as of the batch update counterparts. ASTAR (Agency for Sci., Tech. and Research, S’pore) 2020-05-22T05:54:21Z 2020-05-22T05:54:21Z 2017 Journal Article De, J., Zhang, X., Lin, F., & Li, C. (2018). Transduction on directed graphs via absorbing random walks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 40(7), 1770-1784. doi:10.1109/TPAMI.2017.2730871 0162-8828 https://hdl.handle.net/10356/139874 10.1109/TPAMI.2017.2730871 28809671 2-s2.0-85028451868 7 40 1770 1784 en IEEE Transactions on Pattern Analysis and Machine Intelligence © 2017 IEEE. All rights reserved. |
institution |
Nanyang Technological University |
building |
NTU Library |
country |
Singapore |
collection |
DR-NTU |
language |
English |
topic |
Engineering::Computer science and engineering Random Walks on Directed Graphs Transductive Learning |
spellingShingle |
Engineering::Computer science and engineering Random Walks on Directed Graphs Transductive Learning De, Jaydeep Zhang, Xiaowei Lin, Feng Li, Cheng Transduction on directed graphs via absorbing random walks |
description |
In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality by means of symmetrization, we propose a novel random walk approach on directed graphs using absorbing Markov chains, which can be regarded as maximizing the accumulated expected number of visits from the unlabeled transient states. Our algorithm is simple, easy to implement, and works with large-scale graphs on binary, multiclass, and multi-label prediction problems. Moreover, it is capable of preserving the graph structure even when the input graph is sparse and changes over time, as well as retaining weak signals presented in the directed edges. We present its intimate connections to a number of existing methods, including graph kernels, graph Laplacian based methods, and spanning forest of graphs. Its computational complexity and the generalization error are also studied. Empirically, our algorithm is evaluated on a wide range of applications, where it has shown to perform competitively comparing to a suite of state-of-the-art methods. In particular, our algorithm is shown to work exceptionally well with large sparse directed graphs with e.g., millions of nodes and tens of millions of edges, where it significantly outperforms other state-of-the-art methods. In the dynamic graph setting involving insertion or deletion of nodes and edge-weight changes over time, it also allows efficient online updates that produce the same results as of the batch update counterparts. |
author2 |
School of Computer Science and Engineering |
author_facet |
School of Computer Science and Engineering De, Jaydeep Zhang, Xiaowei Lin, Feng Li, Cheng |
format |
Article |
author |
De, Jaydeep Zhang, Xiaowei Lin, Feng Li, Cheng |
author_sort |
De, Jaydeep |
title |
Transduction on directed graphs via absorbing random walks |
title_short |
Transduction on directed graphs via absorbing random walks |
title_full |
Transduction on directed graphs via absorbing random walks |
title_fullStr |
Transduction on directed graphs via absorbing random walks |
title_full_unstemmed |
Transduction on directed graphs via absorbing random walks |
title_sort |
transduction on directed graphs via absorbing random walks |
publishDate |
2020 |
url |
https://hdl.handle.net/10356/139874 |
_version_ |
1681059778117238784 |