Geometric-DQN: Reimagining Influence Maximization in the Dark
Influence Maximization in Unknown Social Networks: Learning Policies for Effective Graph Sampling
The paper introduces Geometric-DQN, a Deep Reinforcement Learning framework designed for Influence Maximization in unknown social networks. It learns an adaptive sampling policy to discover a subgraph that effectively identifies influential nodes, outperforming hand-crafted heuristics like CHANGE.
TL;DR
When deploying interventions—like HIV prevention programs—social workers often don't have a map of who talks to whom. Mapping the whole network is too expensive. This paper introduces Geometric-DQN, an AI agent that learns how to "scout" a social network. By querying just a few people, it builds a mental model of the hidden graph and finds the most influential leaders, achieving a 7-23% boost in performance over traditional human-designed sampling rules.
The "Invisible Network" Problem
Most research on Influence Maximization (IM) assumes we already have the graph (who is connected to whom). In reality, social networks in vulnerable populations—such as homeless youth—are hidden. To find influencers, we must conduct surveys, but each survey is a "cost."
Previous methods like CHANGE used a rule of thumb: pick a random person and then ask about their friend (leveraging the Friendship Paradox, which suggests your friends are more popular than you). While clever, these hand-crafted rules ignore the nuanced structural patterns (clusters, bridges, hierarchies) that vary from one community to another.
Methodology: Designing the "Geometric" Scout
The authors treat network discovery as a sequential game. At each step, the agent chooses a node to "query" to reveal its neighbors.
1. The Architecture
The core innovation is the Geometric-DQN. Traditional DQNs struggle with graphs because the number of possible actions (nodes to query) changes as the graph grows. The authors solved this by combining:
- Global State (DiffPool): A GNN that "crunches" the discovered graph into a single vector representing the community's overall structure.
- Local Actions (DeepWalk): Vector embeddings for each individual node that capture its local neighborhood.
2. Overcoming Data Scarcity
Since there isn't much real-world "social network" data for training, the team used Stochastic Block Models (SBM). They trained the AI on synthetic clusters that mimic real-world density and community patterns, allowing the agent to generalize to totally unseen environments.
Experiments and Results
The agent was tested on four diverse domains:
- Rural Networks: Micro-finance diffusion in India.
- Animal Interactions: Physical contact between voles.
- Retweet Networks: Information flow on Twitter.
- Homeless Youth: HIV prevention networks in LA.
Performance Comparisons
Geometric-DQN consistently outperformed the SOTA baseline. In "Animal" networks, the improvement was as high as 26.6%, proving the agent's ability to navigate different topologies.
Deep Insight: What Did the AI Learn?
Post-hoc analysis revealed that the AI wasn't just guessing. It learned to prioritize nodes with high Betweenness Centrality. These are "bridge" nodes that connect different social silos. By finding these bridges early, the agent can "jump" from one cluster to another, mapping the network's skeleton much faster than a human-designed random walk.
Conclusion & Future Outlook
Geometric-DQN shifts the paradigm from hand-designed heuristics to learned strategies. For social scientists and public health officials, this means more effective "word-of-mouth" campaigns with less administrative overhead. The next step? Applying this to dynamic networks where social ties change in real-time.
Takeaway: In the world of hidden graphs, a smart scout is worth a thousand random surveys.