This paper presents a novel unsupervised method for structural damage diagnosis, which transforms the problem of structural damage diagnosis into the problem of identifying anomalous data in monitoring data. The method establishes the sensor interrelationships based on the graph structure, optimizes the hyperparameters of the graph neural network (GNN) model, and realizes the structural response prediction. By calculating the discrepancy between the predicted response and the monitoring data, the method identifies the anomalies to facilitate the identification and localization of structural damage. The efficiency of the proposed method for bolt loosening detection was evaluated through the analysis of acceleration data collected from a vibrating grandstand simulator and strain data from a wind tunnel test of a scaled tower model. The experimental results indicated that the established connections can provide a preliminary indication of the relative importance of the sensors, which may also be regarded as a metric for each node in the structure. The proposed method is effective in the detection and localization of minor damage in infrastructure structures.