Many real applications can be modeled using bipartite

graphs, such as users vs. files in a P2P system, traders vs.

stocks in a financial trading system, conferences vs. authors

in a scientific publication network, and so on. The

connections between two entities are the key on mining such

a graph. In particular, we propose algorithms to compute

the neighborhood for each node using random walk with

restarts and graph partitioning; we also propose algorithms

to identify abnormal nodes, using neighborhood information.

We evaluate the quality of neighborhoods based on

semantics of the datasets, and we also measure the performance

of the anomaly detection algorithm with manually

injected anomalies. Both effectiveness and efficiency of

the methods are confirmed by experiments on several real

datasets.