Detecting Localized Categorical Attributes on Graphs
arXiv:1604.00657 · doi:10.1109/TSP.2017.2666772
Abstract
Do users from Carnegie Mellon University form social communities on Facebook? Do signal processing researchers from tightly collaborate with each other? Do Chinese restaurants in Manhattan cluster together? These seemingly different problems share a common structure: an attribute that may be localized on a graph. In other words, nodes activated by an attribute form a subgraph that can be easily separated from other nodes. In this paper, we thus focus on the task of detecting localized attributes on a graph. We are particularly interested in categorical attributes such as attributes in online social networks, ratings in recommender systems and viruses in cyber-physical systems because they are widely used in numerous data mining applications. To solve the task, we formulate a statistical hypothesis testing problem to decide whether a given attribute is localized or not. We propose two statistics: graph wavelet statistic and graph scan statistic, both of which are provably effective in detecting localized attributes. We validate the robustness of the proposed statistics on both simulated data and two real-world applications: high air-pollution detection and keyword ranking in a co-authorship network collected from IEEE Xplore. Experimental results show that the proposed graph wavelet statistic and graph scan statistic are effective and efficient.
arXiv commentAccepted for publication in the IEEE Transactions on Signal Processing
References in corpus (25)
- Community structure in social and biological networks
- Community detection in graphs
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Link communities reveal multiscale complexity in networks
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Community Detection in Networks with Node Attributes
- Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Signals on Graphs: Uncertainty Principle and Sampling
- Signal Recovery on Graphs: Variation Minimization
- Sampling of graph signals with successive local aggregations
- Stationary signal processing on graphs
- Stationary Graph Processes and Spectral Estimation
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- Clustering on Multi-Layer Graphs via Subspace Analysis on Grassmann Manifolds
- Kernel-based Reconstruction of Graph Signals
- Detection of an anomalous cluster in a network
- A Spectral Graph Uncertainty Principle
- Local-set-based Graph Signal Reconstruction
- Learning parametric dictionaries for graph signals
- Trend Filtering on Graphs
- Signal Representations on Graphs: Tools and Applications
- Sampling and Reconstruction of Sparse Signals on Circulant Graphs - An Introduction to Graph-FRI
- Community Detection in Networks with Node Features