A problem that frequently occurs when mining complex networks, is selecting algorithms with which to rank the relevance of nodes to metadata groups characterized by a small number of examples. The best algorithms are often found through experiments on labeled networks or unsupervised structural community quality measures.
However, new networks could exhibit characteristics different from the labeled ones, whereas structural community quality measures favor dense congregations of nodes but not metadata groups spanning a wide breadth of the network. To avoid these shortcomings, the FuturePulse team from CERTH-ITI, Emmanouil Krasanakis , Symeon Papadopoulos and Yiannis Kompatsiaris in the research paper ‘Unsupervised evaluation of multiple node ranks by reconstructing local structures’ propose using unsupervised measures that assess node rank quality across multiple metadata groups through their ability to reconstruct the local structures of network nodes; these are retrieved from the network and not assumed.
The authors explore three types of local structures:
- linked nodes
- nodes up to two hops away
- nodes forming triangles
The team first compared the resulting measures alongside unsupervised structural community quality ones to the AUC and NDCG of supervised evaluation in one synthetic and four real-world labelled networks. As the FuturePulse team explains “the experiments suggest that the proposed local structure measures are often more accurate for unsupervised pairwise comparison of ranking algorithms, especially when few example nodes are provided”. Furthermore, the ability to reconstruct the extended neighborhood, which is called HopAUC, manages to select a near-best among many ranking algorithms in most networks.
In addition, the authors mention that future research can move in the direction of providing a unified framework between the unsupervised measures presented in this work, for example by combining their assessments. Last but not least, Emmanouil Krasanakis, Symeon Papadopoulos and Yiannis Kompatsiaris pinpoint that semi-supervised network mining algorithms that involve unsupervised extraction of node ranks is possible to be augmented with unsupervised measures of rank quality that select a different node ranking algorithm for each network.
You can read the research paper ‘Unsupervised evaluation of multiple node ranks by reconstructing local structures’ here.