Many security and privacy problems can be modeled as a graph classification
problem, where nodes in the graph are classified by collective classification
simultaneously. State-of-the-art collective classification methods for such
graph-based security and privacy analytics follow the following paradigm:
assign weights to edges of the graph, iteratively propagate reputation scores
of nodes among the weighted graph, and use the final reputation scores to
classify nodes in the graph. The key challenge is to assign edge weights such
that an edge has a large weight if the two corresponding nodes have the same
label, and a small weight otherwise. Although collective classification has
been studied and applied for security and privacy problems for more than a
decade, how to address this challenge is still an open question. In this work,
we propose a novel collective classification framework to address this
long-standing challenge. We first formulate learning edge weights as an
optimization problem, which quantifies the goals about the final reputation
scores that we aim to achieve. However, it is computationally hard to solve the
optimization problem because the final reputation scores depend on the edge
weights in a very complex way. To address the computational challenge, we
propose to jointly learn the edge weights and propagate the reputation scores,
which is essentially an approximate solution to the optimization problem. We
compare our framework with state-of-the-art methods for graph-based security
and privacy analytics using four large-scale real-world datasets from various
application scenarios such as Sybil detection in social networks, fake review
detection in Yelp, and attribute inference attacks. Our results demonstrate
that our framework achieves higher accuracies than state-of-the-art methods
with an acceptable computational overhead.

本文提出了一种新颖的集合分类框架来解决安全和隐私分析中长期存在的挑战 —— 如何分配边缘权重，以获得更高的精度。通过将学习边缘权重和传播信誉度称为联合优化问题，我们可以同时解决这两个问题，并获得比传统方法更高的准确性。

基于图的安全和隐私分析，通过联合权重学习和传播进行集体分类

Graph-based Security and Privacy Analytics via Collective Classification  with Joint Weight Learning and Propagation

In a series of recent works, we have generalised the consistency results in
the stochastic block model literature to the case of uniform and non-uniform
hypergraphs. The present paper continues the same line of study, where we focus
on partitioning weighted uniform hypergraphs---a problem often encountered in
computer vision. This work is motivated by two issues that arise when a
hypergraph partitioning approach is used to tackle computer vision problems:
(i) The uniform hypergraphs constructed for higher-order learning contain all
edges, but most have negligible weights. Thus, the adjacency tensor is nearly
sparse, and yet, not binary. (ii) A more serious concern is that standard
partitioning algorithms need to compute all edge weights, which is
computationally expensive for hypergraphs. This is usually resolved in practice
by merging the clustering algorithm with a tensor sampling strategy---an
approach that is yet to be analysed rigorously. We build on our earlier work on
partitioning dense unweighted uniform hypergraphs (Ghoshdastidar and Dukkipati,
ICML, 2015), and address the aforementioned issues by proposing provable and
efficient partitioning algorithms. Our analysis justifies the empirical success
of practical sampling techniques. We also complement our theoretical findings
by elaborate empirical comparison of various hypergraph partitioning schemes.

本文基于之前的研究，在计算机视觉中解决超图分割的问题，并提出可以证明的高效分割算法，同时对各种超图分割方案进行了详细的实证比较。

统一超图划分：可证张量方法和采样技术

Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling  Techniques

We propose a framework that learns the graph structure underlying a set of
smooth signals. Given $X\in\mathbb{R}^{m\times n}$ whose rows reside on the
vertices of an unknown graph, we learn the edge weights
$w\in\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that
$\text{tr}{X^\top LX}$ is small. We show that the problem is a weighted
$\ell$-1 minimization that leads to naturally sparse solutions. We point out
how known graph learning or construction techniques fall within our framework
and propose a new model that performs better than the state of the art in many
settings. We present efficient, scalable primal-dual based algorithms for both
our model and the previous state of the art, and evaluate their performance on
artificial and real data.

本文提出了一种基于平滑信号的图形结构学习框架，可以通过学习边权重和已知顶点位置的图，实现自然的稀疏解，且提出的方法在许多场景下表现出更好的性能。

如何从平滑信号中学习图形

How to learn a graph from smooth signals

In the Network Inference problem, one seeks to recover the edges of an
unknown graph from the observations of cascades propagating over this graph. In
this paper, we approach this problem from the sparse recovery perspective. We
introduce a general model of cascades, including the voter model and the
independent cascade model, for which we provide the first algorithm which
recovers the graph's edges with high probability and $O(s\log m)$ measurements
where $s$ is the maximum degree of the graph and $m$ is the number of nodes.
Furthermore, we show that our algorithm also recovers the edge weights (the
parameters of the diffusion process) and is robust in the context of
approximate sparsity. Finally we prove an almost matching lower bound of
$\Omega(s\log\frac{m}{s})$ and validate our approach empirically on synthetic
graphs.

研究图网络推断问题，探讨基于稀疏恢复的级联模型，提出第一个可以高概率和 O（slog m）的测量找到图的边缘的算法，并能恢复边权及适用于近似稀疏条件下的情景。最后，通过人造数据验证了本算法的可靠性及降低边缘误差和参数估计误差的能力。