Abstract: An intrusion detection method based on graph theory was proposed. The method introduced the idea of graph theory into intrusion detection system. By transferring the similarity relationship between data objects into the adjacency matrix in the graph, and transferring the adjacency matrix into an association matrix, it could reflect the relationships between data objects clearly. The steepest descent method was used to calculate the optimal transition matrix, and obtain the result of data clustering by transferring the association matrix into a block diagonal matrix, which could identify clusters of normal data and intrusion data. Meanwhile, KDD CUP 1999 dataset was used to simulate. The result shows that the proposed method has a higher detection probability under the condition of low constant false alarm rate compared with fuzzy Cmeans clustering algorithm.