Graph Quality Matters on Revealing the Semantics Behind the Data in Physical World

The physical world is composed of graphs, such as the protein structures in life science, the patient relations in medical diagnosis, the user connections in social media, etc. Graphs help both build the world itself and understand the semantics behind the data for humans. However, how such graph structures work toward semantic representation is still unclear, where existing attempts focus on employing the graphs for special tasks. In this work, we first introduce two measures to evaluate graph quality, namely structural complexity and homophily. Structural complexity describes the quantity of graph structural information representing the graph structure's symmetry, and homophily describes the percentage of intra-class edges to quantify edge consistency. Using these two measures, we then discover the relationship between the graph quality and the corresponding performance for general tasks, that is the performance positively correlates with the structural complexity, and "J"-shaped correlates with homophily, which are proved mathematically. Based on these, we design a graph augmentation tool Graph$^+$+. Graph$^+$+ can enhance the natural graph structure and accordingly improve the general tasks. Empirical validation on tasks including Alzheimer's diagnosis and breast cancer subtype identification shows Graph$^+$+'s ability to improve both graph structure and task performance, revealing the underlying data semantics.