Overview
This paper introduces a framework for learning time-varying coverage functions, which model how the "reach" or "influence" of a set of items grows and exhibits diminishing returns over time. By connecting these functions to stochastic counting processes and using a novel random-feature parametrization, the authors develop an efficient algorithm (TCOVERAGELEARNER) that can estimate influence in social networks more accurately and robustly than traditional model-based approaches.
The Challenge of Dynamic Influence
In fields like social network analysis and economics, we often use coverage functions to model "diminishing returns." For example, if you follow five influential people on Twitter, the sixth person you follow likely provides less new information than the first one did.
Traditionally, these functions are treated as static. However, real-world processes are dynamic: news doesn't hit everyone at once; it spreads over hours or days. Previous research either ignored the time dimension or made rigid assumptions about the underlying "diffusion" mechanism (e.g., assuming news spreads exactly like a virus).
The challenge is learning these functions $f(S, t)$—where $S$ is a set of sources and $t$ is time—directly from data without knowing the "ground truth" network structure or the specific rules of how information flows.
Methodology
The authors bridge the gap between discrete combinatorial functions and continuous time-series analysis using three key steps:
- Counting Process Connection: They model the arrival of events (like "retweets") as a counting process. The "intensity" (the rate at which events happen) is tied to the derivative of the coverage function.
- Random Function Approximation: Inspired by the "random kitchen sinks" technique in machine learning, they represent the complex, time-varying function as a weighted combination of simpler, random kernel functions. This turns an infinite-dimensional problem into a finite, manageable one.
- TCOVERAGELEARNER Algorithm: They frame the learning task as a Maximum Likelihood Estimation (MLE) problem. Because the formulation is convex, they can use efficient optimization tools (like projected quasi-Newton methods) to find the best weights for their random features.
Crucially, this approach is "model-agnostic." It doesn't care if the information spreads via a "cascade" or a "threshold" model; it simply learns the patterns from the timestamps of observed events.
Key Insights
- Robustness through Generality: Most existing tools for social networks require you to guess the "diffusion model" correctly. If you guess wrong, your predictions fail. TCOVERAGELEARNER is more robust because it learns the coverage function directly from the data, making it less sensitive to "model misspecification."
- The Power of Random Features: By using random change points to build their basis functions, the authors can approximate any smooth, monotonic time-varying coverage function. This allows the model to scale linearly with the number of features.
- Theoretical Guarantees: The paper provides a "sample complexity" analysis, proving that the algorithm can learn the true function with a polynomial number of samples—a vital "sanity check" for any machine learning algorithm.
Experimental Results
The authors evaluated their approach on both synthetic data (simulating information diffusion using standard models like Continuous-time Independent Cascade) and real-world data (MemeTracker, tracking how short phrases spread across websites).
Superior Accuracy on Synthetic Data: On synthetic data, TCOVERAGELEARNER consistently achieved lower Mean Absolute Error (MAE) than baselines like Kernel Ridge Regression. Even when competing against models that were given "extra" information (like the identity of every node reached), the proposed method remained highly competitive.
Real-World Performance and Scalability: On the MemeTracker dataset, the algorithm showed consistent and robust estimation across seven different groups of cascades, outperforming standard baselines. Furthermore, the runtime scales linearly with the number of random features, making it practical for large-scale social media datasets. The authors also demonstrated that their learned functions could effectively solve the "influence maximization" problem (picking the best people to start a trend), matching the performance of more complex, specialized models.
Limitations and Future Work
- Feature Selection: The strategy for picking random features relies on historical data. If the training data is very sparse, the chosen features might not represent the full domain well.
- Computational Complexity: While the optimization is convex, the worst-case complexity is $O(mnW)$ (where $m$ is samples, $n$ is items, and $W$ is features). For extremely large networks with millions of nodes, further optimizations might be needed.
- Future Directions: The authors suggest that this framework could be extended to other submodular functions beyond simple "coverage," potentially opening doors to more complex economic modeling.
Summary updated