A kernel method for unsupervised structured network inference

Christoph Lippert, Oliver Stegle, Zoubin Ghahramani, Karsten M. Borgwardt

Introduction

Network inference—the task of predicting interactions (edges) between objects (nodes) based on their characteristics—is a cornerstone of bioinformatics and social science. However, existing kernel-based approaches often suffer from three major drawbacks: a heavy dependency on labeled training data, an assumption that edges are independent events, and a lack of statistical rigor in common heuristics.

This paper introduces NETHSIC, a novel unsupervised framework that uses the Hilbert-Schmidt Independence Criterion (HSIC) to infer network structures. By maximizing the statistical dependence between node attributes and graph topology, NETHSIC incorporates global network properties and provides a rigorous foundation for network inference tasks.

Methodology: The NETHSIC Framework

The core of the NETHSIC algorithm is the maximization of dependence between a kernel on node attributes ($K$) and a "node kernel" ($L_E$) that describes the nodes' positions within the graph topology $E$.

Node Kernels and Topological Priors

The authors define two primary types of node kernels to encode different structural expectations:

  • Local Effects: Such as 1-step random walks. The authors prove that using this kernel is mathematically equivalent to the common heuristic of connecting the most similar nodes.
  • Global Effects: These kernels capture broader network properties, where adding a single edge can change values for many node pairs. Examples include kernels based on node degree, closeness centrality, betweenness centrality, or common neighbors (squared adjacency matrix).

Optimization via Greedy Selection

Since finding the optimal graph is NP-hard, the authors utilize a greedy forward selection strategy. The algorithm begins with an empty graph and iteratively adds the edge that maximizes the HSIC objective until a target number of edges $m$ is reached.

The greedy forward selection algorithm used in NETHSIC to iteratively build the network structure by maximizing the HSIC objective.

Experimental Evaluation

The authors evaluated NETHSIC on four classic social network datasets: Krackhardt’s High-tech Managers, Freeman’s EIES Network, Countries Trade Data, and Padgett’s Florentine Families. These datasets serve as benchmarks where both node attributes and "gold standard" relationship networks are known.

Key Results

NETHSIC frequently outperformed standard unsupervised methods like Correlation Relevance Networks and Mutual Information networks. A significant finding was the power of global roles: in many social datasets, attributes predicted a node's structural role (e.g., its degree or centrality) better than they predicted specific pairwise similarities. Consequently, kernels based on node degree ($\Delta$-degr) and centrality often reached significantly higher Area Under the ROC Curve (AUC) values than simple similarity-based kernels.

Comprehensive performance comparison (AUC) of NETHSIC across various datasets and node kernels, demonstrating the superiority of global kernels in many scenarios.

Conclusion and Future Work

NETHSIC provides a "statistical 'aha' moment" by showing that intuitive practices, like connecting similar nodes, are specific cases of maximizing statistical dependence under local priors. By allowing for the inclusion of topological priors through different node kernels, researchers can tailor the inference process to specific structural expectations without needing labeled examples.

Future work will focus on improving computational scalability, as recomputing global kernels in every iteration is expensive. The authors suggest leveraging dynamic graph algorithms and exploring more sophisticated search strategies, such as Simulated Annealing, to further enhance performance and efficiency.

Summary updated

Abstract

Network inference is the problem of inferring edges between a set of real-world objects, for instance, interactions between pairs of proteins in bioinformatics. Current kernel-based approaches to this problem share a set of common features: (i) they are supervised and hence require labeled training data; (ii) edges in the network are treated as mutually independent and hence topological properties are largely ignored; (iii) they lack a statistical interpretation. We argue that these common assumptions are often undesirable for network inference, and propose (i) an unsupervised kernel method (ii) that takes the global structure of the network into account and (iii) is statistically motivated. We show that our approach can explain commonly used heuristics in statistical terms. In experiments on social networks, different variants of our method demonstrate appealing predictive performance.
BibTeX
@article{lippert2009kernel,
  author = {Christoph Lippert and Oliver Stegle and Zoubin Ghahramani and Karsten M. Borgwardt},
  title = {{A kernel method for unsupervised structured network inference}},
  journal = {AISTATS},
  year = {2009},
}
Figure