GLLP: Graph Learning from Label Proportions

Yufei Jin, Jiajun Shen, Yi He, Xingquan ZhuOpenReview 2026 · Submission to ICLR 2026 · Rejected · OpenReview

TL;DR

GLLP (Graph Learning from Label Proportions) is a new framework that solves the challenge of training Graph Neural Networks when individual node labels are unavailable due to privacy or cost. By using Optimal Transport with a "homophily-aware" cost matrix, the authors successfully translate coarse group-level statistics into reliable individual node predictions, outperforming existing methods by an average of 17%.

What Problem Does This Paper Address?

In traditional graph learning, we usually assume we have a "ground truth" label for at least some nodes (e.g., "this user is a bot," "this paper is about AI"). However, in the real world, individual labels are often hidden to protect privacy—like Apple or Google reporting ad conversions only in aggregate—or are simply too expensive to collect.

This leads to a paradigm called Learning from Label Proportions (LLP). Instead of knowing that Node A is Class 1, you only know that in a "bag" of 100 nodes, 30% belong to Class 1. While LLP has been studied for independent data (like images), it hasn't been effectively applied to graphs. The challenge is that nodes in a graph aren't independent; they are connected. Existing LLP methods fail because they ignore this topological structure, treating a group of connected nodes as just a random pile of data points.

Methods

The authors propose GLLP, which bridges the gap between group-level proportions and node-level classification using two main components:

  1. Optimal Transport (OT) with a Homophily-Aware Cost: The core innovation is how GLLP generates "pseudo-labels" for individual nodes. It treats the problem as an Optimal Transport task: how do we best "transport" the known bag-level label proportions to individual nodes?
  2. They design a custom cost matrix that includes a graph penalty. This penalty leverages homophily—the tendency of connected nodes to share the same label. If two nodes are neighbors, the cost of assigning them different pseudo-labels increases.
  3. Alternating Training Scheme: The model doesn't just train once. It enters a loop:
  4. The Graph Neural Network (GNN) makes a prediction.
  5. The OT module uses those predictions and the graph structure to generate refined, structurally consistent pseudo-labels.
  6. The GNN is then updated using a joint loss: a standard KL-divergence loss (to match bag proportions) and a cross-entropy loss (to match the new pseudo-labels).

Datasets

The authors evaluated GLLP on six well-known homophilic graph benchmarks:

  • Citation Networks: Cora, CiteSeer, and PubMed.
  • E-commerce Networks: Amazon-Photos and Amazon-Computers.
  • Knowledge Graphs: WikiCS.
  • Case Study: A simulated COVID-19 outbreak dataset, where privacy concerns make individual infection data unavailable, but aggregate regional statistics are known.

Key Insights and Ideas

  • Topology as a Constraint: The "aha moment" here is that graph structure isn't just an input feature; it’s a powerful regularizer for label distribution. If you know 10% of a group is infected, and you see a cluster of highly connected nodes, the graph structure tells you that the 10% are likely to be clustered together rather than scattered randomly.
  • The Failure of Naive Matching: The paper demonstrates that simply matching bag-level distributions (using KL loss alone) is insufficient for graphs. Without a mechanism to "anchor" labels to specific topological positions, the model struggles to learn the underlying decision boundaries.
  • Theoretical Alignment: The authors provide a mathematical proof (Theorem 1) showing that their graph-regularized cost function produces pseudo-labels that are strictly closer to the true (hidden) labels than methods that ignore the graph.

Key Results

  • Significant Accuracy Boost: GLLP outperformed the best existing LLP baselines (like LLP-MixBag and PT-LLP) by an average of 17% across all datasets.
  • Robustness to Bag Size: Unlike baseline methods, which often saw performance stagnate as more bags were added, GLLP showed a consistent performance increase, effectively "soaking up" the supervision provided by aggregate data.
  • Real-World Utility: In the COVID-19 case study, GLLP successfully inferred individual infection risks using only aggregate statistics, proving its potential for privacy-preserving public health monitoring.

Limitations and Future Work

The primary limitation acknowledged by the authors is the homophily assumption. GLLP is designed for graphs where "like links with like." In heterophilic graphs (where different types of nodes tend to connect, like in a dating app or a predator-prey network), the current graph penalty might actually hurt performance.

Future work involves designing more flexible cost matrices that can adapt to diverse graph topologies and integrating GNN architectures specifically built for heterophilic settings. Additionally, scaling the Optimal Transport solver for extremely large graphs (millions of nodes) remains a practical challenge for future engineering.

Summary updated

Abstract

Learning from Label Proportion (LLP) is a weakly supervised learning paradigm in which only aggregated label proportions over collections of instances (i.e., bags) are provided, rather than individual labels. This allows classification while preserving privacy or reducing annotation costs. Existing LLP methods, however, have been largely restricted to i.i.d. tabular or image data. No solution currently addresses graphs, where instances are inherently interdependent through network structure. In this paper, we generalize LLP to the graph domain and study the problem of node classification with label proportions, where only distributional supervision is available for node bags, and the goal is to infer labels for all nodes in the graph. We argue that the lack of node-level supervision is the main challenge for LLP on graphs, and that existing methods based on i.i.d. assumptions fail to exploit topological correlations. To overcome this, we propose GLLP(Graph Learning from Label Proportions), a framework that leverages Optimal Transport (OT) with a homophily-aware cost to generate soft pseudo-labels for individual nodes. These pseudo-labels provide stronger supervision signals for training Graph Neural Networks. We further establish theoretical guarantees showing the alignment of our cost function with the node classification objective. Extensive experiments on six homophilic graph benchmarks demonstrate that GLLP consistently outperforms existing LLP baselines and variants. Code and benchmark datasets is released in: https://anonymous.4open.science/r/GLLP-2C9E/README.md.
BibTeX
@misc{jin2026gllp,
  author = {Yufei Jin and Jiajun Shen and Yi He and Xingquan Zhu},
  title = {{GLLP: Graph Learning from Label Proportions}},
  year = {2026},
  url = {https://openreview.net/forum?id=dE3i5snJkm},
  howpublished = {OpenReview},
  note = {Submitted to ICLR 2026},
}
Figure