GraMeR:Graph Meta Reinforcement Learning for Multi-Objective Influence Maximization

Consider a directed graph $G=(V,E,\omega)$, where $V$ is a set of vertices, $E$ is a set of edges (pairwise relationships on vertices), and $\omega$ is a set of edge weights; a diffusion model, and a budget $k$. Influence maximization (IM) is the problem of identifying a set of $k$ seed nodes, which when activated, will result in the activation of a maximal number of nodes in $G$, for the given diffusion model of influence. IM has applications in various domains ranging from viral marketing in social networks to influential proteins in biological networks. For instance, one of the reasons behind the tremendous success of social media platforms is the quality of content the users create or generate via sharing. These actions can be attributed to influence dynamics in the social network. IM was first introduced in 2001 and was formulated as a combinatorial optimization problem by [1]. Majority of the IM algorithms focus on settings where seed nodes are activated deterministically and then neighborhood nodes are activated via influence. However, there exists two types of activation in real-life scenarios, namely intrinsic and influenced [2]. In case of social media, intrinsic refers to users who post content whereas sharing, retweeting, commenting constitute influenced activation. To this end, the authors in [3] recognize that the events on social media can be categorized as exogenous and endogenous and model the overall diffusion through a multivariate Hawke’s process to address activity shaping in social networks. In another recent work [4], the authors propose a novel diffusion model based on factor graphs and graphical models where the node potentials can correspond to the notion of intrinsic activation. However, the focus of their work is on the diffusion model itself, not on the aspects of intrinsic activation.

Furthermore, despite the huge potential of IM, its field uses are limited due to the computational inefficiency of conventional greedy algorithms. Therefore, recently, there have been studies that use Reinforcement learning (RL) to learn generalized policy for combinatorial optimization problems on graphs [5, 6, 7] including IM. The key idea is to decompose the node selection process into a sequence, and learn a heuristic policy that selects nodes sequentially. The RL policy is usually trained on a set of seen training graphs, in the hope that it generalizes to unseen test graphs of similar characteristics. To better generalize the trained policy across different graphs, graph embedding techniques, such as Structure to Vector (S2V)[5] and Graph Convolutional Networks (GCNs) [8] are integrated as part of the RL value functions to extract the graph structure information. Primarily proposed to solve relatively simple tasks such as the traveling salesman problem (TSP) and the maximum vertex cover (MVC), some of the recent works [9, 10] extend it to the IM problem. However, they possess following shortcomings: (1) Formulation: Existing works such as GCOMB, S2V-DQN and GCN-TREESEARCH addresses a trivial IM problem without explicitly accounting the intrinsic and influence activations. Thus, these methods could not work effectively in real-world scenarios. (2) Computational complexity: Most of the conventional IM works such as CHANGE and [2] are computationally complex and thus possess limitations in transitioning solution to real-life uses. These methods require re-computation of IM nodes whenever a underlying network changes and usually the stakeholders do not have the HPCs to perform repetitive computation. (3) Scalability: To counter computational complexity of existing IM algorithms, RL based learning algorithms have been recently proposed in the literature. The primary focus of these methods (S2V-DQN and RL4IM) are on obtaining high quality results. Howevever, the efficiency studies are limited to graphs containing only hundreds of thousands of nodes. Real-life graphs may contain millions of nodes/edges. (4) Generalizability: Existing methods such as S2V-DQN, GCOMB and RL4IM does not systematically account for graph variation, i.e., trained RL model would work only on graphs of similar characteristics.

[11] and [1] constitute the seminal work that introduced Influence Maximization (IM) and provided a practical approach to solve it. This work was followed by several other works that explored various diffusion models and variations to the one discussed in [1] namely, the independent cascade (IC) model and the linear threshold model. For instance, in [12], the authors consider the task of identifying the individuals whose strong positive opinion about a product will maximize the overall positive opinion about the product. In the process, the authors leverage the social influence model proposed by Friedkin and Johnsen [13]. In recent works [4, 3], the authors recognize several types of activations in social network and propose methods to identify seed nodes under these activations.

Although the IM literature has become mature enough to tackle various real-world network scenarios, there exists a serious limitation attributed to the high computational costs in various applications [14, 15, 16]. Therefore, AI/ML community focused on developing algorithms for such computationally exhaustive tasks ranging from node identification tasks to combinatorial optimization on graphs [17, 18, 19]. The existing literature for combinatorial and graph problems can be broadly divided into two types: First, algorithms that pose combinatorial optimization into a sequential decision-making process and learn heuristics to support the primary optimizer [20, 21]. The application includes graph discovery in social network, restoration routes in critical infrastructure networks among others [22, 23]. Major drawbacks of these approaches are generalizability and data inefficiency. Therefore, the second category of work focuses on novel graph machine learning algorithms to tackle these shortcomings. Particularly, reinforcement learning (RL) can be used for solving graph optimization problems. However, functional approximators in conventional RL algorithms are not powerful enough to learn complex tasks. The advent of deep learning significantly boosts the approximation capability and enables RL to solve several tasks that were not possible before. [24] is one of the pioneering works in deep reinforcement learning (DRL), which combines attention-based function approximator with policy gradient Deep RL algorithms. Further, graph convolutional networks are more appropriate for capturing topological information in graphs. In this regard, [6] approximate solution with graph convolutional networks (GCN) embeddings, and uses a learning framework based on guided tree search to approximate DRL solutions. Moreover, there are some works where RL is combined with GCN to solve the traveling sales man problem [7]. Similarly, authors in [25], solved the widely known Knowledge Graph (KG) completion problem with DRL. Particularly, they employed GCN to learn a representation of KG and then use a deep deterministic policy gradient algorithm to estimate missing relationships.

Specific to IM, Li et al. and Tian et al. are a few efforts to solve the IM problem using deep Q learning. Here, reward corresponds to marginal gain in influence spread, and agent learns to find a node set that has maximum spread. Manchanda extended the method in Khalil by solving IM problem for very large graphs [9]. Specifically, it has a separate module to predict node quality which is fed as an input to the DRL agent. This induces computational burden in the training pipeline and the method of predicting node quality is not systematic. Recently, [10] developed a DRL algorithm for realistic IM by considering node willingness to be seed node. However, it requires the adjacency matrix as an input, and therefore, unscaleable for large graphs. In this paper, we propose a novel formulation for solving IM that addresses some of the challenges that we discussed so far.

The overall architecture of the proposed framework (GraMeR) is depicted in Fig. 1, and consists of three main modules. Each of these modules is explained in forthcoming sections. In this section, we describe the IM model considered in our work. It is reasonably different and generic relative to typical IM models explored in related recent work. In a social network, users propagate their views or opinions while simultaneously consuming and reacting to content created by friends, people, and organizations they follow. Thus, there are two ways of activation, namely intrinsic (content creation) and spread of influence (content spreading). Conventional IM problem solely considers influence activation and overlooks intrinsic activation. However, in practice, the role of content creators has gained significant importance due to massive digitization. Therefore, in this work, we are considering a generic formulation of IM that incorporates both types of activations and is referred to here as activation-informed influence maximization (AIM).

Enabled by the digital revolution, most users now are both content creators and content spreaders at the same time. This is probabilistically modeled through parameters $p_{s}$ and $p_{f}$ which represent the probability of intrinsic and influence activation, respectively. Intrinsic activation for a user $u$ is based on its own activities, and user $u$ is assumed to be directly influenced by its 1-hop neighbors. Therefore, the influence part of the probability for activation is comprised of the activation probabilities due to the 1-hop neighbors of user $u$. Thus, similar to the IC model, the probability of user $u$ being activated via influence of an user $v$ is written as:

where the weights $w_{uv}$ $(0\leq w_{uv}\leq 1)$ can be determined from the user interactions in a network. The described probabilistic formulation has similarities to the Friedkin-Johnsen social influence model for opinion change [13], where the authors recognize that the dynamics of opinion change are governed by two mechanisms: intrinsic opinion and influenced opinion. Furthermore, by assuming that the nodes are not lazy and are activated by either of the two mechanisms that we outline, we set $P_{f}(u)=(1-P_{s}(u))$. This renders the overall IC probability between nodes $v$ and $u$ to be:

Note that all the parameters discussed can be efficiently determined either by a maximum-likelihood-based approach or expectation-maximization (EM) approach as followed in [26]. For example, in the Twitter network, the proportion of tweets by a user $i$ that are intrinsic in nature can quantify $P_{s}(u)$, while a particular weight $w_{uv}$ can be determined by the proportion of user $u’s$ retweets (or influenced activity) having their origin in the activity of user $v$ that user $u$ follows.

A fundamental aspect of our framework is the fact that only a certain fraction of nodes are likely to contribute to the AIM solution set. These nodes are referred to as “candidate nodes” in this work. Hence, it is desirable that instead of focusing on all nodes, one should attempt all computationally expensive predictions for the candidate nodes. This section describes a novel GNN based node classifier that leverages GNN based classifier to identify candidate nodes for AIM. This classifier precedes our primary DRL algorithm (GraMeR) as shown in Fig. 1, and thereby eases the computational burden.

The task of identifying candidate nodes is framed as a binary node classification problem where the two classes denote “candidate” and “non-candidate” nodes, respectively. The ground truth labels can either be generated via standard greedy hill climbing algorithm or novel centrality metrics recently being proposed [27, 18]. This work uses Influence capacity metric as it is computationally easy to compute compared to other approaches. Influence capacity (IFC) is a novel centrality metric to identify influential nodes. The influence of any node depends on its neighbor connection (local influence) and its own location in the graph (global influence). Local influence of a node $u$ ($I_{L}(u)$) can be estimated as [27]:

where, $P$ is the influence probability associated with links, and the operator $N(.)$ denotes the neighbors. Likewise, the global influence score ($I_{G}(u)$) can be expressed as:

where, $k_{c}(u)$ and $D(u)$ represent coreness score and degree of node $u$, respectively. Notation $D_{N}$ denotes maximum node degree in the graph. The overall influence capacity $I(u)$ of a node $u$ can then be written as:

Nodes retaining extreme values of IFC are labeled as “candidate nodes” while the rest of the nodes are marked as “noncandidate”. The threshold of approx $20\%$ seems to work in our case and it is determined based on several experiments, where the candidacy of nodes is validated with the standard Greedy hill-climbing algorithm. The ground truths from IFC are then leveraged to train the node classifier without relying on a computationally exhaustive Greedy hill-climbing approach [16]. It is important to note that there are various other algorithms to generate groundtruth and one can take any such approach for training the node classifier.

The GNN based node classification model consists of two hidden layers with GraphSAGE as the message-passing algorithm. We selected GraphSAGE since the computation graph for any node $u$ only depends on the induced subgraph up to $k$-hop neighbors of $u$. This allows training/prediction across different graph sizes which is most desirable for GraMeR. The parameters of GNN are trained by minimizing the categorical cross-entropy loss function. The overall candidate node prediction task is summarized in Algorithm A.1 in the appendix. It is interesting to note that if this GNN classifier can provide a confidence interval around its class predictions as shown in [28], then the succeeding DRL engine can utilize that interval while searching for optimal seed nodes. This further strengthens the overall framework and is kept as future work.

Graph Meta Reinforcement Learner (GraMeR) is a deep reinforcement learning (DRL) based framework that learns to identify optimal seed set for AIM. There are various novel aspects of our framework in terms of: (1) Meta learning to enable prediction across different graph types and sizes; (2) double Q learning to estimate sequence of seed nodes without solving a computationally intensive optimization problem at every test time and (3) single policy multi-objective reward formulation for systematic balancing of multiple AIM objectives. This section describes these novel aspects of GraMeR, and architecture is shown in Fig. 1.

This section validates the proposed framework against modified greedy hill-climbing algorithm (MGHC) and S2VDQN. GraMeR offers improved performance with more flexibility while being orders of magnitude faster. The performance is examined on standard networks, namely Barabasi Albert, Power law cluster, stochastic block models. As per the architecture, $1^{st}$ phase of the local Q-network ($Q^{L}$) comprises of $3$ GNN layers for generating node embeddings. The number of neurons in these layers are $64$, $32$ and $16$, respectively. This phase generates state, action and graph embedding vectors which are concatenated into a vector and passed through a regression phase of the $Q^{L}$ network. Regression phase consists of $2$ feedforward layers with $16$ and $1$ neurons respectively. All other settings have been discussed in the appendix.

We presented a GNN fused meta reinforcement learning framework (GraMeR) for identifying influential nodes in a network. Firstly, the search space of IM is reduced via GNN based candidate node predictor. Then deep Q learning is employed to learn to identify IM seed nodes with GNN as environment encoders. The unique aspects of GraMer lies in its computational efficiency and generalizability. Future directions of research include extension of GraMeR for uncertain networks suited for financial/manpower constraint applications.