Random Walk Sampling for Big Data over Networks
It has been shown recently that graph signals with small total variation can be accurately recovered from only few samples if the sampling set satisfies a certain condition, referred to as the network nullspace property. Based on this recovery condition, we propose a sampling strategy for smooth graph signals based on random walks. Numerical experiments demonstrate the effectiveness of this approach for graph signals obtained from a synthetic random graph model as well as a real-world dataset.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
On Random Walk Based Graph Sampling
Random walk based graph sampling has been recognized as a fundamental technique to collect uniform node samples from a large graph. In this paper, we first present a comprehensive analysis of the drawbacks of three widel…
Graph SamplingUniNet: Scalable Network Representation Learning with Metropolis-Hastings Sampling
Network representation learning (NRL) technique has been successfully adopted in various data mining and machine learning applications. Random walk based NRL is one popular paradigm, which uses a set of random walks to c…
Representation LearningWalking with Perception: Efficient Random Walk Sampling via Common Neighbor Awareness
Random walk is widely applied to sample large-scale graphs due to its simplicity of implementation and solid theoretical foundations of bias analysis. However, its computational efficiency is heavily limited by the slow …
Computational EfficiencyMemory-aware framework for fast and scalable second-order random walk over billion-edge natural graphs
Second-order random walk is an important technique for graph analysis. Many applications including graph embedding, proximity measure and community detection use it to capture higher-order patterns in the graph, thus imp…
Community DetectionGraph EmbeddingGAT-RWOS: Graph Attention-Guided Random Walk Oversampling for Imbalanced Data Classification
Class imbalance poses a significant challenge in machine learning (ML), often leading to biased models favouring the majority class. In this paper, we propose GAT-RWOS, a novel graph-based oversampling method that combin…
Graph Attentionimbalanced classification