Introduction
In graph machine learning, predicting node attributes—such as demographic data or behavioral labels—is a fundamental task. Traditionally, researchers have categorized these problems into two broad groups: within-network (predicting labels in a single graph) and across-network (training on one graph and predicting on another). However, this paper argues that this binary classification is insufficient and often leads to misleading performance evaluations.
A New Taxonomy for Node Attribute Prediction
The authors propose a more nuanced taxonomy that distinguishes between three distinct tasks based on node sets and the network generating process (NGP).
- Within-Network: Training and testing on the same set of nodes within a single network.
- Across-Layer: Training on one set of interactions (e.g., phone calls) and predicting on another (e.g., text messages) for the same set of nodes. Because node identities are preserved, models can leverage node-specific behavior across different interaction types.
- Across-Network: Training on one network and predicting on a completely disjoint network (e.g., different student populations at different universities). This is the most difficult task as it requires learning generalizable patterns that transcend specific node identities.
The "performance gap" arises because many studies claim to solve across-network problems but actually evaluate on across-layer datasets. In across-layer tasks, node identities are preserved, allowing models to "cheat" by memorizing specific node behaviors rather than learning generalizable structural patterns.
Feature Dependencies and the Identity Trap
To understand why models fail when moving from across-layer to true across-network tasks, the authors categorize features into a 2x2 matrix based on Identity-Dependence and Label-Dependence.
- Identity-Dependent features (like those used in
node2vecorLINK) rely on specific node IDs. These are highly effective for within-network and across-layer tasks but are mathematically useless for across-network tasks where node IDs do not overlap. - Identity-Independent features (like
ReFeXor node degree) rely on structural roles. These are necessary for across-network prediction, but they only work if the attribute being predicted is tied to a universal structural signature (e.g., "high-degree nodes are more likely to be influencers").
Empirical Findings
The study utilized real-world datasets like the FB100 (social networks from 100 disjoint college populations) and the Copenhagen Networks Study to validate this taxonomy.
Key results include:
- The Identity Trap: Models like
LINKperform exceptionally well in within-network and across-layer settings but drop to random chance in true across-network tasks because Node 17 in Network A has no relation to Node 17 in Network B. - Structural Limitations: Even structural models like
ReFeXstruggle across networks if the primary signal is homophily (nodes with the same label clustering together) rather than a distinct structural role. If "being in a cluster" is the only signal, the model cannot tell which attribute that cluster represents in a new network. - The Bridging Effect: The authors demonstrated that adding even a tiny number of "bridge edges" between disjoint networks—effectively turning an across-network task back into a within-network one—causes a massive spike in accuracy for identity-based models.
Conclusion
The paper concludes that the field of graph machine learning needs more rigorous benchmarking. Researchers must explicitly distinguish between within-network, across-layer, and across-network tasks to avoid misleading performance claims. True across-network prediction remains an open challenge that requires moving beyond simple identity-based embeddings toward robust network alignment and structural role discovery.
Summary updated