A novel mathematical model for simultaneous optimization of a property-based water-allocation and heat-exchange network (WAHEN) is presented in this work, where both linear and nonlinear dependent properties are taken into account. Specifically, state-space representation is modified to capture the structural characteristics of the property-based WAHEN, and a mixed-integer nonlinear programming (MINLP) model is formulated correspondingly to minimize the total annualized cost (TAC) of the network. In the proposed model, not only are property and energy integrations carried out simultaneously, but all possible waste regeneration opportunities are considered as well. To enhance the solution quality, sampling and spectral clustering techniques are introduced to capture the common characteristics of classes of good networks and guide the refined search toward a potential global optimum. Three examples are presented in this work to demonstrate the validity and advantages of the proposed approach.