The smart features of modern cars are enabled by a number of Electronic Control Units (ECUs) components that communicate through an in-vehicle network, known as Controller Area Network (CAN) bus. The fundamental challenge is the security of the communication link where an attacker can inject messages (e.g., increase the speed) that may impact the safety of the driver. Most of existing practical IDS solutions rely on the knowledge of the identity of the ECUs, which is proprietary information. This paper proposes a message injection attack detection solution that is independent of the IDs of the ECUs. First, we represent the sequencing of the messages in a given time-interval as a direct graph and compute the similarities of the successive graphs using the cosine similarity and Pearson correlation. Then, we apply threshold, change point detection, and Long Short-Term Memory (LSTM)-Recurrent Neural Network (RNN) to detect and predict malicious message injections into the CAN bus. The evaluation of the methods using a dataset collected from a moving vehicle under malicious RPM and speed reading message injections show a detection accuracy of 97.32% and detection speed of 2.5 milliseconds when using a threshold method. The performance metrics makes the IDS suitable for real-time control mechanisms for vehicle resiliency to cyber attacks.