The goal of association rule mining is to discover the association or correlation between data item sets, which is an important topic in data mining. For very large data sets, traditional algorithms are inefficient. This paper improves them and gives an association rule mining algorithm based on graph theory and maximum path. The algorithm first constructs the transaction sets into a Boolean matrix. After the matrix is cleaned, the transaction set is converted into the form of a graph, and then an adjacency matrix is generated according to the association rule graph. When the step size is k and k＞2, traverse from the first non-zero element by line to find the path with the largest weight, and the row and column index of the connected elements is the frequent k+2 item set. Experimental results show that the algorithm firstly reduces the number of scans of the data set. Secondly, for large data sets, compared with the traditional Apriori algorithm, it can significantly shorten the time and greatly improve the efficiency.