Fast Random Walk Graph Kernel
Abstract
Random walk graph kernel has been used as an important tool for various data mining tasks including classification and similarity computation. Despite its usefulness, however, it suffers from the expensive computational cost which is at least O(n3) or O(m2) for graphs with n nodes and m edges. In this paper, we propose ARK, a set of fast algorithms for random walk graph kernel computation. ARK is based on the observation that real graphs have much lower intrinsic ranks, compared with the orders of the graphs. ARK exploits the low rank structure to quickly compute random walk graph kernels in O(n2) or O(m) time. Experimental results show that our method is up to 97,865× faster than the existing algorithms, while providing more than 91.3% of the accuracies.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Graph Kernels are quite slow unless approximated.
“Graph Kernels [42] have been proposed as a way to use relational data as part of the classification process, but are quite slow unless approximated [19].”
From DeepWalk: online learning of social representations (2014) · cites this paper as [19]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Trefethen, L. N., & Bau, III (1997) · doi:10.1137/1.9780898719574 · Cited by 3,301 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
DeepWalk: online learning of social representations
Perozzi, B., Al-Rfou, R., & Skiena, S. (2014) · Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/2623330.2623732 · Cited by 10,123 · see citing works
Graph based anomaly detection and description: a survey
Akoglu, L., Tong, H., & Koutra, D. (2015) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-014-0365-y · Cited by 1,504 · see citing works
Self-citationCombating Fake News: A Survey on Identification and Mitigation Techniques
Sharma, K., Qian, F., Jiang, H., Ruchansky, N., Zhang, M., & Liu, Y. (2019) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3305260 · Cited by 514 · see citing works
Random Walks: A Review of Algorithms and Applications
Xia, F., Liu, J., Nie, H., Fu, Y., Wan, L., & Kong, X. (2020) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2019.2952908 · Cited by 295 · see citing works
- Authors
- Kang, U., Tong, H., & Sun, J.
- Affiliations
- Carnegie Mellon University (US)
- Venue
- Proceedings of the 2012 SIAM International Conference on Data Mining
- Published
- 2012-04-26
- Pages
- 828-838
- OpenAlex
- W2407879741
- Cited by
- 127
- References
- 1
- Citations by year
- 2026: 5 · 2025: 7 · 2024: 7 · 2023: 13 · 2022: 7 · 2021: 15 · 2020: 10 · 2019: 14 · 2018: 10 · 2017: 14 · 2016: 10 · 2015: 5 · 2014: 5 · 2013: 5
- FWCI
- 3.41
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- SIAM International Conference on Data Mining (publishedVersion)
- Funders
- Army Research Laboratory (W911NF, W911NF-09-2-0053)
- Topics
- Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Graph Theory and Algorithms
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
- Physical Sciences › Mathematics › Geometry and Topology › Graph theory and applications
- Keywords
- low-rank approximation, computational efficiency, graph classification, similarity measurement, ark
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
