Network administrators are faced with a large amount of network data that they need to sift through to analyze user behaviors and detect anomalies. Through a network monitoring tool, we obtained TCP and UDP connection records together with additional information of the associated users and software in an enterprise network. Instead of using traditional payload inspection techniques, we propose a method that clusters such network traffic data by using relations between entities so that it can be analyzed for frequent behaviors and anomalies. Relational methods like Markov Logic Networks is able to avoid the feature extraction stage and directly handle multi-relation situations. We extend the common pairwise representation in relational models by adopting set evidence to build a better objective for the network service clustering problem. The automatic clustering process helps the administrator filter out normal traffic in shorter time and get an abstract overview of opening transport layer ports in the whole network, which is beneficial for assessing network security risks. Experimental results on synthetic and real datasets suggest that our method is able to discover underlying services and anomalies (malware or abused ports) with good interpretations. © 2010 ACM.