Method and system for detecting anomalies in a bipartite graph

1. A method of detecting anomalies from a bipartite graph, comprising:

analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix, the analyzing of the graph comprising updating the row-cluster membership and the column-cluster membership; and

in a processor, detecting the anomalies from the non-negative residual matrix.

2. The method of claim 1 , wherein the anomalies comprise abnormal nodes and edges in the bipartite graph.

3. The method of claim 1 , further comprising:

generating the graph from a data set,

wherein the analyzing comprises inferring the row-cluster membership, column-cluster membership and non-negative residual matrix from the graph.

4. The method of claim 3 , wherein the detecting of anomalies comprises flagging abnormalities in the non-negative residual matrix.

5. The method of claim 1 , wherein the bipartite graph comprises a people-activity graph and the anomalies comprise abnormal human behavior.

6. The method of claim 5 , further comprising:

generating the people-activity graph from activity logs of a set of people,

wherein the analyzing comprises inferring people-community membership, community-activity membership and a non-negative people-activity residual matrix; and

wherein the detecting of anomalies comprises flagging the abnormal human behavior from the non-negative people-activity residual matrix.

7. The method of claim 6 , wherein the inferring of the people-community membership, community-activity membership and the non-negative people-activity residual matrix comprises:

setting an initial people-community membership, an initial community-activity membership, and an initial non-negative people-activity residual matrix;

updating the initial people-community membership; and

updating the initial community-activity membership.

8. The method of claim 7 , wherein the updating of the initial people-community membership comprises:

fixing and/or freezing the community-activity membership; and

re-calculating a strength of each person of the set of people belonging to a community including the set of people.

9. The method of claim 6 , wherein the inferring of the people-community membership, community-activity membership and the non-negative people-activity residual matrix comprises:

setting an initial non-negative people-activity residual matrix;

inferring a rank-1 people-community membership and a rank-1 community-activity membership; and

updating the non-negative people-activity residual matrix.

10. The method of claim 9 , wherein the inferring of the rank-1 people-community membership and the rank-1 community-activity membership comprises:

setting an initial rank-1 people-community membership, an initial rank-1 community-activity membership, and an initial non-negative people-activity residual matrix;

updating the initial rank-1 people-community membership; and

updating the initial rank-1 community-activity membership.

11. The method of claim 10 , wherein the updating of the initial rank-1 people-community membership comprises:

fixing and/or freezing the rank-1 community-activity membership; and

re-calculating a strength of each person of the set of people belonging to a community including the set of people.

12. The method of claim 1 , wherein the bipartite graph comprises an Internet Protocol (IP) source-destination graph and the anomalies comprise abnormal IP addresses.

13. The method of claim 12 , further comprising:

generating an IP source-destination graph from IP trace logs,

wherein the analyzing comprises inferring an IP source-role membership, an IP destination-role membership and a non-negative IP source-destination residual matrix; and

wherein the detecting of anomalies comprises flagging abnormal IP addresses from the non-negative IP source-destination residual matrix.

14. The method of claim 1 , wherein the updating of the initial row-cluster membership and the initial column-cluster membership, comprises iteratively updating the initial row-cluster membership and updating the initial column-cluster membership.

15. The method of claim 1 , wherein the analyzing of the graph comprises setting an initial row-cluster membership and an initial column-cluster membership, and the updating of the row-cluster membership and the column-cluster membership comprises updating the initial row-cluster membership and the initial column-cluster membership.

16. A system for detecting anomalies from a bipartite graph, comprising:

an analyzer for analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix, the analyzing of the graph comprising updating the row-cluster membership and the column-cluster membership; and

a detector for detecting the anomalies from the non-negative residual matrix.

17. The system of claim 16 , further comprising:

a graph generator for generating the graph from a data set,

wherein the analyzer infers the row-cluster membership, column-cluster membership and non-negative residual matrix from the graph, and

wherein the detector comprises a flagging device for flagging abnormalities in the non-negative residual matrix.

18. The system of claim 16 , wherein the analyzer comprises:

an initial setting device for setting an initial row-cluster membership, an initial column-cluster membership, and an initial non-negative residual matrix;

an updater for updating the initial row-cluster membership, and updating the initial column-cluster membership.

19. The system of claim 18 , wherein the updater for updating the initial column-cluster membership comprises:

a fixing/freezing device for fixing and/or freezing the column-cluster membership; and

a strength re-calculator for re-calculating a strength of each member in the column-cluster membership.

20. The system of claim 16 , wherein the analyzer comprises:

a setting device for setting an initial non-negative residual matrix; and

an updater for updating the initial non-negative residual matrix,

wherein the analyzer infers a rank-1 row-cluster membership and a rank-1 column-cluster membership by:

setting an initial rank-1 row-cluster membership, an initial rank-1 column-cluster membership, and an initial non-negative residual matrix;

updating the initial rank-1 row-cluster membership; and

updating the initial rank-1 column-cluster membership.

21. The system of claim 20 , wherein the updater for updating the initial rank-1 row-cluster membership comprises:

a fixing/freezing device for fixing and/or freezing the rank-1 column-cluster membership; and

a strength re-calculator for re-calculating a strength of each member in the column-cluster membership.

22. A programmable storage medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method of detecting anomalies from a bipartite graph, the method comprising:

analyzing the graph to determine a row-cluster membership, a column-cluster membership and a non-negative residual matrix, the analyzing of the graph comprising updating the row-cluster membership and the column-cluster membership; and

in a processor, detecting the anomalies from the non-negative residual matrix.