Skip to content

Graphs Help Graphs: Multi-Agent Graph Socialized Learning

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper introduces Graph Socialized Learning (GSL), a new multi-agent collaborative learning paradigm for heterogeneous dynamic graph settings, and proposes the "Graphs Help Graphs" (GHG) method to address information collapse and catastrophic forgetting. GHG uses a graph-driven organizational structure, demand-customized synthetic graph generation as an interaction medium, and a prototype-based life cycle for lossless task memory. On seven node-classification benchmarks, GHG substantially outperforms all federated, lifelong, and combined baselines.

Problem

Real-world graphs are fragmented across agents (platforms, institutions) and grow dynamically over time. Existing Graph Federated Learning (GFL) methods suffer information collapse—parameter sharing across heterogeneous graphs fails to transfer sufficient knowledge and ignores directed agent dependencies. Graph Lifelong Learning (GLL) methods address dynamics but only for a single agent and exhibit catastrophic forgetting of old tasks. Combining GFL and GLL naively (GFLL) does not resolve either pathology.

Method

GHG decomposes multi-agent heterogeneous dynamic graph collaboration into three components:

  1. Graph-Driven Organizational Structure (Who): A directed, weighted collaboration graph is built by quantifying pairwise complementarity (via principal angles between SVD subspaces of agent outputs) and similarity (cosine distance over enhanced parameters concatenated with Laplacian-smoothed topology embeddings). Edge weights are solved via a constrained optimization that balances relative graph size, complementarity, and similarity. A top-K sparsification selects collaborators per agent.

  2. Customized Interactive Medium (What): Instead of sharing raw graphs or parameters, each agent generates synthetic graphs tailored to the receiving agent's per-class demand. Fine-grained class-level collaboration weights determine the class composition of synthetic graphs. Synthesis minimizes a distribution alignment loss matching mean and standard deviation of multi-hop node embeddings between synthetic and neighbor graphs. A unit adjacency matrix is used for synthetic graphs, avoiding a learned adjacency generator.

  3. Prototype-Based Life Cycle (When): Upon completing each task, task prototypes are constructed by averaging synthetic-graph node representations from neighbor agents. At test time, the prototype pool is queried by similarity to select the optimal task ID and retrieve the corresponding frozen task-specific prompts and classifier head, achieving zero forgetting without storing raw data.

Training augments standard cross-entropy loss with KL divergence (agents imitate neighbor predictions) and synthesis loss. A pre-trained GNN backbone is frozen; only task-specific prompts and classifier heads are learned per task.

Key Contributions

  • Formal definition of the Graph Socialized Learning (GSL) paradigm and generalization bound proving that collaborative synthetic and KL distributions tighten the error bound over single-graph training (Theorem 1, Proposition 1).
  • Graph-driven directed organizational structure replacing undirected symmetric federation topologies, enabling autonomous asymmetric collaboration.
  • Demand-customized synthetic graph generation as a privacy-preserving, information-rich interaction medium.
  • Prototype-based life cycle enabling 0% average forgetting (MAF = 0) across all seven datasets under strong heterogeneity.

Results

  • CoraFull (strong het): GHG MAP = 54.0% vs. best baseline GFLL (Fed-DMSG) 37.3%; MAF = 0.0% vs. 0.1%.
  • Arxiv: MAP = 59.2% vs. 22.7% (Fed-DMSG); MAF = 0.0%.
  • Reddit: MAP = 86.7% vs. 61.4% (Fed-DMSG); MAF = 0.0%.
  • Cora: MAP = 79.2% vs. 58.7% (Fed-TPP); MAF = 0.0%.
  • CiteSeer: MAP = 65.7% vs. 51.7% (Fed-TPP); MAF = 0.0%.
  • SLAP: MAP = 62.4% vs. 27.2% (Fed-TPP); MAF = 0.0%.
  • Computers: MAP = 82.5% vs. 36.7% (TPP); MAF = 0.0%.
  • Ablation confirms each component contributes incrementally; B → B+Lsyn → B+Lsyn+Lce → full model.
  • Customized synthesis outperforms random graph sampling by ~10% on Cora.
  • GHG peaks performance at 4 interaction rounds, fewer than competing methods.

Limitations

  • Scalability to large-scale multi-agent systems is acknowledged as an open problem; experiments use at most 20 agents.
  • Performance degrades as agent count increases (more dispersed graphs), with a non-monotonic edge case at low participation ratio δ=0.2.
  • Relies on a pre-trained GNN backbone; quality of the frozen representations is a prerequisite.
  • Evaluated only on node classification; generalization to other graph tasks (link prediction, graph classification) is untested.
  • Real-world application datasets not yet evaluated—only benchmarks.

Relevance to Agentic AI / LLM Agents

GHG is a concrete instantiation of the "who/what/when" coordination problem central to multi-agent systems: how autonomous agents should select collaborators, determine what information to share, and manage shared state over time. The directed graph-based organizational structure and demand-driven synthetic information exchange are architectural primitives transferable to LLM agent collectives, where heterogeneous context distributions and continual task accumulation pose similar collapse-and-forgetting challenges. The prototype-based life cycle mirrors episodic memory retrieval mechanisms being explored in long-horizon LLM agents. The formal generalization analysis provides a theoretical lens for reasoning about when agent collaboration actually helps versus hurts in heterogeneous settings.