A network discovery service provides pattern-based techniques to discover relationships between hosts in a network employing address translation. Agents are deployed to hosts of the network. To configure an agent, the discovery service obtains outbound transmission data from the agent, which indicates outbound network transmissions that were established by the host. One or more unique outbound transmission patterns are provided to the agent, based on analysis of the outbound transmission data. Inbound transmission data is then received from the agents. The inbound transmission data indicates transmission events at the host devices, as well as the source for each of the open and close events. The inbound transmission data is analyzed to identify occurrences of the outbound transmission patterns. Based on the analysis, communication relationships between the host devices is determined. In some cases, communication relationships between individual processes on different hosts may be determined.