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.
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.
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