A reliable automated malware classification approach with substantially low false positive rates is provided. Graph-based local and/or global file relationships are used to improve malware classification along with a feature selection algorithm. File relationships such as containing, creating, copying, downloading, modifying, etc. are used to assign malware probabilities and simultaneously reduce the false positive and false negative rates on executable files.